Este trabalho apresenta um estudo sobre a classificação de imagens digitais através da textura com o auxílio de redes neurais. São utilizadas técnicas e conceitos de duas áreas da Informática: O Processamento de Imagens Digitais e a Inteligência Artificial. São apresentados os principais tópicos de processamento de imagens, as principais aplicações em tarefas industriais, reconhecimento de padrões e manipulação de imagens, os tipos de imagem e os formatos de armazenamento. São destacados os atributos da imagem a textura e sua quantificação através da matriz de concorrência dos níveis de cinza. Também apresenta-se alguns sistemas computacionais disponíveis para processamento de imagens. Na área de Inteligência Artificial, o enfoque é para técnicas computacionais inteligentes, mais especificamente as Redes Neurais. É feita uma breve apresentação da área, incluindo seu histórico e suas principais aplicações. As redes neurais são classificadas quanto ao tipo de treinamento, à regra de aprendizado, à topologia da rede e quanto ao tipo de interconexão dos neurônios. O modelo BPN (BackPropagation Network) é visto com maior detalhe, visto ser utilizado na implementação do sistema IMASEG (Sistema para Classificação de Imagens) que faz parte desse trabalho. O BPN é descrito quanto ao seu funcionamento, a forma de aprendizado e as respectivas equações utilizadas. O sistema IMASEG foi desenvolvido com o objetivo de implementar as técnicas propostas para a classificação de imagens utilizando textura e redes neurais. Seu funcionamento e algoritmos utilizados são detalhados e ao final, apresenta-se os resultados obtidos com a respectiva análise. A classificação de imagens é uma das principais etapas no processamento de imagens digitais. Dado um conjunto de classes e um padrão apresentado como entrada para o sistema, o problema consiste em decidir a que classe o padrão pertence. Deve haver a alternativa de rejeição do padrão. Podemos extrair da imagem atributos espectrais, espaciais e de contexto. Por serem mais facilmente quantificáveis, a maioria dos sistemas tradicionais utiliza apenas atributos espectrais para caracterizar uma imagem. Essa abordagem é muito utilizada em imagens multiespectrais. Entretanto, utilizando apenas atributos espectrais, não se obtém uma informação completa sobre a imagem, pois não são levados em consideração as relações espaciais entre seus pixels, bem como a forma de objetos. A textura, atributo espacial, é ainda pouco utilizada, visto que tem origem na sensação visual causada pelas variações tonais existentes em uma determinada região da imagem, tornando difícil sua quantificação. Neste trabalho, é feito um estudo sobre a utilização dos atributos espaciais da imagem no seu processamento. É feita uma análise do comportamento de cinco deles: média, desvio-padrão, uniformidade, entropia e contraste, todos extraídos de janelas pertencentes à uma classe. A uniformidade, entropia e contraste provém da matriz de concorrência dos níveis de cinza. Através do cálculo do valor desses atributos em diversas imagens, constata-se que existem algumas importantes relações entre eles. A partir da análise dos diferentes modelos de redes neurais e das diversas formas de quantificar a textura de uma imagem, é proposto um sistema computacional com o objetivo de classificar imagens. Esse sistema faz o processamento das imagens através de uma janela móvel. O usuário deve escolher o tamanho para a janela: 3x3, 5x5 ou 7x7 pixels. Essa escolha irá depender do tipo e da granularidade da textura que a imagem contém. Em seguida, utilizando a janela, deve selecionar amostras representativas de cada textura (classe) presente na imagem que se deseja classificar. O sistema então, encarrega-se de treinar a rede neural utilizando as amostras selecionadas pelo usuário. Para realizar o treinamento, é necessário encontrar uma forma de mapear os dados da realidade para a rede neural. Essa tarefa nem sempre é trivial. Nesse sistema, são propostas duas abordagens para realizar essa tarefa. Na primeira, o mapeamento é feito através do cálculo das feições da média, desvio-padrão e uniformidade, sendo esse último obtido da matriz de concorrência. Essas feições, após um escalonamento para a mesma faixa de valores, serão os parâmetros de entrada para a rede neural. Na segunda abordagem, o mapeamento é direto, ou seja, o valor de cada pixel, após o escalonamento, corresponde a uma entrada da rede neural. Após a etapa de treinamento, a imagem é processada por inteiro, fazendo-se uma varredura com a janela, gerando como saída uma imagem temática na qual cada tema representa uma das texturas existentes na imagem original. Para testar o sistema IMASEG, foram geradas várias imagens sintéticas com 256 níveis de cinza. Deste total, foram selecionadas 6 imagens para serem apresentadas nesse trabalho. Elas são representativas das diversas situações que podem ocorrer em relação aos valores da média, desvio-padrão e uniformidade. Cada imagem original é processada pelas duas abordagens, gerando duas imagens de saída. É feita uma análise quantitativa e qualitativa dos resultados obtidos, apontando-se as prováveis causas de sucessos e problemas encontrados. Conclui-se que a classificação por textura atinge o objetivo proposto e é muito útil no processamento de imagens, levando-se em consideração os bons resultados obtidos. / This paper is a study about the classification of digital images through texture with the aid of neural networks. The techniques and concepts from the field of Computer Science employed are: Digital Images Processing and Artificial Intelligence. The focus in Image Processing is on its main application in industrial tasks. pattern recognition and image manipulation, the types of images and the storing formats. The specific aspects analyzed are image attributes, texture and its quantification through the Coocurrence Matrix. Several available computing systems for image classification are presented. In Artificial Intelligence, the attention is concentrated on intelligent computational systems, more specifically on the neural networks which are briefly introduced. The subject's historical data and its main application are also addressed. The neural networks are classified according to the type of training, the learning rules, the network topology and the interconnection of neurones. The BPN model (Back Propagation Network) is examined more closely since it is employed in the implementation of the IMASEG system (classifying images system) which is part of this study. The BPN system is described in according to its functioning capacities, the learning method and the respective equations utilized. The IMASEG system was developed with the specific aim of implementing the techniques of image classification. Throughout the paper, the system's operation and related algorithms are presented to the reader, as well as the results obtained and the analysis performed provided in the end of the paper The image classification is one of the principal steps for the processing of digital images. It consists to decide of which class the pattern belong. It can refuse the pattern. We can extract spectral, spatial and contextual image's attributes. Because they are easily quantified, a major part of the traditional systems of image processing employ only the spectral attributes to work the images and are, therefore, extensively used in the processing of multispectral images. However, the exploration of ima ges through spectral attributes is not enough to provide a complete recognition of the image since information such as spatial relations among its pixels as well as the form of objects are not taken into consideration. The use of image processing with spatial attributes is also considered in this paper. Texture is still not a commonly employed attribute. This is due to the fact that its based on visual sensation which is produced by the existing tonal variations of a specific image region, making its quantification a difficult task to perform. A behavior analysis of the spatial attributes under consideration in this paper are the following: mean, standard deviation, uniformity, entropy and contrast. These five attributes were all taken from windows belonging to a single class. Uniformity, entropy and contrast are issued from the gray level coocurrence matrix. Via a calculation of the value of these attributes is observed that there is an important relationship among them. This paper proposes a system of image classification based on the analysis of different models of neural networks and also through the analysis of the diverse ways of quantifying the texture of an image. This system performs the image processing through a shifting window. Then, the user must choose the window's size from among the following dimensions: 3x3, 5x5 or 7x7 pixels. The choice will vary depending on the type and on the image's texture granularity. The selection of meaningful samples of each texture (class) present in the image one wishes to classify is the next step in the process. The system, then, is in charge of training the neural networks by applying the user's selected samples. In order to perform the training, it is necessary to first establish a way of mapping the data reality to the neural network, oftentimes a difficult task. In this system two approaches are proposed for the execution of this task. In the first, the mapping is done through the calculation of the mean, standard deviation and uniformity features. The last item is obtained from the coocurrence matrix. After these features have been scaled to the same value band, they will become the input to the neural networks. In the second approach, it is expected that the neural network will be able to extract textures attributes without executing an explicit calculation exercise. After the training phase, the image is completely processed through a window scanning generatin g a thematic image as the output onto which each theme will represent one of the texture's original image. In order to verify the adequacy of the IMASEG system, several synthetical graylevel images were created. Of these, 7 images were chosen as objects for this analysis, representing the various possible situations that might occur in relation to the average, standard deviation and uniformity. Each original image is processed in according with these two chosen approaches, thus generating two images as outputs, as well as a quantitative and qualitative analysis of the obtained results, pointing to the probable successes and failures generated. The final conclusion is that the classification through texture partially attains the proposed objectives and can be very useful in the processing of images, serving as an aid in the traditional classification process.

