Metodología para el uso de los niveles de gris en verificación de firmas manuscritas

Universidad de Las Palmas de Gran Canaria Departamento de Señales y Comunicaciones Programa de Doctorado Cibernética y Telecomunicaciones Tesis Doctoral: Metodología para el Uso de los Niveles de Gris en Verificación de Firmas Manuscritas. Autor: Jesús Francisco Vargas Bonilla Director: Dr. D. Miguel Angel Ferrer Ballester El Director El Doctorando Las Palmas de Gran Canaria, a 8 de Noviembre de 2010 APaula. I II Agradecimientos Quisiera agradecer al director de esta Tesis Doctoral, al Dr. D. Miguel Ángel Ferrer Ballester, su confianza, su ayuda y su paciencia, lo cual ha permitido la realización de este Trabajo. Agradezco enormemente a mi familia y a mi novia Paula por todo su apoyo, sus ánimos, y su paciencia. Sin ellos esta experiencia hubiese sido imposible de llevar. Me gustaría destacar la ayuda, colaboración y apoyo recibido por parte del resto de los miembros del Grupo de Procesado Digital de Señales (GPDS) del Departamento de Señales y Comunicaciones de la Universidad de Las Palmas: el Dr. D. Carlos Manuel Travieso González, Dr. D. Jesús Bernardino Alonso Hernández y D. José Cruz Gil. Así mismo, mi agradecimiento por la disponibilidad de los recursos puestos a mi disposición, en especial el uso del Centro de Cálculo "José Cruz". A los chicos con los que compartí un lugar en el laboratorio, Aythami Morales, Patricia Henriquez, Alexis Herrera, Jose Luís Vásquez, Fabián Romero y a los que se me escapan, les agradezco los momentos compartidos, los momentos de discusión académica y su apoyo en todo este proceso. A la Universidad de Antioquia, por el apoyo recibido durante la comisión de estudios otorgada, al Instituto para el Desarrollo Tecnológico y la Innovación en Telecomunicaciones - IDeTIC de la ULPGC, y al Programa de Becas de Alto Nivel para Latinoamerica - Programa AlBan por la beca con que fui favorecido. Así mismo, agradezco el apoyo recibido del Grupo de Electrónica de Potencia, Automatización y Robótica - GEPAR de la UdeA. Asi mismo, Y por último, quiero agradecer a todos mis Amigos por el apoyo brindado. Muchas Gracias a todos!. III IV Prologo “Ciencia es todo aquello sobre lo cual siempre cabe discusión.” José Ortega y Gasset (1883-1955) V Índice general 1 Introducción 1 1.1 Motivación ...................................... 1 1.2 LaTesis........................................ 4 1.3 Objetivosdeesteestudio .............................. 4 1.4 Contribuciones.................................... 5 1.5 Esquemadelamemoria .............................. 6 2 Estado actual en biometría de firma estática 7 2.1 Métodosdeevaluacióndesistemasbiométricos. ................ 7 2.1.1 Medidas de desempeño ........................... 8 2.1.2 Tipos de falsificaciones............................ 10 2.2 Revisióndelestadodelarte............................. 12 2.2.1 SistemasbasadosenCaracterísticasGlobales.............. 13 2.2.2 SistemasbasadosenCaracterísticasLocales .............. 17 2.2.3 SistemasbasadosenlaCombinacióndeCaracterísticas. ....... 21 2.2.4 SistemasbasadosenCaracterísticasPseudodinámicas ........ 22 2.2.5 Característicasbasadasenelanálisisdelatinta ............ 25 2.2.6 Comentariossobrelarevisióndelestadodelarte............ 32 3 Esquema general de un sistema AVFM 39 3.1 SistemasAVFM.................................... 39 3.2 Basesdedatos.................................... 40 3.2.1 GPDScorpus ................................. 41 3.2.2 MCYTcorpus................................. 41 3.2.3 ReDigitalizacióndelosfoliosdelGPDScorpus.............. 42 3.2.4 Segmentacióndelasmuestras....................... 43 3.3 Preprocesamiento del Fondo ............................ 45 3.4 Preprocesamiento del Histograma . . . ...................... 48 3.5 MetodologíadeEvaluación............................. 49 4 Caracterización basada en los niveles de gris. 51 4.1 Característicasapartirdelhistograma. ..................... 51 4.2 CoeficientesPseudo-cepstralesdelhistograma.................. 55 4.2.1 Característicapropuesta .......................... 55 4.3 DensidaddepixelesencoordenadasPolares................... 59 4.3.1 PuntosdeAltaPresión ........................... 60 4.3.2 DensidaddePixelesdeAltaPresiónenCoordenadasPolares ..... 62 VI ÍNDICE GENERAL VII 5 Características basadas en textura. 69 5.1 Matrizdeco-ocurrenciadenivelesdegris .................... 69 5.1.1 ConstruccióndelamatrizdeCo-ocurrencia............... 70 5.1.2 Característicasdelamatrizdeco-ocurrencia .............. 70 5.2 LocalBinaryPatterns................................ 78 5.2.1 LBPextendido ................................ 80 5.2.2 LBPconInvarianzaalarotación...................... 81 6 Combinación de información espacial con textura 87 6.1 GLCMUsandoanálisisporbloques........................ 87 6.2 LBPUsandoanálisisporbloques ......................... 93 6.3 Combinacióndecaracterísticas ..........................102 7 Análisis de Texturas en el Dominio Transformado 105 7.1 GLCM.UsandolatransformadaWavelet.....................105 7.2 LBP.UsandolatransformadaWavelet ......................109 7.3 Combinacióneneldominiotransformado ....................113 8 Análisis de la metodología propuesta. 115 8.1 Resumendelosresultados.............................115 8.2 Comparacióncontrabajossimilares .......................116 8.3 MetodologíapropuestaenBlancoyNegro ....................116 8.4 Desempeño vs número de firmantes .......................117 8.5 Desempeño vs número de muestras. . ......................118 9 Discusión y Conclusiones 121 A Transformada Wavelet 125 A.1 Expansiónenserieswavelet ............................128 A.2 Transformawaveletdiscreta............................129 A.3 Transformadarápidawavelet ...........................129 A.4 Transformadawaveletendosdimensiones ...................131 BClasificación 135 B.1AprendizajeSupervisado ..............................135 B.1.1 Aprendizaje de clasificación.........................135 B.1.2Aprendizajedefunción ...........................136 B.2DiscriminanteLineal ................................136 B.2.1ElcasodeDosClases............................136 B.3MáquinasdeSoporteVectorial...........................137 B.3.1 Descripción ..................................137 B.3.2Mapeohaciaunespaciodealtadimensionalidad............140 B.3.3MínimosCuadrados-SVM..........................143 C Metodologías de validación 145 C.1 Evaluación del clasificador.............................145 C.1.1 Método Hold-out ...............................145 XIV ÍNDICE DE CUADROS Notación I(x, y)-Imagen. Ig(x, y)- Imagen en escala de gris. Ibw(x, y)- Imagen en blanco y negro nLNúmero de niveles para posterizado. IS(x, y)- Imágen segmentada. IG(x, y)- Imágen segmentada y con histograma desplazado. M×NDimensionaes de una imagen. LNúmero de niveles de gris presentes en una imagen. gNivel de gris h(g)- Histograma de niveles de gris. F,F−1Operador transformada de Fourier. ˆ IgTransformada de Fourier de Ig. CgCepstrum de una imagen. ChCepstrum de un histograma. gmin - Mínimo nivel de gris presente en una imagen. gmax - Máximo nivel de gris presente en una imagen. IHPP g(x, y)- ImagendepuntosdealtapresióndeIg. HPPthresh - Umbral de alta presión. P(i, j|δx,δy)- Matriz de co-ocurrencia. Abreviado como P(i, j). δx,δy - Desplazamiento en columnas y filasdeunaimagen. αi,j -ElementodeP(i, j). LBPP,R - Operador LBP con Ppixeles y radio R. TTextura de un vecindario. gcNivel de gris del pixel central de un vecindario. giNivel de gris del i-ésimo píxel de un vecindario. ψ(x)- Wavelet ϕ(x)- Función de escala. Capítulo 1 Introducción 1.1. Motivación Se ha planteado que la verificación de la identidad es un aspecto crucial dentro de la actual sociedad de información y comunicación. El número de situaciones en que se hace necesario un procedimiento rápido y de bajo costo para la autentificación de documentos, para el acceso o intercambio de información, y más aún para el comercio electrónico crece diariamente. Para el caso de la verificación personal, es posible considerar dos tipos de medios biométricos: Los Fisiológicos, los cuales se derivan de una medición directa de partes del cuerpo humano; y los de Comportamiento, los cuales se derivan de mediciones realizadas a partir de una acción ejecutada por un individuo y que permite caracterizarlo de una manera indirecta. Como ejemplos del primer caso se pueden citar la huella dactilar, la cara, la palma de la mano, y la retina entre otras. Dentro del segundo grupo se pueden encontrar la voz, la firma, y el ritmo de tecleado en un ordenador [LS01]. La firma manuscrita continúa siendo una de las formas más comúnmente usada y ampliamente aceptada para la autentificación de la identidad de una persona. A diario milesdedocumentossonfirmados por alguien con el fin de autorizar una transacción bancaria, el acceso a información o a un recinto, una representación legal o simplemente un contrato. A pesar de la tecnología disponible, la gran mayoría de los procesos de verificación de estas firmas manuscritas son realizados manualmente por humanos mediante una inspección visual. En consecuencia, existe un gran interés en el desarrollo de sistemas de verificación automática de firmas que sean efectivos y con la capacidad de realizar de manera rápida y acertada la verificación de la firmamanuscritadeun individuo. Lo anterior implica que la verificación de firmas manuscritas (VFM) no solamente es un problema de reconocimiento de patrones teóricamente interesante, sino también un problema del mundo real con implicaciones comerciales muy significativas. La verificación de firmas manuscritas es un problema científicamente muy complejo y atractivo. Generalmente se dispone de pocas muestras para entrenar el modelo de clasificación, y además se presenta una gran variabilidad intraclase. Lo anterior supone un reto para la comunidad científica. Teniendo en cuenta la importancia que desde un punto de vista económico representa esta tarea, se presenta una gran dependencia 1 21.1. MOTIVACIÓN de la efectividad de los sistemas de seguridad que tienen como objetivo evitar los accesosfraudulentosalossistemasdeinformación. En la actualidad el número de documentos que contienen una firma como medio de identificación de la persona que los suscribe es enorme, por ejemplo, se tienen datos de que en Estados Unidos se extienden alrededor de 17 billones de cheques al año [Tow08]. La verificación de todos estos documentos por parte de examinadores expertos supondría costes astronómicos en tiempo y dinero. Figura 1.1: Pérdidas reportadas por los bancos por fraudes en cheques [Moh07] Figura 1.2: Porcentaje de pérdidas según el medio usado para el fraude [Mor09] Intentar aumentar la información de la que se dispone para un sistema de verificación biométrica basado en la firma manuscrita, sin que esto signifique la construcción o compra de dispositivos de captura adicionales, implica la posibilidad de desarrollar sistemas mas confiables y con un valor agregado en constante crecimiento. Como se mencionó anteriormente, para el caso de los sistemas de verificación de firmas tipo offline la información disponible proviene de una imagen estática de la firma que se quiere analizar. Lo anterior implica la no disponibilidad de información dinámica correspondiente a la firma. A partir de lo descrito en el capítulo 2, podemos decir que es posible CAPÍTULO 1. INTRODUCCIÓN 3 realizar una caracterización de la información siguiendo tres lineamientos: un análisis global de la forma de la firma, un análisis local de la misma, o un análisis que se aparta de la forma para centrarse principalmente en la reconstrucción de la información dinámica. Si bien, con el suficiente entrenamiento un falsificador puede llegar a reproducir con gran habilidad la forma y distribución de los trazos que conforman la firma, en lo que concierne a la velocidad, presión y orden de escritura de los trazos, un falsificador encontrará siempre rasgos muy difíciles de reproducir. Lo anterior permite pensar que la posibilidad de poder reconstruir y/o representar información dinámica a partir de imágenes estáticas de una firma, representa un reto bastante atractivo para la comunidad científica. Sin embargo, y teniendo en cuenta que la principal fuente de información para tal objetivo es una imagen en escala de grises, es necesario desarrollar los procedimientos necesarios para identificarelefectodeloscambiosdeluminosidadquese perciben cuando se analizan imágenes de firmas que han sido escritas sobre diferentes tipos de papel (color, gramaje), y usando distintos tipos de bolígrafo (color, tinta). Así mismo, y a pesar de que los sistemas tipo off-line siguen estando en desventaja frente a los sistemas tipo on-line en lo referente a porcentajes de acierto, sigue latente la necesidad de realizar la verificación de identidad de una persona que no se encuentra presente en el momento mismo en que se realiza esta tarea, como es en el caso de pagos de cheques, poderes notariales, firmas de contratos, y cualquier otra transacción que involucren documentación que ha sido firmada por alguien como prueba de su compromiso. Lo anterior implica la necesidad de continuar trabajando en el desarrollo de sistemas tipo off-line más confiables y mejor adaptados a las necesidades reales. La aparición de conferencias internacionales con temática específica en el análisis de documentos, demuestra el alto interés de la comunidad científica en este problema. En consecuencia, se ha generado un importante número de trabajos orientados a la verificación automática de firmas manuscritas con resultados bastante prometedores. Sin embargo, existen fuentes de información poco explotadas. En ese sentido se plantea la presente investigación, en donde se pretende avanzar en el estudio de los niveles de gris como fuente de información, para la caracterización de una firmamanuscritaorientadaasuclasificación como genuina o falsificación. A continuación se plantea la hipótesis de este trabajo y los objetivos que se quieren alcanzar con su desarrollo. 41.2. LA TESIS 1.2. La Tesis Un aspecto poco considerado en la verificación de firmas off line es la utilización de la información presente en los niveles de gris de la firma, a pesar de que son varios los trabajos realizados en busca de un sistema de verificación tipo off-line para firmas manuscritas, han sido pocos satisfactorios los resultados obtenidos para el caso de aquellos sistemas basados en la información de los niveles de gris. Si bien esta deficiencia ha sido compensada con la combinacióndeparámetrosdediferentenaturaleza, la información contenida en los niveles de gris de la imagen de una firma sigue siendo un potencial por explotar. La principal dificultad encontrada por los investigadores ha sido la influencia del tipo de tinta sobre la distribución de los niveles de gris, este hecho ha llevado a que los sistemas desarrollados no realicen la verificación de una firma sino la clasificación del tipo de tinta empleado para su realización. Se supone que la firma depende del aparato neuromotor de la persona cuyo desarrollo es único y determina su forma de escribir, tanto en la forma de escribir los trazos como en la forma de manejar el bolígrafo, y esto último se manifiesta en cómo se deposita la tinta sobre el papel. Según sea el tipo de tinta, se realiza un enmascaramiento del histograma de niveles de gris de la imagen; se hace necesario entonces desarrollar un análisis que permita extraer la información obviando el enmascaramiento causado por la tinta empleada. De esta forma se pueden caracterizar los patrones de distribución propios de cada firmante permitiendo realizar la verificación de la firma. Con el fin de reducir dicho enmascaramiento y posibilitar el uso de la información del firmante contenido en los niveles de gris de la firma, el presente trabajo parte de la siguiente hipótesis: La información del firmante está menos enmascarada en la relación entre los niveles de gris de los pixeles del trazo de una firma manuscrita que en su valor absoluto. Consecuentemente, la tesis a evaluar en el presente trabajo se enuncia como sigue: Caracterizar los cambios entre los niveles de gris del trazo de una firma manuscrita aporta información que permite mejorar la verificación automática de la identidad de una persona a partir de su firma. 1.3. Objetivos de este estudio A partir de la tesis planteada, se proponen los siguientes objetivos para el presente estudio: 1. Explorar metodologías para mejorar la detección de falsificaciones a partir de la información extraída de los niveles de gris de la imagen estática de una firma manuscrita. 2. Analizar la influencia, tanto del tipo de bolígrafo como del tipo de papel utilizados CAPÍTULO 1. INTRODUCCIÓN 5 para realizar la firma, sobre el desempeño del sistema desarrollado. Así mismo, desarrollar los procedimientos orientados a la minimización de tales efectos. 3. Proponer una metodología de verificación que aproveche eficientemente la información obtenida con la caracterización propuesta. 1.4. Contribuciones Se demuestra la viabilidad de una metodología que usa la información de los niveles de gris de una imagen, para la verificación automática de firmas manuscritas. Se han revisado los trabajos más relevantes de verificación tipo off-line de firma manuscrita, haciendo una diferenciación de los mismos según el tipo de características empleadas. Se ha dedicado un apartado para aquellos trabajos basados en características pseudo-dinámicas. Así mismo se han revisado trabajos que han estado orientados a la caracterización de la tinta de textos manuscritos. Se ha puesto a punto una base de datos que contiene muestras de firmas manuscritas de 850 firmantes. Esta base de datos incluye muestras genuinas y falsificaciones elaboradas, realizadas con diferentes tipos de bolígrafo. La versión en blanco y negro de esta base de datos se ha utilizado para la competición 4NSigComp2010 [BFV10] realizada en el marco de la International Conference on Frontiers of Handwriting Recognition ICFHR2010. Se ha realizado un estudio de la influencia que tiene el tipo de tinta sobre la distribución de los niveles de gris de los pixeles que conforman los diferentes trazos de una muestra, y se plantean diferentes alternativas para obtener una caracterización que por lo menos reduce la variabilidad que se presenta cuando el sistema se evalúa con diferentes bases de datos que contienen muestras realizadas con diferentes tipos de bolígrafo (diferentes tipos de tinta). La metodología planteada tiene en cuenta el uso de características basadas en el análisis de textura como la Matriz de Co-Ocurrencia (GLCM) y el Patrón binario local (LBP). En el caso de la GLCM, sus características han sido empleadas para el análisis del tipo de tinta, y en cuanto al LBP, según nuestro conocimiento en el momento de elaborar este documento, no había sido empleado para la verificación de firmas manuscritas. Se propone el uso de la transformada Wavelet como complemento de las características basadas en el análisis de textura. Se hace uso de la descomposición wavelet como aparato matemático para aislar las componentes de la imagen que corresponden a la distribución de pixeles determinada por el tipo de tinta. Los componentes restantes corresponden a la distribución de pixeles determinada por las características personales del firmante y son estos últimos los que se caracterizan mediante el análisis de texturas. 6 1.5. ESQUEMA DE LA MEMORIA 1.5. Esquemadelamemoria Esta memoria de tesis comienza con un marco teórico general del problema que va seguido de la descripción de los distintos experimentos desarrollados en el trabajo. En el capítulo 2 se presenta la revisión del estado del arte realizada para el problema de la verificación biométrica de personas basado en la modalidad off-line de la firma manuscrita. Así mismo se presenta una breve descripción de los métodos de evaluación de los sistemas biométricos. El capítulo 3 describe el esquema general de un sistema automático de verificación de firmas manuscritas. También se describen las bases de datos usadas para las pruebas realizadas sobre las metodologías propuestas. Se presentan los datos más relevantes de cada una de ellas, y se resalta el hecho de que contienen muestras hechas con diferentes tipos de bolígrafo. En este capítulo también se describen los procedimientos de preprocesado implementados y que tienen como objetivo eliminar y normalizar el fondo de las imágenes, y modificar el histograma para reducir la influencia del tipo de bolígrafo sobre las etapas posteriores. Finalmente, se describe la metodología de experimentación empleada a lo largo de este trabajo. El capítulo 4 inicia la descripción de la caracterización de firmas basada en la información de los niveles de gris. Se presentan los estudios realizados para características basadas en la información del histograma, los puntos de alta presión, y finalmente las características basadas en el análisis de textura. Dentro de estas últimas, se describen la Matriz de Co-ocurrencias y el Patrón Binario Local. El capítulo 5 describe las metodologías propuestas a partir de las características descritas en el capítulo 4, y que tienen como objetivo reducir la influencia del tipo de tinta empleado por el firmante, sobre el desempeño general del sistema. Se hace uso de una análisis por bloques con el fin de realizar una caracterización más localizada de la imagen, y se plantea el uso de la transformada Wavelet como complemento de las características basadas en el análisis de textura. Finalmente, el capítulo 6 presenta las conclusiones del trabajo realizado y da espacio para las líneas futuras que pueden plantearse a partir de esta tesis. Se han dejado como apéndices, el planteamiento teórico de la transformada Wavelet (apéndice A), la descripción del modelo de clasificación empleado correspondiente a las Máquinas de soporte vectorial (Apéndice B), y una descripción de las diferentes metodologías de validación consideradas (Apéndice C). Capítulo 2 Estado actual en biometría de firma estática En este capítulo se presenta en primer lugar una serie de conceptos considerandos relevantes y relacionados con las metodologías usadas para la evaluación del desempeño de los sistemas basados en biometría. Posteriormente, se expone la revisión del estado del arte realizada para el presente estudio. 2.1. Métodos de evaluación de sistemas biométricos. Son varios los libros recientes que ofrecen detalles sobre este tema [CPRS03],[JFR08], [RG07], [WG09]. Estos libros, junto con los reportes de los proyectos europeos BioVisioN y BioSecure, son la principal fuente de los siguientes párrafos. La evaluación del desempeño de los sistemas biométricos es importante por varias razones: Para que el sistema pueda ser usado en un contexto real, es necesario cuantificar de manera precisa la calidad del mismo. Es necesario definirsielcontextoen que puede usarse, su eficiencia y la robustez de los algoritmos, cumplen con los requerimientos de una aplicación industrial. La comparación de los diferentes sistemas permite determinar sus ventajas y desventajas. En el campo de la investigación y desarrollo, es necesario disponer de metodologías de evaluación que evidencien los aportes de los nuevos sistemas propuestos. Los sistemas biométricos permiten reconocer individuos de cuatro formas posibles: Verificación de identidad, confirmando que una persona es quien dice ser. No-identificación, chequeando que un usuario no ha sido registrado previamente en la base de datos. Identificación tipo Closed-set, reconociendo a una persona porque sus características son suficientemente similares a las de una persona perteneciente a la base de datos. 7 8 2.1. MÉTODOS DE EVALUACIÓN DE SISTEMAS BIOMÉTRICOS. Identificación tipo Open-set, rechazando un impostor porque sus características no son suficientemente similares a ninguna de las personas pertenecientes a la base de datos. Para cada rasgo biométrico existen diferentes implementaciones. Éstas pueden usar diferentes sensores; diferentes algoritmos para procesar las señales capturadas por el sensor usado; y diferentes interfaces de usuario. Además, el desempeño dependerá en gran medida de la forma en que se implementa la biometría para una aplicación o servicio específico. Por tanto, no tiene mucho sentido comparar el rendimiento de los métodos biométricos en una forma general (p.e. huellas dactilares contra el reconocimiento de caras). La precisión de un sistema biométrico se determina mediante una serie de pruebas; primero, una evaluación de la precisión del algoritmo de coincidencia (evaluación de tecnología); luego, una evaluación del rendimiento en un ambiente de imitación (evaluación específica); seguida de una prueba en vivo en el lugar (evaluación operativa), antes de comenzar con las operaciones completas. Cada evaluación cumple un fin diferente e incluye distintos tipos de análisis. Según el documento NPL Report CMSC 14/02 [MW02] podemos describir estos tres tipos de evaluación de la siguiente forma: Evaluación de tecnología: tiene como objetivo comparar diferentes algoritmos para una tecnología. Las pruebas de todos los algoritmos se llevan a cabo sobre una base de datos estandarizada que ha sido generada empleando un sensor universal. Sin embargo, el desempeño dependerá tanto del ambiente como de la población para la cual ha sido creada dicha base de datos. Teniendo en cuenta que la base de datos no cambia, los resultados de la evaluación de tecnología son repetibles. Evaluación específica: su objetivo es determinar el desempeño global del sistema para una aplicación específica. La prueba se realiza sobre un sistema completo operando en un ambiente que modela el mundo real de interés. Cada prueba tendrá su propio sistema adquisición por lo que se obtendrán datos ligeramente diferentes. Los resultados obtenidos serán repetibles solamente para el caso en que el escenario modelado pueda ser controlado cuidadosamente. Evaluación operativa: Aquí se determina el desempeño de un sistema biométrico completo en un ambiente de aplicación específico con una población objetivo específica. De forma general, los resultados obtenidos nos serán repetibles porque se desconocen y no se tienen documentadas las diferencias entre los ambientes operacionales usados. 2.1.1. Medidas de desempeño El conjunto de evaluación deberá tener muestras de los usuarios para las etapas de entrenamiento y prueba. También se debe disponer de muestras de impostores (cuyo número deberá ser igual o mayor al número de muestras de los usuarios usadas para la etapa de prueba). Ningún usuario ni impostor podrá pertenecer a los dos conjuntos CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 9 de datos. Se pueden usar las técnicas de re-sampling ycross-validation para estimar losintervalosdeconfianza, distribución de los parámetros, etc. El principal objetivo es asegurar la correcta predicción del desempeño del sistema para un conjunto de datos diferente. El desempeño de un sistema biométrico puede ser medido usando varios indicadores. La salida de una prueba es un puntaje de similitud (es decir la probabilidad de que la muestra de prueba provenga de un usuario autorizado). Para tomar la decisión de aceptar o rechazar al individuo, el puntaje obtenido se compara con umbral. Una vez tomada la decisión, se pueden cometer dos tipos de error: una falsa aceptación, si un impostor es aceptado o un falso rechazo, si un usuario genuino es rechazado. Se calcula entonces la tasa de falsa aceptación (FAR, del inglés False Acceptance Rate) y la tasa de falso rechazo (FRR, del inglés False Rejection Rate) para un número adecuado de pruebas con usuarios genuinos e impostores. Si se realiza una normalización de los puntajes de tal forma que se escoge un umbral único para todos los usuarios, es posible encontrar la relación entre FAR y FRR variando el valor de dicho umbral. La gráfica que presenta los valores de FRR como función de los valores de FAR se denomina curva de compensación del error de detección (DET, del inglés Detection Error Trade-off) [MDK+97] y los ejes ordenados se encuentran en una escala de desviación normal, o dicho gráfico se denomina característica operativa del receptor (ROC, del inglés Receiver Operating Characteristic) si se usan otras escalas para los ejes [Ber80]. La figura 2.1 muestra ejemplos de las dos curvas mencionadas. Para el caso en que se necesite resumir el desempeño del sistema con un solo número,sesueleemplearelpuntodeoperaciónenelcualelvalordeFARigualaalvalor de FRR, y que se denomina tasa de igual error (EER, del inglés Equal Error Rate). Por lo general, cuánto más bajo sea el valor de EER, mayor será la precisión del sistema biométrico. Otra medida más operacional combina los valores de FAR y FRR en una función de costo de decisión (DCF, del inglés Decision Cost Function) que se define de la siguiente forma: DCF =CFRPtarFRR+CFAPimpFAR (2.1) en donde CFR es el costo de un falso rechazo, CFA es el costo de una falsa aceptación, Ptar es la probabilidad aprioride los objetivos (targets) y Pimp es la probabilidad apriori de los impostores. Un caso particular de la DCF se conoce como HTER (del inglés Half Total Error Rate) en donde los valores de costo se hacen iguales a 1 y las probabilidades son todas 0.5, es decir HTER =(FAR+FRR)/2(2.2) 16 2.2. REVISIÓN DEL ESTADO DEL ARTE Posteriormente en 1999, Fadhe [FB99] describe una técnica que usa “steerable wavelet". Aquí la transformada es usada como herramienta para la reducción de información y selección de características. Además de la reducción en el vector de datos usado como características, se reduce la complejidad de una Red Neuronal usada como clasificador. Continuando con las transformaciones, en ese mismo año, Kaewkongka y otros [KCT99] usan la Transformada Hough para extraer el espacio parametrizado de Hough a partir del esqueleto de la firma como única característica. Para la clasificación emplearon una NN con Backpropagation. el sistema se prueba con 70 firmas de diferentes firmantes, y se reporta una tasa de reconocimiento de 95 %. En 2002, Mizukami y otros [MYMY02] proponen un sistema basado en un método de extracción del desplazamiento. La función óptima de desplazamiento se calcula para cada par de firma empleando la minimización de un funcional. Dicho funcional se define como la suma del cuadrado de la distancia euclidiana entre dos firmas y un factor de penalización que necesario para suavizar la función de desplazamiento. Una vez calculada la función de desplazamiento, se mide la disimilitud entre la firma que se quiere evaluar y la correspondiente muestra original. La base de datos empleada contenía muestras de 20 firmantes, con 10 muestras genuinas y 10 falsificaciones elaboradas para cada uno. Se reporta un EER de 25 %. Recientemente en 2007, Freire y otros [FFMDOG07] retoma esta línea para evaluar la viabilidad de la Criptobiometría empleando VFM tipo off-line para el caso de falsificaciones aleatorias y elaboradas. Los autores analizan la posibilidad de crear un encriptado difuso, esto es, codificar y decodificar empleando llaves difusas, usando VFM. La extracción de características esta basada en los valores máximos y mínimos de los contorno superior e inferior de una firma. Para la base de datos se emplea el subcorpus de firmas tipo off-line del proyecto MCYT de las Universidades Autónoma de Madrid, Politécnica de Madrid, Politécnica de Cataluña, Valladolid, y del País Vasco; de la cual se seleccionaron 75 firmas, con 15 muestras genuinas y 15 falsificaciones elaboradas para cada uno.Elestudioconcluyequeelenfoquepropuestoesviablesoloparaunapartedelos firmantes analizados. En 2008, Larkins y Mayo [LM08] proponen un Umbralizado adaptativo de características (AFT) para binarizar el vector de características de la imagen que contiene la firma. Las pruebas se realizaron sobre dos bases de datos: CEDAR y GPDS. La clasificación se realiza mediante el calculo de un umbral para los puntajes de similitud. Se reportan porcentajes de acierto de 90 % y 85 % respetivamente. Los autores mencionan que estos resultados son estables para 8 ó más muestras por firmante. En 2009, Vélez y otros [VSME09] introducen un modelo basado en snakes con memoria de forma. La característica principal de dicho modelo es la capacidad para recordar su forma inicial durante el proceso de ajuste a una imagen binaria de una firma. Los autores describen y comparan dos definiciones nuevas para la energía de la snake.La primera basada en un ajuste heurístico fino que hace uso de la firma en evaluación como mapa de potencial. La segunda definición se basa en la caracterización de la energía CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 17 ajustada a un modelo difuso TS que produce un expresión más simple y más intuitiva para el funcional de la energía. Los autores destacan dos características importante de la metodología, la primera, que solamente se requiere una muestra de entrenamiento para construir el modelo de la snake, y la segunda, que dicho modelo converge en unas pocas iteraciones. Se empleó una base de datos con muestras de 56 personas, y 6 muestras por cada firmante. Se reporta un valor de EER de 12.5 % para falsificaciones aleatorias. También en 2009 se reporta el trabajo más reciente del que se tiene conocimiento en esta línea, Wen y otros [WFTZ09], proponen un esquema de verificación orientado a minimizar el problema de la rotación en las firmas. Se plantean las características RPF (por sus siglas en inglés, Ring-Peripheral Features) que también ofrecen invarianza al desplazamiento y al escalamiento. Se entrenaron dos modelos para la firma, uno basado en la transformada FFT y el otro basado en HMM. Finalmente, y desmarcándolo de las líneas de trabajo presentadas hasta ahora, se menciona el trabajo realizado en 2001 por Baltzakis y Papamarkos [BP01] en donde presentan un sistema basado en NN para la detección de falsificaciones aleatorias. Su sistema emplea características globales (densidad de pixeles) y características de textura (matrices de co-ocurrencia) para representar una firma. Para cada una de las características se implementa una red tipo una-clase-una-red (OCON por sus siglas en inglés). En una primera etapa, el clasificador combina la decisión de las NN con la distancia Euclidiana obtenida usando los tres conjuntos de características. El resultado de esta primera etapa alimenta la entrada de una NN con Función de Base Radial (RBF por sus siglas en inglés) encargada de la decisión final. La base de datos usada contiene muestras de 115 firmantes, con entre 15 y 20 muestras originales por cada uno de ellos. Para el entrenamiento se emplean 1500 firmas originales, las demás son tomadas como falsificaciones aleatorias. Se reportan valores de FRR y FAR de 3% y 10% respectivamente. 2.2.2. Sistemas basados en Características Locales Las características locales representan una parte o una región delimitada de la firma. Son sensibles al ruido y a las variaciones en el trazado, pero no a los cambios presentes en otras zonas de las firma. Aunque computacionalmente son más costosas, suele ser más precisas en la representación de la firma. En 1992, Sabourin y Drouhard [SD92] inician la linea de trabajo basada en densidades. Los autores usaron una NN, con la PDF de la dirección de los trazos como vector global de características, pero su poder discriminante no resultó óptimo porque a pesar de ser invariante a la traslación y al escalado, no es invariante a la rotación. La base de datos contenía muestras de 20 firmantes, con un total de 800 muestras. En las pruebas, las falsificaciones corresponden a firmas originales de otros firmantes. Se reportan valores de FAR y FRR de 9% y 2% respectivamente. 18 2.2. REVISIÓN DEL ESTADO DEL ARTE En 1996,Drouhard y otros [DSG96] retoman esta línea y proponen lo que denominan como pattern spectrum y que describe morfológicamente la forma de la imagen. También denominado pecstrum, se calcula realizando sucesivas aperturas morfológicas empleando elementos estructurales que aumentan en tamaño, a estas secuencias se les denomina granulometrías y proporcionan un espectro a partir de un análisis local que toma los segmentos elementales como elementos estructurales. Se emplea una base de datos con muestras de 20 firmantes, con 40 muestras originales para cada uno. El sistema es evaluado para falsificaciones aleatorias y se reporta Error del 5%. Posteriormente en 1997, Sabourin y otros [SGP97] usaron la Granulometría para definir los descriptores locales de forma en un intento por caracterizar la cantidad de actividad contenida en cada celda de un rejilla superpuesta sobre la imagen. Se realizaron experimentos con un clasificador de vecinos más próximos y con un clasificador basado en umbral y se reportan valores de EER de 0.02% y 1% respectivamente. En 2000, El-Yacoubi y otros [EYJSB00] usan una malla aplicada sobre cada imagen para segmentarla en celdas. Para cada celda se calcula la densidad de pixeles como característica de tipo local. De este modo cada firma se representa por un vector de características en donde cada elemento de dicho vector corresponde a la densidad de pixeles asociada a cada columna de celdas de la malla aplicada. Las firmas genuinas de otros usuarios son usadas como falsificaciones en cada una de las pruebas. Se describen dos experimentos. En el primero se evalúa el sistema para una base de datos de 40 firmantes, con 30 muestras para cada uno. En el segundo caso, el número de firmantes es 60. Usando un HMM se reportan valores de EER de 0.46% y 0.91 % respectivamente para cada una de las pruebas realizadas. En 2001, Justino y otros [JBS01] usan un HMM discreto para detectar falsificaciones aleatorias, casuales y elaboradas. Se usan tres tipos de características (usando una malla): la densidad de pixeles, la distribución de los pixeles (usando el ExtendedShadow-Code, ESC) y la inclinación axial del eje principal. El número de estados del modelo para cada firmante se determina usando la validación cruzada. En un primer experimento, se emplea una base de datos con muestras de 40 firmantes, con 40 muestras originales para cada uno de ellos. Con esta base de datos se determina el tamaño óptimo del codebook para detectar las falsificaciones aleatorias. Con los valores óptimos estimados, se emplea un segunda base de datos con muestras de 60 firmantes, con 10 muestras originales, 10 falsificaciones casuales y 10 falsificaciones elaboradas para cada firmante. Se reportan valores de FRR de 2.83% y valores de FAR de 1.44%, 2.50% y 22.67 % para las falsificaciones aleatorias, casuales y elaboradas respectivamente. En 2002, Huang y Yan [HY02] usan modelos estadísticos basados en la distribución de los pixeles y en la composición estructural de la firma, para una clasificación inicial de falsificaciones elaboradas. En esta primera etapa un 32% de las firmas no pueden ser clasificadas con certeza. Para estas firma no clasificadas, los autores emplean un algoritmo de verificación basado en características estructurales, que compara la correlación estructural de la firma evaluada y la referencia. Se emplea una base de CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 19 datosconmuestrasde53firmantes, con 24 muestras originales y 144 falsificaciones elaboradas (realizadas por personas y simuladas). Para una combinación de las dos etapas de clasificación, se reportan valores de FRR y FAR de 6.3% y 8.2% respectivamente. En 2006, Armand y otros [ABM06] retoman esta línea y presentan un método basado en características estructurales de la firma que son calculadas usando una combinación del Modified Direction Feature (MDF) con otras características de origen geométrico. Se evalúa un clasificador NN basado en RBF. Se usa un subconjunto de la base de datos GPDSSignature, con muestras de 39 firmantes, con 24 muestras genuinas y 30 falsificaciones elaboradas para cada uno. Se reporta una tasa de verificación de 91%. En 2010 se reporta el trabajo más reciente del que se tiene conocimiento en esta línea, Bertolini y otros [BOJS10] proponen nuevas características grafométricas que consideran la curvatura de los segmentos más relevantes de la firma. La idea principal del trabajo es simular la forma de la firma haciendo uso de las curvas de Bezier y a partir de ellas calcular las características. Las pruebas se realizaron usando muestras de 100 firmantes. Se reportan valores de FRR de 5.16 % y de FAR de 5.16%, 3.16 % y 3.32% para falsificaciones Simuladas, Aleatorias y Simples respectivamente para un clasificador basado en disimilitud. Revisando una línea de trabajo diferente basada en transformaciones, en 1993, Sabourin y otros [SCG93] proponen una representación denominada Extended-ShadowCode (ESC). El ESC intrínsecamente es un factor de forma global pero que permite una proyección local de los trazos sin perder la localización de las mediciones en el espacio 2D; por tanto, ofrece un buen equilibrio entre las características globales del aspecto general de la firma, y las características locales de partes específicas sin que sea necesaria una segmentación de los trazos, que representa una difícil tarea. Se realizaron dos experimentos para los casos de un clasificador k-vecinos más cercanos y un clasificador de distancia mínima, respectivamente, para un base de datos de 800 firmas originales yfalsificaciones aleatorias correspondientes a 20 firmantes. Para el primer experimento se reporta un EER de 0.01 % con k=1, y un EER de 0.77 % para el segundo caso. En 1997, Bastos y otros [BBSK97] desarrollan un enfoque estructural para detectar falsificaciones aleatorias. El trazo de la firma se subdivide en secciones cónicas, semirrectas, elipses e hipérboles. Para una base de datos con muestras de 6 firmantes, con 20 muestras por cada uno, se reporta un indice de acierto promedio de 91 %. Pasando a los trabajos basados en características geométricas de la firma, En 1997, Guo y otros [GDA97] proponen un procedimiento para segmentar los trazos más relevantes de la firma en sus partes estadísticamente significativas para luego establecer una correspondencia local entre los elementos de la firma evaluada y un patrón de referencia establecido. Las características estimadas para los segmentos detectados corresponden con la curvatura, el ángulo de entrada y salida, así como la posición y tamaño relativo. Para una base de datos con muestras de 20 firmantes, con 40 muestras para cada uno, se reporta un FAR de 0.75 % y un FRR de 0 %. 20 2.2. REVISIÓN DEL ESTADO DEL ARTE En 2001, Guo y otros [GDR01] plantean una correspondencia local entre un modelo yunafirma a evaluar. La nueva firma es segmentada en trazos consecutivos que luego son comparados con los segmentos del modelo. El grado de similitud se determina comparando las propiedades geométricas de los subtrazos correspondientes y realizando una sumatoria ponderada de las diferencias. Para la comparación de los modelos se emplea el DTW. La base de datos usada contenía muestras de 10 firmantes, con 10 muestras originales, 20 falsificaciones elaboradas y 10 falsificaciones aleatorias. Se reportan FRR de 6 % y FAR de 12 % para el caso de las falsificaciones elaboradas y FRR de 2% y FAR de 3.3 % para las aleatorias. En 2003, Fang y otros [FLT+03]comparan individualmente y directamente los segmentos de trazo de una imagen de prueba y la imagen de referencia, empleando para ello un algoritmo de comparación elástica en 2-dimensiones. El objetivo es maximizar la similitud entre elementos comparados pero minimizando la deformación de las imágenes originales, empleando para ello un procedimiento de gradiente descendiente. Los elementos que son comparados corresponden a pequeñas lineas rectas que se aproximan al esqueleto de la firma. Para este caso se reporta un EER de 24%. En 2005, Ferrer y otros [FAT05] proponen un conjunto de características de tipo geométrico basado en la descripción del contorno de la firma y la distribución interna de los trazos, realizados tanto en coordenadas cartesianas como polares. Las características son calculadas empleado aritmética de punto fijo de 16 bits. Para evaluar el desempeño del sistema se evalúan tres clasificadores: Distancia euclidiana, HMM y SVM Ligth. Se emplea la base de datos GPDSSignature con muestras de 160 firmantes, con 24 muestras genuinas y 30 falsificaciones simples. Los mejores resultados se reportan para el HMM con valores para FRR de 2.2 % y FAR de 3.3 % para el caso de falsificaciones aleatorias, y valores para FRR de 14.1 % y FAR de 12.6 % para falsificaciones simples. En 2006, Majhi y otros [MRB06] sugieren un nuevo esquema para la extracción de características basado en el cálculo de centros geométricos para diferentes versiones de la imagen. La imagen de la firma es dividida horizontal o verticalmente de forma intercalada con base en la posición del centro geométrico. Para la verificación se emplea un clasificador de distancia euclidiana. La selección del umbral de decisión se hace a partir de los valores de media y desviación estándar calculados sobre la imagen. La base de datos utilizada contiene 30 muestras genuinas y 30 falsificaciones simples para cada firmante, no hay claridad sobre el número de firmantes. Se reportan valores para FRR de 14.58 % y para FRR de 2.08 %, 9.75 % y 16.36 % para firmas aleatorias, simples y elaboradas, respectivamente. No hay claridad en cuanto a la cantidad de falsificaciones elaboradas tenidas en cuenta. También en 2006, Chen y otros [CS06] presentan un enfoque basado en Comparación Gráfica de firmas manuscritas. Cada firma se representa con un conjuntos de puntos, el cual incluye los extremos locales de diferentes tipos a lo largo del contorno de la firma. La comparación gráfica incluye una medida de deformación y una función CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 21 de mapeo entre conjuntos de puntos, así como una correspondencia local de la firma evaluada y la referencia. Las mediciones de deformación y similitud se combinan para tomar la decisión final. Se emplea un base de datos con muestras de 55 firmantes, con 24 muestras genuinas y 24 falsificaciones simples para cada uno. Se reporta un EER de 8 %. En 2007, Nguyen y otros [NBML07] proponen un método basado en características estructurales de la firma. Las características se calculan a partir del contorno de la firma y usando tanto enfoque MDF (Modified Direction Feature) como una versión modificada del mismo EMDF (Enhanced MDF). El sistema es evaluado para dos tipos de clasificadores: NN y SVM Ligth. Se emplea la base de datos GPDSSignature con muestras de 160 firmantes, con 24 muestras genuinas y 30 falsificaciones elaboradas para cada uno. Se reporta un valor de EER de 23% y 18% para los clasificadores basados en RBF-NN y SVM con kernel RBF respectivamente. También en 2007, El autor de este trabajo y otros [VFTA07a] analizan el efecto de la resolución de una imagen en la VFM. Para las características propuestas en [FAT05], La resolución de la imagen se disminuye progresivamente desde 600 hasta 45ppp. Se evalúa el sistema para falsificaciones aleatorias y simples empleando un HMM. Se menciona que es suficiente una resolución de 150ppp para el calculo de las características referidas, ya que para valores superiores a este no se manifiesta una ganancia en el desempeño del sistema. Se reportan valores de EER de 1.6 % y 10.8% para falsificaciones aleatorias y simples respectivamente. Se debe mencionar que [JBS01], [HY02] y [ABM06], descritos en la línea de trabajo basada en densidad, pueden ser incluidos aquí si se tiene en cuenta las características geométricas usadas por los autores. Finalmente se menciona el trabajo reportado en 2000 por Ismai y Gad [IG00]. Los autores exploran el uso de conceptos de lógica difusa para la verificación de firmas de origen arábigo. Los autores emplean características locales para formar un primer conjunto de características, que permiten representar las posiciones de los pixeles y que son poco sensibles al ruido. En lugar de usar un umbral bien definido, se determinan un conjunto de reglas difusas para tomar la decisión final con un determinado grado de certeza. Para una base de datos con muestras de 22 firmantes, con 10 muestras genuinas y 5 falsificaciones elaboradas para cada uno de ellos, se reporta un nivel de confianza promedio del 98 %. 2.2.3. Sistemas basados en la Combinación de Características Globales y Locales En 2002, Quek y Zhou [QZ02] investigaron sobre la viabilidad del uso del producto pseudo-externo basado en una NN difusa (POPFNN-TVN por sus siglas en inglés) para detectar firmas elaboradas. Los autores usaron características globales de la línea base 22 2.2. REVISIÓN DEL ESTADO DEL ARTE (las posiciones horizontal y vertical dentro de la firma que corresponden con el pico del histograma de las proyecciones vertical y horizontal de la respectiva imagen binarizada), características de presión (regiones de alta presión), características de inclinación (examinando los vecinos de cada pixel en la imagen esqueletizada). Los autores realizan dos tipos de experimentos. En primer lugar emplean firmas genuinas y falsificaciones para el entrenamiento, y para el otro caso, emplean solo firmas originales. La base de datos usada contenía muestras de 15 firmantes (de 3 grupos étnicos diferentes y 5 firmantes en cada grupo), con 5 muestras originales y 5 falsificaciones elaboradas para cada uno de ellos. Cuando las muestras originales y falsificaciones se emplean para las pruebas, se reporta un EER de 23 %, y para el caso en que solo se emplean las genuinas para entrenar, se menciona que los resultados obtenidos son comparables. En 2005, Justino y otros [JBS05] comparan un clasificador basado en Maquinas de Soporte Vectorial (SVM por sus siglas en inglés) con otro basado en Modelos Ocultos de Markov (HMM) bajo dos condiciones específicas: la primera, el número de muestras usadas en el entrenamiento, y la segunda, el tipo de falsificaciones empleadas. Los autores emplean un conjunto de características Grafométricas (de tipo estáticas y pseudodinámicas) obtenidas por medio de un esquema de segmentación basado en una malla. La densidad de pixeles y el centro de masa de cada celda de dicha malla corresponden a las características estáticas. El angulo de curvatura del trazo mas grande contenido en cada celda y la inclinación predominante en cada celda son las características pseudodinámicas empleadas. No se reportan valores de EER específicos, solo se destaca que para los experimentos realizados se aprecia un mejor desempeño del clasificador basado en SVM a partir de las curvas ROC. También en 2005, Ozgunduz y otros [OSK05] presentan un enfoque basado en características globales, de dirección y basadas en una malla. Las globales brindan información para casos específicos de la forma de la firma. Al aplicar mascaras sobre la imagen, se obtiene la información de dirección de cada trazo. La malla aplicada permite tener información general de la apariencia de la firma. Se emplea una base de datos con muestras de 70 personas, con 16 muestras genuinas y 16 falsificaciones simples para cada uno. Usando un clasificador SVM se reportan valores para FFR y FAR de 2 % y 11% respectivamente. 2.2.4. Sistemas basados en Características Pseudodinámicas Teniendo en cuenta la línea de investigación que será abordada en la presente propuesta de Tesis, a continuación se presenta una descripción de los trabajos mas representativos que describen metodologías de verificación de firmas tipo off-line basadas en características pseudo-dinámicas, esto es, características que intentan representar la información dinámica de la firma y que no se encuentra disponible en una imagen estática. CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 23 En 1986, Ammar y otros [AYF86] plantearon por primera vez la posibilidad de recuperar cierta información correspondiente a la dinámica de una firma a partir de una imagen estática de la misma. Para su análisis, la imagen es conservada en escala de grises. Una vez eliminado el fondo de la imagen, se determina un Umbral de Alta Presión (UAP) a partir de la información del histograma, se asume que aquellos trazos realizados con una presión mayor aparecen con tonalidades mas oscuras en la imagen. Con ésta información se calcula el porcentaje de puntos que superan el umbral calculado respecto al número total de puntos que conforman la imagen de la firma. Para realizar la verificación, además de este factor de alta presión, los autores conforman el vector de características con otras mediciones hechas a partir del histograma de la imagen, como lo valores mínimos y máximos de nivel de gris de la imagen, el valor mismo del UAP, y el rango dinámico de la firma, entre otros. Para las pruebas se uso un clasificador basado en distancias y una base de datos con muestras de 20 personas, con 10 muestras originales y 10 falsificaciones simples para cada uno, el sistema presentó un desempeño correspondiente a un EER de 5.25 %. En 1997, Huang y Yan [HY97] retoman la idea y proponen un sistema basado en características geométricas que incluyen informaciónextraídaapartirdelaimagen en niveles de gris y que brindan información Pseudodinámica de la firma. Plantean el cálculo del Núcleo, que esta conformado por los elementos de la imagen cuyo nivel de gris corresponde a un máximo local en el histograma. Para determinar los puntos que pertenecen tanto al Contorno como a las Regiones de Alta Presión (RAP), se determinar dos umbrales a partir de los niveles de gris máximos y mínimos presentes en el histograma de la imagen. Las fronteras en las 8 direcciones también fueron tenidas en cuenta en este trabajo. Se usa un base de datos con muestras de 20 firmantes, con 24 muestras genuinas y 24 falsificaciones simples para cada uno. Adicionalmente, los autores generaron muestras artificiales para el entrenamiento de una NN, con el finde simular algunas alteraciones naturales presentes en un aplicación real (rotación, escalado, inclinación y perspectiva). Se reporta un EER de 11.45 %. En 1999, Fang y otros [FWL+99] proponen un método inspirado en la técnica de los examinadores expertos, correspondiente a un criterio de suavidad de los trazos de una firma y orientado a la detección de falsificaciones elaboradas. Los autores observaron que si se comparan detalladamente una firmagenuinayotrafalsa,esposibleafirmar que las falsificaciones poseen trazos menos suaves y menos naturales respecto a la muestra genuina, especialmente para firmas que contienen caracteres cursivos. A partir de la imagen esqueletizada, se detectan los trazos que superen una longitud mínima, y se procede a calcular un Indice de Suavidad (SMI por sus siglas en inglés) para cada uno de ellos. Cada trazo es clasificado como suave o no-suave para finalmente estimar un relación entre el número de trazos suaves y el número total de trazos encontrados inicialmente en la firma. La característica propuesta se evalúa en combinación con otras características globales que caracterizan el aspecto general de la firma. Empleando una base de datos con muestras de 55 firmantes, 24 muestras genuinas y 24 falsificaciones elaboradas, y un clasificador basado en la medida de disimilitud, el sistema reporta un EER de 21.7 %. 24 2.2. REVISIÓN DEL ESTADO DEL ARTE En 2000, Sansone y Vento [SV00] proponen un sistema multi-experto serial de tres etapas. El primer experto, emplea una sola característica de tipo global correspondiente a las proyecciones sobre las 4 direcciones del contorno de la firma, para detectar falsificaciones aleatorias. La segunda etapa evalúa las firmas que no fueron clasificadas con el nivel de certeza adecuado en la primera etapa, y para ello determina las RAP de la firma basándose en el procedimiento descrito en [HY97]. En caso de no lograrse un clasificación con la suficiente certeza en esta segunda etapa, la salida se alimenta hacia una tercera etapa, en donde se tomará una decisión final con base en los resultados de las dos etapas anteriores. Para las pruebas realizadas sobre una base de datos con muestras de 49 firmantes, con 20 muestras genuinas, 10 falsificaciones simples y 10 falsificaciones elaboradas para cada uno, el sistema reporta lo siguientes valores: El primer experto de forma individual obtiene valor de FRR de 2.65 % y FRR de 0.09 %, 7.14 % y 38.98 % para falsificaciones aleatorias, simples y elaboradas, respectivamente. El segundo experto de forma individual (basado en RAP) obtiene valores de FRR de 12.04 % y FRR de 0.86%, 1.45% y 26.12% para falsificaciones aleatorias, simples y elaboradas, respectivamente. La combinación de las dos etapas, que corresponde al sistema propuesto obtiene valores de FRR de 5.71 % y FAR de 0.03 %, 4.29 % y 20.82 % para falsificaciones aleatorias, simples y elaboradas, respectivamente. También en 2000, Guo [JDA00] presentan una modificación de su trabajo anterior [GDA97], en donde se incorpora una función de coste independiente para cada firmante por lo que la caracterización en este caso es dependiente del escritor. Así mismo, las características usadas aquí corresponden a la magnitud del gradiente y su dirección, los niveles de gris y el ancho del trazo. El sistema se evalúa para falsificaciones simples y se reporta un EER de 9%. En 2005, Oliveira y otros [OJFS05] discuten la VFM en el contexto de la grafología. Los autores describen los principales conceptos de la grafología y proponen un conjunto de características orientado a la VFM. Así, el calibre, la proporción, el espaciamiento, el alineamiento respecto a la línea base, la progresión, la presión y la inclinación entre otras, son las características analizadas en este trabajo. Para el calculo de las características se empleo una malla con un tamaño de celda de 16x40 pixeles determinado experimentalmente. Se emplea una base de datos con muestras de 60 firmantes, con 40 muestras genuinas y 20 falsificaciones (10 simples y 10 simuladas) para cada uno. Empleando un HMM para la verificación, se reportan los diferentes valores de ERR obtenidos para las características pseudo-dinámicas evaluadas: Densidad de pixeles 7.87%, la distribución de pixeles 7.65 %, la inclinación 7.92 %, la progresión 9.15 % y la forma 11.30 %. En 2005, Lv y otros [LWWZ05] proponen un método que emplea características estáticas y dinámicas. Como características estáticas se usan 8 momentos estadísticos y las distribución de pixeles en 16 direcciones. Para el caso de las características dinámicas, los autores emplean la distribución de niveles de gris y la distribución del ancho de trazos. Para la verificación se usa una SVM y se evalúa el desempeño para tres tipos de kernel: Polinomial, RBF y Sigmoide. Se usa una base de datos con muestras de 20 CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 25 firmantes, con 25 muestras genuinas y 30 falsificaciones simples. Se realizaron pruebas individuales para cada una de las características así como una combinación de todas ellas. Para los momentos se reporta un EER de 18.5 %, para distribución direccional un EER de 12.4%, para la distribución de niveles de gris un EER de 31.1 %, para la distribución de ancho de trazo un EER de 28 % y par la combinación de todas las anteriores un EER de 5.0 %. Los datos anteriores corresponden a una SVM con kernel tipo RBF. En ese mismo año, Mitra y otros [MKA05] proponen un enfoque orientado a la detección de falsificaciones elaboradas. Se considera la información de presión ejercida sobre el bolígrafo a partir de la dinámica espacial de la imagen. Los autores proponen 10 características que incluyen la densidad de puntos presentes en Regiones de Baja Presión (RBP), y una relación de densidades entre RAP y RBP. Para la clasificación se propone un criterio adaptativo. La base de datos empleada contiene muestras de 20 firmantes, 10 muestras genuinas y 10 falsificaciones elaboradas para cada uno. Todas las muestras fueron realizadas con el mismo bolígrafo. Para un umbral de decisión simple se reporta un valor de ERR de 6.5 %, para el caso de un umbral modificado se tiene un ERR de 5.25 % y para un umbral flexible se presenta un EER de 3.25% 2.2.5. Características basadas en el análisis de la tinta Las metodologías pertenecientes a la VFM pueden ser divididas en tres grandes grupos: Los métodos matemáticos que estiman el orden temporal con que son realizado los trazos [AA93] [DR95] [NdPH05] [Abu07]; los métodos inspirados en la teoría de control y que recuperan las características temporales a partir de la geometría de los trazos, como por ejemplo la curvatura [Pla97] [SGP97] [ABM06]; y finalmente, los métodos que analizan las variaciones en la intensidad y/o grosor de los trazos [AYF86] [DR95] [SPL92] [ZZL+07]. Sin embargo, los investigadores apenas han dado importancia al estudio de la influencia de las herramientas como es el caso del papel, la tinta y el bolígrafo; sobre los trazos resultantes. Este apartado se dedica al modelado de proceso de deposición de tinta en el papel en aquello que pueda utilizarse en VFM. Existen diversas metodologías para la reconstrucción de la información dinámica a partir del análisis de tinta en muestras manuscritas. En él campo del análisis forense de documentos, dichas metodologías se basan principalmente en la inspección microscópica de los trazos y en suposiciones sobre el proceso de escritura. Lo anterior ha dado lugar al desarrollo del modelo de distribución de tinta propuesto por Franke [FG98]. Este primer modelo, permitía su adaptación para propiedades específicas del bolígrafo usado (de tinta solida, liquida ó viscosa). Su debilidad era que esa adaptación se hacía en forma manual mediante la selección del modelo de distribución de la tinta de acuerdo al tipo de bolígrafo. En [FBS02], los autores proponen una evolución para el modelo. Se determina automáticamente el tipo de bolígrafo usado, analizando los trazos estáticos. Estos trabajos abren la posibilidad para desarrollar procedimientos que minimicen el efecto del uso de diferentes tipos de bolígrafo sobre los sistemas de verificación automática. 32 2.2. REVISIÓN DEL ESTADO DEL ARTE 2.2.6. Comentarios sobre la revisión del estado del arte Con el fin de ofrecer un medio más practico para observar el desarrollo cronológico de las diferentes lineas de investigación presentes en el área de la VFM y basados en los trabajos revisados en esta sección, se presentan las tablas 2.2 y 2.3, así como la figura 2.8. Dentro de los trabajos que usan características globales, pueden identificarse cuatro líneas de trabajo principales. En primer lugar, los trabajos que hacen uso del DTW para comparar modelos, por otro lado están aquellos trabajos que basan la caracterización en los contornos de la firma, una tercera linea la definen los trabajos que hacen uso de las transformaciones y finalmente la línea que considera la densidad global de pixeles en la imagen. Para el caso de los trabajos basados en características locales, se tienen 5 líneas. Laprimeraladefinen los trabajos que consideran la densidad localizada de pixeles. Por otro lado, se tienen los trabajos que tienen en cuenta características geométricas de la firma. Los trabajos que hacen uso de transformaciones forman la tercera línea. En cuarto lugar se tienen los trabajos que hacen uso de representaciones matemáticas de la firma, y finalmente se tiene la aproximación difusa. En cuanto a los trabajos basados en características pseudodinámicas, se tiene una línea principal basada en los puntos de alta presión. Solo unos pocos trabajos, incluyen información sobre la suavidad de los trazos y/o o el ancho de los mismos. Si nos referimos a los trabajos que tienen como objetivo el análisis de la tinta, se destacan los trabajos realizados por Franke. CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 33 Tabla 2.2: Resumen de los trabajos publicados para sistemas VFM del tipo off-line. L:Local, G: Global, C: Combinación, P: Pseudodinámicas. Año Ref. Biblio Clasificador Característica empleada Tipo 1986 AYF86 Distancias Umbral Alta Presión P 1990 WG90 DTW Curvatura,ángulo de inclinación G 1992 SD92 NN PDF de trazos L 1993 SB93 DTW Proyección de firma en varios ángulos G SCG93 KNN ESC L 1994 PB94 Globales básicas G NP94 DTW Contorno G CRVR94 Contorno y Geométricos G 1996 DSG96 Pattern spectrum - análisis estructural L 1997 YY97 DTW Proyección del perfilsobreejex G SDW97 Dist. mín Matriz forma G SGP97 KNN Granulometría L BBSK Estructural - secciones cónicas, semirectas,etc L GDA97 Estructural - segment. en trazos, estadisticam. L HY97 geométricas - Núcleo, Contorno, RAP, P 1999 DLHT99 Contorno cerrado, Wavelet G FB99 NN Steerable Wavelet G KCT99 NN Transformada Hough G FWL99 Distancias Indice de Suavidad P 2000 IG Fuzzy Distribución de pixeles L EYJSB00 HMM Densidad pixeles - malla L DA00 Niveles gris, ancho, gradiente P Continua en la siguiente página.. . . 34 2.2. REVISIÓN DEL ESTADO DEL ARTE Tabla 2.2 – Continuación Año Ref. Biblio Clasificador Característica empleada Tipo SV00 Multi-exp Proyecciones contorno, RAP P 2001 BP01 NN Densidad pixeles, textura G GDR01 DTW Propiedades geométricas de subtrazos L JBS01 HMM Densidad de pixeles, ESC, inclinación L 2002 FLT02 Distancia Características periféricas, comparación elástica G MYMY02 Disimilitud Función de desplazamiento G XL02 RedBayes Perfiles superior e inferior G HY02 Estructural - distribución de pixeles L QZ02 NN+Fuzzy Linea base, RAP, inclinación C 2003 FLT+03 DTW Proyección de la firma (H + V) G FLT03 DTW Comparación elástica en 2D, segmentos de trazo L 2005 CS05 Distancia Contorno sup e inf, momentos de Zernike G FAT05 HMM+SVML Contorno de firma, distribución de trazos L JBS05 HMM+SVM Grafometría, dens. de pixeles, centros d masa C OSK05 SVM Dirección, aplica malla C OJFS05 HMM Grafología P LWWZ05 SVM Moment estad, distrib pixels, gray-level, ancho C MKA05 Umbral RBP, RAP P 2006 WHJ06 Fuzzy Elems Espect de Func Densid Gradiente Direcc. G CS06 Distancia Puntos del Contorno, mapeo. L MRB06 Distancia Centros geométricos, varias divisiones H + V L ABM06 NN Estrucutral - Modified Direction Feature L 2007 FFMDOG Cancelabilidad de la firma G SR07 DTW modif. Proyección Vertical de la firma G NBML07 NN+SVML Contorno - MDF modificado L Continua en la siguiente página.. . . CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 35 Tabla 2.2 – Continuación Año Ref. Biblio Clasificador Característica empleada Tipo VFTA07 HMM Efecto de la resolución de la imagen L 2008 LM08 Disimilitud Umbralizado adaptativo de características (AFT) G 2009 VSME09 Fuzzy TS Snakes G WFTZ09 HMM Ring-peripheral features G 2010 BOJS10 Disimilitud Curvas de Bezier L 36 2.2. REVISIÓN DEL ESTADO DEL ARTE Tabla 2.3: Organización cronológica de los trabajos publicados según tipo de características usado. Un nivel de gris más oscuro representa un mayor número de trabajos revisados. 86 90 92 93 94 96 97 99 00 01 02 03 05 06 07 08 09 10 Pseudo-dinámica Proyecciones Densidad de Pix. Contorno Geométricas Transformaciones Momentos Estad. CAPÍTULO 2. ESTADO ACTUAL EN BIOMETRÍA DE FIRMA ESTÁTICA 37 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 2006 2008 2010 0 1 2 3 4 5 6 7 Figura 2.8: Número de publicaciones en ASV tipo off-line por año, revisadas en este trabajo. Resumen En este capítulo se ha presentado una revisión del estado actual de la biometría de firma estática, referenciando los trabajos más representativos y que corresponden a sistemas basados en características de diferentes tipos. Específicamente para los trabajos basados en características pseudo-dinámicas se reconoce el esfuerzo por recuperar la información dinámica no disponible en las firmas estáticas. En cuanto a las características basadas en análisis de texturas, los resultados sugieren mayores esfuerzos para desarrollar metodologías que permitan explotar la información de los niveles de gris en una imagen sin la influencia que tiene el tipo de tinta con que se realizan los trazos. Es por esta razón, que el presente trabajo pretende realizar avances que mejoren la VFM empleando análisis estadístico de texturas, teniendo en cuenta la influencia del tipo de tinta sobre los niveles de gris con que se representa la firma. En el siguiente capítulo se describen las bases de datos utilizadas en este estudio y se plantean los procedimientos para el pre-procesamiento de las muestras analizadas. 38 2.2. REVISIÓN DEL ESTADO DEL ARTE Capítulo 3 Esquema general de un sistema AVFM 3.1. Sistemas AVFM La figura 3.1 presenta el diagrama de bloques de un sistema AVFM. Preprocesado Características Clasificación Acepta/Rechaza B.D. Almacena Verificación Captura Crea modelo Figura 3.1: diagrama general de un sistema AVFM. A continuación se describe el esquema general de un Sistema Automatizado de Verificación de Firmas Manuscritas: Captura: Teniendo en cuenta que en el presente trabajo se considera un sistema tipo off-line, el sensor corresponde a un escáner. En la captura de las imágenes en niveles de gris, es posible determinar la resolución de la imagen resultante. Preprocesado: Una vez capturada la imagen, es necesario realizar un preprocesado 39 40 3.2. BASES DE DATOS orientado a la segmentación de la firma. Para el caso en que se realice la digitalización de una plantilla en la que están contenidas varias realizaciones de una firma, se hace uso de un procedimiento para la detección, segmentación y posterior creación de archivos individuales para las firmas encontradas en la plantilla. En este punto se define el formato que deberá tener el nombre de cada archivo. Almacenamiento: Cada muestra analizada, entraaformarpartedelabasededatos del sistema. En una primera etapa, cuando se realiza la digitalización de una nueva base de datos, todas las muestras son almacenadas para una etapa posterior de entrenamiento. Validación: Una vez entrenado el sistema, cada nueva muestra, además de ser almacenada en la base de datos, es validada por el sistema. Esto es, determinar si la firma corresponde a quien dice ser. Base de Datos (BD): Corresponde a uno de los componentes más críticos de este tipo de sistemas, ya que demanda una logística importante para su creación. Generalmente es necesario la creación de una BD propia debido al número reducido de BD públicas disponibles. Lo anterior demanda de cada autor una descripción completa de la base de datos creada para cada trabajo. Características: Como se mencionó en el capítulo anterior, se tienen varias alternativas para esta etapa (Globales, locales, pseudo-dinámicas). Es posible la combinación de diferentes características, pertenecientes o no al mismo grupo. El objetivo es capturar la información más relevante que permite realizar la verificación. Creación de modelo: Una vez definidas las características a usar, se realiza el entrenamiento del modelo que permitirá discriminar entre una firma genuina y las falsificaciones. Es importante mencionar que el modelo creado, debe ser lo suficientemente robusto frente a las variaciones naturales del patrón original. De igual forma, se debe tener en cuenta el número reducido de muestras de las que por lo general se dispone. Clasificación: Cada muestra analizada por el sistema es clasificada como genuina ofalsificación. Como se mencionó en 2.1, el desempeño del este tipo de sistemas puede ser cuantificado mediante el uso de los valores FAR, FRR, y EER. Teniendo en cuenta la descripción realizada, en las siguientes secciones se presentan con mayor detalle las bases de datos, los procedimientos de preprocesado y la metodología de experimentación, usadas en el presente trabajo. Para la caracterización, se han destinado los capítulos 4, 5, y 6 de este documento. 3.2. Bases de datos A pesar del gran número de trabajos realizados en el área de la verificación off-line de firmas manuscritas, uno de los principales problemas al que se enfrenta un investigador en el proceso de desarrollo, prueba y evaluación de un nuevo sistema, sigue siendo CAPÍTULO 3. ESQUEMA GENERAL DE UN SISTEMA AVFM 41 la falta de bases de datos de referencia, de gran tamaño, y disponibles públicamente. Las bases de datos a las que se ha tenido acceso se relacionan en la tabla 3.1, como se puede apreciar, su tamaño es reducido. Tabla 3.1: Bases de datos públicas de firmas estáticas. Nombre BD #Firmante #Genuinas #Falsificaciones GPDSsignature [FAT05] 160 24 24 MCYT-75 [OGFADS+03] 75 15 15 De lo anterior se desprende que los diferentes grupos de investigación en el área, opten por crear sus propias bases de datos para llevar a cabo la evaluación de los sistemas propuestos. Esto hace difícil la comparación entre las diferentes metodologías. 3.2.1. GPDS corpus El Grupo de Procesado Digital de Señales (GPDS) de la Universidad de las Palmas de Gran Canaria, ha dedicado esfuerzos para la creación de una base de datos de gran tamaño denominada GPDS-960 Corpus [VFTA07b]. Esta base de datos contiene muestras de 960 firmantes, con 24 muestras genuinas y 24 falsificaciones para cada uno. Se creó una plantilla con 24 recuadros de 2 tamaños diferentes (12 recuadros de 5x3.5cm y 12 de 5.5x2.5cm). Los folios usados para la recolección de las muestras fueron escaneados con una resolución de 300ppp. Teniendo en cuenta que para el presente estudio se analizan características que brindan información indirecta acerca de la dinámica del proceso de firmado, se decidió digitalizar de nuevo las bases de datos desarrolladas por el Grupo de Procesado Digital de Señales, con el fin de aumentar la cantidad de información disponible en cada imagen. Las bases de datos fueron redigitalizadas a una resolución de 600ppp. En el proceso de redigitalización, se evidenció el deterioro y/o pérdida de algunos folios que contenian muestras de firmas, por lo que la base de datos obtenida contiene muestras de 850 firmantes. Teniendo en cuenta la epoca en la que fueron recolectadas las muestras originalmente, el corpus fue dividido en dos: GPDS100 y GPDS750. En la sección 3.2.3 se describen los procedimientos realizados para la puesta a punto de las dos bases de datos tratadas. 3.2.2. MCYT corpus Con el animo de tener una base de datos de referencia, en el presente estudio se tiene en cuenta también un subcorpus de la base de datos multimodal creada por el Grupo de reconocimiento biométrico - ATVS de la Escuela Politécnica Superior de la Universidad Autónoma de Madrid. Se encuentra disponible en http://atvs.ii.uam.es/databases.jsp. El corpus MCYT-SignatureOff-75 [FAAHMMOG04], contiene muestras de 75 firmantes. 48 3.4. PREPROCESAMIENTO DEL HISTOGRAMA (a) Imagen original. (b) Imagen posterizada. (c) Fondo eliminado. Figura 3.8: Posterización usada para la eliminación del fondo. Imagen tomada de MCYT corpus. 3.4. Preprocesamiento del Histograma Una vez segmentada la firma, se plantea un procedimiento para reducir la influencia de los diferentes tipos de tinta que puede usar un firmante. Se propone un desplazamiento del histograma de la firma hacia el valor cero (negro). Este desplazamiento debe ser realizado asegurando que el fondo se mantiene en un valor de nivel de gris de 255 (blanco). Si aseguramos que el valor del nivel de gris más oscuro presente en la firma es siempre 0, el rango dinámico del histograma reflejará de mejor manera las características propias del estilo del firmante. Este procedimiento se propone en consonancia con el trabajo de Franke [FR04], en donde se muestra que un cambio en el color de la tinta usada (no un cambio en el tipo de tinta) implica un desplazamiento del histograma de la firma. El procedimiento planteado se logra simplemente restando el valor mínimo de nivel de gris de los demás pixeles presentes en la imagen de la firma, esto es IG(x, y)=IS(x, y),siI S(x, y) = 255 IS(x, y)−min {IS(x, y)},otrocaso (3.4) donde IG(x, y)es la imagen de la firma segmentada y con histograma desplazado hacia cero. La figura 3.9 ilustra el efecto de este procedimiento. CAPÍTULO 3. ESQUEMA GENERAL DE UN SISTEMA AVFM 49 (a) Histograma original (b) Imagen original (c) Histograma desplazado (d) Imagen con histograma desplazado Figura 3.9: Preprocesamiento del histograma mediante desplazamiento hacia cero. Una vez preprocesadas las imágenes, y según lo planteado en la figura 3.1, se da paso al proceso de caracterización. Sin embargo y con el ánimo de presentar resultados en el momento de describir cada uno de los métodos de caracterización tenidos en cuenta en este trabajo, a continuación se describe primero la metodología experimental adoptada para la realización de las pruebas hechas en el desarrollo de esta tesis. Dicha metodología es el fruto de los invaluables comentarios recibidos en los diferentes escenarios académicos en donde se presentaron los resultados preliminares de este trabajo. Se han destinado los capítulos 4 y 5 para la descripción completa de la metodología de caracterización desarrollada. 3.5. Metodología de Evaluación Una vez preprocesada, cada muestra es caracterizada y representada por un vector de parámetros que alimenta la etapa de verificación. En este trabajo, cada firmante es modelado usando Mínimos Cuadrados-Máquinas de Soporte Vectorial (LS-SVM pos sus siglas en inglés). El entrenamiento del modelo se realiza con 5 y 10 muestras genuinas como muestras positivas. Lo anterior se hizo con el fin de realizar un análisis del desempeño del sistema respecto al número de muestras originales usadas para la construcción del modelo. Estas muestras genuinas son escogidas de forma aleatoria. Como muestras negativas se usaron falsificaciones de tipo aleatorio (muestras genuinas de otros firmantes). El uso 50 3.5. METODOLOGÍA DE EVALUACIÓN de este tipo de muestras fue planteado en [BOJS09], y para este trabajo se tomo una muestragenuinadecadaunodelosotrosfirmantes de una base de datos, esto es, 74 para el caso de MCYT, 99 para GPDS100 y 749 para GPDS750. Teniendo en cuenta el número reducido de muestras disponibles para el entrenamiento, se empleó el procedimiento de Validación-cruzada Dejando-uno-fuera (LOOCV por las siglas en inglés de leave-one-out cross-validation), que se describe en el anexo C, para determinar el valor de los parámetros (γ,C) del clasificador LS-SVM con kernel RBF. Para la prueba, se usaron falsificaciones aleatorias y también falsificaciones elaboradas. Para el caso de las falsificaciones aleatorias, se tomo una firma genuina de cada uno de los otros usuarios de la base de datos (asegurando que fuese diferente a la muestra usada en el entrenamiento). Para el caso de las falsificaciones elaboradas, se usaron todas las muestras disponibles en la base de datos, esto es, 15 en la MCYT y 24 en la GPDS. Con el fin de obtener resultados mas confiables, los procedimientos de entrenamiento y prueba fueron repetidos en 10 ocasiones con conjuntos de datos de entrenamiento y prueba diferentes. En cuanto al umbral necesario para determinar los valores de FAR y FRR, y teniendo en cuenta que el clasificador LS-SVM fue entrenado con muestras etiquetas como ’+1’ para las muestras genuinas y ’-1’ para las muestras de falsificaciones, el valor establecido fue cero para todos los firmantes. Es decir, si la LS-SVM entrega un valor mayor a cero en su salida, la firma es aceptada como genuina. Si la LS-SVM entrega un valor menor que cero en la salida, la firma se considera como falsificación y por tanto se rechaza. Resumen En este capítulo se ha establecido el marco básico para poder realizar las aportaciones de la tesis. Dicho marco lo conforman las etapas de preprocesado de las muestras, las bases de datos, el esquema de verificación y la metodología de experimentación; todas orientadas al uso de la información contenida en los niveles de gris de los trazos que conforman una firma. En el siguiente capítulo se inicia la descripción de las características estudiadas en este trabajo, y se presentan los resultados obtenidos para cada caso. Se ha querido seguir un orden cronológico con el ánimo de visualizar el desarrollo de la metodología final presentada aquí. Con el fin de realizar una comparación justa de los resultados obtenidos con cada una de las diferentes bases de datos empleadas, inicialmente se realizaron las pruebas tomando igual número de firmantes para todos los casos. Teniendo en cuenta que el menor número de firmantes era 75 (para el caso de MCYT), se tomaron pues las muestras de los primeros 75 firmantes pertenecientes a cada base de datos. Se ha destinado una sección al final de este documento, para presentar los resultados obtenidos con la totalidad de las muestras. Capítulo 4 Caracterización de firmas basada en información de los niveles de gris Se describen las diferentes etapas seguidas en el desarrollo de la metodología de extracción de características. Las primeras pruebas realizadas para tener en cuenta la información de los niveles de gris de la firma, corresponden a la caracterización del histograma de la imagen. Conocedores de las limitaciones de este tipo caracterización, ya que el histograma es una medida de primer orden en el sentido que solo analiza cada pixel sin relacionarlo con sus vecinos, creemos que es interesante conocer el desempeño de dicha aproximación. 4.1. Características estadísticas a partir del histograma. Las características estadísticas de primer orden tienen en cuenta el valor individual de niveles de gris para cada pixel en una matriz Igde dimensiones MxN, pero sin considerar la disposición espacial, p.e. Diferentes texturas pueden tener el mismo histograma de niveles de gris. Uno de los métodos mas simples para describir una textura es utilizando los momentos del histograma de niveles de gris de una imagen o región. Sea gla intensidad de una imagen discreta (g=0para el negro y g= 255 para el blanco) y h(g), g=0,1,...,L−1el correspondiente histograma normalizado ( L h(g)=1), donde Les el número de niveles. El momento n-ésimo de grespecto a la media es: μn(g)= L−1  g=0 (g−¯g)nh(g)(4.1) donde ¯ges el valor medio de g(la intensidad media): ¯g= L−1  g=0 g·h(g)(4.2) El segundo momento (llamado también varianza, σ2 g)esdeparticularimportancia porque es la medida del contraste del nivel de gris que se puede utilizar para establecer descriptores de suavidad relativa. Por ejemplo : 51 52 4.1. CARACTERÍSTICAS A PARTIR DEL HISTOGRAMA. R=1−1 1+σ2 g (4.3) es cercano a 0para áreas de intensidad constante (σ2 g=0si todas las gtienen el mismo valor) y se aproxima a 1para valores grandes de σ2 g. El tercer momento es una medida de la desviación del histograma (skewness), mientras que el cuarto corresponde a la monotónica relativa (flatness). El quinto momento así como los siguientes no están relacionados con la forma del histograma, pero proporcionan una mayor discriminación cuantitativa del contenido de la textura. Las características más comunes en la caracterización de un histograma son entonces las siguientes: ValorMedio ¯g= L−1  g=0 g·h(g) Varianza σ 2 g= L−1  g=0 (g−¯g)2·h(g) Skewness gs=1 σ3 g L−1  g=0 (g−¯g)3·h(g) Kurtosis gk=1 σ4 g L−1  g=0 (g−¯g)4·h(g)−3 Energia ge= L−1  g=0 [h(g)]2 (4.4) donde nuevamente Les el numero de niveles de gris presentes en la imagen y h(g)el histograma. Estas medidas nos permiten medir por ejemplo la dispersión o la concentración de los niveles, en el caso de la Kurtosis, y la simetría de la distribución de los niveles en el histograma, Skewness. Sin embargo, Las medidas de la textura calculadas utilizando solamente histogramas presentan la limitación de no contener información referente a la posición relativa de cada pixel con respecto a los otros. Una forma de introducir este tipo de información en el proceso de análisis de la textura consiste en considerar no solamente la distribución de intensidades, sino también las posiciones de pixeles que tienen iguales, o casi iguales, valores de intensidad. Resultados Para el histograma de la imagen en escala de gris Igcon 255 niveles, se calcularon las siguientes características según la ecuación 4.4: Media, Varianza, Skewness, Kurtosis, Energía y Entropía. El vector de características resultante con dimensión 6 alimenta el clasificador basado en LS-SVM, siguiendo la metodología experimental descrita en la sección 3.5. La tabla 4.1 presenta los resultados obtenidos. CAPÍTULO 4. CARACTERIZACIÓN BASADA EN LOS NIVELES DE GRIS. 53 Tabla 4.1: Resultados para características del histograma usando 255 niveles de gris. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 7,02 46,85 22,95 4,61 13,35 GPDS100 4,17 34,91 17,75 2,88 16,55 GPDS750 3,05 39,77 19,28 2,61 17,07 10 MCYT 8,28 41,84 16,67 4,92 18,17 GPDS100 4,49 38,12 16,88 2,99 20,07 GPDS750 3,51 34,83 15,06 2,01 19,53 También se realizaron pruebas para diferentes valores de niveles de gris. A continuación los resultados para 128, 64, 32 , y 16 niveles en el histograma. Para reducir el número de niveles de gris presentes en la imagen, se empleó el procedimiento de posterizado descrito en la sección 3.3. Tabla 4.2: Resultados para características del histograma usando 128 niveles de gris. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 7,38 47,27 23,34 5,37 12,89 GPDS100 3,74 37,41 18,62 3,06 17,03 GPDS750 2,73 38,42 18,50 2,16 15,63 10 MCYT 8,16 42,72 16,80 4,91 18,48 GPDS100 4,97 36,90 16,73 3,21 19,89 GPDS750 3,29 36,39 15,48 2,10 18,63 Tabla 4.3: Resultados para características del histograma usando 64 niveles de gris. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,92 48,41 23,51 4,73 12,92 GPDS100 4,04 37,08 18,65 3,06 18,72 GPDS750 2,76 34,89 16,97 2,72 16,13 10 MCYT 8,79 41,00 16,85 5,10 16,80 GPDS100 4,26 41,87 18,12 3,03 20,10 GPDS750 3,09 34,62 14,70 1,80 20,06 Tabla 4.4: Resultados para características del histograma usando 32 niveles de gris. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 7,29 47,99 23,57 5,06 12,63 GPDS100 3,99 36,02 18,14 2,76 17,06 GPDS750 3,11 36,06 17,67 2,94 15,09 10 MCYT 8,36 41,28 16,59 4,86 17,85 GPDS100 4,91 34,97 15,98 3,08 18,51 GPDS750 3,03 36,15 15,23 2,13 20,67 54 4.1. CARACTERÍSTICAS A PARTIR DEL HISTOGRAMA. Tabla 4.5: Resultados para características del histograma usando 16 niveles de gris. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 7,13 46,58 22,91 5,49 11,96 GPDS100 4,82 34,58 17,97 3,29 15,77 GPDS750 2,75 37,67 18,18 2,34 17,75 10 MCYT 8,58 41,64 16,85 4,71 16,43 GPDS100 4,47 38,13 16,88 3,44 19,59 GPDS750 2,97 35,81 15,06 1,89 18,32 (a) (b) Figura 4.1: Comparación de los resultados para características del histograma usando diferente número de niveles de gris de la imagen. Buscando una mejor caracterización del histograma, se plantea entonces el uso de los coeficientes cepstrales como la siguiente alternativa. CAPÍTULO 4. CARACTERIZACIÓN BASADA EN LOS NIVELES DE GRIS. 55 4.2. Coeficientes Pseudo-cepstrales del histograma de niveles de gris. Las anteriores medidas representan promedios del histograma sin incluir información de la forma de la curva del mismo. Puesto que un modelado de dicha forma se supone puede mejorar el desempeño del sistema se propone realizarlo mediante el procesado cepstrum. 4.2.1. Característica propuesta Para una imagen Ig(x, y), el cepstrum se define como: Cg(p, q)=F−1log  ˆ Ig(u, v)(4.5) donde ˆ Ig(u, v)es la transformada de Fourier de Ig(x, y),yF−1es la transformada inversa. Según la ecuación 4.5, la imagen en el dominio cepstral es la transformada inversa de Fourier del logaritmo del espectro de potencia de la imagen original [CSK77]. Para la metodología propuesta, aunque se analiza la imagen de una firma, solo se tiene en cuenta su histograma de niveles de gris. En este sentido, el cepstrum de un vector de datos (no el de una imagen), es: Ch(p)=F−1{log |D(u)|} (4.6) donde D(u)se reemplaza con el vector correspondiente al histograma de la imagen, y que representaría el “espectro” de la misma, en el sentido de que nos brinda información sobre la distribución de los componentes tonales que conforman la imagen que analizamos, esto es Ch(p)=F−1{log |hisI (g)|} (4.7) Finalmente, se estima la secuencia de fase mínima como ˆ C(n)=ReF−1eF{Ch} (4.8) y se usa como vector de características para la verificación. Resultados Puesto que la mayor información esta en los primeros coeficientes cepstrum, se realizaron pruebas orientadas a determinar el número mínimo de coeficientes cepstrales que permitiese un buen desempeño del sistema. La figura 4.2 muestra la evolución del EER, respecto al número de coeficientes tomados para la clasificación usando falsificaciones simuladas. Puede verse que el desempeño del sistema es mejor cuando los usuarios han usado diferentes tipos de bolígrafo (GPDS100 y GPDS750) lo que evidencia una fuerte 56 4.2. COEFICIENTES PSEUDO-CEPSTRALES DEL HISTOGRAMA. influencia del tipo de tinta empleado sobre las características basadas en la información de niveles de gris. Figura 4.2: ERR respecto al número de coeficientes cepstrum. La tabla 4.6, presenta los resultados cuando se toman los 256 coeficientes. La tabla 4.7, presenta los resultados cuando se toman los primeros 22 coeficientes. Esta selección obedece al mejor desempeño observado en la figura 4.2 para MCYT75. Se puede ver que el valor de EER para GPDS750 es mucho menor respecto a MCYT y GPDS100. Tabla 4.6: Cepstrum 256 coeficientes #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 4,64 59,39 26,54 3,39 7,98 GPDS100 6,21 48,09 24,72 3,92 8,94 GPDS750 6,71 42,66 22,59 3,60 10,77 Tabla 4.7: Cepstrum 22 coeficientes #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 13,46 31,70 20,75 7,85 15,32 GPDS100 5,43 39,48 20,48 4,59 20,48 GPDS750 4,44 32,49 16,83 3,84 19,47 Con el fin de observar la influencia del procedimiento de procesado del fondo descrito en la sección 3.3 y del preprocesamiento del histograma propuesto en la sección 3.4, la figura 4.3 muestra la evolución del EER, respecto a número de coeficientes tomados para la clasificación, cuando no se realiza ninguno de los dos procedimientos. CAPÍTULO 4. CARACTERIZACIÓN BASADA EN LOS NIVELES DE GRIS. 57 Figura 4.3: ERR respecto al número de coeficientes cepstrum. Sin procesado del fondo ni preprocesado de histograma. Teniendo en cuenta el comportamiento casi estable para MCYT75 y GPDS100, y la tendencia final descendiente para GPDS750. La tabla 4.8 presenta los resultados cuando se toman 256 coeficientes cepstrales, la tabla 4.9 presenta los resultados cuando se toman los 13 primeros coeficientes (Mejor desempeño para MCYT75). Tabla 4.8: Cepstrum 256 coeficientes. Sin procesado de fondo ni preprocesado de histograma. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 17,78 23,99 20,25 11,63 23,10 GPDS100 27,42 12,09 20,64 9,87 9,44 GPDS750 14,28 4,64 10,02 3,93 6,26 Tabla 4.9: Cepstrum 13 coeficientes. Sin procesado de fondo ni preprocesado de histograma. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 13,95 34,62 22,22 9,02 19,73 GPDS100 8,22 39,93 22,23 6,96 18,86 GPDS750 11,46 33,12 21,03 6,24 20,51 Como complemento, la figura 4.4 muestra la evolución del EER, respecto a número de coeficientes tomados para la clasificación cuando se realiza el procesado del fondo, pero no el preprocesamiento del histograma. Si bien el comportamiento es similar a lo observado en la figura 4.2 en el sentido de que el desempeño es notablemente peor para MCYT75, se observa que las curvas para GPDS100 y GPDS750 muestran una tendencia descendiente con un mayor número de coeficientes usados. 64 4.3. DENSIDAD DE PIXELES EN COORDENADAS POLARES 0.05 0.25 0.5 0.75 1 0 10 30 60 90 120 360 14 16 18 20 22 Gamma Theta EER (%) Figura 4.9: EER para diferentes combinaciones de θyγpara HPPD. MCYT. Tabla 4.12: EER para diferentes combinaciones de θyγpara HPPD. MCYT. γ\θ510 15 20 30 45 60 90 120 180 360 0,05 19,78 19,75 19,74 19,62 16,39 16,58 16,37 16,44 16,37 16,60 16,73 0,10 19,77 19,46 19,75 19,67 16,61 16,27 16,73 16,37 16,37 16,36 16,52 0,15 19,75 19,57 19,66 19,63 16,35 16,61 16,55 16,31 16,53 16,50 16,33 0,20 19,72 19,78 19,71 19,61 16,96 16,79 16,30 16,50 16,12 16,49 16,36 0,25 19,69 19,59 19,58 19,79 16,46 16,09 16,34 16,24 16,22 15,99 16,38 0,30 19,68 19,72 19,69 16,54 16,30 16,30 15,97 16,58 16,49 16,06 16,17 0,35 19,81 19,71 19,82 16,27 16,29 16,04 16,36 16,01 16,45 16,59 16,33 0,40 19,80 19,70 19,73 16,13 16,44 16,47 16,83 16,65 16,13 16,59 16,76 0,45 19,48 19,78 19,85 16,06 16,45 16,36 16,51 16,43 15,77 16,26 16,51 0,50 19,65 19,73 19,83 16,21 16,47 16,28 16,71 16,06 16,38 16,63 16,58 0,55 19,88 19,76 19,80 16,43 16,04 16,31 16,58 16,06 16,22 16,21 16,34 0,60 19,84 19,81 19,86 16,26 16,16 16,45 16,54 16,54 16,17 16,67 16,12 0,65 19,71 19,77 19,71 16,59 16,24 16,44 16,60 16,52 16,24 16,73 16,45 0,70 19,79 19,62 19,89 16,44 16,61 16,43 16,46 16,76 16,39 16,35 16,33 0,75 19,75 19,64 19,68 16,19 16,70 16,59 16,65 16,54 16,88 16,15 16,84 0,80 19,78 19,65 19,75 16,42 16,77 16,60 16,35 16,57 16,28 16,55 17,23 0,85 19,81 19,82 19,82 16,66 16,79 16,62 17,03 17,11 16,63 16,98 16,79 0,90 19,81 19,81 19,80 16,74 17,05 16,88 16,70 16,69 16,66 17,09 16,95 0,95 19,74 19,97 19,93 17,22 17,02 17,00 17,03 17,08 17,15 17,08 17,11 1,00 20,07 19,94 20,03 17,62 17,41 17,71 17,73 17,66 17,35 17,53 17,62 CAPÍTULO 4. CARACTERIZACIÓN BASADA EN LOS NIVELES DE GRIS. 65 0.05 0.25 0.5 0.75 1 0 10 30 60 90 120 360 18 19 20 21 22 23 GammaTheta EER(%) Figura 4.10: EER para diferentes combinaciones de θyγpara HPPD. GPDS100. Tabla 4.13: EER para diferentes combinaciones de θyγpara HPPD. GPDS100. γ\θ510 15 20 30 45 60 90 120 180 360 0,05 21,53 21,79 21,85 21,59 20,26 19,93 20,19 19,77 19,99 19,96 20,07 0,10 21,73 21,78 21,59 21,76 20,05 19,93 20,28 20,07 20,20 20,05 20,21 0,15 21,76 21,66 21,61 21,74 20,19 20,04 20,11 20,18 19,88 20,42 20,36 0,20 21,66 21,74 21,73 21,76 19,97 19,91 20,04 20,02 19,87 20,29 20,07 0,25 21,75 21,75 21,61 21,71 20,08 20,13 20,13 19,81 20,03 20,05 19,85 0,30 21,72 21,67 21,72 20,05 19,91 19,93 20,11 19,60 19,98 20,12 19,81 0,35 21,73 21,78 21,74 19,82 19,96 19,84 19,78 20,03 19,71 19,98 19,96 0,40 21,87 21,90 21,80 20,14 19,84 19,88 19,78 19,86 19,63 20,28 19,89 0,45 21,97 21,84 21,85 19,82 19,60 19,96 19,74 19,86 19,68 19,53 19,97 0,50 21,84 21,86 21,81 19,39 19,60 19,44 19,38 19,34 19,45 19,55 19,31 0,55 21,97 21,75 21,89 19,67 19,15 19,65 19,31 19,32 19,22 19,45 19,78 0,60 21,81 21,84 21,96 18,85 19,22 19,37 19,21 19,33 19,58 19,28 19,78 0,65 21,87 21,99 21,96 19,49 19,37 19,23 19,40 19,00 19,06 19,22 19,49 0,70 21,96 22,04 21,85 19,12 19,21 19,22 19,42 19,23 19,30 19,36 19,02 0,75 22,01 21,89 21,93 19,59 19,16 19,13 18,96 18,87 19,08 19,04 19,16 0,80 21,88 21,93 21,96 19,18 19,29 18,93 18,89 18,90 19,03 19,28 19,08 0,85 21,97 22,06 22,00 19,36 18,67 19,09 19,29 19,14 18,74 19,27 19,09 0,90 22,05 22,08 22,06 18,90 19,11 19,09 19,27 18,87 18,86 19,00 19,07 0,95 22,00 22,10 22,10 18,62 18,67 18,91 18,75 18,92 18,73 18,90 18,84 1,00 22,07 22,03 22,06 19,18 18,92 18,82 18,81 19,18 18,85 19,00 19,09 66 4.3. DENSIDAD DE PIXELES EN COORDENADAS POLARES 0.05 0.25 0.5 0.75 1 0 10 30 60 90 120 360 18 19 20 21 22 23 Gamma Theta EER(%) Figura 4.11: EER para diferentes combinaciones de θyγpara HPPD. GPDS750. Tabla 4.14: EER para diferentes combinaciones de θyγpara HPPD. GPDS750. γ\θ510 15 20 30 45 60 90 120 180 360 0,05 21,76 21,71 21,70 21,64 19,46 19,26 19,29 19,49 19,77 19,45 19,62 0,10 21,75 21,78 21,68 21,80 19,55 19,24 19,76 19,36 19,51 19,72 19,51 0,15 21,69 21,86 21,77 21,71 19,19 19,52 19,31 19,35 19,26 19,28 19,85 0,20 21,81 21,75 21,81 21,83 19,24 19,03 19,12 19,00 19,21 19,27 19,06 0,25 21,77 21,83 21,81 21,70 19,32 19,59 19,17 19,38 19,56 19,28 19,44 0,30 21,93 21,75 21,82 19,47 19,09 19,33 19,41 19,09 19,39 19,39 19,29 0,35 21,90 21,90 21,77 18,96 19,62 19,26 19,37 18,95 19,46 19,43 19,26 0,40 22,02 21,89 21,96 18,94 19,16 19,62 19,36 19,69 19,37 19,29 19,50 0,45 21,85 21,89 21,89 19,58 18,99 18,86 19,13 19,18 19,19 19,47 19,47 0,50 22,03 21,84 21,86 19,26 19,28 19,29 19,30 19,44 19,17 19,07 19,42 0,55 21,89 21,98 21,99 19,60 19,87 19,20 19,02 19,32 19,41 19,69 19,35 0,60 22,11 22,02 22,02 19,16 19,49 19,57 19,41 19,21 19,13 18,94 19,57 0,65 21,97 21,89 21,92 19,46 19,29 19,53 19,29 19,31 19,70 19,42 19,36 0,70 22,02 21,99 21,92 19,53 19,40 19,40 19,58 19,58 19,67 19,19 19,59 0,75 21,95 22,03 22,08 19,06 19,52 19,25 19,28 19,19 19,43 19,19 19,13 0,80 22,06 22,02 22,03 19,02 19,23 19,41 19,47 19,52 19,64 19,14 19,55 0,85 22,02 22,03 22,02 19,35 19,42 19,19 19,40 19,36 19,14 18,99 19,29 0,90 22,09 22,05 22,09 19,40 19,30 19,57 18,99 19,10 19,31 19,58 19,04 0,95 22,06 22,06 22,04 18,99 19,01 19,30 19,09 19,04 19,20 19,40 19,08 1,00 22,16 22,08 22,07 19,35 19,39 19,52 18,97 19,27 19,62 19,18 19,24 Se observa que para valores de θmenores a 30 el desempeño del sistema es el peor. El valor de EER disminuye para valores grandes de γ. Lo anterior sugiere que existe un compromiso entre el tamaño de los segmentos angulares empleados para realizar el análisis y el desempeño del sistema. Segmentos angulares demasiado pequeños inciden negativamente en los resultados, porque existirán pocos puntos de alta presión en ca- CAPÍTULO 4. CARACTERIZACIÓN BASADA EN LOS NIVELES DE GRIS. 67 da segmento lo que aumenta el ruido en los estadísticos del vector de características. Respecto al factor γ, se tiene que el sistema opera mejor cuando el umbral se acerca al valor gmaxHis del histograma. Como alternativa a las características pseudodinámicas encontradas en la literatura, y a partir del trabajo realizado por Franke [FBS02], orientado hacia el análisis de la textura de tinta para la identificación de escritor, se plantea la posibilidad de usar el análisis de textura para la verificación de firmas manuscritas. Resumen Se han descrito las diferentes etapas seguidas en el desarrollo de la metodología de extracción de características. Comenzando con las características basadas en el histograma, se dio paso a la metodología propuesta que incluye el análisis cepstrum del histograma de la imagen, y finalmente se estudió el cálculo de los puntos de alta presión de la firma haciendo uso del mapeo de los datos hacia un espacio polar con el finde hacer un análisis localizado de la imagen mediante segmentos angulares. Conscientes de las limitaciones de estos parámetros, pues son altamente influenciados por el tipo de tinta, en el siguiente capitulo se presentan las características basadas en el análisis de texturas. Se describe el uso de la Matriz de Co-ocurrencias y el Patrón Binario Local. Se estudian diferentes configuraciones para estas herramientas y se presentan los resultados obtenidos para cada caso. 68 4.3. DENSIDAD DE PIXELES EN COORDENADAS POLARES Capítulo 5 Características basadas en el análisis estadístico de textura El análisis estadístico de textura involucra el cálculo de características de una textura a partir de la distribución estadística de las combinaciones de los valores de intensidad observados en posiciones específicas relativos a cada punto dentro de una imagen. De acuerdo al número de píxeles presentes en cada una de estas combinaciones, se puede hablar de estadísticos de primero, segundo y alto orden. Se plantea que los sistemas biométricos basados en la verificación de firmas manuscritas y que emplean análisis de texturas, puede ofrecer información acerca de la distribución de los píxeles pertenecientes a un trazo que refleja características personales de un firmante, p.e. La forma en que toma el bolígrafo, la velocidad de los trazos y la presión empleada en cada uno de ellos. 5.1. Matriz de co-ocurrencia de niveles de gris La matriz de co-ocurrencia de niveles de gris (GLCM, por sus siglas en inglés) es una forma de extraer características estadísticas de texturas de segundo orden para una imagen [CH80]. Este método ha sido usado en múltiples aplicaciones incluyendo el análisis de tipo de tinta [FBS02], [Har79],[HWG87], [THCG84]. Una GLCM es una matriz en donde el número de filas y el número de columnas es igual al número de niveles de gris, L, presentes en la imagen. El elemento P(i, j|Δx, Δy)de la matriz es la frecuencia relativa con la cual dos píxeles, separados por una distancia en píxeles (Δx, Δy), aparecen dentro de un vecindario dado, uno con valor de intensidad iy el otro con un valor de intensidad j. Se podría decir que el elemento P(i, j|d, θ)de la matriz contiene los valores de probabilidad de segundo orden para las transiciones entre los niveles de gris iyjpara un desplazamiento dado dyunángulo(θ). Se puede hacer una buena estimación de la distribución de probabilidad conjunta cuando la matriz tiene un nivel relativamente alto de ocupación. Lo anterior se puede lograr restringiendo el número de niveles de cuantización de los niveles de gris o usando una ventana relativamente grande. Para el primer caso, se pierde precisión en la descripción de la textura cuando se tienen texturas con amplitudes bajas, mientras que 69 70 5.1. MATRIZ DE CO-OCURRENCIA DE NIVELES DE GRIS para el segundo caso se, presentará incertidumbre y error si la textura cambia a lo largo de la ventana de análisis. Nótese que la parametrización (Δx, Δy) hace que la matriz GLCM sea sensible a la rotación. Una rotación de la imagen diferente de 180◦generará una distribución de coocurrencia diferente. Teniendo en cuenta que lo anterior es un resultado no deseable para las aplicaciones en las que se emplea la matriz de co-ocurrencia, generalmente se usa un conjunto de compensaciones haciendo un barrido de 180◦(p.e. 0, 45, 90 y 135◦) a la misma distancia para generar una matriz GLCM con algún grado de invarianza a la rotación. 5.1.1. Construcción de la matriz de Co-ocurrencia Para la construcción de la matriz de co-ocurrencia se sigue un procedimiento sencillo. Basado en la construcción de una matriz provisional que contiene la información del número de pares de píxeles que cumplen la condición de (distancia dyánguloθ), ordenadosdeformaqueelnúmerodefila de cada elemento indica el nivel de gris del píxel en la dirección y el ángulo con relación al nivel de gris del píxel indicado por el número de columna. Sea la matriz provisional A, de dimensión LxL,dondeLes el número de niveles de gris de la imagen, cuyo elemento aij es el número de veces que un píxel con nivel de gris i, se encuentra en la dirección de un píxel con nivel de gris j. Una vez obtenida esta matriz provisional, se halla el número de pares de píxeles que cumplen satisfactoriamente con la condición, lo que equivale a dividir cada uno de los elementos de la matriz provisional por la sumatoria de todos ellos. De esta forma se obtiene la matriz de co-ocurrencia para un valor de ángulo determinado. 5.1.2. Características de la matriz de co-ocurrencia A partir de la matriz GLCM es posible calcular varias características de textura, (ver Haralick et al. [Har79] and Conners et al. [CH80]). De aquí en adelante y para simplicidad matemática, la notación P(i, j|d, θ)se reduce a P(i, j). Las siguientes características fueron las consideradas para el presente estudio: Homogeneidad local, segundo momento angular (ASM): HOMOGENEIDAD = L−1  i=0 L−1  j=0 {P(i, j)}2(5.1) ASM es una medida de la homogeneidad de una imagen. Una imagen homogénea estará formada por unos pocos niveles de gris, lo que se verá reflejado en una matriz GLCM con unos pocos pero relativamente altos valores de P(i, j). Por tanto, la suma de los cuadrados será alta. CAPÍTULO 5. CARACTERÍSTICAS BASADAS EN TEXTURA. 71 Contraste: CONTRASTE = L−1  n=0 ⎧ ⎨ ⎩ n2 L−1  i=0 L−1  j=0 P(i, j)⎫ ⎬ ⎭ ,|i−j|=n(5.2) Es lo opuesto a la homogeneidad, es decir es una medida de la variación local en una imagen. El valor de contraste será mayor, si existen más elementos de la matriz de co-ocurrencia alejados de la diagonal principal p.e. i=j. Se desprecia el efecto de las componentes de la diagonal principal, ya que no son relevantes en cuanto a los cambios de nivel en la imagen [GW06]. Entropía: ENTROPIA =− L−1  i=0 L−1  j=0 P(i, j)·log (P(i, j)) (5.3) Es alta cuando los elementos de la matriz de co-ocurrencia tienen valores relativamente iguales. Es baja cuando los elementos son cercanos a 0 ó 1 (por ejemplo cuando la imagen es uniforme dentro de la ventana) Correlación: CORRELACION = L−1  i=0 L−1  j=0 {i·j}·P(i, j)−{μx·μy} σx·σy (5.4) donde μiyσison respectivamente la media y la desviación estándar de las filas de P(i, j),μjyσjson respectivamente la media y la desviación estándar de las columnas de P(i, j). La correlación es una medida de la dependencia lineal del nivel de gris de los pixel en posiciones especificas relativa a las demás. Resultados Para calcular las características basadas en la matriz de co-ocurrencia, las imágenes fueron redimensionadas a [256 x 256], usando el algoritmo de vecino más cercano, para afectar lo menos posible la textura de los trazos. Las características calculadas fueron: Homogeneidad, Contraste, Entropía, Energía y Correlación. Se usaron 8 niveles de gris para el cálculo de la GLCM. Para el vector de offsets (Δx, Δy)de la GLCM se emplearon los valores [0 1;-1 1;-1 0;-1 -1]. A continuación se presentan los resultados obtenidos probando el sistema con las características de forma individual para falsificaciones simuladas. 72 5.1. MATRIZ DE CO-OCURRENCIA DE NIVELES DE GRIS Tabla 5.1: Resultados usando la característica Contraste de la GLCM. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 5,05 52,50 24,03 2,71 4,01 GPDS100 0,08 61,59 27,25 0,11 0,69 GPDS750 0,30 61,76 27,46 0,41 0,89 10 MCYT 7,21 47,26 17,23 1,57 4,74 GPDS100 0,49 59,30 22,16 0,49 1,73 GPDS750 1,16 59,44 22,64 0,58 1,28 Tabla 5.2: Resultados usando la característica Homogeneidad de la GLCM. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 0,50 61,34 24,84 0,36 0,66 GPDS100 0,20 61,89 27,46 0,31 0,73 GPDS750 0,18 61,45 27,25 0,13 0,63 10 MCYT 1,35 59,46 15,89 0,73 1,73 GPDS100 0,53 59,95 22,43 0,53 1,43 GPDS750 0,40 59,90 22,33 0,30 1,45 Tabla 5.3: Resultados usando la característica Energía de la GLCM. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 0,14 61,55 24,70 0,10 0,93 GPDS100 0,36 60,95 27,14 0,28 1,10 GPDS750 0,58 61,68 27,58 0,63 1,03 10 MCYT 1,09 57,00 15,06 0,91 2,83 GPDS100 0,85 58,96 22,26 0,64 1,84 GPDS750 1,70 59,46 22,98 0,84 1,63 Tabla 5.4: Resultados usando la característica Correlación de la GLCM. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 0,68 60,25 24,51 0,44 1,61 GPDS100 0,53 60,43 26,99 0,46 1,50 GPDS750 1,06 54,98 24,89 0,44 1,05 10 MCYT 1,59 51,89 14,16 0,86 2,85 GPDS100 0,98 52,20 19,85 0,60 2,92 GPDS750 2,79 51,87 20,87 0,98 1,69 Tabla 5.5: Resultados usando la característica Entropía de la GLCM. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 0,08 57,17 22,92 0,10 0,44 GPDS100 0,28 61,34 27,26 0,31 0,99 GPDS750 0,44 61,55 27,44 0,69 1,50 10 MCYT 1,01 57,00 15,01 1,06 3,49 GPDS100 0,99 58,89 22,33 0,76 2,14 GPDS750 1,54 59,30 22,81 1,01 1,83 CAPÍTULO 5. CARACTERÍSTICAS BASADAS EN TEXTURA. 73 (a) (b) Figura 5.1: Comparación de los resultados obtenidos con cada una de las cinco características GLCM calculadas. Una vez analizadas las características de forma individual, se realizaron pruebas para diferentes combinaciones de las mismas. La combinación se realiza a nivel de características (feature level). A continuación se presentan los resultados obtenidos en donde las combinaciones se notan como: CHE - Contraste + Homogeneidad + Energía; CHEE - Contraste + Homogeneidad + Energía + Entropía; CHEEC - Contraste + Homogeneidad + Energía + Entropía + Correlación.. Tabla 5.6: GLCM. Correlación + Homogeneidad + Entropía #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 7,89 39,09 20,36 4,08 8,54 GPDS100 3,58 44,79 21,79 2,96 8,50 GPDS750 3,58 48,65 23,49 3,63 8,49 10 MCYT 12,38 28,24 16,34 4,18 9,94 GPDS100 7,10 30,45 15,70 3,58 8,69 GPDS750 7,81 34,69 17,71 3,59 9,35 80 5.2. LOCAL BINARY PATTERNS haciendo que el método sea claramente estadístico. Por estas razones, es de suponer que la distribución LBP puede ser utilizada con éxito en el reconocimiento de una amplia variedad de tipos de textura, para las cuales se han aplicado comúnmente los métodos estadísticos y estructurales por separado. 5.2.1. LBP extendido Se comienza con la definición de textura Ten un vecindario local de una imagen en escala de grises como la distribución conjunta de los niveles de gris de los Ppixeles de la imagen, (P>0). T=t(gc,g 0,...,g P−1)(5.5) donde gccorresponde al nivel de gris del pixel central del vecindario local. gp(p= 0,...,P −1) son los valores de gris de los Ppixeles igualmente espaciados y distribuidos sobre un circulo de radio R(R>0) conformando un conjunto de vecinos circularmente simétricos. Este conjunto de P+1 de pixeles se denota entonces como GP. En el dominio de una imagen digital, las coordenadas de los vecinos gpestán dadas por (xc+Rcos(2πp/P),y c−Rsin(2πp/P)),dondexc,y cson las coordenadas del pixel central. La figura fig:LBP4, presenta tres conjuntos de vecinos circularmente simétricos para diferentes valores de PyR. Aquellos valores de vecinos que no corresponden exactamente con un pixel son estimados usando interpolación bilineal. Teniendo en cuenta que la correlación entre pixeles decrece con la distancia, buena parte de la información de la textura de una imagen se puede obtener a partir de estos vecindarios locales [OVOP01]. Figura 5.9: Conjuntos de vecinos circularmente simétricos. Las muestras que no corresponden exactamente a un pixel se calculan vía interpolación [MP05]. Si se sustrae el valor del pixel central del valor de los vecinos, la textura local puede ser representada, sin pérdida de información, como un distribución conjunta del valor del pixel central y las diferencias: T=t(gc,g 0−gc,...,g P−1−gc)(5.6) Asumiendo que las diferencias son independientes de gc, la distribución puede factorizarse como sigue: CAPÍTULO 5. CARACTERÍSTICAS BASADAS EN TEXTURA. 81 T=t(gc)t(g0−gc,...,g P−1−gc)(5.7) En la practica, no siempre resulta cierta dicha independencia. Debido a la naturaleza limitada del rango de valores en una imagen digital, es obvio que valores muy grandes o muy pequeños de gcreducirán el rango de las posibles diferencias. Sin embargo, tolerando una pequeña pérdida de información es posible obtener invarianza respecto a desplazamientos en la escala de gris. Dado que t(gc)describe la luminancia general de una imagen, la cual no esta relacionada con la textura local, esta no provee información útil para el análisis de textura. Por tanto, la mayor parte de la información sobre las características de textura de la distribución conjunta original, ecuación 5.6, se conserva en la distribución conjunta de diferencias [OVOP01]: T≈t(g0−gc,...,g P−1−gc)(5.8) La distribución de diferencias P-dimensional registra la ocurrencia de los diferentes patrones de textura en el vecindario de cada pixel. Para valores constantes o cambios pequeños, estas diferencias serán cercanas a cero. Para el caso de un punto, todas las diferencias serán relativamente grandes. En un borde, las diferencias en una dirección serán mayores que en los otros. Aunque se obtiene invarianza ante el desplazamiento en la escala de gris, las diferencias son afectadas por el escalamiento. Para obtener la invarianza ante cambios monotónicos de la escala de gris, se consideran entonces solamente los signos de las diferencias: T≈t(s(g0−gc),...,s(gP−1−gc)) (5.9) donde s(x)=1x≥0 0x<0(5.10) Luego, se asigna un peso binomial 2pacadasignos(gp−gc)transformando así las diferencias obtenidas para un vecindario, en un código LBP único. Este código caracteriza la textura local de la imagen alrededor de xc,y c: LBPP,R(xc,y c)= P−1  p=0 s(gp−gc)2p(5.11) 5.2.2. LBP con Invarianza a la rotación Un paso más allá de lo definido en [OVOP01], en [OPM02] se define un operador LBPP,R invariante a la rotación de la siguiente forma: 82 5.2. LOCAL BINARY PATTERNS LBPriu2 P,R (x, y)=⎧ ⎪ ⎨ ⎪ ⎩ P−1  p=0 s(gp−gc),ifU(x, y)≤2 P+1,otherwise (5.12) donde U(x, y)= P  p=1 |s(gp−gc)−s(gp−1−gc)|,with gP=g0(5.13) Analizando estas dos ecuaciones, U(x, y)puede calcularse en la práctica de la siguiente forma: 1. Se resuelve la función f(p)=s(qp−qc),0<p<P considerando que gP=g0; 2. Se calcula su derivada: f(p)−f(p−1),1≤p≤P; 3. Se calcula el valor absoluto: |f(p)−f(p−1)|,1≤p≤P; 4. U(x, y)se obtiene como la suma P  p=1 |f(p)−f(p−1)|. Si los niveles de gris de los pixeles vecinos (x, y)son uniformes o suaves, como se muestra en la figura 5.10(a), f(p)será una secuencia de ’0’ ó ’1’ con ninguno o dos transiciones. En este caso U(x, y)será cero o dos y el código LBPriu2 P,R se calcula como la suma P−1  p=0 f(p). Para el caso opuesto, si los los niveles de gris de los pixeles vecinos (x, y) cambian rápidamente como se muestra en la figura 5.10(b), f(p)será una secuencia con varias transiciones de ’0’ a ’1’ y de ’1’ a ’0’, y U(x, y)será mayor que 2. Por lo tanto, para el caso de una imagen ruidosa, se asigna a LBPriu2 P,R un valor constante e igual P+1, haciendo al operador más robusto frente al ruido. (a) Píxeles uniformes (b) Píxeles no uniformes Figura 5.10: Cálculo del código LBPriu2 P,R para dos casos con P=4yR=2:(a):gc= 152, {g0,g 1,g 2,g 3}={154,156,155,149},{f(0),f(1),f(2),f(3),f(4)}={1,1,1,0,1},U(x, y)= 0+0+ 1+1= 2≤2,portantoLBPriu2 P,R (x, y) =1+1+1+0=3.(b):gc= 154,{g0,g 1,g 2,g 3}= {155,152,159,148},{f(0),f(1),f(2),f(3),f(4)}={1,0,1,0,1},U(x, y)=1+1+1+1=4≥2, LBPriu2 P,R (x, y)=P+1=5. CAPÍTULO 5. CARACTERÍSTICAS BASADAS EN TEXTURA. 83 Resultados Para calcular las características basadas en LBP, las imágenes fueron redimensionadas a [256 x 256], usando el algoritmo de vecino más cercano, para afectar lo menos posible la textura de los trazos. Se realizaron pruebas para dos configuraciones del operador LBP, con R={1,2}yP={8,16}.Estasdosconfiguraciones permiten analizar la imagen con diferentes resoluciones; valores más grandes implican una carga computacional excesiva. Los resultados obtenidos se presentan a continuación. Tabla 5.15: LBP. Con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 4,35 38,00 17,80 3,51 9,13 GPDS100 5,28 37,57 19,55 3,54 8,65 GPDS750 3,60 39,99 19,68 4,36 7,84 10 MCYT 7,28 27,42 12,32 3,46 9,17 GPDS100 9,09 25,53 15,15 3,98 7,23 GPDS750 5,50 30,20 14,59 5,22 7,94 Tabla 5.16: LBP. Con R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 3,38 36,40 16,59 3,01 9,41 GPDS100 4,49 34,79 17,87 3,71 9,37 GPDS750 3,98 36,35 18,27 3,45 8,27 10 MCYT 7,36 25,36 11,86 3,62 10,72 GPDS100 8,65 21,98 13,56 4,42 7,99 GPDS750 6,31 25,19 13,27 3,82 7,95 Con el ánimo de plantear un operador que realice una análisis multiresolución, se propone la combinación de las dos configuraciones anteriores para el operador LBP. Nuevamente, esta combinación se realiza a nivel de características. En las tablas siguientes, el signo ’+’ denota la operación combinación. Tabla 5.17: LBP. Con R=1 y P=8 + R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 5,49 29,41 15,05 4,06 10,05 GPDS100 5,73 28,27 15,69 4,21 10,05 GPDS750 3,13 30,87 15,39 3,98 9,86 10 MCYT 9,96 16,56 11,60 4,34 9,69 GPDS100 10,36 15,07 12,10 4,47 7,31 GPDS750 6,93 18,09 11,05 6,62 7,75 84 5.2. LOCAL BINARY PATTERNS (a) Figura 5.11: Comparación de los resultados. 8_1:PatrónLBPconR=1yP=8.16_2:Patrón LBP con R=2 y P=16. Como se puede ver, el uso de la combinación de los operadores mejora el desempeño del sistema. Para determinar la influencia del tamaño de la imagen en el desempeño del sistema, a continuación se presentan los resultados obtenidos para el caso en que la imagen se redimensiona a [512 x 512], y para el caso en que se trabaja con el tamaño original de la imagen. Los resultados presentados corresponden a la combinación, a nivel de características, de los operadores LBP. Tabla 5.18: LBP. Tamaño de la imagen [512 x 512] con patrón combinación. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,89 24,09 13,77 5,07 10,29 GPDS100 7,53 23,64 14,65 4,75 11,12 GPDS750 4,42 26,27 14,08 5,09 10,14 10 MCYT 11,09 13,49 11,68 4,55 9,97 GPDS100 11,14 11,47 11,26 5,04 7,21 GPDS750 5,61 13,44 8,50 6,50 8,49 Tabla 5.19: LBP. Tamaño original con patrón combinación. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 7,26 31,36 16,89 5,43 9,44 GPDS100 6,54 24,32 14,40 4,30 9,38 GPDS750 5,74 30,21 16,56 9,03 9,59 10 MCYT 13,56 18,83 14,87 5,58 11,24 GPDS100 9,71 12,73 10,82 4,29 7,68 GPDS750 7,97 16,62 11,16 8,83 8,41 CAPÍTULO 5. CARACTERÍSTICAS BASADAS EN TEXTURA. 85 (a) Figura 5.12: LBP. Comparación de los resultados. A continuación se presentan los resultados obtenidos cuando no se realiza el procesado del fondo ni el preprocesado del histograma, usando la imagen en su tamaño original. Tabla 5.20: LBP. Sin procesado fondo y sin preprocesado de histograma. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 0,00 26,22 x14,00 4,19 9,82 GPDS100 0,00 29,28 x15,43 3,77 10,35 GPDS800 0,00 30,73 x18,30 9,83 10,32 10 MCYT 0,00 14,78 x10,80 4,24 9,98 GPDS100 0,00 16,56 x11,37 4,05 8,57 GPDS800 0,00 16,79 x13,13 9,02 8,21 La tabla 5.21 presenta los resultados para el caso en que solamente se procesa el fondo de la imagen. Tabla 5.21: LBP. Sin preprocesado de histograma. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 0,00 26,22 x14,00 4,19 9,82 GPDS100 0,00 29,28 x15,43 3,77 10,35 GPDS800 0,00 30,73 x18,30 9,83 10,32 10 MCYT 0,00 14,78 x10,80 4,24 9,98 GPDS100 0,00 16,56 x11,37 4,05 8,57 GPDS800 0,00 16,79 x13,13 9,02 8,21 Se tiene entonces que el mejor desempeño, cuando se emplea el LBP para caracterizar la firma, se da para el caso de la combinación de las dos configuraciones para el LBP analizadas. Resumen Se han presentado las características basadas en análisis de texturas tenidas en cuenta en este trabajo. Se han descrito la Matriz de Co-ocurrencia y los Patrones Bina- 86 5.2. LOCAL BINARY PATTERNS rios Locales. Una vez estudiadas diferentes configuraciones para cada una de ellas, se tiene que para el caso de la GLCM, el mejor desempeño del sistema se alcanza cuando se emplean 8 niveles de gris para la estimación de la matriz GLCM, usando un vector de offset para cuatro direcciones distintas y redimensionando la imagen a [256x256]. Así mismo, se hace uso de la combinación CHEEC de características calculadas a partir de dicha matriz. Respecto a LBP, el mejor desempeño se da cuando se usa una combinación de dos configuraciones para el operador. En este caso, redimensionar la imagen a [512x512] es la mejor opción. Si hacemos una comparación de los resultados obtenidos con GLCM y LBP, podemos decir que el operador LBP ofrece un mejor desempeño presentadose además una menor varianza de los resultados para diferentes bases de datos. En el siguiente capítulo, se presentan los procedimientos implementados con el objetivo de reducir la influencia del tipo de tinta sobre el desempeño del sistema. Se combina la información espacial con las características basadas en textura, mediante el uso de un análisis por bloques. Capítulo 6 Combinación de información espacial con textura Teniendo en cuenta los resultados obtenidos en el capítulo 5, a continuación se describen los procedimientos implementados para reducir el problema de la influencia del tipo de tinta sobre el desempeño del sistema de verificación. Se describe el análisis por bloques que permite realizar un análisis mas localizado de la imágenes. 6.1. GLCM Usando análisis por bloques Para realizar un análisis local de las imágenes, se establece un tamaño fijo para las imágenes, así como el tamaño del bloque de análisis. Lo anterior asegura que la longitud de los vectores de características sea el mismo para todas las muestras. Una vez determinado el tamaño de los bloques, se realiza un barrido de la imagen usando como ventana de análisis el bloque seleccionado. Esto es, a partir de la imagen original, se crea una subimagen del tamaño del bloque seleccionado, y sobre esta se realiza el análisis correspondiente generando un vector de características temporal. Este vector temporal es almacenado en el vector final de características. A continuación se genera una nueva subimagen con los pixeles contiguos a la subimagen anterior en sentido horizontal. El vector temporal generado para este nuevo bloque se almacena en el vector final de características concatenando los datos actuales con aquellos almacenados previamente. La figura 6.1 ilustra el procedimiento. La tabla 6.1 presenta los resultados cuando las imágenes tienen dimensión [256x256] y el tamaño del bloque es [32 x 32]. La tabla 6.2, presenta los resultados para [512 x 512]. 87 88 6.1. GLCM USANDO ANÁLISIS POR BLOQUES Figura 6.1: Análisis por bloques de una imagen. Tamaño del bloque 4 x 4. Tabla 6.1: GLCM bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 3,14 29,93 13,86 2,20 10,71 GPDS100 5,74 30,14 16,53 3,75 9,92 GPDS750 9,65 29,37 18,37 6,05 10,43 10 MCYT 8,18 18,07 10,65 3,25 11,07 GPDS100 13,09 16,22 14,25 5,32 9,05 GPDS750 19,70 17,46 18,87 7,25 9,53 Tabla 6.2: GLCM bloques. Para imágenes de dimensión [512 x 512] y bloques [32 x 32]. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 1,59 35,52 15,16 1,06 5,98 GPDS100 3,71 32,41 16,39 1,66 5,49 GPDS750 0,00 33,21 20,46 5,87 7,31 10 MCYT 5,91 16,80 8,64 1,64 8,67 GPDS100 10,27 16,86 12,70 2,71 6,22 GPDS750 0,00 11,09 23,61 6,27 5,30 Para el caso de las imágenes con dimensión [256 x 256] y bloque de análisis de tamaño [32 x 32], y se tiene que para cada bloque se calculan 10 características. Si se tienen 64 bloques de análisis en la imagen, se obtienen entonces 10*64=640 características. Lo anterior implica un número alto de características, lo que sugiere el uso de un procedimiento de reducción de dimensionalidad para simplificar el espacio de características en el que trabaja el clasificador LS-SVM. A continuación se presentan los resultados obtenidos cuando se emplea el mapeo PCA para realizar la reducción del número de características. Los resultados en las tablas 6.3 - 6.6 corresponden a los valores de la varianzaretenida :99%. 95%,85% y 75%. La figura 6.2 presenta una comparación de los resultados obtenidos en las tablas 6.1, 6.3 - 6.6. Se observa que para el caso en que se retiene el 85% de la varianza de CAPÍTULO 6. COMBINACIÓN DE INFORMACIÓN ESPACIAL CON TEXTURA 89 los datos, se obtiene un desempeño aceptable del sistema con una reducción de 640 a 35 características. Tabla 6.3: GLCM bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 99 %. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 5,99 20,57 11,82 3,25 8,89 GPDS100 10,82 19,33 14,58 4,68 6,92 GPDS750 16,02 20,93 18,19 6,41 7,48 10 MCYT 11,41 12,85 11,76 3,91 9,21 GPDS100 18,66 11,86 16,16 5,54 7,84 GPDS750 26,69 12,10 21,31 7,20 7,75 Tabla 6.4: GLCM bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 95 %. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,46 20,70 12,16 3,62 9,10 GPDS100 11,11 18,78 14,50 5,13 8,06 GPDS750 15,97 21,53 18,42 7,43 8,54 10 MCYT 11,33 13,89 11,97 3,53 10,07 GPDS100 19,10 12,10 16,51 5,69 7,92 GPDS750 25,74 13,16 21,10 7,59 8,69 Tabla 6.5: GLCM bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 85 %. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,20 21,34 12,26 3,36 9,73 GPDS100 11,66 19,90 15,31 5,06 10,38 GPDS750 16,17 21,91 18,70 6,80 9,37 10 MCYT 10,67 15,18 11,80 4,35 10,71 GPDS100 17,93 14,09 16,51 6,64 10,66 GPDS750 25,19 15,33 21,55 7,99 9,29 Tabla 6.6: GLCM bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 75 %. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,00 23,17 12,87 3,34 11,01 GPDS100 11,18 20,82 15,43 5,15 10,47 GPDS750 14,95 25,45 19,60 7,76 12,16 10 MCYT 9,96 15,86 11,43 3,89 9,78 GPDS100 17,77 14,70 16,64 6,18 10,30 GPDS750 23,90 16,28 21,09 8,90 10,94 96 6.2. LBP USANDO ANÁLISIS POR BLOQUES Tabla 6.21: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 65%. Operador LBP con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,70 15,90 10,38 3,34 6,80 GPDS100 12,12 13,35 12,67 4,12 5,08 GPDS750 15,92 17,65 16,69 5,92 6,19 10 MCYT 10,78 7,85 10,04 3,45 6,70 GPDS100 17,68 7,29 13,86 4,30 3,99 GPDS750 25,31 8,97 19,30 5,15 4,19 La figura 6.5 presenta una comparación de los resultados obtenidos en las tablas 6.3 -6.6. (a) (b) Figura 6.5: LBP bloques. Comparación de los resultados [256 x 256]. Para el caso de las imágenes con dimensión [512 x 512] y bloque de análisis de tamaño [32 x 32], y se tiene que para cada bloque se calculan 10 características. Si se tienen 256 bloques de análisis en la imagen, se obtienen entonces 10*256=2560 características. Los resultados en las tablas 6.22 - 6.26 corresponden a los valores de la varianza retenida :99%. 95%, 85% , 75% y 65% CAPÍTULO 6. COMBINACIÓN DE INFORMACIÓN ESPACIAL CON TEXTURA 97 Tabla 6.22: LBP bloques. Para imágenes de dimensión [512 x 512] y bloques [32 x 32]. PCA con 99%. Operador LBP con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 13,55 9,56 11,95 4,05 4,96 GPDS100 20,08 10,05 15,64 5,03 3,91 GPDS750 37,13 9,13 24,76 6,81 4,58 10 MCYT 23,68 2,06 18,27 3,23 2,63 GPDS100 30,75 3,36 20,65 3,57 2,32 GPDS750 48,77 3,14 31,96 3,16 1,76 Tabla 6.23: LBP bloques. Para imágenes de dimensión [512 x 512] y bloques [32 x 32]. PCA con 95%. Operador LBP con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 13,37 9,76 11,93 4,27 5,01 GPDS100 20,26 10,02 15,73 5,05 3,78 GPDS750 37,11 9,55 24,93 6,68 4,05 10 MCYT 22,84 3,09 17,91 3,38 3,42 GPDS100 30,31 3,36 20,39 4,06 2,36 GPDS750 48,50 3,22 31,82 3,11 2,27 Tabla 6.24: LBP bloques. Para imágenes de dimensión [512 x 512] y bloques [32 x 32]. PCA con 85%. Operador LBP con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 12,71 9,97 11,62 4,20 4,93 GPDS100 18,34 11,02 15,10 4,44 4,15 GPDS750 34,74 10,06 23,84 7,34 4,07 10 MCYT 21,16 3,62 16,78 3,63 3,52 GPDS100 28,74 3,68 19,50 4,05 2,35 GPDS750 47,13 3,53 31,06 3,28 2,30 Tabla 6.25: LBP bloques. Para imágenes de dimensión [512 x 512] y bloques [32 x 32]. PCA con 75%. Operador LBP con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 11,27 11,18 11,24 4,00 5,76 GPDS100 17,71 10,96 14,73 4,69 4,66 GPDS750 33,33 11,72 23,78 7,07 4,57 10 MCYT 20,33 3,65 16,16 3,63 3,37 GPDS100 27,27 3,98 18,69 3,91 2,47 GPDS750 46,01 3,99 30,53 3,61 2,60 98 6.2. LBP USANDO ANÁLISIS POR BLOQUES Tabla 6.26: LBP bloques. Para imágenes de dimensión [512 x 512] y bloques [32 x 32]. PCA con 65%. Operador LBP con R=1 y P=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 10,61 11,49 10,96 4,03 5,69 GPDS100 16,23 12,19 14,44 4,51 4,61 GPDS750 31,38 12,58 23,08 7,30 5,09 10 MCYT 18,54 4,36 15,00 3,52 4,12 GPDS100 26,28 4,44 18,23 4,44 2,98 GPDS750 44,77 4,44 29,91 4,28 2,76 La figura 6.6 presenta una comparación de los resultados obtenidos en las tablas 6.22 - 6.26. (a) (b) Figura 6.6: LBP bloques. Comparación de los resultados [512 x 512]. A continuación se presenta los resultados obtenidos para la configuración R=2, P=16para el LBP, para imágenes de tamaño [256 x 256] y usando el análisis por bloques de tamaño [32 x 32]. CAPÍTULO 6. COMBINACIÓN DE INFORMACIÓN ESPACIAL CON TEXTURA 99 Tabla 6.27: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Operador LBP con R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 11,10 9,00 10,26 3,69 5,39 GPDS100 18,56 9,22 14,43 4,70 3,71 GPDS750 29,45 9,11 20,46 6,03 4,06 10 MCYT 18,99 3,19 15,03 2,94 3,31 GPDS100 28,03 3,42 18,95 4,16 2,24 GPDS750 40,14 2,96 26,44 4,04 2,27 Se tiene que para cada bloque se calculan 18 características. Si se tienen 64 bloques de análisis en la imagen, se obtienen entonces 18*64=1112 características. Nuevamente se presentan los resultados obtenidos cuando se emplea el mapeo PCA para realizar la reducción del número de características. Los resultados en las tablas 6.17 - 6.21 correspondenalosvaloresdelavarianzaretenida:99%.95%,85%,75%y65%,para el operador LBP con R=2 y P=16. Tabla 6.28: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 99%. Operador LBP con R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 13,06 7,72 10,93 4,28 4,42 GPDS100 20,47 8,23 15,07 5,22 3,54 GPDS750 31,10 7,67 20,75 6,41 4,13 10 MCYT 19,83 2,79 15,56 2,97 2,71 GPDS100 29,75 3,05 19,92 4,27 2,31 GPDS750 41,55 2,55 27,19 3,55 2,14 Tabla 6.29: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 95%. Operador LBP con R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 12,13 8,41 10,64 4,14 4,70 GPDS100 19,69 8,37 14,69 4,52 3,90 GPDS750 31,04 8,15 20,93 5,84 3,80 10 MCYT 19,95 2,58 15,61 3,20 2,82 GPDS100 29,56 3,04 19,78 4,09 2,22 GPDS750 40,89 3,09 26,97 3,97 2,29 Tabla 6.30: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 85%. Operador LBP con R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 11,51 9,35 10,65 4,27 5,46 GPDS100 18,49 9,71 14,62 4,93 4,30 GPDS750 30,00 8,86 20,65 6,76 4,05 10 MCYT 18,50 3,59 14,78 3,48 3,78 GPDS100 27,30 3,85 18,66 4,39 2,60 GPDS750 39,31 3,55 26,13 4,20 2,61 100 6.2. LBP USANDO ANÁLISIS POR BLOQUES Tabla 6.31: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. PCA con 75%. Operador LBP con R=2 y P=16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 10,81 10,43 10,66 4,20 5,55 GPDS100 16,47 10,53 13,85 4,80 4,16 GPDS750 27,91 10,81 20,36 6,27 4,74 10 MCYT 17,23 4,05 13,93 3,05 4,34 GPDS100 25,40 4,23 17,61 4,62 2,73 GPDS750 37,94 4,11 25,47 4,52 2,60 En este punto se detecta que al hacer uso del análisis por bloques para el patrón LBP se presenta el caso en el cual el bloque de análisis contenga únicamente pixeles pertenecientes al fondo de la imagen. Los parámetros que corresponden a este tipo de bloques no aportan ninguna información para la caracterización de los trazos que conforman una firma. Lo anterior explicaría el hecho de que se logre una importante disminución de la dimensionalidad sin mayores cambios en el desempeño del sistema. Por esta razón, se implementa un procedimiento orientado a detectar este tipo de bloques, y a eliminar los parámetros correspondientes del vector final de características de la muestra. Una vez seleccionados aquellos bloques de análisis que corresponden a los trazos de la firma, se tiene que el número de bloques resultante varía de muestra a muestra. Para lograr una longitud constante para el vector de características, se toma la idea implementada para las características calculadas para la GLCM, y por tanto, se calculan los valores de la media (μ) y de desviación estándar (σ)paraelpatrónLBPdetodoslos bloques seleccionados. En consecuencia, la longitud del vector final de características será de 20 elementos para el caso del patrón LBP con configuración R=1yP=8(μ=10 yσ= 10) y de 36 elementos para el caso R=2yP=16(μ=18yσ= 18). Los resultados obtenidos con la anterior modificación se presentan a continuación Tabla 6.32: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Seleccionando bloques. R=1yP=8. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 4,54 38,04 17,94 3,63 9,95 GPDS100 4,97 36,48 18,89 3,70 9,49 GPDS750 3,22 38,69 18,88 4,14 8,97 10 MCYT 9,98 23,43 13,34 4,42 11,37 GPDS100 10,50 21,13 14,42 4,77 7,72 GPDS750 5,45 23,53 12,11 5,83 7,87 Tabla 6.33: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Seleccionando bloques. R=2yP= 16. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 3,92 32,05 15,17 3,08 10,38 GPDS100 6,01 29,53 16,41 4,47 9,73 GPDS750 4,08 28,74 14,97 4,07 10,14 10 MCYT 8,94 16,41 10,80 3,82 10,18 GPDS100 12,44 14,79 13,31 4,95 6,98 GPDS750 6,93 14,98 9,90 4,98 7,37 CAPÍTULO 6. COMBINACIÓN DE INFORMACIÓN ESPACIAL CON TEXTURA 101 Tabla 6.34: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Seleccionando bloques. Patrón combinación. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 4,34 31,18 15,07 3,36 9,04 GPDS100 5,37 27,81 15,28 3,61 9,20 GPDS750 4,74 30,60 16,17 4,34 9,92 10 MCYT 9,14 16,53 10,98 3,74 10,18 GPDS100 10,86 14,25 12,11 4,17 6,89 GPDS750 8,25 15,35 10,87 5,64 6,82 Se tiene que la varianza entre resultados para diferentes bases de datos disminuye. Estos resultados representan una mejoría respecto a los datos presentados en las tablas 5.15, 5.16 y 5.17. Haciendo uso del mapeo PCA se tiene Tabla 6.35: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Seleccionando bloques. R=1yP=8.PCAcon95%. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 3,20 41,81 18,64 3,13 8,91 GPDS100 3,11 42,11 20,34 3,06 8,59 GPDS750 2,54 43,07 20,45 2,78 8,92 10 MCYT 6,93 28,43 12,31 3,60 11,50 GPDS100 6,64 29,85 15,19 3,65 8,03 GPDS750 5,32 28,88 14,01 5,44 8,67 Tabla 6.36: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Seleccionando bloques. R=2yP= 16.PCAcon95%. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 4,55 34,24 16,43 3,31 8,48 GPDS100 6,45 26,37 15,25 3,58 8,33 GPDS750 8,12 30,43 17,97 5,81 9,17 10 MCYT 9,26 21,10 12,22 3,43 10,78 GPDS100 11,43 13,44 12,18 3,97 5,65 GPDS750 11,75 16,94 13,66 5,66 6,68 Tabla 6.37: LBP bloques. Para imágenes de dimensión [256 x 256] y bloques [32 x 32]. Seleccionando bloques. Patrón combinación. PCA con 95%. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 4,36 30,68 14,88 3,34 8,94 GPDS100 5,39 29,14 15,89 4,01 8,41 GPDS750 5,04 30,51 16,30 4,35 9,51 10 MCYT 8,91 16,62 10,84 3,53 9,73 GPDS100 10,45 13,93 11,73 4,26 6,51 GPDS750 8,33 15,15 10,84 5,64 6,88 Como se esperaba, una vez implementado el procedimiento para no tener en cuenta la información del fondo de la imagen, el uso del mapeo PCA no tiene incidencia positiva sobre el desempeño del sistema cuando se realiza un análisis por bloques. 102 6.3. COMBINACIÓN DE CARACTERÍSTICAS 6.3. Combinación de características Se propone una combinación a nivel de características (feature level) de los vectores calculados para la GLCM y para el LBP. Para la combinación se toman las configuraciones con mejores resultados obtenidos en la pruebas realizadas hasta este punto. Para el caso de la GLCM, calculamos las cinco características analizadas (CHEEC), y en el caso del LBP usamos el patrón combinación. Como se mostró, el análisis por bloques haciendo uso de la selección de bloques relevantes (que contienen trazos de la firma) es la mejor metodología. La tabla 6.38 presenta los resultados obtenidos. Se puede ver que los resultados son mejores si se comparan con los resultados obtenidos cuando se usan las características de forma separada (Tablas 6.3 y 6.34). Tabla 6.38: GLCM+LBP. Tamaño [256 256] y bloques [32 x 32]. Seleccionando bloques. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,72 25,79 14,34 3,92 9,20 GPDS100 6,20 25,98 14,94 3,73 7,96 GPDS750 6,00 27,67 15,57 4,34 8,79 10 MCYT 11,51 13,71 12,06 3,22 9,76 GPDS100 11,95 11,52 11,79 4,06 5,53 GPDS750 8,29 14,16 10,45 4,40 6,74 Como complemento, la tabla 6.39 presenta resultados cuando se usa el análisis PCA para reducir la dimensión del vector de características reteniendo un 95% de la varianza de los datos. Tabla 6.39: GLCM+LBP. Tamaño [256 256] y bloques [32 x 32]. Seleccionando bloques. PCA 95 % #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 5,23 30,82 15,47 3,32 8,66 GPDS100 6,43 30,62 17,12 5,45 9,51 GPDS750 5,68 30,59 16,69 4,05 9,59 10 MCYT 9,12 17,11 11,12 3,17 10,97 GPDS100 9,81 16,42 12,25 3,81 6,20 GPDS750 7,85 18,43 11,75 4,20 6,88 Estos resultados explican el buen desempeño de la combinación de características, ya que como se ve, al eliminar características el desempeño del sistema empeora. Lo anterior sugiere que las características GLCM y LBP tienen muy poca información redundante entre ellas. Resumen Se ha descrito uno de los procedimientos implementados con el objetivo de reducir el problema de la influencia del tipo de tinta sobre el desempeño del sistema de verificación. El análisis por bloques implementado tiene como objetivo el obtener un análisis CAPÍTULO 6. COMBINACIÓN DE INFORMACIÓN ESPACIAL CON TEXTURA 103 mas localizado de la imágenes. Se pudo comprobar que la inclusión de esta etapa, mejora el desempeño general del sistema respecto a los resultados obtenidos en el capitulo 5. Así mismo, la combinación de las características basadas en textura (combinación a nivel de características) permite obtener un mejor desempeño del sistema respecto al uso individual de las características. En el siguiente capítulo, se describe el uso de la transformada Wavelet como complemento de las características basadas en textura. 104 6.3. COMBINACIÓN DE CARACTERÍSTICAS Capítulo 7 Análisis de Texturas en el Dominio Transformado Una vez establecidas las bondades del análisis de la textura para la verificación de firmas manuscritas, a continuación se describe el uso de la transformada Wavelet como complemento a las características ya descritas y con el objetivo de lograr una disminución en la varianza de los datos para diferentes bases de datos debida al tipo de tinta utilizado por el firmante. El anexo A presenta las bases de la transformada Wavelet. 7.1. GLCM. Usando la transformada Wavelet Una vez que se ha eliminado el fondo de la imagen, se calcula el recuadro de menor tamaño que contiene los trazos de la firma. Posteriormente se redimensiona la imagen para que todas las muestras tengan el mismo tamaño. Después de esto, se realiza la descomposición Wavelet 2D de un solo nivel. Como resultado de esta etapa se obtienen 4 matrices: 1 con los coeficientes de aproximación y otras 3 con los coeficientes de detalle. Para estas 3 últimas se hace uso de 3 wavelet que miden las variaciones funcionales (cambios de intensidad o niveles de gris) en diferentes direcciones. ψHmide las variaciones a lo largo de las columnas (p.e. bordes horizontales), ψVresponde a variaciones alolargodelasfilas (p.e. bordes verticales) y ψDcorresponde a variaciones diagonales. Como se describe en el anexo A, cada una de estas wavelet es el producto de una escala unidimensional ϕy la correspondiente wavelet ψ. Excluyendo aquellos productos que arrojan un resultado unidimensional, como ϕ(x)ψ(x), los cuatro productos restantes definen la función de escala ϕ(x, y)=ϕ(x)ϕ(y)(7.1) y tres wavelet con sensitividad direccional ψH(x, y)=ψ(x)ϕ(y) ψV(x, y)=ϕ(x)ψ(y) ψD(x, y)=ψ(x)ψ(y)(7.2) La wavelet usada fue la Haar. 105 112 7.2. LBP. USANDO LA TRANSFORMADA WAVELET Si se tiene en cuenta el aumento en el coste computacional debido a la inclusión de un nivel más en la descomposición Wavelet, y la leve mejoría obtenida, se puede decir que un solo nivel en la descomposición es suficiente para el buen desempeño del sistema. Como se mencionó anteriormente, las pruebas realizadas hasta ahora corresponden al uso de la Wavelet tipo Haar. Para visualizar el desempeño de la metodología en desarrollo para el caso de las Wavelet más comunes, la tabla 7.14 presenta los resultados obtenidos. Como se puede observar, los mejores resultados se obtienen para la Wavelet tipo Haar, aunque se pueden destacar los resultados obtenidos para el caso de la Wavelet bior1.1. Tabla 7.14: WT+LBP. Diferentes Wavelet evaluadas. Wavelet FAR( %) FRR( %) EER( %) σ-FAR σ-FRR Haar 6,54 25,90 14,28 3,88 8,59 db2 5,66 34,04 17,01 3,69 8,56 db3 6,36 35,09 17,85 3,77 8,50 db4 7,98 38,73 20,29 4,35 7,97 db6 6,83 39,94 20,08 4,23 7,97 db8 7,77 38,78 20,18 4,74 8,44 db10 7,87 39,84 20,65 4,75 8,15 db20 5,77 40,12 19,52 3,69 7,79 sym1 5,23 31,50 15,74 3,29 8,98 sym2 5,75 34,09 17,08 3,81 8,60 sym3 6,01 36,24 18,10 4,08 8,79 sym6 7,43 35,10 18,50 4,13 8,46 sym8 7,67 38,26 19,91 4,73 8,72 sym10 6,95 37,95 19,35 4,63 9,46 sym20 5,57 40,42 19,52 3,78 8,05 coif1 6,57 39,55 19,76 4,40 9,05 coif2 6,39 38,97 19,44 4,51 8,71 coif3 7,31 37,81 19,52 4,07 8,83 coif4 7,37 37,55 19,45 4,78 8,27 coif5 5,52 34,86 17,25 3,37 8,51 bior1.1 4,46 31,59 15,31 2,90 7,77 bior2.2 6,28 36,19 18,24 3,74 8,90 bior3.3 7,27 38,00 19,56 4,58 8,60 bior4.4 7,79 38,09 19,91 4,96 8,83 bior5.5 5,95 35,70 17,85 3,94 8,88 bior1.5 5,72 33,99 17,03 3,70 8,61 bior2.8 6,90 37,18 19,01 4,17 8,82 bior3.9 7,83 36,89 19,46 4,53 8,29 bior6.8 6,85 38,31 19,44 4,42 8,94 rbio1.1 5,29 31,92 15,95 3,35 8,46 rbio2.2 5,06 31,87 15,78 3,58 8,36 rbio3.3 5,97 35,96 17,96 3,83 8,25 CAPÍTULO 7. ANÁLISIS DE TEXTURAS EN EL DOMINIO TRANSFORMADO 113 7.3. Combinación de características en el dominio transformado A continuación, se presentan los resultados obtenidos cuando se usa la transformada Wavelet como complemento de la combinación de características planteada en la sección 6.3. En primer lugar se realiza la descomposición Wavelet, posteriormente se calculan las características GLCM y LBP, y finalmente estas son concatenadas para formar el vector de características. Tabla 7.15: WT+GLCM+LBP. Tamaño original y bloques [32 x 32]. Seleccionando bloques. #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 3,94 25,77 12,67 2,90 9,20 GPDS100 6,30 18,55 11,71 3,27 7,45 GPDS750 6,69 19,63 12,41 5,50 7,87 10 MCYT 9,12 11,83 9,80 3,42 9,42 GPDS100 11,25 6,27 9,42 3,63 4,40 GPDS750 8,51 6,79 7,88 4,31 4,73 Como complemento, la tabla 7.16 presenta resultados cuando se usa el análisis PCA para reducir la dimensión del vector de características reteniendo un 95% de la varianza de los datos. Tabla 7.16: WT+GLCM+LBP. Tamaño original y bloques [32 x 32]. Seleccionando bloques. PCA 95% #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 3,34 28,78 13,51 2,31 8,87 GPDS100 4,88 20,64 11,85 2,98 7,16 GPDS750 5,43 23,62 13,47 4,99 7,84 10 MCYT 7,14 13,83 8,82 2,98 10,03 GPDS100 8,98 8,41 8,76 3,25 5,46 GPDS750 7,27 8,51 7,73 4,53 5,55 Nuevamente, el uso del análisis PCA no conlleva a mejores resultados. Resumen Se ha descrito el segundo procedimiento implementado con el objetivo de reducir el problema de la influencia del tipo de tinta sobre el desempeño del sistema de verificación. Se estudió el uso de la transformada Wavelet como complemento de las características basadas en el análisis de textura. Se pudo comprobar que la inclusión de esta etapa, mejora el desempeño general del sistema respecto a los resultados obtenidos en el capitulo 7. 114 7.3. COMBINACIÓN EN EL DOMINIO TRANSFORMADO En el siguiente capítulo, se analizan diferentes aspectos de la metodología desarrollada con el objetivo de observar el comportamiento del sistema respecto a diferentes variables como el número de firmantes y el número de muestras por firmante. Se analizan los resultados aquí obtenidos respecto a los presentados por otros autores. Capítulo 8 Análisis de la metodología propuesta. En este capítulo se presenta el análisis realizado a la metodología propuesta, y que considera en primer lugar la visualización de los mejores resultados obtenidos con cada una de las características estudiadas en este trabajo. Posteriormente se presentan los resultados obtenidos aquí junto con los resultados obtenidos por otros autores que han usado el corpus MCYT. Se ha querido observar también el comportamiento de la metodologíacuandosehaceusodeimágenes en blanco y negro para la verificación. Y finalmente se analiza el desempeño del sistema frente al número de firmantes y frente al número de muestras disponibles para cada firmante. 8.1. Resumen de los resultados A continuación se presenta un tabla resumen que contiene los mejores resultados obtenidos con cada una de las características estudiadas en las diferentes secciones que componen este documento. Tabla 8.1: Resumen de los resultados (EER) obtenidos con las diferentes características estudiadas. Característica MCYT( %) GPDS100( %) GPDS750( %) Histograma 22,91 17,91 18,18 Pseudo-Cepstrum 20,75 20,48 16,83 HPPPD 15,77 18,62 18,99 GLCM 17,20 17,85 18,65 LBP 15,05 15,69 15,39 GLCM - Bloques 12,02 15,95 20,64 LBP - Bloques 15,07 15,28 16,17 GLCM + LBP - Bloques 14,34 14,94 15,57 WT + GLCM - Bloques 12,91 14,98 17,65 WT + LBP - Bloques 14,28 12,81 13,29 WT + GLCM + LBP - Bloques 12,67 11,71 12,41 En este punto, se puede decir que se tiene una metodología que considera el uso de la transformada Wavelet como complemento de la combinación de las características basadas en el análisis de textura (GLCM y LBP), y que permite la verificación automática de firmas manuscritas a partir de una imagen con información en niveles de gris. Para determinar si los resultados obtenidos pueden considerarse aceptables, es necesario 115 116 8.2. COMPARACIÓN CON TRABAJOS SIMILARES visualizarlos junto a otros resultados obtenidos en trabajos que pueden considerarse similares, en el sentido de que emplean la misma base de datos. 8.2. Comparación con trabajos similares Es necesario aclarar, que realizar una comparación entre trabajos de diferentes autores es una tarea complicada. Existen diversos factores que marcan diferencia y que no permiten la comparación completa de los resultados. La base de datos empleada, la metodología de entrenamiento seguida, los procedimientos de validación adoptados, el modelo de clasificación usado, e incluso los algoritmos de caracterización, se convierten en variables difíciles de controlar. En este sentido, antes que una comparación, a continuación se presenta una tabla que resume los resultados de algunos de los trabajos que han sido revisados en esta Tesis, y que tienen como factor común la base de datos MCYT. Como puede verse en la tabla 8.2, si bien los resultados obtenidos con la metodología propuesta no son los mejores, si están muy cercanos a los reportados por otros autores usando imágenes en blanco y negro. Si se compara con el trabajo que usa la información de los niveles de gris, claramente la metodología propuesta supera los resultados previos. Lo anterior permite validar la hipótesis de la viabilidad de un sistema de verificación de firmas manuscritas basado en la información de los niveles de gris. Tabla 8.2: Comparación de la metodología propuesta con otros trabajos publicados. ( %)EER Escala Güler et al. [GM08] 25,10 Gris Alonso-Fernandez et al.[AFFFOG07] 22,40/20,00* B/N Wen et al.(B)[WFTZ09] 15,00 B/N Fierrez-Aguilar et al. [FaKOgJ05] 11,00/9,28* B/N Gilperez et al [GAFP+08] 10,18/6,44* B/N Metodología propuesta 12,67/9,80* Gris *: 2/3 del total de las muestras se usan para el entrenamiento. 8.3. Metodología propuesta en Blanco y Negro Existe un aspecto muy relevante que concierne a la metodología propuesta, y es el hecho de que es necesario evidenciar el aporte de la información de los niveles de gris al desempeño del sistema. Para estudiar este aspecto, se plantea una prueba en donde se evalúa la metodología propuesta usando imágenes en blanco y negro. Los resultados obtenidos se presentan a continuación CAPÍTULO 8. ANÁLISIS DE LA METODOLOGÍA PROPUESTA. 117 Tabla 8.3: Metodología propuesta evaluada con imágenes en blanco y negro #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5MCYT 6,30 27,14 14,64 4,12 9,49 GPDS100 15,49 17,23 16,26 5,87 6,45 GPDS800 14,97 25,05 19,42 7,69 7,29 10 MCYT 12,37 13,80 12,73 3,83 9,97 GPDS100 25,04 7,04 18,40 5,53 4,36 GPDS800 25,43 12,08 20,50 7,97 6,24 Se tiene entonces que el desempeño del sistema usando imágenes en blanco y negro empeora de forma importante si se compara con los resultados obtenidos cuando se usan las imágenes en niveles de gris. Lo anterior sugiere que la información contenida en los niveles de gris, realmente aporta para un mejor desempeño del sistema. 8.4. Desempeño vs número de firmantes Como se mencionó en la metodología de experimentación descrita en la sección 3.5, hasta ahora las pruebas fueron realizadas tomando las muestras de los primeros 75 firmantes de cada una de las tres base de datos usadas. A continuación se presenta un análisis de los resultados que se obtienen con la metodología desarrollada cuando el número de firmantes de la base de datos aumenta progresivamente. Para ello se hace uso de la base de datos GPDS750, que contiene un total de 750 firmantes, y se evalúa el sistema para 200, 400, 600 y 750 firmantes. Tabla 8.4: Desempeño de WT+GLCM+LBP vs número de firmantes #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 5GPDS800-75 6,69 19,63 12,41 5,50 7,87 GPDS800-200 5,98 20,92 12,62 4,80 7,95 GPDS800-400 6,32 22,31 13,41 5,16 8,07 GPDS800-600 6,29 23,95 13,66 5,12 7,83 GPDS800-800 6,18 23,97 13,69 5,09 7,88 10 GPDS800-75 8,51 6,79 7,88 4,31 4,73 GPDS800-200 8,26 7,13 7,85 4,35 4,93 GPDS800-400 9,29 7,74 8,73 4,73 5,07 GPDS800-600 9,66 8,71 9,07 4,93 5,34 GPDS800-800 9,58 8,83 9,11 4,85 5,43 En la tabla 8.4 se puede ver un aumento progresivo de los valores de EER a medida queseaumentaelnúmerodefirmantes. Se puede destacar el hecho de que el aumento en el valor de EER es cada menor y parece establecerse en 14% y 10% para los casos en que se usan 5 ó 10 muestras genuinas para el entrenamiento, respectivamente. Volviendo a la tabla 8.2, el valor de establecimiento (cercano a 14 %) del desempeño del sistema puede seguir siendo considerado aceptable si se tiene en cuenta que algunos otros autores reportan valores similares, aunque es necesario aclarar que en este caso se habla de experimentos con bases de datos diferentes. 118 8.5. DESEMPEÑO VS NÚMERO DE MUESTRAS. Finalmente, es importante resaltar que se ha tenido un aumento del 11 % en el valor de EER (se pasó de 12,41 a 13,69) para un aumento del 1000 % en el número de firmantes en la base de datos (se pasó de 75 a 750). 8.5. Desempeño vs número de muestras. En esta sección se presenta un análisis del desempeño de la metodología desarrollada respecto al número de muestras genuinas usadas para crear el modelo de cada firmante. Las tablas 8.5, 8.6 y 8.7, presenta los resultados obtenidos para las pruebas realizadas con cada una de las bases de datos usadas en este trabajo, esto es, MCYT, GPDS100 y GPDS750 respectivamente. Los resultados corresponden a las pruebas realizadas cuando el número de muestras genuinas usadas para crear el modelo, varía desde 3 hasta 10. Se usaron los primeros 75 firmantes de cada una de las bases de datos. Tabla 8.5: Desempeño del sistema vs número de muestras. MCYT #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 3MCYT 1,32 40,34 18,66 1,44 8,06 4MCYT 2,60 31,60 14,87 2,07 7,80 5MCYT 3,94 25,77 12,67 2,90 9,20 6MCYT 5,36 21,17 11,29 3,21 8,30 7MCYT 6,80 17,31 10,45 3,50 9,11 8MCYT 7,13 14,55 9,49 3,39 8,74 9MCYT 8,06 13,39 9,59 3,53 9,36 10 MCYT 9,12 11,83 9,80 3,42 9,42 Tabla 8.6: Desempeño del sistema vs número de muestras. GPDS100 #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 3GPDS100 3,01 32,66 16,85 2,38 7,94 4GPDS100 4,78 23,94 13,49 3,20 7,99 5GPDS100 6,30 18,55 11,71 3,27 7,45 6GPDS100 6,99 14,65 10,27 3,48 6,60 7GPDS100 7,97 12,06 9,66 3,31 6,46 8GPDS100 9,40 8,97 9,22 3,93 5,80 9GPDS100 10,29 7,71 9,30 3,90 5,13 10 GPDS100 11,25 6,27 9,42 3,63 4,40 Tabla 8.7: Desempeño del sistema vs número de muestras. GPDS750 #B.D. FAR( %) FRR( %) EER(%) σ-FAR σ-FRR 3GPDS750 4,57 34,09 18,34 4,92 8,12 4GPDS750 5,95 26,21 15,16 5,54 8,40 5GPDS750 6,69 19,63 12,41 5,50 7,87 6GPDS750 6,66 14,50 10,03 5,43 7,31 7GPDS750 7,76 12,21 9,60 4,96 6,73 8GPDS750 8,96 9,76 9,28 4,70 6,38 9GPDS750 9,48 7,72 8,80 4,49 5,05 10 GPDS750 8,51 6,79 7,88 4,31 4,73 CAPÍTULO 8. ANÁLISIS DE LA METODOLOGÍA PROPUESTA. 119 Tomando como referencia el uso de 5 muestras originales, se puede ver que un número menor de muestras (3 ó 4) conlleva a un notable empeoramiento del rendimiento del sistema. Para el caso de un número mayor de muestras, se tiene que el desempeño mejora progresivamente con el aumento del número de muestras genuinas consideradas en el entrenamiento. Para el caso de las bases de datos MCYT y GPDS750, el desempeño parece acercase a un valor estable a partir de 7 u 8 muestras. Para el caso de la base de datos GPDS750, el desempeño continua mejorando a medida que se aumenta el número de muestras. Si bien los resultados obtenidos usando 10 muestras genuinas para la construcción del modelo de cada firmante, son siempre los mejores, este valor puede ser considerado poco práctico para la implementación de un sistema real. Por otro lado, y asumiendo que 5 es número de muestras más cercano a lo que podría ser una aplicación en ambientes reales, podría considerarse la inclusión de una o dos muestras más con el ánimo de aprovechar los beneficios mostrados en las tablas 8.5 - 8.7. Resumen Se ha presentado un análisis de la metodología propuesta en esta Tesis que incluye la combinación a nivel de características, de las características basadas en análisis de textura tenidas en cuenta. Así mismo, se estableció el comportamiento del sistema para diferente número de firmantes, y para diferente número de muestras de cada firmante disponibles para la creación del modelo. En el siguiente capítulo se presentan las conclusiones a las que se puede llegar a partir de los resultados y análisis realizados en cada uno de los capítulos presentado hasta aquí. 120 8.5. DESEMPEÑO VS NÚMERO DE MUESTRAS. Capítulo 9 Discusión y Conclusiones Los resultados obtenidos en las pruebas realizadas con la metodología de verificación propuesta son mejores cuando se hace uso de la información de los niveles de gris de la imagen, respecto al caso en que se trabaja con imágenes en blanco y negro. A continuación se presentan una serie de conclusiones directamente relacionadas con cada una de las etapas seguidas en el desarrollo de la metodología presentada en este documento: 1. Se ha comprobado la hipótesis planteada en el sentido de que caracterizar los cambios entre los niveles de gris del trazo de una firma manuscrita aporta información que permite mejorar la verificación automática de la identidad de una persona a partir de su firma. Los resultados mostraron que el desempeño del sistema empeora de forma importante cuando se usan imágenes en blanco y negro con la metodología propuesta. 2. Se mostró que la metodología propuesta tiene un comportamiento estable para un número grande de firmantes en la base de datos. Si bien los resultados empeoran respecto a los obtenidos con las pruebas iniciales, en donde se evaluó el sistema con 75 firmantes, la diferencia observada entre los resultados para 600 y 750 firmantesesmuchomenor.Loanteriorsugierequeparaunnúmeromayorde firmantes, el desempeño del sistema mostrará variaciones cada vez más pequeñas. 3. Si bien no es posible realizar una comparación real con sistemas planteados por otros autores, se ha presentado un resumen con los resultados obtenidos por diferentes autores cuando usan la misma base de datos MCYT. A partir de este ejercicio, se puede afirmar que un sistema de verificación de firmas manuscritas basado en la información de niveles de gris y usando características basada en análisis de texturas, es viable. Esto teniendo en cuenta que los resultados obtenidos en este trabajo son muy cercanos a los reportados para otros sistemas que usan imágenes en blanco y negro, y que son mejores respecto a resultados previos cuando se trabaja con niveles de gris. 4. El uso de la transformada wavelet como complemento de las características basadas en el análisis de textura, y en especial como complemento del LBP, permitió mejorar el desempeño del sistema. Se demostró que un solo nivel de descomposición es suficiente para lograr resultados aceptables. Una descomposición Wavelet 121 128 A.1. EXPANSIÓN EN SERIES WAVELET define como Wdf(j, n)=Wfaj,nβ αj =∞ −∞ f(x)ψαj x−nβ αjdx =f∗˜ ψαj nβ αj. (A.10) la figura A.3 ilustra el patrón de muestreo en el espacio de fase. Cuando la escala aumenta, la densidad de muestras aumenta. Figura A.3: Muestreo del espacio de fase correspondiente a una transformada wavelet discreta. Cada muestra corresponde al producto interno con una wavelet en particular. Este patrón de muestreo se adapta a la forma de la celda de resolución de la wavelet para diferentes escalas (Figura A.2) [Mal89]. A.1. Expansión en series wavelet Se define la expansión en series wavelet de una función f(x)∈L2(R)relativa a la wavelet ψ(x)y la función de escala ϕ(x),como f(x)= k cj0(k)ϕj0,k(x)+ ∞  j=j0 k dj(k)ψj,k(x)(A.11) donde j0es una escala inicial arbitraria. Los valores cj0(k)se denominan comúnmente como coeficientes de aproximación oescala; mientras que los valores dj(k)son llamados coeficientes de detalle owavelet. Esto debido al hecho de que en la primera sumatoria de la ecuación A.11 se emplean funciones de escala para obtener una aproximación de la función f(x)para la escala j0. Para las escalas superiores, j≥j0en la segunda sumatoria, se adiciona una función con una resolución más fina — sumatoria de wavelets — a la aproximación inicial con el fin de obtener un aumento en el detalle. Los coeficientes de expansión son calculados como cj0(k)=f(x),ϕ j0,k(x)=f(x)ϕj0,k(x)dx dj(k)=f(x),ψ j,k(x)=f(x)ψj,k(x)dx (A.12) APÉNDICE A. TRANSFORMADA WAVELET 129 A.2. Transforma wavelet discreta Al igual que las series de Fourier, la expansión en series wavelet de la sección anterior mapean una función de tiempo continuo en una secuencia de coeficientes. Si la función que se quiere representar es una secuencia de números, como es el caso de muestras de una función continua f(x),loscoeficientes que resultan son llamados la Transformada wavelet discreta (DWT) de f(x). Para este caso, las series definidas en las ecuaciones A.11 y A.12 se convierten en el par de transformadas DWT Wϕ(j0,k)= 1 √M x f(x)ϕj0,k(x) Wψ(j, k)= 1 √M x f(x)ψj,k(x)(A.13) para j≥j0y f(x)= 1 √M k Wϕ(j0,k)ϕj0,k(x)+ 1 √M j=j0 k Wψ(j, k)ψj,k(x).(A.14) Aquí, f(x),ϕjo,k(x)yψj,k(x)son funciones de variable discreta x=0,1,2,···,M −1. Comúnmente, se establece que j0=0y se selecciona Mpara que sea potencia de 2 (esto es, M=2 j) por lo que las sumatorias son desarrolladas para x=0,1,2,···,M −1, j=0,1,2,···,J−1,yk=0,1,2,···,2j−1. Los valores Wϕ(j0,k)yWψ(j, k)corresponden a los valores cj0(k)ydj(k)de la expansión en series de la sección anterior. El cambio no es necesario pero ayuda para la estandarización en la notación. A.3. Transformada rápida wavelet La transformada rápida wavelet (FWT, por sus siglas en inglés) es una implementación computacionalmente eficiente de la transformada discreta wavelet (DWT) que hace uso de las relación entre los coeficientes de la DWT de escalas contiguas. Consideremos la función de escala ϕ(x)= n hϕ(n)√2ϕ(2x−n)(A.15) Los coeficientes hϕ(n)presentes en esta ecuación recursiva se denominan coeficientes de la función de escala;hϕse refiere a un vector de escala. Esta ecuación es fundamental para el análisis multiresolución y es llamada Ecuación de refinamiento, Ecuación MRA (MultiResolution Analysis) o Ecuación de dilatación. Si escalamos a xpor 2j,la trasladamos en k, y hacemos que m=2k+ntenemos que ϕ(2jx−k)= n hϕ(n)√2ϕ(2(2jx−k)−n) = m hϕ(m−2k)√2ϕ(2j+1x−m)(A.16) El vector de escala hϕpuede verse como los “pesos” usados para expandir ϕ(2jx−k) como una suma de escala. De igual forma, podemos definir 130 A.3. TRANSFORMADA RÁPIDA WAVELET ψ(x)= n hψ(n)√2ϕ(2x−n)(A.17) donde hψ(n)corresponde a los coeficientes de la función wavelet yhψes el vector wavelet. Usando el mismo procedimiento planteado en A.16, se llega a ψ(2jx−k)= m hψ(m−2k)√2ϕ(2j+1x−m)(A.18) Recordando la definición de un conjunto de wavelets ψj,k(x)=2 j/2ψ(2jx−k)(A.19) y reemplazándola en la ecuación A.13, se obtiene Wψ(j, k)= 1 √M x f(x)2j/2ψ(2jx−k)(A.20) en la cual puede reemplazarse el valor ψ(2jx−k)con el lado derecho de la ecuación A.18 para obtener Wψ(j, k)= 1 √M x f(x)2j/2 m hψ(m−2k)√2ϕ(2j+1x−m).(A.21) Intercambiando las sumatorias y reordenando términos, se tiene que Wψ(j, k)= m hψ(m−2k)1 √M x f(x)2(j+1)/2ϕ(2j+1x−m)(A.22) donde, la expresión entre corchetes es igual a la ecuación A.13 haciendo j0=j+1, por lo que se puede escribir Wψ(j, k)= m hψ(m−2k)Wϕ(j+1,m)(A.23) lo que muestra que los coeficientes de detalle DWT para la escala json una función de los coeficientes de aproximación DWT en la escala j+1. Mediante un procedimiento similar al anterior, se llega a que Wϕ(j, k)= m hϕ(m−2k)Wϕ(j+1,m).(A.24) Las ecuaciones (A.23) y (A.24), revelan una importante relación entre los coeficientes DWT de escala adyacentes. Es posible realizar el cálculo de Wϕ(j, k)yWψ(j, k)(los coeficientes de aproximación y detalle para la escala j) convolucionando Wϕ(j+1,k)con los vectores de escala y wavelet con tiempo invertido, hϕ(−n)yhψ(−n), y submuestreando los resultados. La figura A.4 resume estas operaciones en un diagrama de bloques. Se escribe entonces que Wψ(j, k)=hψ(−n)∗Wϕ(j+1,n)|n=2k,k≥0(A.25) APÉNDICE A. TRANSFORMADA WAVELET 131 y Wϕ(j, k)=hϕ(−n)∗Wϕ(j+1,n)|n=2k,k≥0(A.26) en donde las convoluciones se evalúan para los instantes n=2kpara k≥0.Evaluar las convoluciones para indices paresynonegativosesequivalenteafiltrar y disminuir la resolución en un factor de 2. Figura A.4: Diagrama de bloques de FWT A.4. Transformada wavelet en dos dimensiones La transformada en una dimensión descrita anteriormente puede ser extendida para el caso de una función de dos dimensiones como son las imágenes. Para ello, se definen una función de escala ϕ(x, y), y tres wavelets bi-dimensionales ψH(x, y),ψV(x, y)y ψD(x, y). Cada una de estas wavelet es el producto de una escala unidimensional ϕy la correspondiente wavelet ψ. Excluyendo aquellos productos que arrojan un resultado unidimensional, como ϕ(x)ψ(x), los cuatro productos restante definen la función de escala ϕ(x, y)=ϕ(x)ϕ(y)(A.27) y tres wavelet con sensitividad direccional ψH(x, y)=ψ(x)ϕ(y) ψV(x, y)=ϕ(x)ψ(y) ψD(x, y)=ψ(x)ψ(y)(A.28) Estas wavelets miden las variaciones funcionales (cambios de intensidad o niveles de gris) en diferentes direcciones. ψHmide las variaciones a lo largo de las columnas (p.e. bordes horizontales), ψVresponde a variaciones a lo largo de las filas (p.e. bordes verticales) y ψDcorresponde a variaciones diagonales. Para realizar la extensión de la DWT para dos dimensiones definimos las funciones base escalada y trasladada: 132 A.4. TRANSFORMADA WAVELET EN DOS DIMENSIONES ϕj,m,n(x, y)=2 j2ϕ(2jx−m, 2jy−n)(A.29) ψj,m,n(x, y)=2 j2ψi(2jx−m, 2jy−n),i={H,V, D}(A.30) donde iidentifica a las wavelets direccionales definidas en la ecuación A.28. Más que un exponente, ies un superíndice que toma los valores H,V yD.Latransformada wavelet discreta de una función f(x, y)de tamaño M×Nqueda entonces definida como Wϕ(j0,m,n)= 1 √MN M−1  x=0 N−1  y=0 f(x, y)ϕj0,m,n(x, y)(A.31) Wi ψ(j, m, n)= 1 √MN M−1  x=0 N−1  y=0 f(x, y)ψi j,m,n(x, y),i={H, V, D}(A.32) donde j0es una escala inicial arbitraria y los coeficientes Wϕ(jo,m,n)definen una aproximación a la función f(x, y)en la escala j0.Loscoeficientes Wi ψ(j, m, n)aportan los detalles horizontales, verticales y diagonales para las escalas j≥j0. Generalmente se tiene que j0=0y se selecciona N=M=2 jhaciendo j=0,1,2,···,J −1y m, n =0,1,2,···,2j−1. Al igual que la transformada wavelet discreta unidimensional, la DWT bidimensional puede ser implementada usando filtros digitales y downsamplers. Con funciones bidimensional wavelet y de escala separables, es posible calcular la FWT unidimensional para las filas de f(x, y), y a continuación calcular la FWT de las columnas resultantes. La figura A.5 muestra el proceso mediante un diagrama de bloques. Es importante resaltar que la FWT dimensional también “filtra´´ los coeficientes de aproximación de la escala j+1para encontrar los coeficientes de aproximación y detalle de la escala j.Sin embargo, para el caso bidimensional se obtienen tres conjuntos de coeficientes de detalle (detalles horizontales, verticales y diagonales). El banco de filtro de escala sencilla de la figura A.5 puede “iterarse´´ (uniendo la salida de aproximación con la entrada de un nuevo banco de filtros) con el fin de producir una transformada de escala Pen la cual la escala j=J−1,J,2,···,J −P. Así como en el caso unidimensional, la imagen f(x, y) se usa como entrada de Wϕ(J, m, n). Se convolucionan las filas con hϕ(−n)yhψ(−n)y se realiza el downsampling sobre las columnas. El resultado son dos imágenes cuyas resoluciones horizontales han sido reducidas por un factor de 2. Las componentes de detalle o pasa-altas caracterizan la información de alta frecuencia de la imagen con orientación vertical; las pasabajas, comoponentes de aproximación, contienen su información de baja frecuencia. Ambas imágenes son filtradas en el sentido de las columnas y después del downsampling se obtienen las subimágenes de salida con un cuarto del tamaño original Wϕ,WH ψ,WV ψyWD ψ. APÉNDICE A. TRANSFORMADA WAVELET 133 Figura A.5: Diagrama de bloques para el cálculo de la DWT bidimensional. 134 A.4. TRANSFORMADA WAVELET EN DOS DIMENSIONES Apéndice B Clasificación El problema del aprendizaje puede plantearse de la siguiente manera: Dada una muestra de tamaño limitado, encuentre una descripción concisa de los datos. Si los datos son una muestra de patrones entrada-salida, una descripción concisa de los datos es una función que pueda producir una salida, a partir de la entrada. Este problema se conoce como aprendizaje supervisado porque los objetos en consideración se encuentran asociados a un valor objetivo (clases, valores reales). Si los datos corresponden solamente a muestras de los objetos sin un valor objetivo asociado, el problema se conoce como aprendizaje no supervisado. Una descripción concisa de estos datos podría ser un conjunto de clusters o una densidad de probabilidad que establezca que tan probable es observar un objeto determinado en un futuro [Her01]. B.1. Aprendizaje Supervisado En el problema del aprendizaje supervisado se tiene una muestra de pares entradasalida (también llamado muestra de entrenamiento), y la tarea es encontrar una función determinística que realice un mapeo de cualquier entrada hacia una salida de tal forma que para futuros pares entrada-salida el desacierto sea mínimo. Claramente, cada vez que se requiera el valor objetivo de un elemento presente en la muestra de entrenamiento, se retornará el valor que aparece con mayor frecuencia asociado a este elemento en la muestra de entrenamiento. Sin embargo, hacer una generalización para nuevos elementos que no están presentes en la muestra de entrenamiento es una tarea difícil. B.1.1. Aprendizaje de clasificación Si el espacio de salida no tiene una estructura excepto si dos elementos del espacio de salida son iguales o no, se denomina un problema de aprendizaje de clasificación. Cada elemento del espacio de salida se llama clase. Este es un problema presente en casi cualquier tarea de reconocimiento de patrones. Es de particular importancia el problema de clasificación binaria, esto es, el espacio de salida tiene solamente dos elementos, una que se considera la clase positiva y otro que será la clase negativa. Aunque conceptualmente es un problema simple, el planteamiento binario puede extenderse a una clasificación multiclase si este se considera como una serie de clasificaciones binarias. 135 136 B.2. DISCRIMINANTE LINEAL B.1.2. Aprendizaje de función Si el espacio de salida es un espacio métrico como el de los números reales entonces la tarea de aprendizaje se conoce como un problema de aprendizaje de función. Una de las ventajas mas importantes del aprendizajedefunciónesquepormediodelamétrica en el espacio de salida es posible usar técnicas de gradiente descendiente siempre que la función f(x)sea una función diferenciable. Existe una relación interesante entre el aprendizaje de clasificación y el aprendizaje de función cuando se toma una perspectiva probabilística. Si consideramos un problema de clasificación binaria, es suficiente considerar solamente la probabilidad de que un objeto dado pertenezca a la clase positiva. Así, siempre que se tenga la capacidad de aprender la función de los objetos hacia [0 1] (la probabilidad de que el objeto pertenece a la clase positiva), habremos aprendido implícitamente una función de clasificación usando un umbral para la salida en 1/2.Lo anterior se conoce en el campo de la estadística como regresión logística, y es la base del algoritmo de aprendizaje de las máquinas de soporte vectorial. De hecho, es una práctica común el uso de valores reales de salida antes de la umbralización como una medida de confianza aún cuando no se ha usado un modelo probabilístico en el proceso de aprendizaje. B.2. Discriminante Lineal La clasificación basada en un discriminante asume directamente un modelo para el discriminante, pasando por alto el cálculo de probabilidades. Esta metodología supone la forma del discriminante pero no supone y tampoco requiere información sobre las densidades. Esta metodología es denominada no-paramétrica, en donde los parámetros hacen referencia a los parámetros de las densidades de probabilidad de las clases. El problema de encontrar una función discriminante lineal se formula como el problema de minimizar una función de criterio. La función de criterio obvia para propósitos de clasificación es el error de entrenamiento. Sin embargo, a pesar de lo atractivo que resulta este criterio, es necesario aclarar que tiene muchos inconvenientes. Dado que el objetivo es clasificar nuevos patrones de prueba, un error de entrenamiento pequeño no garantiza un error de prueba pequeño. B.2.1. El caso de Dos Clases Se puede definir una función discriminante como una combinación lineal de los componentes de un vector de entrada xcomo [DHS00] g(x)=wtx+w0(B.1) donde wes el vector de pesos y w0el sesgo o umbral de peso. Un clasificador lineal para dos clases implementa la siguiente regla de decisión: Decide w1si g(x)>0y decide w2si g(x)<0.Así,xseasignaalaclasew1si el producto interno wtxsupera el umbral w0yseasignaaw2en otro caso. Si se tiene que g(x)=0,xpuede ser asignado a cualquiera de las dos clases. APÉNDICE B. CLASIFICACIÓN 137 La ecuación g(x)=0define la superficie de decisión que separa los puntos asignados aw1de los puntos asignados a w2.Cuandog(x)es lineal, dicha superficie de decisión es un hiperplano. Si tanto x1como x2están sobre la superficie de decisión, entonces wtx1+w0=wtx2+w0 wt(x1−x2)=0 (B.2) lo que muestra que wes normal a cualquier vector ubicado en el hiperplano. En general, el hiperplano Hdivide el espacio de características en dos mitades, la región de decisión R1para w1ylaregiónR2para w2.Dadoqueg(x)>0si xse encuentra en R1,setiene que el vector normal wapunta hacia R1. Se dice que cualquier vector xubicado en R1 está en el lado positivo de Hy cualquiera ubicado en R2está en el lado negativo. La función discriminante g(x)proporciona una medida algebraica de la distancia de xhasta el hiperplano. Tal vez la forma mas sencilla de ver esto es expresar xcomo x=xp+rw w(B.3) donde xpes la proyección normal de xsobre H,yres la distancia algebraica deseada (positiva si xestá en el lado positivo y negativa en caso contrario). Entonces, dado que g(xp)=0, g(x)=wtx+w0=rw,(B.4) es decir, r=g(x) w(B.5) En particular, la distancia desde el origen a Hesta dada por w0/w.Siw0>0el origen esta en el lado positivo de H,ysiw0<0este está en el lado negativo. Si w0=0, entonces g(x)tiene la forma homogénea wtx, y el hiperplano pasa por el origen. La figura B.1 ilustra geométricamente estos resultados. B.3. Máquinas de Soporte Vectorial Las máquinas de soporte vectorial (SVM, por sus siglas en inglés) tienen como idea básica la de encontrar un hiperplano que separe correctamente ua conjunto de datos d-dimensional. Teniendo en cuenta que frecuentemente los datos analizados no son linealmente separables, las SVM introduce el concepto de un “espacio de características inducido por un kernel” el cual mapea los datos hacia un espacio de mayor dimensión en donde los datos son separables. Comúnmente, el mapeo de los datos hacia este espacio acarrea problemas de costo computacional y de overfitting. B.3.1. Descripción Si se tienen lmuestras de entrenamiento {xi,y i},i =1,···,l, donde cada muestra tiene dentradas (xi∈Rd), y una etiqueta de clase con dos valores posibles (yi∈ {−1,1}).