Uma Maneira Simples de Obter Regiões de Interesse em Imagens de Impressões Digitais

Uma Maneira Simples de Obter Regiões de Interesse em Imagens de Impressões Digitais Igor L. P. Andrezza1,2, Erick V. C. de L. Borges1,2, Adriano da S. Marinho1,2, Adriana E. de Oliveira1,2, José R. T. Marques2, Pedro A. Jr.2, e Leonardo V. Batista1 1

Departamento de Informática – Universidade Federal da Paraíba (UFPB) 58051-900 – João Pessoa – PB – Brasil 2

Departamento de Pesquisa e Desenvolvimento, Divisão de Segurança Vsoft Tecnologia, Joao Pessoa, Paraiba {igor, erick, adrianosmarinho, drill}@di.ufpb.br, {raphaelmarques, pedro}@vsoft.com.br, [email protected]

Abstract. In order to use fingerprint images to identify people, image segmentation pre-processing is normally needed. In this paper, we show a simple technique to segment fingerprint images in background and foreground, so as to obtain the Region-Of-Interest (ROI) by using standard deviation, median and binarization filters. Resumo. Segmentar imagens de impressão digital para obter a região de interesse (ROI) é uma etapa necessária ao reconhecimento biométrico automático de indivíduos. Neste trabalho, apresentamos um método simples, que usa os filtros de desvio-padrão, mediana e binarização, para extração da região de interesse de impressões digitais.

1.Introdução Com a proliferação de serviços baseados em Internet, sistemas de identificação confiáveis tornaram-se componentes chaves de várias aplicações que disponibilizam serviços para usuários autenticados. Métodos tradicionais para estabelecer a identidade de um usuário incluem mecanismos baseados em conhecimento (e.g., senhas) e mecanismos baseados em tokens (e.g., cartões de identidade). Porém, tais mecanismos podem ser facilmente perdidos, roubados ou até mesmo manipulados, objetivando um acesso não autorizado. Neste contexto, entra em cena a autenticação por Biometria (Ross, Nandakumar, & Jain, 2006). A Biometria oferece um mecanismo de autenticação confiável utilizando traços (físicos ou comportamentais) que permitam identificar usuários baseados em suas características naturais. Assim, utilizando a Biometria é possível estabelecer a identidade de um usuário baseado em quem ele é (who you are) ao invés de em o que ele possui (what you possess) ou de o que ele lembra (what you remember) (Ross, Nandakumar, & Jain, 2006). Atualmente, a impressão digital é o traço biométrico mais utilizado no mundo. Isto se deve à unicidade das mesmas, bem como ao baixo custo associado aos produtos

que dela se utilizam. Identificar suspeitos de um crime é um exemplo de uso prático das impressões digitais. Sistemas que identificam automaticamente indivíduos utilizando impressões digitais são chamados de AFIS (Automatized Fingerprint Identification Systems). Neles, normalmente uma etapa de segmentação das imagens de impressão digital é necessária, pois separar a região de interesse faz com que o tempo de processamento diminua e evita erros indesejados (Maltoni, Maio, Jain, & Prabhakar, 2009). Neste trabalho, apresentamos um método de extração da ROI (Region Of Interest, região de interesse) em imagens de impressão digital que usa os filtros de desvio-padrão, mediana e binarização, em detrimento de métodos complexos que utilizam classificadores.

2.Fundamentação Teórica Nesta seção apresentamos os conceitos referentes a biometria, impressões digitais e segmentação de imagens necessários para o entendimento deste trabalho. 2.1 Biometria O termo Biometria se refere ao uso de características físicas ou comportamentais, tais como face, íris, impressão digital, voz e keystroke (forma de digitar), para identificar pessoas automaticamente. Uma vez que os identificadores biométricos não podem ser facilmente extraviados, forjados, ou compartilhados, métodos de identificação biométricos são considerados mais confiáveis do que métodos baseados em tokens (como smart cards) ou senhas (Maltoni, Maio, Jain, & Prabhakar, 2009). Assim, os sistemas de reconhecimento biométrico estão sendo cada vez mais implantados em um grande número de aplicações governamentais e civis. Devido ao fato das impressões digitais serem únicas e invariantes em relação à idade do indivíduo, técnicas de reconhecimento utilizando impressões digitais têm sido amplamente aplicadas em sistemas de identificação pessoal (Liu, Zhao, Guo, Liang, & Tian, 2011). Atualmente, o reconhecimento utilizando impressões digitais é o método mais popular de reconhecimento biométrico e é utilizado em todo o mundo pelas autoridades policiais na procura de suspeitos (Zhu, Yin, Hu, & Zhang, 2006). Apesar de ser um método popular, o reconhecimento biométrico utilizando impressões digitais não é perfeito. Erros que variam desde a forma como as impressões digitais são capturadas pelo sistema até a forma do matching podem ocorrer. Para uma referência completa dos tipos de erros e suas causas, o leitor deve consultar (Maltoni, Maio, Jain, & Prabhakar, 2009). 2.2 Extração da região de interesse em impressões digitais Uma imagem da impressão digital consiste em cristas (linhas escuras) e vales (linhas em branco) intercaladas. As terminações e bifurcações das cristas, chamadas minúcias, são os traços mais característicos da impressão digital (Zhu, Yin, Hu, & Zhang, 2006). A maioria dos AFIS é baseada em minúcias. Imagens de impressões digitais geralmente precisam ser segmentadas em segundo plano e primeiro plano (onde o primeiro plano é a região de interesse) para