Ecocardiografia fetal é uma importante ferramenta para diagnóstico. Esta tese apresenta um método que provê localização automática de cavidades cardíacas em imagens ecocardiografias fetais, onde o diagnóstico de problemas congênitos do coração pode melhorar os resultados do tratamento. As estruturas de interesse são as quatro cavidades cardíacas (átrio direito, átrio esquerdo, ventrículo direito e ventrículo esquerdo). O método é baseado na busca por cavidades cardíacas através de uma molde de busca (template) para encontrar padrões de interesse. Este molde é calculado usando uma função densidade probabilidade que recebe como parâmetro os níveis de cinza de uma região representativa da cavidade, na imagem. Além disso, em alguns testes também foram utilizadas características espaciais da imagem para cálculo do molde de busca. Nesse sentido a busca é implementada de uma forma hierárquica: (i) primeiro, é localizada a região do coração; e (ii) em seguida, baseando na região do coração a cavidade de interesse á buscada. A comparação do molde de busca e as regiões de interesse na imagem é feita utilizando o Coeficiente de Bhattacharyya, o qual é analisado ao longo dos testes para justificar sua escolha. Uma das principais características do método é a invariância a rotação apresentada pelas estruturas. / Fetal echocardiography is an important tool for diagnosing. This thesis presents a method to provide automatic localization of cardiac cavities in fetal echocardiography images, where the early diagnostics of heart congenital diseases can greatly improve results from medical treatment. The structures of interest are the four cardiac cavities (left and right atrium, left and right ventricle). The method is based in the search of cardiac structures with a mold to find the pattern of interest. This mold is calculated using a probability density function that receives as parameter the gray level of a representative image and also uses spatial features of the images to calculate the mold. A hierarchical search is performed: (i) first, the region of interest is covered to locate the heart; and (ii) based on the position of the heart, the desired structure is found in the image. The comparison of the mold and the candidate image is made using the Bhattacharyya coefficient, which our experimental tests have shown good results. One of the main characteristics of the method is its rotation invariance.

