Biometrica:huellas dactilares

Reconocimiento de huellas dactilares N.K. Ratha, K. Karu, S. Chen, A.K. Jain, (1996) A real-time matching system for large fingerprint databases, IEEE TPAMI 18(8) 799 A.K. Jain, L. Hong, R. Bolle (1997) On-line fingerprint verification, IEEE TPAMI 19(4) 302 L. Hong, A. Jain (1998) Integrating faces and fingerprints for personal identification IEEE TPAMI 20(12) 1295

1

Biometrica:huellas dactilares

Emparejamiento de huellas dactilares • Usos: – Law enforcement – Control de acceso para instalaciones seguras

• Ventajas – La huella es única – Las características que se usan para la identificación permanecen invariantes con la edad 2

Biometrica:huellas dactilares

• Existen métodos manuales estandarizados para la búsqueda de huellas dactilares en colecciones de forma manual • El método automátizado de búsqueda precisa de una representación (cjto de características) que posea las propiedades: – Retiene el poder discriminante de cada fingerprint a distintos niveles de resolución – Facilmente computable – Permite algoritmos automáticos de emparejamiento – Estable e invariante a ruido – Representación compacta y eficiente

• Las crestas y los valles son las características primarias. Las anomalías en el flujo de las crestas y valles (bifurcaciones, final, cruces, crestas cortas, etc) son las minutiae

3

Biometrica:huellas dactilares

4

Biometrica:huellas dactilares

5

Biometrica:huellas dactilares

6

Biometrica:huellas dactilares

7

Biometrica:huellas dactilares

Las características de interés para clasificación automática se reducen a dos: final y bifurcación.

Características complejas se pueden caracterizar como combinaciones de las caract. Simples. 8

Biometrica:huellas dactilares

La minutia se caracteriza por su posición (x,y) y ángulo

El emparejamiento se convierte en un problema de emparejamiento de conjuntos de puntos, que son problemas de emparejamiento de grafos o subgrafos.

9

Biometrica:huellas dactilares

Características de alto nivel • Clases de huellas: – Arch, tented arch, left loop, rigut loop and whorl

• Densidad de las crestas: nº por unidad de distancia. – Usualmente entre los puntos de interés: core y delta. • Core: punto interno más elevado de la cresta más interna al bucle • Delta: puntos con tres crestas irradiando

10

Biometrica:huellas dactilares

Calculo de las orientaciones • Pasos (método de Rao): – Calcular las magnitudes de los gradientes Gx(i,j) y Gy(i,j). – Obtiene la dirección dominante en bloques 16x16

11

Biometrica:huellas dactilares

La clasificación en clases primitivas se hace sobre los vectores de orientación en una imagen 64x64. Se calculan las direcciones, se suavizan (hasta que se obtiene un resultado), se encuentran los puntos singulares y se detectan los puntos core y delta. De acuerdo con ellos se clasifica la huella.

12

Biometrica:huellas dactilares

El índice de Pincaré se calcula sumando todos los cambios de en el ángulo de la dirección a lo largo de una curva cerrada en torno al punto que se examina. La clasificación de los puntos se hace en base al índice de Poincaré.

13

Biometrica:huellas dactilares

La discriminación de las clases se hace estudiando las lineas que conectan los 14 core y deltas y su relación con el campo de orientaciones local

Biometrica:huellas dactilares

Problemas de ruido • El método de captura de la huella produce – Areas con demasiada tinta: manchones – Rupturas en las crestas producidas por falta de tinta. – Variaciones de posición debidas a los cambios de presión.

15

Biometrica:huellas dactilares

Pasos de extracción de minutiae • Preproceso y segmentación – – – –

Cálculo del campo de orientación Separación de fondo y objeto Segmentación de crestas Suavización direccional de las crestas

• Adelgazamiento morfológico y extracción de características • Postproceso: eliminación de ruido • Densidad de crestas entre el core y el delta calculada a partir de la imagen adelgazada 16

Biometrica:huellas dactilares

17

Biometrica:huellas dactilares

Busqueda multinivel • Una secuencia de niveles de búsqueda que reducen el espacio de búsqueda en cada paso: – Búsqueda basada en texto: nombre, color de pelo, color de ojos,… – Basada en la clase – Basadas en la densidad de crestas – Basada en el emparejamiento de minutiae 18

Biometrica:huellas dactilares

Emparejamiento elástico de minutias • Registro: corrección de las rotaciones/traslaciones indeseadas • Emparejamiento de minutias: • Cálculo de la bondad (score) de emparejamiento

19

Biometrica:huellas dactilares

registro • Entrada: conjuntos de minucias

• Transformación asumida: afin, ruido, eliminación y añadido de puntos • Es un problema de optimización: busca el mejor emparejamiento mediante una trasformada de Hough generalizada 20

Biometrica:huellas dactilares

En el emparejamiento algunos puntos pueden no tener correspondencias y tras el registro los emparejamientos se recuperan con un cierto error.

21

Biometrica:huellas dactilares

Transformada de Hough • Conjunto de transformaciones admitidas

• Espacio de parámetros de las transformaciones admitidas

22

Biometrica:huellas dactilares

• Matriz de acumulación

• Cálculo de la trasnformación: para cada par de puntos de minucias de cada imagen se calcula la transformación y se acumula

23

Biometrica:huellas dactilares

24

Biometrica:huellas dactilares

Emparejamiento de minucias

25

Biometrica:huellas dactilares

26

Biometrica:huellas dactilares

Identificación de huellas • Es el proceso de emparejar una huella interrogación (query) contra una base de datos de huellas dada para establecer la identidad de un individuo. • Objetivos – Determinar si la huella está presente en la base de datos – Obtener los mejores candidatos 27

