Instituto Superior de Engenharia de Lisboa

Departamento de Engenharia de Electrónica e

Telecomunicações e de Computadores

Autenticação com Impressão Digital

César Alexandre Rodrigues dos Anjos Pacheco

cesar_pacheco@[Link]

Relatório submetido como requisito parcial

para obtenção do grau de licenciado em
Engenharia de Sistemas de Telecomunicações e Electrónica

Orientado por
Arnaldo Abrantes, Artur Ferreira
aja@[Link], arturj@[Link]

Dezembro de 2003
 ISEL Projecto Final de Curso

Resumo

A autenticação/identificação de um indivíduo pelas suas características biológicas e

comportamentais chama-se biometria. A necessidade de autenticação/identificação está

associada à possibilidade de acesso restrito a um determinado bem ou serviço. A

autenticação/identificação pode ser realizada de várias formas: aquilo que se possui; aquilo

que se sabe; aquilo que se é - características biométricas, tais como: íris, impressão digital

e outras).

Com o aumento de produtos e serviços e a necessidade de autenticação, o uso da biometria

tem vindo a ganhar relevância. Dentro da biometria; a impressão digital é a característica

sobre a qual existe mais conhecimento. É usada na identificação criminal há mais de um

século.

Neste trabalho trata-se a autenticação com impressão digital. São apresentadas duas

soluções de autenticação automática de impressões digitais: baseada em minúcias; baseada

em textura orientada.

Conclui-se que o método baseado nas minúcias é altamente dependente da qualidade da

imagem e o seu tratamento complexo. A solução baseada em textura orientada é pouco

dependente da qualidade da imagem. Foi criada uma aplicação de demonstração baseada

no método da textura orientada onde se comprovam os bons resultados em imagens reais

de baixa qualidade.

Autenticação com impressão digital Página I

 ISEL Projecto Final de Curso

Índice

RESUMO ..........................................................................................................................................................I

ÍNDICE ..........................................................................................................................................................III

1 - INTRODUÇÃO.......................................................................................................................................... 1
1.1 – BIOMETRIA ........................................................................................................................................... 2
1.2 – RESUMO HISTÓRICO DO USO DAS IMPRESSÕES DIGITAIS NA IDENTIFICAÇÃO.................................... 3
1.3 – ORGANIZAÇÃO DO RELATÓRIO ........................................................................................................... 5
2 - IMPRESSÃO DIGITAL............................................................................................................................ 7

3 - AUTENTICAÇÃO COM IMPRESSÃO DIGITAL ............................................................................. 11

3.1 – PONTO DE REFERÊNCIA ..................................................................................................................... 12
3.1.1 – Algoritmo de cálculo ................................................................................................................... 13
3.1.2 – Resultados obtidos....................................................................................................................... 21
[Link] – Localização do ponto de referência nas classes de impressão digital ...................................... 21
[Link] - Localização do ponto de referência em imagens reais................................................................ 23
[Link] - Dependência do ponto de referência com a rotação da imagem ................................................ 25
4 - SISTEMA DE AUTENTICAÇÃO ......................................................................................................... 31
4.1 - MÉTODO BASEADO EM MINÚCIAS ....................................................................................................... 32
4.1.1- Resultados obtidos ........................................................................................................................ 34
4.2 - MÉTODO BASEADO EM TEXTURA ORIENTADA.................................................................................... 38
4.2.1 - Invariância à rotação................................................................................................................... 45
4.2.2 - Comparação de impressões digitais............................................................................................. 47
4.2.3 – Estimação do limiar de decisão................................................................................................... 47
5 - APLICAÇÃO DE DEMONSTRAÇÃO ................................................................................................. 51

6 – CONCLUSÕES E TRABALHO FUTURO .......................................................................................... 57

7 - REFERÊNCIAS ....................................................................................................................................... 59

Autenticação com impressão digital Página III

 ISEL Projecto Final de Curso

1 - Introdução
A necessidade de autenticação/identificação está associada à possibilidade de acesso

restrito a um determinado bem ou serviço.

O aumento de produtos e serviços (tais como caixas automáticas, compras electrónicas,

entre outros) e a necessidade de segurança; é a motivação para encontrar uma forma de

autenticar/identificar, cómoda, sempre presente, fiável e pouco introsiva.

As caixas de pagamento automático e o controlo de acessos são exemplos de aplicações

nas quais se realiza a autenticação de indivíduos.

Autenticação e identificação não são a mesma coisa. A autenticação é verificar se um

indivíduo é quem ele diz ser. Realiza-se através da comparação de dois identificadores,

como resultado da autenticação os identificadores são iguais ou diferentes. A identificação

é obter a identidade de um indivíduo dada uma característica e implica a procura do

identificador, no conjunto de identificadores guardados. O resultado dessa procura, é a

existência ou não do identificador procurado.

A chave é uma das primeiras formas usadas para conseguir acesso restrito. Pela

combinação única, entre chave e fechadura, o portador da chave tem acesso a algo, que os

outros não têm; esta forma de autenticação é caracterizada pelo que se possui. A

desvantagem desta forma de controlo de acessos é o furto ou a perda da chave, para além

de algum incómodo de transporte.

Uma das evoluções introduzidas pelos cartões magnéticos e chip cards traduz-se na

possibilidade de autenticar o portador. Os cartões referidos anteriormente realizam a

autenticação do suporte físico e do utilizador através do PIN (Personal Identification

Number), o qual autentica o portador como legítimo utilizador porque só ele o sabe. Este

método de autenticação é usado nas caixas de pagamento automático.

Autenticação com impressão digital Página 1

 ISEL Projecto Final de Curso
No caso da maioria dos serviços da internet, o acesso é concedido por um identificador

alfanumérico e/ou password que autentica o utilizador. Não existe necessidade de

autenticar o suporte físico; a autenticação é feita com base naquilo que o utilizador sabe. A

desvantagem deste tipo de autenticação está na quantidade de passwords que é necessário

memorizar para os diferentes serviços. Para garantir segurança, estas devem ser alteradas

frequentemente e memorizadas.

1.1 – Biometria

Existem características biológicas e comportamentais que são únicas em cada indivíduo. A

biometria é a técnica que autentica/identifica uma pessoa baseada nas suas características

biológicas, (tais como, impressões digitais, íris e outros) ou comportamentais, tais como a

caligrafia, por exemplo.

Na biometria, os identificadores são obtidos a partir de singularidades pertencentes às

características biológicas e/ou comportamentais. Esta técnica apresenta a vantagem de usar

as características do indivíduo, que estão presentes, sem necessidade de possuir objectos ou

memorizar algo. O indivíduo é autenticado/identificado por aquilo que é. Actualmente, os

governos e empresas apostam na biometria: este ano (2003) a União Europeia informou a

intenção de investir milhões de Euros num projecto de criação de um cartão de

identificação biométrico.

De todas as características biométricas a impressão digital é a mais estudada, sendo usada,

desde o séc. XIX, como elemento de identificação de indivíduos.

É neste âmbito que surge este trabalho, cujo objectivo é implementar um sistema

automático de autenticação com impressão digital.

Autenticação com impressão digital Página 2

 ISEL Projecto Final de Curso

1.2 – Resumo histórico do uso das impressões digitais na identificação

Em 1902 um tribunal de Londres aceita pela primeira vez a impressão digital como meio

de identificação. O homem que impulsionou o uso deste meio, na Scotland Yard, foi

Edward Henry (1850-1931), após de 27 anos na Índia, onde tinha começado a usar as

impressões digitais como meio de identificação.

Os primeiros ensaios de Edward Henry aconteceram nas corridas de cavalos de Derby, os

quais atraiam muitos carteiristas. No primeiro dia são apanhados em flagrante 54

carteiristas, dos quais, 29 são encontrados nos registos da Scotland Yard. Este novo

método começa a dar provas da sua eficácia. Alguns meses mais tarde, um tribunal de

Londres, condena pela primeira vez um criminoso com base nas provas deixadas no lugar

do crime.

O primeiro a estudar sistematicamente as linhas em relevo existentes nas pontas dos dedos

chamadas, ridges, linhas ou cristas, foi o italiano Marcello Malpighi (1628-1694). O

trabalho deste professor de anatomia da Universidade de Bolonha, consistiu em registar a

existência de estrias nos dedos e notou que estas se organizavam em três tipos: espirais,

arcos e laços. Os estudos que se seguiram, abordaram o problema noutra perspectiva e em

nenhum deles se estuda as linhas, (dermatóglifos digitais), como meio de identificação.

No século XIX, um funcionário britânico chamado William James Herschel (1833-1917),

deparou-se com dificuldades em fazer cumprir contratos comerciais. Começa a usar as

impressões como meio de prova para fazer cumprir os contratos.

Com resultados satisfatórios, Herschel pensou em generalizar este método e interrogou-se

sobre as cristas existentes nos dedos. Seriam suficientes para identificarem univocamente

uma pessoa? Mudariam com o tempo? É aqui que Herschel ganha relevância no estudo das

impressões digitais. Para responder a estas perguntas, começou a coleccionar impressões.