O estudo das propriedades de transporte do meio poroso é um tema importante para muitas áreas como a Ciência do Solo, onde o conhecimento dos processos que envolvem o movimento da água é de fundamental importância para o manejo e a conservação do mesmo. Nas últimas décadas, as técnicas não-invasivas e o processamento de imagens têm ajudado muito na modelagem e visualização da estrutura do meio, e têm sido aplicadas no estudo da distribuição dos fluidos com diferentes abordagens. Nesse trabalho é apresentado um novo método para análise do movimento da água, baseado na descrição da estrutura tridimensional da frente de molhamento no processo de infiltração vertical na região não-saturada do solo, considerando que a frente de molhamento tem informação relevante sobre os primeiros estágios da infiltração na interface líquido-sólido. O método proposto para a descrição da estrutura tridimensional da frente de molhamento compõe-se de dois principais módulos. O primeiro é responsável pela segmentação de imagens tomográficas para a detecção da frente de molhamento e cujo resultado é crucial para a análise da superfície resultante. O segundo módulo efetua a determinação de descritores da superfície obtida baseada na computação da variabilidade morfológica e a identificação de zonas de máxima adsorção através da análise da curvatura. As imagens usadas nos experimentos foram obtidas usando um tomógrafo de campo específico para estudos de solos, permitindo o processamento sem alterar a estrutura do solo. Os resultados preliminares são encorajadores e indicam que a abordagem utilizada consegue descrever o movimento da água usando informação da frente de molhamento no espaço tridimensional e no tempo. / The study of the transport properties in porous media is an important issue for many areas such as soil science, where knowledge about processes that involve the movement of water in the soil has fundamental importance to soil management and soil conservation. In recent decades noninvasive techniques and image processing algorithms have been very helpful in modeling and visualization of the structure medium and have been applied to study of the distribution of fluid with different approaches. This work present a new method to analysis of the movement of water based on the description of the three-dimensional wetting front structure in vertical infiltration process in unsaturated soil, whereas the wetting front structure has relevant information in the earliest stages of infiltration in liquid-solid interface. The proposed method for the description of the three-dimensional wetting front structure is comprised of two main modules. The first module is responsible of the three-dimensional image segmentation for the wetting front detection and its result is a very crucial step to analysis of the surface obtained. The second module compute features of the surface obtained to analysis based on morphological variability and maximal adsorption zones identification through the curvature. The image used in the experimental test were obtained using a tomograph of field specific to soil study, allowing the processing without changing of the soil structure. Our preliminary results are encouraging and indicate that our approach can describe the movement of water using information from the wetting front in three-dimensional space and time.

