ReCIBE, Año 3 No.1, Enero 2014

Los Triángulos de Delaunay como Procesamiento Previo para Extractores Difusos


Manuel Ramírez Flores
Instituto Politécnico Nacional, Sección de Estudios de Posgrado e Investigación, México
manuel300688@gmail.com


Gina Gallegos Garcia
Instituto Politécnico Nacional, Sección de Estudios de Posgrado e Investigación, México
Unidad Culhuacán
ggallegosg@ipn.mx

Gualberto Aguilar Torres
Instituto Politécnico Nacional, Sección de Estudios de Posgrado e Investigación, México
gaguilar@ipn.mx

Miguel Angel Garcia Licona
Instituto Politécnico Nacional, Sección de Estudios de Posgrado e Investigación, México
Unidad Culhuacán
ma52gl@yahoo.com.mx


Resumen: La información biométrica que se extrae de las huellas dactilares tiende a ser diferente en cada adquisición, dada la incertidumbre existente en las mediciones y la presencia de ruido en las muestras, lo cual puede ocasionar que las palabras código generadas dentro de un extractor difuso posean un número de errores tal que rebase la capacidad de corrección de la codificación. Como consecuencia se tiene que lo anterior puede ocasionar que las huellas dactilares de una misma persona sean catalogadas como no coincidentes en su verificación o bien, que huellas de individuos diferentes parezcan demasiado similares.
Para mitigar los efectos antes mencionados y sobrepasar las dificultades del pre-alineamiento de huellas dactilares, se propuso el uso de triángulos de Delaunay, lo cual permite proveer de estabilidad estructural local a la representación espacial de la información biométrica. En esa propuesta, las minucias de la huella son utilizadas como vértices de las triangulaciones y la red formada por éstas es tolerante a distorsiones, rotaciones y traslaciones.
Sin embargo, en dicha propuesta se considera a la dispersión de minucias de huellas dactilares como no degenerativa y por tanto no se mencionan los umbrales o criterios necesarios para la formación de dichas triangulaciones, lo cual repercute en el desempeño de los extractores difusos. Con base en ello, este artículo presenta los resultados obtenidos al probar la formación de triangulaciones de Delaunay en imágenes de huella dactilar, en donde se aplican umbrales y criterios geométricos para luego contabilizar los triángulos coincidentes entre las estructuras formadas y definir los umbrales que maximicen dichas coincidencias.


Palabras clave: Extractores Difusos, Huella Dactilar, Triángulos de Delaunay.


Delaunay Triangles as preprocessing for Fuzzy Extractors

Abstract: The biometric extracted data from fingerprints tends to be different in each acquisition due to uncertainty in measurements and the noise in samples, which can cause that codewords, generated by fuzzy extractors, may have a number of errors that surpasses codification error-correcting capacity. As a consequence, the foregoing could cause that the fingerprints from same person would be classified as “mismatched”, while fingerprints from different people would be classified as “mismatched”.
To mitigate the effects mentioned before and surpass the difficulties of fingerprint’s pre-alignment, the Delaunay Triangles were proposed to provide local structural stability to spacial representation of biometric data. In that approach, the fingerprint’s minutiae are used as the triangles’s vertexes, and the formed net is tolerant to distortions, rotations and translations.
However, in that approach, the fingerprint’s minutiae dispersion is considered as non degenerative and because of that, neither thresholds nor specific criteria for triangulations are established. This has repercussions in the fuzzy extractors’ performance and because of that, in this article it is shown the obtained results after testing Delaunay triangulation's formations with fingerprints using geometric thresholds and criteria, Finally, the matched triangles are counted and the final thresholds are set to guarantee maximum matching.


Keywords: Fuzzy Extractors, Fingerprint, Delaunay Triangles.



1. Introducción

Los extractores difusos propuestos por Dodis, Reyzin, y Smith (2004), con la finalidad de derivar llaves criptográficas a partir de datos biométricos de forma segura. Para ello se utilizan 2 primitivas: extractor difuso y bosquejo seguro. El primero, parte de una entrada biométrica, para extraer una variable R, probabilísticamente casi uniforme, siendo esta extracción tolerante a errores. Por su parte, el bosquejo seguro produce información pública a partir de una entrada biométrica, sin revelar información de la misma. A la vez permite recuperar los valores de ésta, utilizando una segunda muestra biométrica.