Autenticação com impressão digital Página 3

 ISEL Projecto Final de Curso
Registou as impressões de bebés e seguiu a sua evolução ao longo dos anos e concluiu que

os padrões se mantinham. Comparou os registos de diferentes pessoas e verificou a sua

unicidade.

Com Herschel, as impressões não passaram de meios de intimidação e confronto entre duas

marcas conhecidas, faltava-lhe um processo de classificação para confrontar algumas

impressões digitais com milhares de outras arquivadas. Com essa dificuldade a aplicação

do método não se generalizou.

Algumas das questões em aberto foram resolvidas algum tempo depois por um médico,

cujo o nome era Henry Faulds (1843-1930). Motivado por um caso que incriminava um

funcionário do hospital de que era responsável e depois de provar a sua inocência através

da comparação das impressões do funcionário e dos assaltantes, Faulds a partir daí

dedicaria toda a sua vida a criar um sistema de identificação baseado nessas marcas

pessoais. Faulds estudou ao longo da sua vida um universo grande de indivíduos e provou

que os dermatóglifos não mudam durante a vida. Ele próprio e os seus colaboradores

removeram as ridges da pele, usando desde ácido até à pedra-pomes e reparou que elas

reapareciam com as mesmas características. Um método de classificação das impressões

foi outro dos contributos de Faulds, de forma a tipificá-las em grupos e assim facilitar a

procura. Faulds propôs o recurso às impressões para identificar criminosos.

Ao estatístico Francis Galton (1822-1911), é atribuído o primeiro grande estudo sobre o

tema, no livro Fingerprints, publicado em 1892. Além de propor um sistema de

classificação, a inovação dá-se com o estudo das anomalias que ocorrem na terminação ou

bifurcação das linhas da impressão digital, que ainda hoje é seguido no essencial. É com

estas bases que Edward Henry fundamenta o seu trabalho na Scotland Yard. Desenvolveu,

em conjunto com um colaborador indiano, Azizul Hacque (1853-?), um método de

Autenticação com impressão digital Página 4

 ISEL Projecto Final de Curso
classificação, chamado método de Henry, que é ainda hoje é usado, sendo a base do

sistema usado pela polícia de todo mundo. [9]

1.3 – Organização do relatório

No capítulo 2 descrevem-se as impressões digitais, as suas características e formação. O

restante texto está organizado da forma que a seguir se apresenta. O capítulo 3 aborda a

autenticação com impressão digital. No capítulo 4 apresenta-se o sistema automático de

autenticação por Impressão digital, com duas abordagens: baseada nas minúcias; baseada

em textura orientada. O capítulo 5 apresenta uma aplicação que demonstra o

funcionamento do algoritmo de autenticação baseado em textura orientada. O capítulo 6

apresenta as conclusões e trabalho futuro. No capítulo 7, são apresentadas as referências

bibliográficas.

Autenticação com impressão digital Página 5

 ISEL Projecto Final de Curso

2 - IMPRESSÃO DIGITAL

A individualidade da impressão digital é uma constatação empírica, que se obtém da

observação de grande número de impressões digitais. O estudo biológico da formação das

impressões confirma este resultado.

O processo de formação dos dermatóglifos acontece até aos sete meses de gestação e

mantém-se ao longo de toda a vida. O crescimento das células das impressões digitais

acontece segundo um padrão determinado pela informação genética e pelo micro-ambiente

no qual o feto está envolvido e que varia de dedo para dedo. O micro-ambiente é a razão

pela qual gémeos idênticos possuem impressões digitais diferentes [1].

A impressão digital é formada por um conjunto de cristas ou ridges, usando o termo inglês.

Localmente, as cristas encontram-se distribuídas paralelamente umas às outras, segundo

determinada orientação e espaçamento. As cristas alternam periodicamente com as

depressões resultando num comportamento semelhante a uma sinusóide. As cristas variam

em largura desde 100 micro metros, para cristas muito finas, até 300 micro metros, para

cristas finas. Tipicamente o período de um ciclo crista/depressão é de 500 micro metros.

Neste conjunto de cristas, orientado e espaçado, existem perturbações resultando no

aparecimento das anomalias locais que são a terminação ou bifurcação de uma crista,

conhecidas por minúcias. Estes dois tipos de minúcia subdividem-se dando origem pela

sua conjugação a outras anomalias menos frequentes [2], tal como apresentado na figura

2.1.

Autenticação com impressão digital Página 7

 ISEL Projecto Final de Curso

Figura 2.1- Tipos de minúcias encontradas nas impressões digitais, A- Termination, B-

Island or Point, C- Spur, D- Lake, E- Independent ridge, F- Bifurcation.

Para lidar com as dificuldades da detecção automática dos diferentes tipos, são utilizados

os tipos básicos ou um número restrito de tipos. O American National Standards Institute

(ANSI, 1986) propôs a classificação das minúcias em quatro tipos: terminações,

bifurcações, “cruzamentos” e indeterminado. O FBI (Federal Bureau of Investigation)

considera apenas terminações e bifurcações – cada minúcia é caracterizada pelo seu tipo,

coordenada x, y e o ângulo entre a tangente à crista da minúcia e o eixo horizontal.

Do ponto de vista global, as cristas formam padrões geométricos, onde são identificados

três tipos de pontos: Loop; Whorl e Delta, conhecidos por pontos de singularidade,

mostrados na figura 2.2.

Figura 2.2 – Regiões singulares (rectângulos) e pontos de referência (círculos a cheio).

Autenticação com impressão digital Página 8

 ISEL Projecto Final de Curso

Os pontos de singularidade Loop e Whorl são usados em muitas abordagens da

autenticação/identificação por impressão digital, para encontrar um ponto de referência

(core point, mostrado na figura 2.2) usado na resolução de problemas de translação e

extracção da área a analisar. As impressões digitais são classificadas com base nos seus

padrões globais. Existem três classes básicas que depois se subdividem em cinco [3]. As

três classes são: Arch , Loop e o Whorl, tal como mostrado na figura 2.3, e que se

encontram distribuídos na população mundial com a frequência de ocorrência de 60%,

35% e 5%, respectivamente.

Figura 2.3- Classes básicas de impressão digital.

Neste trabalho usam-se cinco classes – Arch, Tented Arch, Left loop, Right loop, Whorl,

identificadas pelo National Institute of Standards and Technology (NIST) para comparação

de algoritmos de classificação de impressões digitais e apresentadas na figura 2.4.

Figura 2.4 – Classes definidas pelo NIST, da esquerda para a direita: Arch, Tented Arch,
Left loop, Right loop, Whorl.

Autenticação com impressão digital Página 9

 ISEL Projecto Final de Curso
A frequência de ocorrência destas classes na população mundial são 6.2%, 7.8%, 17%,

36.5% e 32.5% respectivamente [3].

A autenticação/identificação automática baseada nas impressões digitais implica a

digitalização das mesmas. A impressão digital é guardada numa matriz de intensidade com

resolução M x N. Cada pixel I( i ,j ) é representado na matriz por um valor de intensidade

de 0 a 255. Valores próximos de 0, são pixels escuros e fazem parte de uma crista, valores

próximos de 255, são pixels claros e fazem parte de uma depressão.

A identificação/autenticação da impressão digital pode ser realizada com base em

características da minúcia: tipo, localização, orientação.

A classificação da impressão digital é realizada com base nos padrões globais e é utilizada

para as separar, facilitando os processos de armazenamento e pesquisa.

Autenticação com impressão digital Página 10

 ISEL Projecto Final de Curso

3 - Autenticação com impressão digital

A autenticação baseada na impressão digital é utilizada há mais tempo do que qualquer

outra característica biométrica. Existem duas formas de fazer a autenticação utilizando a

impressão digital: assistida e automática. A assistida é feita por peritos que, por inspecção

visual, determinam se uma impressão é ou não igual a outra, através das minúcias.

A autenticação automática, através de hardware e software, recorre ao processamento

digital de imagem.

Esta forma tem a vantagem de libertar o ser humano de tarefas rotineiras e diminuir o

tempo de resposta. Neste trabalho, realiza-se a autenticação automática por impressão

digital, representada por imagem monocromática.

Um sistema automático de autenticação por impressão digital funciona num de dois

modos: registo e autenticação. No modo registo, a imagem é adquirida, analisada e

registada numa base de dados (modo de registo). No modo de autenticação, a imagem é

comparada com um registo existente na base de dados.

Neste trabalho, considerou-se a autenticação automática baseada em dois métodos: (1)

detecção estrutural da impressão digital (minúcias); (2) por textura orientada que tira

partido dos padrões que as riscas formam entre si e da quantidade de perturbações

existentes na vizinhança de um ponto. Estes métodos necessitam de obter um ponto de

referência na impressão digital, o qual é a base de partida para a extracção de

características. Define-se como ponto de referência, o ponto de máxima curvatura côncava

da imagem. No método de extracção de minúcias, é a partir do ponto de referência que se

mede a localização de cada minúcia. No outro método, define-se a área circular de

interesse centrada nesse ponto. A figura 3.1 ilustra a localização do ponto e

posicionamento das características a analisar, a partir do mesmo.