This thesis present an efficient approach for performing smoke simulation on curvilinear grids. The solution of the Navier-Stokes equations on curvilinear is made on three steps: advection, pressure solving and velocity projection. The proposed advection method is simple, fast and unconditionally-stable. Our solution is able to maintain a staggered-grid variable arrangement, and includes an efficient solution to enforce mass conservation. Compared to approaches based on regular grids traditionally used in computer graphics, our method allows for better representation of boundary conditions, lending to more realistic results, with just a small increment in computational cost. Moreover, we are able to condensate cells where interesting artifacts tend to appear, like swirling vortices or turbulence. We demonstrate the effectiveness of our approach, both in 2-D and 3-D, through a variety of high-quality smoke simulations and animations. These examples show the integration of our method with overlapping grids and multigrid techniques.

Esta dissertação de mestrado propõe um algoritmo adaptativo que é capaz de dinamicamente definir partições tile para quadros intra- e inter-preditos com o objetivo de reduzir o impacto na eficiência de codificação. Tiles são novas ferramentas orientadas ao paralelismo que integram o padrão de codificação de vídeos de alta eficiência (HEVC – High Efficiency Video Coding standard), as quais dividem o quadro em regiões retangulares independentes que podem ser processadas paralelamente. Para viabilizar o paralelismo, os tiles quebram as dependências de codificação através de suas bordas, gerando impactos na eficiência de codificação. Este impacto pode ser ainda maior caso os limites dos tiles dividam regiões altamente correlacionadas do quadro, porque a maior parte das ferramentas de codificação usam informações de contexto durante o processo de codificação. Assim, o algoritmo proposto agrupa as regiões do quadro que são altamente correlacionadas dentro de um mesmo tile para reduzir o impacto na eficiência de codificação que é inerente ao uso de tiles. Para localizar as regiões altamente correlacionadas do quadro de uma maneira inteligente, as características da imagem e também as informações de codificação são analisadas, gerando mapas de particionamento que servem como parâmetro de entrada para o algoritmo. Baseado nesses mapas, o algoritmo localiza as quebras naturais de contexto presentes nos quadros do vídeo e define os limites dos tiles nessas regiões. Dessa maneira, as quebras de dependência causadas pelas bordas dos tiles coincidem com as quebras de contexto naturais do quadro, minimizando as perdas na eficiência de codificação causadas pelo uso dos tiles. O algoritmo proposto é capaz de reduzir mais de 0.4% e mais de 0.5% o impacto na eficiência de codificação causado pelos tiles em quadros intra-preditos e inter-preditos, respectivamente, quando comparado com tiles uniformes. / This Master Thesis proposes an adaptive algorithm that is able to dynamically choose suitable tile partitions for intra- and inter-predicted frames in order to reduce the impact on coding efficiency arising from such partitioning. Tiles are novel parallelismoriented tools that integrate the High Efficiency Video Coding (HEVC) standard, which divide the frame into independent rectangular regions that can be processed in parallel. To enable the parallelism, tiles break the coding dependencies across their boundaries leading to coding efficiency impacts. These impacts can be even higher if tile boundaries split highly correlated picture regions, because most of the coding tools use context information during the encoding process. Hence, the proposed algorithm clusters the highly correlated picture regions inside the same tile to reduce the inherent coding efficiency impact of using tiles. To wisely locate the highly correlated picture regions, image characteristics and encoding information are analyzed, generating partitioning maps that serve as the algorithm input. Based on these maps, the algorithm locates the natural context break of the picture and defines the tile boundaries on these key regions. This way, the dependency breaks caused by the tile boundaries match the natural context breaks of a picture, then minimizing the coding efficiency losses caused by the use of tiles. The proposed adaptive tiling algorithm, in some cases, provides over 0.4% and over 0.5% of BD-rate savings for intra- and inter-predicted frames respectively, when compared to uniform-spaced tiles, an approach which does not consider the picture context to define the tile partitions.

