Gaudi-AFIS - Journal of the Brazilian Computer Society Logo

Gaudi-AFIS:
Manual de Referência, Utilização e Desenvolvimento
Murilo Santos de Lima
Universidade Federal da Bahia - Instituto de Matemática
Departamento de Ciência da Computação
Grupo de Engenharia de Algoritmos e Programação Distribuída
Av. Adhemar de Barros, S/N, Campus de Ondina
CEP: 40170-110 - Salvador/BA
[email protected]
SUMÁRIO
1
Introdução
4
2
Instalação
5
2.1
Obtendo o código-fonte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2
Pacotes necessários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Compilando o sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.4
Configurando o diretório base nos scripts de teste . . . . . . . . . . . . . . . .
8
3
4
Reconhecimento de impressões digitais: métodos utilizados
10
3.1
Classificação de impressões digitais . . . . . . . . . . . . . . . . . . . . . . .
10
3.2
Comparação de impressões digitais . . . . . . . . . . . . . . . . . . . . . . . .
12
Utilização e exemplos
13
4.1
Diretórios do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.2
Comandos do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.2.1
Subsistema de classificação . . . . . . . . . . . . . . . . . . . . . . .
14
4.2.2
Subsistema de comparação . . . . . . . . . . . . . . . . . . . . . . . .
19
4.2.3
Programas auxiliares . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
Bibliotecas auxiliares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.3.1
Biblioteca de manipulação de imagens em tons de cinza . . . . . . . .
25
4.3.2
Biblioteca de manipulação de sinais 2D . . . . . . . . . . . . . . . . .
26
4.3.3
Biblioteca de lista ligada . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.3.4
Biblioteca de fila de prioridades . . . . . . . . . . . . . . . . . . . . .
29
4.3
4.3.5
5
Biblioteca de mensagens de erro padrão . . . . . . . . . . . . . . . . .
Dificuldades associadas ao desenvolvimento
30
32
Referências Bibliográficas
33
Apêndice A -- Licenciamento
35
A.1 Biblioteca IM - Tecgraf / PUC-Rio . . . . . . . . . . . . . . . . . . . . . . . .
36
A.2 Funções Matlab para Processamento de Imagens de Peter Kovesi . . . . . . . .
36
4
1
INTRODUÇÃO
As impressões digitais constituem-se no identificador biométrico mais amplamente utilizado, tanto por sua aceitação no meio jurídico, forense e civil, quanto por sua praticidade,
segurança e baixo custo. Entidades como agências de polícia utilizam o reconhecimento de
impressões digitais para diversos fins, incluindo o auxílio à investigação criminal pela identificação de indivíduos através de impressões latentes.
Essa identificação no entanto não pode ser feita manualmente, visto que tais entidades dispõem de largas bases de dados. O processo é automatizado, então, por um Sistema Automático
de Identificação de Impressões Digitais (AFIS - Automatic Fingerprint Identification Systems).
Notou-se que: o tema é pouco explorado no Brasil (em especial na Bahia); há demanda
pela utilização de tais sistemas (inclusive da Secretaria de Segurança Pública do Estado da
Bahia); trata-se de um tema atual e com várias questões a serem solucionadas; há carência de
ferramentas livres que auxiliem seu estudo.
Estas considerações levaram à necessidade de implementação de um AFIS, mesmo que
incompleto e em forma de protótipo, para fins acadêmicos. Este texto documenta a implementação de tal sistema pelo grupo Grupo de Engenharia de Algoritmos e Programação Distribuída
(Gaudi) (http://gaudi.dcc.ufba.br/) do DCC/UFBA, no contexto do projeto BIOMÉTRICA, sob
auxílio da Fundação de Amparo à Pesquisa do Estado da Bahia (Fapesb).
Agradeço ao Prof. Perfilino Jr., orientador do projeto de iniciação científica que originou
este trabalho, ao colega Amadeu Júnior por sua colaboração em diversas etapas, à Profa . Fabíola Greve (co-orientadora do referido projeto) pelos sábios conselhos e à FAPESB pelo apoio
financeiro. A todos que de alguma forma contribuíram, em especial ao Deus de Abraão, Isaque
e Jacó pelo Seu constante auxílio.
5
2
INSTALAÇÃO
Este capítulo descreve a instalação do sistema Gaudi-AFIS em um sistema Debian GNU/Linux1 e foi testada na versão Lenny RC2. A instalação em outras distribuições do GNU/Linux
ou em sistemas Microsoft Windows não foi testada. Para instalações em Microsoft Windows é
necessário o uso de sistemas como Cygwin2 ou MinGW3 .
2.1
OBTENDO O CÓDIGO-FONTE
O código-fonte do Gaudi-AFIS está disponível no seguinte endereço eletrônico, clicando
no item “código-fonte do projeto”:
http://wiki.dcc.ufba.br/Gaudi/ProjetoICMuriloBiometrica
2.2
PACOTES NECESSÁRIOS
Para compilar o sistema, os seguintes pacotes são necessários:
• gcc
• make
• fftw-dev
A biblioteca IM, do laboratório Tecgraf/PUC-Rio4 é fornecida juntamente com o código,
na versão 2.6. O licenciamento da mesma é descrito no Apêndice A.
1 http://www.debian.org/
2 http://www.cygwin.com/
3 http://www.mingw.org/
4 http://www.tecgraf.puc-rio.br/im/
6
Existe um programa de geração de números aleatórios na pasta test escrito em linguagem
Pascal. Apesar de não ter sido utilizado, para compilar tal programa é necessário o pacote gpc.
A ferramenta conv_jpgtiff utiliza o programa GIMP5 em tempo de execução.
A ferramenta conv_cjpegb utiliza comandos do sistema NFIS do NIST/FBI6 em tempo de
execução. Tal ferramenta, no entanto, só é utilizada para testar o sistema com a basa de dados
NIST Special Database 14 (WATSON, 1993), fornecida juntamente com o NFIS. O usuário que
desejar realizar tais testes deve solicitar o sistema NFIS diretamente ao NIST7 .
Para executar alguns scripts de teste, são necessários os seguintes pacotes:
• octave2.1
• octave2.1-forge
• gnuplot
• imagemagick
Alguns scripts de teste também utilizam comandos do sistema NFIS.
Alguns scripts de teste utilizam as funções de processamento de imagens para Matlab desenvolvidas por Peter Kovesi (KOVESI, 2005). As funções estão disponibilizadas, com pequenas modificações para utilização no Octave, no diretório share/octave/peter_kovesi/.
Consulte o licenciamento no Apêndice A.
Para visualização dos arquivos com resultados de testes (no formato ODS), é necessário o
uso da aplicação OpenOffice.org Calc8 .
2.3
COMPILANDO O SISTEMA
Para compilar o sistema, extraia o pacote para um diretório, por exemplo, /usr/local/gaudi-afis/:
cd /usr/local
tar -zxvf gaudi-afis.tar.gz
5 http://www.gimp.org/
6 http://fingerprint.nist.gov/NFIS/
7 Membros
do grupo Gaudi têm acesso a um CD-ROM com uma versão do NFIS.
8 http://www.openoffice.org/product/calc.html
7
Entre no diretório onde o sistema foi extraído, abra o arquivo Makefile com um editor de
texto simples. Altere a variável PROJDIR para o diretório no qual o sistema foi extraído:
...
SHELL=/bin/sh
PROJDIR= /usr/local/gaudi-afis
...
Caso queira compilar o sistema para Microsoft Windows, altere também a variável EXEEXT
para o valor .exe:
...
CFLAGS =
CDEFS =
EXEEXT = .exe
...
Para compilar o sistema, execute os comandos:
make install
Os arquivos executáveis serão disponibilizados na pasta bin. Para que os mesmos estejam acessíveis no terminal, edite o arquivo .bash_profile no seu diretório pessoal (diretório
"home"), adicionando a seguinte linha no final do arquivo:
export PATH=$PATH:/usr/local/gaudi-afis
Novamente, substitua /usr/local/gaudi-afis pelo diretório no qual você instalou o sistema.
Nota para futuro mantenedor: Na versão atual, o comando make está com problemas,
uma vez que as bibliotecas recém-compiladas ainda não estarão na pasta lib. Por isso apenas
o comando make install deve ser executado. O futuro mantenedor deve corrigir isto.
8
2.4
CONFIGURANDO O DIRETÓRIO BASE NOS SCRIPTS
DE TESTE
Alguns scripts de teste necessitam que seja configurado o diretório no qual o sistema está
instalado.
Especificamente, para realizar testes no console do Octave, é necessário acrescentar à variável LOADPATH os caminhos que contêm código a ser utilizado. Algumas funções no diretório
share/octave/peter_kovesi/ são utilizadas por diversos scripts de teste, portanto em alguns diretórios há um arquivo inicializa.m que atualiza a variável LOADPATH da seguinte
forma:
LOADPATH=strcat(LOADPATH, "/usr/local/gaudi-afis/share/octave/peter_kovesi/");
Novamente, substitua /usr/local/gaudi-afis/ pelo diretório no qual o sistema está
instalado. Para utilizar tais funções no console do Octave, execute o código acima ou crie um
link simbólico do arquivo test/inicializa.m para o diretório no qual você está trabalhando
e execute inicializa();. Para executar um script Octave (utilizando o comando octave -q)
que utilize as funções acima, é necessário que o arquivo inicializa.m esteja no diretório
corrente.
Eis uma listagem dos arquivos de teste que devem ter o diretório do sistema configurado:
share/octave/example_scripts/kovesi_script.m
share/octave/example_scripts/pankanti_script
test/inicializa.m
test/script_exec.sh
test/script_exec_kovesi.sh
test/teste.sh
test/nfis/script_exec.sh
test/performance/script_exec_kovesi.sh
test/performance/script_exec.sh
test/performance/teste.sh
9
test/performance/comparativo/script_exec*.sh
test/performance/novo_teste/teste.sh
Alguns scripts de teste supõem que o usuário possui o sistema NFIS instalado no diretório
/usr/local/nfis/. Caso o usuário queira utilizar tais scripts e tenha o sistema NFIS instalado
em outro diretório, deve configurar os seguintes arquivos:
test/script_exec.sh
test/script_exec_kovesi.sh
test/nfis/script_exec.sh
test/performance/script_exec_kovesi.sh
test/performance/script_exec.sh
test/performance/comparativo/script_exec*.sh
Os scripts de teste na pasta test/performance/comparativo/ supõem que existem imagens de teste na pasta test/performance/comparativo/imgs/ no formato WSQ (formato
do NFIS). Essas imagens não são fornecidas com o sistema. Uma opção é copiar algumas
imagens da base de imagens fornecida com o NFIS. Para os resultados que são apresentados no
arquivo test/performance/comparativo/comparativo.ods, foram utilizadas 198 imagens
(200 menos 2 que não puderam ser classificadas).
Nota para futuro mantenedor: para facilitar a configuração do diretório do sistema, podese criar um arquivo no diretório raiz do projeto que centralize a configuração. Os demais scripts
utilizariam o dado desse arquivo.
10
3
RECONHECIMENTO DE
IMPRESSÕES DIGITAIS:
MÉTODOS UTILIZADOS
Este capítulo descreve os elementos básicos de um AFIS e os métodos que foram implementados no Gaudi-AFIS.
O trabalho de um AFIS consiste em identificar um indivíduo através de sua impressão
digital. O sistema compara uma digital com uma massa de digitais disponibilizadas em um
banco de dados. Dois problemas básicos precisam ser resolvidos: (1) como comparar se duas
imagens são do mesmo dedo e (2) como classificar as imagens de forma a otimizar a busca em
grandes bases de dados. Os métodos apresentados neste capítulo são agrupados em torno desses
dois problemas.
Para uma abordagem completa sobre reconhecimento de impressões digitais, consulte (MALTONI et al., 2003).
3.1
CLASSIFICAÇÃO DE IMPRESSÕES DIGITAIS
O método de classificação empregado no Gaudi-AFIS é baseado na análise de pontos singulares (KARU; JAIN, 1999; COSTA, 2001). As imagens são classificadas em uma das classes
de Henry (THE. . . , 2003). Os resultados foram apresentados em (LIMA; FERREIRA JÚNIOR,
2007).
A classificação utiliza a arquitetura exibida na Figura 3.1. Obtém-se a imagem direcional
da imagem, dos quais são identificados os pontos singulares com base no cálculo do Índice
de Poincaré. Segmenta-se a imagem do plano de fundo, removendo pontos singulares falsos.
Classifica-se então a impressão digital com base em avaliações geométricas das coordenadas
dos pontos singulares.
Foram implementados os métodos de segmentação de Maio (MAIO; MALTONI, 1997;
11
Figura 3.1: Arquitetura do sistema de classificação
MALTONI et al., 2003, p. 95) e Amengual (AMENGUAL et al., 1997, seção “Fingerprint
image preprocessing”); os métodos de Karu (KARU; JAIN, 1999, p. 10), de Pankanti (JAIN;
PANKANTI, 1999, p. 10), de Hong (JAIN; HONG; BOLLE, 1997, p. 11–12) e de Kovesi
(KOVESI, 2005) de cálculo da imagem direcional, sendo os três últimos baseados num mesmo
princípio descrito em (MALTONI et al., 2003, p. 89), com pequenas variações.
(COSTA, 2001) descreve, para o método de Karu, dois métodos de suavização da imagem direcional, denominados método da moda e do seno-cosseno, sendo o segundo também
descrito em (KARU; JAIN, 1999). Ambos foram implementados, juntamente com uma suavização utilizando um borramento gaussiano (que, conforme (MALTONI et al., 2003, p. 88-89),
não funciona). Sugere-se também implementar uma suavização utilizando filtros sequenciais
alternados (MAINTZ, 2007, p. 157–158).
Duas variações do cálculo do índice de Poincaré foram implementadas, a descrita em
(KARU; JAIN, 1999, p. 5–8), que utiliza blocos do tipo 3 × 3 e gira no sentido horário, e a
descrita em (MALTONI et al., 2003, p. 97–100), que utiliza blocos 2 × 2 e gira no sentido antihorário. A classificação é realizada utilizando os métodos em (KARU; JAIN, 1999, p. 5–8),
(MALTONI et al., 2003, p. 97–100) e (COSTA, 2001, p. 65–69), mais algumas modificações
sugeridas em (LIMA; FERREIRA JÚNIOR, 2007).
12
3.2
COMPARAÇÃO DE IMPRESSÕES DIGITAIS
Iniciou-se a implementação da comparação de impressões digitais segundo a arquitetura
descrita em (COSTA, 2001; JAIN; PANKANTI, 1999) e em (MALTONI et al., 2003, p. 113):
aplicam-se filtros para melhorar a qualidade da imagem; em seguida-se, aplica-se a binarização, transformando a imagem em preto e branco e afinamento, que reduz a espessura das linhas
(cristas) da impressão digital a um pixel. Com base na imagem afinada, identifica-se as minúcias. Utilizando a posição das minúcias e a angulação das cristas adjacentes, compara-se duas
impressões digitais, utilizando um algoritmo de casamento de padrões.
Foi implementado o método de melhoramento de imagem de Hong (HONG; WAN; JAIN,
1998; MALTONI et al., 2003, p. 107), embora não tenham sido obtidos resultados satisfatórios
(o resultado não influenciou positivamente na classificação) e iniciou-se a implementação da
filtragem com filtros de Gabor (ver Seção 4.2.2) (JAIN; PANKANTI, 1999, p. 13–17), (MALTONI et al., 2003, p. 108–111). Sugere-se futuramente a implementação do melhoramento
utilizando filtros sequenciais alternados (MAINTZ, 2007, p. 157–158).
A binarização e o afinamento seguem os métodos descritos em (COSTA, 2001), bastante
abordados na literatura. Adicionalmente, foi implementado o algoritmo de podamento descrito
em (GONZALEZ; WOODS, 2002, p. 545–547). No entanto, é necessário ainda complementar
o afinamento com algoritmos como staircase removal (FACON, 2004) e extração de componentes conectados (SERRA, 1982). No diretório src/inutil há o início de uma implementação
da extração de componentes conectados, mas o desempenho está inviável. Uma boa técnica de
melhoramento da imagem afinada que poderia ser implementada é o “preenchimento de buracos” descrito em (AMENGUAL et al., 1997, seção “Elimination of Small Holes”). Sugere-se
também, para efeito de comparação dos resultados, a implementação de outros métodos de binarização, tais como os descritos em (JAIN; HONG; BOLLE, 1997, p. 12–14, seção “Ridge
Detection”) e (MALTONI et al., 2003, p. 116–117), este último utilizando filtros de Gabor.
A identificação e filtragem das minúcias e algoritmos de comparação não foram implementados.
13
4
UTILIZAÇÃO E EXEMPLOS
Este capítulo descreve os recursos do Gaudi-AFIS, sua utilização e alguns exemplos. Apresenta-se uma descrição de cada comando, dos parâmetros identificados como bons, assim como
das bibliotecas auxiliares.
O sistema Gaudi-AFIS executa em uma arquitetura do tipo “canos e filtros” (do inglês pipe
and filter1 ), em que cada etapa do processamento consiste em um programa individual, que
utiliza arquivos (geralmente imagens) como entrada, executa algum processamento e devolve
outro arquivo como saída. Para automatizar a execução de vários filtros, o usuário pode utilizar
código ShellScript2 ; ver, por exemplo, o arquivo test/script_exec.sh.
4.1
DIRETÓRIOS DO SISTEMA
O sistema contém os diretórios a seguir:
• bin - após a compilação, conterá os executáveis dos programas do sistema e auxiliares
• doc - contém esta documentação e seu fonte LATEX
• etc - (atualmente este diretório está vazio)
• include - contém os arquivos-cabeçalho das bibliotecas do sistema
• inutil - após a compilação, conterá os executáveis para programas que não estão funcionando (nota para futuro mantenedor: ver um local melhor para colocar esses programas; cuidado para não misturar com código estável)
• lib - contém bibliotecas de terceiros fornecidas juntamente com o sistema e, após a
compilação, conterá as bibliotecas do sistema
1 http://www.dossier-andreas.net/software_architecture/pipe_and_filter.html
2 http://aurelio.net/shell/
14
• res_testes_src - contém resultados de testes de implementação; especificamente, contém o resultado de testes comparativos (visuais) dos algoritmos de cálculo da imagem
direcional (ver Seção 3.1)
• share - contém arquivos a serem utilizados nos testes no Octave. Note que o Octave
aceita apenas imagens no formato JPG ou em formato de matriz (ver na Seção 4.2.3 a
descrição do programa tiff2octave).
• src - contém o código-fonte do sistema
• test - contém scripts de teste e os resultados de alguns testes, funcionando também como
uma espécie de “sandbox”. Nos diretórios test/performance e test/performance/novo_teste
estão os testes de tempo de execução e no diretório test/performance/comparativo
estão os testes de taxa de acerto na classificação. No diretório test/performance/problematicas
há uma cópia das imagens do NFIS que não puderam ser classificadas pelo sistema, devido à grande quantidade de ruído
• thinning - contém arquivos auxiliares ao algoritmo de afinamento e podamento (ver
Seção 4.2.2)
4.2
COMANDOS DO SISTEMA
Esta seção descreve o funcionamento de cada comando do sistema. Ao executar um programa com parâmetros incorretos, é exibida uma mensagem com o formato correto do mesmo.
O código-fonte dos programas também contém informação relevante sobre seu funcionamento.
Parâmetros entre maior e menor (<>) devem ser substituídos por um valor (numérico ou
textual); parâmetros entre colchetes ([]) são opcionais.
4.2.1
SUBSISTEMA DE CLASSIFICAÇÃO
Esta seção descreve os programas relacionados ao problema de classificação de impressões
digitais (ver Seção 3.1).
SEGMENTAÇÃO DA IMAGEM
Sintaxe do comando:
segmentation <metodo> <imagem> <tam_bloco> <lim_gradiente> [verbose] [octave]
15
<metodo> deve ser maio ou amengual (ver Seção 3.1).
<imagem> deve ser o caminho para uma imagem no formato TIFF3 sem alpha. Ver a
descrição do programa conv_jpgtiff na Seção 4.2.3.
<tam_bloco> deve ser um inteiro informando o tamanho do bloco de segmentação: a imagem é dividida em blocos, e cada bloco é analisado se pertence à imagem ou ao plano de fundo.
Na literatura recomenda-se blocos de tamanho 16.
<lim_gradiente> deve ser um número decimal informando o limiar de segmentação.
Para o método de Maio, recomenda-se utilizar o valor .2; para o método de Amengual, .02.
Verificou-se que o valor ótimo depende, no entanto, da qualidade da imagem.
O parâmetro verbose, caso presente, indica que o programa deve exibir mensagens indicando a situação da execução.
O parâmetro octave, caso presente, indica que o programa deve gerar um arquivo no formato de matriz do Octave com a imagem do gradiente, no caso do método de Maio, ou da
variância, no caso do método de Amengual.
Como saída, é gerada a imagem segmentada segmented.tiff.
CÁLCULO DA IMAGEM DIRECIONAL
Sintaxe do comando:
direction <imagem> <metodo> <PARAMETROS> [octave] [verbose]
<imagem> deve ser o caminho para uma imagem no formato TIFF sem alpha (a mesma
imagem de entrada do programa de segmentação; ver descrição de conv_jpgtiff na Seção
4.2.3)).
<metodo> deve ser karu, kovesi, pankanti ou hong (ver Seção 3.1). Os PARAMETROS
dependem do método:
• Karu: <num_direcoes> <dim_bloco> <tipo_suaviz>
<num_direcoes> deve ser 8 ou 16; recomenda-se 8.
<dim_bloco> deve ser um inteiro, define o tamanho do bloco de subdivisão da imagem.
Após o cálculo da imagem direcional, este método realiza uma suavização da imagem
3 http://pt.wikipedia.org/wiki/Tagged_Image_File_Format
16
direcional (ver Seção 3.1): a cada bloco é atribuída uma única direção, com base nas
direções dos pixeis no bloco. Recomenda-se 16; recomenda-se também utilizar o mesmo
tamanho de bloco da segmentação.
<tipo_suaviz> deve ser 1 para método da moda, 2 para método do seno-cosseno, 3 para
borramento gaussiano e 4 para filtros sequenciais alternados. Nota: Esta última opção
ainda não está implementada; ao selecioná-la, será realizado borramento gaussiano.
• Kovesi: <desv_gradiente> <desv_momento> <desvio_suaviz>
Os três parâmetros são inteiros e indicam desvios em borramentos gaussianos; consultar
o arquivo share/octave/peter_kovesi/ridgeorient.m. O autor do método recomenda utilizar os valores 1 3 3.
• Pankanti e Hong: <dim_bloco> <lim_cons>
<dim_bloco> deve ser um inteiro, define o tamanho do bloco de subdivisão da imagem
(valor de W em (JAIN; PANKANTI, 1999, p. 10)). Recomenda-se 32.
<lim_cons> deve ser um decimal, define o limite superior para a consistência das orientações em uma região (valor de Tc em (JAIN; PANKANTI, 1999, p. 10), valor em graus).
Recomenda-se 50.0.
O parâmetro octave, caso presente, indica que o programa deve gerar um arquivo no formato de matriz do Octave com a imagem direcional (opcionalmente, com o mapa de consistência também; ver nota abaixo).
O parâmetro verbose, caso presente, indica que o programa deve exibir mensagens indicando a situação da execução.
Como saída é gerado o arquivo direcoes.dat contendo a imagem direcional num formato
interno ao sistema. O formato é descrito no arquivo src/bin/direction/direction.c, linhas 17–22. Nota para futuro mantenedor: Esse formato grava cada direção como um double
inteiro, o que consome muito espaço em disco. Utilizar um número fixo de direções e fazer uma
aproximação não funciona, seria necessário utilizar um processo de quantização (GOMES;
VELHO, 1994).
Note que o formato da estrutura de dados para a imagem direcional está no arquivo include/direction
de forma que a imagem direcional possa ser utilizada em outros programas.
Parâmetros em tempo de compilação: Alguns parâmetros podem ser modificados apenas
em tempo de compilação. Obviamente, sua alteração requer que o sistema seja recompilado
(ver Seção 2.3).
17
• O cálculo da confiabilidade da imagem direcional foi implementado em alguns métodos
mas não pôde ser aproveitado na classificação (mantenedor: futuramente, rever isto),
logo por padrão não é inserido no arquivo direcoes.dat (nem é utilizado por outros
programas). Para modificar esta opção, edite a variável global GERA_CONF nos arquivos
src/bin/direction/direction.c, linha 74 e src/bin/direction/kovesi.c, linha
67, alterando seu valor de 0 para 1.
• Para realizar, nos método de Kovesi e Pankanti, uma suavização da imagem direcional
similar à realizada no método de Karu, modifique a variável TESTA_SUAVIZ nos arquivos
src/bin/direction/kovesi.c, linha 66 e src/bin/direction/pankanti.c, linha
62, aterando seu valor de 0 para 1. No método de Pankanti, isso é feito por padrão.
• Para o método de Pankanti, pode-se imprimir o número de melhoras que o programa tentar realizar (isto é útil para testes): modifique a variável PRINT_MELHORAS no arquivo
src/bin/direction/pankanti.c, linha 61, alterando seu valor de 0 para 1. No entanto, a impressão só ocorre se a opção verbose for indicada.
• No método de Pankanti é possível definir o máximo de melhoras que o programa deve
tentar. Por padrão utiliza-se 100. Para alterar modifique a variável LIM_MELHORAS no
arquivo src/bin/direction/pankanti.c, linha 60.
• Nos métodos de Pankanti e Hong, é possível definir o tamanho da vizinhança local
(tamanho de D em (JAIN; PANKANTI, 1999, p. 10)). Por padrão utiliza-se 5, conforme indicado pelos autores. Para alterar modifique a variável TAM_VIZ nos arquivos
src/bin/direction/pankanti.c, linha 60 e src/bin/direction/hong.c, linha 61.
CLASSIFICAÇÃO DE IMPRESSÕES DIGITAIS
Sintaxe do comando:
classification <direcional> <imagem_original> <vizinhanca> [sem_blocos]
[verbose] [saida_pts]
<direcional> deve ser o caminho para o arquivo gerado pelo programa de cálculo da
imagem direcional.
<imagem_original> deve ser o caminho para a imagem original (formato TIFF sem alpha;
ver descrição de conv_jpgtiff na Seção 4.2.3), de preferência segmentada.
18
<vizinhanca> deve ser 2x2 ou 3x3. Recomenda-se utilizar 2x2; ver Seção 3.2.
O parâmetro sem_blocos, caso presente, indica que o cálculo do índice de Poincaré (ver
Seção 3.2) deve ser feito pixel a pixel. Recomenda-se utilizar esta opção. Caso não esteja
presente, o cálculo é feito por blocos (isto é, só é considerada a direção do bloco inteiro), o que
só deve ser feito se a vizinhança for do tipo 2x2.
O parâmetro verbose, caso presente, indica que o programa deve exibir mensagens indicando a situação da execução.
O parâmetro saida_pts, caso presente, indica que o programa deve gerar um arquivo texto
singular_points.txt contendo a informação dos pontos singulares identificados (coordenadas e tipo), juntamente com uma imagem singularity.tiff, que consiste na imagem original
com os pontos singulares pintados (núcleos de vermelho, deltas de verde e verticilos em azul –
verticilos, no entanto, não foram encontrados nos testes).
Como saída, o programa imprime na saída-padrão o número da classe da impressão digital
(0 = arco, 1 = presilha esquerda, 2 = presilha direita, 3 = cicatriz, 4 = arco angular, 5 = verticilo).
Imagens com alto nível de ruído, que não puderem ser classificadas como uma das classes
padrão, serão classificadas como cicatriz (classe 3).
Parâmetros em tempo de compilação: Alguns parâmetros podem ser modificados apenas
em tempo de compilação. Obviamente, sua alteração requer que o sistema seja recompilado
(ver Seção 2.3).
• Caso o cálculo do índice de Poincaré seja realizado por blocos, o sistema supõe blocos de
tamanho 16 × 16. Para alterar isto, modifique o valor inicial da variável TAM_BLOCO na
linha 73 do arquivo src/bin/classification/classification.c.
• É possível modificar o número de máximo suavizações que o programa deve tentar (pa-
drão = 10): modifique o valor comparado com a variável num_suaviz no arquivo src/bin/classifi
linha 187.
• É possível imprimir o número de suavizações que o programa tentar realizar (isto é útil
para testes): modifique a variável CONTA_SUAVIZ no arquivo src/bin/classification/classific
linha 78, alterando seu valor de 0 para 1. No entanto, a impressão só ocorre se a opção
verbose for indicada. Esta opção é habilitada por padrão.
• Caso a opção saida_pts esteja indicada, é possível visualizar (na imagem singularity.tiff)
a linha que o algoritmo traça ao testar se a digital é do tipo arco angular (caso ele alcance
19
esse ponto): modifique a variável VERIFICA_TA no arquivo src/bin/classification/classifica
linha 79, alterando seu valor de 0 para 1.
• Caso a opção saida_pts esteja indicada, é possível visualizar (na imagem singularity.tiff)
o caminho que o algoritmo percorre em direção à borda ao testar se a digital é do tipo
presilha direita ou presilha esquerda (caso ele alcance esse ponto): modifique a variável
VERIFICA_LOOP no arquivo src/bin/classification/classification.c, linha 80,
alterando seu valor de 0 para 1. Para modificar o máximo de pontos percorridos, altere o
valor comparado com a variável i na linha 456 do mesmo arquivo (padrão = 50).
• Para alterar o limite de erro no cálculo do índice de Poincaré, altere a variável LIM_ERRO_POINCARE
na linha 55 do arquivo src/bin/classification/poincare.c. O valor deve estar em
graus, deve ser inteiro e seu padrão é 5.
• Para alterar a distância mínima (exclusiva) entre dois pontos singulares, altere a variável TAM_LIM_DIST na linha 56 do arquivo src/bin/classification/poincare.c. O
valor deve estar em pixeis, deve ser inteiro e seu padrão é 16 (a largura de um bloco
padrão).
4.2.2
SUBSISTEMA DE COMPARAÇÃO
Esta seção descreve os programas relacionados ao problema de comparação de impressões
digitais (ver Seção 3.2).
MELHORAMENTO DE HONG
Sintaxe do comando:
hong_enhancement <imagem> <media> <variancia> [octave] [verbose]
<imagem> deve ser o caminho para uma imagem no formato TIFF sem alpha (ver descrição
de conv_jpgtiff na Seção 4.2.3).
<media> e <variancia> devem ser inteiros no intervalo [0, 255]. Ver referências na Seção
3.2.
O parâmetro verbose, caso presente, indica que o programa deve exibir mensagens indicando a situação da execução.
Como saída, o programa gera a imagem normalizada normalized.tiff.
20
Parâmetros em tempo de compilação: É possível modificar o tamanho do bloco utilizado
no melhoramento (por padrão, utiliza-se 16 × 16). Para tanto, modifique a variável TAM_BLOCO
na linha 56 do arquivo src/bin/enhancement/hong.c. Obviamente, sua alteração requer que
o sistema seja recompilado (ver Seção 2.3).
FILTRAGEM DE GABOR
O programa para melhoramento da imagem com filtros de Gabor (ver Seção 3.2) não foi
concluído. O código encontra-se na pasta src/bin/enhancement/gabor, arquivo gabor.c.
Ali há um scprit compila_gabor.sh que compila o código, gerando o executável gabor. Para
executá-lo:
gabor <imagem>
Há também um diretório octave com funções para teste no Octave. Para executá-los, edite
o arquivo inicializa.m, substituindo o diretório /usr/local/gaudi-afis pelo diretório no
qual o sistema foi instalado. Execute octave e, no terminal do Octave, digite os seguintes
comandos:
inicializa();
imgs = enh_gabor('<imagem>');
imagem deve ser o nome do arquivo de uma imagem no formato JPG. A variável imgs
contém uma matriz de imagens filtradas. Cada imagem pode ser visualizada com o comando
show(imgs(:,:,i,j));, sendo i e j índices inteiros e i ∈ [1, 3], j ∈ [1, 8].
Há também no diretório gabor uma implementação da FFT (Transformada Rápida de Fourier) (CORMEN et al., 2002, cap. 30) baseada na descrita em (MYLER; WEEKS, 1993), que
não está funcionando (arquivos fft.c e usa_fft.c). Seu uso foi substituído pela biblioteca
FFTW4 . O script compila_fft.sh compila esse código. Para testá-lo, execute ./usa_fft. O
programa utiliza como entrada a imagem teste.tiff e gera como saída as imagens img_fft.tiff
e img_inv_fft.tiff (transformada e inversa da trasformada).
O futuro mantenedor, caso o finalize o programa de filtragem de Gabor, deve mover o
arquivo gabor.c para o diretório superior (enhancement) e incluí-lo no Makefile. Ver arquivo
src/bin/thinning/Makefile como exemplo de como compilar mais de um programa no
4 http://www.fftw.org/
21
mesmo Makefile. Não esquecer de incluir as bibliotecas -lfftw -lrfftw na variável LLIBS.
Se possível, criar um programa que integre os melhoramentos de Hong e Gabor (ver como
exemplo o programa src/bin/direction/direction.c). Lembrar também que é necessário,
ao recompilar, recriar o wisdom da biblioteca FFTW (consultar documentação referente).
AFINAMENTO
Sintaxe do comando:
thinning <imagem> <arquivo_mascaras> <passo_a_passo>
<imagem> deve ser o caminho para uma imagem no formato TIFF sem alpha (ver descrição
de conv_jpgtiff na Seção 4.2.3). Fornecer, de preferência, uma imagem segmentada e melhorada.
<arquivo_de_mascaras> deve ser o caminho para um arquivo semelhante a thinning/mask.dat
ou thinning/mask2.dat, contendo máscaras a serem utilizadas no afinamento (consulte referências na Seção 3.2).
<passo_a_passo> deve ser 0 ou 1. Caso seja selecionado 1, o programa gera uma série de
imagens com nomes no formato temp<i>-<j>.tiff (sendo i e j inteiros) com o passo-a-passo
do processo de afinamento. Uma animação pode ser gerada utilizando o comando convert do
pacote ImageMagick5 (consultar documentação referente).
Como saída, o programa gera a imagem binarizada binarizado.tiff, a imagem afinada
thin.tiff e imprime na saída-padrão o número de passos realizados no afinamento.
PODAMENTO
Sintaxe do comando:
poda <imagem> <arquivo_mascaras> <passo_a_passo> [verbose]
<imagem> deve ser o caminho para uma imagem afinada no formato TIFF sem alpha. Utilizar a imagem fornecida pelo programa de afinamento, descrito acima.
<arquivo_de_mascaras> deve ser o caminho para um arquivo semelhante a thinning/mask_poda.da
contendo máscaras a serem utilizadas no podamento (consulte referências na Seção 3.2).
5 http://www.imagemagick.org/
22
<passo_a_passo> deve ser 0 ou 1. Caso seja selecionado 1, o programa gera uma série de
imagens com nomes nos formatos original.tiff, temp<i>-<j>.tiff e dilata<i>.tiff
(sendo i e j inteiros) com o passo-a-passo do processo de podamento. Uma animação pode
ser gerada utilizando o comando convert do pacote ImageMagick (consultar documentação
referente).
O parâmetro verbose, caso presente, indica que o programa deve exibir mensagens indicando a situação da execução.
Após o fornecimento dos parâmetros, o programa aguarda na entrada-padrão por um inteiro
informando o número de passos a ser utilizado no podamento. Recomenda-se utilizar o número
de passos fornecido pelo programa de afinamento.
Note-se aqui que o usuário pode automatizar o processo de afinamento-podamento redirecionando a saída-padrão do afinamento para um arquivo x e em seguida redirecionar a entradapadrão do podamento para x. Por exemplo, supondo que o usuário se encontra no diretório base
do sistema:
$ thinning img.tiff thinning/mask.dat 0 > x
$ poda thin.tiff thinning/mask_poda.dat 0 < x
Como saída, o programa gera a imagem afinada poda.tiff.
4.2.3
PROGRAMAS AUXILIARES
Esta seção descreve o funcionamento dos programas auxiliares ao sistema.
• confusion - gera uma matriz de confusão6 com base em um arquivo com os resultados esperados e outro arquivo com os resultados de teste. Os arquivos devem estar em
modo texto e devem conter um inteiro no intervalo [0, MAX_CLASSES[ por linha, cada
inteiro representando uma classe (ver classes na descrição do programa de classificação
na Seção 4.2.1). Os dois arquivos devem possuir o mesmo número de resultados. Para
alterar o número de classes (padrão = 6), edite a variável NUM_CLASS na linha 39 do arquivo src/etc/confusion.c, altere o caracter-nome das classes na linha 44 do mesmo
arquivo e recompile o sistema (ver Seção 2.3). Parâmetros: <arquivo_classes_reais>
<arquivo_classes_teste>. A matriz de confusão é impressa na saída-padrão.
6 http://en.wikipedia.org/wiki/Confusion_matrix
23
• conv_cjpegb - converte uma imagem RAW (gerada pelo comando dwsq do NFIS) numa
imagem no formato JPEGB (ver documentação do NFIS), utilizando o comando cjpegb
do NFIS. Parâmetros: <qualidade> <formato> <imagem> <arquivo NCM> (sugere-se
utilizar os valores 95 para a qualidade e jpg para o formato). A imagem convertida é gerada com o mesmo nome da fornecida e com o formato especificado. Para utilizar a imagem resultante no sistema, converta-a em seguida utilizando o comando conv_jpgtiff
(ver abaixo).
• conv_jpgtiff - converte uma imagem JPEG em uma imagem no formato TIFF aceito
pelo sistema (sem alpha), utilizando o modo Batch do programa GIMP7 . Note que o comando convert da ferramenta ImageMagick não produz o formato desejado. Parâmetro:
imagem de entrada. A imagem de saída é gerada com o nome digital.tiff.
• edit_res - edita o resultado de um arquivo gerado pelo programa testa (ver descrição
abaixo). Limpa o resultado, exibindo apenas o valor de tempo de cada teste. Ao final,
exibe o valor da média e do desvio padrão dos dados fornecidos. Parâmetros: arquivo de
resultados. O resultado é gravado num arquivo com nome idêntico ao arquivo de entrada
mais o sufixo _ed.
• gaussian - efetua um borramento gaussiano sobre uma imagem no formato aceito pelo
sistema (ver descrição de conv_jpgtiff acima). Este programa só deve ser utilizado
para testes, por ser acoplado e ter baixo desempenho; o sistema deve utilizar as funções
da biblioteca de manipulação de sinais (ver Seção 4.3.2). Parâmetros: imagem a ser borrada e desvio da função gaussiana (número decimal). O resultado é gravado na imagem
gaussian.tiff.
• testa - executa testes de desempenho de um programa. Executa o comando 30 vezes,
testando seu tempo de execução (30 é o mínimo necessário para obter-se uma distribuição
normal das medidas8 ). Para alterar o número de testes, modifique a variável NUM_TESTES
na linha 40 do arquivo src/etc/testa.c e recompile o sistema (ver Seção 2.3). Parâmetros: arquivo no qual os resultados serão gravados, caminho para o comando a ser
executado nos testes (pode apenas o nome do comando, se o mesmo estiver nos diretórios
do PATH do sistema) e os argumentos para o programa a ser testado. Recomenda-se finalizar todos os aplicativos em execução (inclusive, se possível, o gerenciador de janelas)
durante a execução dos testes, a fim de obter-se medidas confiáveis.
7 http://www.gimp.org/tutorials/Basic_Batch/
8 http://www.ufpa.br/dicas/biome/bionor.htm
24
• tiff2octave - converte uma imagem TIFF no padrão do sistema (ver descrição de
conv_jpgtiff acima) no formato de imagem-matriz do Octave (que pode ser lido utilizando a função loadimage. Parâmetros: imagem a ser convertida, caminho para o
arquivo a ser gerado. Consultar documentação do Octave para maiores informações.
• xor - calcula a função ou exclusivo entre duas imagens em tons de cinza (no formato
TIFF sem alpha; ver comando conv_jpgtiff acima) (GONZALEZ; WOODS, 2002).
Parâmetros: caminhos para as duas imagens a serem comparados. O resultado é gravado
no arquivo xor.tiff.
• connected_componentes (executável no diretório inutil) - calcula o maior componente conectado de uma imagem (SERRA, 1982, p. 41–42). Em seguida, recorta a imagem, deixando apenas a área do maior componente conectado. Este programa não está
funcionando bem, principalmente por ter um desempenho intratável. Parâmetros: imagem. É gravado um arquivo lista_pts.dat com a lista dos pixels da região calculada;
a imagem recortada é gravada no arquivo recorte.tiff.
Há ainda, no diretório src/etc/plota_min, o início da implementação de um programa
para pintar um conjunto de minúcias em uma imagem de impressão digital (arquivo plota.c).
As minúcias devem estar descritas em um arquivo no formato XYT do NFIS com o nome
finger.xyt, e a imagem deve estar no formato TIFF sem alpha com o nome finger.tiff
(ver acima descrição de conv_jpgtiff). Não se sabe se as coordenadas no arquivo XYT estão
sendo interpretadas corretamente. O resultado é gravado no arquivo finger+min.tiff. Para
compilar o programa, execute o script compila_plota.sh. Há ainda uma tentativa de obter-se
o mesmo resultado utilizando a ferramenta GNUPlot9 no arquivo combina.sh, no entanto há
uma translação entre a imagem das minúcias e a imagem da impressão digital. Mantenedor:
após obter um resultado razoável e correto, o programa deve ser modificado para receber o
nome dos arquivos de entrada como parâmetro.
4.3
BIBLIOTECAS AUXILIARES
Esta seção apresenta uma descrição das bibliotecas do sistema. Para uma descrição da
biblioteca IM, consulte http://www.tecgraf.puc-rio.br/im/.
9 http://www.gnuplot.info/
25
4.3.1
BIBLIOTECA DE MANIPULAÇÃO DE IMAGENS EM TONS DE
CINZA
Arquivo-cabeçalho: include/proc_img.h - declara os tipos Tcor (cor, equivalente a
unsigned char), Imagem e MapaCinza e as consantes PRETO, CINZA, BRANCO (cores) e tam_pal_cinza
(tamanho da paleta e tons de cinza).
Funções:
• int abrirImagem (Imagem *img, char *nome_arq);
abre a imagem do arquivo nome_arq. A estrutura img já deve estar alocada, mas não
inicializada. Retorna 0 se obteve sucesso.
• Tcor corImagem (Imagem *img, int x, int y, int tipo_ext);
obtém a cor da imagem img no pixel [x, y]. tipo_ext indica o tratamento para pixels
além das bordas: se 0, retorna PRETO; se 1, retorna BRANCO. Retorna -1 em caso de erro.
• void apagarImagem (Imagem *img);
desaloca conteúdo da estrutura img. Não desaloca a estrutura em si.
• void inicializa_paleta (void);
inicializa a paleta de tons de cinza.
• int criaMapaCinza (MapaCinza *img, int larg, int alt);
cria um mapa de tons de cinza com as dimensões larg e alt. A estrutura img já deve
estar alocada, mas não inicializada. Retorna 0 se obteve sucesso.
• Tcor corMapaCinza (MapaCinza *img, int x, int y, int tipo_ext);
obtém a cor do mapa de tons de cinza img no pixel [x, y].tipo_ext indica o tratamento
para pixels além das bordas: se 0, retorna PRETO; se 1, retorna BRANCO. Retorna -1 em
caso de erro.
• int mudaCorMapaCinza (MapaCinza *img, int x, int y, Tcor cor);
altera a cor do mapa de tons de cinza img no pixel [x, y]. Retorna 0 se obteve sucesso.
• int gravaMapaCinza (MapaCinza *img, char *nome_arq);
grava o mapa de tons de cinza img no arquivo nome_arq. Retorna 0 se obteve sucesso.
• void apagaMapaCinza (MapaCinza *img);
desaloca conteúdo da estrutura img. Não desaloca a estrutura em si.
26
4.3.2
BIBLIOTECA DE MANIPULAÇÃO DE SINAIS 2D
Arquivo-cabeçalho: include/proc_sinal.h - declara o tipo MapaSinal2d. Note que
este tipo é declarado como um ponteiro para uma estrutura.
Funções:
• int criaMapaSinal2d(MapaSinal2d *img, int larg, int alt);
cria um mapa de sinal 2D com as dimensões larg e alt. O “objeto” resultante é inicializado com zeros e é gravado no endereço indicado pelo ponteiro img (mantenedor:
aparentemente, isto está causando vazamento de memória, devido a uma suposição sobre
o comportamento da função malloc. Quando tenta-se alocar um ponteiro com tamanho
sizeof(MapaSinal2d*), parece estar alocando a estrutura e não apenas o ponteiro. O
mesmo parece ocorrer quando se declara uma variável do tipo MapaSinal2d). Retorna 0
se obteve sucesso.
• int inicializaMapaSinal2d(MapaSinal2d img, double valor);
inicializa o mapa de sinal 2D com o valor valor. Supõe que o mapa esteja inicializado
(isto é, alocado/criado). Retorna 0 se obteve sucesso.
• double valorMapaSinal2d(MapaSinal2d img, int x, int
y, int tipo_ext);
obtém o valor do mapa de sinal 2D img no ponto [x, y]. tipo_ext indica o tratamento
para pontos além das bordas: se 0, retorna 0.0; se 1, retorna +∞; se 2, retorna o valor do
ponto da borda mais próximo. Retorna +∞ em caso de erro.
• int setaMapaSinal2d(MapaSinal2d img, int x, int y, double valor);
altera o valor do mapa de sinal 2D img no ponto [x, y] para valor. Retorna 0 se obteve
sucesso.
• int copiaMapaSinal2d(MapaSinal2d img_in, MapaSinal2d img_out);
copia os valores do mapa de sinal 2D img_in para img_out. Supõe que ambas as imagens
já estão inicializadas. Retorna 0 se obteve sucesso.
• void apagarMapaSinal2d(MapaSinal2d img);
desaloca conteúdo da estrutura img e a estrutura em si (mantenedor: problema de vazamento de memória também se aplica aqui).
27
• MapaSinal2d filtrarMapaSinal2d(MapaSinal2d img,
MapaSinal2d kernel, MapaSinal2d outp);
filtra o mapa img com o núcleo kernel, retornando o resultado (isto é, convolui img
com kernel). img e kernel devem estar inicializados. Se outp estiver inicializado, a
saída será gravada nele; senão, será alocada uma nova estrutura (passe NULL para sempre
alocar). Caso outp esteja inicializado, deve ter as mesmas dimensões de img. Retorna
NULL em caso de erro.
• MapaSinal2d gradienteMS2d(MapaSinal2d img, char var,
MapaSinal2d outp);
calcula o gradiente do mapa img em relação à variável var (que deve ser 'x' ou 'y'. São
utilizadas máscaras de Sobel10 para o cálculo. Se outp estiver inicializado, a saída será
gravada nele; senão, será alocada uma nova estrutura (passe NULL para sempre alocar).
Caso outp esteja inicializado, deve ter as mesmas dimensões de img. Retorna NULL em
caso de erro.
• MapaSinal2d opAritMS2d(MapaSinal2d op1, MapaSinal2d op2,
char op, MapaSinal2d outp);
calcula uma operação aritmética ponto-a-ponto entre dois mapas. Os dois mapas devem
estar inicializados e devem ter as mesmas dimensões. op define a operação e deve ser '+',
'-', '*', ou '/'. Se outp estiver inicializado, a saída será gravada nele; senão, será alocada uma nova estrutura (passe NULL para sempre alocar). Caso outp esteja inicializado,
deve ter as mesmas dimensões de op1 e op2. Retorna NULL em caso de erro.
• MapaSinal2d multEscalarMS2d(MapaSinal2d op, double
escalar, MapaSinal2d outp);
multiplica cada elemento do mapa op pelo escalar escalar. op deve estar inicializado.
Se outp estiver inicializado, a saída será gravada nele; senão, será alocada uma nova
estrutura (passe NULL para sempre alocar). Caso outp esteja inicializado, deve ter as
mesmas dimensões de op. Retorna NULL em caso de erro.
• MapaSinal2d somaEscalarMS2d(MapaSinal2d op, double
escalar, MapaSinal2d outp);
soma cada elemento do mapa op com o escalar escalar. op deve estar inicializado.
Se outp estiver inicializado, a saída será gravada nele; senão, será alocada uma nova
10 http://www.pages.drexel.edu/~weg22/edge.html
28
estrutura (passe NULL para sempre alocar). Caso outp esteja inicializado, deve ter as
mesmas dimensões de op. Retorna NULL em caso de erro.
• MapaSinal2d aplicaFuncMS2d(MapaSinal2d op, double
(*f)(double x), MapaSinal2d outp);
aplica uma função f: double -> double em cada elemento do mapa op. op deve estar
inicializado. Se outp estiver inicializado, a saída será gravada nele; senão, será alocada
uma nova estrutura (passe NULL para sempre alocar). Caso outp esteja inicializado, deve
ter as mesmas dimensões de op. Retorna NULL em caso de erro.
• MapaSinal2d aplicaFunc2argMS2d(MapaSinal2d op1,
MapaSinal2d op2, double (*f)(double y, double x), MapaSinal2d
outp);
aplica uma função f: (double, double) -> double em cada par de elementos dos mapas
op1 e op2 de mesma posição. O elemento de op1 é fornecido como primeiro parâmetro da função; o elemento de op2 como o segundo. Note que a função fornecida deve
considerar y como sendo o primeiro parâmetro. op1 e op2 devem estar inicializados e
devem ter as mesmas dimensões. Se outp estiver inicializado, a saída será gravada nele;
senão, será alocada uma nova estrutura (passe NULL para sempre alocar). Caso outp esteja inicializado, deve ter as mesmas dimensões de op1 e op2. Retorna NULL em caso de
erro.
• MapaSinal2d filtroGabor(MapaSinal2d img, int nscale, int
norient, int minWaveLength, int mult, double sigmaOnf, double
dThetaOnSigma);
a implementar.
• MapaSinal2d GaussianKernel(int sigma);
retorna um núcleo gaussiano com desvio sigma. Retorna NULL em caso de erro.
4.3.3
BIBLIOTECA DE LISTA LIGADA
Arquivo-cabeçalho: include/listaligada.h - declara os tipos ChaveLL (o elemento
a ser gravado na lista, composto das coordenadas de um pixel), ElemLL (o nó da lista) e
ListaLigada.
Funções:
29
• void inicializaLL(ListaLigada *l);
inicializa uma lista ligada. A estrutura l já deve estar alocada, mas não inicializada.
• int buscaLL(ListaLigada *l, ChaveLL *ch);
retorna 1 se existe um elemento com chave idêntica a ch em l; retorna 0, caso contrário.
• int insereLL(ListaLigada *l, ChaveLL *ch);
insere (ordenadamente) um elemento com chave ch na lista l. Se o elemento já existia na
lista, retorna 1; senão, retorna 0.
• int gravaArquivoLL(ListaLigada *l, char *nome_arq);
grava a lista l no arquivo nome_arq. O arquivo é gravado em formato binário, como uma
sucessão de coordenadas x e y. Não aceita uma lista vazia. Retorna 0 se obteve sucesso.
• void apagarLL(ListaLigada *l);
desaloca conteúdo da estrutura l. Não desaloca a estrutura em si.
Nota para futuro mantenedor: Nesta biblioteca não está sendo feito qualquer tratamento
de erros. Modificar isto.
4.3.4
BIBLIOTECA DE FILA DE PRIORIDADES
Arquivo-cabeçalho: include/filaprioridade.h - declara os tipos ElemFP (o elemento a
ser gravado na fila, composto de um double – o valor a ser gravado – e um long – a prioridade
do elemento na fila) e FilaPrioridades. Note que esses tipos são declarados como ponteiros
para estruturas.
Para entender filas de prioridades, consulte (CORMEN et al., 2002, Seção 6.5).
Funções:
• ElemFP criaElemFP(double valor, long chave);
cria e retorna um elemento da fila com valor valor e prioridade chave. Retorna NULL
em caso de erro.
• int inicializaFP(FilaPrioridades *f);
cria um fila de prioridades e inicializa-a. O “objeto” resultante é gravado no endereço
indicado pelo ponteiro f (mantenedor: verificar problema com vazamento de memória
aqui também). Retorna 0 se obteve sucesso.
30
• void apagarFP(FilaPrioridades f);
desaloca conteúdo da estrutura f e a estrutura em si (mantenedor: verificar se problema
de vazamento de memória também se aplica aqui).
• int insereFP(FilaPrioridades f, ElemFP elem);
insere elemento elem na fila de prioridades f. Retorna 0 se obteve sucesso.
• int insereValorFPnrep(FilaPrioridades f, double valor);
insere o valor valor na fila f, aumentando sua prioridade (evitando repetições de elementos). Retorna 0 se obteve sucesso.
• ElemFP maximoFP(FilaPrioridades f);
retorna o elemento com maior prioridade na fila f. Em caso de erro, ou se a fila estiver
vazia, retorna NULL.
• double valorMaximoFP(FilaPrioridades f);
retorna o valor do elemento de maior prioridade na fila f. Em caso de erro, finaliza o
programa (mantenedor: melhorar isto).
• ElemFP retiraMaxFP(FilaPrioridades f);
retira o elemento com maior prioridade na fila f e retorna-o. Em caso de erro, retorna
NULL.
• int aumentaChaveFP(FilaPrioridades f, long i, ElemFP elem);
substitui o elemento na posição i da fila f por elem. A substituição, no entanto, só ocorre
se a prioridade de elem for maior que a prioridade antiga na posição i. Retorna 0 se
obteve sucesso.
4.3.5
BIBLIOTECA DE MENSAGENS DE ERRO PADRÃO
Arquivo-cabeçalho: include/erros.h.
Funções:
• void erro_img(void);
Mensagem de erro informando imagem não inicializada.
31
• void erro_memoria(void);
Mensagem de erro informando erro com alocação de memória.
• void erro_escreve_arq(void);
Mensagem de erro informando erro na gravação de arquivo.
• void erro_le_arq(void);
Mensagem de erro informando erro na leitura de arquivo.
32
5
DIFICULDADES ASSOCIADAS AO
DESENVOLVIMENTO
A principal dificuldade no desenvolvimento do Gaudi-AFIS foi a não-utilização de bibliotecas de manipulação de imagens e de processamento de sinais prontas. Tentou-se ainda utilizar
GSL1 , no entanto boa parte do código já estava implementado, logo não valia a pena refazer
tudo.
O fato de a versão utilizada da biblioteca IM (2.6) só funcionar com imagens TIFF sem
alpha também foi um incoveniente, já que um bom tempo foi gasto em pesquisa sobre conversão
de formatos.
O sistema foi reestruturado diversas vezes, a fim de se obter uma estrutura melhor, mas
principalmente (e infelizmente) para obter melhor desempenho, principalmente relacionado a
uso de memória (o que, infelizmente, não foi alcançado por completo).
Uma coisa que ajudou bastante foi o uso de Makefiles2 . Além disso, o fato de sistemas AFIS
terem uma arquitetura bem definida na literatura (do tipo “canos e filtros”, do inglês pipe and
filter3 ) e de tal tipo de arquitetura ser inerente ao Linux (herdado do UNIX) facilitou bastante o
projeto do sistema.
Pequenos detalhes também implicaram em melhorias absurdas de desempenho; a principal
foi a troca da ordem dos for’s durante laços em imagens ou mapas de sinais: devido à utilização
de uma matriz, colocar a segunda dimensão (y) no for mais externo leva a um desempenho
melhor, já que o “vetor” é acessado sequencialmente. Problemas em associar as dimensões com
o formato cartesiano fixado na mente também ocorreram. Outro exemplo: um pequeno erro no
programa de segmentação de imagens (que foi corrigido) levava a uma péssima taxa de acerto
na classificação inteira.
1 http://www.gnu.org/software/gsl/
2 http://www.hsrl.rutgers.edu/ug/make_help.html
3 http://www.dossier-andreas.net/software_architecture/pipe_and_filter.html
33
REFERÊNCIAS BIBLIOGRÁFICAS
AMENGUAL, J. C. et al. Real-time minutiae extraction in fingerprint images. In: Sixth
International Conference on Image Processing and Its Applications. Washington, DC, USA:
IEEE Computer Society, 1997. v. 2, p. 871–875.
CORMEN, T. H. et al. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 2002. Tradução
da 2a edição americana.
COSTA, S. M. F. Classificação e Verificação de Impressões Digitais. Dissertação (Mestrado)
— Universidade de São Paulo, 2001.
FACON, J. Algoritmo de Afinamento de Holt. 2004. Pontifícia Universidade Católica do Paraná.
Disponível em <http://www.ppgia.pucpr.br/~facon/Afinamento/AfinamentoHolt3.
pdf>.
GOMES, J.; VELHO, L. Computação Gráfica: Imagem. Rio de Janeiro, Brasil: IMPA:
Instituto de Matemática Pura e Aplicada e SBM: Sociedade Brasileira de Matemática, 1994.
ISBN 85-244-0088-9.
GONZALEZ, R. C.; WOODS, R. E. Digital Image Processing. 2nd. ed. New York: Prentice
Hall, 2002.
HONG, L.; WAN, Y.; JAIN, A. K. Fingerprint image enhancement: Algorithms and
performance evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence,
v. 20, n. 8, p. 777–789, 1998. ISSN 0162-8828.
JAIN, A.; PANKANTI, S. Fingerprint Classification and Matching. Department of Computer
Science, Michigan State University, East Lansing, MI, USA, 1999. Technical Report
MSU-CPS-99-5.
JAIN, A. K.; HONG, L.; BOLLE, R. On-line fingerprint verification. IEEE Transactions on
Pattern Analysis and Machine Intelligence, v. 19, n. 4, p. 302–313, 1997.
KARU, K.; JAIN, A. K. Fingerprint Classification. Department of Computer Science,
Michigan State University, East Lansing, MI, USA, 1999. Technical Report MSU-CPS-99-21.
KOVESI, P. Matlab Functions for Image Processing. 2005. University of Western Australia.
Acessado em: Julho de 2007. Disponível em: <http://www.csse.uwa.edu.au/~pk/
research/matlabfns/>.
LIMA, M. S. de; FERREIRA JÚNIOR, P. E. Classificação de impressões digitais via análise
de pontos singulares. In: Workshop of Undergraduate Work, XX Brazilian Symposium
on Computer Graphics and Image Processing. Belo Horizonte, MG, Brazil: Sociedade
Brasileira de Computação, 2007. Disponível em <http://wiki.dcc.ufba.br/pub/Gaudi/
Publicacoes/wuw-sibgrapi2007-published.pdf>.
34
MAINTZ, T. Digital and Medical Image Processing. 2007. Utrecht University. Disponível em
<http://www.cs.uu.nl/docs/vakken/imgp/>.
MAIO, D.; MALTONI, D. Direct gray-scale minutiae detection in fingerprints. IEEE
Transactions on Pattern Analysis and Machine Intelligence, v. 19, n. 1, p. 27–40, 1997.
MALTONI, D. et al. Handbook of Fingerprint Recognition. New York: Springer-Verlag, 2003.
MYLER, H. R.; WEEKS, A. R. Computer Imaging Recipes in C. Englewood Cliffs, NJ, USA:
Prentice-Hall, 1993.
SERRA, J. Image Analysis and Mathematical Morphology. Orlando, FL, USA: Academic
Press, 1982.
THE Henry Classification System. 2003. International Biometric Group. Disponível em
<http://www.biometricgroup.com/Henry%20Fingerprint%20Classification.pdf>.
WATSON, C. I. NIST Special Database 14, Fingerprint Database. National Institute of
Standards and Technology, 1993.
35
APÊNDICE A -- LICENCIAMENTO
Este apêndice apresenta o licenciamento do projeto Gaudi-AFIS. O código do projeto em
si está licenciado sob a GPL versão 2, na seguinte forma:
Copyright (C) 2007
Murilo Santos de Lima
Projeto Biometrica
Grupo de Engenharia de Algoritmos e Programação Distribuída
Departamento de Ciência da Computação
Instituto de Matemática
Universidade Federal da Bahia
http://gaudi.dcc.ufba.br/
under support of Fundação de Amparo à Pesquisa do Estado da Bahia
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
O arquivo GPLv2.txt no diretório raiz do projeto contém uma cópia da GPL versão 2.
36
A biblioteca IM do laboratório Tecgraf/PUC-Rio e as Funções Matlab para Processamento
de Imagens de Peter Kovesi têm suas licenças específicas, apresentadas a seguir. Tais licenças
também estão presentes no arquivo LICENSE.
A.1
BIBLIOTECA IM - TECGRAF / PUC-RIO
c 1994-2007 Tecgraf / PUC-Rio and PETROBRAS S/A.
Copyright Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
A.2
FUNÇÕES MATLAB PARA PROCESSAMENTO DE
IMAGENS DE PETER KOVESI
Copyright (c) 1995-2007 Peter Kovesi
School of Computer Science & Software Engineering
The University of Western Australia
http://www.csse.uwa.edu.au/
Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
37
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
The software is provided "as is", without warranty of any kind, express or
implied, including but not limited to the warranties of merchantability, fitness
for a particular purpose and noninfringement. In no event shall the authors or
copyright holders be liable for any claim, damages or other liability, whether
in an action of contract, tort or otherwise, arising from, out of or in
connection with the software or the use or other dealings in the software.