Isomorfismo de grafos aplicado à comparação de impressões digitais

Abstract

Resumo: Este trabalho apresenta uma metodologia para comparação de impressões digitais baseada em isomorfismo de grafos. Esta metodologia é baseada na construção de grafos a partir das minúcias encontradas na impressão digital e retorna verdadeira quando a árvore geradora de um grafo GF, que representa uma impressão digital a ser comparada é isomorfa a um subgrafo de GC, que representa a impressão digital candidata para ser o par da primeira. Cada vértice do grafo representa uma minúcia encontrada na imagem da impressão digital e é rotulado com o seu tipo e posição geométrica na imagem. As arestas representam uma relação de vizinhança entre as minúcias. A comparação é realizada através do cômputo do isomorfismo dos grafos. Pretendeu-se com esta metodologia ser flexível, evitando problemas que podem acontecer quando há minúcias faltando em uma das impressões digitais e diferenças geométricas tais como: rotações, translações e escalas das imagens das impressões digitais. O algoritmo foi implementado e testado usando imagens adquiridas da Internet para as quais as minúcias foram encontradas em um processo manual. Os testes foram realizados com diferentes tipos de grafos construídos a partir das minúcias das impressões digitais, definindo diferentes relações de vizinhança entre elas. Neste trabalho também é apresentada uma abordagem elaborada para o cálculo do isomorfismo com consideração no tamanho das arestas com a finalidade de reduzir o número de comparações realizadas.

Abstract: This work presents a methodology to fingerprint matching using graph isomorphism. This methodology is based on the graph construction from minutiae found in fingerprints and returns true when the spanning tree of a graph GF (that represents a fingerprint to be compared) is isomorph to a subgraph of GC (that represents the candidate fingerprint to be the pair of the first one). Each vertex represents one minutiae found in the fingerprint image and is labelled with its type and geometric position in the image. The edges represent a relation of neighborhood between these features. The matching is done through the computation of graph isomorphism. With this methodology, it was intended to be flexible, avoiding problems that can happen when there are no minutiae enough in some places of the fingerprint and geometric problems such as: rotation, translation and scale of fingerprint images. The algorithm was implemented and tested using images from the Internet which the minutiae had been found using a manual process. The tests has been done with different types of graphs constructed from the minutiae of the fingerprints, defining different relations between them. Also, in this work is elaborated a new method to calculate the isomorphism, considering the size of the edges to reduce the number of comparisons done.