Árvore de componentes é uma representação completa de imagens que utiliza componentes conexos dos conjuntos de níveis de uma imagem e a relação de inclusão entre esses componentes. Essas informações possibilitam diversas aplicações em processamento de imagens e visão computacional, e.g. filtros conexos, segmentação, extração de características entre outras. Aplicações que utilizam árvore de componentes geralmente computam atributos que descrevem os componentes conexos representados pelos nós da árvore. Entre esses atributos estão a área, o perímetro e o número de Euler, que podem ser utilizados diretamente ou indiretamente (para o cálculo de outros atributos). Os \"bit-quads\" são padrões de tamanho 2x2 binários que são agrupados em determinados conjuntos e contados em imagens binárias. Embora o uso de \"bit-quads\" resulte em um método rápido para calcular atributos em imagens binárias, o mesmo não ocorre para o cálculo de atributos dos nós de uma árvore de componentes, porque os padrões contados em um nó podem se repetir nos conjuntos de níveis da imagem e serem contados mais de uma vez. A literatura recente propõe uma adaptação dos bit-quads para o cálculo incremental e eficiente do número de buracos na árvore de componentes. Essa adaptação utiliza o fato de cada nó da árvore de componentes representar um único componente conexo e uma das definições do número de Euler para o cálculo do número de buracos. Embora essa adaptação possa calcular o número de Euler, os outros atributos (área e perímetro) não podem ser computados. Neste trabalho é apresentada uma extensão dessa adaptação de bit-quads que permite a contagem de todos os agrupamentos de bit-quads de maneira incremental e eficiente na árvore de componentes. De forma que o método proposto possa calcular todos os atributos que podem ser obtidos pelos bit-quads (além do número de buracos) em imagens binárias na árvore de componentes de maneira incremental. / Component tree is a full image representation which uses the connected components of the level sets of the image and these connected components\' inclusion relationship. This information can be used in various image processing and computational vision applications, e.g. connected filters, segmentation, feature extraction, among others. In general, applications which use component trees compute attributes that describe the connected components represented by the tree nodes. Attributes such as area, perimeter and Euler number, can be used directly or indirectly (when they are used to compute other attributes) to describe the component tree nodes in various applications. The bit-quads are binary patterns of size 2x2 that are grouped in determined sets and counted in binary images to compute area, perimeter (also their continuous approximation) and Euler number. Even though the bit-quads usage can yield an efficient method to compute binary image attributes, they cannot be used efficiently to compute attributes for all component tree nodes, since some bit-quads can be counted more than once over the level sets. An adaptation of the bit-quads has been proposed to compute efficiently and incrementally the number of holes for all component tree nodes. This adaptation uses the fact that each component tree node represents a unique connected component and one of Euler number definitions to compute the number of holes. Even though this adaptation can compute Euler number, it cannot compute other attributes derived from the bit-quads (area and perimeter). In this work, an extension of this adaptation is proposed to efficiently and incrementally count all bit-quads sets in a component tree. Moreover, it yields a method to compute all attributes which can be computed by the bit-quads in binary images in the component tree using an incremental strategy.

Árvore de componentes é uma representação completa de imagens que utiliza componentes conexos dos conjuntos de níveis de uma imagem e a relação de inclusão entre esses componentes. Essas informações possibilitam diversas aplicações em processamento de imagens e visão computacional, e.g. filtros conexos, segmentação, extração de características entre outras. Aplicações que utilizam árvore de componentes geralmente computam atributos que descrevem os componentes conexos representados pelos nós da árvore. Entre esses atributos estão a área, o perímetro e o número de Euler, que podem ser utilizados diretamente ou indiretamente (para o cálculo de outros atributos). Os \"bit-quads\" são padrões de tamanho 2x2 binários que são agrupados em determinados conjuntos e contados em imagens binárias. Embora o uso de \"bit-quads\" resulte em um método rápido para calcular atributos em imagens binárias, o mesmo não ocorre para o cálculo de atributos dos nós de uma árvore de componentes, porque os padrões contados em um nó podem se repetir nos conjuntos de níveis da imagem e serem contados mais de uma vez. A literatura recente propõe uma adaptação dos bit-quads para o cálculo incremental e eficiente do número de buracos na árvore de componentes. Essa adaptação utiliza o fato de cada nó da árvore de componentes representar um único componente conexo e uma das definições do número de Euler para o cálculo do número de buracos. Embora essa adaptação possa calcular o número de Euler, os outros atributos (área e perímetro) não podem ser computados. Neste trabalho é apresentada uma extensão dessa adaptação de bit-quads que permite a contagem de todos os agrupamentos de bit-quads de maneira incremental e eficiente na árvore de componentes. De forma que o método proposto possa calcular todos os atributos que podem ser obtidos pelos bit-quads (além do número de buracos) em imagens binárias na árvore de componentes de maneira incremental. / Component tree is a full image representation which uses the connected components of the level sets of the image and these connected components\' inclusion relationship. This information can be used in various image processing and computational vision applications, e.g. connected filters, segmentation, feature extraction, among others. In general, applications which use component trees compute attributes that describe the connected components represented by the tree nodes. Attributes such as area, perimeter and Euler number, can be used directly or indirectly (when they are used to compute other attributes) to describe the component tree nodes in various applications. The bit-quads are binary patterns of size 2x2 that are grouped in determined sets and counted in binary images to compute area, perimeter (also their continuous approximation) and Euler number. Even though the bit-quads usage can yield an efficient method to compute binary image attributes, they cannot be used efficiently to compute attributes for all component tree nodes, since some bit-quads can be counted more than once over the level sets. An adaptation of the bit-quads has been proposed to compute efficiently and incrementally the number of holes for all component tree nodes. This adaptation uses the fact that each component tree node represents a unique connected component and one of Euler number definitions to compute the number of holes. Even though this adaptation can compute Euler number, it cannot compute other attributes derived from the bit-quads (area and perimeter). In this work, an extension of this adaptation is proposed to efficiently and incrementally count all bit-quads sets in a component tree. Moreover, it yields a method to compute all attributes which can be computed by the bit-quads in binary images in the component tree using an incremental strategy.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional. / Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional. / Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.

