Upload
internet
View
109
Download
0
Embed Size (px)
Citation preview
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:
• Versão discretizada:
• h geralmente é representada por uma matriz chamada de máscara do filtro
dttxhtfxhfxfL )()()()(
k
knhkfnhf )()()(
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
• Faz uma média ponderada
com os pixels vizinhos
• Suaviza a imagem
2
22
2
)(
22
1,
yx
eyxG
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:
• Gradiente discreto (4 métodos):1. Gx(j, k) = ½ i(j + 1, k) – ½ i(j – 1, k)
2. Gx(j, k) = i(j + 1, k) – i(j, k)
3. Gx(j, k) = i(j, k) – i(j – 1, k)
4. Gx(j, k) = i(j + 1, k + 1) – i(j, k)
Gy(j, k) = i(j, k + 1) – i(j + 1, k)
y
IG
x
IG yx
;
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°
Delta-180°
Núcleo180°
Ordinário0°
Tipo de pontoSomatório
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) 4-conectados 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