Autenticação com impressão digital Página 11

 ISEL Projecto Final de Curso

(a) (b)

Figura 3.1: Exemplo da localização das características com base no ponto de referência:
(a) minúcias; (b) textura orientada.

3.1 – Ponto de referência

A consistência na detecção do ponto de referência é crucial. Em imagens da mesma

impressão deve ter sempre a mesma localização relativa na imagem. A detecção do ponto

de referência deve ser invariante à rotação e translação garantido assim a consistência

pretendida. A qualidade da imagem e a qualidade da própria impressão digital são factores

que afectam o seu cálculo. Se a impressão digital estiver danificada por cortes ou outro tipo

de agressões, a detecção do ponto de referência é prejudicada. Por outro lado, existe ruído

introduzido no processo de aquisição da imagem. O algoritmo de detecção do ponto de

referência deve ser robusto relativamente a estes factores.

A abordagem usada neste trabalho é a de [4], que consiste em encontrar o ponto de maior

curvatura côncava.

Da observação da figura 2.4, verifica-se que, para todas as classes de impressão digital,

existem zonas onde as cristas descrevem curvaturas, acentuadas na zona central da

Autenticação com impressão digital Página 12

 ISEL Projecto Final de Curso
impressão digital. A figura 3.2, apresenta o diagrama de blocos do algoritmo de cálculo do

ponto de referência.

Matrix O Ponto de
Matrix I Matrix O’ Matrix E Matrix V
dim P x Q referência
dim M x N dim P x Q dim P x Q dim P x Q
(x,y)

Determina Calcula
Suaviza Detecção de
orientação local componente seno Filtro de variância
orientação Maximo
dos blocos

(1) (2) (3) (4) (5)

Figura 3.2 – Diagrama de blocos do algoritmo de cálculo do ponto de referência.

Apresenta-se de seguida, a descrição dos vários passos do algoritmo.

3.1.1 – Algoritmo de cálculo

O Bloco orientação local (1) recebe a imagem da impressão digital em níveis de cinzento

numa matriz I de dimensão M x N, divide a imagem I em P x Q blocos não sobrepostos de

dimensão w x w e calcula a orientação local de cada bloco.

Entrada:

I – Matriz da impressão digital em níveis de cinzento

w – Dimensão dos blocos

Saída: O - Matriz orientação

1. Calcular os gradientes σ x (i, j ) e σ y (i, j ) para cada pixel I(i,j); foi usado o operador de
Sobel.

2. Calcular a orientação local de cada bloco centrado no pixel I(i,j) :

w w
i+ j+
2 2
ν x (i, j ) = ∑ ∑ (σ (u, v ) − σ (u, v ))
2
x
2
y (3.1)
w w
u =i − v = j −
2 2

Autenticação com impressão digital Página 13

 ISEL Projecto Final de Curso
w w
i+ j+
2 2
ν y (i, j ) = ∑ ∑ 2σ (u, v )σ (u, v )
x y (3.2)
w w
u =i − v = j −
2 2

1 v y (i, j )
ο (i, j ) = tan −1 ( ) (3.3)
2 vx (i, j )

Algoritmo 3.1 – Cálculo da orientação local dos blocos.

A equação (3.3) tem em conta a existência da ambiguidade de kπ no cálculo da tangente,

ou seja, se tg (θ ) = y x então a tg (θ + kπ ) = y x , o que resulta na mesma tangente para os

r r
vectores v = (x, y ) e u = (− x,− y ) , tal como ilustrado na figura 3.3.

Y
r
v = (x, y )
y

θ
x X

r
u = (− x,− y )

Figura 3.3 – Ambiguidade no cálculo da tangente.

Dado que a informação do sentido não é importante, isto é, as transições claro para escuro

e escuro para claro têm o mesmo significado para o propósito da autenticação, e orientação

a solução está em calcular o ângulo 2θ em vez do ângulo θ . O ângulo θ é transformado

em 2θ e o ângulo θ + kπ é transformado em 2(θ + kπ ) = 2θ + 2kπ = 2θ com K ∈ Ζ . Das

relações trigonométricas sabe-se que:

sen(2θ ) = 2 sen(θ ) cos(θ ) (3.4)

Autenticação com impressão digital Página 14

 ISEL Projecto Final de Curso
cos(2θ ) = cos 2 (θ ) − sen 2 (θ ) (3.5)
y
sen(θ ) = r (3.6)
v

x
cos(θ ) = r (3.7)
v
Substituindo nas equações (3.4) e (3.5) as equações (3.6) e (3.7) obtém-se

2 xy x2 − y2
sen(2θ ) = r 2 e cos(2θ ) = r2 (3.8)
v v
sen(2θ ) 2 xy
Dado que tg (2θ ) = = 2 substituindo x e y respectivamente pelos gradientes
cos(2θ ) x − y 2

2σ xσ y 1 2σ xσ y
em x e em y do bloco temos , resultando θ= tan −1 ( 2 ).
σ x2 −σ y2 2 σ x −σ y2

O bloco (2) suaviza as diferenças de orientação entre blocos adjacentes da imagem,

provocadas por ruído. Recebe a matriz orientação do campo, transforma a orientação nas

suas componentes em x e y e aplica um filtro passa baixo e devolve uma matriz com as

orientações suavizadas.

Entrada: O - Matriz orientação de campo.

Saída: O ’- Matriz orientação de campo suavizada.

1. Transformar a matriz orientação de campo O , num vector de campo normalizado

definido por:

Φ x (i, j ) = cos(2O(i, j )) (3.10)

Φ y (i, j ) = sen(2O(i, j )) , as componentes em x e y do vector de campo (3.11)

Autenticação com impressão digital Página 15

 ISEL Projecto Final de Curso
2. Filtragem do vector de campo usando um filtro de média com máscara W de dimensão

wΦ × wΦ ; ( wΦ = 5 ).

Φ ′x (i, j ) = ∑u =Φ− w ∑ W (u, v )Φ x (i + u, j + v )

w 2 wΦ 2
2 v = − wΦ 2
(3.12)
Φ

Φ ′y (i, j ) = ∑u =Φ− w ∑ W (u , v )Φ y (i + u , j + v )
w 2 wΦ 2
2 v = − wΦ 2
(3.13)
Φ

3. Cálculo da matriz O ′ de orientação do campo suavizado.

1  Φ ′y (i, j ) 
O ′(i, j ) = tan −1   (3.14)
2  Φ ′x (i, j ) 

Algoritmo 3.2 – Bloco que suaviza orientação de campo.

A figura 3.4 apresenta imagens de duas impressões digitais antes e depois da suavização da

orientação.

Autenticação com impressão digital Página 16

 ISEL Projecto Final de Curso

Figura 3.4 - Resultado obtido pelo método apresentado no cálculo da orientação das
cristas para duas imagens:(a) antes da filtragem e (b) após a filtragem.

O bloco (3) consiste em calcular o seno da orientação do campo suavizado.

Entrada: O’ – Matriz orientação do campo suavizada.

Saída: ε – Matriz componente Seno da orientação de campo suavizada.

ε (i, j ) = sen(O ′(i, j )) (3.15)

Algoritmo 3.3 – Cálculo da componente seno da orientação.

Autenticação com impressão digital Página 17

 ISEL Projecto Final de Curso
O quarto bloco do diagrama calcula a variância da componente seno da orientação de

campo suavizada.

Entrada: ε – Matriz componente seno da orientação de campo suavizada.

Saída: V- Matriz de variância.

1 - Determinar a variância para cada ponto da imagem ε (i, j ) na vizinhança de dimensões

w × w , obtendo-se a imagem de variância V (i, j ) = EQ(i, j ) − m E2 (i, j ) ,com (3.16)

EQ(i, j ) = ∑u = − w 2 ∑v = − w 2 (K (u, v ) ⋅ ε 2 (i − u , j − v ))
w2 w2
(3.17)

m E (i, j ) = ∑u = − w 2 ∑v = − w 2 (K (u , v ) ⋅ ε (i − u, j − v )) , em que
w2 w2
(3.18)

K corresponde à máscara do filtro de média com integral unitário e dimensão w × w , com

w = 5.

Algoritmo 3.4 – Filtro de variância.

O quinto bloco do diagrama calcula o ponto de maior curvatura côncava procura-se na

imagem de variância V (i, j ) , um padrão de modo a sobressair o local do ponto de

referência. O padrão procurado é representado por um máscara.

Entrada: V– Matriz de variância.

Saída: localização (x ,y) do ponto de referência

A máscara que representa o padrão é:

Autenticação com impressão digital Página 18

 ISEL Projecto Final de Curso
− 1 0 0 1 0 0 − 1
− 1 0 0 1 0 0 − 1

− 1 0 0 1 0 0 − 1
 
K = − 1 0 0 1 0 0 − 1
− 1 0 0 − 1 0 0 − 1
 
− 1 0 0 − 1 0 0 − 1
− 1 − 1 − 1 − 1 − 1 − 1 − 1


e encontra-se optimizado para w = 5 .

Analisa-se a imagem V (i, j ) com blocos de dimensões iguais às da matriz K , realizando a

