Download - Reconocimiento huellas digitales con Matlab
Diego Barragán – Pablo Vallejo ([email protected])
TABLA DE CONTENIDO
Capitulo 1. ELECCIÓN DEL FORMATO DE IMÁGENES .................................. 1
1.1. Imagen digital. ................................................................................. 1
1.2. Imágenes Vectoriales ...................................................................... 1
1.3. Imágenes de Mapa de Bits. ............................................................. 2
1.4. Formatos de imágenes digitales. ..................................................... 6
Formato de imagen BMP ................................................................. 6
Formato de archivo GIF ................................................................... 6
Formato de archivo TIFF.................................................................. 7
1.5. Elección del Formato. ...................................................................... 8
Capitulo 2. ANÁLISIS Y REPRESENTACIÓN DE HUELLAS DIGITALES ....... 9
2.1. Introducción ..................................................................................... 9
2.2. Características Fundamentales........................................................ 9
2.3. Regiones Singulares ...................................................................... 10
2.4. Minucias. ....................................................................................... 11
Capitulo 3. REALCE DE LA IMAGEN ............................................................. 16
3.1. Introducción ................................................................................... 16
3.2. Binarización. .................................................................................. 20
3.3. Área de Interés. ............................................................................. 22
3.4. Adelgazamiento. ............................................................................ 25
Capitulo 4. IDENTIFICACIÓN DE MINUCIAS ................................................. 26
4.1. Introducción ................................................................................... 26
4.2. Mapa de Crestas. .......................................................................... 26
4.3. Identificación de Minucias .............................................................. 27
Capitulo 5. ALGORITMO DE EMPATE. .......................................................... 32
5.1. Etapa de Alineación. ...................................................................... 32
5.2. Etapa de Empate. .......................................................................... 33
Capitulo 6. MANEJO DE BASE DE DATOS. .................................................. 34
Capitulo 7. Resultados. .................................................................................. 35
7.1. Rendimiento y Eficiencia. ............................................................... 38
7.1.1.Rendimiento .......................................................................... 38
7.1.2.Eficiencia .............................................................................. 39
Capitulo 8. Conclusiones y Recomendaciones. ........................................... 40
Diego Barragán – Pablo Vallejo ([email protected])
Ilustraciones y Tablas
FIGURA 1-1. REPRESENTACIÓN DE UNA IMAGEN MEDIANTE PÍXELES. ...................... 2
FIGURA 1-2. IMAGEN MONOCROMÁTICA, 1 BIT POR PÍXEL. ............................................ 3
FIGURA 1-3. IMAGEN EN ESCALA DE GRISES, 8 BITS POR PÍXEL .................................. 4
FIGURA 1-4. IMAGEN RGB, 24 BITS POR PÍXEL. ................................................................. 4
FIGURA 1-5. IMAGEN EN 256 COLORES .............................................................................. 5
FIGURA 2-1. CRESTAS Y VALLES. ...................................................................................... 10
FIGURA 2-2. TIPOS BÁSICOS DE REGIONES SINGULARES ........................................... 11
FIGURA 2-3. CLASIFICACIONES BÁSICAS DE LOS PATRONES DIGITALES. ................ 11
FIGURA 2-4. TIPOS PRINCIPALES DE MINUCIAS. ............................................................ 12
FIGURA 2-5. COMPONENTES DEL SISTEMA DE MINUCIAS COORDENADAS (F.B.I.). . 13
FIGURA 2-6. DIAGRAMA DE FLUJO ALGORITMO RECONOCIMIENTO ........................... 14
FIGURA 2-7. DIAGRAMA DE FLUJO ALGORITMO DE EMPATE. ...................................... 15
FIGURA 3-1. IMAGEN REALZADA CON ANÁLISIS DE FOURIER TRADICIONAL. ........... 17
FIGURA 3-2. (A) IMAGEN REAL, (B) MODELADO APROXIMADO. .................................... 19
FIGURA 3-3. IMAGEN MEJORADA....................................................................................... 19
FIGURA 3-4. IMAGEN BINARIZADA. .................................................................................... 21
FIGURA 3-5. CAMPO DE ORIENTACIONES ANTES Y DESPUÉS DE APLICAR EL NIVEL DE CONFIABILIDAD. .................................................................................................... 23
FIGURA 3-6. ÁREA DE INTERÉS LUEGO DE APLICAR “BWMORPH”. ............................. 24
FIGURA 3-7. IMAGEN ADELGAZADA. ................................................................................. 25
FIGURA 4-1. MAPA DE CRESTAS. ....................................................................................... 26
FIGURA 4-2. CRESTA CONTINUA. ...................................................................................... 28
FIGURA 4-3. TERMINACIÓN. ................................................................................................ 28
FIGURA 4-4. BIFURCACIÓN. ................................................................................................ 29
FIGURA 4-5. ANCHO ENTRE CRESTAS. ............................................................................ 30
FIGURA 4-6. MINUCIAS MARCADAS. .................................................................................. 31
FIGURA 7-1. OPCIONES DE ALMACENAMIENTO TIFF ..................................................... 35
FIGURA 7-2. INTERFAZ GRÁFICA DEL PROGRAMA ......................................................... 36
FIGURA 7-3. ARCHIVO DAT GENERADO. .......................................................................... 36
FIGURA 7-4. RESULTADOS DE BÚSQUEDA DE HUELLA DESCONOCIDA. .................... 37
FIGURA 7-5. CARACTERÍSTICAS TÉCNICAS DEL COMPUTADOR ................................. 38
FIGURA 7-6. RESULTADO FUNCIONES TIC – TOC PARA ALMACENAMIENTO ............. 38
FIGURA 7-7. RESULTADO FUNCIONES TIC – TOC PARA EMPATE. ............................... 39
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 1. ELECCIÓN DEL FORMATO DE IMÁGENES
1.1. Imagen digital.
Una imagen digital es una representación binaria de una escena real (un
gráfico o dibujo) la misma que puede ser representada o modificada en un
computador u otros dispositivos electrónicos, como teléfonos celulares por ejemplo.
Las imágenes digitales en dos dimensiones se dividen en dos tipos: Imágenes
vectoriales y de mapa de bits.
1.2. Imágenes Vectoriales
Las imágenes vectoriales están compuestas por líneas y curvas definidas de
forma matemática y denominadas vectores. Esto significa que puede mover,
redimensionar o cambiar el color de una línea sin que el gráfico pierda calidad.
Los gráficos vectoriales no dependen de la resolución, es decir, se pueden escalar
a cualquier tamaño e imprimir en cualquier resolución sin pérdida de detalle ni
claridad.
Las imágenes vectoriales tienen el inconveniente de tener dificultades en tratar
algunas cosas de forma natural (sombras, luces, etc.) y cuando son muy grandes o
muy complejas pueden volverse extremadamente difíciles de manejar para la
capacidad de un computador.
Son, por tanto, la mejor opción para crear gráficos que requieren líneas nítidas que
puedan escalarse a distintos tamaños como, por ejemplo, los logotipos.
Diego Barragán – Pablo Vallejo ([email protected])
1.3. Imágenes de Mapa de Bits.
Las imágenes de mapa de bits (denominadas técnicamente imágenes
rasterizadas) están compuestas por una cuadrícula de puntos denominados píxeles.
Al trabajar con imágenes de mapa de bits, se editan los píxeles, en lugar de los
objetos o las formas. Las imágenes de mapa de bits son el medio electrónico más
usado para las imágenes de tono continuo, como fotografías o pinturas digitales,
puesto que pueden representar degradados sutiles de sombras y color.
Las imágenes se pueden representar mediante retículas de celdas a las que vamos
asignando valores. Este modo es la base de todas las imágenes impresas y de
buena parte de las digitales. (Figura 1-1).
Figura 1-1. Representación de una imagen mediante píxeles.
Cada una de las celdas de dicha retícula se llama "píxel", que es una composición
de las palabras inglesas “picture element”. Un píxel es un concepto inmaterial que
no tiene una medida concreta. No se puede afirmar si un píxel mide 1 cm. o 1 km.
En principio, es solamente una medida de división en celdas.
Una forma muy importante de clasificar las imágenes de mapa de bits es según la
cantidad y tipo de información que se asigne a cada píxel.
Diego Barragán – Pablo Vallejo ([email protected])
Imágenes de 1 bit por píxel
En este tipo de imágenes cada celdilla (píxel) sólo puede tener uno de dos valores:
Uno o cero. Como basta 1 bit para definir esa alternativa, se les llama "imágenes de
1 bit" (también se les llama "imágenes de mapa de bits, de alto contraste,
monocromáticas o imágenes de línea"). Figura 1-2.
Figura 1-2. Imagen Monocromática, 1 bit por píxel.
Imágenes de escala de grises (8 bits por píxel)
En este tipo de imágenes, cada píxel puede tener 256 valores diferentes (las 256
posibilidades combinatorias de un byte u octeto). En ellas se distinguen hasta 256
tonos diferentes de gris, por lo general no todos a la vez. (Figura 1-3).
Diego Barragán – Pablo Vallejo ([email protected])
Figura 1-3. Imagen en escala de grises, 8 bits por píxel
Imágenes RGB (24 bits por píxel)
Si se toma un píxel y se le asigna tres bytes, se dispondrá de 24 bits en tres grupos
de ocho, el cual puede ser colorado siguiendo el sistema de color de los monitores
de televisión, que se basan en tres "canales" de luz de color (Rojo, Azul y Verde).
De este modo se puede distinguir aproximadamente 16 millones de tonos de color
(256 Rojo × 256 Azul × 256 Verde). En realidad, lo que se hace es superponer tres
canales de luz, uno rojo, otro verde y otro azul, cada uno con 256 posibilidades de
tono.
Figura 1-4. Imagen RGB, 24 bits por píxel.
Diego Barragán – Pablo Vallejo ([email protected])
Imágenes en color de 8 bits o menos
Es lo que se llama color indexado. Lo que se hace es crear una tabla o índice de 16
o 256 colores generalmente y a cada una de los posibles valores de un píxel se le
asigna uno de ellos.
Figura 1-5. Imagen en 256 colores
Diego Barragán – Pablo Vallejo ([email protected])
1.4. Formatos de imágenes digitales.
Formato de imagen BMP
Esta clase de formato lo utiliza el sistema operativo Windows para guardar sus
imágenes. Este sistema de archivo puede guardar imágenes de 24 bits (millones de
colores), 8 bits (256 colores) y menos.
Esta clase de archivos poseen una muy alta calidad y nitidez en las imágenes, pero
su tamaño en disco es bastante considerable, ya que por lo general, no se
encuentran comprimidos.
Formato de archivo GIF
GIF (Compuserve GIF o Graphics Interchange Format) 1 es un formato gráfico
utilizado ampliamente en la Internet, tanto para imágenes como para animaciones.
GIF llegó a ser muy popular porque podía usar el algoritmo de compresión LZW
(Lempel Ziv Welch) para realizar la compresión de la imagen, que es más eficiente
que el algoritmo Run-Lenght Encoding (RLE). Por lo tanto, imágenes de gran
tamaño podían ser descargadas en un razonable periodo de tiempo, incluso con
modems muy lentos.
GIF es un formato sin pérdida de calidad para imágenes con hasta 256 colores,
limitados por una paleta restringida a este número de colores. Por ese motivo, con
imágenes con más de 256 colores (profundidad de color superior a 8 bits), la
imagen debe adaptarse reduciendo sus colores, produciendo la consecuente
pérdida de calidad.
1 El formato fue creado por CompuServe en 1987 para dotar de un formato de imagen en color para sus áreas de
descarga de archivos.
Diego Barragán – Pablo Vallejo ([email protected])
Formato de archivo TIFF
TIFF (Tagged Image File Format) es un formato de fichero para imágenes.
La denominación en inglés "Tagged Image File Format" (formato de archivo de
imágenes con etiquetas) se debe a que los ficheros TIFF contienen, además de los
datos de la imagen propiamente dicha, "etiquetas" en las que se archiva
información sobre las características de la imagen, que sirve para su tratamiento
posterior.
Estas etiquetas describen el formato de las imágenes almacenadas, que pueden
ser de distinta naturaleza:
• Binarias (blanco y negro), adecuadas para textos, por ejemplo.
• Niveles de gris, adecuadas para imágenes de tonos continuos como fotos
en blanco y negro.
• Paleta de colores, adecuadas para almacenar diseños gráficos con un
número limitado de colores.
• Color real, adecuadas para almacenar imágenes de tono continuo, como
fotos en color.
Las etiquetas también describen el tipo de compresión aplicado a cada imagen, que
puede ser:
• Sin compresión.
• PackBits.
• Huffman modificado.
• LZW, el mismo que usa el formato GIF.
• JPEG.
Diego Barragán – Pablo Vallejo ([email protected])
1.5. Elección del Formato.
La lectura de la imagen al entorno de Matlab, se realizó mediante la función
“imread”, lo cual permite trabajar con casi cualquier formato de imagen existente.
Luego de realizadas las pruebas, y basando la selección en dos criterios
primordiales, que son calidad de la imagen y tamaño de la misma, se concluye que
los formatos óptimos para el proyecto son los “BMP” y “TIFF”.
Sin embargo, se seleccionó el formato TIFF, que presenta la ventaja de ser
compresible, con lo cual se emplea menos memoria en la base de datos, sin
presentar una pérdida en la calidad de la imagen.
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 2. ANÁLISIS Y REPRESENTACIÓN DE HUELLAS DIGITALES
2.1. Introducción
Una huella digital es una representación de la forma de la piel de las yemas
de los dedos, que se produce cuando se presionan los dedos sobre una superficie
lisa. Se trata de un patrón, único y diferente, de un dedo humano.
Las huellas digitales se encuentran completamente formadas alrededor de los siete
meses de gestación y este patrón permanecerá invariable durante toda la vida del
individuo, salvo el caso de accidentes como heridas o cortes graves.
Si bien se puede afirmar que no pueden existir dos huellas digitales iguales, no se
puede decir que éstas sean patrones completamente aleatorios, ya que poseen
características o formas comunes, las que se detallarán más adelante. [1]
2.2. Características Fundamentales
Una de las características principales de las huellas digitales, es su
individualidad, ya que se considera, con fuertes evidencias, que las huellas digitales
son diferentes de persona a persona, e incluso un mismo individuo posee huellas
diferentes en cada uno de los dedos de sus manos.
Esta característica permite el uso de las huellas digitales como uno de los métodos
de reconocimiento más usados en muy diversas aplicaciones.
Diego Barragán – Pablo
La característica más evid
intercalados entre sí, que aparecen en las imágenes como partes oscuras y claras
respectivamente. (Figura 2
Las crestas y los valles generalmente tienen un espesor que varía entre los 100 y
300µm. [1]
2.3. Regiones Singulares
Al hacer un análisis general, los pa
más regiones donde las líneas de la misma toman formas distintivas.
A éstas partes se las conoce como regiones singulares, las cua
clasificadas en cuatro tipos:
Pablo Vallejo ([email protected])
acterística más evidente de una huella es un patrón de crestas y valles
intercalados entre sí, que aparecen en las imágenes como partes oscuras y claras
(Figura 2-1)
Las crestas y los valles generalmente tienen un espesor que varía entre los 100 y
Figura 2-1. Crestas y Valles.
Regiones Singulares
Al hacer un análisis general, los patrones de las huellas digitales muestran una o
más regiones donde las líneas de la misma toman formas distintivas.
se las conoce como regiones singulares, las cua
tipos: lazos, deltas, remolinos y arcos (Figura 2
huella es un patrón de crestas y valles
intercalados entre sí, que aparecen en las imágenes como partes oscuras y claras
Las crestas y los valles generalmente tienen un espesor que varía entre los 100 y
muestran una o
más regiones donde las líneas de la misma toman formas distintivas.
se las conoce como regiones singulares, las cuales pueden ser
y arcos (Figura 2-2).
Diego Barragán – Pablo Vallejo ([email protected])
Figura 2-2. Tipos Básicos de Regiones Singulares
Las regiones singulares son comúnmente usadas para la clasificación de las
huellas digitales, esto es asignar una huella a una clase específica de un grupo de
clases, basándose en sus regiones singulares, con el fin de simplificar la búsqueda
de las mismas. [1] (Figura 2-3)
Figura 2-3. Clasificaciones Básicas de los patrones digitales.
2.4. Minucias.
En un nivel más detallado, se denotan otras características importantes dentro de
los patrones digitales, conocidas como minucias. Las minucias se refieren a las
diferentes formas en que las crestas pueden ser discontinuas. Por ejemplo, una
cresta puede súbitamente finalizar (terminación), o puede esta dividirse en dos
crestas independientes (bifurcación).
Diego Barragán – Pablo Vallejo ([email protected])
Aunque se pueden considerar diversos tipos de minucias, los principales se
muestran en la Figura 2-4.
Figura 2-4. Tipos principales de Minucias.
El Instituto Nacional Americano de Estándares ANSI, propuso en 1986 un sistema
basado en cuatro clases de minucias: terminaciones, bifurcaciones, trifurcaciones o
cruces, e indeterminados.
Por su parte el Buró Federal de Investigaciones FBI introdujo el modelo de minucias
coordenadas, que considera solo terminaciones y bifurcaciones, las que se denotan
por su clase, las coordenadas en los ejes “x” y “y” y el ángulo entre la tangente de
la línea de la cresta con el eje horizontal, como se aprecia en la Figura 2-5. [1]
Diego Barragán – Pablo Vallejo ([email protected])
Figura 2-5. Componentes del Sistema de Minucias Coordenadas (F.B.I.).
En la práctica existe una ambigüedad entre terminaciones y bifurcaciones, que se
debe a la presión aplicada en el dedo cuando se deja la huella, las terminaciones
pueden aparecer como bifurcaciones y viceversa.
Si se adquiere una imagen en alta resolución, por ejemplo 1000 ppp, es posible
identificar claramente los poros de la piel, que pueden variar en tamaño de 60 a
250µm. Aunque la información de los poros es altamente distintiva, muy pocas
técnicas de identificación usan esta característica, dado que su aplicación confiable
requiere una muy alta resolución e imágenes de muy buena calidad, lo que es difícil
de conseguir en el campo práctico.
Para determinar las características de una huella, el algoritmo propuesto se
muestra en la siguiente figura:
Diego Barragán – Pablo Vallejo ([email protected])
Figura 2-6. Diagrama de Flujo Algoritmo Reconocimiento
Una vez almacenada la huella en la base de datos, se continúa con el proceso de
empate:
Diego Barragán – Pablo Vallejo ([email protected])
Figura 2-7. Diagrama de Flujo Algoritmo de Empate.
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 3. REALCE DE LA IMAGEN
3.1. Introducción
Existen muchas técnicas de reconocimiento biométrico, que comparan directamente
dos imágenes mediante una correlación, pero las imágenes en escala de grises que
se emplean generalmente en estas actividades no son adecuadas para estos
métodos, debido a que la operación de la correlación es precisa solo si las
imágenes tienen la misma orientación y posición en el plano.
Con este antecedente, para un sistema de identificación por huellas digitales, se
hace necesaria una etapa de extracción de características que facilite el
reconocimiento y clasificación.
Así que el garantizar una imagen de calidad aceptable es uno de los puntos básicos
que permiten mejorar la precisión de los sistemas de reconocimiento y
autenticación dactilar, por lo que se debe prestar suma importancia a la etapa de
mejora de las imágenes digitales.
Una imagen de una huella digital puede considerarse como un sistema de texturas
cuya orientación y frecuencia varían lentamente a lo largo de la imagen, es decir
poseen propiedades no estacionarias. Por lo tanto el análisis tradicional de Fourier
no es el adecuado para analizar la imagen completa.
Dado que la calidad de la imagen a procesar no es siempre la más adecuada, al
emplear una Transformada de Fourier tradicional, se obtienen resultados
adecuados solo en ciertas partes de la imagen, lo que implica una gran pérdida de
información en el resto de la misma.
La mayoría de algoritmos de realce, emplean ventanas para su aplicación, por lo
general ventanas de 32 píxeles, lo que combinado con un análisis de Fourier de
tipo estacionario, produce diferencias muy marcadas entre las ventanas de la
Diego Barragán – Pablo Vallejo ([email protected])
imagen, como se ve en la Figura 3-1, lo que además puede introducir información
falsa en la imagen.
Figura 3-1. Imagen realzada con análisis de Fourier tradicional.
Como vemos en la figura, existen sectores donde la calidad de la imagen es óptima,
pero ante una ligera variación de la orientación de las crestas, produce una muy
pobre calidad de la imagen.
Para el presente proyecto se empleará el algoritmo de realce en base al análisis
STFT, propuesto por el Centro Unificado para Biométrica y Sensores de la
Universidad de Buffalo, Estados Unidos. [6]
La Transformada de Fourier de Tiempo Corto o STFT, es una transformada que se
emplea para encontrar la frecuencia sinusoidal y la orientación de secciones locales
de una señal, mientras esta varía con el tiempo. La STFT, para una dimensión está
dada por la ecuación (1):
(1)
Diego Barragán – Pablo Vallejo ([email protected])
En el análisis STFT, se divide la imagen en ventanas que se solapan unas a otras,
con lo que se puede considerar que la imagen es estacionaria en esta pequeña
región, cada bloque es transformado al dominio de Fourier y se almacena como
resultado la frecuencia y orientación del bloque.
Al permitir que las ventanas se solapen unas a otras, se evita también obtener
límites muy marcados entre las diferentes ventanas de la imagen, lo que se conoce
como efecto bloque.
Este método puede ser extendido a dos dimensiones, con lo que la STFT, puede
definirse como:
����� ��� ��� ��� ���� ����� � ��� � ������������������
�
��(2)
Donde I(x, y) es la imagen de entrada y W es una ventana espectral previamente
seleccionada.
A partir de este análisis, se obtienen estimaciones estadísticas de frecuencia de
crestas y orientación de las mismas, las cuales son empleadas para el filtrado de la
imagen.
Con esta información cada bloque puede ser aproximadamente moldeado como
una onda superficial de acuerdo con la ecuación (3) y como puede verse en la
figura 3.2.
���� � ���� !�"#$��%&'�(� ) '*+�(���, (3)
Diego Barragán – Pablo Vallejo ([email protected])
Figura 3-2. (a) Imagen real, (b) Modelado aproximado.
Una vez obtenidos los datos de frecuencia y orientación, se filtra cada bloque en el
dominio de Fourier, se obtiene su Transformada Inversa y entonces se puede
reconstruir la imagen original a partir de los bloques realzados. (Figura 3.3)
Figura 3-3. Imagen Mejorada.
Diego Barragán – Pablo Vallejo ([email protected])
3.2. Binarización.
La imagen mejorada, resultante del proceso de realce, se encuentra en escala de
grises, es decir una imagen que contiene 8 bits por cada píxel, y con 256
posibilidades diferentes de tonos de gris.
El próximo paso consiste en transformar esta imagen a un formato binario, unos o
ceros, lo que va a permitir diferenciar claramente y procesar las crestas y los valles
en la imagen.
Para esta tarea, la mejor opción es la utilización de la función “im2bw”, que se
encuentra incluida en el toolbox de procesamiento de imágenes de Matlab. Esta
función convierte imágenes en color o escala de grises en imágenes binarias,
basándose en un determinado umbral, el cual se calcula con la función “graytresh”,
que devuelve el valor del umbral más adecuado para una imagen determinada y
que puede ser usado como parámetro de entrada en la función “im2bw”.
Dado que la imagen de una huella digital no es estática, es decir los valores de gris
varían considerablemente a través de la misma, la forma más eficiente de realizar la
transformación es dividiendo la imagen en bloques, y para cada uno de estos,
calcular el umbral de conversión.
Existen algunas alternativas para realizar este procesamiento, una de las más
comunes es realizar un ciclo repetitivo o condicional, “for”, “while” o “if”, aunque
Matlab provee en su toolbox de procesamiento de imágenes, una herramienta más
adecuada para este trabajo. Se trata de la función “blkproc”, que se encarga de
aplicar a cada bloque de la imagen de entrada, uno o varios procesos programados.
Para nuestro caso se aplicarán las funciones “graytresh” e “im2bw” a cada bloque
de 32 por 32 pixeles.
El resultado final del proceso de Binarización se puede apreciar en la figura 3.4.
Diego Barragán – Pablo Vallejo ([email protected])
3.3. Área de Interés.
En el procesamiento de la huella es importante determinar el área de interés, o lo
que es lo mismo, la región donde está la información para de este modo los
posteriores procesamientos se realicen solo dentro de esta área y economizar
procesos.
Para determinar el área de interés, se realiza el siguiente procedimiento presentado
en [3] y [5]:
1. Dividir la huella en bloques de w x w. Se usó un bloque de 16. La función de
Matlab para este punto es nuevamente “blkproc”, que se encarga de
aplicar a cada bloque de la imagen de entrada, uno o varios procesos
programados
2. Calcular el gradiente ( ),x i j∂ y ( ),y i j∂ de cada bloque. Para este trabajo
se usó el operador de Sobel, dado por la función “fspecial('sobel')”. Sin
embargo, otra alternativa pude ser usar la función “gradient”.
3. Estimar la orientación de cada bloque centrada en el píxel (i,j) usando las
siguientes ecuaciones:
( ) ( ) ( )
( ) ( ) ( )( )
( )( )( )
2 2
2 2
2 22 2
2 2
1
, 2 , , (4)
, , , (5)
,1, tan (6)
2 ,
w wi j
x x yw w
u i u j
w wi j
y x yw w
u i u j
y
x
V i j u v u v
V i j u v u v
V i ji j
V i jθ
+ +
= − = −
+ +
= − = −
−
= ∂ ∂
= ∂ − ∂
=
∑ ∑
∑ ∑
Donde θ(i,j) es la estimación del mínimo cuadrado de la orientación de la
cresta en cada bloque centrado en el píxel (i,j). Matemáticamente, esto
representa la dirección que es ortogonal con la dirección dominante del
espectro de Fourier de la ventana de w x w.
Diego Barragán – Pablo Vallejo ([email protected])
Para el cálculo del gradiente se usó la función “filter2”, la cual es un filtro
FIR de dos dimensiones, que realiza el cálculo del gradiente usando la
correlación.
4. Luego de estimar el campo de orientación de la huella, se determina la
región de interés en base a un nivel de confiabilidad de la orientación. La
definición de este nivel de confiabilidad se define como:
( )( ) ( )( )
( )
2 2, ,1
,,
x y
e
V i j V i ji j
wxw V i jε
+=
(7)
( ) ( )( )2 2
2 2
2 2
, ,
w wi j
e x yw w
u i u j
V u v u v
+ +
= − = −
= ∂ + ∂∑ ∑(8)
Para cada bloque, si el nivel de confiabilidad está por debajo de un umbral (en este
caso 0.05), se deduce que todos los píxeles de ese bloque pertenecen al fondo y no
a la huella. La figura 3.5 muestra el campo de orientaciones antes y después de
determinar el nivel de confiabilidad.
Figura 3-5. Campo de orientaciones antes y después de aplicar el nivel de confiabilidad.
5. Se crea una matriz de ceros (usando la función “zeros”) cuya dimensión son
los múltiplos de 16 de la imagen. Por ejemplo, una imagen cuyas
dimensiones son 156 píxeles de ancho por 230 píxeles de alto, producirá
Diego Barragán – Pablo Vallejo ([email protected])
una matriz de 15 filas (ceil (alto/16)) por 10 columnas (ceil (ancho/16)). Cada
elemento de esta matriz es un identificador de bloque de la imagen de la
huella. Si la orientación pasó el umbral del nivel de confiabilidad, ese
identificador se establece en 1, con lo cual se delimita el área de interés.
6. El área de interés dada por el campo de orientación deber ser procesada
usando una operación morfológica con el fin de eliminar cavidades en la
misma. La función de Matlab “bwmorph” con el parámetro open puede
expandir la imagen y quitar picos introducidos por el ruido de fondo. Con el
parámetro close encoge la imagen y eliminar cavidades pequeñas.(Figura
3-6)
Figura 3-6. Área de interés luego de aplicar “bwmorph”.
Diego Barragán – Pablo Vallejo ([email protected])
3.4. Adelgazamiento.
Adelgazamiento es el proceso por el cual, las crestas en la imagen, que se
representan mediante unos binarios, son reducidas en espesor, para de esta
manera obtener una imagen en la que todas las crestas tengan solamente 1 pixel
de ancho, lo que va a facilitar el posterior proceso de extracción de puntos
características.
Se emplearán operaciones morfológicas sobre las imágenes, en este caso se
utilizará la función “bwmorph”, la cual comprende algunos tipos de operaciones
morfológicas de las cuales usaremos adelgazamiento “thin”, “clean” y “spur”.
La operación “thin” va a realizar el adelgazamiento repetidas veces, hasta que la
imagen deje de cambiar, esto ocurrirá cuando las crestas tengan solamente un pixel
de ancho como se muestra en la Figura 3.7.
Las operaciones “clean” y “spur” van a remover los pixeles aislados que
generalmente son producto del ruido de la imagen.
Figura 3-7. Imagen Adelgazada.
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 4. IDENTIFICACIÓN DE MINUCIAS
4.1. Introducción
Una vez obtenida la imagen “esqueleto” de la huella digital, todas las crestas
tienen un espesor de un pixel, lo que permite realizar una búsqueda de las minucias,
bifurcaciones y terminaciones.
Para esta tarea se emplearán también algunas operaciones morfológicas, incluídas
en el toolbox de procesamiento de imágenes de Matlab.
4.2. Mapa de Crestas.
El primer paso es identificar todas las crestas presentes en la imagen, para ello se
utilizó la función “bwlabel”, que identifica y etiqueta todos los elementos
conectados en una imagen binaria. El resultado de esta función se puede observar
en la Figura 4.1, donde cada cresta es etiquetada con un número diferente, es decir
cada uno de los elementos conectados es representado con un color distinto.
Figura 4-1. Mapa de Crestas.
Diego Barragán – Pablo Vallejo ([email protected])
La función “bwlabel”, devuelve además el número total de elementos conectados,
es decir el número total de crestas.
4.3. Identificación de Minucias
Para la identificación de minucias, se empleará el algoritmo propuesto en varias
referencias conocido como “Crossing Number”. Este algoritmo consiste en tomar
ventanas de la imagen de 3 por 3 pixeles, y sobre éstas aplicar la siguiente
ecuación [5]:
%+�-� �
�. /-0!123!4 � -0��/
405� (9)
Donde p es el valor de cada pixel adyacente al pixel central de la ventana.
Dependiendo del resultado de esta ecuación, el pixel central de la ventana puede
ser identificado como terminación, bifurcación o cresta continua. [1]
Valor de CN Minucia
1 Terminación
2 Cresta Continua
3 Bifurcación
Para ilustrar este algoritmo se tiene algunos ejemplos en las figuras 4.2, 4.3. y 4.4.
Diego Barragán – Pablo Vallejo ([email protected])
Figura 4-2. Cresta Continua.
Esta matriz de tres por tres, usando la función “sum” que suma los elementos de
cada columna, con lo cual se calcula el crossing number. En la Figura 4.3.1 se tiene
una cresta continua, al aplicar la fórmula del crossing number, se obtiene el valor de
dos.
Figura 4-3. Terminación.
Diego Barragán – Pablo Vallejo ([email protected])
En la Figura 4.3.2 se tiene una terminación, al aplicar la fórmula del crossing
number, se obtiene el valor de uno.
Figura 4-4. Bifurcación.
Finalmente en la Figura 4.3.3 se tiene una bifurcación, al aplicar la fórmula del
crossing number, se obtiene el valor de tres.
Debido a la presencia de ruido en la huella se marcan minutas en estos sectores, y
es necesario un paso posterior para remover estas minutas espurias. Simplemente
hay que calcular la distancia euclidiana entre cada supuesta minuta y todas las
demás. Si esta distancia es menor a la distancia entre crestas, ambas minutas son
removidas. La ecuación de la distancia euclidiana se muestra a continuación:
( ) ( )2 2
1 2 1 2d x x y y= − + −
(10)
Para determinar la distancia entre crestas, se realiza un muestreo en toda la huella.
Este muestreo toma filas de la matriz, suma todos los píxeles de la fila cuyo valor
sea 1 y luego se divide la longitud de la fila para el resultado de la suma. Se
promedia el valor con los resultados de las otras filas.
Diego Barragán – Pablo Vallejo ([email protected])
La Figura 4-5 muestra la longitud de la distancia entre crestas. El cálculo arrojó el
valor de 9, que es cercano a la aproximación hecha en la huella (7.85 píxeles) con
la función “imdistline”, que mide distancias en píxeles en una imagen [2].
Figura 4-5. Ancho Entre Crestas.
Al identificar un pixel como terminación o bifurcación, resulta relativamente simple
almacenar las coordenadas de estos puntos así como las respectivas orientaciones
y marcarlos en la imagen original, Figura 4.6.
Para obtener la orientación de cada minucia, de coordenadas (mx, my), se toma un
segmento de la cresta, con una longitud igual al ancho inter crestas, con el origen
en la minucia. Luego se suman las coordenadas de todos los puntos del segmento,
tanto en x como en y, estas sumatorias son divididas por el valor del ancho inter
crestas (sx, sy), y el ángulo de orientación es igual a:
( 678�9 �:��;��
�:��;�� (11)
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 5. ALGORITMO DE EMPATE.
El algoritmo de empate es el encargado de calcular la semejanza entre dos
huellas. El algoritmo de empate por minucias es el más conocido y ampliamente
usado para reconocimiento de huellas digitales [3].
Para este apartado, se eligió el algoritmo que se basa en alineación de la huella de
entrada con la plantilla de la base de datos. Este algoritmo divide esta etapa en dos
pasos: (i) Etapa de alineación y (ii) etapa de empate.
5.1. Etapa de Alineación.
Con respecto a la etapa de alineación, el primer paso es tomar puntos de la
cresta asociada a la minucia (durante la extracción de la minucia, la cresta donde
reside la minucia también es almacenada y el origen de la misma coincide con la
coordenada de la minucia). Los puntos se toman a una distancia igual al ancho
entre crestas (distancia en píxeles entre una cresta y otra).
Empatando las crestas, se obtiene un umbral que de superar el valor de 0.8, da una
primera estimación de semejanza. Definiendo Rd y RD es el conjunto de crestas
asociadas con las minucias de entrada y de la plantilla, respectivamente. La
ecuación de empate se describe como sigue [3]:
0
2 2
0
L
i i
i
L
i i
i
d D
S
d D
=
=
=∑
∑ (12)
L denota el ancho entre crestas y d∈ Rd y D ∈ RD. Cuando S (0≤S≤1) es mayor a
0.8, se continúa con el empate minucia a minucia, caso contrario, se pasa a la
siguiente huella.
Diego Barragán – Pablo Vallejo ([email protected])
Si S es mayor a 0.8, se realiza la rotación de las minucias con respecto a una
minucia de referencia (x,y,θ)d:
cos sin 0
sin cos 0 *
0 0 1
A d
i i
A d
i i
A d
i i
x x x
y y y
θ θθ θ
θ θ θ
− = − − − (13)
5.2. Etapa de Empate.
La etapa de empate, ante todo, debe poseer cierto grado de flexibilidad dado que
es prácticamente imposible tener datos que empaten de manera perfecta.
Para esto, se emplean ventanas de veinte por veinte pixeles, rango dentro del cual
puede variar la ubicación de la minucia. Del mismo modo, se acepta un grado de
tolerancia de un tercio de pi para el valor de la orientación.
Para las minucias que se encuentren dentro de estos valores de tolerancia, son
empatadas como minucias coincidentes, caso contrario se continúa con la siguiente
minucia.
El porcentaje de empate es igual al número total de minucias coincidentes, para el
número total de minucias en la plantilla de comparación.
<!��!=>-?@� !ABC
ADB� 9EE (14)
NME: Número de minucias empatadas
NTM: Número de minucias totales
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 6. MANEJO DE BASE DE DATOS.
Para almacenar los tanto los datos del ciudadano, la imagen de la huella y
los resultados del procesamiento, se destinan tres carpetas. La primera contiene un
archivo txt con los datos del ciudadano (nombre, dirección, cédula de ciudadanía,
etc.), el segundo contiene un archivo ASCII con las coordenadas de cada minuta en
la huella y el mapa de crestas y una tercera almacena la huella.
Para almacenar los datos de la huella, se usa la función “save”, y para leerlos se
usa la función “load” [2]. Debido a que la lectura de las huellas (archivo .dat) se
realiza en otra carpeta, se añade las funciones de este programa al “path” de
Matlab para evitar problemas de dirección.
Con la ayuda de la función “dir”, se realiza el empate de la huella de entrada con
todas las plantillas almacenada.
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 7. Resultados.
Para las pruebas experimentales, se obtuvieron impresiones de huellas digitales
reales, las cuales fueron digitalizadas por medio de un escáner, con una resolución
de trescientos puntos por pulgada. Las imágenes fueron almacenadas en formato
TIFF, empleando compresión LWZ en la imagen y compresión RLE para las capas.
(Figura 7-1).
Figura 7-1. Opciones de almacenamiento TIFF
Dentro del GUI del programa, se tienen dos opciones, la primera es Ingresar
Nueva Huella, esta opción procesa la imagen y almacena las coordenadas de la
minucias y su respectiva orientación dentro de un archivo de texto con extensión
*.dat. Los resultados del ingreso de una nueva huella se muestran en las Figuras 7-
2 y 7-3.
Diego Barragán – Pablo Vallejo ([email protected])
Figura 7-2. Interfaz Gráfica del Programa
Figura 7-3. Archivo DAT generado.
Diego Barragán – Pablo Vallejo ([email protected])
En la Figura 7-3 se aprecia el contenido del archivo DAT generado por el programa,
donde las columnas corresponden a las coordenadas X, Y con la orientación de
cada una de las minucias.
La segunda opción del GUI permite ingresar una huella desconocida y compararla
con cada una de las huellas ingresadas previamente, y presenta como resultado la
etiqueta de la huella que más se asemeja a la ingresada. (Figura 7-4).
Figura 7-4. Resultados de Búsqueda de Huella Desconocida.
Diego Barragán – Pablo Vallejo ([email protected])
7.1. Rendimiento y Eficiencia.
7.1.1. Rendimiento
El rendimiento del sistema está en relación directa con las características del
computador donde se ejecuta el programa. Para estas pruebas, se usó un PC
portátil cuyas características se detallan a continuación (Figura 7-5):
Figura 7-5. Características Técnicas del Computador
Para medir el tiempo de cómputo de un programa se usa las funciones “tic” y “toc”
las cuales miden el rendimiento usando el cronómetro de un timer [2]. “Tic” toma el
valor actual de tiempo y “toc” retorna entre el tiempo transcurrido. Mathworks
recomienda hacer de tres a cuatro mediciones para obtener un valor estable y real.
Los resultados de se muestran a continuación:
Figura 7-6. Resultado funciones tic – toc para almacenamiento
Diego Barragán – Pablo Vallejo ([email protected])
Para calcular el rendimiento del empate entre las minucias, se usan las mismas
funciones “tic” y “toc”. Sin embargo, el resultado de tiempo se divide para el
número total de huellas en la base de datos.
Figura 7-7. Resultado funciones tic – toc para empate.
De esta manera, el tiempo en comparar las minucias de una huella con otra es:
F �G�H�
�I EG9J!'�KL+�&' (15)
7.1.2. Eficiencia
Con propósitos de prueba fue ingresado un número total de catorce imágenes
obteniendo empates correctos en doce casos. En base a estas pruebas
experimentales se puede afirmar que la eficiencia del sistema es igual a:
<=MM&M�' !N!3O!OPP2PO:
N;2;QR!3O!SPTOUQ:� 9EE!!!!!!!!!(16)
<=MM&M�' !�
�I� 9EE 9V�"< (17)
Diego Barragán – Pablo Vallejo ([email protected])
Capitulo 8. Conclusiones y Recomendaciones.
• En base a los resultados obtenido en la sección 7.1.2. podemos concluir que
aunque no se obtenga una precisión del cien por ciento en las etapas de
identificación de minucias y empate de huellas, si se puede conseguir
identificar las imágenes que presenten mayor porcentaje de similitud, con
una eficiencia aproximada del ochenta y cinco por ciento.
• Debido a que el adelgazamiento de la huella no es a un pixel exacto, en el
sector de las bifurcaciones ciertas minucias de bifurcación se eliminan
debido a que cerca de ellas se marca una terminación cuya distancia es
menor al área inter crestas.
• En base a las pruebas, si una huella posee pocas minucias (menos de 6), la
imagen de entrada tiene alto porcentaje de empate con aquella huella
debido a que el número de minucias empatadas es cercano al número total
de minucias.
• Se consiguió plasmar en un programa computacional, toda una base teórica
que envuelve el reconocimiento de huellas digitales, consiguiendo una
aplicación de buena precisión, y bajo coste computacional.
• Las aplicaciones del presente proyecto son muy variadas, empezando por la
automatización de sistemas de control de acceso, hasta llegar a la
investigación forense. Con pequeñas modificaciones, tales como un sistema
de Login, o un preciso sistema de adquisición de huellas, este trabajo se
puede convertir en una poderosa herramienta de investigación de delitos,
para instituciones como la Policía Judicial Nacional.
• Como trabajos futuros, se cree conveniente, la implementación del manejo
de una base de datos más completa, empleando programación
especializada como SQL, ORACLE, etc. Los datos a almacenar en esta
base de datos corresponden a dos matrices: Coordenadas y orientaciones
de minucias junto a su mapa de crestas.
Diego Barragán – Pablo Vallejo ([email protected])
Referencias.
[1]. Maltoni, Maiao. “Handbook of fingerprint recognition”, 2003.
[2]. Gonzalez, Word, Eddins. Digital Image Processign Using Matlab, 2002, 2nd
Edition.
[3]. Lin Hong. "Automatic Personal Identification Using Fingerprints", Ph.D.
Thesis, 1998.
[4]. Fingerprint Verification Competition, FVC2002.
http://bias.csr.unibo.it/fvc2002/.
[5]. Thai Raymond, “Fingerprint Image Enhancement and Minutiae Extraction”,
University of Western Australia, 2003.
[6]. Chikkerur Sharat S, Cartwright Alexander, “Fingerprint Image Enhancement
using STFT”, University of Buffalo, NY. 2003.
[7]. SFINGE (Sintetic Fingerprint Generator), Biometric System Laboratory,
University of Bologna, Italy.
http://biolab.csr.unibo.it/home.asp.