L'objectif du travail présenté dans cette thèse est de proposer un avancement dans la construction des systèmes embarqués de traitement d'images numériques, flexibles et puissants. La proposition est d'explorer l'utilisation d'une représentation d'image particulière appelée « arbre des composantes connexes » (connected component tree – CCT) en tant que base pour la mise en œuvre de l'ensemble de la chaîne de traitement d'image. Cela est possible parce que la représentation par CCT est à la fois formelle et générale. De plus, les opérateurs déjà existants et basés sur CCT recouvrent tous les domaines de traitement d'image : du filtrage de base, passant par la segmentation jusqu'à la reconnaissance des objets. Une chaîne de traitement basée sur la représentation d'image par CCT est typiquement composée d'une cascade de transformations de CCT où chaque transformation représente un opérateur individuel. A la fin, une restitution d'image pour visualiser les résultats est nécessaire. Dans cette chaîne typique, c'est la construction du CCT qui représente la tâche nécessitant le plus de temps de calcul et de ressources matérielles. C'est pour cette raison que ce travail se concentre sur la problématique de la construction rapide de CCT. Dans ce manuscrit, nous introduisons le CCT et ses représentations possibles dans la mémoire de l'ordinateur. Nous présentons une partie de ses applications et analysons les algorithmes existants de sa construction. Par la suite, nous proposons un nouvel algorithme de construction parallèle de CCT qui produit le « parent point tree » représentation de CCT. L'algorithme est conçu pour les systèmes embarqués, ainsi notre effort vise la minimisation de la mémoire occupée. L'algorithme en lui-même se compose d'un grand nombre de tâches de la « construction » et de la « fusion ». Une tâche de construction construit le CCT d'une seule ligne d'image, donc d'un signal à une dimension. Les tâches de fusion construisent progressivement le CCT de l'ensemble. Pour optimiser la gestion des ressources de calcul, trois différentes stratégies d'ordonnancement des tâches sont développées et évaluées. Également, les performances des implantations de l'algorithme sont évaluées sur plusieurs ordinateurs parallèles. Un débit de 83 Mpx/s pour une accélération de 13,3 est réalisé sur une machine 16-core avec Opteron 885 processeurs. Les résultats obtenus nous ont encouragés pour procéder à une mise en œuvre d'une nouvelle implantation matérielle parallèle de l'algorithme. L'architecture proposée contient 16 blocs de base, chacun dédié à la transformation d'une partie de l'image et comprenant des unités de calcul et la mémoire. Un système spécial d'interconnexions est conçu pour permettre à certaines unités de calcul d'accéder à la mémoire partagée dans d'autres blocs de base. Ceci est nécessaire pour la fusion des CCT partiels. L'architecture a été implantée en VHDL et sa simulation fonctionnelle permet d'estimer une performance de 145 Mpx/s à fréquence d'horloge de 120 MHz / The aim of this work is to enable construction of embedded digital image processing systems, which are both flexible and powerful. The thesis proposal explores the possibility of using an image representation called connected component tree (CCT) as the basis for implementation of the entire image processing chain. This is possible, because the CCT is both simple and general, as CCT-based implementations of operators spanning from filtering to segmentation and recognition exist. A typical CCT-based image processing chain consists of CCT construction from an input image, a cascade of CCT transformations, which implement the individual operators, and image restitution, which generates the output image from the modified CCT. The most time-demanding step is the CCT construction and this work focuses on it. It introduces the CCT and its possible representations in computer memory, shows some of its applications and analyzes existing CCT construction algorithms. A new parallel CCT construction algorithm producing the parent point tree representation of the CCT is proposed. The algorithm is suitable for an embedded system implementation due to its low memory requirements. The algorithm consists of many building and merging tasks. A building task constructs the CCT of a single image line, which is treated as a one-dimensional signal. Merging tasks fuse the CCTs together. Three different task scheduling strategies are developed and evaluated. Performance of the algorithm is evaluated on multiple parallel computers. A throughput 83 Mpx/s at speedup 13.3 is achieved on a 16-core machine with Opteron 885 CPUs. Next, the new algorithm is further adapted for hardware implementation and implemented as a new parallel hardware architecture. The architecture contains 16 basic blocks, each dedicated to processing of an image partition and consisting of execution units and memory. A special interconnection switch is designed to allow some executions units to access memory in other basic blocks. The algorithm requires this for the final merging of the CCTs constructed by different basic blocks together. The architecture is implemented in VHDL and its functional simulation shows performance 145 Mpx/s at clock frequency 120 MHz