Algoritmos de Classificação
e Verificação de
Impressões Digitais
Imagem
• Cena real: cada ponto no espaço emite um impulso
luminoso
• Definição matemática (imagem contínua):
– Função i: U  C, onde U é uma superfície do R³ e C é um
espaço vetorial
• Como i é função, pode-se definir continuidade, derivada, gradiente
– Geralmente U é um subconjunto do plano e C é um espaço de
cor
• Se dim(C) = 1, a imagem é monocromática (geralmente em tons de
cinza)
• Imagens coloridas são formadas por 3 componentes (geralmente
Red, Green, Blue)
• Imagens coloridas são tratadas, em muitos casos, como três
imagens distintas em tons de cinza
Imagem Digital
• Representação Matricial:
• A = (ajk)mxn = (i(xj, yk))
– Discretização de um
retângulo
• Cada elemento: pixel (picture element)
• Representações retangular e hexagonal:
simplificação da definição de vizinhança
4-vizinhança e 8-vizinhança de um pixel
Formato de um arquivo de imagem
• Cabeçalho: formato, dimensões da imagem,
padrão de compressão
• Vetor de cores formado pelas linhas da matriz
da imagem
– 24 bits: canal alpha, R, G, B (8 bits para cada
componente)
– 8 bits: tons de cinza (R = G = B)
• preto = 0; branco = 255
– 1 bit (imagem binarizada):
• preto = 0; branco = 1
Operações sobre imagens
• O espaço das imagens no plano é um
espaço vetorial
• Classificação em relação ao escopo de
atuação
– Local: T(p) depene do comportamento de
uma vizinhança de p
– Pontual: T(p) depende apenas do valor de p
• Operações unárias são chamadas de
filtros
Filtros
• Extrema importância em tratamento de
imagens
• Baseados na teoria de sinais
• Tipos
– Lineares (transformação linear) x não-lineares
– Estatísticos x determinísticos
– Filtros de amplitude x topológicos
• Filtros de amplitude: operam nas cores
• Topológicos: operam na estrutura da imagem
Convolução
• Sendo h a função de resposta de impulso de um
filtro L, a aplicação do filtro sobre uma imagem f
é obtida pela convolução:
L f ( x)   f  h( x) 

 f (t )h( x  t )dt

• Versão discretizada:  f  h (n) 

 f ( k ) h( n  k )
k  
• h geralmente é representada por uma matriz
chamada de máscara do filtro
Convolução (2)
• Na prática (máscara 3x3):
• 0 := 0.0’ + 1.1’ + 2.2’ + 3.3’ + 4.4’ + 5.5’ + 6.6’ + 7.7’ + 8.8’
• Algoritmo caro
– pode ser reduzido utilizando-se transformada de
Fourier
Ex.: Filtro Gaussiano
G x, y  
1
2 
2
( x 2  y 2 )
e
2 2
• Faz uma média ponderada
com os pixels vizinhos
• Suaviza a imagem