correlação cruzada com essa máscara, dando origem à matriz Z . O máximo da matriz Z

indica a localização do ponto de referência:

( x, y ) = arg (i , j ) max Ζ(i, j ) (3.19)

Algoritmo 3.5 – Localização do ponto de referência.

Figura 3.5 - Exemplo do resultado dos vários passos no método de cálculo do ponto de
referência, (a) imagem original, (b) gradiente na horizontal ∂ x , (c) gradiente na vertical

∂ y , (d) orientação do campo O , (e) orientação do campo após filtragem O ′ e (f) após o

filtro de variância .

Autenticação com impressão digital Página 19

 ISEL Projecto Final de Curso
A figura 3.5 mostra um exemplo com os resultados obtidos após cada fase do processo de

cálculo do ponto de referência: visualizam-se os gradientes em x e em y ; a orientação do

campo antes e após a filtragem de média; mostra-se o ponto de referência após o filtro de

variância e antes de se detectar o máximo, onde se pode ver a branco a zona onde se situa o

ponto de referência. Na figura 3.6, mostra-se o ponto de referência obtido para quatro

impressões digitais diferentes: a localização do ponto encontra-se assinalada com uma

cruz. A imagem onde o processo de cálculo falha é de má qualidade sendo quase

impossível detectar pontos de singularidade. Para as restantes três imagens, o ponto é

detectado correctamente, de forma consistente em sucessivos testes.

a) b)

c) d)

Figura 3.6 - Exemplo da localização do ponto de referência para algumas impressões

digitais; falha na imagem d) porque tem baixa qualidade.

Autenticação com impressão digital Página 20

 ISEL Projecto Final de Curso

3.1.2 – Resultados obtidos

Nesta secção, analisa-se a robustez do algoritmo, medindo o desempenho em várias

situações. Estas são algumas das perguntas para as quais houve preocupação em obter

resposta:

1) Qual o comportamento do algoritmo em cada uma das cinco classes apresentadas no

capítulo 2 ?

2) Qual a influência da qualidade da imagem na localização do ponto de referência ?

3) Qual a dependência do ponto de referência com a rotação e translação da imagem ?

Para dar resposta a estas perguntas, foi desenvolvido um conjunto de testes, que se passam

a descrever. Para verificar o comportamento do algoritmo nas cinco classes foi criada uma

base de dados. Esta designa-se por base de dados 1 e é constituída por 100 impressões

digitais sintéticas, geradas com o programa SfingeV2.0 [5], segundo a sua distribuição na

população mundial conforme descrito no capítulo 2. Usam-se impressões sintéticas para

avaliar o desempenho do algoritmo nas várias classes, com imagens sem ruído. A má

qualidade da imagem dificulta a localização do ponto de referência (ver figura 3.6).

Para testar o algoritmo com imagens reais, foi criada a base de dados 2, com 130

impressões digitais recolhidas num sensor do tipo óptico. A base de dados 3 foi criada,

com 240 impressões digitais; foram usados 4 dedos e por cada dedo foram recolhidas 60

imagens com o sensor óptico.

[Link] – Localização do ponto de referência nas classes de impressão digital

O teste da localização do ponto de referência consiste, por inspecção visual, determinar se

o ponto de referência, em cada uma das impressões da base de dados 1, é bem localizado.

A medida de localização é qualitativa e consiste na votação de duas pessoas; cada uma

Autenticação com impressão digital Página 21

 ISEL Projecto Final de Curso

indica se o ponto está localizado na zona de maior curvatura côncava da imagem. O ponto

é considerado bem localizado apenas quando ambas concordam que está bem localizado.

Caso contrário é considerado mal localizado. A tabela 3.1, apresenta os resultados obtidos.

Localizaç
número de
distribuição da Localização ão
classe impressões
classe (%) correcta (%) incorrect
digitais
a (%)
right loop 37 37,0 97,3 2,7
whorl 33 33,0 100,0 0,0
left loop 17 17,0 100,0 0,0
tented arch 8 8,0 87,5 12,5
arch 5 5,0 0,0 100,0

total 100 100,0 93,0 7,0

Tabela 3.1 - Resultados do teste de localização do ponto de referência em cada uma das
classes de impressões digitais – imagens sintéticas; total de 100 imagens.

O ponto de referência é localizado com taxas de sucesso acima dos 80% em todas as

classes, à excepção da classe Arch. Esta classe tem ocorrência de 5%, sendo a mais rara na

população mundial o que minimiza o problema, embora continue a ser um

constrangimento para um sistema que pretende ser universal. A razão porque este

algoritmo tem dificuldade em localizar correctamente o ponto de referência em impressões

da classe Arch, é porque se baseia no ponto de maior curvatura côncava. A observação das

impressões digitais da classe Arch, (ver a figura 3.7), leva a concluir que não existe um

ponto com curvatura côncava mais pronunciada.

Autenticação com impressão digital Página 22

 ISEL Projecto Final de Curso

Figura 3.7 - Exemplo de impressões digitais sintéticas da classe Arch .

[Link] - Localização do ponto de referência em imagens reais

O objectivo deste teste é comprovar a influência que a qualidade da imagem tem na

localização do ponto de referência. O método para classificar a localização do ponto de

referência como correcta ou incorrecta é o mesmo do teste anterior. Utilizam-se imagens

da base de dados 2. A má qualidade da imagem distorce a informação de orientação do

campo, na qual este algoritmo se baseia para calcular o ponto de referência.

número de
distribuição da Localização Localização
classe impressões
classe (%) correcta (%) incorrecta (%)
digitais
left loop 49 37,69 81,63 18,37
whorl 38 29,23 76,32 23,68
right loop 36 27,69 94,44 5,56
tented arch 6 4,62 100,00 0,00
arch 1 0,77 0,00 100,00

total 81 62,31 83,85 16,15

Tabela 3.2 - Resultados do teste de localização do ponto de referência em cada uma das
classes de impressões digitais – imagens reais.

Autenticação com impressão digital Página 23

 ISEL Projecto Final de Curso

As percentagens mais elevadas de localizações incorrectas em impressões reais, confirma

este pressuposto. A figura 3.8 mostra algumas das impressões da base de dados 2; as três

imagens inferiores, contribuíram para aumentar a percentagem de localizações incorrectas.

Mostram-se também imagens, (as três superiores), que apesar do ponto bem localizado não

seria possível extrair área útil centrada nesse ponto, para análise. Este constrangimento é

ultrapassado com um sistema mecânico rígido que dificulte a não cooperação do utilizador

e facilite o contacto no que diz respeito à área recolhida e qualidade da imagem. Através de

pré processamento sobre a imagem, é possível validar a sua área útil e/ou qualidade de

aquisição.

Figura 3.8 - Impressões digitais recolhidas com imagens de má qualidade.

Autenticação com impressão digital Página 24

 ISEL Projecto Final de Curso

[Link] - Dependência do ponto de referência com a rotação da imagem

Neste teste avalia-se o desempenho do algoritmo face à rotação da imagem, nas várias

classes de impressão digital. O algoritmo é tanto melhor quanto maior for a consistência da

localização do ponto de referência nas versões rodadas da imagem. Dado que não é

possível adquirir versões com rotação da imagem, em intervalos regulares constantes, e

garantir que esta sofra apenas rotação, usa-se a função imrotate() do Matlab para criar

essas versões da imagem. Determina-se a localização teórica do ponto de referência, para

uma dada rotação da imagem, e compara-se com a localização medida depois de submeter

a imagem a essa rotação. O intervalo de rotação da imagem considerado é de -45º a 45º

com espaçamento de 1º. Não se consideram rotações maiores porque tal implicaria que o

dedo se encontrasse fora da área do sensor. A medida usada para aferir a proximidade entre

os pontos de referência é a distância euclideana em pixels. O algoritmo 3.6 calcula

teoricamente o ponto de referência.

Entrada: lin , col (linha e coluna do ponto em relação ao centro da imagem) e β (

ângulo de rotação)

Saída: lin ′ e col ′ (linha e coluna do ponto depois da rotação)

1. Determinar o centro da imagem original, x0 = linhacentral e y 0 = colunacentral .

2. Determinar as coordenadas do ponto de referência na imagem original, lin e col .

Autenticação com impressão digital Página 25

 ISEL Projecto Final de Curso

Q3 Q2

pontoref .′ = (lin ′, col ′)

ρ
center = (x0 , y 0 )
α+β Y

ρ
α
pontoref . = (lin, col )

Q4 Q1
X

3. Determinar as coordenadas do ponto de referência em relação ao ponto central,

x = lin − x0 e y = col − y 0 .

 y
4. Determinar ρ = x 2 + y 2 e α = tg −1   , a tangente inversa deve ser obtida em
x

relação aos quatro quadrantes.

5. Para cada ângulo β :

a. Calcula-se o novo ângulo α ′ = α + β .

b. Obter x ′ = ρ cos(α ′) e y ′ = ρ sin (α ′) .

c. Calcular as novas coordenadas do ponto de referência após a rotação, lin ′ = x ′ + x0 e

col ′ = y ′ + y 0 .

