Extração de Minúcias em Imagens de Impressões Digitais
CASADO, Ricardo S.; PAIVA, Maria S. V. de
Escola de Engenharia de São Carlos
Universidade de São Paulo
Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.
Resumo
O trabalho apresenta métodos para a extração de minúcias em imagens de impressões digitais. O objetivo foi desenvolver um sistema semi-automático para extração de minúcias para auxiliar especialistas na tarefa de identificação de indivíduos, onde o istema executa as seguintes etapas: pré-processamento das imagens com o objetivo de aumentar a discriminação visual das mesmas. Etapa de afinamento e marcação das minúcias nas imagens. E por último é realizada a etapa de pósprocessamento, que visa eliminar as falsas minúcias encontradas pelo sistema. Porém é um sistema semiautomático onde ainda será necessária a intervenção de um especialista para o reconhecimento do indivíduo através da imagem.
1. Introdução
A biometria tem se tornado um tópico cada vez mais importante, em face das crescentes necessidades de proteção e segurança no mundo hodierno. Ela é definida como a(s) característica(s) ou métrica(s) que identifica(m) de forma única o indivíduo [1]. As impressões digitais vêm ao longo destes anos demonstrando maior confiabilidade no que se diz respeito à identificação de indivíduos. Utilizada nos tribunais de justiça como provas criminalísticas esta é, portanto junto com a assinatura a técnica biométrica mais aceita no mundo inteiro. As impressões digitais são formadas nos primeiros meses de gestação, onde cada um tem sua própria impressão digital, e pode ser observado que até mesmo gêmeos idênticos possuem os desenhos que formam a geometria da impressão digital diferente por existir variações no fluxo amniótico e cada um estar inserido em um micro ambiente diferente dentro do útero [2]. No trabalho primeiro são executados algoritmos de pré-processamento. Já na etapa de extração das minúcias é realizado o trabalho de afinamento das cristas papilares e depois a marcação das minúcias. A etapa final é a de pós-processamento, onde é realizada a remoção de falsas minúcias encontradas pelo sistema.
Existem vários sistemas de detecção de minúcias em impressões digitais, na qual a maioria deles realiza o processo de classificação e verificação, estes por sua vez são conhecidos como sistemas automáticos. Já o sistema apresentado trabalha apenas com a detecção de minúcias, porém é conhecido como um sistema semi-automático. Onde em uma imagem de impressão digital pode-se observar vários tipos delas como as apresentadas na figura de número 1.1.
Fig. 1.1 Amostra de várias minúcias.
Estas minúcias podem se restringir a apenas dois grupos, as terminações e as bifurcações. Na qual já é possível diferenciar um indivíduo do outro. Geralmente em uma imagem de impressão digital de boa qualidade é possível observar de 40 a 100 minúcias [3].
No sistema desenvolvido foram utilizados para testes imagens do DB2 e do DB4 encontradas no site FVC2004 (Fingerprint Verification Competition) [4]. As imagens encontradas no DB2 foram obtidas através de um sensor óptico e as encontradas no DB4 foram geradas pelo SFinGe (Synthetic Fingerpring Generation).
Fig. 1.2 Amostras das imagens capturadas pelos sensores.
2. Etapa de pré-processamento
As imagens de impressões digitais são pré-processadas com o intuito de reduzir as distorções e aumentar a discriminação visual entre os objetos contidos na imagem. Pois desde que as imagens são obtidas através de sensores podem apresentar deformações se comparadas com a digital original do indivíduo.
2.1 Espalhamento de contraste
O espalhamento de contraste é utilizado, pois em imagens de má qualidade apresentam deficiência no contraste que podem gerar configurações de pixels similares ou ignorar minúcias verdadeiras. Este processo consiste em calcular para cada pixel um valor médio de intensidade em uma vizinhança de 5x5. Se o valor do pixel for menor que a média do bloco considerado, então o pixel de interesse receberá o valor zero; caso contrário o pixel receberá seu valor original [5].
Fig. 2.1 Imagem original e imagem equalizada.
A binarização das imagens é de grande uso e de destacada importância quando são usadas imagens digitalizadas de impressões digitais. Uma vez que uma impressão digital deve possuir apenas duas tonalidades, a cor do fundo e a cor do desenho. Então a binarização é transformar a imagem original de 8 bits em uma imagem de 1 bit, ou seja, a binarização consiste em transformar uma imagem em tons de cinza em uma imagem preto e branco e esta operação é referida na literatura como threshold [6].
Um método de threshold adaptável é executado para binarizar a imagem que contém a impressão digital. Neste método verificam-se os valores de intensidade dos pixels com um determinado valor chamado de nível de threshold. Se o pixel de interesse tem valor menor que o nível de threshold utilizado, então o pixel receberá o valor zero, caso contrário este receberá o valor um. Esta operação pode ser expressa pela seguinte expressão:
(1)
B(i, j) = 0 se O(i, j) < T
B(i, j) =1se O(i, j) >= T
(i =1, 2, ..., N; j =1, 2, ...,M)
Onde B(i,j) é a imagem binária resultante, O(i,j) é a imagem de entrada, ou seja, a imagem original, T é o nível de threshold utilizado para realizar a binarização da imagem, N são as linhas e M as colunas da imagem.
O threshold adaptável é utilizado, pois o valor do nível de cinza é diferente em cada parte da imagem. Por isso é necessária a utilização de pequenos blocos para percorrer a imagem e realizar a binarização. Então o
threshold é calculado para cada bloco da imagem usando o valor médio de cinza como valor de nível de threshold [7].
Fig. 2.2 Imagem binarizada.
2.3 Imagem direcional
A maior parte dos trabalhos de extração de minúcias utilizam a imagem direcional, pois através dela obtêm-se informações contidas nos padrões de impressões digitais que podem ser seguramente calculadas em imagens ruidosas [8]. A imagem direcional na verdade tem grande importância durante o processo de extração das características globais (núcleo e delta) da imagem para um posterior processo de classificação desta dentre os cinco padrões adotados pelo NIST (National Institute of Standards and Technology) que são: Arco angular, arco plano, presilha interna, presilha externa e verticilo, na qual depois de localizada à qual classe pertence tal imagem o processo torna-se mais rápido, pois não é preciso procurar a imagem entre todas as outras no banco de dados. Ela também é importante durante o processo de reconhecimento do indivíduo, onde é criado um vetor de características contendo a localização da minúcia, seu tipo e orientação.
A princípio o objetivo era desenvolver um sistema automático que realizasse a detecção de minúcias, das características globais, classificação e reconhecimento. E como a técnica para o cálculo da imagem direcional já havia sido pesquisada, foi interessante mantê-la no trabalho para estas futuras tarefas. O fluxo direcional das cristas papilares que formam as impressões digitais pode ser estimado através de suas texturas. Assim o campo de orientação forma uma matriz de direções representando as cristas e os vales (espaço entre as cristas) para cada localização na imagem, este método é bastante utilizado em sistemas de identificação e autenticação de impressões digitais [9].
Para estimar o fluxo da orientação local das cristas papilares é necessário utilizar um bloco de estimação para cada bloco da imagem que contém a impressão digital com tamanho de WxW (W tem 16 pixels por padrão).
Calculam-se os valores dos gradientes na direção x e y para cada pixel através de uma máscara de sobel 3x3. E a fórmula para realizar o cálculo da orientação do vetor gradiente é apresentada abaixo.
Para estimar a direção das cristas papilares basta calcular os valores do vetor gradiente que foram computados juntamente com os valores dos cossenos e dos senos dos ângulos formados entre as cristas papilares e os eixos x e y.
E então o processo é finalizado com a estimação da direção de cada bloco, aqueles blocos sem informações significantes das cristas papilares e dos vales da imagem que contêm a impressão digital são descartados baseados na seguinte fórmula:
Se o nível de E é menor que o nível de threshold, então o bloco é estimado como se fosse o fundo da imagem.
Fig. 2.3 Direção estimada do fluxo das cristas papilares.
2.4 Região de interesse (ROI)
Os operadores morfológicos são utilizados aqui para determinar a região de interesse que na verdade é apenas a região em que se encontram as informações importantes da impressão digital, ou seja, o algoritmo de detecção de minúcias só irá percorrer a área em cinza apresentada na figura 2.4 ignorando as outras regiões. Nesta etapa são utilizados dois operadores morfológicos chamados de operação “OPEN” e “CLOSE”, ambos encontrados na toolbox de morfologia matemática do software Matlab (bwmorph).
A operação “OPEN” é capaz expandir a imagem e remover pontos introduzidos por ruídos existentes no fundo da imagem. Já a operação “CLOSE” é capaz de contrair a imagem e eliminar pequenas cavidades existentes na mesma.
Fig. 2.4 Região de interesse (área cinza).
3. Etapa de extração das minúcias
Nesta etapa serão apresentados métodos de afinamento das cristas papilares da impressão digital contida na imagem (thinning). Após a operação de afinamento são utilizadas técnicas para remover pontos isolados e reentrâncias existentes entre as cristas papilares. E por fim é realizada a operação de extração das minúcias encontradas na impressão digital, ou seja, as terminações e as bifurcações.
3.1 Afinamento ou thinning
O thinning também conhecido como afinamento das cristas papilares é uma técnica que pode ser utilizada para remover pontos isolados no fundo da imagem e ângulos retos ao longo de bordas dos objetos [10]. O algoritmo de afinamento é um casamento de máscaras (blocos) que percorrem a imagem verificando se um pixel faz ou não parte das cristas papilares que compõem a impressão digital. O afinamento é definido em termos da transformada “hit or miss”, que no caso é o casamento
das máscaras. Em geral os algoritmos de afinamento consomem muito tempo em específico para impressões digitais, pois a varredura da imagem é feita linha a linha, examinando a vizinhança e verificando quando um pixel pode ou não ser apagado [11].
O algoritmo de afinamento é executado até que as cristas papilares da imagem atinjam a espessura de um pixel, normalmente estes algoritmos necessitam de 20 a 30 passos para afinar as cristas em uma imagem de impressão digital. E, portanto para otimizar este processo é necessário conhecer o processo de thinning. O afinamento é realizado através de pares de elementos estruturantes, porém é sugerido na literatura que estas operações podem ser efetuadas de forma simétrica a partir de uma família de elementos estruturantes, que é uma seqüência de rotações de um determinado elemento [13]. Quando um pixel é apagado, ou seja, seu valor muda de um para zero, a imagem é dita transformada. Um número total de pixels apagados em um passo constitui um número total de mudanças neste passo. O afinamento pode ser dado como completo quando o número de mudanças na imagem converge para zero, ou seja, quando não ocorrem mais mudanças [12].
Fig. 3.1 Família de elementos estruturantes.
Os símbolos ativos são representados pelo número zero e os representados pela letra x são os pixels que não interagem com a imagem.
Fig. 3.2 Afinamento.
3.2 Filtro de remoção de ruídos
Considerando as características essenciais mencionadas no algoritmo de afinamento, pretende-se remover os pixels que contornam as cristas papilares que formam a impressão digital, exceto aqueles que compõem estas cristas, de forma iterativa. Por exemplo, o pixel P(i, j) para ser removido deve ter alguns relacionamentos especiais em relação a seus vizinhos.
Fig. 3.3 Pixel central e seus respectivos vizinhos.
Observa-se a seguinte condição para realizar a remoção de pontos indesejáveis, ou seja, que não fazem parte das cristas papilares (ruídos). Primeiramente, define-se o pixel de interesse P (i, j) localizado no centro
da máscara ou bloco que irá percorrer a imagem linha a linha.
Se os pixels (i, j), (i + 1, j + 1) e (i – 1, j + 1) possuírem valor um, então os pixels (i + 1, j), (i, j + 1) e (i - 1, j) receberão o valor zero (Figura 5.10). Desta forma é possível obter uma imagem filtrada do esqueleto que forma a impressão digital.
Fig. 3.4 Máscara de remoção de reentrâncias.
Já para a remoção de pontos existentes no fundo da imagem, ou seja, totalmente desconexos das cristas que formam a impressão digital é utilizado também como anteriormente uma um bloco de dimensões 3x3, porém se todos os pixels vizinhos ao pixel central possuírem valor zero e apenas o pixel central possuir valor um, então ele é transformado em zero também, passando a fazer parte do fundo da imagem.
Fig. 3.5 Máscara de remoção de pontos.
Fig. 3.6 Remoção de ruídos.
3.3 Detecção de minúcias
Depois de executar o algoritmo de afinamento das cristas papilares na imagem de impressão digital o processo de extração das minúcias se torna relativamente fácil, pois depois das cristas serem afinadas estas passarão a ter uma espessura de um pixel o que torna possível que seja utilizado um bloco 3x3 (pequeno) para varrer a imagem em busca das minúcias. Porém a extração das minúcias não é uma tarefa trivial como apresentado em muitas literaturas porque por menor que seja pode haver um caso que necessite de cuidados especiais durante o estágio de marcação destas.
O algoritmo para marcação das supostas minúcias dá-se através do processo, onde um bloco ou máscara de dimensão 3x3 percorrerá a imagem linha a linha para detectar terminações e bifurcações nas cristas papilares. Por exemplo, se o pixel central tem valor um e também mais três vizinhos com valor um, então este local será marcado como uma minúcia do tipo bifurcação. Agora se o pixel central possuir valor um e apenas um de seus pixels vizinhos também possuir valor um, então o local será marcado como uma minúcia do tipo terminação.
Fig. 3.7 Bifurcação e Terminação.
Fig. 3.8 Marcação das minúcias.
4. Etapa de pós-processamento
A etapa de pré-processamento não recupera completamente a imagem da impressão digital. Todas as etapas anteriores ocasionalmente introduzem algum tipo de ruído na imagem que posteriormente influenciam na detecção das minúcias. Por isso é necessário que haja um processo de remoção de falsas minúcias.
4.1 Remoção de falsas minúcias
As falsas minúcias afetam significativamente na precisão do processo que vem logo a seguir, que é o de verificação e comparação das minúcias para uma suposta identificação. Pois o sistema irá realizar comparações com pontos que na verdade não são as minúcias reais que diferenciam um indivíduo do outro, ocasionando assim uma falsa identificação. Portanto alguns mecanismos para remover as falsas minúcias são necessários para manter um sistema de verificação de impressões digitais
estável.
No diagrama abaixo são especificados seis tipos de falsas minúcias que ocorrem em uma imagem de impressão digital.
Fig. 4.1 Estrutura de falsas minúcias.
Em (a) temos um caso de quebra encontrado na crista papilar, já em (b) uma ponte que conecta duas cristas, no caso (c) ocorre um pequeno segmento de crista no vale também conhecido como ilhota, em (d) ocorre um caso
conhecido como lago que é o encontro de duas bifurcações existentes na mesma crista papilar criando um espaço entre ela, em (e) pode-se observar uma espúria que é uma pequena ramificação encontrada na crista e por último em (f) nota-se uma ocorrência de pontos isolados encontrados entre as cristas papilares.
O processo para remoção de falsas minúcias é o seguinte:
I – Se duas terminações estão dentro de um mesmo bloco com distância D e suas direções são coincidentes com uma pequena variação angular, então é imposta a condição de que não há nenhuma terminação entre as duas terminações que foram marcadas como minúcias, pois é considerado que houve uma quebra na crista (caso a).
II – Se a distancia entre duas bifurcações é menor que D e elas estão na mesma crista, é removida as duas bifurcações (casos b e d).
III – Se duas terminações se encontram em uma distância menor que a especificada em D, é removido as duas terminações (caso c).
IV – Se a distância entre uma bifurcação e uma terminação é menor que D e as duas minúcias se encontram na mesma crista são removidas ambas as minúcias (caso e).
V – Se por algum motivo ainda existirem pontos isolados entre as cristas papilares e estes não tiverem nenhum vizinho dentro da distância especificada, esta minúcia também será removida.
Fig. 4.2 Remoção de falsas minúcias.
5. Testes
Os testes foram realizados em um micro-computador AMD Athlon 64 3800+ com 2GB de memória RAM. E foram utilizadas 50 imagens obtidas por um sensor óptico e 50 obtidas através do SFinGe (Synthetic Fingerprint Generator), que gera imagens de impressões digitais sintéticas. Os resultados foram satisfatórios, visto que segundo [14] em uma digital contendo, entre 36 a 46 minúcias em média, 15 já são suficientes para realizar uma identificação correta. Analisando-se 10 imagens de cada banco de dados nas quais foram realizados os testes e em todas foram detectadas de 42 a 80 minúcias, e uma média de 18 minúcias detectadas corretamente. O que se enquadra nas estatísticas citadas acima.
Porém ainda é um número muito alto de falsas minúcias, o que incentivou mais pesquisas relacionadas a filtragem no domínio da freqüência com filtros passabaixas e passa-altas que estão sendo pesquisados para serem aplicados e agrupados ao projeto final.
6. Conclusões
O sistema apresentado atinge o objetivo que é o de detecção de minúcias nas imagens de impressões digitais, porém ainda está em fase de aperfeiçoamento. Mesmo assim apresenta várias técnicas de processamento de imagens que são relevantes para as etapas de detecção e marcação das minúcias. Na etapa de pós-processamento são definidos seis tipos de falsas minúcias que podem ser detectadas pelo algoritmo e posteriormente removidas o que torna o sistema mais robusto.
Referências
[1] LIU, S.; SILVERMAN, M. “A Practical Guide to Biometric Security Technology”. IT Pro, [S.l.], pp. 27-32, January/February, 2001.
[2] PRABHAKAR, S. “Fingerprint Classification and Matching Using a Filterbank”. PhD Thesis, Michigan State University, 2001.
[3] HONG, L.; JAIN, A. K. “Fingerprint Image Enhencement: Algorithm and Performance Evaluation” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, nº 8, pp. 777-789, 1998.
[4] The Third International Fingerprint Verification Competition. Disponível em: <http://bias.csr.unibo.it/fvc2004/>. Acesso em: 06 Dez 2006.
[5] HONG, L.; JAIN, A. K.; PANKANTI, S.; BOLLE, R. “Fingerprint Enhancement”. Proc. Third IEEE Workshop on Applications of Computer Vision, pp. 202-207, 1996.
[6] RATHA, N. K.; CHEN, S.; JAIN, A. K. “Adaptative Flow Orientation – Based Feature Extraction in Fingerprint Images”. Pattern Recognition, vol. 28, nº 11, pp. 1657-1672, 1995.
[7] FARINA, A.; KOVÁCS-VAJNA, Z. M.; LEONE, A. “Fingerprint minutiae extraction from skeletonized binary images”. Pattern Recognition, 32, pp. 877-889, 1999.
[8] CAPPELLI, R.; LUMINI, A.; MAIO, D.; MALTONI, D. "Fingerprint Classification by Directional Image Partitioning". IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, nº 5, pp. 402-421, 1999.
[9] ZHANG, Q.; HUANG, K.; HONG, Y. “Fingerprint Classification Based on Extraction and Analysis of Singularities and Pseudoridges. School of Electrical and Information Engineering University of Sydney, NSW 2006, Australia. [10] MEHTRE, B. M. "Fingerprint Image Analysis for Automatic Identification". Machine Vision and Aplicattions, vol. 6, n º 2 . 3, pp. 124-139, 1993.
[11] CHONG, M. S.; GAY, R. K. L.; TAN, H. N.; LIU, J. “Automatic Representation of Fingerprints for Data Compression by B-Spline Functions”. Pattern Recognition, vol. 25, nº 10, pp. 1199-1210, 1992.
[12] VERMA, M. R.; MAJUNDAR, A. K.; CHATTERJEE, B. ”Edge Detection in Fingerprints”. Pattern Recognition, vol. 20, nº 5, pp. 513-523, 1987.
[13] GONZALEZ, R. C.; WOODS, R. E. “Digital Image Processing”. Addison Wesley Publishing Company, 1987.
[14] PRABHAKAR, S. “Fingerprint Classification and Matching Using a Filterbank”. PhD Thesis, Michigan State University, 2001.