Tese de Doutorado

Morphological trees are image representations that can be used in a wide range of applications from medical imaging to digital photography. Morphological trees are interesting representations because they hierarchically encode the connected components (with and without their holes filled) according to their subset relationship. In this way, we can analyse and process connected regions of the images based on the hierarchy represented by the tree. A common morphological tree application pipeline consists of building the tree, computing attributes, processing the tree based on the tree structure and attributes of each node, and outputting results. Consequently, efficient attribute computation is a recurrent demand for unlocking new morphological tree applications. In this thesis, we describe our research on how to efficiently compute bit-quad counts, contours and distance transforms in morphological trees by exploiting the subset relationship encoded in trees for reuse of the attribute computation of the child nodes into their parent. First, we review how we can count bit-quads in component trees incrementally from the leaves to the root. Next, we design a novel incremental algorithm to count bit-quads in the tree of shapes. Then, we design a novel incremental method that can extract the contour of the nodes of component trees by counting the number of background neighbours of the pixels. Finally, we use our incremental contour method and Differential Image Foresting Transform to differentially compute the distance transform of component trees. We experimentally show that our differential and incremental methods are faster than non-incremental node-reconstruction approaches. We also explore the usage of morphological trees for image manipulation. In particular, we propose a novel morphological tree visualisation using icicle plots for node selection. In this visualisation, the nodes are coloured by an iso-illuminant colour map according to an attribute which aids the user in selecting the nodes. Then, the selected nodes can be manipulated using a spline-based dense medial descriptor. In summary, the thesis shows that we can compute bit-quad counts, contours, and distance transforms in morphological trees quickly by reusing the computation on the child nodes into their parent. It also discusses a software application of morphological trees for image manipulation.

Árvores morfológicas são representações de imagens que podem ser usadas em inúmeras aplicações, desde imagens médicas até fotografia digital. Árvores morfológicas são representações interessantes porque elas estruturam os componentes conexos (com e sem os buracos preenchidos) de acordo com seus relacionamentos de subconjuntos. Dessa forma, podemos analisar e processar regiões conexas das imagens baseando-se na hierarquia representada pela árvore. O pipeline comum de aplicações de árvore morfológica consiste em construir a árvore, computar atributos, processar a árvore conforme a sua estrutura e atributos de cada nó, e produzir os resultados. Consequentemente, a computação eficiente de atributos é uma demanda recorrente para novas abordagens com árvores morfológicas. Nesta tese, descrevemos nossas pesquisas em como computar eficientemente contagem de bit-quads, contorno e trasformada de distância em árvores morfológicas, explorando o relacionamento de subconjuntos codificado nas árvores para reusar a computação de atributo nos nós filhos em seus nós pais. Primeiramente, revisamos como podemos contar bit-quads em árvores de componentes incrementalmente das folhas até a raiz. Em seguida, desenvolvemos um novo algoritmo incremental para contar bit-quads na árvore de formas. Então, apresentamos um novo método incremental que pode extrair contornos dos nós de árvores de componentes contando o número de vizinhos de fundo dos pixels. Por fim, usamos nosso método incremental de extração de contorno com a transformada imagem-floresta diferencial para computar diferencialmente a transformada da distância em árvores de componentes. Mostramos experimentalmente que nossos métodos incrementais e diferenciais são mais rápidos que abordagens não-incrementais baseadas na reconstrução dos nós. Também exploramos o uso de árvores morfológicas para manipulação de imagens. Em particular, propomos a visualização de árvores morfológicas usando \\textit{icicle plots} para seleção de nós. Nesta visualização, os nós podem ser coloridos por um mapa de cor iso-iluminante de acordo com um atributo que auxilia o usuário a selecionar os nós. Então, os nós selecionados podem ser manipulados usando descritor denso medial baseado em splines. Portanto, a tese mostra que podemos computar contagem de bit-quads, contorno e transformada de distância em árvores morfológicas rapidamente, reusando a computação nos nós filhos em seus nós pais. Ela também discute uma aplicação de árvores morfológicas em manipulação de imagens.