Algoritmo 3.6 – Calculo teórico do ponto de referência após rotação β .

A figura 3.9 mostra os resultados dos testes efectuados, em impressões digitais de classes

diferentes, considerando as imagens rodadas no intervalo referido anteriormente. Conclui-

se que para as classes right loop, left loop e tented arch os erros só são significativos acima

Autenticação com impressão digital Página 26

 ISEL Projecto Final de Curso
dos 30º, o que não é preocupante porque para esta rotação o dedo está fora da área de

recolha de imagem do sensor. Para a classe Whorl o algoritmo revela-se algo irregular:

com 4 impressões desta classe o comportamento é similar ao das outras classes; nas outras

imagens existem diferenças grandes, para rotações abaixo dos 30º, correspondentes a

situações em que falha a detecção do ponto de referência. Estes ensaios são úteis porque

verificam onde o algoritmo apresenta falha e que é necessário ter em conta na análise dos

resultados da autenticação de impressões digitais.

Erro no cálculo do ponto referência vs rotação da imagem

250

200 Distância (pixels)

150

100

50

0
50 40 30 20 10 0 -10 -20 -30 -40 -50
Rotação (degrees)

fp_whorl_a_3.bmp fp_whorl_a_4.bmp fp_whorl_a_5.bmp fp_whorl_a_7.bmp

fp_whorl_a_8.bmp fp_whorl_a_9.bmp fp_whorl_a_10.bmp

a)

Autenticação com impressão digital Página 27

 ISEL Projecto Final de Curso

Erro no cálculo do ponto referência vs rotação da imagem

300

250
Distância (pixels)

200

150

100

50

0
50 40 30 20 10 0 -10 -20 -30 -40 -50
Rotação (degrees)

fp_right_a_1.bmp fp_right_a_2.bmp fp_right_a_3.bmp fp_right_a_4.bmp fp_right_a_5.bmp fp_right_a_6.bmp

fp_right_a_7.bmp fp_right_a_8.bmp fp_right_a_10.bmp

b)

Erro no cálculo do ponto referência vs rotação da imagem

250

200
Distância (pixels)

150

100

50

0
50 40 30 20 10 0 -10 -20 -30 -40 -50
Rotação (degrees)

fp_left_a_1.bmp fp_left_a_2.bmp fp_left_a_3.bmp fp_left_a_4.bmp fp_left_a_6.bmp

fp_left_a_7.bmp fp_left_a_8.bmp fp_left_a_9.bmp fp_left_a_10.bmp

C)

Autenticação com impressão digital Página 28

 ISEL Projecto Final de Curso

Erro no cálculo do ponto referência vs rotação da imagem

180

160

140 Distância (pixels)

120

100

80

60

40

20

0
50 40 30 20 10 0 -10 -20 -30 -40 -50
Rotação (degrees)

fp_tented_a_1.bmp fp_tented_a_2.bmp fp_tented_a_3.bmp fp_tented_a_4.bmp fp_tented_a_5.bmp

fp_tented_a_6.bmp fp_tented_a_7.bmp fp_tented_a_8.bmp fp_tented_a_9.bmp

d)

Figura 3.9 - Resultado da dependência em relação à rotação para impressões digitais de

diferentes classes: (a) whorl, (b) right loop, (c) left loop e (d) tented arch.

Autenticação com impressão digital Página 29

 ISEL Projecto Final de Curso

4 - Sistema de autenticação
Neste capítulo descreve-se o sistema de autenticação desenvolvido, cujo modelo básico é

descrito por dois módulos: extracção de características e comparador, tal como se

apresenta na figura 4.1.

Iguais
Extracção de Modo de comparação Comparador /
caracteristicas diferentes

Modo de extracção

Base de dados

Figura 4.1- Diagrama de blocos do sistema automático de autenticação por impressão

digital.

O módulo de extracção de características recolhe um conjunto de características que

identificam a impressão digital e escreve-as na base de dados. O módulo comparador

indica se duas impressões são iguais ou não, analisando as respectivas características.

O sistema funciona em dois modos: extracção e comparação. No modo de extracção

apenas o módulo de extracção está em funcionamento, realizando a tarefa de extracção e

escrita das características na base de dados. No modo de comparação, o módulo de

extracção recebe uma impressão digital e extrai as características. O módulo de

comparação recebe as características extraídas e verifica se são semelhantes às guardadas.

Em caso afirmativo as impressões são classificadas como iguais, caso contrário são

diferentes.

A configuração do módulo de extracção depende do tipo de características a utilizar na

autenticação. Todas as singularidades que distingam univocamente duas impressões

Autenticação com impressão digital Página 31

 ISEL Projecto Final de Curso
digitais podem ser usadas. As mais frequentes são as minúcias e os padrões formados pelas

cristas. Nas secções 4.1 e 4.2 são descritos os processos que usam estas características,

respectivamente.

4.1 - Método baseado em minúcias

As primeiras técnicas de identificação por impressão digital são baseadas na observação

das minúcias, sendo usadas na identificação criminal. Trata-se de inspecção visual, para

determinar se duas impressões digitais são iguais ou não. Para que uma impressão digital

seja considerada igual a outra, existe um número mínimo de minúcias iguais que têm de ser

encontradas e não pode ser encontrada nenhuma diferente. O número mínimo de minúcias

iguais exigido, está relacionado com a probabilidade de encontrar minúcias iguais em

impressões digitais diferentes. Quanto mais minúcias forem consideradas, mais baixa é a

probabilidade das impressões serem consideradas iguais quando na realidade são diferentes

(falsa aceitação). Existem vários modelos que determinam esta probabilidade para um

determinado número de minúcias iguais, [4]. O número mínimo de minúcias é importante

na especificação de um sistema automático de autenticação baseado em minúcias. A área a

analisar deve conter o número suficiente de minúcias para que a autenticação seja válida.

Na extracção das minúcias é necessário ter em atenção que, a deformação, provocada pela

pressão do dedo na superfície do sensor, origina imagens diferentes para o mesmo dedo. A

sujidade, suor, cortes e outras marcas provocadas por acidentes também danificam as

minúcias.

É necessária a incorporação, no módulo de extracção, de um bloco de melhoramento da

imagem. O diagrama de blocos do módulo de extracção para este tipo de característica é

constituído por quatro blocos, apresentados na figura 4.2.

Autenticação com impressão digital Página 32

 ISEL Projecto Final de Curso

Vector de
características
melhoramento da binarização da extracção das
esqueletização
imagem imagem minúcias

(1) (2) (3) (4)

Extracção de
características

Figura 4.2 – Diagrama de blocos do módulo de extracção baseado em minúcias.

O módulo de extracção funciona da forma que a seguir se descreve. A impressão é

digitalizada por um sensor, sendo criado um ficheiro em escala de cinzentos com a

impressão. O bloco de melhoramento da imagem recebe a imagem e trata-a procurando

obter uma qualidade mínima. Para sobressair as cristas dos vales usa-se filtragem orientada

realizada, por exemplo com filtros de gabor [7], com diferentes orientações. O passo

seguinte consiste na binarização, a qual transforma a imagem noutra com dois níveis de

intensidade: 0 (preto) ou 1 (branco), em que o preto indica as cristas e o branco indica as

depressões. O algoritmo de binarização testa cada pixel da imagem de entrada e atribui o

valor 0 se a intensidade desse pixel for menor que o nível de decisão e o valor 1 se a

intensidade for maior. O nível de decisão é calculado pela função MATLAB graythresh,

que recebe a imagem de níveis de cinzento e devolve o limiar de decisão. Esta função usa o

método de Otsu [6]. Para facilitar a extracção de minúcias e minimizar os erros (detecção

falsa de minúcia, ou rejeição de minúcia verdadeira) reduz-se a largura das cristas a um

pixel, através da esqueletização da imagem [4]. A extracção de minúcias percorre a

imagem e procura padrões guardados numa tabela: terminações, bifurcações, ilhas; quando

encontra um destes padrões, extrai a sua posição e cria uma entrada no vector de

Autenticação com impressão digital Página 33

 ISEL Projecto Final de Curso
características com a posição, orientação e o tipo da minúcia, tal como representado na

figura 4.3.

1 coord x coord y orientação tipo minucia ... n coord x coord y orientação tipo minucia

Figura 4.3 – Vector de características, para armazenamento das minúcias detectadas.

4.1.1- Resultados obtidos

Sabendo que a qualidade da imagem influencia o sucesso da detecção das minúcias, os

resultados práticos foram divididos em duas fases. Na primeira, foram testados os blocos

da binarização, esqueletização e extracção de minúcias, com imagens de boa qualidade,

(imagens sintéticas criadas com o programa Sfinge v2.0, disponível no site da universidade

de Bolonha [5]). Na segunda fase, foi testado o bloco de melhoramento da imagem, com

imagens reais, adquiridas com o sensor óptico.

A esqueletização da imagem consiste em usar a função MATLAB bwmorph, sobre a

imagem binária, para realizar a operação ‘thin’, a qual reduz as cristas a um pixel de

largura. A figura 4.4 apresenta uma imagem binária e a respectiva esqueletização.

