OBJETO DE LA INVENCiÓN
La presente invención se enmarca en el campo de los sistemas y métodos de identificación biometrica.
El objeto de la invención consiste en un método y un dispositivo que permiten generar un vector de características de una huella dactilar humana mediante una serie de procesos realizados a partir de la imagen de dicha huella. Con esos vectores se puede realizar una clasificación, indexación o determinación de identidad de huellas (y, por tanto, de individuos) , así como proteger secretos o generar claves criptograficas a partir de huellas.
ANTECEDENTES DE LA INVENCiÓN
El uso de huellas dactilares como característica biometrica esta ampliamente extendido para aplicaciones de identificación de individuos, control de acceso, ele., por 25 su alta discriminación y porque los usuarios aceptan con normalidad el hecho de introducir la huella en un dispositivo de captura (proporciona facilidad de uso al ser una técnica no intrusiva) Es una de las características biometricas que con mayor éxito se han aplicado en la actividad forense y policial y. mas recientemente. en sistemas de control de acceso Los sistemas automaticos de identificación de huellas (AFIS. 30 '"Automatic Fingerprint Identificaban Systems'") requieren comparar una huella de entrada con las huellas almacenadas en la base del sistema. En estas aplicaciones, los individuos se registran previamente en una base mediante las características de sus huellas dactilares. Posteriormente, cuando se quiere identificar un individuo, se vuelven a extraer las características de sus huellas y se comparan con las caracterlsticas almacenadas en la base de huellas.
Actualmente es un desafío la realización eficiente de sistemas de identificación que N° solicitud F.Efccllva 30/10/2015
utilicen bases con un número elevado de huellas y proporcionen tiempos de respuesta inmediatos. a la vez que exactitud en la identificación El tiempo necesario para la identificación de un individuo (tidentificación) se puede expresar como:
tidentificación = textracción + temparejamiento*N + tdecisión donde textracción es el tiempo invertido en la extracción de características de la huella, temparejamiento es el tiempo empleado para comparar las características extraídas de la huella de entrada con cada una de las N caracteristicas almacenadas en la base, y tdecisión es el tiempo empleado para decidir cuál de los N individuos registrados es el candidato elegido como poseedor de la huella de entrada, en el caso de una aplicación de identificación, o el tiempo empleado en generar una lista reducida con los M individuos candidatos a poseerla (con M mucho menor que N) , en el caso de una aplicación de indexación.
El valor de (extracción es mucho mayor que el de temparejamiento porque el proceso de extracción de características es mucho mas complejo que el del emparejamiento. Por ejemplo, el algoritmo de extracción MINOTCT desarrollado por el NIST ("National Institute of Standards and Technology") es un orden de magnitud más lento en una 20 misma plataforma PC con un procesador Intel Core i7 que el algoritmo de emparejamiento BOZORTH98 de NIST, por ejemplo, más de 200 ms de media para el primero y menos de 20 ms para el segundo (tanto MINDTCT como BOZORTH98 disponibles en NIST Biometric Image Software (NBIS) , http://WW'vV.nist.govlltlllad/ig/nbis.cfm ). Sin embargo, aunque el (emparejamiento sea menor, al estar multiplicado por N, la búsqueda en la base puede ser demasiado lenta para aplicaciones en tiempo real
Para reducir el número de comparaciones de la huella de entrada con respecto a las huellas almacenadas en la base del sistema, se utilizan métodos denominados de "clasificación exclusiva" en los que las huellas se distribuyen en grupos disjuntos preestablecidos, de forma que la huella de entrada se clasifica en uno de esos grupos y sólo se compara con las huellas registradas de ese grupo. El esquema comúnmente util izado sigue las propuestas de Galton y Henr y (E.R Henr y , "Classification and Uses of Finger PrintsR London: Routledge, 1900). que distinguen cinco grupos de huellas,
r arch" , uwhorl", Utended arch", ~Ieft loop·, y "right loop"). El problema es que la mayor parte de las huellas pertenecen sólo a tres grupos ("right loop", "Ieft loop·, y "whorl") , con lo cual no se produce una gran reducción del número de comparaciones en una
F.OEPM
02/11 /2015
base de huellas extensa (R. Cappelli. A. Lumini, D. Maio, and O Maltoni, ~Fingerprint classification by directlonal ¡mage partitioning"; IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21 , pages 402-421 , 1999). Otro problema de los métodos de clasificación exclusiva es que determinar a que clase pertenece una huella 5 se trata en muchos casos de una operacíón ambigua. Estos inconvenientes han propiciado la aparición de los metodos denominados de "clasificación continua", que asignan un vector de caracteristicas numéricas a cada huella. De esta forma, en la fase de indexación rindexing") , se crea una tabla o base índexada de huellas. En la fase de recuperación rretrieving") , ante una huella de entrada con un vector de características representativo, se calcula la similitud entre el vector de entrada y las almacenadas mediante una medida de distancia, de forma que puede obtenerse una lista reducida con las M candidatos más similares (con M mucho menor que N). A continuación se pueden aplicar otros métodos de identificación para determinar el ind ividuo correcto de entre los seleccionados Una huella dactilar es una imagen donde se distinguen crestas y valles en escala de grises. La comparación directa de las huellas en escala de grises no ofrece buenos resultados, además de ser una técnica costosa en cuanto a cómputo y almacenamiento. Es mejor procesar la imagen para obtener características distintivas 20 y compactas. Se suele hablar de características de 3 niveles, segun el nivel de detalle con el que se analice la huella. Las características de nivel 1 se obtienen de un análisis global de la huella. Un ejemplo es la imagen (campo o mapa) direccional (también llamado imagen, campo o mapa de orientaciones) , que contiene las orientaciones locales de las crestas respecto a un eje de referencia. Otro ejemplo son 25 los puntos sing ulares, que son puntos de la huella donde convergen (núcleos o ·cores") o divergen ("deltas") las orientaciones y en torno a los cuales se encuentra la mayor parte de la información distintiva de una huella. Las características de nivel 2 se obtienen de un análisis local y en mas detalle de la huella. Un ejemplo son las tradicionales minucias, que pueden ser terminaciones (lugares donde las crestas acaban) y bifurcaciones (lugares donde las crestas se separan en otras dos). Las caracteristicas de nivel 3 (como poros o crestas incipientes) se obtienen tras un análisis muy detallado de la huella que requiere una adquisición de la misma con muy buena calidad. La extracción de características es tanto mas distintiva y a la vez mas costosa cuanto mayor sea el nivel.
Hasta el momento, apenas se han reportado técnicas que empleen caracteristicas de nivel 3. Si se han reportado varias técnicas que emplean características de nivel 2. El
paso previo a todas estas técnicas es extraer las minucias. Los procesos de extracción
de minucias son complejos debido a que la imagen de la huella tiene que ser
preparada para localizar los mínimos detalles (las minucias son poco robustas ante el
posible ruido que la imagen de una huella puede presentar). Por ejemplo, la técnica de
s extracción de minucias mas común requiere que la imagen de la huell a sea mejorada,
segmentada , binarizada, y adelgazada Un ejemplo ampliamente conocido de
algoritmo detector de minucias es el MINOTCT comentado anteriormente. La
comparación de huellas basada en minucias es relativamente lenta y, por ) 0 tanto, no
es adecuada para indexación (por ejemplo, usando algoritmos como BOZORTH98
10 comentado anteriormente). Las técnicas de indexación que usan características de
nivel 2 aplican un post-procesado sobre las minucias extraídas. Así por ejemplo, en la
Patente "Method for searching fingerprint database based on quantum algorithm",
CN102495886 {Al, se elige un conjunto de minucias y se expresan en coordenadas
polares respecto a unas puntos de referencia que también se eligen
15 convenientemente En la Patente "Fast fingerprint identification and verification by
minutiae pair indexing", W02008135521 (A2) , se emplea indexación mediante parejas
de minucias. En el documento "Methods and systems for automated fingerprint
recognition", W02008098357 (A1) , se asocian patrones de minucias a las huellas. El
metodo y sistema propuesto en el documenta "Progressive fingerprint matching system
20 and method", US2004062426 (A1) se basa en emparejamiento de huellas por
minucias. En el documento "Fingerprint verificationn , US2005058325 (A1) , se
muestrean las minucias y se ordenan en subconjuntos. En el documento "System and
method for matching (fingerprint) images an aligned string-based representation~,
US6185318 (81) , se emplean las minucias como puntos de referencia. En el
25 documento "Methods and related apparatus for fingerprint indexing and searching",
US6181807 (81) , se extraen minucias de las huellas y se comparan en el proceso de
búsqueda En el documento "Vector based topological fíngerprint matching",
W09532482 (A 1 " se emplean las posiciones de las minucias y se les asigna un
número de índice. Otras técnicas conocidas son las que emplean tripletas de minucias.
30 En el documento "Fingerprint identification method based on triangulation and LOO
technology~, CN101620677 (A) , se emplea una tecnolog ía de triangulación para
extraer vectores de características globales y locales. Anteriormente se ha propuesto
usar todas las tripletas posibles que pueden formarse can cada minucia. Otros autores
proponen aplicar la triangulación de Oelaunay de orden 1 a las coordenadas de las
35 minucias para asignar una estructura topológica única a cada huella. En otras técnicas
conocidas en el arte se usan triángulos de Delaunay de arden superior a 1 para
extraer mas información geométrica. Otra técnica que usa características de nivel 2 es
la representación MCC ('"Minutia Cylinder-Code"). que asigna a cada minucia una estructura local que codifica la probabilidad de encontrar minucias a su alrededor, con una diferencia de orientación similar a un valor dado Las técnicas que usan características de nivel 1 ofrecen prestaciones competitivas con mucho menor coste computacional. De hecho, la extracción de la imagen direccional es un paso necesario en la mayoría de los algoritm os de extracción de minucias y de comparación de huellas, por lo que podría decirse que su coste es cero_ Estas técnicas se diferencian unas de otras en cómo extraen características representativas y compactas de la imagen direccional. Por ejemplo, en técnicas conocidas se emplea un modelo de orientación de huellas basado en expansiones de Fourier bidimensionales para adaptarse a la periodicidad intrínseca de las orientaciones. En otras soluciones se emplean un conjunto de momentos complejos polares (PCMs) para extraer características de la imagen direccional invariantes a rotaciones de la huella.
En el documento ~New fingerprint database retrieval method", CN102368242 (A) , se emplean puntos singulares, información sobre la relación entre puntos singulares y
momentos invariantes ortogonales. En el documento ~Method for rapidly calculating
fingerprínt similarity", CN1 01996318 (A) , se buscan unidades topológicas similares entre cada par de huellas a comparar, se expanden para obtener unidades topológicas similares mayores y se agrupan para obtener una medida de similitud global.
La mayoría de las soluciones para identificación e indexación de huellas son implementaciones software que involucran algoritmos de un coste computacional elevado en términos de tiempo y recursos. El coste es elevado, no sólo para la extracción de las características, sino incluso para el algoritmo de emparejamiento que calcula la similitud entre las características de la huella de entrada y las almacenadas.
Las soluciones para indexación normalmente se evalúan mostrando, para una razón de penetración dada (un porcentaje promedio de la base de huellas que se va a analizar) , la razón de error (porcentaje de huellas de entrada cuyo registro no se recupera de entre la lista con similitudes mas altas con esa penetración). Esta es la razón de penetración definida como el porcentaje de candidatos que se consideran para ver si entre ellos está el poseedor verdadero de la huella de entrada (M/N). Otra medida normalmente analizada para evaluar la bondad de una técn ica de indexado es la tasa promedio en un escenario de búsqueda incremental ("incremental search scenario~) , que se calcula como la tasa promedio que hay que llevar a cabo cuando no se quieren cometer errores en la recuperación del poseedor de la huella de entrada. Los tiempos promedios que se invierten en la búsqueda no suelen reportarse y tampoco los requerimientos de memoria. En los trabajos que sí se reportan. los tiempos que se muestran son de realizaciones sobre PCs: 67 ms en un Intel Pentium 4 a 2.26 GHz y 1.6 ms, 14 ms 016 ms (según la técnica) en un Inlel Core 2 Quad a 2.66 GHz sobre 2000 huellas de la base NIST 084.
En las soluciones para identificación, una vez generado el vector de características y
comparado con los vectores almacenados, no se genera una lista ordenada de huellas sino que se establece un umbral de emparejamiento para aceptar o rechazar si un individuo es quién dice ser. En este caso, lo que se miden son razones de falso rechazo (FRR, uFalse Rejection Rate") y de falsa aceptación (FAR, "False Acceptance Rate"). en lugar de tasas de penetración, como en el caso de inde) (ación. También denominadas FNMR (MFalse Non-Match Rate") o FMR r False Match Rate6
) ,
respectivamente.
El contexto de aplicación de estas soluciones suele ser el forense y policial, en el que las huellas que se tienen de un individuo se han adquirido sin su cooperación (por 20 ejemplo, porque se trate de identificar a un fallecido o a un delincuente). Se denomina un contexto "fuera de linea", por Jo que las capturas pueden ser de mala calidad y los algoritmos pueden realizarse sobre PCs sin requerimientos especialmente restrictivos de velocidad y consumo de memoria. Existen bases de huellas , como las de la "Fingerprint Verification Competition" (FVC) , que estan construidas con muchas capturas de mala calidad y mal adquiridas para probar la bondad de técnicas complejas de identificación e indexado.
Un contexto de aplicación diferente es el que se denomina "en línea", en el que el usuario de un sistema de reconocimiento coopera con el sistema porque quiere 30 autenticarse (por ejemplo, en un sistema de control de acceso). En este caso, las capturas son de mucha mejor calidad e, incluso, se puede interactuar con el usuario para que introduzca bien su huella. En esta linea, se conoce una solución para la estimación de la calidad de una huella basada en un algoritmo para la extracción de puntos singulares que satisface las restricciones en términos de recursos, tiempo de 35 respuesta y resultados de reconocimiento impuestos para una aplicación de adquisición inteligente en un dispositivo hardware empotrado. En el documento "Melhod for authenticating an individual by use of fingerprint data-, US7136514 (81) ,
se tiene en cuenta que el individuo que introduce su huella mediante un sensor de
barrido puede barrer el dedo en diferentes direcciones respecto al eje del sensor. En el
documento ~ Fingerprint matching", GB2320352 (A) , se emplean índices de calidad en
la extracción del vector de características para luego emplearlos en el calculo del
5 emparejamiento entre huellas.
l os requerimientos de velocidad si son restrictivos en un contelcto de aplicación en
linea , porque la operación debe ser en tiempo real. la facilidad de uso del sistema y
su precio también pueden ser requerimientos importantes en este contexto. El usuario
10 puede emplear cómodamente un dispositivo electrónico pequei'lo, ligero y barato, por
ejemplo, una tarjeta o token con recursos reducidos. los recursos de los que dispone
una tarjeta inteligente o un OSP para dispositivos empotrados son mucho menores
que los de un pe: CPUs de 50 ó 100 MHz y memorias disponibles (ROM , EEPROM Y
RAM) de unas cuantas decenas de KBytes, en el mejor de los casos.
' 5
Los tiempos aumentan mucho si la plataforma donde se implementan los algoritmos
tiene pocos recursos. Por ejemplo, el algoritmo MINOTCT adaptado y ejecutado sobre
un procesador lEON2 empotrado invierte en su ejecución casi tres órdenes de
magnitud mas que en la plataforma PC (unos 100 s, segun se ha reportado). Por este
20 motivo, la extracción de características se suele hacer sobre una plataforma tipo p e y
las soluciones que emplean tarjetas o DSPs para reconocimiento en línea por huella
dactilar sólo implementan el algoritmo de emparejamiento entre las caracteristicas
almacenadas y las que le llegan del exterior. Ademas, las características almacenadas
suelen ser las de un individuo sólo (emparejam iento 1 frente a 1 en vez de 1 frente a
25 N). A esta solución se le suele denominar ~ match on card". Aun así , se han propuesto
soluciones en las que se redisei'la el software del algoritmo de emparejamiento, se
emplea aritmética de punto fijo y se extiende el conjunto de instrucciones del
procesador empotrado para acelerar la ejecución. los algoritmos de "match on card"
se han estudiado recientemente en la campaña MINEX II organizada par el NIST. Los
30 resultados obtenidos demuestran que san menas precisos que los que se ejecutan
sobre una plataforma PC Otra opción para la implementación en sistemas empotrados
es emplear FPGAs ("Field Programmable Gate Arrays"). En las FPGAs se pueden
implementar coprocesadores hardware que aceleren la ejecución de los algoritmos.
Así, por ejemplo, existe una solución que propone la correlación directa de imágenes
35 en escala de grises, usando una FPGA Virtex 4. Para aplicaciones de indexación de
huellas, existe una tecnica que crea una base de huellas cuyos índices se basan en la
extracción de minucias, en la que la base de huellas y la búsqueda sobre la base se
implementan en placas PC I basadas en FPGAs mientras que la extracción de minucias se realiza en el PC al Que se conectan las placas.
En términos de seguridad , es muy interesante Que todo el proceso de extracción de 5 características, su almacenamiento y emparejamiento se pueda realizar en el mismo dispositivo, lo que se denomina "authentication on card~, porque así las características distintivas de los individuos se circunscriben dentro de un perímetro mucho más pequeño, que, por tanto, es mas facil de controlar y defender. En esta línea, existen soluciones donde se implementa un algoritmo de extracción de minucias en una FPGA 10 Spartan 3 y soluciones donde se implementa un sistema de reconocimiento basado en la localización de puntos singulares sobre una placa RC203E de Celoxica equipada con una FPGA Virtex 11. En vez de simplificar los algoritmos a implementar, la solución analizada en una segunda opción es emplear FPGAs que se reconfiguran según la tarea a realizar (extracción de la imagen direccional, mejora y segmentación de la imagen de la huella, binarización, suavizado, adelgazamiento, detección de minucias, alineamiento y emparejamiento). Esta idea de ~authentication on card~ aparece en varias patentes. Entre ellas, podemos citar "Siometric identity verification system and method~, US 20080223925 A 1 y, entre las más recientes, "Smart card system with
ergonomic fingerprint sensor and method of using", US 8276816 82
Otro gran problema de los sistemas de identificación basados en huella dactilar, ya no relacionado con la implementación sino con su propia naturaleza, es el de la falta de diversidad en la obtención de caracteristicas distintivas. Por ejemplo, un usuario dispone como mucho de 10 dedos en sus manos. Si se descubre Que un impostor se apodera de las características de uno de sus dedos, el individuo ya ha perdido el 10% de sus posibles características. Si el impostor se apodera de las características de los 10 dedos, el individuo ya no puede registrarse en ningún sistema Este problema también se denomina como la escasa revocabilidad del sistema, es decir, es difícil generar nuevas características cuando otras han sido descubiertas o comprometidas.
Para evitar que las características puedan ser comprometidas , se han propuesto sistemas que las transforman mediante funciones no invertibles, como las funciones hash, de forma que recuperar las caracteristicas originales a partir de las transformadas sea prácticamente inviable desde el punto de vista computacional. En estos sistemas, la medida de similitud o emparejamiento entre las características de entrada y las previamente registradas se realiza en el espacio transformado. Por eso hay Que analizar muy bien cómo afecta la transformación a las prestaciones del
sistema resultante (por ejemplo, en cuanto a tasas de falsa aceptación y fa lso rechazo). Esta solución no solventa el problema de la diversidad porque la transformación de caracteristicas no incrementa el número de posibles características. Para ello, se puede emplear un número aleatorio (conocido como "salt" en las técnicas 5 criptograficas) que se combine con las características originales, de forma que su transformación sea diferente aun cuando emplee [a misma información biométrica El ~saltN actúa como una palabra de paso que el individuo debe introducir en el sistema,
además de su huella dactilar. La desventaja de esta solución es que la palabra de paso y las características transformadas no deben hacerse pUblicas para incrementar 10 [a seguridad del sistema.
Otro esquema que posee la ventaja de no requerir almacenamiento seguro de información es el de los denominados sistemas de cifrado biométricos rbiometric criptosystems'). Se basan en combinar las caracteristicas biometricas originales (sin ninguna transfomación) con información adicional de tal manera que los datos 15 resultantes, conocidos como "helper data" (datos de ayuda) , puedan ser públicos. Las dos técnicas mas empleadas en sistemas de cifrado han sido las denominadas Fuzzy Commitment y Fuzzy Vault. Fuzzy Comm itment es un esquema mas basico y mas simple que Fuzzy Vault. Como contrapartida, Fuzzy Commitment requiere que el vector de características sea un vector binario, ordenado y de longitud fija. Fuzzy
Commitment se implementa en las dos fases siguientes:
-Fase de registro: la característica biométrica se combina (usualmente mediante una operación XOR , en el caso de caracteristicas binarias) con una palabra código generada mediante la aplicación de un código correc10r de errores a un número aleatorio, clave o palabra de paso (contrase~a). El resultado es una información de
ayuda que no necesita ser almacenada de forma segura.
-Fase de verificación o recuperación de secreto: la nueva característica biometrica, ligeramente diferente a la que se obtuvo durante el registro (lo cual es habitual). se combina con la información de ayuda, que es pública, para recuperar la palabra código (aplicando un código corrector de errores). A partir de la información recuperada en
esta fase, también se puede generar una clave criptográfica.
Hoy en dia, la mayoría de los métodos de identificación por huella dactilar reportados (así como los sistemas de cifrado basados en ellos) emplean vectores de características y técnicas para e:xtraerlos y compararlos que no son adecuados para dispositivos electrónicos con recursos de cómputo y almacenamiento reducidos. Por 35 eso son necesarias soluciones de identificación por huella dactilar válidas para sistemas de cifrado que, manteniendo buenos resultados de reconocimiento, sean adecuadas para dispositivos electrónicos de bajo consumo de potencia, con capacidad de cálculo limitada y que no requieran un -hardware" potente ylo voluminoso que emplee grandes recursos.
DESCRIPCiÓN DE LA INVENCiÓN
Se propone un metodo y un dispositivo para implementar el metodo que permiten,
mediante una serie de procesos y a partir de una imagen capturada de una huella dactilar, generar un vector de características basado en características de nivel 1, en concreto en la segmentación de la imagen direccional en regiones homogeneas. El metodo permite obtener una cadena de bits de longitud fija a partir de la huella capturada preferentemente en linea mediante un sensor de huella de los que se emplean en los sistemas automáticos de identificación (óptico, capacitivo, etc.).
En una posible realización el metodo aquí descrito puede ser adaptado y emplearse en aplicaciones de clasificación en las que las huellas de los individuos se distribuyen en grupos más o menos disjuntos, según el algoritmo de agrupamiento que se aplique 20 sobre los vectores de características. El método tambien puede emplearse en aplicaciones de indexado e identificación/autenticación, en las que se registran los individuos mediante los vectores de características que se generan en una fase de indexado o registro. En la fase de recuperación o verificación, dada una huella de entrada, se genera una lista ordenada de individuos candidatos a poseer esa huella (en el indexado) o se identifica el mejor candidato (en aplicaciones de identificación). En el caso de autenticación, se registra un solo individuo y en la fase de verificación se mide la similitud entre el vector generado y el almacenado. Si supera un umbral, el individuo se autentica. No se autentica en otro caso.
El metodo aquí descrito se puede emplear en multi-biometría. Dadas varias muestras de huellas capturadas de dedos diferentes de un mismo individuo, los vectores obtenidos de cada dedo se concatenan para obtener un vector de Identificación digital del individuo. Y tambien, dadas varias muestras de huellas capturadas de un mismo dedo, los vectores obtenidos de cada muestra se concatenan para obtener un vector
de identificación de la huella.
El método puede emplearse en aplicaciones de identificación (y autenticación) por doble factor porque el vector que genera puede combinarse facilmente con vectores derivados de claves o contraserias.
El método puede emplearse en los denominados esquemas de protección de plantilla nemplate~). En particular. es muy adecuado para sistemas de cifrado basados en la tecnica Fuzzy Commitment, porque el vector generado es binario, ordenado y de longitud fija. En estos esquemas, el método de la invención ofrece las ventajas de noreversibilidad de los vectores transformados y diversificación de los vectores generados, manteniendo la precisión en la identificación (y autenticación).
El método propuesto en esta invención puede implementarse en un dispositivo electrónico de bajo coste (con recursos de cómputo y memoria reducidos). como por ejemplo, una FPGA o un circuito integrado de aplicaciones específicas, ofreciendo 15 buenas prestaciones en cuanto a tiempos de extracción de características (situando los por debajo del milisegundo para tamarios de huellas estándares) , tiempos de emparejamiento y ordenación de candidatos (valores despreciables de pocos nanosegundos por candidato) así como requerimientos de memoria (poco más de 100 bytes por huella). As; se puede conseguir una solución muy segura porque toda la información biométrica de los individuos puede estar confinada dentro del mismo dispositivo electrónico y no salir de él.
El objeto de la invención se basa en un contexto de aplicación en línea, es decir, el usuario del dispositivo colabora para identificarse, a diferencia de otros contextos de 25 aplicación de identificación por huella dactilar, como el forense o el policial, en los que el usuario no colabora (porque esta fallecido o no desea que lo identifiquen). En un contexto de aplicación en el que el individuo quiere registrarse e identificarse. las características se extraen con calidad. En cualquier caso, el dispositivo que implementa la invención permite evaluar la calidad del proceso y la interacción en línea con el usuario para evitar capturas defectuosas de huellas.
El metodo de identificación se basa en generar un vector de características de la huella dactilar para su identificación a partir de una primera imagen de la misma en escala de grises que contiene crestas y valles de la huella, para ello se llevan a cabo los siguientes pasos: a) determinar para cada pixel de la primera imagen, PII (donde ij hacen referencia a la fila y columna del pixel en la imagen) , el gradiente de la intensidad de la imagen (de los niveles de grises) en ese pixel, b) determinar la dirección del gradiente mediante un ángulo a~ con respecto a un eje de referencia,
e) dividir el intervalo de valores posibles de ángulos, a¡¡:, en G sub·intervalos (9"... , 9G) que no se solapan y cuya unión da Jugar al intervalo completo de posibles valores, englobando cada sub-intervalo 9k angulas desde un valor
O k_l hasta ak,
d) etiquetar cada Qk sub-intervalo con una etiqueta, Ck ,
e) asociar, para cada pixel Pij de la primera imagen, la etiqueta correspondiente al sub-intervalo al que pertenece el angula aij correspondiente a ese pixel,
f) generar una segunda imagen a partir de la primera imagen, donde en dicha segunda imagen cada pixel lleva asociado una etiqueta, g) realizar un proceso de suavizado a la segunda imagen para obtener zonas que comprenden pixeles con las mismas etiquetas, h) localizar al menos un punto núcleo convexo en la segunda imagen suavizada, i) definir una ventana centrada en el punto núcleo convexo, j) realizar un muestreo de pixeles comprendidos en la ventana, y k) generar el vector a partir de las etiquetas de los pixeles muestreados en el
paso anterior, de forma ordenada.
La determinación del sub-intervalo al que pertenece el angula ex del gradiente en un pixel se determina a partir del calculo del gradiente horizontal (G.l y del gradiente vertical (Gy) de la intensidad de la imagen (de los niveles de grises) en ese pixel.
La determinación del sub-intervalo gk = [a..¡, Ok) que se le asocia al pixel p¡j comprende:
• determinar el signo de G.
• determinar el signo de Gy
• determinar que :
• o pertenece al primer cuadrante de angulas comprendido entre 0° y 90°, cuando G. y G~ tienen el mismo signo, y, dentro de este primer cuadrante se distinguen dos situaciones según el rango de angulos que abarca cada sub-intervalo a evaluar:
-si el sub-intervalo que se evalúa, [Uk.\ , (l~) , esta totalmente incluido en el primer cuadrante, porque tanto ak.' como Uk son menores o iguales que 900, entonces
-si el sub-intervalo que se evalúa, [ak.1, ak) , esta parcialmente incluido en el primer cuadrante, porque Clk_' es menor que 90" pero ak es mayor que 90", entonces
10 • a pertenece al segundo cuadrante comprendido entre 900 y 1800 ,
cuando Gx Y Gy tienen signos distintos, y, dentro de este segundo
cuadrante se distinguen dos situaciones según el rango de angulas que
abarca cada sub-intervalo a evaluar:
15 -si el sub-intervalo que se evalua , (ak.1, a k) , esta totalmente incluido en el
segundo cuadrante , porque tanto ak., como ak son mayores o iguales
que 90", entonces
si el sub-intervalo que se evalúa, Ia....,. ak}, esta parcialmente incluido en el segundo cuadrante, porque ak es mayor que 90" pero o.k., es menor que 90", entonces El proceso de suavizado calcula para cada pixel P'j de la segunda imagen preferentemente cual de las etiquetas es la que mas veces aparece en una ventana de tamafio S x S píxeles de la segunda imagen, ventana centrada en el pixel a suavizar, donde S se puede factorizar como S= 51 x 52 x. x sn, proceso que comprende:
• comenzar con ventanas de tamaño s1 x s1 píxeles y aplicarles el 30 suavizado a sus s1 x s1 etiquetas ,
• continuar con ventanas de (s 1 x s2) x (s 1 x s2) píxeles y aplicar el suavizado sobre s2 x 52 etiquetas suavizadas previamente en el paso anterior,
• proceder así hasta llegar al tamario de ventana (51 x 52 x.. x sn) x (s1 35 x s2 x.. x sn) píxeles y aplicar el suavizado sobre sn x sn etiquetas
suavizadas previamente en el paso anterior
La determinación del núcleo convexo puede llevar a cabo los siguientes pasos:
• hacer otra división del intervalo de valores posibles de angulos, ct.j, en 4 sub
intervalos (9\,... , g'4) que no se solapan y cuya unión da lugar al intervalo completo de posibles valores,
• etiquetar cada g'k sub-intervalo con una etiqueta, C'k,
• convertir la segunda imagen suavizada, en la que a cada uno de los píxeles se le asocia una de entre G etiquetas (Cl... , cG) , donde-preferiblemente G > 4, en
una imagen tetra-direccional suavizada, en la que a cada uno de los píxeles se le asocia una de entre cuatro etiquetas (C'1 •... , C'4) y la conversión comprende a su vez:
• cambiar cada etiqueta Ck asociada al sub-intervalo de angulas Qk por
aquella etiqueta C'k asociada al sub-intervalo de angulas g 'k que verifique que la 15 intersección gk n g'k sea la mayor, y
• determinar el núcleo convexo como el punto donde se tocan tres de cuatro regiones homogéneas de la Imagen tetra-direccional suavizada, que son regiones que engloban la mayoría de las crestas con curvatura convexa Asimismo la invención aquí descrita también esta dirigida como otro objeto de la misma a un dispositivo para generar un vector de características de una huella dactilar a partir de una imagen de la misma, dispositivo que se encuentra asociado a unos medios de captura de imagen de la huella y caracterizado porque comprende:
• un bloque de asignación de etiquetas destinado a asignar a cada pixel de la imagen una de entre G etiquetas posibles, que permite generar la segunda imagen,
• un bloque de suavizado destinado a realizar un proceso de suavizado a la segunda imagen para obtener zonas que comprenden pixeles con las mismas etiquetas,
• un bloque de determinación del núcleo convexo en la huella, destinado a localizar al menos un punto núcleo convexo en la segunda imagen suavizada,
• un bloque de ventana destinado a definir una ventana centrada en el punto núcleo convexo, realizar un muestreo de pixeles comprendidos en la ventana, obtener la etiqueta de cada pixel muestreado y generar el vector a partir de las etiquetas obtenidas de forma ordenada El bloque de asignación de etiquetas comprende:
• un filtro preferiblemente de Sobel 3x3 con mascaras de convolución con valores enteros y potencias de 2 para calcular los gradientes horizontales (G~) 5 y los gradientes verticales (Gy) de la intensidad de la imagen (de los niveles de grises) en los pixeles, y
• operadores lógicos tipo OR y ANO, operadores relacionales y operaciones de valor absoluto y multiplicación por valores constantes El bloque de suavizado se encuentra adaptado para procesar la segunda imagen barriendo sus pixel es de uno en uno y proporcionar los píxeles de la imagen suavizada también de uno en uno, donde el bloque de suavizado define una ventana de tamaño SxS, donde S se puede factorizar como S= s1 x s2 x... x sn, y donde el bloque de suavizado comprende una serie de registros y n sub-bloques con una arquitectura 15 híbrida serie-paralelo de los que:
• un primer sub-bloque con tamaño de ventana 51 x s1 esta adaptado para aplicar una función de suavizado en paralelo sobre s1 x s1 etiquetas de píxeles que se han ido almacenando en Jos correspondientes registros, sub-bloque cuya etiqueta resultante se va almacenando una tras otra en una serie de 20 registros;
• un segundo sub-bloque con tamarío de ventana (s1 x 52) x (51 x 52) esta adaptado para aplicar una función de suavizado en paralelo sobre s2 x s2 etiquetas suavizadas previamente por el primer sub-bloque y disponibles en los correspondientes registros que almacenan la salida del primer sub-bloque, sub
bloque cuya etiqueta resultante se va almacenando una tras otra en una serie de reg istros;
• así hasta un sub-bloque enésimo con tamarlo de ventana (s1 x s2 x... x sn) X (s1 x s2 x x sn) , que de nuevo aplica la función de suavizado en paraleJo sobre sn x sn etiquetas suavizadas previamente por el sub-bloque anterior y
disponibles en los correspondientes registros que almacenan la salida del subbloque anterior, sub-bloque cuya salida proporciona la etiqueta del pixel en la imagen suavizada.
El bloque de determinación del núcleo convexo comprende: 35 • un sub-bloque del bloque de determinación del núcleo convexo adaptado para convertir la segunda imagen suavizada en una imagen tetra-direccional,
preferentemente truncando los 1092G bits de cada pixel a 2 bits que codifican las etiquetas de la imagen tetra-direccional, y
• un sub-bloque del bloque de determinación del nucleo convexo adaptado para localizar al menos un punto núcleo convexo.
De manera adicional y en diversas realizaciones se puede disponer de:
• Un bloque de memoria destinado a almacenar la imagen capturada de la huella • Un bloque de mejora de la imagen destinado a procesar la misma mejorando 10 su calidad.
• Un bloque de fusión de información adaptado para: adquirir una clave o contraseña, aplicar una función no invertible (hash) a dicha clave o contraseña y combinar el resultado del paso anterior con el vector de características de la huella.
Dado que el dedo, la huella, no siempre se encuentran orientados de la misma manera respecto al sensor, se contempla la opcion de incluir un bloque de orientación de la imagen destinado a girar o rotar la misma hasta una posición determinada en el caso 20 de que la huella captada por los medios de captura de imagen de la huella no se encuentre en una orientación determinada, bloque que preferentemente gira por angulas fijos para aplicar transformaciones lineales entre pixeles originales (x" Yi) y píxeles de las imagenes rotadas (XI, YI) con los parametros de la transformación lineal fijos para cada giro, y bloque que en una realización posible puede ser programable en el número de rotaciones así como los parámetros asociados a las rotaciones.
En el caso de protección de plantilla ("template~) , el dispositivo que implementa el método adicionalmente puede comprender:
• Un bloque de adquisición adaptado para adquirir un número aleatorio, clave o contraseña y aplicar un codificador de un código corrector de errores para generar un secreto ,
• Un bloque con operadores XOR adaptado para calcular y almacenar unos datos de ayuda públicos a partir del vector de características de la huella y el 35 secreto y
• Un bloque decodificador de un código corrector de errores adaptado para N° solicitud F.Erccliva F.OEPM
30/10/2015 02/11/2015
recuperar un secreto a partir de una extracción del vector de características y de los datos de ayuda almacenados de la huella asociada al secreto Todos los bloques descritos anteriormente pueden incluirse en un dispositivo electrónico de bajo coste que, ademas, permite interactuar con el usuario en base a la evaluación de la calidad con unos indicadores extraídos fundamentalmente de la operación de suavizado. El dispositivo puede contar con LEOs para comunicar al usuario con un sencillo código de colores que la huella ha sido adquirida con buena calidad y/o el dedo ha sido bien colocado sobre el sensor (por ejemplo, un LEO
iluminado en verde indica proceso correcto y en rojo indica error). El dispositivo puede comunicar al usuario información mas extensa sobre la captura (de forma visual mediante un pequer"io panel LCO o de forma audible mediante un sintetizador de voz sencilla) , como por ejemplo "el dedo se ha colocado demasiado abajo en el sensor". Puesto que el contexto de aplicación es en linea y el usuario esta presente. esta información puede traducirse en que el usuario introduzca otra vez su dedo en el sensor (mas arriba o abajo, con más o menos presión, etc , según la información que reciba del dispositivo). En tal caso, si el dispositivo incluye un panel LeO y/o un sintetizador de voz para la interacción en línea con el usuario a la hora de capturar la huella, éstos también se pueden aprovechar para comunicar hacia el exterior elllos candidato/s seleccionado/s en el proceso de reconocimiento.
La interacción en linea con el usuario proporciona muestras biométricas de calidad , que, por tanto, reducen las tasas de error que se obtienen para unas tasas bajas de penetración en la base de huellas y la tasa promedio de penetración en un escenario de búsqueda incremental ("incremental search scenario") en una aplicación de indexado. Como consecuencia, el promedio de candidatos entre los que siempre aparece el poseedor de la huella de entrada es un porcentaje pequeño de toda [a base. También mediante la interacción con el usuario se mejoran las razones de falso rechazo (FRR) y falsa aceptación (FAR) para una aplicación de identificación.
DESCRIPCiÓN DE LOS DIBUJOS
Para complementar la descripción que se esta realizando y con objeto de ayudar a una mejor comprensión de las características de la invención, de acuerdo con un ejemplo preferente de realización practica de la misma, se acompar"ia como parte integrante de dicha descripción, un juego de dibujos en donde con caracter ilustrativo y no limitativo, se ha representado lo siguiente:
Figura 1. Muestra un gráfica donde se aprecia la tasa de error frente a la tasa de penetración obtenida con el método de la invención aplicada a tres bases de huellas: la FVC2000 082a y la FVC2002 081 a (de las bases de huellas de MFingerprint Verification Competition-) y una base de huellas generada a partir de usuarios de un sistema experimental de identificación en línea.
Figuras 2a-2d. Muestran unas gráficas donde se representa la razón de falsa aceptación (FAR) y de falso rechazo (FRR) frente a un umbral que mide el porcentaje de etiquetas diferentes entre los vectores de características obtenidos con el método de la invención aplicado a la base de huellas en linea: (a) Sin aplicar fusión multibiométrica. (b) Con fusión (operador mínimo) de 3 muestras por huella en la fase de registro. (e) Con fusión (operador suma) de 2 dedos y (operador mínimo) de 3 muestras por dedo en la fase de registro. (d) Con fusión de una muestra de un dedo y contraseña.
Figuras 3a-3d. Muestran unas imágenes donde se aprecian posibles resultados de los pasos basicos del método para generar un vector de características de una huella dactilar: (a) Primera imagen de la que parte el método, una imagen en escala de grises captada por un sensor óptico de huella dactilar (tomada de la FVC2002 081). (b) Segunda imagen suavizada, con regiones homogéneas de etiquetas, donde cada pixel lleva asociado una de entre ocho etiquetas (cada una de las ocho etiquetas se representa por una trama diferente). (cl Ventana con información distintiva centrada en el punto núcleo convexo. (d) Pixel es muestreados de la ventana para obtener el vector de características.
Figura 4 -Muestra el diagrama de bloques funcionales de un dispositivo que extrae un vector de características distintivo de una huella dactilar. Los bloques dibujados con línea discontinua se usan o no según la aplicación.
Figura 5. Muestra una representación del bloque de suavizado 27 x 27 que emplea tres sub-bloques: un primer sub-bloque de tamaño de ventana 3 x 3, que suaviza 3 x 3
pixeles; un segundo sub-bloque de tamaño de ventana 9 x 9, que aplica suavizado sobre 3 x 3 resultados del sub-bloque anterior; y, por último un sub-bloque 27 x 27, que apljca suavizado sobre 3 x 3 resultados del sub-bloque anterior.
Figura 6. Muestra el diagrama de bloques funcionales de un dispositivo que implementa un método de indexación e identificación/autenticación por huella y posible clave: (1A) Fase de registro sin clave (2A) Fase de verificación sin clave (1 8) Fase de registro con clave (28) Fase de verificación con clave. Los caminos Que no se marcan se usan tanto en la fase de registro como en la de verificación. Los bloques y caminos dibujados con linea discontinua se usan o no segun la aplicación.
Figura 7. Muestra el diagrama de bloques funcionales de un dispositivo que 10 implementa un sistema de cifrado biometrico de identificaciónJautenticación por huella:
(1) Fase de registro (2) Fase de verificación. Los caminos que no se marcan se usan tanto en la fase de registro como en la de verificación. Los bloques y caminos dibujados con linea discontinua se usan o no segun la aplicación.
REALIZACiÓN PREFERENTE DE LA INVENCiÓN
A la vista de las figu ras se describe a continuación un modo de realización del objeto 20 de la invención aquí descrita El método de la invención se ha implementado en un dispositivo electrónico también objeto de esla invención; para una realización particular del dispositivo se selecciona una implementación en una FPGA de Xilinx, una Virtex 6 XC6VLX240T-3FFG1 156,
que contiene 37680 slices y 416 bloques RAM de 36 Kbits. El método de la invención también se podría implementar en un circuito integrado de aplicación específica (ASIC) ; en tal caso, el dispositivo electrónico seria aun más pequefio, consumiria menos potencia y pOdria integrarse con sensores de huellas (por ejemplo, de tipo capacitivo) que emplean tecnologías eMOS.
En una realización preferida del método de identificación de huellas dactilares a partir de una extracción de vectores de caracleristicas de la invención se ha implementado de la siguiente manera. Un bloque asigna a cada píxel de una imagen, correspondiente a una huella dactilar, una de entre ocho etiquetas posibles, 35 empleando 3 bits para codificar las etiquetas, 8 bits para codificar intensidades (Iuminancias) de la imagen de la huella en escala de grises y 14 bits para los gradientes (obtenidos mediante filtros de Sobel 3x3) , generándose una segunda N° solicitud F.Erccliva F.OEPM
30/10/2015 02/11/2015
imagen.
Un bloque que aplica suavizado sobre la segunda imagen emplea un bloque de suavizado 3x3 conectado en cascada con otro bloque 9x9, conectado en cascada con 5 otro bloque 27x27. Un bloque detecta el núcleo convexo de la huella como el punto donde intersectan tres de las cuatro regiones de la imagen tetra-direccional suavizada.
La segunda imagen suavizada se procesa para seleccionar una ventana distintiva centrada en el núcleo convexo. En este caso la ventana tiene unas dimensiones de 10 129x129 píxeles, muestreada de 8 en 8 pixeles, es decir, que se genera una cadena de 867 bits por huella capturada. La implementación incluye, ademas, bloques para calcular indicadores de calidad, una memoria para almacenar la imagen de la huella en escala de grises y un bloque que aplica una rotación sobre la imagen en escala de grises almacenada en la memoria. Todo ello ocupa el 18.31% de los slices yeI15.87% 15 de los bloques RAM, pudiéndose alcanzar una frecuencia maxima de operación de 257.7 MHz y considerando una huella con 374 filas x 388 columnas (como las de la FVC 2002 081). Aplicando un procesado pixel a pixel de la huella, esto significa que el tiempo en obtener los 867 (17x17x3) bits del vector de características de una captura (sin rotaciones) puede ser de 0.56 ms (374 x 388 f 2577 I-Is).
Si se tienen en cuenta 3 rotaciones de la huella para registrar a un usuario, se almacenan vectores de 2601 (3 x 17 x 17 x 3) bits por usuario. En la FPGA Virtex 6 considerada, pueden almacenarse los vectores de casi 5900 usuarios en los 416 bloques RAM de 36 Kbits.
El bloque que ordena los niveles de similitud entre el vector de entrada y los almacenados, que aplica un me lodo de inserción y genera una lista con 50 candidatos, ocupa el 11.48% del total de slices de la FPGA Virtex 6 que estamos considerando y permite una frecuencia maxima de 207.5 MHz. Esto significa que el tiempo invertido en la fase de recuperación es bastante bajo (varias décimas de milisegundo para ordenar 5900 usuarios).
El mismo dispositivo, en este caso la misma FPGA, puede incluir todos los bloques requeridos por las fases de indexado y recuperación del método de la invención. En el
caso de la Virtex 6 XC6VLX240T-3FFG1156 de Xilinx como dispositivo único, 66 bloques RAM de 36 Kbits se emplean para almacenar la huella y la ventana distintiva (considerando una huella con 374 filas x 388 columnas como las de la FVC 2002 081)
y se dispone de 350 bloques RAM de 36 Kbits. que permiten registrar más de 4950 usuarios (considerando 2601 bits por usuario)
El método de la invención, implementado en este ejemplo de realización FPGA, se ha evaluado con dos de las bases de huellas de ~Fingerprint Verification Compet¡tion~: la FVC2000 OB2a y la FVC2002 OB1 a, con 800 capturas cada una. Hay que tener en cuenta que bases como las FVC estan construidas con muchas capturas de mala calidad y mal adquiridas para probar la bondad de técnicas complejas de identificación e indexado. Además, también se ha considerado una base de huellas con 560 capturas, generada a partir de usuarios de un sistema experimental de identificación en línea.
La colocación del dedo es importante para extraer correctamente el vector de características. En el contexto de aplicación en línea en el que el usuario quiere identificarse, el dedo se suele colocar adecuadamente. Por ejemplo, en el experimento de registro de usuarios en línea en el que se capturaron 560 huellas, 23 capturas no permitieron extraer la ventana distintiva (4.11 %). En las bases de huellas FVC2000 OB2 y FVC2002 OB1 , con 800 capturas, coma el contexto de aplicación es distinto, el número de capturas de las que no puede extraerse correctamente el vectar de características es bastante superior: 149 en la FVC20aO 082 (18.6%) Y 104 en la FVC2002 DSl (13%).
La calidad de la imagen capturada también es importante evaluarla, pues en una captura de 560 huellas, 10 capturas (1.79%) fueron de muy mala calidad (porque las huellas realmente estaban deterioradas). En las bases de huellas FVC2000 OB2 y FVC2002 081 , 16 (2%) Y 24 (3%) capturas son también de muy mala calidad (debido a huellas deterioradas o capturas no bien adquiridas).
La Figura 1 representa la tasa de error frente a la tasa de penetración obtenida con la técnica de la invención implementada en este ejemplo de realización y aplicada a las tres bases de huellas consideradas. Para obtener esta figura, en todas las bases se han eliminado las huellas de las que no se puede extraer su vector de características correctamente y que son de muy mala calidad (los porcentajes comentados anteriormente) , puesto que con el dispositivo de la invención, que interactúa con el 35 usuario, estos porcentajes se hubieran reducido a cero. Se ha aplicado una mejora sobre las imágenes en escala de grises (aplicando filtros complejos) y reforzado la técnica de detección del núcleo convexo. Como vectores de características registrados en la base se han tomado los de la primera captura de cada individuo (con 5 rotaciones en la FVC2002 081 , 3 rotaciones en la FVC 2000 082, Y ninguna en la tercera de las bases). Como vectores de entrada se han tomado todos los del resto de capturas, sin ninguna rotación. Para calcular el nivel de similitud entre el vector de entrada y los almacenados previamente rotados (en el caso de las FVC2002 081 y FVC 2000 082) se ha seleccionado el máximo de los niveles de similitud con cada uno de los almacenados La tasa promedia de penetración que hay que llevar a cabo cuando no se quieren cometer errores en la recuperación del poseedor de la huella de entrada ("incremental search scenario") , en las mismas condiciones que los resultados de la Figura 1, ha sido 3.16% en la FVC2000 082, 2.88% en la FVC2002 DBl y 1.62% en la tercera de las bases analizadas El mismo dispositivo, en este caso la misma FPGA, puede incluir una implementación de la función hash ganadora de la última competición SHA-3 del NIST, Keccak, para permitir la identificación/autenticación por el doble factor de ~quién eres· y "lo que sabes· Esta función para generar 512 bits ocupa 1188 slices (3.1 5% del total) permitiendo una frecuencia máxima de 435.3 MHz.
La Figura 2 representa la razón de falsa aceptación (FAR) y de falso rechazo (FRR) frente a un umbral que mide el nivel de disimilitud (porcentaje de etiquetas diferentes entre los vectores de características). Los resultados corresponden a la base de huellas con capturas en linea. La Figura 2a ilustra los resultados de una identificación sin fusión biométrica. El valor donde las razones se intersectan (EER) es 5.4%. La Figura 2b ilustra los resultados de una identificación con fusión de 3 muestras capturadas por cada huella del individuo en la fase de registro y una muestra capturada en la fase de verificación. El valor donde las razones se intersectan (EER) es 2.5%. La Figura 2c ilustra los resultados de una identificación con fusión de 2 dedos por individuo, con 3 muestras capturadas por cada dedo en la fase de registro y una muestra capturada por cada dedo en la fase de verificación. El valor donde las razones se intersectan (EER) es 0.9%. La Figura 2d ilustra los resultados de una identificación con fusión de los vectores de características con una función hash que devuelve 512 bits aplicada sobre una palabra de paso o contraseña para cada individuo. El valor
donde las razones se intersectan (EER) es 0%.
El mismo dispositivo, en este caso la misma FPGA, puede incluir todos los bloques N° solicitud F.Erccliva F.OEPM
30/ 10/2015 02/11/2015
requeridos por la técnica de protección del método de la invención. En el caso de la Virtex 6 XC6VLX240T-3FFG1156 de Xilinx como dispositivo único, el bloque codificador de Reed-Solomon para n"'511 y k"'383 ocupa 473 slices (1.26% de los slices) y permite operar a una frecuencia máxima de 415 MHz. El bloque decodificador
de Reed-Solomon para n=511 y k=383 ocupa 24.763 slices (el 65% del total de slices) trabajando con una frecuencia máxima de 78.5 MHz.
De manera mas detallada el método para generar un vector de características de una huella dactilar genera el vector Que es una cadena de bits de longitud fija que 10 representa de forma compacta una huella dactilar. Para obtener ese vector, y tal y como se ha detallado anteriormente, se parte de una primera imagen como por ejemplo la captura de la huella como imagen en escala de grises (Figura 3a) , se determina para cada píxel el gradiente de ) a intensidad de la imagen (de los niveles de grises) en ese pixel , y se determina la dirección del gradiente mediante un angula con 15 respecto a un eje de referencia. El intervalo de valores posibles de ángulos se divide en G sub-intervalos (gl,.. , gG) que no se solapan y cuya unión da lugar al intervalo completo de posibles valores, cada sub-intervalo g~ englobando ángulos desde Uk.l hasta 0k. A cada sub-intervalo, gk, se le asocia una etiqueta, Ck. A cada pixel de la imagen de la huella se le asocia la etiqueta correspondiente al sub-intervalo al que 20 pertenece el angula de la dirección del gradiente en ese pixel. Como resultado, se genera una segunda imagen a partir de la primera imagen de la huella, donde en dicha segunda imagen cada píxel lleva asociado una etiqueta. A continuación, se realiza un proceso de suavizado a la segunda imagen para obtener zonas que comprenden pixeles con las mismas etiquetas (Figura 3b). Se localiza al menos un punto núcleo convexo en la segunda imagen suavizada y se define una ventana centrada en el punto núcleo convexo (Figura 3c). Se realiza un muestreo de píxeles comprendidos en la ventana (Figura 3d). Las etiquetas de los píxeles muestreados, ordenadas, generan el vector de características de la huella. Si las eliquetas se codifican con bits, el vector es una cadena de bits ordenada y de longitud fija.
Si el número de etiquetas, G, considerado es pequeño (por ejemplo, cuatro etiquetas) , el vector que se va a generar es poco distintivo de la huella, es decir, puede haber muchas huellas con un vector parecido, lo que se traduce en una tasa elevada de falsa aceptación, en el caso de una aplicación de identificación/autenticación. Si puede 35 emplearse un número como cuatro etiquetas en aplicaciones de clasificación, en las que las huellas se distribuyen en grupos pre-establecidos de acuerdo a la similitud de sus vectores de características, de forma que la huella de entrada se clasifica en uno de esos grupos o se le asignan grados de pertenencia a varios de esos grupos.
Por el contrario, si se contempla un nümero de etiquetas alto (por ejemplo, dieciséis etiquetas) , el vector que se va a generar es muy distintivo, pero cambia demasiado para diferentes capturas de una misma huella, lo que se traduce en una tasa elevada de falso rechazo, en el caso de una aplicación de identificación/autenticación. En una realización preferente del método de la invención para aplicaciones de identificación/autenticación, se han elegido ocho etiquetas, que es el caso que se ilustra en la Figura 3.
Los sub-intervalos deben cubrir todo el rango de ángulos que pueden tener las direcciones de los gradientes (entre 0° y 18 (0) de una forma más o menos espaciada. En una realización preferente de la invención para aplicaciones de identificación/autenticación con G=8, se han elegido los siguientes: gl = (0°, 22.5°) , g2
=[22.5', 45') , 93 =[45', 67.5') , 9. =[67.5', 90') , 9, =[90', 112.5') , g, =[112.5', 135') ,
g7 = (135°, 157.5°) Y g8 = (157.5°, 1800) , eligiendo como eje de referencia el eje longitudinal de la huella.
El tama~o de la ventana centrada en el nüc!eo convexo depende del sensor empleado. 20 Por ejemplo, para las huellas de las bases FVC2002 OSl (imágenes de 388x374 pixeles capturadas mediante un sensor óptico) , las de la FVC2000 OB2 (imágenes de 256x364 pixeles capturadas mediante un sensor capacitivo de bajo coste) y las de una base experimental (imágenes de 440x300 pixeles capturadas mediante un sensor óptico) , se ha probado que una ventana adecuada es de 129x129 pixeles (Figura 3c). 25 Como representación distintiva y compacta de la huella no son necesarios todos los píxeles de la ventana, sino que se aplica un muestreo l /n r down-sampling H ) que
,
significa emplear, preferentemente, 1 de entre n píxeles consecutivos en cada fila de la ventana. Por ejemplo, para las huellas de las bases citadas anteriormente, se aplica un muestreo 1/8 sobre la ventana de 129x129 píxeles, que significa emplear la información de 17x17 pixeles (Figura 3d). En este ejemplo, si las ocho etiquetas se codifican con 3 bits, el vector obtenido para cada huella es una cadena de 17x17x3 = 867 bits = 108.4 Bytes. Estos vectores pueden cifrarse, por motivos de seguridad, y/o comprimirse (por ejemplo aplicando "Run-Length Encoding") , para consumir menos memoria y/o transmitirse más fácilmente.
La técnica para extraer los vectores de caracteristicas de las huellas se implementa mediante el empleo de los siguientes bloques básicos (Figura 4) :
N° solicitud F.Efccfiva F.OEPM
30/10/2015 02111/2015
• Un sensor de huella, que proporciona una imagen de la huella en escala de grises. Si el sensor no aplica mejoras sobre la imagen adquirida, se incluye un bloque de mejora de la imagen
• Si la posición del dedo sobre el sensor de huella puede rotar, también se
incluye un bloque que aplica rotación a la imagen de entrada en escala de grises
• Un bloque que asigna a cada pixel de la imagen una de entre las G etiquetas posibles y genera una segunda imagen.
• Un bloque que aplica suavizado a la segunda imagen.
• Un bloque para detectar el núcleo convexo (o varios puntos candidatos a ser núcleo convexo) en la huella.
• Un bloque para determinar la ventana distintiva, muestrear sus píxeles y almacenar los valores de las etiquetas de esos plxeles en una cadena de bits.
• Adicionalmente, se puede incluir un bloque que evalúa la calidad de todo el 15 proceso y permite la interacción en linea con el usuario.
El bloque que asigna a cada pixel de la imagen una de entre las G etiquetas posibles puede implementarse mediante un sencillo circuito digital. El primer paso que lleva a cabo este bloque es calcular los gradientes horizontales (GlI) y verticales (Gy) de la 20 intensidad de la imagen (de los niveles de grises) con algún filtro adecuado para su implementación hardware (por ejemplO, mediante filtros de Sobel 3 x 3 que emplean máscaras de convolución con valores enteros y potencias de 2). Este paso es habitual en cualquier técnica de extracción de características. A continuación, en vez de calcular en cada pixel la dirección del gradiente de una forma mas o menos exacta 25 mediante una función trigonométrica (en hardware dedicado, se emplea usualmente un procesador CORDIC, "COordinate Rotalion Digital Computer-, para calcular el ángulo a cuya tangente es (G¡Gx) ) y luego calcular el sub-intervalo de entre los G posibles al que pertenece a, la técnica de esta invención compara entre si los valores de los gradientes G" y Gy Y aplica operadores lógicos (OR y ANO) , operadores relacionales y operaciones de valor absoluto y multiplicación por valores constantes, que es mucho mas eficiente desde un punto de vista hardware. En primer lugar, el bloque determ ina que a pertenece a un primer cuadrante comprendido entre 0° y 900, cuando G" y Gy tienen el mismo signo. En segundo lugar, dentro de este primer cuadrante, el bloque determina que:
-si el sub-intervalo que se evalúa , l (l~." (l~) , está totalmente incluido en el primer cuadrante, porq ue lanlo (l~. , como (l~ son menores o iguales que 900, entonces
-si el sub·intervalo que se evalua. [O~.l , w.) está parcialmente incluido en el primer cuadrante, porque a~.1 es menor que 90° pero Qk es mayor que 90°, entonces
El bloque determina que a pertenece a un segundo cuadrante comprendido entre 900 10 Y 1 BOo, cuando Gx y Gy tienen signos distintos. En tal caso, dentro de este segundo cuadrante, el bloque determina que:
si el sub· intervalo que se evalúa, [a...1, O~) , está totalmente incluido en el segundo cuadrante, porque tanto U¡,.1 como Ok son mayores o iguales 15 que 900, entonces. si el sub-intervalo que se evalúa, [Q¡,.1, O~) , esta parCialmente incluido en el segundo cuadrante, porque Ok es mayor que 90° pero a.k_l es menor que 90°, entonces Donde tan (a.k) y tan{ak.') son valores constantes previamente conocidos una vez se han fijado los sub-intervalos a considerar, Qk = [ak.l, (lk).
El circuito digital Que implementa estas operaciones puede emplear aritmética de punto fijo, y palabras de log2G bits para codificar las G etiquetas posibles correspondientes a los G sub-intervalos gk.
El bloque de suavizado aplica un tamarlo de ventana S x S, donde S depende, en general, del tipo de sensor de huella empleado. Como suavizar en paralelo S x S pixeles (para conseguir elevada velocidad de procesado) puede ser muy costoso, se puede optar por conectar en cascada varios sub-bloques de suavizado uno tras otro. Si el valor de S se puede factorizar como S= s1 x 52 x. x sn: primero se puede usar
un sub-bloque con tamarlo de ventana s1 x 51 , que aplica la función de suavizado sobre sl x sl etiquetas de píxeles; el segundo sub-bloque con tamarlo de ventana (sl x s2) x (s1 x s2). que aplica la función de suavizado sobre s2 x s2 etiquetas suavizadas previamente por el sub-bloque anterior, y asi hasta el último sub-bloque con tamaño de ventana (sl x s2 x. x sn) x (s1 x s2 x... x sn) , que de nuevo aplica la 5 función de suavizado sobre sn x sn etiquetas suavizadas previamente por el subbloque anterior. Por ejemplo, para sensores ópticos que captan imagenes de 388x374
o 440x300 pixeles o sensores capacitivos que captan imágenes de 256x364 pixeles, se ha probado que es adecuado un bloque de suavizado 27 x 27 que se puede realizar con tres sub-bloques de suavizado conectados en cascada: un primer sub-bloque de 10 tamai"io de ventana 3 x 3, que suaviza 3 x 3 pixeles; un segundo sub-bloque de tamai"io de ventana 9 x 9, que aplica suavizado sobre 3 x 3 resultados del sub-bloque anterior: y, por último un sub-bloque 27 x 27, que aplica suavizado sobre 3 x 3 resultados del sub-bloque anterior (Figura 5). En una realización preferente, la función de suavizado sj x sj considera una ventana de pixeles en torno al pixel analizado y 15 asigna a éste el valor de la etiqueta que mas veces aparece en toda la ventana. La técnica de conectar n sub-bloques en cascada permite reducir el hardware requerido y la latencia del proceso de suavizado porque procesar S x S valores en paralelo es mucho mas costoso que procesar en paralelo sj x sj pixeles. Por ejemplo, si los pixeles de la imagen se van procesando uno a uno, el suavizado de toda la imagen se puede realizar con estos sub-bloques en cascada (y los bancos de registros necesarios) invirtiendo tantos ciclos de reloj como pixeles tenga la imagen.
El bloque que calcula el núcleo convexo (o los puntos candidatos a serlo) puede emplear técnicas ampliamente conocidas, como las basadas en el cálculo del indice 25 de Poincaré. Una ventaja del método de la invención es que permite reforzar la detección de este punto sin apenas coste computacional, como se describe a continuación. Partiendo de la segunda imagen suavizada , se obtiene directamente una imagen tetra-direccional suavizada. Por ejemplo, si G=8 y los ocho sub-intervalos son 9, = (O', 22.5') , 9, = (22.5', 45') , 9' = (45' , 675') , 9. = (67 5', 90') , 9, = (90', 112.5') ,
g6 = (112.5°, 135°) , g7 = [135°, 157.5°) Y g8 = [157.5°, 180°) , se pueden obtener directamente los siguientes cuatro sub-intervalos g'¡= g\ U g8, g'2= g2 U g3, 9'3= g4 U g5 Y g'4= g6 U g7. Puesto que cada pixel de la segunda imagen suavizada se representa por 3 bits, la obtención de la imagen tetra-direccional suavizada es tan simple como truncar de 3 a 2 los bits de cada pixel, si las etiquetas se codifican adecuadamente. El
núcleo convexo se puede determinar como el punto donde intersectan tres de cuatro regiones homogéneas de la imagen tetra-direccional suavizada, que son las tres regiones que engloban la mayoría de las crestas con curvatura convexa. Como la detección correcta del núcleo convexo es importante para extraer correctamente el vector de características, se pueden considerar varios puntos como candidatos y extraer los vectores de características asociadas a ellos.
La ttknica de la invención permite contemplar huellas adquiridas con el dedo rolado respecto al eje longitudinal del sensor. La ventana con información representativa de la huella descrita anteriormente está caracterizada por su invariancia ante traslaciones del dedo sobre el sensor puesto que el punto central de la ventana es el punto nücleo convexo. Sin embargo, la ventana no es invariante a rotaciones. Para asegurar que diferentes capturas de la misma huella adquiridas con posibles rotaciones presenten un nivel de similitud alto con su vector de caracteristicas correspondiente almacenado en la base, una solución con bajo coste en hardware es incluir un bloque que permite rotar la imagen de la huella en escala de grises. Pueden tenerse en cuenta R rotaciones previas a la obtención de la segunda imagen (por ejemplo, con R=5: -22.5°,
-11.25°, 0°, 11.25° Y 22.5°). Si la imagen capturada de la huella, cuyos pixeles tienen por coordenadas cartesianas (x" Yl) , se rota un angula ¡3 respecto al pixel de coordenadas (xc, Ycl, las coordenadas de los pixeles pasan a ser ahora (x" y, ). Esta operación se puede expresar matemáticamente como sigue:
o Xc cos (jJ) -sen (p) O· 1 O
-xi l·x'l [X'
O 1 y, sen (p) cos (P) O O 1 -Yc Yi = Yt O O 1 O O.0 O 1 1 1.
Por ejemplo, si el punto de giro se toma como el punto central de la imagen de la huella (para una imagen de 374 filas y 388 columnas, los valores para Xc e Yc son 187 y 194, respectivamente) , y el angula de rotación se elige como 11.25°, la expresión anterior se puede reducir a la siguiente:
0.9808 -0.1951
41.4407 IIX'I IX, ]
10.1951 0.9808 -32.7542 ~' = Y, Por ejemplo, si cada pixel de la imagen de entrada se direcciona por sus coordenadas (Xl, y, ) en la memoria donde se almacena la captura, el bloque que aplica una rolación de 11.25°, como la anterior, direcciona ahora a ese pixel por sus coordenadas (x" y, ). Como las rotaciones que se contemplan son fijas, este bloque implementa una 30 transformación lineal entre (Xi, YI) Y (X" y, ) con para metras constantes. por lo que no requiere el empleo de multiplicadores. En una realización posible de este bloque, el nümero de rotaciones puede ser programable así como los parametros asociados a las rotaciones.
Para hacer la técnica de clasificación, indexada o identificación robusta a rotaciones. se contemplan más o menos angulos según el nivel de rotación que se quiera 5 soportar. Las rotaciones se pueden contemplar en la fase de indexado o registro y/o en la fase de recuperación o verificación y no tienen por qué coincidir en número. Asi, por ejemplo, en la fase de indexado o registro, si se consideran P candidatos de núcleo convexo y V pixeles por ventana distintiva, se puede extraer una cadena de P x V x 3 bits par cada rotación, según lo comentado anteriormente. Si se contemplan R
rotaciones, el índice total que se emplea para representar una captura de huella concatena las R cadenas de bits, resultando un vector característico de una longitud de R x P x V x 3 bits.
El método genera un número de identificación digital (un vector de R x P x V x 3 bits)
que se le asocia al individuo poseedor de la huella, de forma que puede generarse una base can los N números asociadas a las N individuas registrados (los vectores pueden cifrarse, por motivos de seguridad, y/o comprimirse, para consumir menos memoria y/o transmitirse mas facilmente). En aplicaciones multi~biométricas que empleen O dedos por individuo, se genera para cada individuo un vector de O x R x P x V x 3 bits concatenando los O números de identificación que se obtienen a partir de la huella de cada dedo. En aplicaciones multi-biométricas que empleen Z muestras del mismo dedo del individuo, se genera para cada individuo un vector de Z x R x P x V x 3 bits concatenando los Z números de identificación que se obtienen a partir de cada muestra.
En la fase de recuperación se genera una lista ordenada de individuos registrados en la base, calculando un nivel de disimilitud (o similitud) entre el vector de características de entrada y cada vector almacenada. Si los vectores han sido cifrados ylo comprimidos deben ser descifrados y/o descomprimidos para calcular el nivel de disimilitud. El nivel de disimili1ud se calcula como el porcentaje de etiquetas que son diferentes entre el vector de acceso y cada vector almacenado. En el caso de multibiometría con O dedos, la disimilitud global se obtiene a partir de la fusión (por ejemplo con el operador suma) de las disimilitudes de cada dedo. En el caso de multi-biometría con Z muestras de un mismo dedo, la disimilitud global se obtiene como la fusión (por
ejemplo, con el operador mínimo) de las disimilitudes con cada muestra. La lista de individuos registrados se ordena de menor a mayor nivel de disimilitud, pudiéndose truncar la lista en un número dado de individuos o un porcentaje maximo de disimilitud.
En una aplicación de identificación. se selecciona el candidato de la lista que posea
menor disimilitud (o. equivalentemente. mayor similitud). En una aplicación de
autenticación, el nivel de disimilitud se compara con un umbral.
5 Para generar números de identificación digital diferentes para una misma huella
dactilar, el número obtenido según el método de la invención puede combinarse con el
resultado de una función no invertible (hash) de una clave o palabra de paso. siendo la
combinación: (a) una simple concatenación o (b) una intercalación determinada de los
bits o (c) una operación XOR entre los dos (para ello deben tener la misma longitud de
10 bits) , combinación que permite indexación e identificación (o autenticación) por el
doble factor de "quien eres· (la huella) y "lo que sabes· (la clave o palabra de paso) y
que permite revocar números de identificación comprometidos, generando otros
nuevos con una nueva clave o palabra de paso.
15 La técnica para llevar a cabo la fase de recuperación o verificación se Implementa
mediante los siguientes bloques basicos (Figura 6) : (a) Una memoria para almacenar
los números de Identificación digital o vectores de caracteristicas , Si (i=1 ,.... N). de N
individuos y así permitir su registro. (b) Un bloque para calcular la similitud entre el
número de identificación obtenido de la huella a identificar, S', Y los N números
20 almacenados , Bi (i=1 ,.. , N) , bloque que calcula la igualdad entre una etiqueta de
entrada y otra almacenada (ambas codificadas con 3 bits, en el caso de G=8)
preferentemente con 3 operadores XOR cuyas salidas sean las entradas a un
operador NOR, a continuación un contador calcula el número de etiquetas iguales
entre el vector de entrada y cada vector almacenado (el nivel de disimilitud es el
25 complemento del nivel de similitud). (e) En el caso de verificación, un bloque que
compara el resultado anterior con un umbral En el caso de recuperación, un bloque
que ordena de mayor a menor las similitudes con cada vector almacenado, hasta
llegar a un número máximo, M, de candidatos. Existen muchos algoritmos de
ordenación reportados en la literatura (por ejemplo basados en arboles binarios o n-
JO arios, métodos de inserción, etc.) , pudiéndose elegir uno u airo dependiendo de los
objetivos de velocidad y recursos a emplear (los algoritmos más rápidos suelen
necesitar más recursos que Jos mas lentos y vice versa).
Los números de identificación digital, B, generados pueden protegerse mediante la
J 5 técnica denominada Fuzzy Commilment. de la siguiente manera'
en la fase de registro : se asocia a cada usuario una palabra código aleatoria, Ci
(1=1 ,.. , N) , de un código corrector de errores (a S se le anaden ceros o unos hasta
que su tama~o sea el mismo que el de las Gi) y se realiza el calculo y almacenamiento de una función hash de Ci, hash (Ci) , y de los resultados Hi= (8 XOR Ci) , que se denominan datos de ayuda.
en la fase de verificación, dado un número de entrada, B', se calculan los Ci'=B' XQR Hi (si B' es similar a B, Ci' sera similar a Ci) , se aplica el código corrector de errores a Ci' y a su resultado se le aplica el hash. Si el resultado coincide con algún hash de los almacenados, se Identificara el usuario correspondiente (si N=1, el usuario sera autenticado).
en una posible fase de comunicación, ei ó B=Ci XOR Hi se pueden usar como secretos de los Que generar claves criptograficas para cifrar o autenticar mensajes.
El código corrector de errores es preferiblemente un código Reed-Solomon, que trata las etiquetas codificadas con 3 bits como símbolos.
Para elegir la tasa de error que debe corregir el código Reed-Solomon se puede aplicar: (a) el porcentaje de etiquetas diferentes para las que se obtiene que la razón de falso rechazo coincide con la razón de falsa aceptación, si se Quiere un compromiso óptimo entre ambas tasas; (b) el porcentaje de etiquetas diferentes para las que se obtiene una falsa aceptación nula, si se quiere eliminar el intrusismo; o (c) el porcentaje de etiquetas diferentes para las que se obtiene un falso rechazo nulo, si se quiere eliminar la denegación del servicia.
La técnica para llevar a cabo la protección de los vectores de características se implementa mediante los siguientes bloques básicos (Figura 7) : (a) Un bloque de adquisición adaptado para adquirir un número aleatorio, clave o contraser'ia y aplicar un codificador de un código corrector de errores para generar una palabra código. (b) Un bloque adaptado para generar unos datos de ayuda públicos a partir del vector de características de la huella y de la palabra código, para calcular una función hash de la palabra código y almacenar los resultados en una memoria. (el Un bloque decodificador de un código corrector de errores adaptado para recuperar un secreto a partir de una extracción del vector de características y de los datos de ayuda almacenados de la huella asociada al secreto.
