Uso de impressão digital para biometria

Uso de impress˜ao digital para biometria Antonio Paoli, Gabriel Dahia, Lucas Amparo 5 de Setembro de 2016

1

Introdu¸ c˜ ao

de superf´ıcies ou objetos que foram tocados por seu dono. O uso de digitais latentes ´e muito difundido na ciˆencia forense. Adv´em da colheita indireta dessas imagens a dificuldade de identificar pessoas apenas com esse tipo de impress˜ao. Geralmente, nesses casos, a informa¸c˜ao das cristas ´e pouco clara, a ´ area dispon´ıvel ´e menor do que o usual (o que significa um n´ umero menor de min´ ucias) e ela sofre de forte distor¸c˜ao n˜ao-linear devido a press˜ao [8]. A difus˜ao da impress˜ao digital como identificador biom´etrico provavelmente est´a atrelada a suas vantagens: o custo vinculado `a sua implementa¸c˜ao ´e baixo (hoje em dia, sensores capazes de colher digitais j´ a est˜ao presentes em celulares e computadores pessoais), sua permanˆencia e singularidade, dois fatores essenciais a uma biometria, j´a foram estabelecidos [16], e, de maneira geral, seres humanos possuem dez dedos, o que garante sua universalidade [2]. Esses fatores tamb´em garantiram sua aplica¸c˜ao em ´areas de maior visibilidade pelas pessoas. Isso, aliado a rapidez da coleta, tornou a impress˜ao digital uma das biometrias mais aceitas pela popula¸c˜ao. Por outro lado, dependendo da qualidade do leitor ´otico em que ´e feita a captura da impress˜ao digital, este tipo de biometria pode ser facilmente burlada. Outro ponto que pesa contra ela ´e a necessidade do usu´ario estar conivente com o uso e manter contato direto com o leitor [13]. Na literatura, a grande maioria dos m´etodos se utiliza de algum conjunto de peculiaridades das impress˜oes digitais. Nesses casos, ´e preciso que elas sejam demarcadas nas imagens colhidas, seja de forma manual ou autom´atica. Um desses processos ´e a detec¸c˜ao de singular points, uma outra denomina¸c˜ao para os conhecidos delta e n´ ucleo. O delta ´e uma regi˜ao onde ocorrem di-

O uso de impress˜ oes digitais como um meio de identifica¸c˜ ao de indiv´ıduos ´e muito mais antigo do que se pode imaginar. Retratos hist´ oricos apontam o uso desse tipo de biometria antes mesmo do nascimento de Cristo, na China, com t´ abuas de barro que eram utilizadas para identificar compradores e em potenciais investiga¸c˜ oes criminais. Outros relatos apontam seu uso em diversas culturas espalhadas pelo mundo, como na P´ersia, muito antes da existˆencia de tecnologias que automatizassem essa identifica¸c˜ ao [15]. J´a no s´eculo XIX, muitos acadˆemicos da ´ area de Anatomia atuaram nesta linha de pesquisa, propondo artigos que discutiam os padr˜ oes vinculados as pessoas, como marcas de fric¸c˜ ao, espiras e curvas. Francis Galton deu o nome de ”min´ ucias”a estas peculiaridades. Essas min´ ucias podem ser classificadas como fim de linha, bifurca¸c˜ oes ou ilhas. Outras marca¸c˜oes tamb´em relevantes s˜ ao o n´ ucleo (ou centro) da impress˜ ao digital e o delta. Dentre os trabalhos do s´eculo citado, um dos mais relevantes foi o do policial argentino Juan Vucetich, que conseguiu classificar as marcas dos dedos em quatro padr˜ oes (Arco, Presilha Interna, Presilha Externa e Verticilo), al´em de criar um m´etodo de armazenamento para essas informa¸c˜ oes, baseado em tinta e papel. Bastava o indiv´ıduo sujar a ponta dos dedos com algum tipo de tinta e pression´ a-lo contra o papel, resultando em uma c´ opia fiel de sua digital [3]. Impress˜ oes digitais podem ser colhidas de diversas maneiras: em um ambiente colaborativo, geralmente s˜ ao classificadas como roladas ou planas, nomenclaturas referentes ao movimento realizado pelo dedo no papel ou sensor de coleta; podem tamb´em ser obtidas indiretamente - s˜ ao as impress˜ oes latentes, extra´ıdas 1

Figura 1: Delta e N´ ucleo. Grosso

Fonte: Politec Mato

versas bifurca¸c˜ oes em sequˆencia. J´ a o n´ ucleo ´e o centro da impress˜ ao, onde ocorrem diversas curvas nas linhas. Ambos os pontos s˜ ao apresentados na Figura 1. No trabalho de Alias et al [1], um novo m´etodo de valida¸c˜ ao biom´etrica foi implementado, onde cada ponto marcado gera um template u ´nico, com base na posi¸c˜ ao espec´ıfica de cada singularidade. Outro processo ´e a detec¸c˜ ao de min´ ucias. Dentre as diversas dispon´ıveis, as mais simples de serem utilizadas s˜ ao os fins-de-linha e as bifurca¸c˜ oes, apresentadas na Figura 2. O trabalho apresentado por Reddy [18] prop˜ oe um algoritmo de matching usando min´ ucias at´e mesmo para digitais latentes. Quando se trata da utiliza¸c˜ ao de impress˜oes digitais de adultos, roladas ou planas, colhidas em ambiente controlado e com equipamento moderno, pode-se dizer que esse ´e um processo consolidado e os desafios que ainda enfrenta est˜ ao relacionados com a seguran¸ca e eficiˆencia de seus m´etodos. Existem outras situa¸c˜ oes, contudo, onde ainda existem desafios de outras naturezas. Os resultados obtidos com identifica¸c˜ ao de impress˜ oes latentes, por exemplo, ainda n˜ ao s˜ ao compar´ aveis ` aqueles obtidos entre impress˜oes de melhor qualidade. Algumas pesquisas apontam poss´ıveis solu¸c˜oes contra o problema do “dedo morto”, que ´e a tentativa de burlar o sistema utilizando um dedo falso, utilizando mecanismos como sensores de temperatura ou diferen¸cas na intera¸c˜ ao com a luz ambiente, aumentando assim a confiabilidade do m´etodo. A Dermalog, empresa alem˜ a, lan¸cou em 2011 um leitor que resolve