Autenticação com impressão digital Página 34

 ISEL Projecto Final de Curso

a) b)

Figura 4.4 – Imagem a) binária. Imagem b) – esqueletizada.

A detecção de minúcias, neste teste, consiste na sua marcação e é implementada com as

funções MATLAB makelut e applylut. A primeira recebe uma função e a dimensão de uma

matriz, (neste caso 3) e cria uma tabela com 512 entradas. Cada entrada contém o valor 0,

1, 2 ou 3. Os tipos considerados 0, 1, 2 e 3 identificam respectivamente: não é minúcia, é

terminação, ilha ou bifurcação. Na tabela, o valor de cada entrada é calculado pela função

que é passada, a qual gera sequencialmente os números de 0 a 511 em binário e converte

para decimal; cada número representa uma possível minúcia que pertence a um dos tipos

referidos anteriormente. A figura 4.5 mostra como são codificadas as minúcias do tipo

terminação, tendo em consideração o peso de cada pixel num bloco 3x3 e as posições que a

terminação ocupa dentro do bloco.

Autenticação com impressão digital Página 35

 ISEL Projecto Final de Curso
256 32 4
128 16 2
64 8 1
a)

17 18 20 24

48 80 144 272
b)

Figura 4.5 – a) Peso dos pixels no bloco, b) codificação da minúcia tipo terminação.

A função applylut, recebe a imagem esqueletizada e a tabela com os tipos; percorre a

imagem analisando blocos centrados nos vários pixels. A análise consiste em converter o

conteúdo do bloco num número decimal e indexar à tabela obtendo o tipo. Cada pixel da

imagem original é substituído pelo tipo de minúcia. O desempenho deste algoritmo na

detecção das minúcias é comprovado na figura 4.6, na qual as minúcias são identificadas

na imagem original, distinguindo-se o seu tipo pela cor (ou tonalidade claro/escuro).

Aplicando o algoritmo sobre várias imagens sintéticas, os resultados foram semelhantes

aos apresentados na figura 4.6, isto é, as minúcias são correctamente identificadas (posição

e tipo). A figura 4.7 mostra imagens reais, antes e depois de aplicado o algoritmo de

detecção anteriormente descrito.

Autenticação com impressão digital Página 36

 ISEL Projecto Final de Curso

a) b)

Figura 4.6 – a) Imagem onde cada minúcia é identificada por uma etiqueta. b) Impressão
digital com as minúcias identificadas, terminação (vermelho/ponto claro), bifurcação
(azul/ponto escuro).

a) b) c) d)

Figura 4.7- a) Original em escala de cinzentos; b) Imagem binária , c) Imagem

esqueletizada , d) Imagem com minúcias identificadas.

Autenticação com impressão digital Página 37

 ISEL Projecto Final de Curso

Os resultados obtidos verificam que para autenticar com impressões digitais reais é

necessário realizar pré-processamento para melhorar a imagem. O método baseado em

minúcias tem alta dependência com a qualidade da imagem. Os resultados obtidos com

imagens reais mostram que sem pré-processamento, a autenticação pelo método das

minúcias não é fácil. A implementação do método aqui descrito ficou na detecção das

minúcias.

4.2 - Método baseado em textura orientada

Textura orientada é textura que exibe um sentido de direcionalidade bem definida. A

textura orientada pode ser usada para distinguir componentes com diferentes frequências

espaciais e orientações e assim classificar a imagem. A classificação pode ser baseada na

informação local ou global; a classificação baseada apenas em informação local pode

resultar em erros, porque é muito dependente do ruído existente; por outro lado a

classificação baseada apenas em informação global é muito limitada, já que não descrimina

todo o pormenor e pode levar a que duas imagens diferentes sejam classificadas iguais.

A impressão digital pode ser encarada como textura: localmente as impressões digitais

podem ser vistas como um conjunto de cristas e vales paralelos com frequência espacial e

orientação bem definidas. Globalmente, as cristas e vales formam um padrão descrito pela

mudança de direcção das cristas e vales ao longo da imagem. Um filtro de Gabor [7],

sintonizado de forma apropriada, remove o ruído e preserva as cristas e vales, fornecendo a

informação contida numa orientação particular da imagem. Também capta as minúcias,

uma vez que estas podem ser vistas como anomalias entre duas cristas paralelas. Este é o

princípio base para a extracção de características da impressão digital, com base na textura

orientada.

Autenticação com impressão digital Página 38

 ISEL Projecto Final de Curso
O método implementado neste trabalho, proposto em [4], consiste em criar um código,

designado por FingerCode, que identifica a impressão digital, usando informação local e

global. Localmente, descrimina-se a orientação das cristas e capta-se a existência das

minúcias. Globalmente, relacionam-se as orientações locais das cristas.

O método consiste, conforme mostra o diagrama de blocos da fígura 4.8: (1) calcular o

ponto de referência (apresentado no Cap. 3); (2) dividir em células uma região circular

com origem no ponto de referência; (3) normalizar a intensidade da imagem da região

circular; (4) captar a informação local da imagem (cada célula) por um conjunto de filtros

de Gabor sintonizados de forma apropriada; (5) quantificar a informação extraída num

valor de 0 a 255 usando a medida estatística desvio médio absoluto da intensidade média

da célula. Cada valor quantificado é organizado num vector. O vector é composto pelo

conjunto ordenado e enumerado das características quantificadas extraídas em cada célula.

Desta maneira, as características extraídas captam a informação local e a análise ordenada

das células capta as relações globais entre os padrões locais.

8
3 bandas x 16 sectores =
48 células 1 .. .
Filtro de Gabor Quantificação
Divisão da área Fingecode
Calculo do ponto Normalização da Filtro de Gabor usando desvio médio
considerada em
de referência intensidade orientado 0º absoluto da intensidade
células
média da célula

(1) (2) (3) (4) (5)

Extracção de
características

Figura 4.8 - Diagrama de blocos da extracção de características usando um banco de

filtros.

O cálculo do ponto de referência, descrito no capítulo 3, é a partida para este processo.

Com centro nele é extraída a região de interesse que consiste numa área circular de B

Autenticação com impressão digital Página 39

 ISEL Projecto Final de Curso
bandas com k sectores; o cruzamento dos sectores com as bandas dá origem a B × k

células.

Seja I ( x, y ) a imagem original de uma impressão digital com dimensão M × N e

(xc , y c ) as coordenadas do ponto de referência, então a região de interesse é definida

como o conjunto de células S i onde i ∈ [0,..., (B × k − 1)] indica a respectiva célula.

Cada banda tem largura b (número de pixels da banda).

S i = {( x, y ) | b(Ti + 1) ≤ r < b(Ti + 2),θ i ≤ θ < θ i +1 ,1 ≤ x ≤ N ,1 ≤ y ≤ M } (4.1)

Onde,

Ti = i div k
θ i = (i mod k ) × (2π k )

r= ( x − x c )2 + ( y − y c )2 ,

θ = tg −1 (( y − y c ) ( x − xc ))

A figura 4.9 mostra a região de interesse para duas impressões digitais. O número de

bandas deve ser escolhido de forma a que a área seleccionada não saia fora da imagem;

tal acontece se o número de bandas for grande. Por outro lado, o número de bandas não

pode ser pequeno, porque é necessário captar informação suficiente para bom

desempenho da autenticação. O número de sectores é outro parâmetro importante; deve

ser escolhido tendo em atenção que se for muito grande implica células mais pequenas

onde a influência do ruído é maior; por outro lado um número pequeno de sectores

implica células maiores, o que pode levar a que se perca informação local

discriminatória. Segundo [4], a largura das bandas (parâmetro b) deve ser tal que, em

média, deve conter uma crista, um vale e uma minúcia. A distância entre cristas

praticamente não varia entre impressões lidas com a mesma resolução. Existe portanto,

uma distância entre cristas que pode ser considerada óptima, observada nas impressões
Autenticação com impressão digital Página 40
 ISEL Projecto Final de Curso
recolhidas com o sensor óptico, para o qual a distância média de pixels entre cristas foi

10. Os valores dos parâmetros são B = 3 , k = 16 e b = 20 .

Figura 4.9 - Exemplo da região de interesse e divisão em células de duas impressões

digitais diferentes.

Antes de extrair as características, é necessário normalizar a intensidade da imagem em

cada célula da região seleccionada para remover o ruído introduzido pelo sensor, bem

como eliminar as diferenças de intensidade resultantes da deformação provocada pela

pressão do dedo no sensor, como é mostrado na figura 4.10. A normalização é calculada

considerando M i como a média e Vi como a variância do nível de intensidade para a

célula S i da imagem original de uma impressão digital I ( x, y ) . A imagem N i ( x, y ) ,

normalizada na região de interesse, é obtida pela expressão (4.2) em que M 0 e V0

representam respectivamente a média e a variância pretendidas; os valores usados

são M 0 = 100 e V0 = 100 .

 V0 × ( I ( x , y ) − M i )
2
M 0 + , se I ( x, y ) > M i
 Vi
N i ( x, y ) =  (4.2)
V0 × ( I ( x , y ) − M i )
2

M 0 − , se I ( x, y ) ≤ M i
 Vi

