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

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.