Las huellas dactilares como ejemplo de entradas biométricas, tienden ser diferentes en cada captura cuando son de una misma persona, y las huellas de diferentes personas, pueden ser en cierto punto similares. Estas situaciones se presentan debido a la incertidumbre y variabilidad en las adquisiciones de datos biométricos, aunado al ruido inherente presente en estos procesos.

Para mitigar estos efectos y sobrepasar las dificultades del pre-alineamiento de huellas dactilares, se propuso el uso de triángulos de Delaunay, con lo que se logró proveer de estabilidad estructural local a los datos biométricos extraídos de huellas dactilares. (Wencheng, Jiankun, Song, 2012). En esa propuesta, las minucias de la huella son utilizadas como vértices de las triangulaciones y la red formada por éstas es tolerante a distorsiones, rotaciones y traslaciones. Sin embargo, en ese esquema no se consideran umbrales ni criterios para la formación de triangulaciones por lo que las discrepancias entre palabras código generadas dentro de las operaciones de un extractor difuso son mayores y pudieran no eliminarse por los códigos correctores de errores que estos contienen.

Con base en ello, en este artículo se presentan los umbrales y criterios adecuados que impacten positivamente en la tarea de reconocimiento de patrones entre huellas dactilares al utilizar Triángulos de Delaunay para caracterizar las minucias.

El artículo se encuentra organizado de la siguiente manera: En la Sección Biometría de Huella Dactilar, se enlistan las ventajas y desventajas del uso de datos biométricos de huella dactilar en procesos de autenticación. En la Sección Procesamiento de Huellas Dactilares, se habla sobre algunos algoritmos para procesar los datos biométricos extraídos y caracterizar las huellas dactilares. Posteriormente, en la Sección de Esquemas para el Tratamiento de Información sobre Huellas dactilares, se describen algunas propuestas hechas hasta el momento para organizar y utilizar información de huellas dactilares en procesos de autenticación.

En la Sección Triángulos de Delaunay, se establecen los principios teóricos y los algoritmos de implementación con los cuales es posible manipular información biométrica de huellas dactilares para mejorar el desempeño de las tareas de autenticación. Posteriormente, en la Sección Uso de triángulos de Delaunay en Extractores Difusos, se presenta un caso de práctico del esquema propuesto. Después, se presentan y discuten los resultados de las pruebas realizadas. Finalmente, se puntualizan las conclusiones del trabajo realizado.

2. Biometría de huella dactilar

Un sistema biométrico utilizado para autenticar, se puede definir como un sistema de reconocimiento de patrones que verifica la validez de una característica psicológica, fisiológica o de comportamiento de una persona. El sistema biométrico puede utilizar un algoritmo de verificación o identificación en su implementación, de ahí que un algoritmo de verificación busca autenticar la identidad de una persona, comparando la característica biométrica con la plantilla, de su biométrico, previamente almacenada (Maltoni, Maio, Jain, Prabhakar, 2005).

Las propiedades que debe tener cualquier característica psicológica, de comportamiento o física, para utilizarse como identificador biométrico son:

Universalidad: Todo individuo debe poseer una o más características biométricas.

Distintiva: Cualesquiera dos personas deben ser suficientemente diferentes en términos de un identificador biométrico.

Permanencia: El identificador biométrico debe ser suficientemente invariante con respecto al criterio de comparación, sobre un período de tiempo.

Cobrabilidad: La característica biométrica debe poder medirse cuantitativamente.

Aceptabilidad: Límite hasta el cual los individuos están dispuestos a aceptar la medición del identificador biométrico (Maltoni, et al, 2005).

La huella dactilar es un identificador biométrico que todos los humanos poseen con excepción de aquellos que presentan mutilaciones en sus manos o dedos. Además son distinguibles, sus detalles son permanentes aún y cuando pueden presentar variaciones y ligeros cambios con el tiempo debido a cortadas o golpes en la piel por las condiciones ambientales.

Los sensores utilizados para la toma de muestras de huellas dactilares eliminan el problema de segmentación entre el fondo y la huella y capturan imágenes con altas resoluciones. Adicionalmente, las nuevas tecnologías han permitido la miniaturización de estos dispositivos.

