NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM / NOVAS HEURÍSTICAS E UMA ABORDAGEM POR PROGRAMAÇÃO INTEIRA PARA UM PROBLEMA DE CORRESPONDÊNCIA INEXATA DE GRAFOS
AUTOR(ES)
ALEXANDRE ROCHA DUARTE
DATA DE PUBLICAÇÃO
2004
RESUMO
Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata.
ASSUNTO(S)
programacao inteira correspondencia inexata de grafos otimizacao combinatoria meta-heuristics integer linear programming modelagem por multi-fluxos combinatorial optimization meta-heuristicas multicommodity flow model inexact graph matching
