Seminário de Teoria da Computação

   Extensão do algoritmo de Dijkstra para processamento de imagens

                         Jorge Stolfi

         Sexta-feira, 06 de dezembro de 2002, Sala 96  13:00hs


A Transformada Árvore-Floresta (Image Foresting Transform, IFT) é uma
nova técnica geral para análise de imagens, desemvolvida por Alexandre
Falcão, Roberto Lotufo e outros, que consiste em calcular uma certa
árvore de caminhos mínimos num grafo derivado da imagem.  Diferentes
efeitos são obtidos variando-se a fórmula que define o custo de um
caminho nesse grafo.

A construção eficiente dessa árvore pode ser feita pelo algoritmo de
Dijkstra.  Este algoritmo foi inicialmente proposto para a função-custo
aditiva (onde o custo do caminho é a soma de custos fixos associados às
arestas); e verificou-se posteriormente que ele funciona também para
outras funções-custo monotônicas e associativas, como por exemplo
custo da aresta mais cara.

Para a IFT, foi considerado necessário estender ainda mais a classe de
funções-custo que podem ser tratadas pelo algoritmo.  Nesta palestra
vamos paresentar um conjunto de condições mais fracas que
monotonica-associativa, e mostrar que elas ainda assim são suficientes
para o funcionamento do algoritmo de Dijkstra.