Autenticação com impressão digital Página 41

 ISEL Projecto Final de Curso

Figura 4.10: Região seleccionada depois de normalizada.

Após a normalização da imagem, procede-se à extracção da informação local com base

num banco de oito filtros de Gabor. Os filtros são sintonizados à mesma frequência

espacial mas com direcções diferentes. A frequência espacial foi determinada com base

na distância média entre riscas a qual é praticamente constante em imagens recolhidas

com o mesmo sensor, mantendo a mesma resolução. Sendo Rridges a distância entre

cristas, a frequência é dada por f ridges = 1 Rridges ; neste caso tem-se f ridges = 0,1 . Os oito

filtros foram calculados recorrendo à expressão (4.3), em que as diferentes rotações são

obtidas aplicando a transformação de variáveis x ′ = x ⋅ sen(θ ) + y ⋅ cos(θ ) e

y ′ = x ⋅ cos(θ ) − y ⋅ sen(θ ) .

 1  x′ 2 y ′ 2  
  
−  2 + 2 
G ( x , y; f , θ ) = e ⋅ cos(2πfx ′)
 2  δ x δ y  
(4.3)

Como a distância entre cristas se mantém constante, os filtros têm todos a mesma

frequência espacial f . A orientação θ da sinusóide em relação ao eixo dos xx é dada

o
 180 
por i ×   , i ∈ [1,8] , δ x e δ y são as constantes da envolvente gaussiana que
 8 

determina a largura da função segundo os eixos dos xx e yy respectivamente. Os

valores de δ x e δ y devem ser dimensionados de forma a encontrar equilíbrio entre a

Autenticação com impressão digital Página 42

 ISEL Projecto Final de Curso
sensibilidade ao detalhe da informação local e a rejeição do ruído. As funções utilizadas

têm dimensões 33 × 33 com δ x = δ y = 4 e encontram-se representadas na figura 4.11.

Figura 4.11- Máscaras 2-D das 8 funções de Gabor utilizadas.

A extracção da informação local realiza-se pela convolução de cada uma destas funções

com a impressão digital. As cristas sintonizadas com os filtros são evidenciadas, tudo o

resto é considerado não significativo, tal como se mostra na figura 4.12.

Figura 4.12 - Exemplo do resultado da filtragem de uma imagem pelas 8 funções de

Gabor.

Autenticação com impressão digital Página 43

 ISEL Projecto Final de Curso
O resultado são 8 imagens com 48 células cada. A informação filtrada e contida em

cada célula das 8 imagens é codificada num valor de 0 a 255 e dá origem a um vector de

características com dimensão 8*48 = 384 bytes. A codificação de cada célula baseia-se

na média do desvio em relação à média do nível de intensidade em cada célula. Em [4]

afirma-se que é difícil extrair características em imagens de má qualidade, baseadas na

detecção estrutural da imagem, e o problema não é crítico quando a extracção é baseada

em métodos estatísticos. O vector de características é calculado pela expressão (4.4),

onde Fiθ j ( x, y ) representa a intensidade do pixel j da célula i na imagem filtrada

segundo a direcção θ ; ni é o número de pixels existentes no sector S i e Piθ é a média

do valor dos pixels pertencentes à célula Fiθ ( x, y ) .

1  ni 
Viθ =  ∑ Fiθ ( x, y ) − Piθ  (4.4)
ni  j 
 j =1 

A figura 4.13 mostra um exemplo das características extraídas em cada área

sectorizada. Verifica-se que, em duas imagens da mesma impressão digital, as

características visualizadas pelos níveis de cinzento em cada célula são muito

semelhantes. Entre imagens de impressões digitais diferentes, as características são

bastante distintas.

Autenticação com impressão digital Página 44

 ISEL Projecto Final de Curso

Figura 4.13: Fingercodes de 4 imagens, 2 iguais e 2 diferentes.

4.2.1 - Invariância à rotação

Diferentes aquisições da mesma impressão digital, dão origem a diferentes imagens com

rotação e translação. Tal implica que as características extraídas são diferentes, nas várias

imagens. A translação é resolvida com a detecção do ponto de referência. Para resolver a

Autenticação com impressão digital Página 45
 ISEL Projecto Final de Curso
rotação é necessário que o sensor não permita a rotação do dedo ou que este problema seja

resolvido depois da aquisição. O sensor usado neste trabalho não resolve o problema da

rotação. O problema é resolvido gravando para a mesma impressão digital um conjunto de

FingerCodes correspondentes à rotação da imagem em intervalos regulares de α entre

+
− 30 º . Considera-se que o dedo rodado mais de 30 º ou menos de 30 º não está alinhado com

o sensor e por isso a imagem adquirida não é válida. Por causa do tipo de estatística e da

sectorização do FingerCode, rotações pequenas não alteram o FingerCode. O ângulo α

deve ser suficientemente pequeno para captar as alterações no FingerCode, mas também

deve ter em conta o número de FingerCodes gerados. Neste trabalho considerou-se α =7º e

rotações não superiores a 30º, pela razão já referida. É gerado um FingerCode da imagem

original e um das imagens rodadas de ± α ; cada um destes FingerCodes é depois rodado

de um sector em ambos os sentidos. No final, o resultado são 9 FingerCodes com rotações

-29.5º, -22.5º, -15.5º, -7º, 0º, 7º, 15.5º, 22.5º e 29.5º. O algoritmo 4.1 é usado para criar os
FingerCodes.

Entrada:
R – número e direcção do sector rodado [-1,0,1]
k – número de sectores em cada banda
i - índice dos sectores de cada imagem
θ - orientação das funções de Gabor

R
Saída: Viθ - FingerCode rodado.

R
O FingerCode rodado de um angulo R × 22.5º ( Viθ ), é calculado a partir do FingerCode
R
original Viθ = Vi′θ ′ , com:

i ′ = (i + k − R ) mod k + (i div k ) × k

Autenticação com impressão digital Página 46

 ISEL Projecto Final de Curso
θ ′ = (θ − 180º +22,5º×(− R )) mod 180º

Algoritmo 4.1 – Versões rodadas do FingerCode original.

4.2.2 - Comparação de impressões digitais

A autenticação de uma impressão digital implica a comparação com o registo de uma

impressão digital guardada na base de dados. A distância euclidiana, equação (4.5), entre

os FingerCodes das imagens que se pretende comparar é a medida de semelhança: valores

baixos indicam que as imagens são da mesma impressão digital, valores altos indicam o

contrário. O valor nunca será zero porque as condições de aquisição e cálculo variam, tais

como sujidade e rotação, por exemplo. Devido à variabilidade nas condições de aquisição,

cada impressão digital é adquirida três vezes, o que em termos de registo, significa guardar

9x3=27 FingerCodes. O valor mais baixo resultante da comparação do FingerCode da

impressão que se pretende autenticar com todos os FingerCodes das impressões digitais

registadas é a medida de semelhança considerada. A decisão para considerar duas

impressões como iguais é feita com base num limiar de decisão; valores inferiores indicam

igualdade e valores superiores indicam diferença.

d= ∑ (F Code1 (i ) − FCode 2 (i ))2 [ ]

com i ∈ 1,..., B × k × 8 (4.5)
i

4.2.3 – Estimação do limiar de decisão

A estimação do limiar de decisão consiste em criar o histograma das distâncias obtidas

entre imagens iguais e diferentes. O histograma permite verificar o conjunto de distâncias

que identificam as impressões iguais e o conjunto que identifica as impressões diferentes.

No histograma observa-se que algumas impressões iguais e diferentes apresentam valores

muito próximos existindo uma zona de intersecção. Esta zona resulta do facto do método

Autenticação com impressão digital Página 47

 ISEL Projecto Final de Curso
ser estatístico e estar sujeito também à boa localização do ponto de referência que é

sensível à qualidade da imagem. O treino permitiu igualmente traçar as curvas de

percentagem cumulativa das impressões iguais e diferentes, as quais podem ser observadas

na figura 4.14. Estas indicam a percentagem cumulativa de uma imagem ocorrer com

determinado valor de semelhança. A linha rosa (clara) indica que todas as imagens iguais

têm um valor de semelhança superior a 50, 40% valor superior a 700 e 0,02% valor

superior 1200. A linha azul (escura) indica que todas as imagens diferentes têm valor de

semelhança inferior 2150, 50% têm valor inferior a 1200 e 0% têm valor inferior 950.

Estas curvas permitem calcular o limiar de semelhança com base na FAR (False Accept

Rate) e FRR (False Reject Rate) especificada. O FAR é a percentagem de imagens que

sendo diferentes foram consideradas iguais e o FRR é a percentagem de imagens que

foram rejeitas e eram iguais. Por exemplo no gráfico da figura 4.14, para FAR=12,5% e

FRR=7% o limiar é 1100. O limiar de decisão é escolhido consoante o contexto da

autenticação. Em determinados casos o FAR deve ser mínimo e noutros casos o importante

é reduzir o FRR. É necessário ter ainda em atenção que FAR e FRR são dependentes.

Diminuir FAR significa aumentar FRR e vice-versa.

