Identificación mediante huellas digitales utilizando búsqueda por proximidad sobre el índice métrico M-Tree

Abstract

Muchas aplicaciones computacionales necesitan buscar información en una base de datos. Tradicionalmente la operación de búsqueda se ha aplicado a datos estructurados y las bases de datos tradicionales se construyen alrededor del concepto de búsqueda exacta. En la actualidad han surgido depósitos no estructurados de información y no sólo se consultan nuevos tipos de datos (texto libre, imágenes, audio y video), sino que además ya no es posible estructurar la información de la manera clásica y, aun cuando sea posible hacerlo, nuevas aplicaciones tales como minería de datos (data mining) requieren acceder a la base de datos por cualquier campo, no sólo aquellos marcados como “claves”, como también resulta ser en el caso de identificación mediante huellas digitales. Un concepto unificador es el de “búsqueda por similitud” o “búsqueda por proximidad”, es decir buscar elementos de la base de datos que sean similares a un elemento de consulta dado. La similaridad es modelada usando una función de distancia (o métrica) que satisface ciertas propiedades y el conjunto de objetos es llamado un espacio métrico. En general, como la distancia es bastante costosa de calcular, el objetivo es reducir el número de evaluaciones de distancia. La identificación de personas a través de huellas digitales es una técnica ampliamente utilizada especialmente por las policías de investigaciones de casi todos los países del mundo. Un proceso crítico de la identificación de huellas digitales es el de la búsqueda de un individuo dentro de una base de datos con gran cantidad de información, pues el tiempo de espera es notablemente alto, dependiendo de la cantidad de huellas almacenadas. En este proyecto se trata de dar solución a esa gran problemática, utilizando un índice métrico denominado M-Tree, el cual permite realizar búsquedas por proximidad o similitud utilizando como cálculo de distancia entre dos huellas digitales el matching basado en minucias. Para el proceso de matching se describe la aplicación de la Transformada de Hough Generalizada, para obtener unos valores específicos que permiten alinear dos huellas digitales y así poder optar a más apareamientos de minucias. Para el proceso de comparación de huellas, una vez alineadas, se describe un algoritmo basado en coordenadas polares. Se ha implementado un algoritmo de matching de huellas digitales que arroja resultados aceptables considerando que se ha utilizado un algoritmo de extracción de minucias con muchas deficiencias, pero que promete muy buenos resultados mejorando dicho algoritmo. Además, se ha logrado implementar un interesante algoritmo de búsqueda por proximidad sobre espacios métricos. De esta forma se han obtenido muy buenos resultados en un tiempo mucho menor que los algoritmos de búsquedas actuales, en donde sólo se clasifican las huellas por su tipo, o simplemente realizan una búsqueda secuencial. Este trabajo constituye un aporte valioso al desarrollo e implementación de algoritmos biométricos en Chile, pues esta área sólo se está incursionando en estos últimos años en nuestro país, y la propuesta de un algoritmo de búsqueda distinto a los actuales (en la misma área) da una base para futuros estudios o propuestas que mejoren lo que ya se ha logrado.