Árvore máxima : teoria, algoritmos e aplicações

Orientadores: Roberto de Alencar Lotufo, Letícia RittnerTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de ComputaçãoResumo: A árvore máxima é uma estrutura que representa os componentes conexos resultantes de todos os limiares superiores possíveis de uma imagem. Esse trabalho foca em desenvolver a teoria, os algoritmos e aplicações da árvore máxima. Na teoria, são definidos os filtros de extinção (EF - Extinction Filter) para atributos crescentes e um procedimento para calcular EFs para atributos não crescentes. Nos algoritmos, uma estrutura de dados para a representação da árvore m áxima baseada em matrizes e orientada a nós junto com seus algoritmos de processamento são propostos. Esta estrutura dá acesso direto aos nós da árvore, é mais eficiente em termos de memória e tempo de processamento comparado a outras estruturas descritas na literatura. Usando a estrutura proposta, EFs podem ser implementados eficientemente, como indicado nos nossos experimentos e análise de complexidade. EFs são comparados experimentalmente com filtros de atributo e os resultados mostram que EFs são melhores em termos de simplificação para reconhecimento da imagem. Uma biblioteca de funções chamada iamxt que implementa a estrutura de dados e os algoritmos de processamento propostos ?é desenvolvida. Nas aplicações, nós investigamos dois problemas: classificaço de imagens de satélite e extração o do cérebro em imagens de ressonância magnética (RM). Essas aplicações são desenvolvidas em cima de EFs e dos algoritmos eficientes propostos. A abordagem de classificação de imagens de satélite proposta é chamada perfil de extinção (EP - Extinction Profile). Ela corresponde ao atual estado da arte tendo sido validada através da comparação com outro método do estado da arte chamado perfil de atributo, usando dois conjuntos de dados. Um conjunto de dados público com 359 volumes de RM com imagens adquiridas em aparelhos de RM de três vendedores e dois campos magnéticos diferentes foi desenvolvido. "Padrões prata" de segmentaço do cérebro também são fornecidos. O método de extração do cérebro proposto foi validado usando o conjunto de dados desenvolvido e dois outros conjuntos públicos. Os resultados mostram que o método proposto praticamente não deixa cérebro de fora na segmentação final comparado aos outros métodos e é robusto a inicialização dos seus parâmetrosAbstract: The max-tree is a mathematical morphology tool that represents all connected components resulting of every possible upper threshold of an image. This work focus on advancing further the max-tree theory, algorithms and applications. In the theory domain, extinction filters (EFs) for increasing attributes are defined and a procedure for computing EFs for non-increasing attributes, based on the space of shapes approach, is presented. In the algorithms domain, an array-based node-oriented data structure to store the max-tree and algorithms to process it are proposed. This structure gives direct access to the max-tree nodes, is more memory efficient and allows faster processing than other structures described in the literature. Using this proposed structure, EFs can be implemented efficiently as our experiments and complexity analysis indicate. EFs are experimentally compared to attribute filters and the results show that EFs are better in terms of simplification for recognition. We provide an open-source toolbox entitled iamxt that implements the data structure and the algorithms proposed using an array-based programming style. In the applications domain, we investigate two problems: classification of satellite images and magnetic resonance (MR) images brain segmentation. These applications are built upon EFs and the efficient max-tree algorithms. The satellite image classification approach we propose is called Extinction Profiles. It is currently the state-of-the-art for the classification of this kind of image. We validate this comparing to another state-of-the-art approach called Attribute Profile using two different datasets. For the brain segmentation application, we propose a public multi-vendor multi-field strength T 1-weighted brain MR dataset with 359 volumes and brain segmentation "silver standards" generated using supervised classification. We validate our method using this dataset and two other public datasets. The results show that our method has the highest sensitivity among the methods compared, i.e. preserves the brain, and it is robust to parameter initializationDoutoradoEngenharia de ComputaçãoDoutor em Engenharia Elétrica2013/23514-0, 2015/12127-0FAPES