Sin embargo, a pesar de todas las bondades que ofrece un identificador biométrico como la huella dactilar, siguen estando presentes una serie de problemas inherentes a las mediciones biométricas, entre los que destacan:

  • El ruido en las mediciones biométricas.
  • El hecho de que si los datos biométricos de alguien son comprometidos, no pueden ser remplazados fácilmente, lo cual implica la pérdida de identidad de un usuario ante los sistemas de información.
  • La dificultad de construir un registro de huellas dactilares debido a las rotaciones, desplazamientos y variaciones de presión u otro tipo de distorsiones que pueden tenerse en las muestras utilizadas como plantillas biométricas.
  • Otro grave problema es el hecho de que los datos biométricos proveen singularidad pero no secrecía, por lo que deben ser resguardados y protegidos de posibles ataques de robo de información.

Debido a lo anterior, se han estudiado y propuesto nuevos esquemas, que buscan minimizar las variaciones en las mediciones.

3. Procesamiento de huellas dactilares

Una huella dactilar se compone de dos elementos denominados crestas y valles que conforman su relieve. Una cresta tiene una anchura promedio de 100 a 300 μm. A nivel global, una huella dactilar posee alrededor de 150 crestas diferentes y no están uniformemente distribuidas. Las diferentes formas o estructuras que se forman por la unión de crestas, se denominan minucias (Maltoni, et al, 2005).

Las minucias más comunes son: las terminaciones de crestas y las bifurcaciones de crestas. Una bifurcación de cresta es donde hay una separación o divergencia en ramificaciones de crestas. Ejemplos de otros tipos de minucias son: ciclos, deltas, espirales e islas, por mencionar algunas.

Algunos de estos tipos de minucias son utilizadas para alinear las imágenes de huella dactilar y encontrar el centro de la misma (Maltoni, et al, 2005).

4. Esquemas para el tratamiento de información sobre huellas dactilares

Algunos de los pre-procesamientos que se han realizado a datos biométricos como una etapa previa en el uso de extractores difusos y bóveda difusa son: transformaciones seguras para cancelabilidad en bóvedas difusas, caracterización de minucias para una bóveda difusa cifrada y Extractores difusos en la práctica, propuesta con base en FingerCodes.

En la primera propuesta, se utiliza un filtro de Gabor para la extracción de características, se genera un vector de 384 posiciones con la información obtenida. Los valores son normalizados en un rango de 0 a 255 para su uso en la bóveda difusa. Posteriormente, dicho vector convierte en una matriz de 15*17 y se convoluciona con una señal aleatoria de tamaño 10*10 para evitar que los datos biométricos sean comprometidos fácilmente ( Nagar, Chaudhury, 2006).

Una segunda propuesta se basa en la representación de minucias mediante 3 datos: coordenadas espaciales x y y, así como la orientación de la minucia θ. En este caso, la tripleta con estos datos forma parte de la bóveda segura que posteriormente se cifra para proteger los datos biométricos (Feng, Fei, Anni, 2009).

En trabajos similares a la propuesta anterior, esta tripleta, que se extrae por medio de un análisis de frecuencias y orientación de crestas, se combina con un secreto personal del usuario (contraseña) para posteriormente aplicarle una función hash, de esta manera se obtienen los valores de entrada para la bóveda difusa (Je-Gyeong, Jong-Won, Hyung-Woo, 2007)

En una tercera propuesta, los criptosistemas generadores de claves que utilizan el esquema de compromiso difuso o fuzzy commitment, y procesan la información biométrica mediante las siguientes operaciones: mejoramiento de huella, detección de centro, recortado, extracción de características de textura incluyendo FingerCodes, patrones locales binarios, y patrones locales de dirección. Posteriormente se procede a una discretización biométrica y fusión de bits confiables.

La generación de los FingerCodes requiere un punto de referencia en la huella (centro). Después de esta localización del centro, una región circular de interés es definida y se divide en bandas concéntricas cada una de las cuales está conformada por sectores. Dependiendo de la resolución de la imagen el número de bandas, su anchura, número de sectores que contiene y radio interior variarán.

La información extraída y analizada en estas regiones de la huella dactilar, mediante filtros de Gabor, es referente a orientaciones locales y frecuencias en la textura de la imagen. Para ello, se requieren 8 diferentes orientaciones sobre las cuales hacer el análisis. También es necesario calcular la desviación absoluta de los grises en los sectores de las imágenes filtradas (Imamverdiyev, Jin Teoh, Kim, 2012).

Adicionalmente se extraen patrones locales binarios que resultan invariantes ante niveles monótonos de grises. Estos patrones permiten la detección de orillas, finales de línea, esquinas, puntos y áreas planas. Finalmente, se calculan patrones locales de dirección que a diferencia de los anteriores si son tolerantes a ruido aleatorio e iluminaciones no monótonas (Imamverdiyev, et al, 2012).