O treino foi realizado com base em 60 imagens de três impressões digitais diferentes, num

universo de 180 imagens. Cada uma das três impressões digitais foi comparada com todas

as outras. Como resultado foram obtidos 180 valores de impressões iguais e 360 de

impressões diferentes. A distribuição dos valores obtidos é mostrada no histograma da

figura 4.15.

Autenticação com impressão digital Página 48

 ISEL Projecto Final de Curso

100,00

90,00

80,00

70,00
Percentagem acumulada

60,00

cum dif
50,00
cum same

40,00

30,00

20,00

10,00

0,00
0

00

00

00

00
0

00

00

00

00

00

00

00

00

00

00
60
10

20

30

40

50

70

80

90

10

11

12

13

18

19
14

15

16

17

20

21

22

23
Distância euclidiana

Figura 4.14 - Percentagem acumulada para impressões iguais e diferentes.

80

70

60

50
Número ocorrências

hist dif
40
hist same

30

20

10

0
0

00

00

00
00

00

00

00

00

00

00

00

00

00

00
20

50

70
10

30

40

60

80

90

14

16

21

23
10

11

12

13

15

17

18

19

20

22

Distância euclidiana

Figura 4.15 - Histograma com distribuição das distâncias euclidianas de imagens

iguais e diferentes.

Autenticação com impressão digital Página 49

 ISEL Projecto Final de Curso

5 - Aplicação de demonstração
Foi criada uma aplicação de demonstração que implementa o algoritmo de autenticação

baseado em textura orientada. A aplicação é constituída por uma janela principal,

apresentada na figura 5.1, com duas funcionalidades: alterar os parâmetros do algoritmo;

chamar as janelas “Registar” e “Autenticar”. Os parâmetros estão identificados pelo nome

e algoritmo onde são usados.

Figura 5.1 – Janela principal.

A janela “Registar”, apresentada na figura 5.2, permite dois modos de registo da impressão

digital. Directamente do sensor óptico se a check box – Sensor – estiver seleccionada, ou

então, de uma imagem gravada em disco. No primeiro modo, as três imagens de registo são

adquiridas através de aplicação que controla o sensor e grava em disco as imagens; esta é

apresentada na figura 5.3. Após a aquisição da terceira imagem o registo é executado.

Nesta janela indicam-se as directorias onde se quer gravar as imagens e registar a

impressão, assim como o nome a dar ao registo. O segundo modo, é idêntico ao primeiro,

Autenticação com impressão digital Página 51

 ISEL Projecto Final de Curso
com excepção na forma de adquirir as imagens. Estas são seleccionadas em disco numa

lista disponível na Combo Box – “Seleccionar impressão digital”. Nos dois modos é

possível visualizar o conjunto de passos do algoritmo. A selecção é feita nas respectivas

check box.

Figura 5.2 - Janela registar.

Autenticação com impressão digital Página 52

 ISEL Projecto Final de Curso

Figura 5.3- Aplicação [Link] que controla o sensor e adquire as imagens no formato
windows bitmap [8].

A janela “autenticar”, ilustrada na figura 5.4, autentica uma impressão digital com outra

registada na base de dados. Directamente do sensor, ou a partir da lista disponível na

combo box – “Seleccionar a impressão digital”. O registo com o qual se pretende autenticar

é seleccionado na combo box – “Seleccionar o ficheiro de registo”. Os resultados da

autenticação vão depender do limiar de decisão, o qual pode ser alterado. A visualização

dos passos seguidos no processo autenticação podem ser seleccionados nas respectivas

opções na parte inferior da janela. Na autenticação, depois do processo terminado, é

mostrada a mensagem de “Acesso Negado”, ver figura 5.4, ou “Acesso Permitido”, ver

figura 5.5 consoante a autenticação é negativa ou positiva, respectivamente. O resultado da

comparação entre as impressões digitais (a medida de semelhança) é também mostrado.

Autenticação com impressão digital Página 53

 ISEL Projecto Final de Curso

Figura 5.4 – Janela de autenticação, com “Acesso Negado”.

Figura 5.5 – Janela de autenticação, com “Acesso Permitido”.

Autenticação com impressão digital Página 54

 ISEL Projecto Final de Curso
Em seguida mostram-se imagens envolvidas na autenticação, usando a aplicação de
demonstração. A figura 5.6 mostra as três imagens usadas no registo da impressão
digital Finger1. A figura 5.7 mostra o resultado de 8 autenticações da mesma impressão
digital com 6 sucessos e 2 insucessos. As figuras 5.8 e 5.9 mostram imagens usadas no
registo e na autenticação, respectivamente, usando uma impressão da classe right loop.

Figura 5.6 - Imagens de registo para a impressão digital Finger1.

(a) (b) (c) (d)

(e) (f) (g) (h)

Figura 5.7: Imagens da impressão digital “Finger1” para autenticação: (a,b,c,e,f,g)

autenticação bem sucedida; (d,h) autenticação falhada.

Autenticação com impressão digital Página 55

 ISEL Projecto Final de Curso

Figura 5.8 - Imagens de registo para a impressão digital Finger2.

(a) (b) (c) (d)

(e) (f) (g) (h)

Figura 5.9 - Imagens da impressão digital Finger2 para autenticação: (a,b,c,f,g)

autenticação bem sucedida; (d,e,h) autenticação falhada.

Autenticação com impressão digital Página 56

 ISEL Projecto Final de Curso

6 – Conclusões e trabalho futuro

Este trabalho trata a autenticação com impressão digital. São apresentadas duas soluções

de autenticação automática de impressões digitais: (i) baseada em minúcias e (ii) baseada

em textura orientada. A solução baseada em minúcias tem bons resultados em imagens

sintéticas (imagens criadas a partir de um simulador), mas apresenta maus resultados, em

imagens reais. A solução baseada em textura orientada funciona bem em imagens reais

com excepção das impressões pertencentes à classe Arch. Este mau desempenho não está

directamente relacionado com o método da textura orientada mas com o algoritmo de

cálculo do ponto de referência que serve para extrair a área analisada.

Este trabalho permitiu chegar à conclusão, que a autenticação baseada em minúcias é

altamente dependente da qualidade da imagem. As minúcias captam em detalhe as

singularidades da imagem, num ambiente onde a qualidade da imagem é boa; nesse

ambiente as minúcias são identificadas correctamente e como consequência a autenticação

é bem sucedida (caso das imagens sintéticas). A dependência com a qualidade da imagem

implica um algoritmo de melhoramento da imagem, que na maior parte da literatura sobre

o assunto, não introduz as melhorias suficientes e acima de tudo consome tempo de

processamento. Pode-se dizer que o método das minúcias produz resultados fiáveis no que

diz respeito à autenticação, quando se verifica a condição da qualidade da imagem. Acções

de melhoria usando este método passariam por implementar algoritmos robustos de

melhoramento da imagem e métodos de aquisição da imagem de boa qualidade.

Ao contrário do uso das minúcias, a textura orientada, produz resultados estatísticos que

têm a vantagem de não serem tão dependentes com a qualidade da imagem, e a

desvantagem de serem menos precisos, porque o nível de detalhe é menor, resultando em

alguns erros. Este método é mais rápido do que aquele baseado em minúcias.

Autenticação com impressão digital Página 57

 ISEL Projecto Final de Curso
Em termos de trabalho futuro seria importante implementar um algoritmo de cálculo do

ponto de referência mais robusto e principalmente, que funcionasse em impressões digitais

do tipo Arch. O desenvolvimento de um algoritmo que detecte impressões do tipo Arch, é

uma forma de resolver o problema. Este algoritmo seria usado para solicitar a autenticação

de outro dedo, dado que, normalmente, um indivíduo possui impressões digitais de várias

classes.

Com o objectivo de tornar a autenticação por textura orientada mais fiável, o cálculo do

limiar de decisão no qual se determina as distribuições das impressões iguais e diferentes

deveria incluir um universo maior de impressões, adquiridas com o sensor óptico, em dois

períodos diferentes para ter em conta as alterações decorridas no tamanho e forma,

provocadas por cortes e acidentes, por exemplo.

Autenticação com impressão digital Página 58

 ISEL Projecto Final de Curso

7 - Referências

[1] E.P. Richards, “Phenotype vs. Genotype: why identical Twins Have Diferent
Fingerprints?”

[2] [Link]

[3][Link]
[Link]

[4] Salil Prabhakar, Fingerprint Classification and Matching Using a Filterbank, PhD
Thesis, Michigan State University, 2001.

[5] [Link]

[6] N. Otsu, "A Threshold Selection Method from Gray-Level Histograms," IEEE
Transactions on Systems, Man, and Cybernetics, vol. 9, no. 1, pp. 62-66, 1979.

[7] D. Gabor, “Theory of comunication”, Journal of the Institution of Electrical Engineers,

93, 1946, pp 429-457.

[8] W. Wouters, “BMP Format –Windows Bitmap File Format Specifications, v1.1”, Clean
Coding Company, 1997.

[9] “Pelas pontas dos dedos”, Revista do Jornal Expresso, 23 de Novembro de 2002.

Autenticação com impressão digital Página 59