Esta dissertação de mestrado propõe um algoritmo adaptativo que é capaz de dinamicamente definir partições tile para quadros intra- e inter-preditos com o objetivo de reduzir o impacto na eficiência de codificação. Tiles são novas ferramentas orientadas ao paralelismo que integram o padrão de codificação de vídeos de alta eficiência (HEVC – High Efficiency Video Coding standard), as quais dividem o quadro em regiões retangulares independentes que podem ser processadas paralelamente. Para viabilizar o paralelismo, os tiles quebram as dependências de codificação através de suas bordas, gerando impactos na eficiência de codificação. Este impacto pode ser ainda maior caso os limites dos tiles dividam regiões altamente correlacionadas do quadro, porque a maior parte das ferramentas de codificação usam informações de contexto durante o processo de codificação. Assim, o algoritmo proposto agrupa as regiões do quadro que são altamente correlacionadas dentro de um mesmo tile para reduzir o impacto na eficiência de codificação que é inerente ao uso de tiles. Para localizar as regiões altamente correlacionadas do quadro de uma maneira inteligente, as características da imagem e também as informações de codificação são analisadas, gerando mapas de particionamento que servem como parâmetro de entrada para o algoritmo. Baseado nesses mapas, o algoritmo localiza as quebras naturais de contexto presentes nos quadros do vídeo e define os limites dos tiles nessas regiões. Dessa maneira, as quebras de dependência causadas pelas bordas dos tiles coincidem com as quebras de contexto naturais do quadro, minimizando as perdas na eficiência de codificação causadas pelo uso dos tiles. O algoritmo proposto é capaz de reduzir mais de 0.4% e mais de 0.5% o impacto na eficiência de codificação causado pelos tiles em quadros intra-preditos e inter-preditos, respectivamente, quando comparado com tiles uniformes. / This Master Thesis proposes an adaptive algorithm that is able to dynamically choose suitable tile partitions for intra- and inter-predicted frames in order to reduce the impact on coding efficiency arising from such partitioning. Tiles are novel parallelismoriented tools that integrate the High Efficiency Video Coding (HEVC) standard, which divide the frame into independent rectangular regions that can be processed in parallel. To enable the parallelism, tiles break the coding dependencies across their boundaries leading to coding efficiency impacts. These impacts can be even higher if tile boundaries split highly correlated picture regions, because most of the coding tools use context information during the encoding process. Hence, the proposed algorithm clusters the highly correlated picture regions inside the same tile to reduce the inherent coding efficiency impact of using tiles. To wisely locate the highly correlated picture regions, image characteristics and encoding information are analyzed, generating partitioning maps that serve as the algorithm input. Based on these maps, the algorithm locates the natural context break of the picture and defines the tile boundaries on these key regions. This way, the dependency breaks caused by the tile boundaries match the natural context breaks of a picture, then minimizing the coding efficiency losses caused by the use of tiles. The proposed adaptive tiling algorithm, in some cases, provides over 0.4% and over 0.5% of BD-rate savings for intra- and inter-predicted frames respectively, when compared to uniform-spaced tiles, an approach which does not consider the picture context to define the tile partitions.