En una cuarta y última propuesta, se utilizan FingerCodes, un extractor difuso, una función de bosquejo seguro y un polinomio cuyos coeficientes fungen como secreto para formar un esquema de compromiso difuso modificado (Tong, Sibert , Lecceur, Girault, 2007).

Un FingerCode es un vector de 640 componentes, el cual para ser formado, requiere de la localización del centro morfológico de la huella dactilar. Para calcular el centro de la huella dactilar, se hace una estimación de la orientación de campo de los bloques de la imagen. Posteriormente se extrae una región circular de interés alrededor del centro de la huella y se definen 5 bandas concéntricas y 16 porciones angulares, lo que genera 80 sectores (Tong, et al, 2007).

Con la propuesta anterior, se eliminan los problemas de rotación y traslación en la huella, mientras que los problemas de cambios de presión se solventan con una normalización de la imagen en términos de promedio y varianza. Finalmente las crestas y valles de la huella se caracterizan por su frecuencia local y orientación, la cual es obtenida utilizando filtros de Gabor y analizando los datos sector a sector (Tong, et al, 2007).

En todas las propuestas antes mencionadas si bien existe un tratamiento de la información biométrica de huella como procesamiento previo al uso de extractores difusos, ninguna propuesta resulta del todo robusta. En general, o se confía en la precisión de las adquisiciones biométricas o en la precisión de algoritmos para ubicar características como el centro de una huella dactilar, lo cual requiere cierto procesamiento computacional y no siempre es exacto.

Ante tal situación, en este artículo se retoma la propuesta hecha por Wencheng, et al. (2012), donde se utiliza la geometría computacional para caracterizar las huellas dactilares mediante triangulaciones y eliminar así problemas de distorsiones, rotaciones o traslaciones en las huellas dactilares.

5. Triánculos de Delaunay

Dentro de la geometría computacional, se lleva a cabo el estudio de la formación de triangulaciones sobre un conjunto de puntos P en un plano, el cual se define como una subdivisión plana máxima cuyos vértices son P.

Bajo las condiciones antes establecidas, si se tiene un conjunto de puntos P en un plano y estos forman una triangulación T, T será una triangulación de Delaunay de P si y sólo si la circunferencia circunscrita de cualquier triángulo de T no contiene un punto de P en su interior. Por otro lado, cualquier triangulación de Delaunay maximiza el ángulo mínimo sobre todas las triangulaciones de P.

El procedimiento para calcular un diagrama de Delaunay, es el siguiente: Se selecciona el punto lexicográficamente más elevado p0 en el conjunto P, esto es aquél con la coordenada x y y más grandes. Después se definen dos puntos p-1 y p-2 en el plano cartesiano lo suficientemente alejados tal que el conjunto P esté contenido en el triángulo formado por p0 p-1 p-2

Para cada uno de los puntos en el conjunto P, se ejecutan las siguientes operaciones:

  • Se encuentra el triángulo pi p j p k que contiene al punto a insertar pr.
  • Si pr, cae en el interior del triángulo pi pj pk, se agregan las aristas desde pr a los vértices de este triángulo, generando 3 triángulos nuevos como se puede ver en la Figura 1.
  • Luego, se corrigen las aristas que generaron triangulaciones que no cumplen con las características de un triángulo de Delaunay.
Figura 1. Inserción de punto al interior de un triángulo.

Figura 1. Inserción de punto al interior de un triángulo.

  • Si el punto pr cae sobre una arista del triángulo pi pj pk, se agregan aristas hacia los vértices no unidos y se dividen los 2 triángulos existentes en 4 nuevos, tal y como se aprecia en la Figura 2.
Figura 2: Inserción de punto sobre arista de un triángulo.

Figura 2. Inserción de punto sobre arista de un triángulo.

  • Posteriormente, se corrigen las aristas de las triangulaciones generadas.
  • Al final se descartan los puntos p-1 y p-2 con todas las aristas incidentes de la red de triángulos.

El procedimiento para corregir las aristas que no cumplen con las características de los triángulos de Delaunay, es el siguiente:

  • Una vez insertado el punto pr, si una arista pi pj resulta ilegal, entonces para el triángulo pi pj pk y su triángulo adyacente pr pi pj a lo largo de pi pj, se remplaza la arista pi pj por la arista pr pk tal y como se muestra en la Figura 3.
