Busca de padroes em subdivisoes planares

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorGuedes, Andre Luiz Pires, 1966--
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorAndrade Neto, Pedro Ribeiro de-
Data de aceite: dc.date.accessioned2025-09-01T12:47:29Z-
Data de disponibilização: dc.date.available2025-09-01T12:47:29Z-
Data de envio: dc.date.issued2024-10-16-
Data de envio: dc.date.issued2024-10-16-
Data de envio: dc.date.issued2004-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/1899-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/1899-
Descrição: dc.descriptionOrientador: André Luiz Pires Guedes-
Descrição: dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 2004-
Descrição: dc.descriptionInclui bibliografia-
Descrição: dc.descriptionResumo: O sub-isomorfismo de grafos é uma abordagem muito utilizada para solucionar problemas de busca de padrões, mas este e um problema NP-completo. Desta forma, deve-se investir em pesquisa para encontrar soluções aproximadas, ou que funcionem em casos especiais do problema. Subdivisões planares podem ser consideradas um caso especial de grafos, pois, além dos vértices e arestas, existe uma topologia mais r³gida quanto µa ordem das arestas, surgindo o conceito de face. Este trabalho apresenta um algoritmo linear para busca de padrões em subdivisões planares. Os padrões a serem buscados também são considerados subdivisões e, portanto, este e um problema de sub-isomorfismo. O algoritmo apresentado baseia-se em uma representação h³brida entre o dual e o grafo de regiões adjacentes (RAG) para representar os padrões, de forma a não ter qualquer custo adicional de armazenamento. Então, os padrões são procurados na subdivisão de busca, utilizando um algoritmo de crescimento de regiões. Este trabalho também realiza um estudo comparativo das estruturas de dados mais utilizadas para armazenamento de subdivisões planares.-
Descrição: dc.descriptionAbstract: Graph sub-isomorphism is a very used approach to solving pattern search problems, but this is a NPcomplete problem. This way, it is necessary to invest in research of approximate solutions, or in special cases of the problem. Planar subdivisions can be considered as a special case of graphs, because, in addition to nodes and edges, there is a more rigid topology in relation to the order of the edges, arising to the concept of face. This work presents a linear algorithm for pattern search in planar subdivisions. The patterns to be searched are also considered subdivisions, and therefore it is a sub-isomorphism problem. The presented algorithm is based on a hybrid approach between the dual and the region adjacency graph (RAG) to represent the patterns, saving additional storage costs. Thus, the patterns are looked over the search subdivision, using an algorithm of region growing. This work also performs a comparative study of the data structures commonly used for storage of planar subdivisions.-
Formato: dc.formatviii, 45f. : il.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectVisão por computador-
Palavras-chave: dc.subjectProcessamento de imagens-
Palavras-chave: dc.subjectReconhecimento de padrões-
Palavras-chave: dc.subjectProjeto auxiliado por computador-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleBusca de padroes em subdivisoes planares-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.