Este trabalho introduz um modelo fisiológico para o reflexo pupilar em função das condições de iluminação (Pupil Light Reflex - PLR), e um modelo baseado em imagem para deformação dos padrões da íris. O modelo para PLR expressa o diâmetro da pupila ao longo do tempo e em função da iluminação ambiental, sendo descrito por uma equação diferencial com atraso, adaptando naturalmente o tamanho da pupila a mudanças bruscas de iluminação. Como os parâmetros do nosso modelo são derivados a partir de modelos baseados em experimentos científicos, ele simula corretamente o comportamento da pupila humana para um indivíduo médio. O modelo é então estendido para dar suporte a diferenças individuais e a hippus, além de utilizar modelos para latência e velocidade de dilatação e contração. Outra contribuição deste trabalho é um modelo para deformação realista dos padrões da íris em função da contração e dilatação da pupila. Após capturar várias imagens de íris de diversos voluntários durante diferentes estágios de dilatação, as trajetórias das estruturas das íris foram mapeadas e foi identificado um comportamento médio para as mesmas. Demonstramos a eficácia e qualidade dos resultados obtidos, comparando-os com fotografias e vídeos capturados de íris reais. Os modelos aqui apresentados produzem efeitos foto-realistas e podem ser utilizados para produzir animações preditivas da pupila e da íris em tempo real, na presença de variações na iluminação. Combinados, os dois modelos permitem elevar a qualidade de animações faciais, mais especificamente, animações da íris humana. / This thesis introduces a physiologically-based model for pupil light reflex (PLR) and an image-based model for iridal pattern deformation. The PLR model expresses the pupil diameter as a function of the environment lighting, naturally adapting the pupil diameter even to abrupt changes in light conditions. Since the parameters of the PLR model were derived from measured data, it correctly simulates the actual behavior of the human pupil. The model is extended to include latency, constriction and dilation velocities, individual differences and some constrained random noise to model hippus. The predictability and quality of the simulations were validated through comparisons of modeled results against measured data derived from experiments also described in this work. Another contribution is a model for realist deformation of the iris pattern as a function of pupil dilation and constriction. The salient features of the iris are tracked in photographs, taken from several volunteers during an induced pupil-dilation process, and an average behavior of the iridal features is defined. The effectiveness and quality of the results are demonstrated by comparing the renderings produced by the models with photographs and videos captured from real irises. The resulting models produce high-fidelity appearance effects and can be used to produce real-time predictive animations of the pupil and iris under variable lighting conditions. Combined, the proposed models can bring facial animation to new photorealistic standards.

Este trabalho introduz um modelo fisiológico para o reflexo pupilar em função das condições de iluminação (Pupil Light Reflex - PLR), e um modelo baseado em imagem para deformação dos padrões da íris. O modelo para PLR expressa o diâmetro da pupila ao longo do tempo e em função da iluminação ambiental, sendo descrito por uma equação diferencial com atraso, adaptando naturalmente o tamanho da pupila a mudanças bruscas de iluminação. Como os parâmetros do nosso modelo são derivados a partir de modelos baseados em experimentos científicos, ele simula corretamente o comportamento da pupila humana para um indivíduo médio. O modelo é então estendido para dar suporte a diferenças individuais e a hippus, além de utilizar modelos para latência e velocidade de dilatação e contração. Outra contribuição deste trabalho é um modelo para deformação realista dos padrões da íris em função da contração e dilatação da pupila. Após capturar várias imagens de íris de diversos voluntários durante diferentes estágios de dilatação, as trajetórias das estruturas das íris foram mapeadas e foi identificado um comportamento médio para as mesmas. Demonstramos a eficácia e qualidade dos resultados obtidos, comparando-os com fotografias e vídeos capturados de íris reais. Os modelos aqui apresentados produzem efeitos foto-realistas e podem ser utilizados para produzir animações preditivas da pupila e da íris em tempo real, na presença de variações na iluminação. Combinados, os dois modelos permitem elevar a qualidade de animações faciais, mais especificamente, animações da íris humana. / This thesis introduces a physiologically-based model for pupil light reflex (PLR) and an image-based model for iridal pattern deformation. The PLR model expresses the pupil diameter as a function of the environment lighting, naturally adapting the pupil diameter even to abrupt changes in light conditions. Since the parameters of the PLR model were derived from measured data, it correctly simulates the actual behavior of the human pupil. The model is extended to include latency, constriction and dilation velocities, individual differences and some constrained random noise to model hippus. The predictability and quality of the simulations were validated through comparisons of modeled results against measured data derived from experiments also described in this work. Another contribution is a model for realist deformation of the iris pattern as a function of pupil dilation and constriction. The salient features of the iris are tracked in photographs, taken from several volunteers during an induced pupil-dilation process, and an average behavior of the iridal features is defined. The effectiveness and quality of the results are demonstrated by comparing the renderings produced by the models with photographs and videos captured from real irises. The resulting models produce high-fidelity appearance effects and can be used to produce real-time predictive animations of the pupil and iris under variable lighting conditions. Combined, the proposed models can bring facial animation to new photorealistic standards.