Figura 3. Corrección de aristas ilegales.

Figura 3. Corrección de aristas ilegales.

  • Posteriormente, se ejecuta el mismo procedimiento anterior para las aristas del nuevo triángulo formado. Es decir, para los segmentos pi pk y pk pj .
Figura 4 Grafo acícliclo dirigido para inserción de puntos.

Figura 4. Grafo acícliclo dirigido para inserción de puntos.

Todos los procedimientos antes descritos se realizan, asumiendo que se conoce el triángulo que contiene el punto pr a insertar. El procedimiento para conocer dicha triangulación es el siguiente:

  • Se requiere construir una estructura de localización de puntos, la cual es un grafo dirigido acícliclo.
  • Los nodos de la estructura corresponden a los triángulos dentro de la triangulación T, y se deben mantener apuntadores cruzados entre esas hojas y la triangulación. Los nodos internos en la estructura corresponden a triángulos que estuvieron presentes en la estructura en etapas tempranas del diagrama pero que ya fueron eliminados.
  • La inicialización de la estructura comienza con el grafo dirigido acíclico con un simple nodo que corresponde al triángulo p0 p-1 p-2. Algunos ejemplos de operaciones sobre esta estructura se observan en la Figura 4.

Una vez definidos los algoritmos y estructuras necesarios para la creación de los Triángulos de Delaunay, se presenta un caso de estudio en donde se emplean estas triangulaciones para caracterizar imágenes de huellas dactilares con presencia de ruido y variaciones por traslación y rotación de minucias.

6. Uso te triángulos de Delaunay con extractores difusos

En el trabajo realizado por Wencheng, et al. (2012), se propuso utilizar un extractor difuso libre de registro, además del uso de triángulos de Delaunay, que pudieran mitigar la incertidumbre biométrica, lo que permitió eliminar el proceso de pre-alineamiento en la autenticación de huellas dactilares, lo cual se consigue dado que a partir de un conjunto de minucias M, los triángulos de Delaunay particionan en pequeñas áreas, toda la región de una huella dactilar y presentan las estructuras vecinas de minucias más cercanas de una manera precisa.

Algunas de las características especiales que ofrecen los triángulos de Delaunay son:

  • Presentan buena estabilidad local ante distorsiones elásticas de las imágenes.
  • La inserción de puntos nuevos solo afecta a los triángulos que contienen esos nuevos puntos en todo el diagrama, por lo que se conserva estabilidad estructural bajo perturbaciones aleatorias de posiciones.
  • Las triangulaciones de Delaunay son únicas si la dispersión de puntos es única (minucias).

Para caracterizar cada vértice de los triángulos de Delaunay, se toma la información biométrica de huella dactilar referente a coordenadas espaciales de las minucias, orientación de las crestas asociadas a la minucia y el tipo de minucia de la que se trata.

Con la información antes mencionada se procede a caracterizar cada arista de los triángulos de Delaunay, calculando la siguiente información de los vértices que la conforman: Distancia euclidiana d12 en la Ecuación (1), diferencia de ángulo entre las orientación de cresta de una minucia y la arista calculada a12 en la Ecuación (2), la diferencia de orientaciones de cresta de los vértices que componen la arista β12, expresado en la Ecuación (3), y la concatenación de los tipos de minucia que conforman la arista t12 definida en la Ecuación (4) (Wencheng, et al., 2012).

Las ecuaciones que definen los cálculos antes detallados son:

Con esta información, se puede conformar el vector V12, como se aprecia en la Ecuación (5), que junto a otros dos, puede caracterizar los 3 vértices de un triángulo en la gráfica de Delaunay lo cual es denotado mediante un nuevo vector LF expresado en la Ecuación (6).

Una vez que se obtienen los vectores característicos de la huella dactilar mediante el uso de Triángulos de Delaunay, se procede a introducir la información a una etapa de codificación en el extractor difuso, específicamente, a la función de bosquejo seguro SS, que trabaja sobre una métrica de Diferencia establecida con el algoritmo de Pinsketch (Dodis, et al. 2004). El valor obtenido SS(LFin), junto con el valor hash H(LFin) que se obtiene al generar el valor hash de los vectores característicos, se almacenan para una decodificación futura.