Figura 2: Fins-de-linha e Bifurca¸c˜oes.

este problema com grande eficiˆencia. A aplicabilidade de uma leitura biom´etrica precisa ´e t˜ao grande que pode ser utilizada at´e mesmo para efetuar chamadas de emergˆencia, como proposto por Srividya & Ramesh [17], onde um smartphone se torna fundamental para a r´apida resposta em situa¸c˜oes de perigo eminente. A seguran¸ca dos templates biom´etricos de digitais ´e fundamental. Estudos [4, 19] mostram que ´e poss´ıvel reconstruir uma digital a partir apenas de uma representa¸c˜ao de suas min´ ucias. Outra vulnerabilidade ´e a intercepta¸c˜ao por terceiros de informa¸c˜oes durante o trˆansito entre o leitor biom´etrico e a unidade de processamento [21]. Atualmente, diversas pesquisas tem como objetivo melhorar o processo j´a existente. O trabalho de Labati et al. [12] inclusive aponta um m´etodo de leitura que n˜ao necessite de contato direto com o leitor, denominado touchless. J´a Kaggwa et al. [11] apresentou um trabalho que melhorava a performance da identifica¸c˜ao atrav´es de um m´ ultiplo cadastro de digitais, tornando consideravelmente mais robusta a constru¸c˜ao do template. 2

