FANDOM


Uma Visão Geral da Transformada Imagem-Floresta

Joaquim Coragem Manzini Junior

Resumo Edit

Este artigo traz uma visão geral sobre a ferramenta de modelagem, implementação e avaliação de processamento de imagens denominada Transformada Imagem-Floresta. Será visto neste artigo, uma introdução aos conceitos da transformada, posteriomente um aprofundamento em seu algoritmo e detalhes deste. As aplicações que serão mostradas são: transformada de watershed e mínimos regionais.

Introdução Edit

A Transformada Imagem-Floresta (IFT) é uma ferramenta geral para modelar, implementar e avaliar operadores de processamento de imagens 2D/3D baseados em conexidade. A IFT define uma floresta de caminhos de custo mínimo em um grafo, onde os nós são os pixels da imagem e os arcos são definidos por uma relação de adjacência entre estes pixels. (Falcão, 2004a). Os custo de um caminho traçado sobre este grafo é dependente da aplicação a ser desenvolvida. A este custo é dado o nome de função de custo de caminho. Esta função é baseada em propriedades da imagem tais como: cor, gradiente e posição de pixels (Falcão, 2004a). A figura 1 mostra as relações de adjacência possíveis entre pixels.

Distancia euclidiana

O algoritmo envolvido no processamento da IFT é basicamente o algoritmo de Dijkstra modificado para o uso de várias raízes do grafo (mais conhecidas como sementes no âmbito do Processamento de Imagens). Uma outra variação possível a ser feita neste algoritmo é a possibilidade de uso de funções mais gerais de custo de caminho (Falcão, 2004b).

Uma das vantagens da IFT é unificar e extender muitas técnicas de análise tais como: propagação ordenada, inundação (watershed), dilatações geodésicas, programação dinâmica, crescimento de regiões e busca A*. Estas técnicas, tidas como independentes, geram zonas de influência que se assemelham muito às árvores da IFT (Falcão, 2000). Outra vantagem é a possibilidade de obtenção de operadores pouco relacionados à partição de imagem, por exemplo, reconstrução morfológica, transformações de distância, esqueletos multiescalares, saliências em formas e fractais multiescalares (Falcão, 2004b).

Organização do trabalho Edit

Este trabalho está organizado da seguinte forma: A seção 2 apresenta o algoritmo expandido de Dijkstra utilizado nas IFTs, sua implementação e detalhes desta. A seção 3 aborda algumas aplicações que utilizam IFT. As considerações finais são dispostas na seção 4.

Transformada Imagem-Floresta Edit

O algoritmo da IFT tem em suas raízes o algoritmo de Dijkstra. Uma grande diferença entre eles é o fato de o algoritmo da IFT comportar a escolha de várias sementes iniciais, enquanto Dijkstra essencialmente trabalha com apenas um pixel como ponto de partida. A IFT deve permitir também a utilização flexível de funções de custo associado a cada aresta do grafo.

Cada problema requer a escolha de uma função f, quando associa um custo proveniente de valores de um conjunto V ordenado e denotado inicialmente por +\infty, para cada caminho.

Uma mapa de predecessores P é uma função que atribui para cada pixel da imagem, ou a marcação null (no caso da ausência de predecessor), ou um outro pixel da imagem. Quando um pixel aponta seu predecessor para null, pode-se afirmar também que este é a raiz do mapa. O mapa completo de predecessores representa a floresta ótimo, a qual será a primeira saída da função.

Outros dois valores de retorno envolvidos são um mapa de custos C e um mapa de raízes R. O primeiro tem como objetivo guardar o custo de caminho ótimo gerado de cada pixel até sua raiz. O mapa de raízes, mais utilizado por questões de eficiência, permite acessar as raízes de um determinado pixel em tempo constante.

De maneira geral, têm-se:

  • Algoritmo Geral da IFT (MIRANDA):
ENTRADA: Uma imagem, uma relação de adjacência A e um conjunto de nós sementes S;
SAÍDA: Um mapa de custo C, uma mapa de predecessores P, e mapa de raízes R;
AUXILIARES: Uma fila de prioridades Q inicialmente vazia.
Para cada nó p do grafo derivado da imagem, faça:
C(p) \leftarrow + \infty, R(p) \leftarrow p, P(t) \leftarrow null.
Para cada p \in S, faça:|a. Imagem de um cérebro obtida por ultrassom. b. A colocação de duas sementes. c. O resultado da transformada de Watershed e segmentação de uma área de interesse.]]
C(p) \leftarrow = 0
Insira p em Q.
Enquanto Q não estiver vazia, faça:
Remova p de Q tal que C(p) seja mínimo.
Para cada q \in A(p) tal que C(q) > C(p), faça:
cst \leftarrow OP(C(p), \delta(p,q)).
Se cst < C(q), então:
Se C(q) \neq +\infty, então
Remova q de Q.
C(q) \leftarrow cst, R(q) \leftarrow R(p), P(q) \leftarrow p.
Insira q em Q.
Retorne \{C, P, R\}