remover as regiões que não contêm informações úteis antes de executar outros passos de processamento, tais como o realce e detecção de minúcias. Desta forma, o processamento de imagem vai consumir menos tempo de CPU e evitar erros indesejados, como a detecção de minúcias espúrias em imagem de baixa qualidade. 2.3 Trabalhos relacionados Nos parágrafos seguintes, citamos alguns trabalhos relacionados ao nosso. Em (Afsar, Arif, & Hussain, 2005), um algoritmo de segmentação de impressão digital que utiliza Fisher Discriminant Analysis and Learning Vector Quantization (LVQ) Neural Networks foi proposto. Os autores alegam uma taxa de apenas 1,8% de erros na segmentação de todas as bases de imagens FVC 2000 (Maio, Maltoni, Capelli, Wayman & Jain, 2000). (Shi, Wang, Qi, & Xu, 2004) apresenta um algoritmo que introduz novas características para extrair ROI em imagens de impressões digitais. Os autores utilizam uma etapa de pré-processamento para estimar a qualidade da impressão digital antes da segmentação. Depois, propõem e utilizam uma nova característica, denominada Momento Excêntrico, para localizar a fronteira borrada. Os autores informam que o algoritmo foi testado na base de imagens DB3 do FVC 2002 (Maio, Maltoni, Capelli, Wayman & Jain, 2002), entretanto não informam um percentual de acertos. Finalmente, (Bazen & Gerez, 2001) apresentou um algoritmo de segmentação de impressões digitais baseado em três características: a média, a coerência e a variância. Ele treina um classificador linear ótimo para classificar por pixel.

3. Algoritmo Proposto A fim de identificar a região de interesse em uma imagem de impressão digital, desenvolvemos um algoritmo de segmentação simples e eficaz. Seu fluxo de dados é mostrado na Figura 1 e seus passos são descritos a seguir.

Figura 1: Fluxo de dados do algoritmo

A Figura 2 mostra a impressão digital usada para ilustrar o nosso algoritmo de segmentação.

Figura 2: Imagem usada para ilustrar os passos do nosso algoritmo

Em primeiro lugar, um filtro de desvio padrão (Hengl, 2011) é aplicado à imagem da impressão digital de modo a obter sua variação em escala de cinza e dividir a imagem em blocos. O tamanho dos blocos é um parâmetro definido pelo usuário na aplicação do filtro de desvio padrão. A Figura 3 ilustra o resultado desta operação. O próximo passo é reduzir a imagem a partir de blocos de pixels. Todos os pixels em cada bloco resultante do processo de desvio padrão têm o mesmo valor. Consequentemente, cada bloco irá produzir um único pixel. Esta etapa é realizada visando à eliminação de informações redundantes, de modo que os resultados dos próximos passos não sejam afetados erroneamente. A Figura 3b mostra o resultado da segunda etapa. Por conseguinte, a fim de homogeneizar a imagem reduzida, um filtro de mediana (Arias-Castro & Donoho, 2009) é aplicado a ela. A mediana é usada em vez da média devido à sua capacidade de preservar as bordas da imagem. A Figura 3c ilustra o resultado. A imagem é binarizada no próximo passo, como mostrado na Figura 3d, a fim de separar o plano de fundo e o primeiro plano. A maior região contínua do primeiro plano, i.e., a maior região branca, é então identificada (usando o algoritmo conhecido como Region Growing) e marcada como ROI (Figura 3e). Por fim, a imagem segmentada é ampliada de volta ao seu tamanho normal. A Figura 4 ilustra o resultado final e a imagem original cercada pelo contorno da ROI.