Biometrica:huellas dactilares

Identificación como correspondencia entre minutiae • No se conoce una correspondencia a priori entre las minucias de las dos huellas • Existen translaciones, rotaciones y deformaciones no lineales entre las minucias patrón y las de entrada. • Aparecen minucias espureas en ambos casos • Se pierden algunas minucias 28

Biometrica:huellas dactilares

Dos huellas del mismo dedo, se aprecian las deformaciones debidas a la presión, además de rotación y traslación. 29

Biometrica:huellas dactilares

Sistema de verificación on-line • Basado en escaners de huellas digitales

30

Biometrica:huellas dactilares

Fases • Extracción de minucias (500 dpi) – Extracción del mapa de crestas – Búsqueda de las minucias

• Emparejamiento de minucias – Emparejamiento elástico de un conjunto de puntos. – Sujeto a deformaciones. 31

Biometrica:huellas dactilares

Extracción de minucias

32

Biometrica:huellas dactilares

Estimación del campo de orientación • Mejora jerárquica del método de Rao • Calcula el nivel de consistencia de las orientaciones entre bloques vecinos D son los 5x5 bloques vecinos

33

Biometrica:huellas dactilares

Si la consistencia está por encima de un cierto umbral, se reestiman las orientaciones entorno a esa región a una resolución menor.

34

Biometrica:huellas dactilares

Detección de crestas • Convoluciona con máscaras de tamaño LxH

• Acentúan los máximos locales de intensidad adaptativamente,en la dirección normal a la dirección local de la cresta. • Precisa de un postproceso de detección de agujeros y raspaduras (hole & speckle) 35

Biometrica:huellas dactilares

Si las dos imágenes convolución son mayores que un umbral se define como cresta el pixel

Dirección local de la cresta

36

Biometrica:huellas dactilares

Extracción de minucias • Trivial si el mapa de crestas está bien definido: idealmente adelgazado. – Finales de crestas: el número de 8 vecinos es 1 – Bifurcaciones: mas de dos 8-vecinos

• Problemas: rupturas y spikes indeseados producen minucias espúreas. Es necesario aplicar algún método de suavización. 37

Biometrica:huellas dactilares

Suavización de crestas • Heurísticos: – Si una rama es ortogonal a la dirección de la cresta y su longitud es menor que un umbral, se remueve. – Si una ruptura es suficientemente pequeña y no pasan otras crestas por medio de ella, se unen los extremos.

• Refinamiento basado en información estructural – Si varias minucias forman un cluster en una región pequeña, se remueven todas menos la más cercana al centro del cluster – Si dos minucias se encuentran bastante cerca, enfrentadas sin crestas intermedias, eliminar ambas.

• Información asociada a las minucias: posición, orientación y cresta asociada. 38

Biometrica:huellas dactilares

39

Biometrica:huellas dactilares

Emparejamiento de crestas • Proponen reconocimiento mediante alineamiento. – Fase de alineamiento: se estiman transformaciones de rotación, traslación y escalado entre el input y el patrón en la BD – Fase de emparejamiento: se convierten las minucias en polígonos en el sistema de coordenadas polares y se aplican algoritmos de emparejamiento elástico de cadenas (strings). 40

Biometrica:huellas dactilares

Alineamiento de patrones de puntos • Cada minucia se corresponde con una cresta y el emparejamiento se hace sobre las crestas

41

Biometrica:huellas dactilares

Durante la detección de las minucias, se registran también las crestas. Se representan como curvas planares, con su origen coincidente con la minucia, el eje x coincidente con la dirección de la minucia. La curva está normalizada por la distancia entre crestas promedio. Sean Rd y RD las crestas asociadas con las minucias input y patrón. Paso 1: calcular el emparejamiento como curvas 1D, con L el mínimo de las longitudes, di y Di la distancia al eje x, y el intervalo de muestreo es la distancia intercresta. Si S supera un umbral proseguir con el paso 2, sino intentar con otro par de crestas patrón e input.

42

Biometrica:huellas dactilares

Paso 2: calcular la transformación entre las dos crestas. Calcula el vector de traslación referido a las minucias de referencia:

Calcula el ángulo de rotación entre las crestas:

Paso 3: sea la minucia de referencia. Trasladar y rotar todas las minucias de acuerdo con los parámetros calculados para esta minucia de referencia.

43

Biometrica:huellas dactilares

Emparejamiento de los puntos alineados • La existencia de deformaciones en la impresión de la huella implica que es necesario un emparejamiento elástico. Minucias patrón e input

44

Biometrica:huellas dactilares

Paso 1: convertir a coordenadas polares respecto de la minucia de referencia:

Paso 2: representar las minucias en orden de distancia radial

Paso 3:Emparejar las representaciones radiales mediante un algoritmo de programación dinámica y obtener la distancia de edición entre las representaciones polares. 45

Biometrica:huellas dactilares

Paso 4: usa la distancia de edición para establecer la correspondencia de las minucias. La medida del emparejamiento es: Npair número de minucias que caen en las cajas de acotación de las minucias patrón.

Justificación: Deformaciones no lineales son radiales. Es más facil de formular la rotación en el espacio de coordenadas polares. 46

Biometrica:huellas dactilares

Emparejamiento de cadenas • Se hace en el paso 3 • Introducen criterios de elasticidad • Definición recursiva de la distancia de edición C(M,N)

47

Biometrica:huellas dactilares

48

Biometrica:huellas dactilares

Ajuste adaptativo de alineamiento para el emparejamiento elástico

49

Biometrica:huellas dactilares

50