Este trabalho apresenta uma solução geral para a detecção de alinhamentos de dados em conjuntos multidimensionais não ordenados e ruidosos. Nesta abordagem, o tipo requerido de alinhamento de dados pode ser uma forma geométrica (e.g., linha reta, plano, círculo, esfera, seção cônica, entre outras) ou qualquer estrutura, com dimensionalidade arbitrária, que possa ser caracterizada por um subespaço linear. A detecção é realizada por meio de um procedimento composto por três etapas. Na etapa de inicialização, um espaço de parâmetros com p (n − p) dimensões é definido de modo que cada ponto neste espaço represente uma instância do alinhamento requerido, descrito por um subespaço p-dimensional em um domínio n-dimensional. Em seguida, uma grade de acumuladores é criada como sendo a representação discreta do espaço de parâmetros. Na segunda etapa do procedimento, cada elemento no conjunto de dados de entrada (também um subespaço no domínio n-dimensional) é mapeado para o espaço de parâmetros como os pontos (no espaço de parâmetros) representando os subespaços requeridos que contém ou que estão contidos no elemento de entrada. À medida que os elementos de entrada são mapeados, as células do acumulador relacionadas com o mapeamento são incrementadas pelo valor de importância do elemento mapeado. A etapa final do procedimento recupera os subespaços p-dimensionais que melhor se ajustam aos dados de entrada como sendo os máximos locais na grade de acumuladores. A parametrização proposta é independente das propriedades geométricas dos alinhamentos a serem detectados. Além disso, o procedimento de mapeamento é independente do tipo de dado de entrada e é capaz de se adaptar a elementos com dimensionalidades arbitrárias. Essas características permitem a utilização da técnica (sem a necessidade de modificações) como uma ferramenta para a detecção de padrões em uma grande quantidade de aplicações. Por conta de sua natureza geral, otimizações desenvolvidas para a abordagem proposta beneficiam, de forma imediata, todos os casos de detecção. Neste trabalho eu demonstro uma implementação em software da técnica proposta e mostro que ela pode ser aplicada tanto em casos simples de detecção, quanto na detecção concorrente de tipos diferentes de alinhamentos, com diferentes interpretações geométricas e em conjuntos de dados compostos por vários tipos de elementos. Esta dissertação também apresenta uma extensão do esquema de detecção para dados de entrada com distribuição Gaussiana de incerteza. A extensão proposta produz distribuições de valores mais suaves na grade de acumuladores e faz com que a técnica fique mais robusta à detecção de subespaços espúrios. / This dissertation presents a generalized closed-form framework for detecting data alignments in large unordered noisy multidimensional datasets. In this approach, the intended type of data alignment may be a geometric shape (e.g., straight line, plane, circle, sphere, conic section, among others) or any other structure, with arbitrary dimensionality that can be characterized by a linear subspace. The detection is performed using a three-step process. In the initialization, a p (n − p)-dimensional parameter space is defined in such a way that each point in this space represents an instance of the intended alignment described by a p-dimensional subspace in some n-dimensional domain. In turn, an accumulator array is created as the discrete representation of the parameter space. In the second step each input entry (also a subspace in the n-dimensional domain) is mapped to the parameter space as the set of points representing the intended p-dimensional subspaces that contain or are contained by the entry. As the input entries are mapped, the bins of the accumulator related to such a mapping are incremented by the importance value of the entry. The subsequent and final step retrieves the p-dimensional subspaces that best fit input data as the local maxima in the accumulator array. The proposed parameterization is independent of the geometric properties of the alignments to be detected. Also, the mapping procedure is independent of the type of input data and automatically adapts to entries of arbitrary dimensionality. This allows application of the proposed approach (without changes) in a broad range of applications as a pattern detection tool. Given its general nature, optimizations developed for the proposed framework immediately benefit all the detection cases. I demonstrate a software implementation of the proposed technique and show that it can be applied in simple detection cases as well as in concurrent detection of multiple kinds of alignments with different geometric interpretations, in datasets containing multiple types of data. This dissertation also presents an extension of the general detection scheme to data with Gaussian-distributed uncertainty. The proposed extension produces smoother distributions of values in the accumulator array and makes the framework more robust to the detection of spurious subspaces.