(a)

(b)

(c)

(d)

(e)

Figura 3: Passos do algoritmo proposto. (a) Desvio padrão. (b) Redução por blocos. (c) Mediana. (d) Binarização. (e) Maior região contínua.

(a)

(b)

Figura 4: Último passo. (a) Resultado da extração da maior região contínua. (b) Desenho do contorno da ROI na imagem original.

4. Resultados Para avaliar a nossa técnica, efetuamos um teste de calibração dos parâmetros dos filtros, descrito a seguir. 4.1 Calibração dos parâmetros dos filtros Quatro parâmetros podem ter seus valores alterados no algoritmo para que se obtenha uma melhor região de interesse: tamanho da janela mediana, limiar de binarização e os tamanhos do bloco interno e do bloco externo. O tamanho do bloco interno refere-se ao tamanho dos blocos produzidos pelo desvio-padrão e o tamanho do bloco externo refere-se ao tamanho da janela usada para calcular o desvio-padrão. Para calibrar estes valores e descobrir quais produzem os melhores resultados, escolhemos aleatoriamente 50 imagens do banco de impressões digitais UareU (NEUROtechnology, 2007). Os valores padrão dos parâmetros que produzem os melhores resultados são, baseados em testes empíricos, respectivamente: 2, 25, 5, 10. A Figura 5 mostra os resultados do algoritmo (com variações nos parâmetros) para a mesma imagem de entrada, onde a Figura 5a mostra o resultado com os melhores valores. Os resultados são descritos nos parágrafos seguintes. Variações no tamanho da janela da mediana (abaixo e acima do melhor valor, respectivamente) foram testadas nas Figuras 5b e 5c. Durante o teste, observou-se que, quanto menor o valor, mais sensível é o algoritmo (detectando as mínimas falhas da imagem). O aumento no valor produz um contorno mais preciso (que desconsidera pequenas imperfeições). O limiar de binarização foi testado nas Figuras 5d e 5e. Na Figura 5d, ele foi testado com um valor abaixo do melhor, enquanto que na Figura 5e, com um valor acima. Observa-se que a diminuição deste parâmetro faz com que o algoritmo encontre uma região de interesse muito maior (e, portanto, imprecisa). Aumentar o valor torna o algoritmo mais preciso, causando na região de interesse a eliminação de partes de baixa qualidade da impressão digital.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figura 5: Resultados com diferentes valores nos parâmetros.

Nas Figuras 5f e 5g, valores diferentes para o tamanho do bloco interno (abaixo e acima do melhor valor) foram aplicados. O valor mais baixo leva a um maior detalhamento da ROI, enquanto o oposto ocorre com o mais elevado. Nota-se também que, quanto maior o valor, menor o tempo de processamento do algoritmo, conforme mostra a Figura 6.

Figura 6: Gráfico do tempo de processamento x tamanho do bloco interno.

Finalmente, as Figuras 5h e 5i ilustram a variação do tamanho do bloco externo, respectivamente acima e abaixo do melhor valor. O tamanho do bloco externo sempre tem que ser maior que o tamanho do bloco interno. Os testes indicam que, quanto mais próximo do melhor valor, mais sensível é o resultado do algoritmo. Além disso, quanto maior o valor do tamanho do bloco externo, maior o tempo de processamento, conforme mostra a Figura 7.

Figura 7: Gráfico do tempo de processamento x tamanho do bloco externo.

5. Discussão e Conclusão Neste trabalho, uma nova técnica para extrair a região de interesse em imagens de impressão digital foi apresentada. Em primeiro lugar, o filtro de desvio padrão é aplicado à imagem, esta é reduzida em blocos e um filtro de mediana é aplicado para homogeneizá-la. A imagem homogeneizada é binarizada e a região de interesse é extraída a partir da maior região contínua. Por último, a imagem é devolvida ao seu tamanho normal.

