[en] NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM

ALEXANDRE ROCHA DUARTE

[pt] NOVAS HEURÍSTICAS E UMA ABORDAGEM POR PROGRAMAÇÃO INTEIRA PARA UM PROBLEMA DE CORRESPONDÊNCIA INEXATA DE GRAFOS

dc.contributor	CELSO DA CRUZ CARNEIRO RIBEIRO
dc.contributor	CELSO DA CRUZ CARNEIRO RIBEIRO
dc.creator	ALEXANDRE ROCHA DUARTE
dc.date	2004-03-26
dc.date.accessioned	2022-09-21T21:43:44Z
dc.date.available	2022-09-21T21:43:44Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4715@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4715@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.4715
dc.identifier.uri	https://hdl.handle.net/20.500.12032/42588
dc.description	[pt] 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.
dc.description	[en] This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] PROGRAMACAO INTEIRA
dc.subject	[pt] MODELAGEM POR MULTI-FLUXOS
dc.subject	[pt] CORRESPONDENCIA INEXATA DE GRAFOS
dc.subject	[pt] META-HEURISTICAS
dc.subject	[pt] OTIMIZACAO COMBINATORIA
dc.subject	[en] INTER LINEAR PROGRAMMIN
dc.subject	[en] MULTICOMMODITY FLOW MODEL
dc.subject	[en] INEXACT GRAPH MATCHING
dc.subject	[en] META-HEURISTICS
dc.subject	[en] COMBINATORIAL OPTIMIZATION
dc.title	[en] NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM
dc.title	[pt] NOVAS HEURÍSTICAS E UMA ABORDAGEM POR PROGRAMAÇÃO INTEIRA PARA UM PROBLEMA DE CORRESPONDÊNCIA INEXATA DE GRAFOS
dc.type	TEXTO

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

Documentos - PUC-RIO

Show simple item record