En la etapa de decodificación, con una segunda muestra biométrica se calculan un segundo conjunto de vectores LFi m = (V’ij,V’jk,V’ik). Estos vectores son comparados con su versión asegurada SS(LFi), utilizando el procedimiento de recuperación REC del algoritmo de Pinsketch.

Si la diferencia es menor a un umbral t,dis(LF’i, LFi) ≤ t , se realiza una corrección de errores en los vectores. Después se aplica la misma función hash al vector corregido y se comparan los valores de H(LFin) y H(LFim). En caso de ser los mismos, para un cierto número de vectores LF, según un umbral previamente establecido, se verifica la identidad del usuario (Wencheng, et al. 2012).

La propuesta anterior considera que para el uso de los Triángulos de Delaunay se debe contar con una dispersión de puntos no degenerativa. Es decir, que el conjunto de minucias de una huella dactilar no cambia entre una muestra y otra, por lo que puede construirse la misma red de triangulaciones en cada adquisición.

Esta última condición difícilmente se cumple en su totalidad en un escenario con adquisiciones en vivo, por lo que es necesario evaluar la viabilidad del esquema y plantear bajo qué condiciones o umbrales se puede considerar que la dispersión de minucias es constante. Dicha evaluación se presenta a continuación.

7. Pruebas y Resultados

Las pruebas que se realizaron para evaluar la viabilidad del uso de Triángulos de Delaunay como procesamiento previo de la información biométrica de huella dactilar para extractores difusos, fueron la construcción de triangulaciones sobre imágenes de huella dactilar de alta calidad e imágenes extraídas en vivo. En cada una se utilizó una de las imágenes para extraer las triangulaciones que conformarían la plantilla biométrica de un conjunto de 5 muestras por huella dactilar.

Posteriormente se hizo un análisis comparativo entre pares de muestras biométricas, en donde se determinó si las minucias de una muestra eran coincidentes con las de la segunda, de acuerdo a un conjunto de umbrales definidos desde teclado.

Dichos umbrales se definieron con base en las siguientes mediciones: radio de probabilidad de aparición espacial de minucias, orientación o ángulo de minucias y distancia euclidiana entre las minucias que forman un triángulo de Delaunay.

La Tabla 1 muestra los resultados de las pruebas realizadas con imágenes obtenidas de mediciones en vivo sobre una misma huella dactilar. Se toma la imagen “vivo1” como plantilla de registro y 4 imágenes adicionales para una comparación entre el número de triangulaciones de cada muestra.

Las columnas 3 a 5 describen los umbrales configurados para las mediciones de las minucias, tomando en cuenta una imagen de dimensiones 352 x 288 pixeles. Las columnas 6 y 7 indican el número de triangulaciones de Delaunay por imagen y la última columna, el porcentaje de triángulos coincidentes

Tabla 1. Análisis comparativo sobre triangulaciones de Delaunay

Tabla 1. Análisis comparativo sobre triangulaciones de Delaunay


Tabla 2. Análisis comparativo sobre triangulaciones para imágenes de alta calidad

Tabla 2. Análisis comparativo sobre triangulaciones para imágenes de alta calidad


Tabla 3. Análisis comparativo sobre triangulaciones para huellas dactilares diferentes

Tabla 3. Análisis comparativo sobre triangulaciones para huellas dactilares diferentes


Figura 5. Programa discriminador de triangulaciones

Figura 5. Programa discriminador de triangulaciones


Figura 6. Comparativa visual de triangulaciones de Delaunay

Figura 6. Comparativa visual de triangulaciones de Delaunay


Figura 7 Sub-diagrama de triangulaciones de Delaunay coincidentes

Figura 7. Sub-diagrama de triangulaciones de Delaunay coincidentes


8. Discusión

Como se puede apreciar en la Tabla 1, los porcentajes de triangulaciones coincidentes son muy variados dependiendo de la huella utilizada y su comparación con la plantilla. Los porcentajes de coincidencia oscilan entre un 30-35% para los mejores casos e incluso llegan a un 0% para los peores.

Esto indica que las variaciones entre una muestra biométrica y otra pueden generar triangulaciones muy diferentes en cada caso, por lo que se descarta la idea de que la dispersión de minucias sea no degenerativa. Sin embargo, algunos resultados obtenidos también indican que con una corrección de errores mediante códigos lineales, se pueden mejorar estas coincidencias.

En las últimas 2 filas de la Tabla 1, se observa una comparación entre la muestra biométrica 3 con las muestras 4 y 5, esto se debe a que estas tres muestras fueron adquiridas con una diferencia de 1 día.

