Fandom

Students

LAPIS/Disciplinas/Processamento de Imagens:TransfImagemFloresta

< LAPIS | Disciplinas

1,331pages on
this wiki
Add New Page
Talk0 Share

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.

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]]

Also on Fandom

Random Wiki