TESIS PUCP Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No comercial-Compartir bajo la misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/pe/ 1 PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA MEJORA DE IMÁGENES DE HUELLAS DIGITALES Tesis para optar el Título de Ingeniero Electrónico, que presenta el bachiller: Alfredo Ortiz Lozada ASESOR: Andrés Flores Lima, febrero del 2010 2 Resumen: El presente trabajo de investigación tiene por objetivo mejorar la calidad de la imagen de una huella digital, ya que no siempre obtenemos una imagen nítida. Con frecuencia se observan imágenes de huellas digitales borrosas, lo cual hace que sea difícil identificar la huella. Esta tesis está dividida en cuatro capítulos. El primer capítulo está enfocado hacia el estudio de la biometría y en especial de las huellas digitales, la problemática de las imágenes borrosas de huellas digitales y una posible solución para mejorar este problema. En el segundo capítulo se describe el procedimiento que se sigue para realzar la imagen de una huella digital. Este procedimiento se divide en varias etapas como son la etapa de orientación, la etapa de frecuencia y la etapa de filtrado. El tercer capítulo está enfocado hacia la implementación del algoritmo descrito en el capítulo anterior usando el entorno de simulación en matlab y se muestran imágenes que resultan de cada etapa del algoritmo. El cuarto capítulo, último capítulo de esta tesis, está enfocado a justificar la validez de este algoritmo con pruebas de realce que se han hecho con diferentes tipos de huella. Con las pruebas hechas en el último capítulo se concluye que efectivamente las imágenes de las huellas al ser realzadas, mejoran su calidad, ya que es posible encontrar más minucias en las imágenes de las huellas mejoradas que en las imágenes originales. 3 4 5 Índice: Introducción……………………………………..……………….……………....7 1. Imágenes borrosas en huellas digitales……………..………...……..9 1.1 La Biometría y los Sistemas Biométricos……………...……...9 1.2 Diferentes Tipos De Huellas Digitales………………..………12 2. Desarrollo de un programa que mejore la imagen de una huella digital y funcione correctamente……………………………………..14 2.1 Realce De Huellas…………………………………….………….14 2.2 Diagrama de Bloques del proceso de mejora de imágenes…18 2.2.1 Normalización………………………………….……….....19 2.2.2 Estimación de la Orientación…………………….………20 2.2.3 Estimación de la Frecuencia………………..…………...24 2.2.4 Filtrado…………………………………………..………....29 2.2.4.1 Filtro Gabor………………………….………………....34 3. Empleo del Matlab en el Desarrollo del Programa………………...36 3.1 Etapa de orientación……………………………………………..36 3.2 Etapa del cálculo de la frecuencia……………………………...37 3.3 Etapa de filtrado…………………………………………………..38 3.4 Mejoras posteriores……………………………………………....39 4. Pruebas y Resultados del programa………………………………...41 4.1 Detección de minucias………………………………………….. 41 4.1.1 Tipos de minucias importantes…………………… …….41 4.2 Comparación…………………………………………….…..…...42 Conclusiones …………………………………………..……….……….…...46 Recomendaciones………………………………………………………..….47 Bibliografía……………………………………………………….…....….…..48 6 Agradecimientos Me gustaría agradecer a mi asesor, el Ing. Andrés Flores, por sus útiles sugerencias y comentarios. También quiero agradecer al Ing. Pedro Crisóstomo y al Ing. Julio Manco por sus propuestas, ayudas y consejos brindados. Y también agradecer a mis padres por estimularme en el desarrollo de este trabajo. 7 Introducción: Este trabajo de investigación está basado en el realce de imágenes de huellas digitales y tiene como objetivo desarrollar un programa que sirva para mejorar la calidad de la imagen de una huella digital, es decir, para hacerla más nítida e identificable, para lo cual se cuenta con algoritmos matemáticos complejos, debido a la forma y la característica que tiene una huella digital. Actualmente se usan dispositivos que reconocen huellas digitales como son los sensores ópticos, capacitivos o de alta frecuencia, y son empleados en el acceso a los cajeros automáticos mostrando sólo la huella del índice, o para entrar a una oficina sin uso de llaves, siendo las imágenes de las huellas previamente realzadas para ser identificadas de una manera más acertada. Usos en el futuro: Se usarán huellas digitales en lugar de tarjetas de crédito. En Japón se eliminarán las tarjetas de crédito, las billeteras y los códigos secretos: pronto podrán hacer sus compras con una simple huella digital, gracias a la floreciente tecnología biométrica [5]. Desde setiembre del 2006, empleados del grupo japonés Hitachi están probando un nuevo sistema en el que ya no son necesarias las tarjetas, las monedas o los billetes y que cuenta con la colaboración de varios comercios y de la sociedad de crédito JCB. Al pasar por caja, los empleados especifican que desean pagar a través de su cuenta, por lo que deberán pasar un dedo sobre un lector que captará la imagen del sistema vascular a través de un rayo luminoso, sin contacto directo. Según Hitachi, como la estructura de los vasos capilares del dedo es única y no se modifica con el tiempo, es imposible reproducirla artificialmente. 8 Los datos biométricos del comprador, transmitidos por vía informática, serán comparados en el acto con el registro de JCB y las referencias bancarias del cliente. Al igual que para una compra tradicional pagada con tarjeta de crédito, el monto se deducirá automáticamente al final de mes de la cuenta corriente. En caso de que la huella digital no corresponda con los datos de la entidad, la transacción se denegará. El experimento, el primero de este tipo en Japón, tiene por objetivo elaborar un modelo técnico y económico. La biometría es un sistema muy extendido en el Japón, en particular en las empresas y hospitales que se sirven para los controles de acceso o las conexiones de red [5]. En efecto la biometría es lo que se empleará en el futuro para identificar a un individuo a través de medidas físicas o comportamientos. Como métodos biométricos, se emplearán el reconocimiento de huellas digitales, reconocimiento de la retina o del iris, de la escritura del individuo, de la forma de su mano o de su dentadura, de su voz o su cara, todo esto al digitalizarse tendrá un único código para cada individuo. 9 Capítulo 1: Imágenes Borrosas En Huellas Digitales 1.1 La Biometría y los Sistemas Biométricos: La biometría es el estudio de métodos automáticos para el reconocimiento único de humanos basados en uno o más rasgos conductuales o físicos intrínsecos. Etimológicamente la palabra biometría proviene de dos palabras: bio que significa vida y metría que significa medida, lo cual da a entender que todo artefacto biométrico mide y luego identifica alguna característica intrínseca de la persona [2]. La tecnología biométrica, mediante la verificación de la identidad de los empleados, contribuye a la creación de entornos laborales más seguros como parte del proceso de recopilación de datos. Pese a la generalizada aceptación de los beneficios de la biometría, es posible que algunos empleados manifiesten preocupación por la privacidad asociada a esta tecnología. La "biometría informática" es la aplicación de técnicas matemáticas y estadísticas sobre los rasgos físicos o de conducta de un individuo, para “verificar” identidades o para “identificar” individuos. En las tecnologías de la información (TI), la autentificación biométrica se refiere a las tecnologías para medir y analizar las características físicas y del comportamiento humano con el propósito de autentificación. Las huellas dactilares, las retinas, el iris, los patrones faciales, de venas de la mano o la geometría de la palma de la mano, representan ejemplos de características físicas (estáticas), mientras que entre los ejemplos de características del comportamiento se incluye la firma, el paso y el tecleo (dinámicas). La voz se considera una mezcla de características físicas y del 10 comportamiento, pero todos los rasgos biométricos comparten aspectos físicos y del comportamiento. Figura 1: La figura muestra algunas formas de biometría como son: a) la oreja; b) la cara; c) el termograma facial; d) el termograma de la mano; e) vena de la mano; f) geometría de la mano; g) huella digital; h) iris; i) retina; j) firma; k) señal de voz [1]. El siguiente cuadro muestra la confiabilidad en el análisis biométrico de algunas de las formas mostradas en la figura: Tabla 1: Fiabilidad y uso de algunas formas de biometría [1]. Huellas digitales Firma o escritura Voz Iris Retina Cara Voz Fiabilidad Alta Alta Alta Muy alta Muy alta Alta Alta Facilidad de uso Alta Alta Alta Media Baja Alta Alta Prevención de ataques Alta Media Media Muy alta Muy alta Media Media Aceptación Media Muy alta Alta Media Media Muy alta Muy alta Estabilidad Alta Media Media Alta Alta Media Media 11 Un sistema biométrico es un sistema de reconocimiento de patrones, identificando de esta forma a un individuo por sus características fisiológicas o por su comportamiento. Un sistema de verificación compara las características biométricas de un individuo con su propia característica biométrica y su plantilla biométrica almacenada previamente en el sistema. Esto se compara uno a uno para verificar si la identidad del individuo es verdadera, en cambio el sistema de identificación reconoce a un individuo buscando entre todas las plantillas o huellas almacenadas la mejor coincidencia. Esto funciona de tal manera que compara una huella insertada en el sistema con muchas huellas almacenadas previamente en la base de datos y de esa forma se establece la identidad del individuo. El sistema de reconocimiento de huellas digitales, es el sistema que más ha sido usado como medio de identificación en los últimos años. La imagen de la huella digital casi siempre presenta degradaciones, a causa de las variaciones en la piel y a condiciones de impresión, es necesario aplicar técnicas de mejora de imagen, para así obtener la extracción de minucias. En las siguientes secciones se presentan las técnicas en la mejora de imagen y la extracción de minucias. Este sistema ha sido implementado en organizaciones para la identificación y muy comúnmente usado en el área de criminología. La huella digital es una característica física, única que nos distingue a los seres humanos, la cual está formada por un patrón de crestas y valles. Las cresta son segmentos de curvas de la huella dactilar y los valles se encuentran en medio de las crestas. 12 1.2 Diferentes tipos de las huellas digitales: Podemos encontrar diferentes tipos de huellas digitales. Pero lo que más resalta son los caminos que siguen las líneas de las crestas. Los flujos se dividen en tres grupos principales: arco, lazo y carpa, los cuales se subdividen en grupos más pequeños como son el arco, arco tendido, lazo izquierdo, lazo derecho, carpa y carpa con lazo gemelo, tal como lo muestra la figura 3. Figura 3: Diferentes tipos de huellas digitales: Primera fila: de izquierda a derecha: a) Arco; b) Arco tendido; c) Lazo izquierdo; Segunda fila: De izquierda a derecha: d) Lazo derecho; e) Carpa; f) Carpa con doble lazo [1]. También se pueden encontrar puntos resaltantes como un núcleo o un delta, con líneas de cresta alrededor de estos. Un núcleo está definido como el punto en la cima de la curva más interna y está presente cuando hay al menos una cresta que entra a un lado y luego dicha curva regresa al mismo lado. Un delta tiene forma triangular y es definido como el punto donde las crestas divergen y es más cercana al núcleo. 13 Figura 4: Se muestra un núcleo y un delta en una huella [2]. Delta Núcleo 14 Capítulo 2: Desarrollo de un programa que mejore la imagen de una huella digital y que funcione correctamente 2.1 Realce de Huellas: La huella está conformada por crestas y valles. Las crestas varían en ancho de 100 µm a 300 µm. Ese patrón por lo general corre en paralelo y algunas veces se bifurcan o terminan, dando lugar a las minucias. Las heridas o quemaduras o cortes pueden afectar algunas regiones de la huella, pero las minucias se mantienen. Las imágenes de las huellas contienen un rango limitado de frecuencias especiales, además cada píxel tiene asociado una orientación dominante y una medida local de coherencia del patrón flujo. La resolución más usada comercialmente es la de 500 puntos por pulgada o en inglés dots per inch (dpi), ya que al utilizar menos resolución como 250 o 300 puntos por pulgada se pierden datos de la huella [2]. Si se utiliza más resolución como 1000 puntos por pulgada es posible identificar más características de la huella como los “poros sudorosos”, lo cual ayuda a identificar con mayor precisión la huella. Figura 5: Se muestran huellas a diferentes resoluciones como son 500 puntos por pulgada, 400, 300 y 250 [1]. 15 Las huellas con las que se ha probado el algoritmo usado en este proyecto son de 500 puntos por pulgada en promedio. La imagen de una huella puede ser representada por un arreglo bidimensional, el cual muestra la imagen de la huella en escala de grises, siendo el nivel de gris en el píxel (x, y). Figura 6: Superficie de una huella [7]. La performance de los algoritmos de extracción de minucias de otras técnicas de reconocimiento depende de la calidad de la entrada de las imágenes de las huellas digitales. En una imagen ideal de una huella digital, crestas y valles alternan y fluyen en una dirección local constante. En líneas generales hay varios tipos de degradación asociados con huellas digitales: a) Las crestas no son estrictamente continuas, las crestas tienen pequeñas rupturas. 16 b) Las crestas paralelas no están bien separadas. Esto es debido a la presencia de ruido el cual une crestas paralelas resultando una pobre separación. c) Cortes, manchas o pliegues. Estos tres tipos de degradación hacen que la extracción de crestas sea extremadamente dificultosa en las regiones altamente corrompidas. Esto conduce a diferentes problemas en la extracción de minucias: i) Un significativo número de minucias espuria son extraídas; ii) Un gran número de minucias se pierden y iii) Se adjuntan grandes errores en la localización (posición y orientación) de minucias. Para estar seguros de la correcta extracción de minucias en pobre calidad de imágenes de huellas digitales es necesario un algoritmo para mejorar la claridad de las estructuras de las crestas. (a) (b) (c) Figura 7: En esta figura se pueden apreciar diferentes calidades en las imágenes de las huellas digitales: a) buena calidad de huella digital; b) mediana calidad de huella digital caracterizada por raspaduras y crestas rotas; c) muy mala calidad de huella digital conteniendo mucho ruido [1]. 17 Un experto de huellas frecuentemente es capaz de identificar correctamente las minucias usando varias claves visuales tales como orientación de cresta local, continuidad de cresta, tendencia de cresta, etc. En teoría es posible un algoritmo de mejora que explote esas claves visuales para mejorar la calidad de las imágenes. Generalmente, para una determinada huella digital, las áreas de huellas que resultan de una segmentación pueden ser dividas en tres categorías: a) Región bien definida: donde las crestas están claramente diferenciadas de las otras. b) Región recuperable: donde las crestas son corrompidas por pequeñas cantidades de brechas, pliegues, manchas, enlaces, etc., pero aún así hay regiones visibles y las regiones vecinas proveen suficiente información de su verdadera estructura. c) Región no recuperable: donde las crestas son corrompidas por ruido y distorsión de tal manera que no hay crestas visibles y las regiones vecinas no permiten ser reconstruidas. Regiones de buena calidad, recuperables y no recuperables pueden ser identificadas de acuerdo a muchos criterios, en general contraste de imagen, consistencia de orientación, frecuencia de crestas y otras características locales pueden ser combinadas para definir el índice de calidad. El éxito de un algoritmo de mejora es aumentar la calidad de las estructuras de las crestas en regiones recuperables y señalar las regiones no recuperables o muy ruidosas para un futuro proceso. La entrada de un algoritmo de realce de imágenes es generalmente una imagen en escala de grises. La salida puede estar en escala de grises o en binario, dependiendo del algoritmo. El aumento del contraste, la manipulación del histograma, la normalización y el filtrado han contribuido eficazmente para un buen realce de la huella digital. [4] 18 Figura 8: Imagen de huella digital conteniendo regiones de diferente calidad: a) región bien definida; b) región recuperable; c) región no recuperable [1]. 2.2. Diagrama de bloques del proceso de mejora de imágenes: Huella de entrada Imagen realzada Figura 9: Diagrama de bloques A continuación tenemos la explicación de cada parte de este diagrama de bloques, como son la normalización, la orientación, la estimación de frecuencia y el filtrado que viene a ser lo más importante. Normalización Estimación de la orientación de la imagen y suavizado Estimación de la frecuencia Filtrado : Filtro Gabor 19 2.2.1 Normalización: En esta etapa se determina el nuevo valor de intensidad de cada píxel en la imagen tal como: Donde m y v son la media y la varianza de la imagen y mo y vo son la media y la varianza deseada después de la normalización. El proceso de normalización es una operación relacionada con los píxeles de la imagen. El valor depende sólo de un valor previo y otros parámetros globales y no cambia en las estructuras de crestas y valles. En particular este proceso no es capaz de rellenar pequeñas rupturas en las crestas para rellenar huecos, o separar crestas paralelas en contacto. El principal objetivo de la normalización es reducir las variaciones en los valores en la escala de grises alrededor de las crestas y valles de la imagen de la huella que facilite los pasos siguientes. Figura 10: Se muestra un ejemplo usando mo=100 y vo = 100 Tomada de [4]. (1) 20 2.2.2: Estimación de la orientación: Luego de la normalización el siguiente paso es la estimación de la orientación de las crestas locales. La orientación local implica la mayor tendencia de orientación de crestas en una vecindad local. Esto representa una propiedad intrínseca de la imagen de una huella digital y define una coordenada invariante para crestas y valles en una vecindad local. Siguiendo las crestas, la orientación de las crestas locales cambia lentamente. Además no hay diferencia entre una orientación local de crestas de 90º y de 270º , ya que las crestas locales orientadas a 90º no pueden diferenciarse de las crestas orientadas a 270º. Figura 11: Ejemplos de estimación de la orientación local de las crestas [4]. La orientación local de la cresta en (x, y) es el ángulo que la cresta forma con el eje horizontal, la cual es calculada en una localidad arbitraria centrada en el punto (x, y). Cuando hablamos de dirección, nos referimos a la dirección de un vector como está mostrado en la figura 12 (a) y cuando hablamos de orientación varía entre 0 y 180º como está descrito en la figura 12 (b) 21 (a) (b) Figura 12: La figura (a) muestra la dirección y la figura (b) muestra la orientación [2]. Se puede emplear una matriz cuyos elementos codifican la orientación local. Cada elemento de orientación corresponde a un nodo de una grilla cuadrada localizada sobre el píxel se calcula el promedio de las orientaciones de las crestas de una vecindad, y una medida de coherencia en las orientaciones, permitiendo localizar regiones afectadas por el ruido o regiones de alta curvatura como un núcleo o un delta [2]. El método más simple para la extracción de orientaciones locales está basado en determinar los gradientes en la huella. El gradiente en el punto de la imagen I es un vector bidimensional donde los componentes son las derivadas de la imagen I en con respecto a las direcciones x e y. El ángulo calculado como el arco tangente del cociente da la dirección del máximo cambio de intensidad del píxel . El método de Sobel o Prewitt (descrito en el libro “Digital Image Processing Using Matlab” de González y Woods) para determinar los componentes del gradiente y y el arcotangente del cociente presenta algunos errores debido a la discontinuidad alrededor de 90º y además presenta orientaciones a escala muy fina siendo susceptible al ruido. Ə Ə 22 Para evitar estos errores se sigue la técnica del suavizado, que consiste en promediar orientaciones, evitando de esta manera el ruido. Pero al promediar orientaciones tales como 135º y 45º llegamos a 90º. Para no tener más errores se emplea un método que consiste en duplicar los ángulos de modo que cada elemento es representado ahora por el vector: ( 2 ) representa la coherencia de flujo de orientación y es usado en vez de , y de este modo se evita tener errores. Luego se promedia en una ventana n x n y se obtiene una estimación más exacta. ( 3 ) En la figura 13 se muestra la imagen original de una huella digital, en la figura 13 b se muestran los vectores de orientación de la imagen de la huella sin el empleo de la técnica del suavizado, y en la figura 13 c se pueden apreciar los vectores de orientación de la imagen de la huella con el empleo de la técnica del suavizado. (a) (b) (c) Figura 13: En la figura (a) se muestra la imagen original, en (b) se muestran las orientaciones y en (c) las orientaciones calculadas a través de la ecuación (3) [1]. 23 Para encontrar la orientación de la imagen se emplea un método en la que se procesan las orientaciones dominantes de las crestas combinando varias estimaciones de gradientes dentro de una ventana 16 x 16 centrada en el píxel [2]. donde Donde y son las componentes de los gradientes obtenidos por máscaras de Sobel. Después de que se obtienen las orientaciones, se procede a suavizarlos utilizando un filtro gaussiano mediante las siguientes ecuaciones: Las componentes y son filtradas para después calcular nuevamente el ángulo: ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 10 ) 24 2.2.3. Estimación de frecuencia: Luego de la orientación local pasamos a la estimación local de la frecuencia. La frecuencia local de las crestas es el número de veces que aparecen las crestas y las estructuras de los valles en una vecindad local a lo largo de la dirección normal de la orientación local de las crestas. Las estructuras de las crestas y los valles de una huella, en la parte donde se forman minucias, nudos o deltas no forman una onda sinusoidal bien definida. En esas situaciones se toma la frecuencia promedio de la vecindad. La frecuencia local de la cresta representa otra propiedad intrínseca de la imagen de una huella digital. [2] La frecuencia de las crestas y los valles puede ser estimada a partir de una onda sinusoidal en un número promedio de píxeles entre dos picos consecutivos. En algunas partes de la imagen tal vez no se llegue a una buena estimación. No obstante las regiones difíciles de estimar o no recuperables pueden ser fácilmente compensadas usando la propiedad de variación baja de la frecuencia local. [2] Figura 17: Estimación de la frecuencia de cresta local [2]. 25 La frecuencia local f de las crestas en un punto (x, y) es la inversa del número de crestas por unidad de longitud a lo largo de un segmento referencial centrado en el punto (x,y) y ortogonal a la orientación de las crestas . Una imagen de frecuencia, es análoga a una matriz de orientación, que puede ser definida como si la frecuencia fuese estimada en posiciones discretas y arregladas en forma matricial. La frecuencia local de las crestas varía en diferentes regiones en una huella. Se estima la frecuencia de crestas locales en una huella contando el número de píxeles promedio entre dos picos consecutivos a lo largo de la dirección normal de la orientación local de las crestas. Para lograr esto, la superficie S correspondiente a la huella es seccionada con un plano paralelo al eje z y ortogonal a la orientación local de la cresta. La frecuencia fij en [xi , yj ] es calculada de la siguiente manera: En una vecindad local de una imagen de una huella donde no hay minucias, los niveles de gris pueden ser modelados como una onda de forma sinusoidal a lo largo de una dirección normal a la orientación local (ver fig. 17). Por lo tanto la frecuencia local es otra propiedad intrínseca de la imagen de una huella digital. Sea G la imagen normalizada y O la orientación de la imagen, luego los pasos para estimar la frecuencia local son los siguientes [4]: a) Se divide G en bloques de dimensiones ω x ω (16 x 16), ya que se ha observado en forma empírica que ese tamaño es el más pequeño en donde se puede ver un arco de la huella bien definido o una minucia. b) Para cada bloque centrado al píxel i, j se calcula una ventana de orientación de dimensiones l x ω (32 x 16) que es definida en el sistema coordenado de las crestas, según su ángulo de orientación (ver fig. 17). c) Para cada bloque centrado en el píxel (i,j) se calcula la siguiente suma: Donde k = 0,1……………..l -1 ( 11 ) 26 Si no hay minucias ni puntos singulares en la ventana orientada, la suma X (ecuación 11) forma una onda discreta de forma sinusoidal, la cual tiene la misma frecuencia de las crestas y los valles en la ventana orientada. [4] Por lo tanto la frecuencia de las crestas y los valles puede ser estimada de la suma X. Sea T(i,j) el promedio del número de píxeles entre dos picos consecutivos en la onda descrita por la suma X de la ecuación 11 (ver fig. 17), luego la frecuencia Ω (i,j) es calculada de la siguiente manera: Si los picos consecutivos no pueden ser detectados de la ecuación 11, se le asigna a la frecuencia un valor de -1, para diferenciarlo de los valores válidos de frecuencia. [4] Para una huella digital escaneada a una resolución arreglada, el valor de la frecuencia de las crestas y valles en una vecindad local está dentro de un rango determinado. Para una imagen de 500 puntos por pulgada, el rango es [1/50, 1/3], ya que empíricamente está demostrado que en ese intervalo se espera una imagen sin manchas. Por lo tanto si el valor de la frecuencia está fuera de ese rango, se le asigna a la frecuencia el valor de -1 para indicar que una frecuencia válida no puede ser obtenida. Para calcular la frecuencia de los bloques de 16 x 16 se aplica una función que centra la onda sinusoidal de la suma X y luego se aplica la transformada de Fourier para calcular el pico máximo de la señal. Se halla el período y ( 12 ) ( 13 ) ( 14 ) 27 posteriormente la frecuencia, que viene a ser la inversa multiplicativa del período Como mencionamos anteriormente un píxel o bloque en una imagen de una huella digital puede estar en una región recuperable o no recuperable. Para clasificar los píxeles en regiones recuperables o no recuperables se debe tener en cuenta forma de la onda formada por crestas y valles. En el algoritmo tres características son usadas para caracterizar la onda de forma sinusoidal [4]: a) La amplitud que es el promedio de las alturas de los picos o el promedio de la profundidad de los valles. b) La frecuencia es la inversa multiplicativa del período, donde el período es el promedio del número de píxeles entre dos picos consecutivos. c) La varianza, que se calcula de la siguiente manera. Sea X[1], X[2],….X[l] la suma X calculada en un bloque centrado a (i,j). La varianza es representada por la siguiente fórmula: En la práctica se usa la desviación estándar que es la raíz cuadrada de la varianza y después de probar varios valores en forma empírica se comprueba que con un valor de 3 o 4 la imagen puede mejorar su calidad. ( 15 ) 28 Figura 18: Superficie correspondiente a una pequeña área de una huella digital [1]. Figura 19: Ventana orientable en un patrón local [4]. 29 Figura 20: Ventana orientable en una sección de huella [8]. El método es simple y rápido, pero es difícil extraer picos consecutivos en el dominio del espacio de imágenes con ruido, por lo que es necesario usar filtros pasabajos e interpolación. Luego pasamos a la estimación de la máscara de la región en donde el objetivo es indicar la categoría del píxel. Un píxel puede ser de valle y cresta no recuperable o de valle y cresta recuperable. El número de regiones recuperables y no recuperables es calculado. Si el número de regiones no recuperables excede al de regiones recuperables la imagen es rechazada. 2.2.4. Filtrado: Finalmente pasamos al filtrado. Muchos tipos de filtros contextuales han sido propuestos para mejorar las imágenes de huellas digitales. Aunque los métodos son diferentes, el propósito es el mismo: tener un efecto de filtro pasa bajos a lo largo de la dirección de la cresta con el propósito de enlazar pequeñas rupturas y llenar impurezas debido a los poros o al ruido. Se ha definido un filtro basado en cuatro parámetros para imágenes de huellas a una resolución dada en donde se establece un mínimo y un máximo de espesor del valle. El filtro es en forma de campana como lo muestra figura 21, alargada alrededor de la dirección de la cresta y una forma de coseno en dirección normal a las crestas [1]. 30 La frecuencia de cresta local se asume constante y por lo tanto el contexto es definido sólo por la orientación local. Una vez que el filtro principal es generado se rota a 16 ángulos en pasos de 22.5º (22.5º x 16 = 360º). La mejora de la imagen es lograda al convolucionar cada punto de la imagen con el filtro en donde la orientación encaje de la mejor manera con la orientación local de la cresta. Dependiendo de algunos parámetros de entrada, la imagen de salida puede estar en escala de grises o en binario. Figura 21: La forma del filtro propuesto por O´ Gorman y Nickerson en 1989 [1]. La convolución circular o periódica en el dominio espacial corresponde a una multiplicación punto por punto en el dominio de Fourier. El filtro es definido en el dominio de la frecuencia por la función: donde Hradial depende sólo del espacio de cresta local y Hángulo depende sólo de la orientación θ de la cresta local. Tanto el filtro Hradial como el filtro Hángulo son definidos como filtros pasabanda y caracterizados por un valor de media y un ancho de banda. ( 16 ) ( 17 ) ( 18 ) Z= ( 19 ) 31 Donde y son la frecuencia central y el ancho de banda del filtro. La frecuencia es un parámetro para la propiedad de corte inferior, el cual suprime los efectos de frecuencias bajas causados por desigualdades en las huellas impresas; es el parámetro para la propiedad de corte superior, el cual suprime los efectos de ruido de alta frecuencia tal como huecos de glándulas sudoríparas y rasguños en las crestas. Z es el factor de normalización para la salida del filtro y es el factor que suprime los componentes de altas frecuencias relativas. C es una constante. Los factores Z y son necesarios para la selección del filtro [2]. El filtro angular o direccional es designado de la siguiente manera: Donde es la dirección del filtro pasabanda y es la dirección del parámetro del ancho de banda. (a) (b) (c) Figura 22: a) Multiplicación del filtro angular y radial ; b) Filtro radial; c) Filtro angular [2]. ( 20 ) 32 (d) (e) ( f ) Figura 23: Las figuras d, e y f son las transformadas inversas de Fourier de las imágenes mostradas en la Figura 23 en a) en b) y en c) respectivamente [2]. Dada una imagen original g(x,y) en el dominio del espacio, la operación de filtro es designada en el dominio 2D de Fourier bajo la siguiente ecuación: Donde g’ (x,y) es la imagen filtrada por el filtro H(u,v). F(.) y F-1(.) denotan las transformada directa de Fourier y la transformada inversa de Fourier respectivamente [2]. Un banco de n filtros discretos es derivado en consecuencia. En experimentos para reducir el número de filtros, sólo se usa un valor para la frecuencia de cresta local y en consecuencia el contexto es determinado sólo por la orientación. La transformada de Fourier Pi i=1,2,..,n de los filtros es calculada previamente y almacenada. El filtrado de una imagen I de entrada es procesado como se muestra en la figura 24: El procedimiento que describe la figura es el siguiente: a) Se calcula la transformada de Fourier F de la imagen I. b) Cada filtro Pi es multiplicado punto por punto por F, obteniendo n transformadas de la imagen filtrada PFi i= 1..n en el dominio de la frecuencia. c) Se calcula la inversa de la transformada de Fourier para cada PFi resultando n imágenes filtradas PIi i=1..n en el dominio del espacio. ( 21 ) 33 d) La imagen Imejorada es obtenida colocando para cada píxel [x,y], Imejorada [x,y] = PIk [x,y], donde k es el índice del filtro cuya orientación está cercana a Əxy [1] . Figura 24: Diagrama del realce de Sherlock [1]. PF1,PF2,…PFn son los espectros de las imágenes filtradas. En el esquema se asume que la frecuencia de las crestas es constante. La imagen filtrada es formada por cada píxel. El valor de cada píxel proviene de la imagen filtrada con la orientación más cercana a la calculada en la imagen original. Dicho proceso ocurre en la etapa del selector. Luego se umbraliza la imagen filtrada [1]. FFT x filtro PIn PFn I F PF1 PI1 FFT inversa PF2 PI2 Orientación de la cresta local Imejorada S E L E C T O R 34 2.2.4.1: Filtro Gabor: Los filtros Gabor se caracterizan por tener propiedades de frecuencia selectiva y orientación selectiva y tienen óptimos resoluciones tanto en el dominio de la frecuencia como en el dominio del espacio [4]. Un filtro Gabor es definido en el libro “Handbook of Fingerprint Recognition” de Davide Maltoni, como una onda en el plano sinusoidal. El filtro Gabor simétrico de dos dimensiones tiene la siguiente fórmula [1]: Donde Ө es la orientación del filtro y [xӨ,yӨ] son las coordenadas de [x,y] después de un giro horario de 90º - Ө de los ejes del plano cartesiano. Donde f es la frecuencia de la onda de plano sinusoidal, σx y σy son las desviaciones estándar de la función gausiana a lo largo del eje x e y respectivamente. Para aplicar filtros Gabor a una imagen, los cuatro parámetros (θ,f,σx,σy) deben ser especificados. La frecuencia del filtro está determinada completamente por la orientación de la cresta local. La selección de los valores de σx y σy tiene una desventaja. Mientras más grandes sean los valores, más robustos serán los filtros al ruido en la imagen de la huella digital, pero también serán más capaces de crear crestas espurias y valles. Por otro lado si los valores son pequeños, los filtros serán menos propensos de introducir crestas espurias y valles pero serán menos efectivos en remover el ruido. Al modular la función de transferencia del filtro Gabor se puede mostrar que al aumentar los valores ( 22 ) ( 23 ) 35 de σx y σy disminuye el ancho de banda del filtro y viceversa. Basados en un dato empírico se le puede dar un valor a σx = σy = 4. En el algoritmo de mejora de imágenes siempre se busca colocar los mejores valores para σx y σy según sea la huella. Pero más o menos están en un rango de 2,5 a 5. (a) (b) Figura 25: La figura (a) muestra la representación gráfica lateral del filtro Gabor y la figura (b) muestra la representación gráfica horizontal del mismo, ambos definidos por los parámetros θ=135º, f=1/5, σx = σy = 3 [1]. Para hacer una mejora rápida, en vez de calcular el filtro contextual para cada píxel un conjunto de filtros son previamente creados y almacenados, donde es el número de orientaciones discretas y es el número de frecuencias discretas . Luego cada píxel [x, y] de la imagen es convolucionado en el dominio del espacio, con el filtro tal que es la orientación discreta cercana a y es la frecuencia discreta cercana a . En la siguiente figura se ve un ejemplo del filtro donde n0 = 8 y nf = 3. Figura 26: Representación gráfica de los filtros Gabor de un banco de 24 ubicaciones donde n0=8 y nf=3 y además σx=σy=4 [1]. 36 Capitulo 3: Empleo del Matlab en el desarrollo del programa: Primero el programa lee la imagen original sin realce y la muestra en pantalla: Figura 27: Imagen mostrada por el programa después de leer la imagen. Luego empieza el realce el cual está dividido en las siguientes etapas: 3.1 Etapa de orientación: En esta etapa se calcula la orientación de la siguiente manera: - Se divide la imagen en bloques de 16 x 16 píxeles, ya que es la mínima área de la imagen es donde se espera ver un arco o minucia de la huella bien definida. - Se emplean las funciones de Sobel hy y hx que se van a usar para derivar, a través de un filtro. 37 - Se calcula el gradiente de cada bloque. - Con los valores del gradiente de x y de se calcula el ángulo de orientación de cada bloque. - Se utiliza un comando para mostrar las orientaciones, las cuales se ven como vectores de color azul (ver figura 28). Figura 28: Imagen mostrada por el programa después del cálculo de la orientación. 3.2 Etapa del cálculo de la frecuencia: Se toman bloques de 48 x 48 avanzando de 16 en 16, tanto en las filas como en las columnas. Se rota cada bloque de 48 x 48 al ángulo del bloque central de 16 x 16 obtenido en la etapa de orientación tomado exactamente en el centro de cada bloque de 16 x 16. Los bloques de 48 x 48 se recortan en bloques 32 x 16 y se suman las filas de cada bloque. 38 Luego se procede a encontrar la distancia pico de todas esas sumas. Para esto se usa la transformada de Fourier. Se encuentra el punto máximo, y luego se evalúa el primer máximo. De esta forma se calcula la frecuencia de cada bloque. 3.3 Etapa de filtrado: Con la frecuencia obtenida se pasa a la etapa de filtrado. Utilizamos el filtro Gabor. Se calcula la transformada de Fourier de un bloque de 16 x 16 de la imagen, el cual lo expandimos a 32 x 32, para mejorar la precisión y también se calcula la transformada de Fourier del filtro Gabor. Luego se pasa a calcular la transformada de Fourier inversa del producto del las transformadas calculadas anteriormente. Finalmente se reordena el vector, para tener la componente continua centrada. De esta forma ya se tiene la imagen mejorada. Figura 29: Imagen mostrada por el programa después de pasarle los filtros a la imagen y al concluir el realce. 39 Figura 30: Filtro Gabor aplicado a un bloque de la imagen. Figura 31: Transformada de Fourier del Filtro Gabor aplicado a un bloque de la imagen. 3.4 Mejoras posteriores: La imagen obtenida después de este proceso tiene un entorno de manchas, las cuales las eliminamos a través comandos del matlab que erosionan y dilatan la imagen. Se busca el área máxima de la imagen que viene a ser el área de la huella y se extrae. A través de la ecuación 40 de la recta se convierte la huella a escala de ceros y unos para posteriormente aplicar funciones de suma y multiplicación. Se determina el histograma acumulado de la huella y lo transformamos a un rango entre 0 y 255. Se hace un barrido de toda la imagen convirtiéndola al nuevo rango de histograma acumulado entre 0 y 255. Luego recortamos la imagen llenando el entorno de blanco y con esto obtenemos una imagen mejor en donde sólo se ve la huella sin manchas en su contorno. Figura 32: Imagen mostrada por el programa después de realizar las mejoras posteriores para retirar las manchas del contorno de la imagen. 41 Capítulo 4: Pruebas y Resultados del Programa: 4.1 Detección de minucias: Para medir la eficiencia del algoritmo se necesita determinar las características de las imágenes de las huellas digitales originales y las imágenes de las huellas digitales mejoradas con el algoritmo. Primero hay que recordar que la imagen de una huella digital tiene crestas y valles. Las regiones claras corresponden a las crestas, mientras que las regiones oscuras corresponden a los valles. La imagen de una huella digital presenta núcleos y deltas, lo cual fue explicado anteriormente. Estos vienen a ser las características de las huellas digitales, también llamadas minucias. La mayoría de los sistemas de comparación de huellas digitales están basados en la comparación de las minucias, por lo tanto la extracción de minucias es extremadamente importante. Se ha determinado la cantidad de minucias en la imagen de la huella original y en la imagen de la huella mejorada. En la imagen de la huella mejorada se han encontrado mayor cantidad de minucias que en la huella original, lo cual implica que hay una mejora en la imagen que permite ver a simple vista más minucias que en la huella original. Tipos de minucias importantes: a) La minucia tipo terminal: la cual es definida como el punto donde una cresta termina. b) La minucia tipo bifurcación: que consiste como el punto donde una cresta bifurca o diverge en otra u otras crestas. 42 Figura 33: En la figura se pueden apreciar los dos tipos de minucias: la minucia tipo terminal y la minucia tipo bifurcación [2]. 4.2 Comparación: Se hace una comparación entre las minucias halladas en las imágenes originales y las minucias halladas en las imágenes realzadas. En este trabajo de investigación la comparación se hizo con 53 imágenes en las cuales el tesista hizo un conteo de las minucias de las imágenes de las huellas originales, así como de las imágenes de las huellas realzadas. En las figuras siguientes se muestran las minucias de una huella digital antes de ser realzada y después de ser realzada. (a) (b) Figura 34: La figura (a) muestra la imagen antes de ser realzada con sus respectivas minucias y la figura (b) muestra la imagen realzada con sus minucias. 43 En la figura 35 se observa que en la imagen realzada se ven 19 minucias más que en la imagen original, lo cual comprueba que el programa al mejorar la imagen hace que se vean más minucias de las que se ven en la imagen original de la huella. Cuadro comparativo con 53 imágenes: Figura número de minucias encontradas antes de la mejora número de minucias encontradas después del algoritmo de mejora Diferencias del número de minucias Imagen 001 12 19 7 Imagen 002 12 19 7 Imagen 003 10 20 10 Imagen 004 9 17 8 Imagen 005 19 22 3 Imagen 006 12 19 7 Imagen 007 24 30 6 Imagen 008 15 25 10 Imagen 009 18 29 11 Imagen 010 16 29 13 Imagen 011 15 28 13 Imagen 012 17 33 16 Imagen 013 14 26 12 Imagen 014 19 36 17 Imagen 015 27 33 6 Imagen 016 22 24 2 Imagen 017 12 23 11 Imagen 018 18 33 15 Imagen 019 26 43 17 Imagen 020 24 33 9 Imagen 021 26 35 9 Imagen 022 18 27 9 Imagen 023 20 18 -2 Imagen 024 25 33 8 Imagen 025 19 28 9 Imagen 026 26 26 0 Imagen 027 37 35 -2 Imagen 028 24 39 15 Imagen 029 20 23 3 Imagen 030 20 25 5 Imagen 031 16 15 -1 Imagen 032 18 15 -3 Imagen 033 22 33 11 Imagen 034 24 29 5 Imagen 035 25 23 -2 Imagen 036 23 22 -1 Imagen 037 26 29 3 Imagen 038 26 32 6 44 Imagen 039 26 42 16 Imagen 040 23 21 -2 Imagen 041 18 20 2 Imagen 042 27 39 12 Imagen 043 18 24 6 Imagen 044 15 28 13 Imagen 045 20 30 10 Imagen 046 22 37 15 Imagen 047 22 42 20 Imagen 048 27 33 6 Imagen 049 25 29 4 Imagen 050 20 28 8 Imagen 051 19 31 12 Imagen 052 20 22 2 Imagen 053 14 23 9 Figura 35: Se muestran la cantidad de minucias adicionales encontradas con el algoritmo de mejora. De la comparación se puede ver que en la mayoría de los casos se pueden observar más minucias con la mejora que sin la mejora, lo cual comprueba que el realce ha hecho posible que se pueda observar la huella con mayor nitidez y por lo tanto detectar más minucias. 45 Se ha aplicado el algoritmo de mejora con 53 huellas, de las cuales en 46 huellas se han detectado más minucias que vistas en las huellas originales. En las 7 huellas restantes se han obtenido menos minucias, esto se puede deber a que manchas de la huella que parecían minucias al realzarse ya no se ven como minucias. Debido a que en 46 de 53 imágenes se observan más minucias, el algoritmo tiene una efectividad del 87%. 46 Conclusiones: Se ha implementado un programa de mejora de imágenes de huellas digitales el cual mejora la claridad de las crestas y de los valles de la imagen basado en la orientación local de las crestas y en la frecuencia estimada de estas. Los resultados del programa desarrollado son aceptables ya que permiten mejorar la calidad de la imagen de una huella digital, sobretodo en regiones que están bien definidas y recuperables, pero no se puede aplicar al 100% en regiones no recuperables. Al aplicar el programa desarrollado a un conjunto de huellas, se observa en el 87% de las imágenes realzadas más minucias. Hay partes de algunas imágenes de huellas que no han podido ser realzadas, esto se debe a que son regiones no recuperables como son las zonas borrosas de las imágenes que salen al mover el dedo cuando se deja la huella. El algoritmo tarda 10 segundos en ejecutarse en una computadora Pentium 4 de 2.4 GHz, memoria RAM de 512MB con bus de 266 Mhz y memoria caché L2 de 512 KB. 47 Recomendaciones: En los programas de reconocimiento de imágenes se recomienda que las imágenes sean realzadas antes pasar a la etapa de reconocimiento, por lo que es necesario el algoritmo de realce desarrollado en el presente trabajo. Este algoritmo es recomendable para imágenes que no sean muy nítidas, siempre y cuando no sean imágenes de muy mala calidad o producto de borrones debido a movimientos del dedo cuando se deja una huella. No es recomendable para reconstruir la imagen de una huella digital parcial. Algunas huellas se pueden mejorar aumentando o disminuyendo los parámetros del filtro Gabor, como la desviación estándar. Para que la imagen de una huella se mejore, empíricamente se ha observado que la desviación estándar debe estar en un rango de 2 a 6. En promedio al algoritmo se le puede poner una desviación estándar de 4, aunque sería recomendable crear una función en el algoritmo que permita hallar el valor de la desviación adecuado para cada imagen. Para mejorar la eficiencia de este algoritmo es necesario diseñar un filtro más eficiente que el filtro Gabor, que realce la imagen sin distorsionar los detalles. 48 Bibliografía: [1] Davide Maltoni, Dario Maio, Anil K. Jain, Salil Prabhakar: Handbook of Fingerprint Recognition. New York, Springer, 2003. [2] Nalini Ratha, Ruud Bolle: Automatic Fingerprint Recognition Systems. New York: Springer-Verlak, 2004. [3] Rafael C. Gonzalez, Richard E. Woods, Steven L. Eddins: Digital Image Processing Using Matlab, New Jersey: Pearson, 2004. [4] Lin Hong, Yifei Wan, Anil Jain: “Fingerprint Image Enhacement; Algorithm and Performance Evaluation”: IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 20, No. 8, pp. 777-789, 1998. [5] Artículo del Diario El Comercio: “Usarán huellas digitales en lugar de tarjetas de crédito. Japón probará sistema con 200 trabajadores”. (28 de agosto del 2007). [6] D. C. Huang: “Enhancement and Feature Purification of Fingerprint Images” : IEEE Transactions on Pattern Recognition, vol. 26 no. 11, pp 1661 – 1671, 1993. [7] A.K. Jain and F. Farrokhnia: “Unsupervised Texture Segmentation Using Gabor Filters”: IEEE Transaction on Pattern Recognition, vol. 24, no. 12, pp. 1167 – 1186, 1991. [8] M. Kass and A. Witkin: “Analyzing Oriented Pattens”, Computer Vision, Graphics and Image Processing, vol. 37, no.4, pp. 362 – 385, 1987.