Tamb´em na vertente da seguran¸ca, Galbally et al. 2 Marca¸c˜ ao manual de [5] construiu um trabalho onde ´e poss´ıvel detectar min´ ucias diversos tipos de biometrias falsas, inclusive para impress˜ oes digitais, a partir de uma an´ alise da qualidade 2.1 Processo de marca¸c˜ ao da imagem obtida na aquisi¸c˜ ao. Caso essa imagem n˜ ao atenda os padr˜ oes predefinidos, o c´ odigo emitir´a Para a valida¸c˜ao de nosso sistema autom´atico de um alerta de falsa biometria. detec¸c˜ao de min´ ucias, ´e necess´ario comparar as marca¸c˜oes realizadas pelo sistema com marca¸c˜ oes O principal benchmark relacionado a impress˜ao di- verdadeiras, o ground truth. Assim, decidimos que gital como biometria ´e mantido pelo NIST, um insti- cada um dos autores deveria marcar manualmente as tuto dos EUA que mensura diversas ´ areas de estudos min´ ucias nas impress˜oes digitais dispon´ıveis em nossa tecnol´ ogicos. O FpVTE avalia a performance de al- base de imagens. Ela possui 250 imagens de 50 ingoritmos na busca de uma digital em um conjunto de div´ıduos, com exatamente 5 imagens por indiv´ıduo. milh˜ oes. J´ a o PFT, agora chamado de PFTII, menNossa marca¸c˜ao manual se limitou a fins de linha sura a eficiˆencia dos templates utilizados em solu¸c˜oes e bifurca¸c˜oes. Escolhemos basear nosso sistema de comerciais. Outros testes, como (SlapSeg, MINEX e reconhecimento nessas min´ ucias pelo seu amplo uso ELST ), tamb´em est˜ ao dispon´ıveis e s˜ ao amplamente na literatura [7, 10] e por sua alta frequˆencia em imutilizados como base de compara¸c˜ ao. press˜oes digitais. Outras min´ ucias, como o centro, por exemplo, n˜ao s˜ao encontradas em todas as imaUm outro benchmark avaliando a performance de gens de nossa base. algoritmos de reconhecimento de impress˜ oes digitais ´e Para realizar a marca¸c˜ao manual, foi desenvolvido o Fingerprint Verification Competition (FVC), manum programa que escolhia aleatoriamente N imagens tido pelo Biometric System Laboratory da Univerda base para realiza¸c˜ao sequencial da marca¸c˜ao das sidade de Bologna. Antes apresentado como uma min´ ucias. O programa apresenta uma imagem e o competi¸c˜ ao realizada de dois em dois anos, com prausu´ario marca, separadamente, os fins de linhas e bizos para submiss˜ ao, atualmente est´ a na vers˜ao FVCfurca¸c˜oes. Findada a marca¸c˜ao de uma imagem, as onGoing, que ´e descrito pelos pr´ oprios organizadores coordenadas das marca¸c˜oes s˜ao salvas em um arquivo como “uma competi¸c˜ ao em curso”e um “reposit´orio de texto e o sistema oferece outra imagem at´e que online para avalia¸c˜ ao de m´etricas e resultados”. A o usu´ario marque as N imagens destinadas `aquela avalia¸c˜ ao dos m´etodos ´e automatizada em uma plasess˜ao ou aborte a execu¸c˜ao do programa. O valor taforma web e os resultados s˜ ao publicados na p´agina de N era decidido de acordo com a comodidade do dedicada ao FVC [14]. autor. A aleatoriedade da apresenta¸c˜ao das imagens viCom base na revis˜ ao para essa breve introdu¸c˜ao, sou for¸car os autores a reexaminar as imagens de foi acordado pela implementa¸c˜ ao um sistema de reum mesmo indiv´ıduo atrav´es da separa¸c˜ao tempoconhecimento de impress˜ oes digitais atrav´es do matral entre as marca¸ c˜oes e dessa forma, possivelmente, ching de min´ ucias de primeiro n´ıvel - fins de linha e perceber min´ u cias que n˜ao haviam sido notadas em bifurca¸c˜ oes. Para isso, precisamos primeiramente imoutra sess˜ a o de marca¸ c˜ao. A decis˜ao de dividir em plementar um sistema autom´ atico de detec¸c˜ao dessas conjuntos separados essas min´ ucias foi tomada com min´ ucias. O resultado final deste trabalho se enconintuito de facilitar o reconhecimento (somente depois 1 tra acess´ıvel na plataforma emphGithub ver´ıamos que isso n˜ao ´e necessariamente verdade).

2.2 1 Para acessar o https://github.com/gdahia/afis

c´ odigo

Gera¸c˜ ao do ground truth

Ap´os as marca¸c˜oes individuais realizadas por cada autor, foi necess´aria a constru¸c˜ao de uma marca¸c˜ ao

fonte:

3

Falsa), DR (Discovery Rate, Taxa de N˜ao-Descoberta Falsa), a distˆancia m´edia de uma marca¸c˜ao para a min´ ucia gerada em sua correspondˆencia e o desvio padr˜ao dessa estat´ıstica, tendo por base as correspondˆencias obtidas no algoritmo do c´alculo de correspondˆencias. Os resultados se encontram na Tabela 1.

consolidada para cada imagem. Para isso, idealizamos o seguinte m´etodo para unir as marca¸c˜oes de uma mesma imagem I: para cada min´ ucia mi em um conjunto de marca¸c˜ oes de um autor, ´e buscado nas marca¸c˜ oes dos outros autores para esta mesma imagem, a min´ ucia de mesmo tipo mais pr´oxima a ´ medida, ent˜ esta. E ao, a distˆ ancia entre as min´ ucias encontradas e mi . Em seguida, ´e verificado se cada uma dessas distˆ ancias ´e maior do que uma constante t. Caso afirmativo, ´e considerado que, para o autor daquela marca¸c˜ ao, n˜ ao houve uma correspondˆencia e ele falhou em apontar mi em suas marca¸c˜oes. Isso nos permite evitar o seguinte cen´ ario: ap´os todas as correspondˆencias corretas entre as marca¸c˜oes de uma mesma imagem serem encontradas, dois autores poderiam ter falhado, cada um, em marcar uma min´ ucia que o outro marcou, o que geraria uma correspondˆencia esp´ uria entre essas marca¸c˜ oes. Depois de encontradas todas as correspondˆencias, calculamos uma nova min´ ucia mT da seguinte forma: P mj ∈Ci mj mT = |Ci |

Vemos que os resultados encontrados validam o limiar utilizado: a m´edia das distˆancias para todos os autores foi inferior 2 pixels, assim como seus desvios ´ interessante notar que, mesmo considepadr˜oes. E rando marca¸c˜oes sem correspondˆencia com outros autores como v´alidas e as adicionando ao ground truth, ainda houve, para todos os autores, falsas detec¸c˜ oes. A explica¸c˜ao desse fato adv´em do limiar t utilizado: marca¸c˜oes de um mesmo autor que distavam menos de t pixels de uma correspondˆencia j´a estabelecida, eram eliminados.

Um outro aspecto interessante da gera¸c˜ao do ground truth ´e que, para gerar correspondˆencias, ele utiliza inerentemente a ordem com que foram marcaucias pelos autores. Uma vez que uma coronde C denota o conjunto de correspondˆencias das as min´ respondˆ e ncia ´e estabelecida, ela ´e considerada como v´ alidas entre mi e as marca¸c˜ oes dos outros autores, a melhor correspondˆ encia para aquele trio de pontos. al´em da pr´ opria mi , a soma ´e considerada como soma Dessa forma, caso os autores tivessem marcados os de pontos de coordenadas, assim como divis˜ao por um pontos em outra ordem, o resultado seria diferente. escalar. Aplicando esse processo a todas min´ ucias, tePelos resultados encontrados e pelo aspecto visual do mos dois conjuntos resultantes para a imagem I, FTI , ground truth, julgamos, por´ e m, que os resultados separa as marca¸c˜ oes de fins-de-linhas, e BTI , para as riam m´ ınimos. marca¸c˜ oes de bifurca¸c˜ oes. Marca¸c˜ oes para as quais n˜ ao foram encontradas correspondˆencias s˜ao todas consideradas v´ alidas e adicionadas a esses conjuntos, para todos os autores. Assim, n˜ ao perdemos min´ ucias FDR DR µ σ as quais passaram desapercebidas pelos autores. Lucas Amparo 0,02% 30,61% 1,32 1,02 Gabriel Dahia 0,10% 21,34% 1,19 0,88 2.3 Resultados e discuss˜ ao Antonio Paoli 0,02% 23,68% 1,11 1,00 Utilizando o procedimento descrito acima, foram encontrados, para cada imagem I, os conjuntos FTI e Tabela 1: Compara¸c˜oes de Performance. µ denota a BTI . Escolhemos um valor de t = 8 empiricamente, distˆancia m´edia das marca¸c˜oes em pixels e σ denota observando apenas o aspecto visual do resultado geo desvio padr˜ao. rado ao variar de valores de 0 a 10. N˜ ao foram geradas estat´ısticas para t 6= 8. Em seguida, foram calculados os FDR (False Discovery Rate, Taxa de Descoberta 4

3

Detec¸ c˜ ao min´ ucias

autom´ atica

de

As imagens de impress˜ oes digitais apresentam distor¸c˜ oes como ru´ıdos esp´ urios e confus˜ oes para diferenciar claramente na imagem vales e cristas. Isso, al´em da existˆencia de poros e rupturas no padr˜ ao das cris´ tas, dificulta a extra¸c˜ ao autom´ atica das min´ ucias. E usual na literatura [7, 20] fazer um pr´e-processamento para diminuir o impacto dessas caracter´ısticas inerentes ` a imagens de impress˜ ao digital. Esse processo ´e geralmente chamado de melhoria da imagem. Neste Figura 4: Imagem representando a orienta¸c˜ao para trabalho, utilizamos uma vers˜ ao adaptada do pro- janelas de pixels. cesso proposto por Hong et al. [7] para realizar a melhoria da imagem e, em seguida, realizar a extra¸c˜ao gradientes nessas dire¸c˜oes para cada pixel (i, j), redas min´ ucias na imagem resultante. presentados por ∂x (i, j) e ∂y (i, j), respectivamente. Qualquer filtro serviria para esse pr´oposito; escolhe3.1 Melhoria da imagem mos o filtro Sobel pois essa ´e a escolha apresentada no orios O processo descrito por Hong et al. apresenta um artigo original, ele apresenta resultados satisfat´ m´etodo de normaliza¸c˜ ao para aumentar o contraste e sua execu¸c˜ao tem custo computacional baixo. Esentre cristas e vales. Contudo, ao implement´a-lo, ses valores s˜ao utilizados nas equa¸c˜oes 1-3 para a obn˜ ao ficamos satisfeitos com o resultado e resolvemos ten¸c˜ao de uma orienta¸c˜ao O(i, j) para cada pixel. A empregar um m´etodo mais utilizado nos dias atuais, figura 4 apresenta uma representa¸c˜ao gr´afica para vio filtro CLAHE (Contraste Limited Adaptive Histo- sualiza¸c˜ao da orienta¸c˜ao obtida para alguns pixels. Dentre os pontos baixos da maneira escolhida para gram Equalization) [20]. Ele ´e mais apropriado para imagens de impress˜ oes digitais por ser adaptativo `as detectar a orienta¸c˜ao dos pixels, destacamos o fato de ao distribui¸c˜ oes de histograma ao longo de toda a ima- que no centro das digitais, a estimativa da orienta¸c˜ n˜ao apresenta um resultado satisfat´orio. Isso se deve gem. a brusca mudan¸ca de orienta¸c˜ao dentro da janela de 16pixels × 16pixels para essa regi˜ao.

Φx (i, j) =

i+8 X

j+8 X

(∂x2 (u, v) − ∂y2 (u, v))

(1)

u=i−8 v=j−8

Φy (i, j) =

i+8 X

j+8 X

(2∂x (u, v)∂y (u, v))

(2)

u=i−8 v=j−8

Figura 3: CLAHE.

Imagem equalizada utilizando o filtro O(i, j) =

1 tan−1 2



Φx (i, j) Φy (i, j)

 (3)

Em seguida, atrav´es da aplica¸c˜ ao do filtro de SoCom a informa¸c˜ao de orienta¸c˜ao para cada pixel, bel nos sentidos horizontal e vertical, s˜ ao obtidos os ´e poss´ıvel aproximar a topologia de uma regi˜ ao de 5

Figura 6: Imagem antes (`a esquerda) e depois (` a direita) da aplica¸c˜ao do filtro Gabor. Figura 5: Janela perpendicular a orienta¸ca˜o das cristas e assinatura X.

cristas e vales como uma curva senoide. Assim, utilizando uma janela perpendicular a orienta¸ca˜o naquele ponto (como visto na figura 5), estimamos o comprimento dessa onda. Em seu artigo, Hong et al. descreve como obter a assinatura X para cada janela, mas ´e vago em como aproximar os valores obtidos em uma senoide. Esse processo n˜ ao se resume a apenas contar picos, vales ou cruzamentos pelo 0 - os j´ a citados poros e rupturas no padr˜ ao de cristas deformam consideravelmente a curva encontrada. Dessa forma, filtramos regi˜oes de pico utilizando a amplitude RMS (Root mean squared ) e calculamos as distˆ ancias entre os centros dessas regi˜ oes. Esse resultado ´e o comprimento de onda para cada pixel. Por fim, utilizamos essas informa¸c˜ oes - orienta¸c˜ao e comprimento de onda - para melhoria da qualidade da impress˜ ao digital, aplicando um filtro de Gabor [9] em cada pixel da digital. Como visto nas equa¸c˜oes 4-6 do filtro, a intensidade de cada pixel depende diretamente de sua vizinhan¸ca, onde I(i, j), L(i, j), O(i, j) e E(i, j) s˜ ao, respectivamente, o valor na imagem equalizada, comprimento de onda, a orienta¸c˜ao e o valor resultante do pixel (i, j). A figura 6 apresenta uma imagem de digital antes e uma imagem depois do processo.

m(x, y, θ) = −

1 2



(xcosθ)2 (ysenθ)2 + δx2 δy2 

h(x, y; θ, λ) = exp(m(x, y, θ))cos



2πx cosθ λ



E(i, j) =

15 X

15 X

h(u, v; θ(i, j), L(i, j))I(i−u, j−v)

u=−15 v=−15

O resultado ´e bastante satisfat´orio para imagens como a apresentada, onde n˜ao h´a regi˜oes uniformes com apenas cristas ou vales e a orienta¸c˜ao n˜ao varia bruscamente. Isso n˜ao ´e a regra para imagens de impress˜ao digital. Em regi˜oes onde n˜ao h´a cristas, por exemplo, as estimativas da orienta¸c˜ao e do comprimento de onda geram resultados imprevis´ıveis. A aplica¸c˜ao do filtro de Gabor com essas informa¸c˜ oes equivocadas acaba gerando nessa regi˜ao uma grande quantidade de cristas falsas, o que inevitavelmente leva a cria¸c˜ao de min´ ucias n˜ao existentes na imagem original. Outro exemplo de situa¸c˜ao desfavor´avel ao m´etodo apresentado ´e a ocorrˆencia de falhas em uma crista, como um grande poro: ao inv´es de fech´ a-lo, como deveria, a crista em quest˜ao ´e dividida em duas cristas menores.

3.2

Detec¸c˜ ao autom´ atica

Como a imagem resultante do processo de melhoria j´a est´a binarizada, aplicamos o processo de “esqueletiza¸c˜ao”como proposto por Guo-Hall [6]. O resultado ´e uma imagem em que cristas possuem apenas 1 pixel de espessura, como na figura 7. Nessa imagem, ´e (4) trivial extrair as min´ ucias contando o n´ umero de vizinhos de cada pixel pertencente a uma crista - aqueles que possuem apenas um vizinho n˜ao cont´ıguo s˜ao fins de linha, os que possuem trˆes vizinhos s˜ao bifurca¸c˜ oes (5) e nada al´em disso s˜ao min´ ucias de interesse. 6

tema. O procedimento escolhido para gerar as correspondˆencias ´e: para cada min´ ucia mi marcada automaticamente, ´e tentado o pareamento com uma min´ ucia mj do ground truth. A correspondˆencia ´e considerada v´alida se j ´e tal que mj = argmin(d(mi , mk )) mk ∈M

mi = argmin(d(mk , mj ))

Figura 7: Resultado do processo de esqueletiza¸c˜ao.

mk ∈G

d(mi , mj ) ≤ t onde M ´e o conjunto de marca¸c˜oes autom´aticas, G ´e o ground truth para essa mesma imagem e t ´e um limiar pr´e-estabelecido. Caso n˜ao exista j que satisfa¸ca essas condi¸c˜oes, ´e considerado que mi ´e uma marca¸c˜ao n˜ao-existente no ground truth. A figura 9 apresenta os resultados obtidos ao variar de t. Percebemos que, mesmo com limiar de distˆancia elevado (at´e 30 pixels), as detec¸c˜oes falsas s˜ao superiores a 50%. Uma tentativa de explicar esse resultado pode ser feita `a luz do que j´a foi dito antes: em regi˜oes onde n˜ao h´a cristas, por exemplo, o processo de melhoria da imagem gera diversas min´ ucias n˜ao existentes. Al´em do mais, o m´etodo empregado, diferentemente de um humano, n˜ao ´e capaz de diferenciar a ocorrˆencia de fins de linha ocasionados por cicatrizes ou falhas na digital; os artefatos criados por essas situa¸c˜oes tamb´em s˜ao erroneamente identificados como min´ ucias. Apesar disso, nosso sistema ´e capaz de identificar 60% com um limiar de 15 pixels, o que consideramos um resultado satisfat´orio.

Figura 8: Extra¸c˜ ao de min´ ucias em cristas com um pixel de espessura.

3.3

Resultados e discuss˜ ao

Com um processo de extra¸c˜ ao autom´atico de min´ ucias funcional, extra´ımos as min´ ucias de todas as impress˜ oes digitais em nossa base de imagens. Durante esse processo, percebemos que, diversas vezes, a melhoria na imagem causava a jun¸c˜ ao de um fim de linha com uma crista (transformando-a efetivamente em uma bifurca¸c˜ ao), e a separa¸c˜ ao de uma bifurca¸c˜ao em um fim de linha pr´ oximo a uma crista. Isso nos levou a descartar a separa¸c˜ ao das min´ ucias em duas classes e considerar apenas min´ ucias de maneira geral. O resultado desse processo foram as coordenadas das min´ ucias de cada imagem salvas em arquivos de texto separados. A valida¸ca˜o realizada para nosso procedimento de detec¸c˜ ao autom´ atica de min´ ucias consiste em tentar fazer a correspondˆencia entre uma marca¸c˜ao gerada automaticamente com uma min´ ucia do ground truth. Caso n˜ ao seja encontrada uma correspondˆencia v´ alida, a marca¸c˜ ao gerada automaticamente ´e contabilizada como um falso positivo. Em seguida, com base nos n´ umeros de correspondˆencias v´ alidas e de falsos positivos, s˜ ao calculados FDR e o DR do sis-

4

Reconhecimento baseado em min´ ucias

Um sistema de identifica¸c˜ao biom´etrico baseado em imagens de digitais deve receber uma imagem de impress˜ao digital e uma suposta identidade previamente cadastrada e, com essas informa¸c˜oes e aquelas armazenadas em seu banco de dados, determinar se o indiv´ıduo ´e quem ele diz ser. 7

1.0 0.8

• Somat´orio dos erros: efetua-se a soma de todas as distˆancias euclidianas entre as correspondˆencias v´alidas encontradas;

0.6

min´ ucias presentes na digital de entrada sem correspondˆencia com o conjunto de min´ ucias pr´evio;

0.4

• Erro m´edio: ´e a raz˜ao entre o somat´orio dos erros e a quantidade de correspondˆencias v´alidas;

0.2

• Desvio padr˜ao: ´e o desvio padr˜ao do erro m´edio em rela¸c˜ao ao erro de cada correspondˆencia. FDR DR 0.0

4.1

Sistema de reconhecimento

Dada a imagem de impress˜ao digital de entrada, nosso sistema detecta automaticamente (utilizando Figura 9: Performance da detec¸c˜ ao autom´atica de o procedimento descrito anteriormente) as min´ ucias min´ ucias ao variar do limiar da distˆ ancia t, medida e armazena suas coordenadas. Em seguida, as coorem pixels denadas do indiv´ıduo cuja identidade foi apontada ´e carregado para compara¸c˜ao. Uma vez obtidos dois conjuntos de min´ ucias, Nesse trabalho, escolhemos realizar o reconhechamemos-os de M e M , as correspondˆ e ncias s˜ ao 1 2 cimento de impress˜ oes digitais atrav´es da corresgeradas da seguinte maneira: Para cada par de pondˆencia entre min´ ucias. Isso corresponde a extrair ucias m1 , m2 ∈ M1 , ´e suposto que elas corresas min´ ucias da digital de entrada e compar´a-las com min´ ´ pondem a cada outro par de min´ ucias p1 , p2 ∈ M2 . E um conjunto de min´ ucias associado ` a identidade forent˜ a o computada a transforma¸ c a ˜ o linear σ tal que: necida, retornando uma m´etrica de semelhan¸ca entre esses conjuntos. Comparando essa m´etrica com m1 = σp1 um limiar pr´e-estabelecido, decidimos pela rejei¸c˜ao ou pela confirma¸c˜ ao da identidade do indiv´ıduo em quest˜ ao. σ(p2 − p1 ) (m2 − m1 ) = Os desafios de realizar competentemente correskm2 − m1 k kp2 − p1 k pondˆencias v´ alidas s˜ ao muitos: impress˜ oes digitais Nesse momento, caso d(m2 , σp2 ) > t, onde t ´e um s˜ ao sujeitas a desgaste, a imagem de entrada pode a estar rotacionada ou transladada em rela¸c˜ao ao ca- limiar pr´e-estabelecido, a correspondˆencia que est´ dastro e a press˜ ao com que o dedo foi pressionado sendo analisada ´e descartada e outros pares s˜ao buscontra o sensor torna a imagem propensa a distor¸c˜ao cados. Caso contr´ario, as correspondˆencias sob a suespacial n˜ ao-linear, o que pode alterar a disposi¸c˜ao posi¸c˜ao de correspondˆencia entre m1 e p1 e m2 e p2 das min´ ucias e at´e sua ocorrˆencia, por exemplo. ucia Uma vez realizada a correspondˆencia entre os con- s˜ao feitas da seguinte maneira: dada uma min´ juntos de min´ ucias, as m´etricas dispon´ıveis para rea- mi ∈ M1 , ´e buscado pj ∈ M2 tal que lizar o reconhecimento s˜ ao: pj = argmin(d(mi , σpk )) • Correspondˆencias v´ alidas: o n´ umero de correspk ∈M2 pondˆencias v´ alidas encontradas; mi = argmin(d(mk , σpj )) • Falsos positivos: corresponde ao n´ umero de mk ∈M1 0

20

40

60

80

Distância máxima entre correspondências (em pixels)

8

1.0 0.8

d(mi , σpj ) ≤ t

4.2

0.4

1 − FRR

0.6

Caso exista um tal pj , essa ´e considerada uma correspondˆencia v´ alida. A m´etrica utilizada, ent˜ao, ´e o n´ umero m´ aximo de correspondˆencias, para alguma transforma¸c˜ ao σ ou, equivalentemente, a maior quantidade de correspondˆencias encontrada dentre aquelas obtidas com a suposi¸c˜ ao de correspondˆencia entre m1 − p1 e m2 − p2 . Devido a complexidade desse procedimento, conforme n´ os o implementamos, ser de O(|M1 |3 |M2 |3 ), consideramos que conjuntos com mais de 50 min´ ucias se deviam a falhas de captura e n˜ ao poderiam ser autenticados. Escolhemos 50 porque, dentre as imagens de nossa base, n˜ ao h´ a nenhuma com mais de 50 min´ ucias.

0.0

0.2

Impressão digital − detecção manual Impressão digital − detecção automática Íris − detecção manual Íris + Impressão digital − Probabilístico Íris + Impressão digital − Ponderado Aleatório

0.0

0.2

0.4

0.6

0.8

1.0

FAR

Figura 10: Curva ROC comparando a performance dos reconhecimentos.

Resultados e discuss˜ ao

Validamos nosso sistema com o procedimento a seguir: para cada imagem, foram extra´ıdas suas min´ ucias e suas coordenadas foram salvas em um arquivo de texto. Para cada conjunto de coordenadas, ent˜ ao, utilizamos nosso sistema de reconhecimento para todas as outras imagens. Como a base possui 50 sujeitos e 5 imagens para cada um, isso nos d´a 250 × (5 − 1) = 1000 situa¸c˜ oes de usu´ ario genu´ıno e 250 × (250 − 5) = 61250 situa¸c˜ oes de impostor. Como salvamos previamente as coordenadas das min´ ucias para a realiza¸c˜ ao dos testes, foi poss´ıvel realiz´ a-los tamb´em com as marca¸c˜ oes feitas manualmente. Isso fornece um resultado mais apropriado para a an´ alise da performance do sistema de reconhecimento propriamente dito, pois tira sua dependˆencia da extra¸c˜ ao autom´ atica de min´ ucias e dos erros que da´ı podem advir. Para as detec¸c˜ oes manuais, todas as situa¸c˜oes ditas anteriormente foram aproveitadas. Com o m´etodo autom´ atico, por´em, apenas 686 das situa¸c˜oes de usu´ ario genu´ıno e 14315 situa¸c˜ oes de impostor foram aproveitadas - as outras foram descartadas como falhas de captura. A figura 10 apresenta os resultados encontrados. Para o reconhecimento utilizando as marca¸c˜oes manuais, foi obtido um EER (Equal Error Rate, Taxa

de erro igual) de aproximadamente 20, 1%. J´a para a marca¸c˜ao feita de maneira autom´atica, o EER foi de aproximadamente 43, 3%. Para as marca¸c˜oes manuais, vemos que o m´etodo de reconhecimento utilizado tem potencial limitado apesar de tratar rota¸c˜oes e transla¸c˜oes da imagem da impress˜ao digital, nenhum dos outros desafios listados por n´os mesmos foi tratado. Dessa forma, o resultado at´e surpreende; mesmo utilizando uma m´etrica discreta, pouco vari´avel em nossa base de experimentos, e um procedimento de reconhecimento simples, obtivemos um EER de 20, 1%. Muito provavelmente, ´e mais um atestado do poder discriminativo de impress˜oes digitais - e especialmente, das min´ ucias como identificador biom´etrico. O resultado das marca¸c˜oes autom´aticas, j´a limitado pelo m´etodo de reconhecimento, sofre impacto ainda maior da extra¸c˜ao autom´atica e apresenta um resultado levemente superior ao palpite aleat´orio so´ preciso muito trabalho para bre as identidades. E que o sistema funcione adequadamente de maneira totalmente automatizada. J´a para a valida¸c˜ao da identifica¸c˜ao, utilizamos o seguinte procedimento: para cada par de imagens Ii e Ij (0 ≤ i, j ≤ 250), o n´ umero ci,j de correspondˆencias 9

250 200

Como n˜ao conhecemos as distribui¸c˜oes de probabilidade para o n´ umero de correspondˆencias entre min´ ucias de imagens de impress˜ao digital e nem para distˆancias entre modelos LBPH de ´ıris, primeiramente dividimos esses dados em classes - um n´ umero de correspondˆencias entre min´ ucias maior do que o encontrado para o valor FAR de 0.01 ´e considerado como uma correspondˆencia entre digitais do mesmo indiv´ıduo; uma distˆancia inferior `aquela para o valor de FAR de 0.01 para modelos LBPH de ´ıris tamb´em ´e considerada como a distˆancia entre modelos do mesmo sujeito. Sejam, ent˜ao, as vari´aveis aleat´orias D(i, j) e S(i, j) que indicam, respectivamente, o veredito dado sobre a identidade dos indiv´ıduos das imagens Ii e Ij pelo reconhecimento utilizando as informa¸c˜oes de ´ıris utilizando FAR de 0.01 e esse mesmo veredito utilizando a informa¸c˜ao de impress˜ao digital. A nova m´etrica de semelhan¸ca obtida que decidimos utilizar foi a seguinte probabilidade condicional:

50

100

Rank−N

150

5.1

Impressão digital − detecção manual Impressão digital − detecção automática Íris − detecção manual Íris + Impressão digital − Probabilístico Íris + Impressão digital − Ponderado

10

20

30

40

50

N

Figura 11: Curvas de Rank-N para as modalidades estudadas.

Reconhecimento multibiom´ etrico probabil´ıstico

entre min´ ucias dessas imagens foi computado. Considerando [i] a identidade do sujeito a quem pertence a imagem Ii , para cada imagem Ii ´e computado o n´ umero Ni = |{[j] | ci,j ≤ ci,k , [k] = [i]}|. Definimos o Rank-N como o n´ umero R(N ) = |{Ni | Ni ≤ P 0 = P ({[i] = [j]} | {D(i, j)} ∩ {S(i, j)}) (6) N, 1 ≤ i ≤ 250}|. Seu valor ´e determinado pela lei da probabilidade A figura 11 apresenta os resultados de Rank-N para a identifica¸ca˜o utilizando impress˜ oes digitais - os re- condicional, e ´e: sultados s˜ ao apresentados para detec¸c˜ ao manual e autom´ atica de min´ ucias. Curiosamente, apesar de em P ({[i] = [j]} ∩ {D(i, j)} ∩ {S(i, j)}) (7) P0 = todos os Ranks at´e o 42 a performance da detec¸c˜ao P ({D(i, j)} ∩ {S(i, j)}) autom´ atica ser inferior ` aquela da detec¸c˜ ao manual, a Infelizmente, n˜ao ´e pr´atico calcular os valores da partir desse valor a identifica¸c˜ ao utilizando a detec¸c˜ao equa¸c˜ao 7, pois ter´ıamos que calcul´a-las levando em autom´ atica possui Ranks superiores. considera¸c˜ao todas as pessoas da Terra. Ao inv´es de fazer isso, dividimos nossa base de imagens em 2, e ˆ j), S(i, ˆ j) dessas calculamos estimativas [i]=[j], ˆ D(i, 5 Multibiometria vari´aveis aleat´orias atrav´es de suas frequˆencias nessa Tendo, de um mesmo sujeito, mais informa¸c˜oes subdivis˜ao. biom´etricas, podemos melhorar o resultado do recoPara o reconhecimento da primeira metade da nhecimento combinando-as. No nosso caso, dispomos base, essas estimativas s˜ao calculadas utilizando a sede imagens de impress˜ ao digital e da distˆ ancia entre gunda metade e para o reconhecimento da segunda modelos LBPH de ´ıris como tais informa¸c˜ oes. metade, elas s˜ao calculadas utilizando a primeira mePropomos, nesse trabalho, duas maneiras de com- tade; dessa forma, n˜ao h´a indiv´ıduo simultaneamente binar essas informa¸c˜ oes: uma probabilista e outra no treino e na valida¸c˜ao do m´etodo de reconheciatrav´es de soma ponderada. mento. 10

A f´ ormula para a estimativa da similaridade passa ser, ent˜ ao: ˆ j)} ∩ {S(i, ˆ j)}) P ({[i]=[j]} ˆ ∩ {D(i, Pˆ 0 = ˆ j)} ∩ {S(i, ˆ j)}) P ({D(i,

5.2

(8)

Reconhecimento multibiom´ etrico ponderado

A partir de uma outra abordagem, a combina¸c˜ao entre as informa¸c˜ oes foi executada a partir de uma soma ponderada entre os valores de matching de cada um dos m´etodos de reconhecimento biom´etrico. Empiricamente, um valor arbitr´ ario x ´e determinado como o peso aplicado a biometria baseada em impress˜ oes digitais. Este peso deve ser maior que o aplicado a biometria baseada em ´ıris pois o resultado do reconhecimento do primeiro ´e significantemente inferior ao segundo. Desta forma, foi aplicada a equa¸c˜ ao: s0 = li,j +

x ci,j

(9)

onde s0 ´e o novo valor de similaridade para o matching, li,j ´e a distˆ ancia entre os modelos LBPH das imagens Ki e Kj de ´ıris e ci,j ´e o j´ a citado n´ umero de correspondˆencias entre as min´ ucias das imagens Ii e Ij . Ap´ os uma s´erie de testes, buscando um melhor valor para x, foi encontrado como satisfat´ orio x = 19.

5.3

menos consider´avel do que aquela para impress˜ ao digital. Na Figura 11, constatamos, atrav´es do Rank-N do m´etodo desenvolvido, que houve uma piora no resultado da identifica¸c˜ao ao combinar as informa¸c˜ oes de ´ıris `as de impress˜ao digital. N˜ao ´e dif´ıcil explicar esse resultado: no m´etodo proposto, s˜ao encontrados poucos valores distintos de similaridade devido ` a natureza da classifica¸c˜ao realizada. O n´ u mero m´ a ximo

de valores de similaridade ´e apenas 21 21 = 4, j´ a que ˆ j) temos dois conjuntos de dois elementos cada (D(i, ˆ e S(i, j)). De forma semelhante, a curva ROC utilizando o m´etodo de combina¸c˜ao ponderado est´a apresentada na Figura 10. Novamente, a melhoria do resultado em rela¸c˜ao ao reconhecimento baseado em digitais ´e substancial. J´a a melhoria em rela¸c˜ao ao reconhecimento por ´ıris tamb´em apresenta um acr´escimo, respaldando o uso da soma ponderada como um m´etodo eficiente de combina¸c˜ao. Na Figura 11, ´e constatada uma melhoria substancial no Rank-N aplicando segundo m´etodo de combina¸c˜ao, refor¸cando ainda mais a eficiˆencia do mesmo.

Referˆ encias

Resultados e discuss˜ ao

A curva ROC encontrada utilizando o m´etodo de combina¸c˜ ao probabil´ıstica das informa¸c˜oes biom´etricas, considerando apenas as marca¸c˜oes manuais das min´ ucias, est´ a na Figura 10. Houve uma melhoria marginal no resultado previamente encontrado utilizando apenas ´ıris, mas houve uma melhoria enorme do resultado utilizando apenas impress˜ ao digital. Isso, de certa forma, condiz com o perfil do resultado que esper´ avamos: ´ıris apresentou um resultado muito superior ao de impress˜ao digital, o que faria com que a melhora do seu resultado fosse 11

[1] B. Alias, G. Johnson, and A. Thomas. New approach for fingerprint detection based on singular points. In Communication and Computing (ARTCom2012), Fourth International Conference on Advances in Recent Technologies in, pages 263–265, Oct 2012. [2] Roberto Mendes Finzi Neto Cassiana da Silva Bonato. Um breve estudo sobre biometria. Encontro Anual de Computa¸ca ˜o - Enacomp, 2010. [3] Alex Sandro da Silva. Prot´otipo de software para classifica¸c˜ao de impress˜ao digital. 1998, jun 1998. Trabalho de conclus˜ao de curso submetido `a Universidade Regional de Blumenau para a obten¸c˜ao dos cr´editos na disciplina com nome equivalente no curso de Ciˆencias da Computa¸c˜ ao - Bacharelado.

[4] J. Feng and A. K. Jain. Fingerprint reconstruction: From minutiae to phase. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(2):209–223, Feb 2011.

[13] P. S. Magalh˜aes and H. D. Santos. Biometria e autentica¸c˜a. Conferˆencia da Associa¸c˜ ao Portuguesa de Sistemas de Informa¸c˜ ao - CAPSI, oct 2003.

FVC-onGoing, [5] J. Galbally, S. Marcel, and J. Fierrez. Image [14] University of Bologna. https://biolab.csr.unibo.it/fvcongoing/ui/form/home.aspx, quality assessment for fake biometric detection: acessado em 2016-10-04. Application to iris, fingerprint, and face recognition. IEEE Transactions on Image Processing, [15] Onin.com. The history of fingerprints, 2016. 23(2):710–724, Feb 2014. [16] S. Pankanti, S. Prabhakar, and A. K. Jain. On [6] Zicheng Guo and Richard W. Hall. Parallel thinthe individuality of fingerprints. IEEE Transacning with two-subiteration algorithms. Comtions on Pattern Analysis and Machine Intellimun. ACM, 32(3):359–373, March 1989. gence, 24(8):1010–1025, Aug 2002. [7] Lin Hong, Yifei Wan, and A. Jain. Fingerprint [17] Srividya R and Ramesh B. Design of biometric image enhancement: algorithm and performance authentication technique for manet based emerevaluation. IEEE Transactions on Pattern gency response system. In Electrical, Computer Analysis and Machine Intelligence, 20(8):777– and Communication Technologies (ICECCT), 789, Aug 1998. 2015 IEEE International Conference on, pages 1–5, March 2015. [8] A. K. Jain and J. Feng. Latent fingerprint matching. IEEE Transactions on Pattern Analy- [18] Y. B. Reddy. Latent fingerprint matching in large databases using high performance comsis and Machine Intelligence, 33(1):88–100, Jan puting. In 2016 International Conference on 2011. Computing, Networking and Communications (ICNC), pages 1–5, Feb 2016. [9] Anil K. Jain and Farshid Farrokhnia. Unsupervised texture segmentation using gabor filters. [19] A. Ross, J. Shah, and A. K. Jain. From template Pattern Recognition, 24(12):1167 – 1186, 1991. to image: Reconstructing fingerprints from minutiae points. IEEE Transactions on Pattern [10] Tsai-Yang Jea and Venu Govindaraju. A Analysis and Machine Intelligence, 29(4):544– minutia-based partial fingerprint recognition 560, April 2007. system. Pattern Recogn., 38(10):1672–1684, October 2005. [20] M Sepasian, W Balachandran, and C Mares. Image enhancement for fingerprint minutiaebased algorithms using clahe, standard deviation analysis and sliding neighborhood. In Proceedings of the World congress on Engineering and Computer Science, pages 22–24, 2008.

[11] F. Kaggwa, J. Ngubiri, and F. Tushabe. Evaluation of multiple enrollment for fingerprint recognition. In Computer Information Technology (GSCIT), 2014 Global Summit on, pages 1–6, June 2014. [12] R. Donida Labati, A. Genovese, V. Piuri, and F. Scotti. Toward unconstrained fingerprint recognition: A fully touchless 3-d system based on two views on the move. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 46(2):202–219, Feb 2016.

[21] U. Uludag, S. Pankanti, S. Prabhakar, and A. K. Jain. Biometric cryptosystems: issues and challenges. Proceedings of the IEEE, 92(6):948–960, June 2004.

12