Atualmente, o computador pessoal (PC) moderno poder ser considerado como um cluster heterogênedo de um nodo, o qual processa simultâneamente inúmeras tarefas provenientes das aplicações. O PC pode ser composto por Unidades de Processamento (PUs) assimétricas, como a Unidade Central de Processamento (CPU), composta de múltiplos núcleos, a Unidade de Processamento Gráfico (GPU), composta por inúmeros núcleos e que tem sido um dos principais co-processadores que contribuiram para a computação de alto desempenho em PCs, entre outras. Neste sentido, uma plataforma de execução heterogênea é formada em um PC para efetuar cálculos intensivos em um grande número de dados. Na perspectiva desta tese, a distribuição da carga de trabalho de uma aplicação nas PUs é um fator importante para melhorar o desempenho das aplicações e explorar tal heterogeneidade. Esta questão apresenta desafios uma vez que o custo de execução de uma tarefa de alto nível em uma PU é não-determinístico e pode ser afetado por uma série de parâmetros não conhecidos a priori, como o tamanho do domínio do problema e a precisão da solução, entre outros. Nesse escopo, esta pesquisa de doutorado apresenta um sistema sensível ao contexto e de adaptação em tempo de execução com base em um compromisso entre a redução do tempo de execução das aplicações - devido a um escalonamento dinâmico adequado de tarefas de alto nível - e o custo de computação do próprio escalonamento aplicados em uma plataforma composta de CPU e GPU. Esta abordagem combina um modelo para um primeiro escalonamento baseado em perfis de desempenho adquiridos em préprocessamento com um modelo online, o qual mantém o controle do tempo de execução real de novas tarefas e escalona dinâmicamente e de modo eficaz novas instâncias das tarefas de alto nível em uma plataforma de execução composta de CPU e de GPU. Para isso, é proposto um conjunto de heurísticas para escalonar tarefas em uma CPU e uma GPU e uma estratégia genérica e eficiente de escalonamento que considera várias unidades de processamento. A abordagem proposta é aplicada em um estudo de caso utilizando uma plataforma de execução composta por CPU e GPU para computação de métodos iterativos focados na solução de Sistemas de Equações Lineares que se utilizam de um cálculo de stencil especialmente concebido para explorar as características das GPUs modernas. A solução utiliza o número de incógnitas como o principal parâmetro para a decisão de escalonamento. Ao escalonar tarefas para a CPU e para a GPU, um ganho de 21,77% em desempenho é obtido em comparação com o escalonamento estático de todas as tarefas para a GPU (o qual é utilizado por modelos de programação atuais, como OpenCL e CUDA para Nvidia) com um erro de escalonamento de apenas 0,25% em relação à combinação exaustiva. / A modern personal computer can be now considered as a one-node heterogeneous cluster that simultaneously processes several applications’ tasks. It can be composed by asymmetric Processing Units (PUs), like the multi-core Central Processing Unit (CPU), the many-core Graphics Processing Units (GPUs) - which have become one of the main co-processors that contributed towards high performance computing - and other PUs. This way, a powerful heterogeneous execution platform is built on a desktop for data intensive calculations. In the perspective of this thesis, to improve the performance of applications and explore such heterogeneity, a workload distribution over the PUs plays a key role in such systems. This issue presents challenges since the execution cost of a task at a PU is non-deterministic and can be affected by a number of parameters not known a priori, like the problem size domain and the precision of the solution, among others. Within this scope, this doctoral research introduces a context-aware runtime and performance tuning system based on a compromise between reducing the execution time of the applications - due to appropriate dynamic scheduling of high-level tasks - and the cost of computing such scheduling applied on a platform composed of CPU and GPUs. This approach combines a model for a first scheduling based on an off-line task performance profile benchmark with a runtime model that keeps track of the tasks’ real execution time and efficiently schedules new instances of the high-level tasks dynamically over the CPU/GPU execution platform. For that, it is proposed a set of heuristics to schedule tasks over one CPU and one GPU and a generic and efficient scheduling strategy that considers several processing units. The proposed approach is applied in a case study using a CPU-GPU execution platform for computing iterative solvers for Systems of Linear Equations using a stencil code specially designed to explore the characteristics of modern GPUs. The solution uses the number of unknowns as the main parameter for assignment decision. By scheduling tasks to the CPU and to the GPU, it is achieved a performance gain of 21.77% in comparison to the static assignment of all tasks to the GPU (which is done by current programming models, such as OpenCL and CUDA for Nvidia) with a scheduling error of only 0.25% compared to exhaustive search.