This thesis focuses on the study of component-hypertrees, which are graphs that store gray-level images in a hierarchical way. In such graphs, nodes represent connected components of an image extracted from multiple increasing connectivities, while arcs are used to organize these nodes according to an inclusion relation. In this research, the main goal is to develop efficient algorithms and data structures for component-hypertree construction, storage and manipulation. More specifically, our main contributions can be summarized as follows: (i) the theory behind component-hypertrees is reviewed and expanded, with some important properties being highlighted and proved. Using these properties, optimized algorithms and data structures are developed, resulting in implementations that considerably decrease time consumption and memory usage when compared to previously existing strategies; (ii) the impact of the choice of connectivities used to extract connected component is studied and a new family of neighborhoods based on a hierarchy of partitions is proposed, leading to the development of even faster algorithms; (iii) an efficient way of computing attribute variation is explained, allowing the development of applications that extract nodes comprised of clusters of smaller objects; (iv) an experimental analysis is conducted, to show that the proposed strategy is faster and more efficient than previously existing approaches and (v) a word segmentation tool is developed, to showcase an example of an application where attribute variation is particularly suitable.

Esta tese tem como foco o estudo de hiperárvores de componentes, que consistem em grafos utilizados para armazenar imagens em níveis de cinza de forma hierárquica. Neste grafos, nós representam componentes conexos de uma imagem extraídos a partir de um conjunto de vizinhanças crescentes, enquanto arcos são utilizados para organizar os nós de acordo com relações de inclusão. Neste texto, o objetivo principal consiste na elaboração de algoritmos e estruturas de dados eficientes para a construção, o armazenamento e a manipulação de hiperárvores de componentes. Mais especificamente, as principais contribuições podem ser resumidas nos seguintes itens: (i) a teoria por trás de hiperárvores de componentes é revisada e expandida, e as propriedades mais importantes são destacadas e provadas. Estas propriedades são então usadas no desenvolvimento de algoritmos e estruturas de dados otimizados, que reduzem consideravelmente o consumo de tempo e memória comparados com abordagens anteriores; (ii) o impacto da escolha das vizinhanças é analisada e uma nova família de vizinhanças baseadas em hierarquia de partições é proposta, resultando em algoritmos ainda mais rápidos; (iii) uma forma eficiente de computar variações de atributos é fornecida, possibilitando a elaboração de aplicações que focam na extração de objetos compostos de um conjunto de objetos menores; (iv) uma análise experimental é realizada, mostrando que a estratégia proposta é mais rápida e eficiente do que outras abordagens e (v) uma abordagem para segmentação de palavras é desenvolvida, mostrando um exemplo de aplicação onde variação de atributos pode ser particularmente útil.