Imagem Direcional / Campo de
Orientação
• Imagem com a direção de blocos de pixels
• Obtém-se informações de uma impressão digital
através da direção das cristas
• Remoção de minúcias falsas
• Classificação nos grupos de Henry
• Fácil de atenuar ruído
• Baseia-se nos gradientes (derivadas parciais)
da imagem
Gradiente
•
Definição: G  I ; G  I
x
y
•
Gradiente discreto (4 métodos):
x
1.
2.
3.
4.
y
Gx(j, k) = ½ i(j + 1, k) – ½ i(j – 1, k)
Gx(j, k) = i(j + 1, k) – i(j, k)
Gx(j, k) = i(j, k) – i(j – 1, k)
Gx(j, k) = i(j + 1, k + 1) – i(j, k)
Gy(j, k) = i(j, k + 1) – i(j + 1, k)
Imagem Direcional (método 1)
• Cálculo da direção do pixel (i, j):
• Cálculo do índice de consistência da imagem
direcional em um bloco de pixels (i, j):
• Se este índice está acima de um limite, a imagem direcional é
recalculada nesse bloco utilizando uma resolução menor
Image Direcional (método 2)
• Calculam-se as grandezas
direcionais S1, ..., S7
• Sp = min {Si | i=1,...7}
• Sq = max {Si | i=1,...,7}
• Direção (depende da cor do
pixel)
Suavização da Imagem Direcional
• A direção é obtida para grupos de 9 pixels
(3x3) e não pixels individuais
• Métodos:
– Moda: valor para o grupo é o valor mais
freqüente
– Seno-cosseno: média dos vetores da forma
(cos2a, sen2a)
Avaliação de um AFIS
• FAR (False Acceptance Rate)
• FRR (False Rejection Rate)
• EER (Equal Error Rate)
– Valor para o qual FAR = FRR
– Boa medida de qualidade
– FBI: classificação boa se
• FRR = 20%  FAR = 1%
Passos para Classificação
• Cálculo da imagem direcional
• Identificação dos pontos singulares
– Índice de Poincaré
• Classificação
Cálculo do índice de Poincaré
• Toma-se uma curva fechada em torno dos
blocos de pixels
• Calcula-se o somatório (S) das diferenças entre
ângulos consecutivos no sentido anti-horário
• S > 90°  S := S – 180°
• S < -90º  S := S + 180°
Somatório
Tipo de ponto
0°
Ordinário
180°
Núcleo
-180°
Delta
Classificação
• Atribui-se então uma classe com base no número de
pontos singulares
– Nenhum ponto: arco
– Um núcleo e um delta: arco angular ou presilha
• Necessário calcular a direção do vetor núcleo-delta
– Dois núcleos e deltas: verticilo
– Mais de dois núcleos ou deltas: necessário suavizar imagem
direcional (ex.: filtro gaussiano)
• Usando as duas técnicas combinadas, obtém-se 12,5%
de erro.
• Utilizando uma mesma classe para arco e arco angular,
obtém-se erro de 7,7%
Passos para Verificação
• Pré-processamento
– Binarização
– Afinamento
• Detecção de minúcias
• Comparação com a base de dados
Binarização (Thresholding)
• Transformação de uma imagem de tons de
cinza em preto/branco (imagem binária)
– Ex.: limiar de 128 (cinza 50%)
• Pixels com cor >= 128 serão pintados de preto
• Pixes com cor < 128 serão pintados de branco
• Thresholding adaptativo:
– transformação feita por blocos (8x8 ou 10x10)
– valor de limiar (T) é calculado pela média dos tons de
cinza do bloco
– imagem pode ter regiões mais claras/escuras
Afinamento
• Obtenção da estrutura das cristas com
dimensão unitária, facilitando a extração das
minúcias
• Requisitos:
– A conectividade das linhas da imagem original deve
ser preservada
– A imagem deve conter o mínimo de pixels
necessários para manter-se 8-conectada
– Cristas finais próximas devem ser mantidas próximas
– As linhas resultantes devem estar aproximadamente
no centro das linhas originais
– Reentrâncias inseridas na imagem devem ser
minimizadas
Afinamento (2)
• Cortam-se as bordas até obter dimensão 1
• Atribui-se um estado intermediário aos
pixels a serem apagados
– Evitar erosão
• O número máximo de pixels conectados na
vizinhança é 1
• O comprimento máximo das cadeias de
pixels (tanto pretos como brancos) 4conectados deve ser maior que 1
– Manter cristas finais
– Evitar erosão
• Ao final de uma iteração, pixels apagados
são pintados de branco
• Iterações até nenhum pixel ser apagado
Detecção de Minúcias
• Cálculo do Crossing Number (CN)
– Pixel é uma bifurcação se possui 3 pontos vizinhos
– Pixel é crista final se possui apenas 1 ponto vizinho
• Armazena-se, então:
– Tipo da minúcia
– Direção e distância ao ponto singular (geralmente o
núcleo)
– Direção da crista que contém a minúcia
Banco de filtros de Gabor
• O filtro de Gabor
seleciona regiões da
imagem que têm uma
direção preferencial
• Pode ser utilizado para
remover minúcias falsas,
formadas devido à má
qualidade da imagem
Método Sintático de Verificação
• Trata-se a seqüência de registros de minúcias como
uma string
• Aplicam-se transformações (edições: inserções,
deleções) sobre a string candidata a fim de obter a string
do BD
• Calcula-se o mínimo de transformações necessárias
(programação dinâmica)
• Gera-se um índice de similaridade
• Imagem aceita se o índice é maior que um limite
estabelecido (threshold)
• FRR = 19,5%  FAR = 0,003%
Bibliografia
• Costa, S.M.F. Classificação e Verificação de Impressões
Digitais
• Crane, R. A Simplified Approach to Imagem Processing
• Gomes, J.; Velho, L. Computação Gráfica: Imagem
• Jain, A.; Pankanti, S. Fingerprint Classification and Matching
• Prasad, V.S.N.; Domke, J. Gabor Filter Visualization
• Seul, M.; O’Gorman, L.; Sammon, M.J. Practical Algorithms
for Image Analysis