Aplicações Edit

Este algoritmo fornece um framework eficiente para processamento de imagens explorando propriedades locais e globais da imagem, e projetando operadores de processamento de imagens eficientes a partir de saídas da transformada (FALCÃO, 2000). Abaixo serão vistos algumas aplicações que demonstram o uso de IFT.

Mínimos Regionais Edit

Um mínimo regional consiste de um conjunto conectado X \subseteq I no qual I(s) \leq I(t) para qualquer s \in X e qualquer aresta (s,t) \in A. A seguinte função de custo permite o cálculo de mínimos regionais (FALCÃO, 2004):


f_{ini}((t)) = I(t), \mbox{ para todo } t \in I,

Failed to parse (unknown function\cdotp): f_{ini}(\pi \cdotp (s,t)) = |x|=\left\{\begin{array}{rc} f_{ini}(\pi), &\mbox{se} \ I(s) \leq I(t), \\ +\infty &\mbox{c. c.} \end{array}\right.


Os mínimos regionais podem ser usados comao sementes da IFT em algumas tarefas de segmentação. Com a política de desempate FIFO, um pixel será raiz da IFT se, e somente se, ele pertencer a um mínimo regional. Portanto, uma imagem binária dos mínimos regionais pode ser gerada associando 1 a pixels raiz e 0 aos demais. No caso de uma estrutura LIFO para desempate, tem-se uma contagem direta do número de mínimos e a extensão destes mínimos na imagem é obtida podando as árvores com raiz r para escolher os pixels p com <math) I(p) = I(r)</math>.

Transformada de Watershed Edit

Conforme visto em Falcão, 2004, deve se considerar para esta aplicação a função de altitude de pixels, ou I(p). A transformada de watershed clássica simula a inundação desta superfície por fontes de água colocadas uma em cada mínimo regional, e onde uma barreira (ou dique) é erguida toda vez que águas provenientes de diferentes fontes se encontram, o que impede que elas se misturem (FALCÃO, 2004).

Neste caso, a resposta da função IFT pode ser encontrada no mapa de raízes L, que são consideradas como bacias da inundação. Ver figura 2. Utiliza-se a função f_{peak}:


f_{peak}((q)) = h(q),

Failed to parse (unknown function\cdotp): f_{peak}(\pi \cdotp (p,q)) = \mbox{max\{}f_{peak}(\pi), I(q)\mbox{\}}


Watershed

Conclusões Edit

Foi dada uma breve definição da Transformada Imagem-Floresta, abordando seus detalhes de algoritmo e aplicações. Uma implementação de uma IFT deve prezar a eficiência visto que trata-se de uma extensão do algoritmo de Dijkstra. Concluiu-se com duas aplicações que mostram a extensão de funcionamento da transformada e sua aplicação para criação de novos operadores para processamento de imagens.

Referências Edit

[[1]] FALCÃO, A. X., STOLFI, J., LOTUFO, R. A., The Image Foresting Transform: Theory, Algorithms, and Applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, v. 26, n. 1, pp. 19-29, jan. 2004.

[1] FALCÃO, A. X., Image Foresting Algorithm: A graph-based approach to image processing. www.ic.unicamp.br/˜afalcao/ift.html, 2004. Institute of Computing, State University of Campinas, SP - Brazil. Último acesso: 14 jun. 2007.

[[2]] MIRANDA, P. A. V., Segmentação de Imagens pela Transformada Imagem-Floresta. http://libdigi.unicamp.br/document/?view=vtls000379604, 2004. Institute of Computing, State University of Campinas, SP - Brazil. Último acesso: 02 jul. 2007.

[[3] Falcão, A. X., Lotufo, R. A., Araujo, G., The Image Foresting Transformation, Relatorio Tecnico IC-00-12, 2000. http://citeseer.ist.psu.edu/falcao00image.html. Último acesso 02 jul. 2007.

[[4]]

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.