Por lo tanto, las condiciones de las adquisiciones con respecto a las 3 primeras muestras fueron diferentes, mientras que las condiciones de medición entre las 3 últimas mediciones fueron muy similares, de ahí que el número de triangulaciones coincidentes es mayor.

La Tabla 2 muestra los resultados de las pruebas realizadas con imágenes de huella dactilar categorizadas con calidad 1 según las recomendaciones del NIST (Tabassi, Wilson, Watson, 2004). En este caso se toma la imagen “012_3_4” de huella dactilar como plantilla biométrica, se extraen sus triangulaciones de Delaunay y se hace un comparativo con otras 4 muestras de la misma huella.

En la Tabla 3 se muestran los últimos resultados, de un comparativo entre 2 huellas dactilares diferentes y se observa que no hay ninguna triangulación coincidente entre las mismas, por lo que la caracterización de las minucias a través de triángulos de Delaunay, respeta la singularidad de las mismas.

En la Figura 5 se muestra una captura del programa que realiza la discriminación de las triangulaciones con base en los umbrales establecidos desde consola.

La Figura 6 muestra diagramas de Delaunay correspondientes a dos muestras de una misma huella dactilar. En cada uno de ellos se señalan las minucias coincidentes y en la Figura 7 se muestra una tercera imagen, donde se generó un sub-diagrama de triangulaciones coincidentes a partir de los dos anteriores.

9. Conclusiones

En este artículo, se presentaron un conjunto de criterios y consideraciones geométricas para la formación de Triángulos de Delaunay utilizados en la tarea de reconocimiento de patrones para huellas dactilares. Dichos criterios y consideraciones fueron obtenidos de un conjunto de pruebas entre huellas dactilares de una misma persona y un mismo dedo y pruebas entre huellas dactilares del mismo dedo pero que pertenecían a diferentes personas. Con ello se logró comprobar que el uso de criterios y umbrales geométricos para la formación de Triángulos de Delaunay permite caracterizar de una manera más robusta las huellas dactilares de individuos cuando la dispersión de minucias en las huellas dactilares es degenerativa.

Los criterios y umbrales para compensar la degeneración de la distribución de minucias se establecen en términos de:

  • Coordenadas espaciales de las minucias que conforman los vértices de las triangulaciones.
  • Orientación o ángulo de los vértices en las triangulaciones.
  • Distancia euclidiana entre los vértices de las triangulaciones.

Para las coordenadas espaciales, se considera un radio de aparición de 15 pixeles a la redonda, cantidad que representa un porcentaje del 10% de las dimensiones totales de la imagen. Esta es una proporción adecuada de las distorsiones que pudieran presentarse en la imagen.

La orientación o ángulo de las minucias que conforman los vértices de un triángulo en el diagrama de Delaunay, tienen un umbral no mayor a 5 pixeles, ya que el pre procesamiento de una imagen biométrica mediante binarización, adelgazamiento de líneas, filtrado de ruido, entre otros algoritmos, presenta mínimas variaciones de ángulo en sus minucias.

Finalmente el umbral para la distancia euclidiana entre los vértices de un triángulo de Delaunay puede tener una variación de hasta 5 pixeles, debido a que si la ubicación de las coordenadas espaciales de un vértice entre 2 triangulaciones en diferentes muestras biométricas coincide, la variación es mínima y cambia con base en las coordenadas espaciales x y y que define el cálculo de distancia euclidiana.

Por último es importante señalar que la ausencia de umbrales y criterios geométricos en la formación de Triángulos de Delaunay de muestras biométricas de huella dactilar, puede derivar en la construcción de diagramas de Delaunay poco semejantes entre muestras de un mismo origen. Esta situación puede impactar negativamente en el desempeño de otros esquemas como son los extractores difusos, así como en su capacidad para extraer una cadena binaria uniformemente distribuida a partir de una entrada biométrica probabilísticamente no uniforme.


Referencias

Dodis, Y., Reyzin, L. Smith, A. (2004). Fuzzy Extractors: How to generate Strong Keys from Biometrics and Other
          Noisy Data. Advances in Cryptology EUROCRYPT 2004. International Conference on Vol. No., pp. 523-540.

Feng, Q., Fei, S., Anni, C. (2009). Encrypted Fuzzy Vault Based on Fingerprint. IAS2009. Fifth International
          Conference on Information Assurance and Security. Vol. no. 1 pp. 137-140.

