Resumo

Dada a natureza discreta das imagens digitais, a matemática discreta baseada em grafos emergiu como uma ferramenta unificadora para representar, processar e analisar imagens [7]. Como consequência, essa área tem despertado grande interesse nos últimos anos, conforme atestam a crescente quantidade de artigos publicados na área [3], apresentações em congressos/convenções [13], e até livros exclusivamente dedicados ao tópico [7].

A interpretação de uma imagem digital como um grafo pode ocorrer em diferentes níveis, podendo os nós do grafo representar diferentes elementos da imagem tais como pixels, regiões de pixels, ou até objetos da imagem com valor semântico agregado. Até mesmo um banco de dados de imagens pode ser interpretado como um grafo cujos nós são as imagens. Em qualquer caso, cada nó possui um conjunto associado de atributos da imagem, e os arcos descrevem relações binárias entre eles. Neste cenário, os operadores de imagem (e.g., filtragem, segmentação, representação e descrição de objetos, e classificação) podem tirar proveito de uma literatura rica e dinâmica.

Nesse trabalho, trabalharemos com a segmentação de imagens através da técnica do Corte Normalizado [12], que busca dividir os pixels de uma imagem em grupos identificando um corte normalizado mínimo no grafo, o que indicaria que as duas regiões separadas pelo corte têm baixa correlação e, portanto, devem pertencer à regiões diferentes da imagem modelada. Tal técnica é bastante reconhecida e pode-se encontrar referências a ela em livros [9] da área de Visão Computacional. Entretanto, sua complexidade é $O(mn)$ [12], onde $n$ é o número de pixels da imagem e $m$ é a quantidade de passos que o algoritmo sugerido em [12] leva para calcular os auto-valores e auto-vetores, itens necessários para sua execução. Nesse artigo, é citado que $m$ é de ordem $O(n^{\frac{1}{2}})$ e que em testes realizados, uma imagem simples de 100 $\times$ 200 pixels levou mais de 2 minutos para ser segmentada usando apenas o corte normalizado. Portanto, trata-se de uma técnica com constante de proporcionalidade elevada e alto tempo de execução.

Uma outra técnica de segmentação de imagens é a utilização dos superpixels. Ela é utilizada em imagens muito grandes e complexas [4] em que a segmentação seria muito custosa se fosse feita pixel a pixel. Assim buscamos a introdução dos superpixels, que são conjuntos de pixels de características semelhantes. Se a abordagem de segmentação através de grafos for escolhida pode-se, pode exemplo, modelar cada superpixel como um nó do grafo, ao invés de cada pixel ser um nó. Isso diminui drasticamente a quantidade de nós do grafo e, assim, mesmo com a complexidade computacional inalterada, o tempo de execução real de um algoritmo diminui.

A biblioteca LibOPF é uma possível maneira de gerar o mapa de superpixels. A classificação que a LibOPF faz é baseada em encontrar Florestas de Caminhos Ótimos (Optimum-Path Forests (OPF)) [8][11] dentro do grafo e seu resultado é bastante eficiente.

Apesar de diversos estudos [10][6][1] utilizarem o Corte Normalizado para produzir as regiões de superpixel, não encontramos na literatura nenhum estudo relacionando a LibOPF com o Corte Normalizado. Uma modelagem de superpixel pode tornar o Corte Normalizado mais eficiente, uma vez que diminui a quantidade de nós a serem verificados pelo algoritmo e, consequentemente, otempo de execução. Podemos utilizar a LibOPF paragerar os superpixels e usar o Corte Normalizado para segmentação da imagem. Por outro lado, a combinação entre as duas técnicas pode ser benéfica ao resultado da clusterização da LibOPF, pois a segmentação não supervisionada por OPF gera um numero variável de regiões, ou seja não temos como predefinir o número de classes. Nesse sentido o corte normalizado seria usado sobre o resultado do OPF, de modo a fixar um número predeterminado de regiões, o que é importante em algumas aplicações (e.g., separação de tecidos em imagens de ressonância magnética).