Algorithms for hierarchical graph-based image segmentation

Abstract

A segmentação de imagens ´e um problema aberto na visão computacional que tem sido extensivamente investigado por muitos anos. A tarefa de segmentar uma imagem envolve dividir os pixels de uma imagem em diferentes partes, onde cada parte representa uma característica distinta na imagem. Existem duas abordagens gerais que foram desenvolvidas para a segmentação de imagens: segmentação de imagem plana e segmentação de imagem hierárquica. Em uma segmentação de imagem plana, o algoritmo visa capturar em uma ´única partição todos os elementos distinguíveis na imagem. Os objetos de uma imagem são compostos de vários detalhes; em uma abordagem de segmentação de imagem plana, tais detalhes e seus relacionamentos não são considerados. Isso significa que não há estrutura ou ideia de composição de detalhes para os objetos da imagem. Por outro lado, a segmentação hierárquica de imagens aborda a natureza multi-escalar de uma imagem e produz uma representação hierárquica da imagem. A literatura sobre algoritmos de segmentação plana de imagens ´e muito ampla e atualmente possui fundamentos teóricos mais estabelecidos em comparação com a segmentação hierárquica de imagens. Do ponto de vista teórico e algorítmico, existem poucos métodos bem compreendidos na segmentação hierárquica; consequentemente, existe uma brecha entre os estudos teóricos bem estabelecidos feitos para segmentação plana em comparação com a segmentação hierárquica, tal brecha nos d´a uma grande oportunidade para pesquisas sobre os aspectos teóricos e algorítmicos da segmentação hierárquica. Nesta tese, estudamos as noções teóricas e algorítmicas para um algoritmo de segmentação hierárquica de imagens. Examinamos e analisamos um m´método de segmentação de imagens planas baseado em grafos bem estabelecido e o estendemos para uma abordagem de segmentação de imagens hierárquica. As principais contribuições desta tese são as seguintes: •Um m´método de segmentação hierárquico de imagens baseado em grafos: propomos um m´método no qual, similarmente `a extensão de watersheds de segmentação plana para segmentação hierárquica, um n´nível da hierarquia resultante corresponde a uma instância do problema de segmentação plana baseado em grafos planos. • Uma base teórica para hierarquizar um m´método de segmentação de imagens baseado em grafos: elaboramos um formalismo preciso para estudar as propriedades formais para hierarquizar um m´método de segmentação baseado em grafos. Como resultado desta base teórica, somos capazes de propor algoritmos eficientes e exatos para produzir um m´método de segmentação hierárquica de imagens. • Uma série de estratégias para a identificação de hiper parâmetros do m´método: estudamos a identificação de hiper parâmetros de nosso m´método baseado em grafos hierárquicos e propomos novas estratégias para configurar esses hiper parâmetros. • Uma extensão da segmentação baseada em grafos original: propomos uma generalização sobre a noção de medida de relevância originalmente usada pelo m´método baseado em grafos, tal generalização nos permite produzir hierarquias que dão mais importância a regiões que contem certas características. • A demonstração de bom desempenho em uma avaliação prática: validamos e mostramos que todas as nossas propostas têm um bom desempenho em situações práticas, utilizando um framework de avaliação especificamente proposto para hierarquias. Em conclusão, esta tese fornece uma nova base teórica e algorítmica sobre a hierarquização de uma segmentação de imagens baseada em grafos. Nossas contribuições levam a algoritmos eficientes e exatos para calcular um m´método de segmentação hierárquica de imagens baseado em grafos, que ´e prático para seu uso em análise de imagens e visão computacional.