Imamverdiyev, Y., Jin Teoh, A., Kim, J. (2012). Biometric Cryptosystem Based on Discretized Fingerprint Texture
          Descriptors. Expert Systems with Applications. Vol. 40 no. pp. 1888-1901.

Je-Gyeong, J. Jong-Won, S., Hyung-Woo, L. (2007). Biometric Digital Signature Key Generation
          and Cryptography Communication Based on Fingerprint. FAW. Frontiers in Algorithmics.
          Vol. no. pp. 38-49.

Maltoni. D., Maio, D., Jain, A. Prabhakar, S. (2005). Handbook of Fingerprint Recognition. United States: Springer.

Nagar, A., Chaudhury, S. (2006). Biometrics based Asymetric Cryptosystem Design Using Modified Fuzzy
          Vault Scheme. ICPR06, The International Conference on Pattern Recognition. Vol. 04, no. pp. 537-540.

Tabassi, E., Wilson, C., Watson, C. (2004). Fingerprint Image Quality. NISTIR 7151. pp.12.

Tong, V., Sibert, H., Lecceur, J., Girault, M. [2007] Biometric Fuzzy Extractors Made Practical: A Proposal
          Based on FingerCodes. Advances in Biometrics. Lecture Notes in Computer Science. Vol. No. pp. 604-613.

Wencheng Y., Jiankun, H. Song, W. (2012). A Delaunay Triangle-Based Fuzzy Extractor for Fingerprint
          Authentication. Trust, Security and Privacy in Computing and Communications (TrustCom)
          IEEE 11th International Conference on. Vol. no. pp. 66-70. doi: 10.1109/TrustCom.2012.23



Notas biográficas:

Manuel Ramírez Flores Recibió el título de Ingeniería en Telecomunicaciones y Sistemas Electrónicos con mención honorífica por parte del Instituto Tecnológico y de Estudios Superiores de Monterrey Campus Ciudad de México en el año 2010. En el 2012 cursó la especialidad en Seguridad Informática y Tecnologías de la Información en la ESIME Culhuacan. Actualmente se encuentra estudiando la maestría en Informática y Seguridad de la Información en la dicha institución. Sus áreas de interés son la Votación Electrónica, el diseño de Aplicaciones Criptográficas Seguras y la biometría.

Gina Gallegos Garcia Recibió el título de Ingeniería en Computación, el Grado de Maestría y de Doctorado en Ciencias por parte de la ESIME Culhuacan en los años 2002, 2005 y 2011 respectivamente. Durante el verano del 2011 realizó una estancia Posdoctoral de investigación en la Universidad de Yale de los Estados Unidos de América. Actualmente es Profesora de la Sección de Estudios de Posgrado e Investigación de la ESIME Culhuacan y pertenece al Sistema Nacional de Investigadores. Sus áreas de interés son La Votación Electrónica, el Diseño de Aplicaciones Criptográficas Seguras, los Sistemas de Información y la Criptografía.

Gualberto Aguilar Torres Recibió el grado de Maestro en Ciencias de Ingeniería en Microelectrónica y de Doctor en Comunicaciones y Electrónica en 2004 y 2008 respectivamente, en el Instituto Politécnico Nacional. En 2005 recibió el premio a la mejor tesis de maestría por parte del IPN. Actualmente es Profesor de la Sección de Estudios de Posgrado e Investigación de la ESIME Culhuacan y pertenece al Sistema Nacional de Investigadores. Sus principales áreas de interés son procesamiento de señales, reconocimiento de patrones, redes neuronales y biometría.

Miguel Angel Garcia Licona Obtuvo título de Ingeniero Mecánico por la Escuela Superior de Ingeniería Mecánica y Eléctrica del Instituto Politécnico Nacional en 1973, Realizó diplomado en Didáctica de las Matemáticas en INSA Lyon Francia (2007), posteriormente alcanzó el grado de la Maestría en Administración y Desarrollo de la Educación en la Universidad Tecnológica de México (2008) y más adelante cursó el doctorado en educación por la Universidad de Alcalá alcanzando el 100% de los créditos (2010). Área de interés: desarrollo e investigación en didáctica de las matemáticas con aplicaciones a la seguridad informática.



                                                                          Licencia de Creative Commons
                                                  Esta obra está bajo una licencia de Creative Commons                                                                               Reconocimiento-NoComercial-CompartirIgual 2.5 México.