Quatro parâmetros referentes aos filtros (tamanho da janela mediana, limiar de binarização e os tamanhos do bloco interno e do bloco externo) foram testados para descobrir quais os valores representavam as melhores escolhas (2, 25, 5, 10) para a aplicação pretendida. Dependendo da segmentação desejada, não necessariamente devemos usar esses valores que representam a melhor escolha. Consideramos a possibilidade de troca dos valores como uma vantagem do nosso algoritmo. Quando comparado com outras técnicas, verificamos que a simplicidade de implementação de nossa técnica é uma vantagem. Por exemplo, ela não usa classificadores como (Bazen & Gerez, 2001), (Yin, Zhu, Yang, Zhang, & Hu, 2007) e (Zhu, Yin, Hu, & Zhang, 2006), e não desenvolve uma nova medida como (Shi, Wang, Qi, & Xu, 2004) e (Afsar, Arif, & Hussain, 2005). Além disso, ela permite a manutenção das regiões de baixa qualidade na ROI e o ajuste entre a sua velocidade ou precisão, através da variação de parâmetros. Porém, a fim de comparar a eficácia de nosso algoritmo com a eficácia das técnicas citadas (em relação aos acertos na classificação de imagens), apontamos como trabalho futuro a segmentação (manual e automática) completa das bases de impressões digitais FVC 2000 e FVC 2002 DB3. A extração da ROI em imagens de impressões digitais é um passo importante para o reconhecimento biométrico através deste traço. Uma detecção mais precisa desta região auxilia na extração de informação relevante a ser usada no processo de comparação de impressões digitais tanto para a verificação (autenticação) quanto para a identificação de indivíduos, contribuindo para reduzir as taxas de erro do sistema. Para trabalhos futuros, pretende-se também obter resultados quantitativos sobre como a região de interesse extraída afeta o processo de identificação e autenticação em sistemas biométricos.

6.Bibliografia Afsar, F. A., Arif, M., & Hussain, M. (2005). An Effective Approach to Fingerprint Segmentation using Fisher Basis. 9th International Multitopic Conference, IEEE INMIC 2005, (pp. 1-6). Arias-Castro, E., & Donoho, D. L. (2009). Does median filtering truly preserve edges better than linear filtering? Annals of Statistics, 1172-1206. Bazen, A. M., & Gerez, S. H. (2001). Segmentation of Fingerprint Images. PRORISC 2001 Workshop on Circuits, Systems and Signal Processing, (pp. 276-280). Hengl, T. (2011). Standard deviation filters. Retrieved Julho 15, 2011, from "http://spatialanalyst.net/ILWIS/htm/ilwisapp/filter_types_standard_deviation_filters.htm" Liu, E., Zhao, H., Guo, F., Liang, J., & Tian, J. (2011). Fingerprint segmentation based on an AdaBoost classifier. Frontiers of Computer Science in China, 5(2). Maio, D., Maltoni, D., Cappelli, R., Wayman, J., & Jain, A. (2000). FVC2000: Fingerprint Verification Competition. Relatório Técnico. Acesso em Agosto de 2011, disponível em http://bias.csr.unibo.it/fvc2000/Downloads/fvc2000_report.pdf.

Maio, D., Maltoni, D., Cappelli, R., Wayman, J., & Jain, A. (2002). FVC2002: Second Fingerprint Verification Competition. Proceedings of 16th International Conference on Pattern Recognition (ICPR2002) (pp. 811-814). Disponível em http://bias.csr.unibo.it/fvc2002/Downloads/FVC2002_ICPR.pdf. Maio, D., Maltoni, D., Cappelli, R., Wayman, J., & Jain, A. (2004). FVC2004: Third Fingerprint Verification Competition. Springer Berlin / Heidelberg. Maltoni, D., Maio, D., Jain, A. K., & Prabhakar, S. (2009). Handbook of Fingerprint Recognition (2ª ed.). 1848822537: Springer Publishing Company, Incorporated. NEUROtechnology. (2007, Janeiro). U.are.U 4000 sample fingerprint database. Retrieved Julho 10, 2011 Ross, A. A., Nandakumar, K., & Jain, A. K. (2006). Handbook of Multibiometrics (International Series on Biometrics). Secaucus, NJ, USA: Springer-Verlag New York, Inc. Shi, Z., Wang, Y., Qi, J., & Xu, K. (2004). A New Segmentation Algorithm for Low Quality Fingerprint Image. Proceedings of the Third International Conference on Image and Graphics (pp. 314-317). Washington, DC, USA: IEEE Computer Society. Yin, J., Zhu, E., Yang, X., Zhang, G., & Hu, C. (2007). Two steps for fingerprint segmentation. Image Vision Comput., 1391-1403. Zhu, E., Yin, J., Hu, C., & Zhang, G. (2006, Agosto). A systematic method for fingerprint ridge orientation estimation and image segmentation. Pattern Recogn., 39(8), 1452-1472.