Un sistema automático de identificación de tipos de documentos

Universitat Polit` ecnica de Val` encia Departament d’Inform` atica de Sistemes i Computadors Proyecto Final de Carrera 17 de Junio de 2011 Un sistema autom´ atico de identificaci´ on de tipos de documentos Autor: Vicente Castell´ o Fos Director: Joaquim Francesc Arlandis Navarro Titulaci´ on: Ingenier´ ıa en inform´ atica 2 ´ Indice general 1. Introducci´on 5 1.1. Tareaaresolver ........................................... 5 1.2. Aproximaci´ on cient´ ıficaempleada ................................ 6 1.3. Objetivos conseguidos y aportaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4. Plandelaobra............................................ 8 2. Conceptos de reconocimiento estad´ıstico de formas 9 2.1. Modelo gen´ erico de sistema de reconocimiento de formas inductivo y supervisado . . . . 9 2.2. La aproximaci´ on estad´ ıstica.................................... 13 2.2.1. Consideraciones sobre la clasificaci´ on estad´ ıstica.................... 14 2.2.2. LaregladeBayes...................................... 15 2.3. Esquema de votaci´ on directa basado en los k-vecinos m´ as pr´ oximos............. 17 2.4. B´ usqueda r´ apida en kd-trees .................................... 19 2.5. Recuperaci´ ondedocumentos................................... 20 2.5.1. Precisi´ onyexhaustividad................................. 20 3. Estado del arte en identificaci´on de documentos 23 4. Preproceso, extracci´on y selecci´on de caracter´ısticas 25 4.1. Preproceso de im´ agenes ...................................... 26 4.1.1. Correcci´ on de la rotaci´ on ................................. 26 4.1.2. Normalizado del tama˜ no de las im´ agenes........................ 28 4.1.3. Filtrosglobales ....................................... 28 4.1.4. Escalado........................................... 29 4.2. Extracci´ on de caracter´ ısticas.................................... 29 4.2.1. Selecci´ on de caracter´ ısticaslocales ............................ 30 4.2.2. Submuestreo y orla de vecindad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.3. An´ alisis de componentes principales . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2.4. Coordenadas de posici´ on de las ventanas de caracter´ ısticas locales . . . . . . . . . 36 5. Experimentos 37 5.1. Descripci´ ondelcorpus....................................... 37 5.2. Preproceso.............................................. 50 5.3. Optimizaci´ on de par´ ametros.................................... 51 5.4. Opci´ onderechazo ......................................... 54 6. Conclusiones 57 Bibliograf´ıa 60 4´ INDICE GENERAL Cap´ıtulo 1 Introducci´on 1.1. Tarea a resolver En la sociedad actual una empresa puede recibir o generar diariamente una cantidad de documentos en papel que deben ser organizados y archivados. Con un esc´ aner de alta velocidad, consumiendo poco tiempo y esfuerzo, esta empresa puede convertir los documentos recibidos a un formato digital, ante esto surge la necesidad de organizarlos y agruparlos en tipos similares para facilitar posteriores tratamientos. Una tarea habitual en la que se da un problema espec´ ıfico de clasificaci´ on de documentos es la organizaci´ on de recibos, formularios, facturas, documentos legales, informes m´ edicos o documentos administrativos para su posterior proceso (p.ej. OCR) y/o almacenamiento. Siempre que estos documentos puedan ser divididos en categor´ ıas tales como “Factura del proveedor X”, “Formulario de encuesta tipo Y”, etc. se podr´ ıa aplicar alg´ un m´ etodo t´ ıpico de clasificaci´ on. Pero en este caso, solo parte de los documentos de cada clase permanecen invariables, mientras que el resto es distinto en cada instancia. La parte com´ un puede ser significativamente menor que la parte variable, que puede estar compuesta por gran cantidad de texto manuscrito o impreso. As´ ı, un documento perteneciente al ciclo de trabajo descrito puede ser visto como una imagen con contenidos est´ aticos (fijos o preimpresos) y variables (impresos a maquina, manuscritos, pegados, estampados, etc.). Bajo esta definici´ on, una categoria, tipo o clase de documentos se define como un conjunto de im´ agenes con la misma informaci´ on est´ atica, y diferente de la del resto de las clases. La informaci´ on variable puede ser distinta dentro de los documentos de una misma clase, tanto en tama˜ no como en contenido, como se ha apuntado anteriormente. En la figura 1.1, se muestran ejemplos de algunos tipos de documentos con informaci´ on est´ atica y variable. Este trabajo se enfrenta a la tarea de identificaci´ on de im´ agenes de documentos que provienen de m´ ultiples dominios de aplicaci´ on, sin tener en cuenta su dise˜ no, estructura, contenidos textuales y no textuales, as´ ı como diferentes cantidades de contenido cumplimentado 1. 1En este documento se utilizar´ an las expresiones “informaci´ on cumplimentada” o “contenido rellenado” para referirse al t´ ermino ingl´ es “filled-in content”. Con ellas se har´ a referencia a la parte de un documento que no es constante en todas las muestras del mismo tipo. P. ej.: las respuestas del usuario en un formulario o encuesta, o el detalle de una factura. 6 Introducci´on Figura 1.1: Ejemplos de documentos. El primero es un formulario en el que la informaci´ on est´ atica abarca la mayor parte del documento. El segundo es una p´ agina de formulario con gran cantidad de celdas que pueden estar cumplimentadas o no. El tercero es un documento con pocos elementos estructurales y contenidos est´ aticos, pero con mucha informaci´ on variable. 1.2. Aproximaci´on cient´ıfica empleada El presente trabajo est´ a enmarcado en el campo del reconocimiento de formas y an´ alisis de im´ agenes, y se centra en el estudio y experimentaci´ on de una metodolog´ ıa de clasificaci´ on para la identificaci´ on autom´ atica supervisada de im´ agenes de documentos aplicando una t´ ecnica basada en la extracci´ on de caracter´ ısticas locales mediante un clasificador de los k-vecinos m´ as pr´ oximos. El trabajo est´ a acompa˜ nado de una experimentaci´ on exhaustiva para la identificaci´ on y optimizaci´ on de los par´ ametros m´ as relevantes y la evaluaci´ on de las prestaciones del sistema. El problema pr´ actico a resolver es la identificaci´ on de cualquier tipo de documento a partir de su imagen digital. Dada una serie de tipos de documentos conocidos (clases) representados por una o m´ as im´ agenes de referencia, el sistema de identificaci´ on autom´ atica debe identificar una nueva imagen de test asign´ andola a una de las clases conocidas, o rechaz´ andola si la imagen no pertenece a ninguna de ellas. Se pretende que el sistema sea capaz de identificar una imagen entre decenas o centenares de clases de documentos. Un objetivo espec´ ıfico es conseguir que el sistema presente ´ ındices de identificaci´ on satisfactorios frente a im´ agenes de test que contengan informaci´ on a˜ nadida respecto de la imagen de referencia de su clase. Este es el caso de los documentos cumplimentados con informaci´ on manuscrita, por ejemplo formularios, o tambi´ en rellenados con texto impreso, como ocurre, por ejemplo, con las facturas. Para la resoluci´ on del problema planteado se seguir´ a una aproximaci´ on inductiva. Esta se aplica a problemas de reconocimiento de formas para los que no se encuentra una explicaci´ on satisfactoria o tangible sobre cu´ ales son los pasos o mecanismos a seguir para alcanzar una soluci´ on. Se realizar´ a un aprendizaje supervisado, partiendo de un conjunto de entrenamiento etiquetado con cclases predeterminadas con el que se entrenar´ a un clasificador para que frente a cualquier observaci´ on de test (no vista anteriormente) se asigne la clase m´ as probable. Para la clasificaci´ on se emplear´ a una metodolog´ ıa estad´ ıstica (o geom´ etrica), basada en la teor´ ıa de la decisi´ on, donde un objeto est´ a representado por d Objetivos conseguidos y aportaciones 7 caracter´ ısticas y es tratado como un punto de un espacio vectorial d-dimensional. La clasificaci´ on de un objeto en una determinada clase se decide en funci´ on de su posici´ on en este espacio y de las distancias que lo separan de los otros puntos. Hay muchas reglas de clasificaci´ on. En este caso, el clasificador elegido es una combinaci´ on del de los k-vecinos m´ as pr´ oximos junto con un esquema de votaci´ on directa. Para su implementaci´ on se utilizar´ a una estructura kd-tree que permite realizar b´ usquedas de los k-vecinos m´ as pr´ oximos de forma r´ apida y aproximada en contraposici´ on a la b´ usqueda exhaustiva. M´ as concretamente, en el trabajo realizado, las clases ser´ an los diferentes tipos de documentos. As´ ı, cada clase ser´ a modelada utilizando un n´ umero de vectores de caracter´ ısticas locales extraidos de ventanas (o subim´ agenes) 2de dimensiones reducidas sobre una o m´ as im´ agenes de referencia de la clase. De entre todas las ventanas muestreadas, se filtrar´ an los vectores que representan una clase en el modelo y que a priori no aportan informaci´ on relevante y se estudiar´ a el tipo de caracter´ ısticas a utilizar. Posteriormente, las subim´ agenes que superen el filtro contribuir´ an al resultado final de la clasificaci´ on mediante el sistema de votaci´ on directa mencionado. A los vectores anteriores se les aplicar´ a una transformaci´ on basada en el An´alisis de Componentes Principales (PCA). Como resultado, en el espacio transformado, las componentes de los vectores quedar´ an ordenadas por varianza y se les aplicar´ a una reducci´ on de dimensionalidad seleccionando aquellas componentes que presenten mayor varianza. El conjunto de vectores resultante (o prototipos) conformar´ a el conjunto de entrenamiento o modelo. Finalmente, los prototipos se insertar´ an en una estructura kd-tree sobre la que se efectuar´ an las b´ usquedas de los k-vecinos m´ as pr´ oximos. La fase de test consistir´ a en muestrear la imagen de un documento extrayendo m´ ultiples subim´ agenes, obteniendo sus vectores de caracter´ ısticas de la misma forma en que se ha realizado en los vectores de entrenamiento, y clasific´ andolos. Una imagen de test ser´ a asignada a la clase que mayor probabilidad a posteriori presente empleando una regla de clasificaci´ on basada en un esquema de votaci´ on directa, y rechazada en el caso de no superar un l´ ımite m´ ınimo de confianza. Esta t´ ecnica basada en el uso de caracter´ ısticas locales ha sido aplicada con ´ exito a otros problemas como el reconocimiento de caras o el de matr´ ıculas de coche. Ante un problema de reconocimiento de formas, es m´ as sencillo plantear estrategias de decisi´ on efectivas en la clasificaci´ on cuando las variaciones intraclase son peque˜ nas y al mismo tiempo las variaciones interclase son grandes. En este sentido, la identificaci´ on autom´ atica de documentos presenta dificultades propias: por un lado, documentos de la misma clase pueden diferir significativamente respecto de la imagen de referencia ya que pueden contener diferentes cantidades de informaci´ on cumplimentada; por otra parte, documentos de diferentes tipos pueden llegar a ser muy similares, como por ejemplo, cuando tienen una estructura id´ entica o muy similar y difieren s´ olo en unos pocos caracteres (por ejemplo, plantillas de formularios que difieren s´ olo en el n´ umero de p´ agina o en la lengua que est´ an escritos). El uso de caracter´ ısticas locales puede contribuir a que las prestaciones del sistema planteado sean satisfactorias. 1.3. Objetivos conseguidos y aportaciones Creaci´ on de una base de datos de documentos obtenidos de distintas fuentes. Gran parte de ellos han sido escaneados y etiquetados a partir de documentos originales en papel. Adecuaci´ on de las im´ agenes de referencia mediante selecci´ on y boorado manual del contenido cumplimentado. 2Se emplear´ an indistintamente los t´ erminos “caracter´ ıstica local”, “representaci´ on local” o “subimagen” para hacer referencia al t´ ermino ingles “Local feature”. 8 Introducci´on Estudio bibliogr´ afico del estado del arte en identificaci´ on de documentos. Implementaci´ on de herramientas software para la experimentaci´ on sobre distintos par´ ametros relevantes en el proceso de identificaci´ on, incluyendo preprocesos digitales, filtros de texturas, extracci´ on de caracter´ ısticas, esquema de votaci´ on directa, b´ usqueda r´ apida en kd-trees, clasificaci´ on mediante k-vecinos m´as pr´oximos y an´ alisis de resultados. Adaptaci´ on del m´ etodo de votaci´ on directa para la clasificaci´ on de documentos basado en la extracci´ on de caracter´ ısticas locales. Realizaci´ on exhaustiva de experimentos para la optimizaci´ on de par´ ametros. Estudio de una medida de fiabilidad para el rechazo de documentos clasificados con baja confianza. Publicaciones: • [Arlandis 11] J. Arlandis, V. Castello-Fos, and J. C. Perez-Cortes, Filled-in document identification using local features and a direct voting scheme, In IbPRIA, In press, 2011. 1.4. Plan de la obra El presente trabajo se ha estructurado en 6 apartados. En esta primera parte de introducci´ on se han se˜ nalado las razones y objetivos que han llevado a la realizaci´ on de esta investigaci´ on. En el cap´ ıtulo 2 se introduce al lector en los conceptos te´ oricos b´ asicos dentro del campo del reconocimiento estad´ ıstico de formas, centr´ andose en las t´ ecnicas que se emplear´ an posteriormente en el trabajo. En el cap´ ıtulo 3 se hace un repaso al estado del arte dentro del campo de la identificaci´ on de documentos como parte espec´ ıfica de la clasificaci´ on de documentos. Se muestran las diferentes aportaciones que hasta el d´ ıa de hoy se han ido realizando y que sirven de punto de partida para este trabajo. En el cap´ ıtulo 4 se describe de forma detallada el m´ etodo empleado. Se explicar´ an y justificar´ an todas las decisiones tomadas en el dise˜ no del sistema, tanto en la estructura de ´ este como en la relevancia dada a los distintos par´ ametros empleados. En el cap´ ıtulo 5 se muestran los resultados de los experimentos realizados, centr´ andose sobre todo en la variaci´ on de los par´ ametros m´ as significativos que han sido objeto de estudio. Finalmente se mostrar´ an los resultados obtenidos con la combinaci´ on ´ optima de estos par´ ametros. Por ´ ultimo, el capitulo 6 resume las conclusiones alcanzadas tras la realizaci´ on de la investigaci´ on. Cap´ıtulo 2 Conceptos de reconocimiento estad´ıstico de formas En el presente cap´ ıtulo, se realiza una introducci´ on al campo del reconocimiento estad´ ıstico de formas, centr´ andose en las aproximaciones relacionadas m´ as directamente con el trabajo de investigaci´ on efectuado. A modo de introducci´ on, se presenta un modelo gen´ erico de sistema de reconocimiento de formas. Seguidamente se exponen las bases te´ oricas que sostienen la aproximaci´ on estad´ ıstica al reconocimiento de formas empleada en este trabajo, haciendo hincapi´ e en el m´ etodo de caracter´ ısticas locales y esquema de votaci´ on directa tratado en [Paredes 01]. Tambi´ en se describir´ a brevemente la t´ ecnica empleada de mejora de la eficiencia computacional de un clasificador estad´ ıstico basada en ´ arboles de b´ usqueda r´ apida y aproximada kd-tree . El ´ ultimo apartado se ha dedicado a describir la metodolog´ ıa utilizada para estimar el ratio de error del clasificador y una breve introducci´ on al concepto de rechazo. 2.1. Modelo gen´erico de sistema de reconocimiento de formas inductivo y supervisado Los sistemas de reconocimiento admiten distintas taxonom´ ıas. Desde el punto de vista del modo en que se aborda el problema se pueden considerar dos aproximaciones generales: la aproximaci´ on deductiva, que intenta abordar el problema de una forma racional, comprendiendo su naturaleza y buscando la manera de resolverlo a partir de unas ideas l´ ogicas; y la aproximaci´ on inductiva, que se usa en los casos en los que el enfoque deductivo no es aplicable, t´ ıpicamente se utiliza en casos en los que el ser humano es capaz de reconocer f´ acilmente determinadas formas, pero sin tener un conocimiento l´ ogico de c´ omo se hace. Este ´ ultimo enfoque ser´ a el utilizado el presente trabajo. La aproximaci´ on inductiva lleva asociado el concepto de aprendizaje, que puede ser supervisado o no supervisado. El aprendizaje no supervisado se aplica en los casos en los que no se conocen a priori las clases en las que est´ a dividido el conjunto de prototipos. En este trabajo se aplicar´ a el aprendizaje supervisado, ya que, como se ver´ a m´ as adelante, se parte de un conjunto de datos previamente etiquetado en un n´ umero conocido de clases. Un sistema de reconocimiento opera funcionalmente en dos modos: entrenamiento oaprendizaje ytest oclasificaci´on. No obstante, la implementaci´ on de un sistema de reconocimiento inductivo supervisado debe pasar por un total de cinco fases bien definidas: Fase de dise˜no An´ alisis del problema. Elecci´ on de la metodolog´ ıa, t´ ecnicas candidatas y fuentes de 16 Conceptos de reconocimiento estad´ıstico de formas una regla de decisi´ on da lugar a una partici´ on del espacio de caracter´ ısticas en cregiones o clases. Las fronteras que separan estas regiones se denominan fronteras de decisi´ on. Consideramos en primer lugar la posibilidad de que no tengamos informaci´ on de las caracter´ ısticas de la muestra a clasificar. La probabilidad de que una muestra cualquiera, de la cual no tenemos ninguna informaci´ on, pertenezca a la clase wyes lo que conocemos como probabilidad a priori P(wy). Este valor est´ a asociado a cada clase y no depende de la muestra en concreto. En general, es relativamente f´ acil y seguro estimar esta probabilidad por simple conteo si disponemos de suficiente cantidad de muestras de identidad conocida extra´ ıdas del ´ ambito natural de una manera uniforme y aleatoria. En el supuesto de que no fuera posible conocer ning´ un dato del objeto, la decisi´ on m´ as razonable –es decir, aquella que minimizar´ ıa el riesgo de error–, ser´ ıa asignarle la clase con probabilidad a priori m´ as alta: P(wi)> P(wj),1≤i, j ≤c;i6=j Esta regla de decisi´ on ciega es, indudablemente, poco ´ util y supone no hacer uso de ninguna caracter´ ıstica de los objetos que pueda contribuir a una clasificaci´ on m´ as fiable. La informaci´ on que las caracter´ ısticas aportan tiene que emplearse para maximizar la fiabilidad de la clasificaci´ on. En este sentido, resultar´ ıa muy ´ util disponer de un mecanismo que nos proporcionara, a partir de estas observaciones, informaci´ on sobre la probabilidad a posteriori, tambi´ en llamada probabilidad condicional P(wy|x)que un objeto xpertenezca a la clase wy. La manera de obtenerla es justamente la caracter´ ıstica diferenciadora de los distintos m´ etodos de clasificaci´ on. Una vez obtenida la probabilidad a posteriori para cada clase, se escoger´ a aquella clase que presente el mayor valor P(wi|x)> P(wj|x),1≤i, j ≤c, i 6=j⇒x∈wi(2.1) Este criterio constituye la regla de decisi´ on de Bayes de m´ ınimo error y en ´ esta se basan de una u otra manera la pr´ actica totalidad de los m´ etodos de clasificaci´ on de tipo estad´ ıstico. C´ omo hemos visto, el conocimiento de la probabilidad a posteriori es necesario para la aplicaci´ on de las reglas de clasificaci´ on comentadas. Una buena parte de los m´ etodos existentes hoy por hoy no permiten calcular directamente este valor pero, en cambio, son capaces de estimar a partir del conjunto de entrenamiento las funciones de densidad de probabilidad de cada clase p(x|wy)en el espacio de representaci´ on de las muestras. Con la ayuda de la f´ ormula de Bayes, podemos obtener la probabilidad a posteriori que la muestra xpertenezca a la clase wysi conocemos, para esta clase, el valor de la funci´ on de densidad en este punto: P(wi|x) = p(x|wi)P(wi) p(x), y, ya que el denominador no depende de la clase, la regla de decisi´ on de Bayes se puede reescribir como: p(x|wi)P(wi)> p(x|wj)P(wj),1≤i, j ≤c, i 6=j⇒x∈wi Como se ha dicho anteriormente, las posibilidades a priori son conceptualmente f´ aciles de estimar, no as´ ı las funciones de densidad. Se distingue entre aquellos procedimientos que no hacen uso de ning´ un conocimiento respecto de la naturaleza de las funciones de densidad a estimar y aquellos que requieren asumir que estas responden a una determinada distribuci´ on especificada param´ etricamente. Los primeros son llamados m´ etodos no param´ etricos y los ´ ultimos param´ etricos. Hay adem´ as un conjunto de t´ ecnicas conocidas como funciones discriminantes en las cuales se asume una forma param´ etrica, no para las funciones de probabilidad, sino para las superficies de decisi´ on. Esquema de votaci´on directa basado en los k-vecinos m´as pr´oximos 17 2.3. Esquema de votaci´on directa basado en los k-vecinos m´as pr´oximos En los sistemas tradicionales de clasificaci´ on basados en el paradigma estad´ ıstico, cada clase se representa por un vector de caracter´ ısticas, y se aplica una regla de discriminaci´ on para clasificar un vector de test representado tambi´ en por un vector de caracter´ ısticas. En este trabajo, se utilizar´ a una t´ ecnica de clasificaci´ on basada en caracter´ ısticas locales, es decir cada documento (tanto de entrenamiento como de test) estar´ a representado por un conjunto de vectores de caracter´ ısticas locales. Cada uno de estos vectores puede clasificarse dentro de una clase diferente, y ser´ a un sistema de votaci´ on directa el que decidir´ a finalmente la clase asignada al documento de test. La t´ ecnica de extracci´ on de caracter´ ısticas consiste en representar un documento con un conjunto de regiones de la imagen. Cada una de estas regiones est´ a codificada en forma de vector, al cual se le exigir´ a que cumpla unas determinadas condiciones para que sea realmente representativo utilizando distintos filtros (varianza, entrop´ ıa, etc.). Una regi´ on de la imagen de tama˜ no v×westar´ a representada por un vector de v×wdimensiones, cada una de las cuales contiene el valor de intensidad de un p´ ıxel de la regi´ on. Con objeto de reducir el coste computacional se aplicar´ a una reducci´ on de dimensionalidad a edimensiones utilizando el m´ etodo PCA (Principal Component Analysis). La extracci´ on de caracter´ ısticas se puede formalizar de la manera siguiente: Sea I={I1, . . . , In} un conjunto de entrenamiento de nim´ agenes que representan dclases diferentes. Para cada imagen Ii, se obtienen mivectores de caracter´ ısticas que son proyectados con el m´ etodo PCA a un espacio de e dimensiones. Sea Xi={xi1, . . . , ximi}, el conjunto de vectores e-dimensionales asociado con la imagen Ii, y sea T=Sn i=1 Xiel conjunto global de vectores. Cada vector xillevar´ a asociada una etiqueta de clase ωi∈ {ω1, . . . , ωd}que es la etiqueta de clase de la imagen Ii. Obviamente, todas las im´ agenes pertenecientes a la misma clase de documentos tendr´ an la misma etiqueta. El procedimiento de clasificaci´ on utilizado est´ a estrechamente relacionado con una familia de t´ ecnicas referidas de forma habitual como “sistemas de votaci´on directa” [Mohr 97]. De hecho, est´ a basado en la aplicaci´ on de la conocida regla de los k-NN (kvecinos m´ as pr´ oximos) al conjunto de vectores que representan una imagen de prueba, utilizando el vector global de conjunto T como conjunto de referencia o conjunto de prototipos. M´ as formalmente, podemos presentar la t´ ecnica de clasificaci´ on en el marco estad´ ıstico de las “combinaciones de clasificadores” [Kittler 98]. Sea Yuna imagen de test. Siguiendo el marco probabil´ ıstico convencional, Ypuede ser perfectamente clasificada en la clase ˆw, que tiene la m´ axima probabilidad a posteriori: ˆw= arg max 1≤j≤d P(ωj|Y)(2.2) Aplicando el proceso de extracci´ on basado en caracter´ ısticas locales descrito anteriormente, la imagen Yestar´ a representada por un conjunto de vectores mY={y1, . . . , ymY}. Se puede ver el clasificador 2.2 como una combinaci´ on de mYclasificadores, uno para cada vector de caracter´ ısticas de Y. Asumiendo la independencia entre los vectores yi, se puede escribir P(ωj|Y)como el producto de las probabilidades a posteriori asociadas a cada vector de caracter´ ısticas, y 2.2 se convierte en: ˆw= arg max 1≤j≤d mY Y i=1 P(ωj|yi) = arg max 1≤j≤d mY X i=1 log P(ωj|yi)(2.3) Esto es conocido comunmente como la “regla del producto” para combinaciones de clasificadores. Un inconveniente importante de esta regla es que las probabilidades muy peque˜ nas tienden a dominar el 18 Conceptos de reconocimiento estad´ıstico de formas resultado de la combinaci´ on, provocando pobres estimaciones de P(ωj|Y)y un bajo rendimiento de la clasificaci´ on. Para aliviar estos problemas se suele utilizar la llamada “regla de la suma” [Paredes 01]. Esta regla se puede ver como una forma de suavizar el efecto de las probabilidades peque˜ nas. En las situaciones reales, la mayor´ ıa de las probabilidades a posteriori P(ωj|Y)suelen tener valores cercanos a 1 o cercanos a 0. Aquellos cercanos a 1 se pueden aproximar linealmente como: log P(ωj|yi)≈P(ωj|yi)−1 Obviamente, para aquellas probabilidades cercanas a 0, esta aproximaci´ on lineal no es muy adecuada, produciendo valores significativamente mayores que los correctos. Sin embargo, el error introducido realmente produce un efecto de suavizado beneficioso que tiende a compensar la pobre estimaci´ on de dichas peque˜ nas probabilidades. Con todo esto, utilizando la aproximaci´ on lineal, la ecuaci´ on 2.2 se puede reescribir como: ˆw= arg max 1≤j≤d mY X i=1 P(ωj|yi)(2.4) que corresponde a la mencionada “regla de la suma” para combinaciones de clasificadores. Cabe destacar que los vectores de caracter´ ısticas que provienen de subim´ agenes con contenido cumplimentado, o con cualquier otro tipo de ruido, introducen al clasificador vectores “ruidosos” que ser´ an generalmente estimados con bajas probabilidades. La “regla de la suma” produce un efecto de suavizado de estas bajas probabilidades. Es m´ as, los vectores “ruidosos” realmente tendr´ an un efecto beneficioso ya que los vectores mal clasificados tendr´ an tendencia a distribuirse entre diferentes clases. En el caso que nos ocupa, las probabilidades a posteriori se estiman directamente con la regla de los k-vecinos m´ as pr´ oximos. Sea kij el n´ umero de vecinos de yipertenecientes a la clase ωj. Asumiendo que el n´ umero medio de vectores que representan a todas las im´ agenes de entrenamiento de cada clase es m´ as o menos constante, una buena estimaci´ on de P(ωj|yi)es: ˆ P(ωj|yi) = kij k, y, usando esta estimaci´ on en 2.4, nuestra regla de clasificaci´ on se convierte en: ˆw= arg max 1≤j≤d my X i=1 kij (2.5) Esto es, se selecciona la clase ˆwcon el mayor n´ umero de “votos” acumulados sobre todos los vectores pertenecientes a la imagen de test. De esta forma se justifica el por qu´ e estas t´ ecnicas son conocidas como “sistemas de votaci´on”. En [Paredes 01] se describe un clasificador similar muy utilizado para biometr´ ıa facial a partir de un sistema de votaci´ on directa basado en k-NN. B´usqueda r´apida en kd-trees 19 2.4. B´usqueda r´apida en kd-trees El kd-tree es un ´ arbol cl´ asico entre los que se utilizan para la b´ usqueda del vecino m´ as cercano. El nombre kd-tree viene de k-dimensional tree, en el que la krepresenta la dimensi´ on de los datos del espacio de representaci´ on. El kd-tree es un ´ arbol binario que contiene en cada nodo intermedio informaci´ on acerca de una coordenada que divide en dos el conjunto de datos del sub´ arbol correspondiente al nodo, y en las hojas contiene pu˜ nados (buckets) de prototipos. Durante la fase de clasificaci´ on se recorre el ´ arbol siguiendo un esquema de ramificaci´ on y poda para encontrar el vecino m´ as cercano. Tanto en el preproceso (construcci´ on del ´ arbol) como en la clasificaci´ on propiamente dicha se utilizan las coordenadas de los prototipos, por lo que esta estructura de datos y el algoritmo de b´ usqueda necesitan un espacio de representaci´ on con vectores (espacio de vectores). Aunque se han desarrollado muchas mejoras y optimizaciones, es el algoritmo de referencia cuando se utilizan distancias eucl´ ıdeas. Construcci´on del kd-tree La idea principal del algoritmo para la construcci´ on del kd-tree a partir de un conjunto de prototipos P es la siguiente: encontrar un hiperplano que divida el conjunto P en dos subconjuntos y proceder recursivamente con los subconjuntos. El principal aspecto a resolver es la elecci´ on del hiperplano y de la coordenada que va a servir para dirigir la b´ usqueda a un lado u otro del hiperplano, la coordenada discriminante. Para intentar conseguir que cualquier prototipo tenga la misma probabilidad de estar a un lado o a otro del hiperplano y por tanto que el ´ arbol resulte lo m´ as equilibrado posible, se suele elegir el hiperplano de forma que se sit´ ue en la mediana de los valores de la coordenada discriminante. Adem´ as, la coordenada discriminante debe ser aquella que tenga una mayor amplitud, es decir, aquella para la que la diferencia entre la coordenada m´ ınima y m´ axima sea la mayor en valor absoluto. El ´ arbol se construye de la siguiente forma: en cada nodo, que representa un conjunto de prototipos (el nodo ra´ ız representa a todo el conjunto de entrenamiento), se elige la coordenada discriminante y se obtiene la mediana de los valores de dicha coordenada en los prototipos del conjunto; a continuaci´ on, se divide dicho conjunto en dos subconjuntos utilizando la mediana, situando en un subconjunto aquellos prototipos para los que el valor de la coordenada discriminante sea menor o igual que el de la mediana, y en el otro subconjunto los prototipos cuya coordenada discriminante sea mayor que la mediana. A continuaci´ on, se crean recursivamente los ´ arboles asociados a cada uno de los subconjuntos. El proceso termina cuando el tama˜ no del conjunto de prototipos es menor o igual que el valor fijado como tama˜ no de un pu˜ nado, y en este caso el nodo ser´ ıa una hoja. B´usqueda en el kd-tree El proceso de b´ usqueda en el kd-tree es recursivo: dada una muestra desconocida x, en un nodo cualquiera del ´ arbol (que no sea una hoja) se compara la coordenada de xque es discriminante para ese nodo (c) con el valor de corte v(la mediana de las coordenadas discriminantes), y se procede en la direcci´ on m´ as cercana seg´ un esa coordenada. Si x[c] + dnn ≤v(donde dnn es la distancia al vecino m´ as cercano hasta el momento), el hijo derecho de ese nodo no puede contener al vecino m´ as cercano y por tanto no es necesario buscarlo en ese nodo; de forma similar, si x[c]−dnn ≥vel hijo izquierdo no es necesario visitarlo. Si el nodo es una hoja, la muestra se compara con todos los prototipos contenidos en ella. 20 Conceptos de reconocimiento estad´ıstico de formas 2.5. Recuperaci´on de documentos Uno campos de estudio con gran actividad en la actualidad es el de la recuperaci´ on de informaci´ on odocument retrieval. Este auge surge con las nuevas tecnolog´ ıas y la necesidad de analizar y medir las prestaciones de los sistemas de almacenamiento masivo de documentos [D´ ıaz 03]. La recuperaci´ on de informaci´ on es el proceso que permite obtener, de un fondo documental, los documentos adecuados a una determinada demanda de informaci´ on por parte de un usuario. Este proceso engloba el conjunto de acciones referidas a la identificaci´ on, selecci´ on y acceso a los recursos de informaci´ on necesarios para resolver el problema del usuario. Cuando se produce una necesidad informativa, mediante una estrategia de b´ usqueda m´ as o menos complicada, interrogamos al conjunto de documentos, con el fin de obtener una respuesta que satisfaga la demanda. Para saber en qu´ e medida la respuesta es satisfactoria, es necesario evaluar los resultados. Desde este punto de vista, la evaluaci´ on es la etapa final de la creaci´ on de un sistema. La importancia de la evaluaci´ on en recuperaci´ on de informaci´ on est´ a muy ligada a la fase de investigaci´ on ya que sin unas medidas eficaces y estandarizadas, y colecciones experimentales adecuadas para este fin, no se pueden hacer evaluaciones, ni lo que es m´ as importante, no se pueden comparar los sistemas de un modo fiable. Los documentos pueden ser recuperados o rechazados al establecer la comparaci´ on entre la pregunta y la base de datos. El conjunto de documentos recuperados se divide, salvo en los sistemas perfectos, en dos grupos: documentos relevantes recuperados, es decir aquellos que se han recuperados correctamente y los no relevantes, recuperados err´ oneamente que provocan ruido en la salida. Los documentos no recuperados, que a su vez se dividen en los relevantes, rechazados por el sistema de manera err´ onea y los no relevantes, rechazados de manera correcta por el sistema. Esto mismo lo podemos ver en la figura 2.5. Para encontrar un paralelismo entre la recuperaci´ on de informaci´ on y la identificaci´ on de documentos tratada en este trabajo es necesario introducir el concepto de rechazo en la identificaci´ on de documentos. Un clasificador debe ser capaz de detectar documentos de clases para las que no ha sido entrenado y rechazarlos. Con este concepto, la tarea de clasificaci´ on puede ser vista como recuperaci´ on de informaci´ on: los documentos de clases conocidas (relevantes desde el punto de vista de recuperaci´ on de informaci´ on) deber´ an ser clasificados (recuperados) correctamente y el resto de documentos de clases desconocidas (no relevantes) deben ser rechazados. Desde este punto de vista, es posible utilizar las medidas estandarizadas ampliamente utilizadas en el campo de recuperaci´ on de informaci´ on para evaluar los resultados de un clasificador. A continuaci´ on se detallan algunas de estas medidas. 2.5.1. Precisi´on y exhaustividad La precisi´ on es la proporci´ on de material recuperado realmente relevante, del total de los documentos recuperados. Es conocida tambi´ en como factor de pertinencia o ratio de aceptaci´ on. El resultado de esta operaci´ on est´ a entre 0 y 1. As´ ı, la recuperaci´ on perfecta es en la que ´ unicamente se recuperan los documentos relevantes y por lo tanto tiene un valor de 1. Esta medida est´ a relacionada con dos conceptos, el de ruido y el de silencio informativo. De este modo, cuanto m´ as se acerque el valor de la precisi´ on a 0, mayor ser´ a el n´ umero de documentos recuperados que no le sirvan al usuario y por lo tanto el ruido que encontrar´ a ser´ a mayor. La f´ ormula del ratio de precisi´ on es: Recuperaci´on de documentos 21 Figura 2.5: Esquema de recuperaci´ on de documentos. precision =documentos relevantes recuperados documentos recuperados La exhaustividad es el otro concepto m´ as utilizado en la evaluaci´ on de los sistemas de recuperaci´ on. Muchos autores, por influencia del t´ ermino ingl´ es la denominan “recall” o“rellamada”. Es la proporci´ on de material relevante recuperado, del total de los documentos que son relevantes en la base de datos, independientemente de que ´ estos, se recuperen o no. La exhaustividad es inversamente proporcional a la precisi´ on y se calcula de la siguiente manera: exhaustividad =documentos relevantes recuperados documentos relevantes Si el resultado de este c´ alculo tiene como valor 1, tendremos la exhaustividad m´ axima, ya que hemos encontrado todo lo relevante que hab´ ıa en la base de datos, por lo tanto no tendremos ni ruido ni silencio informativo: la recuperaci´ on ser´ a perfecta. Para utilizar estos t´ erminos en la identificaci´ on de documentos ser´ a necesario definir un ´ ındice de fiabilidad en la clasificaci´ on que permita ordenar los documentos de m´ as a menos fiables. El ´ ındice de fiabilidad es una forma de cuantificar la relevancia de los documentos y debe representar el nivel de seguridad que tiene un clasificador de que cierto documento pertenezca a la clase en que ha sido identificado. Una medida ampliamente utilizada que aporta un buen indicador de la calidad de un clasificador es el ´ ındice de exhaustividad para un determinado valor de precisi´ on, “recall at x% precision”, que indica el ratio de exhaustividad que se obtiene con un ´ ındice de fiabilidad predeterminado que permite un x% de precisi´ on. Habitualmente se utiliza el “recall at 100 % precision”. 22 Conceptos de reconocimiento estad´ıstico de formas Cap´ıtulo 3 Estado del arte en identificaci´on de documentos En la clasificaci´ on de documentos, tradicionalmente, se ha dedicado una significativa cantidad de esfuerzo a desarrollar aproximaciones basadas en agrupar documentos con un cierto grado de similitud sem´ antica como pertenecientes a una misma clase o categor´ ıa. Sin embargo, en algunas aplicaciones, como las relacionadas con la digitalizaci´ on y extracci´ on de datos, entre otras, las clases deben ser definidas para representar tipos particulares de documentos. En este caso, la tarea es comunmente conocida como “identificaci´ on de documentos”, y los m´ etodos de agrupamiento o clustering no son adecuados. En la mayor parte de estas aplicaciones, la identificaci´ on de la imagen de un documento es requerida en primera instancia, antes de cualquier otro proceso espec´ ıfico. Se han utilizado muchos tipos de caracter´ ısticas para la clasificaci´ on de im´ agenes de documentos. Est´ an relacionados con el dise˜ no de los documentos, primitivas de texturas, reconocimiento de caracteres y cadenas, c´ odigos de silueta, detecci´ on de marcos, visual salient features, transformaciones globales y proyecciones de im´ agenes, o la detecci´ on de las estructuras sem´ anticas de los bloques. En el ´ ambito de recuperaci´ on de la informaci´ on, cuando no existe contenido cumplimentado, es decir, contenido que puede y suele variar entre diferentes documentos de la misma clase , la identificaci´ on de documentos puede ser visto como una tarea de detecci´ on de duplicados [Doermann 98]. En este caso, los planteamientos tienen que hacer frente a las diferencias entre las instancias de documentos, como la resoluci´ on, sesgo, distorsiones y calidad de imagen, velocidad y robustez, as´ ı como, al manejo de bases de datos muy grandes. La mayor´ ıa de trabajos que tratan con documentos cumplimentados se restringen a la identificaci´ on de formularios. Muchos de ellos se basan en el an´ alisis de estructuras globales y locales [Fan 01], [Ohtera 04], [Mandal 05]. Las caracter´ ısticas estructurales se limitan generalmente a documentos que contienen marcos, celdas, lineas, bloques o elementos similares, y no son de ayuda cuando diferentes tipos de documentos tienen estructuras similares. Otros trabajos se basan en el uso de c´ odigos de car´ acter o de cadena para lograr identificar los documentos [Sako 03], as´ ı como, en computar las densidades de p´ ıxeles dentro de algunas regiones de la imagen [Heroux 98]. Dentro de los documentos tipo formulario existen aplicaciones espec´ ıficas encaminadas a la identificaci´ on de cupones [Nagasaki 06], recibos bancarios [Ogata 03] o documentos administrativos, por ejemplo [Ting 96]. El prop´ osito de este trabajo es hacer frente a la tarea de clasificaci´ on de documentos con total independencia de los dise˜ nos, distribuciones, tama˜ nos y cantidad de contenido rellenado de una manera eficiente. Por lo tanto, la aproximaci´ ones anteriores pueden no ser apropiadas, bien porque utilizan caracter´ ısticas globales, se centran en tipos de documentos espec´ ıficos, o no son capaces de manejar 24 Estado del arte en identificaci´on de documentos documentos con contenido cumplimentado. As´ ı, son escasos los trabajos encontrados en la literatura referidos a la identificaci´ on de im´ agenes de documentos cumplimentados. Algunos trabajos m´ as directamente relacionados con este proyecto, son los presentados por Parker [Parker 10] and Sarkar [Sarkar 06], [Sarkar 10]. Sarkar [Sarkar 06] presenta una metodolog´ ıa para seleccionar y clasificar puntos de anclaje o “anchor points” a partir de im´ agenes de documentos. La selecci´ on de anchor points est´ a basada en el uso de caracter´ ısticas destacadas rectangulares de Viola&Jones en el canal de luminancia. Para cada clase de documento, se obtiene la distribuci´ on de probabilidad de la lista de caracter´ ısticas locales (incluyendo las coordenadas globales de posici´ on) mediante un modelo de Independencia Condicional Latente (LCI). Se clasifica una imagen emparejando su lista de caracter´ ısticas con modelos generativos espec´ ıficos de la clase por el criterio de m´ axima verosimilitud, y se asigna a la clase cuya distribuci´ on emp´ ırica est´ a m´ as cercana, de acuerdo con el valor de KL-divergencia de Kullback-Leibler. Esta correspondencia es bien conocida en la comunidad de clasificaci´ on y recuperaci´ on de textos, donde las observaciones son listas de palabras de longitud variable. Recientemente, Sarkar [Sarkar 10] propone una metodolog´ ıa completa para seleccionar anchor points basados en subim´ agenes elegidas de forma aleatoria y aplicando sucesivos refinamientos expandiendo y ordenando los puntos candidatos utilizando dos medidas de calidad. Parker [Parker 10] propone y compara tres m´ etodos para la selecci´ on de anchor points. El primero est´ a basado en dos criterios: la “acci´ on gr´ afica” y la minimizaci´ on de la distancia intra-clase. Los otros dos m´ etodos intentan la selecci´ on de anchor points que maximicen la funci´ on de KL-divergencia, una medida de separaci´ on de dos distribuciones de probabilidad; uno de las distancias entre anchor points dentro de una muestra dada de una clase de documento, y el otro de las distancias de estos anchor points a los documentos de distintas clases. Parker afirma que el rendimiento del sistema propuesto de identificaci´ on de formularios puede ser estimado de manera te´ orica mediante la KL-divergencia. El autor muestra los resultados de los experimentos de los tres m´ etodos utilizando una base de datos personalizada de formularios extra´ ıdos del IRS, donde s´ olo un tipo de documento conten´ ıa datos rellenados y se utilizaron diez formularios para entrenar el sistema. La principal conclusi´ on de los experimentos es que el uso de la informaci´ on inter-clase para seleccionar los puntos de anclaje de una clase mejora el rendimiento del sistema (estimado mediante la KL-divergencia). Este m´ etodo implica el uso de varios documentos de cada clase para entrenar el sistema, y puede ser necesario efectuar un elevado n´ umero de operaciones de correlaci´ on para que la selecci´ on de anchor points sea robusta frente a las traslaciones de la imagen, algo necesario en la fase de producci´ on. Cap´ıtulo 4 Preproceso, extracci´on y selecci´on de caracter´ısticas La primera tarea a realizar en un trabajo de identificaci´ on de documentos es, obviamente, la digitalizaci´ on de estos mediante un esc´ aner. A partir de este momento, se dispone de una imagen digital para cada documento escaneado. T´ ıpicamente, la imagen de un documento se compone de un fondo de p´ ıxeles blancos y p´ ıxeles negros en primer plano, aunque se pueden encontrar otras combinaciones, como documentos en escala de grises, color o combinaciones heterog´ eneas de fondos y primeros planos. El primer plano de un documento se compone sobre todo de texto (en muchos casos con diferentes aspectos como los tipos de letra, estilos de escritura, letras may´ usculas, texto en negrita, diferentes tama˜ nos, etc), aunque otros objetos como im´ agenes, gr´ aficos, logotipos, o marcos son tambi´ en frecuentes. Por lo general, las ´ areas de texto tambi´ en incluyen patrones de fondo, y un patr´ on de fondo tambi´ en pueden estar presente en la mayor´ ıa de la superficie de un documento. En este cap´ ıtulo, se realizar´ a un recorrido por los principales puntos en los que se ha basado este proyecto. Se justificar´ a el empleo de varias funciones de preproceso de im´ agenes con el objeto de mejorar el rendimiento del sistema, tanto en velocidad de computaci´ on como en tasa de aciertos y se describen las t´ ecnicas empleadas para la extracci´ on de caracter´ ısticas de las im´ agenes. As´ ı, se realizar´ a un submuestreo particularizado, que permite reducir el n´ umero de caracter´ ısticas a extraer de cada imagen disminuyendo el tiempo de proceso en la fase de test; los filtros de varianza y diferencia de entrop´ ıa, con los que la selecci´ on de caracter´ ısticas locales es m´ as efectiva ya que se descartan aquellas que aportan menos informaci´ on a la clasificaci´ on; la reducci´ on de dimensionalidad, que permite el algoritmo PCA proyectando los vectores de caracter´ ısticas en un espacio m´ as disccriminativo que el original y permitiendo prescindir de un n´ umero de dimensiones sin perdida de informaci´ on discriminativa; o el uso de las coordenadas de posici´ on de cada ventana como caracter´ ısticas globales del documento. La secuencia de operaciones que se aplicar´ an a las im´ agenes de documentos antes del proceso de clasificaci´ on es la siguiente: 1. Conversi´ on a PGM 2. Correcci´ on de la rotaci´ on 3. Normalizado a tama˜ no equivalente a un A4 escaneado a 300 dpi 4. Suavizado y umbralizado de las im´ agenes 32 Preproceso, extracci´on y selecci´on de caracter´ısticas f11 =− Ng−1 X i=0 Px−y(i) log Px−y(i) siendo Px−y(k) = Ng X i=1 Ng X j=1 P(i, j) con k={0,1, . . . , Ng−1} |i−j|=k P(i, j)es la probabilidad (o frecuencia) de la entrada (i, j)-´ esima de la matriz de co-ocurrencia Nges el n´ umero de posibles tonos de gris de la imagen Filtro de varianza Los formularios y documentos administrativos son normalmente documentos con gran parte de su superficie de color blanco. Al extraer las caracter´ ısticas locales de estos documentos es importante que ´ estas contengan informaci´ on relevante, y por tanto, conviene descartar las caracter´ ısticas que no aportan informaci´ on espec´ ıfica del documento. En particular, conviene descartar los vectores que se forman a partir de regiones uniformes (todos los p´ ıxeles de la misma intensidad o muy similar). Para ello, se puede establecer un filtro basado en la varianza de los vectores, descartando aquellos que no superen un determinado umbral, o seleccionando los nmejores de una lista ordenada por varianza. La varianza de un vector se define como la varianza estad´ ıstica de sus componentes, es decir, dado un vector de ndimensiones ~x = (x1, ..., xn)su varianza σ2viene determinada por la f´ ormula σ2= n X i=1 (xi−µ)2 n donde µes la media aritm´ etica de las componentes del vector ~x. El m´ etodo empleado en este trabajo consistir´ a en combinar las dos propuestas mencionadas anteriormente, es decir, exigir a todos los vectores de caracter´ ısticas extra´ ıdos un valor m´ ınimo de varianza σ2 min, y entre ellos, elegir s´ olamente los nmejores (si hay suficientes), descartando el resto como representantes del documento. En los experimentos realizados se tratar´ a de ajustar los dos valores planteados σ2 min yncon el prop´ osito de conseguir la mejor tasa de acierto posible. Cabe destacar un par de observaciones acerca del filtrado de catacter´ ısticas locales: Extracci´on de caracter´ısticas 33 Figura 4.6: Ejemplo de la problem´ atica del submuestreo. Dos ventanas de un mismo documento extra´ ıdas en las fases de entrenamiento y test no coinciden en ninguna componente del vector pese a ocupar parcialmente la misma zona de la imagen. Dado que a las im´ agenes de entrenamiento se les ha eliminado la informaci´ on cumplimentada, los vectores seleccionados contendr´ an siempre informaci´ on de la parte est´ atica del documento. En cambio, las im´ agenes de documentos de test no han sido limpiadas, de modo que la selecci´ on puede incluir muchos vectores de la parte cumplimentada del documento. Para compensar este problema, en los documentos de test se extraer´ a un n´ umero de caracter´ ısticas superior al extra´ ıdo en los documentos de entrenamiento. Hay que tener cuidado con las ventanas de baja varianza. Si no se establecen bien los filtros, y alguna clase de documentos contiene vectores de baja varianza en sus prototipos, pueden actuar como sumidero en la clasificaci´ on de cualquier documento de test que tambi´ en incluya este tipo de caracter´ ısticas. Esto provocar´ ıa una disminuci´ on considerable en la tasa de acierto del clasificador. 4.2.2. Submuestreo y orla de vecindad Una estrategia que puede ser aplicada para mejorar los tiempos de proceso es el subsampling o submuestreo, aplicable tanto para la obtenci´ on de los prototipos como para la obtenci´ on de los vectores de test. En un procedimiento sin submuestreo se extraen todas las caracter´ ısticas locales asociadas a cada p´ ıxel del documento. Esto conlleva tratar con un n´ umero muy elevado de caracter´ ısticas y gran cantidad de informaci´ on redundante. Para evitar este derroche de recursos se puede establecer una distancia de separaci´ on entre caracter´ ısticas locales conocida como paso de submuestreo, de forma que los vectores seleccionados aporten informaci´ on al proceso de clasificaci´ on. Es posible establecer pasos de submuestreo distintos en los dos ejes del documento. Debe ser tenida en cuenta la relaci´ on entre el paso de submuestreo y la forma o tama˜ no de la ventana de caracter´ ısticas locales. Esta estrategia tiene un serio inconveniente cuando no existe solapamiento entre los vectores de entrenamiento y test. Si un documento de test es escaneado con un peque˜ no desplazamiento inferior al paso de submuestreo respecto del documento de referencia utilizado en el entrenamiento, las ventanas extraidas en los dos documentos jam´ as coincidir´ an y la clasificaci´ on fallar´ a. En la figura 4.6 se muestra un ejemplo extremo de lo que puede suceder con dos vectores casi id´ enticos tras un desplazamiento de un p´ ıxel. Para evitar el problema de “no solapamiento” de prototipos y vectores de test se ha empleado la siguiente estrategia: una vez extraidas las caracter´ ısticas de los documentos de entrenamiento y reducido el conjunto de estas tras aplicar los filtros de diferencia de entrop´ ıa (4.2.1) y de varianza (4.2.1) se a˜ naden al conjunto los vectores de caracter´ ısticas asociados a los p´ ıxeles vecinos de cada una de ellas. A este conjunto de vecinos se le llamar´ a “orla de vecindad”. 34 Preproceso, extracci´on y selecci´on de caracter´ısticas De esta forma se garantiza que si un vector extraido en la fase de test es relevante para la clasificaci´ on de un documento, su correspondiente prototipo en el documento habr´ a sido incluido en el conjunto de entrenamiento y la clasificaci´ on correcta ser´ a mucho m´ as probable. Asimismo, el tama˜ no de la ventana de vecinos debe guardar una relaci´ on directa con el tama˜ no de submuestreo empleado en el procedimiento. Al incluir los vectores de la orla de vecindad en el conjunto de datos de entrenamiento se empeora ligeramente el tiempo de entrenamiento del sistema. Por contra, el coste computacional de la fase de test disminuye dr´ asticamente con el empleo del submuestreo, adem´ as, no se ve afectado de manera significativa por el aumento del n´ umero de prototipos ya que la b´ usqueda en kd-tree tiene un coste logar´ ıtmico. 4.2.3. An´alisis de componentes principales El an´ alisis de componentes principales (PCA) pretende reducir la dimensionalidad del espacio de representaci´ on de los objetos a partir de proyecciones lineales. Las proyecciones son elegidas de forma que la varianza total de los objetos en la nueva representaci´ on sea m´ axima. Es un m´ etodo no supervisado, ya que no se tiene en cuenta la clase de los objetos. La transformaci´ on PCA consiste en lo siguiente: Sean Nobjetos representados por los vectores de caracter´ ısticas {x1, x2, ..., xN}tales que xi∈Rn. Se considera una transformaci´ on lineal que transforme el espacio original n-dimensional en un espacio m-dimensional, con m<n. Las nuevas representaciones yise calculan como sigue: yi=WTxii= 1,2, ..., N siendo las mcolumnas de W∈Rn×mortonormales. Sea Scla matriz de covarianzas de los vectores de caracter´ ısticas originales definida como: Sc=1 N N X i=1 (xi−µ) (xi−µ)T donde µ∈Rnrepresenta la media de los vectores de caracter´ ısticas originales. Sctiene dimensi´ on n×n y es sim´ etrica, por tanto, tendr´ anvectores propios {φ1, φ2,...φn}ynvalores propios {λ1, λ2,...λn} que cumplen la relaci´ on: ScΦ = ΦΛ (4.1) donde, Φes la matriz de vectores propios φ1, φ2,...φn Λes la matriz de valores propios       λ10. . . 0 0λ2 .... . . . . .......0 0. . . 0λn       Los φison ortogonales entre si, por tanto, la matriz Φdefine una transformaci´ on lineal ortogonal, que define una nueva base y no deforma, por tanto, el espacio original: Extracci´on de caracter´ısticas 35 Figura 4.7: Ejemplo de transformaci´ on PCA en un espacio de dos dimensiones. El vector propio φ1es el que mayor varianza explica. Una reducci´ on del espacio original definido por los ejes x1, x2en el espacio definido por el eje φ1 mantiene una clara separaci´ on de las observaciones entre las clases. yi= ΦTxi(4.2) despu´ es de esta transformaci´ on, los vectores yitienen como matriz de covarianzas: ΦTScΦ(4.3) dado que Φes ortogonal (ΦTΦ = I) y usando (4.1), la nueva matriz de covariazas es Λ. Con esta transformaci´ on se consigue decorrelar los valores de las nuevas dimensiones (que ser´ an las nuevas caracter´ ısticas). Adem´ as, cada nueva dimensi´ on, generada por un vector propio, tendr´ a como varianza el valor propio correspondiente. Si se define W= [φ1, φ2,...φm], siendo φ1, φ2,...φmlos mvectores propios de mayor valor propio, se habr´ a escogido el subespacio lineal de mdimensiones que m´ as cantidad de la varianza original de los datos explica. A este proceso se le llama reducci´ on de la dimensionalidad. Un ejemplo de la aplicaci´ on de esta transformaci´ on se puede ver en la figura 4.7. La reducci´ on PCA permite mejorar el tiempo de proceso del sistema al reducir el n´ umero de c´ alculos necesarios en la etapa de clasificaci´ on. En los experimentos realizados se probar´ an proyecciones en distinto n´ umero de ejes con el objetivo de encontrar el m´ ınimo n´ umero de dimensiones necesarias para conseguir resultados ´ optimos. 36 Preproceso, extracci´on y selecci´on de caracter´ısticas Figura 4.8: Composici´ on final de un vector de caracter´ ısticas 4.2.4. Coordenadas de posici´on de las ventanas de caracter´ısticas locales En este punto, tras aplicar los pasos anteriores, cada caracter´ ıstica extraida est´ a representada por un vector de ndimensiones que contiene informaci´ on sobre el contenido de una determinada regi´ on del documento sin importar la localizaci´ on de esta regi´ on. Esto puede suponer un problema porque documentos distintos pueden contener gran cantidad de subim´ agenes similares, por ejemplo, porciones de texto impreso en un mismo tipo de fuente. Se podr´ ıa mejorar la informaci´ on aportada por un vector si ´ este incluyera la localizaci´ on de la ventana que contiene dichas subim´ agenes dentro del documento. Esto es tan simple como incorporar las coordenadas de la ventana como dos dimensiones m´ as del vector de caracter´ ısticas. Con esta operaci´ on se obtiene un vector final de caracter´ ısticas multimodal con componentes de distinta naturaleza. Para evitar este problema se ha procedido a normalizar las dos componentes de localizaci´ on de la ventana respecto de la primera coordenada PCA. Tambi´ en es importante evaluar la influencia o peso de las coordenadas de posici´ on dentro del c´ alculo de la distancia eucl´ ıdea entre vectores. Por esto, estas coordenadas no se tendr´ an en cuenta durante la transformaci´ on PCA, y de esta forma se podr´ an aplicar distintos pesos a estos valores (despu´ es de haber sido normalizados), observando c´ omo afectan al resultado final. En la figura 4.8 se describe de forma gr´ afica este proceso. Cap´ıtulo 5 Experimentos 5.1. Descripci´on del corpus Para la realizaci´ on del trabajo ha sido necesario construir una base de datos de documentos aptos para el tipo de estudio que se pretende. La primera intenci´ on era utilizar un corpus est´ andar con el que se pudieran comparar los resultados, pero no se ha encontrado ninguno que se adapte completamente a las necesidades de este proyecto. El ´ unico disponible en la literatura es el corpus NIST SD6 [Dimmick 92], pero s´ olo contiene 20 clases de documentos, por lo que se ha decidido completarlo con documentos provenientes de otros or´ ıgenes. Finalmente, el corpus empleado est´ a compuesto por: 20 clases de la base de datos est´ andar SD6 NIST. Todos elllos son formularios de tasas del gobierno de Estados Unidos cumplimentados a mano. 47 clases de documentos escaneados por el autor del proyecto a partir de facturas, recibos bancarios, etc. Todos ellos con contenido impreso o manuscrito variable y con distintos tama˜ nos y proporciones. En todos los casos, los documentos han sido digitalizados a partir de originales impresos en papel mediante un procedimiento mec´ anico de escaneado, por lo que algunos presentan defectos de rotaci´ on. Dependiendo del origen, algunos documentos est´ an escaneados en escala de grises, otros en blanco y negro. En el corpus hay documentos de distintos formatos, tama˜ nos y tipos, por lo que ser´ a necesario un preproceso previo para tratar de transformarlos a un ´ unico formato. La tabla 5.1 muestra una descripci´ on detallada de las clases de documentos utilizada en los experimentos, indicando las etiquetas asignadas a cada clase, una miniatura de una muestra de cada clase, el tama˜ no aproximado en p´ ıxeles de cada imagen, el tipo de imagen (formato de archivo y profundidad del p´ ıxel), el tipo de documento (formulario, factura, albar´ an o recibo), el origen (atendiendo a los tres or´ ıgenes detallados anteriormente) y el n´ umero de muestras disponibles para la experimentaci´ on. En los experimentos con opci´ on de rechazo se han utilizado un conjunto de 200 documentos, compuesto por formularios y documentos administrativos de distintos or´ ıgenes y formatos pertenecientes a 200 clases, todas ellas distintas entre s´ ı y, por supuesto, distintas a las 67 clases del corpus principal. 38 Experimentos Cuadro 5.1: Corpus utilizado en el proyecto. Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras 1040 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 1041 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 2106 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 2107 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 2441 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 Descripci´on del corpus 39 Cuadro 5.1 – Continuaci´ on Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras 4562 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 4563 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 6251 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 AGAG 1656x2339 PNM 1-bit B/N Fact/Alb IDF1 11 ALDA 1648x719 TIFF 1-bit B/N Recibo IDF1 13 AME 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 40 Experimentos Cuadro 5.1 – Continuaci´ on Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras ARCO 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 BCD 1656x2339 PNM 1-bit B/N Fact/Alb IDF1 13 BNCJ 2362x1181 TIFF 8-bit Gris Recibo IDF1 13 CAM 1656x2339 PNM 1-bit B/N Recibo IDF1 11 CENS 3508x2480 TIFF 8-bit Gris Formulario IDF1 13 CIDA 2480x2362 TIFF 8-bit Gris Fact/Alb IDF1 13 Descripci´on del corpus 41 Cuadro 5.1 – Continuaci´ on Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras CIDF 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 COLT 1656x2339 PNM 1-bit B/N Fact/Alb IDF1 9 COMU 1656x2339 PNM 1-bit B/N Fact/Alb IDF1 10 CORR 1656x2339 PNM 1-bit B/N Fact/Alb IDF1 13 CRDT 2480x1181 TIFF 8-bit Gris Recibo IDF1 13 DEDA 2480x1771 TIFF 8-bit Gris Fact/Alb IDF1 13 48 Experimentos Cuadro 5.1 – Continuaci´ on Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras SCF1 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 SCF2 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 SCHA 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 SCHB 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 SHEL 2542x3551 TIFF 1-bit B/N Formulario IDF1 13 Descripci´on del corpus 49 Cuadro 5.1 – Continuaci´ on Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras SONI 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 SSE1 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 SSE2 2560x3300 PNM 1-bit B/N Formulario SD6 NIST 13 TIMB 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 UNOE 2480x1181 TIFF 8-bit Gris Recibo IDF1 13 VICE 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 50 Experimentos Cuadro 5.1 – Continuaci´ on Etiqueta Miniatura Tama˜no Tipo Documento Origen nº muestras WATR 1656x2339 PNM 1-bit B/N Fact/Alb IDF1 9 YOI2 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 YOIG 2480x3507 TIFF 8-bit Gris Fact/Alb IDF1 13 5.2. Preproceso En los experimentos descritos en esta secci´ on y las siguientes se ha utilizado una imagen de referencia por cada clase para el conjunto de entrenamiento, el resto de im´ agenes se ha utilizado para el conjunto de test. Las im´ agenes de entrenamiento se han revisado, y en los casos en los que ha sido necesario, se han limpiado para eliminar el contenido cumplimentado. Se han aplicado varias t´ ecnicas de preproceso a toda la base de datos de documentos. En primer lugar, se ha aplicado una correcci´ on de la rotaci´ on a todos los documentos. Se ha aplicado un filtro de suavizado utilizando una matriz de convoluci´ on de 5×5y se ha aplicado un proceso de binarizado con un umbral del 70 %. Para evitar los inconvenientes originados por las distintas resoluciones de adquisici´ on, as´ ı como los distintos formatos de imagen, cada imagen se ha normalizado en tama˜ no Optimizaci´on de par´ametros 51 para que ocupe la misma superf´ ıcie en n´ umero total de p´ ıxeles (equivalente a la de un documento A4 escaneado a 300dpi) preservando su relaci´ on de aspecto original. En el paso de binarizado, los p´ ıxeles de cada imagen han sido convertidos a negro (0) o blanco (255), es decir, se han eliminado los valores de gris. Posteriormente, la fase de normalizado a tama˜ no A4 ha devuelto algunos de los p´ ıxeles a valores intermedios debido al efecto de suavizado que produce este proceso. ´ Este es el motivo por el que no se han utilizado imagenes binarias con p´ ıxeles de un solo bit, ya que al final del proceso, habr´ a valores de gris dentro del rango [0,255]. La ´ ultima fase de preproceso ha consistido en escalar los documentos a distintos tama˜ nos y observar la evoluci´ on del error obtenido. La figura 5.1 muestra el error de clasificaci´ on para distintos valores de escalado de los documentos. Se han aplicado diversos factores de escala entre 1/4 y 1/12 (partiendo de las imagenes de area A4 a 300dpi). En cada caso el tama˜ no de la ventana de caracter´ ısticas locales se ha escalado aplicando el mismo factor. 5.3. Optimizaci´on de par´ametros Las fases de selecci´ on y extracci´ on de caracter´ ısticas requieren del ajuste de distintos par´ ametros. Para ver como afectan todos ellos al rendimiento del sistema, se han realizado pruebas exhaustivas tratando de probar gran cantidad de combinaciones. En estas pruebas se han combinado los siguientes par´ ametros: Escalado del documento. Con el objetivo de reducir el coste computacional, se han aplicado a los documentos distintos factores de escala entre 1/4 y 1/12 (partiendo de las imagenes de area A4 a 300dpi). En cada caso el tama˜ no de la ventana de caracter´ ısticas locales se ha escalado aplicando el mismo factor. Tama˜no de ventana. Se ha experimentado con varios tama˜ nos de ventana, que incluyen potencialmente subim´ agenes con distinto n´ umero de caracteres de texto u otros objetos. Las ventanas de 80 p´ ıxeles de ancho y 30 p´ ıxeles (respecto de la imagen original) de alto han proporcionado los mejores resultados. Reducci´on de la dimensionalidad. Se ha aplicado una transformaci´ on PCA a los vectores de caracter´ ısticas locales y una reducci´ on de dimensionalidad. La t´ ecnica PCA solamente se ha aplicado a las componentes del vector de caracteristicas resultantes de concatenar los valores de gris de los p´ ıxeles de las ventanas, es decir, no se han tenido en cuenta las dos componentes de posici´ on de la ventana. Se han probado reducciones entre 10 y 25 dimensiones, obteniendo los mejores resultados en cuanto a coste computacional y tasa de error con las primeras 15 componentes PCA. Esto significa que los vectores de caracter´ ısticas con los que se trabajar´ a finalmente tendr´ an 17 componentes: las 15 de la reducci´ on PCA m´ as las 2 coordenadas de posici´ on de la ventana. Peso de las caracter´ısticas globales. Despu´ es de la reducci´ on de la dimensionalidad, se han agregado a cada vector de caracter´ ısticas las coordenadas de posici´ on del punto central de cada ventana. Los valores de estas nuevas caracter´ ısticas se han normalizado a la desviaci´ on est´ andar del primer componente PCA y se han multiplicado por un factor de peso para sintonizar su efecto con respecto al resto de los componentes. Se han probado combinaciones de factores de peso (αx, αy)entre 0 y 8. Paso de submuestreo y orla de vecindad. Se han efectuado varios experimentos con estos dos par´ ametros. Finalmente, se ha llegado a la conclusi´ on de que estos par´ ametros est´ an fuertemente ligados al tama˜ no de la ventana de caracter´ ısticas locales. Los mejores resultados se obtienen aplicando pasos de submuestreo y orla de vecindad con valores de la mitad del tama˜ no de la ventana 52 Experimentos Figura 5.1: Tasas de error a nivel de documento (eje izquierdo) y nivel de caracter´ ıstica local (eje derecho) para diferentes escalas de reducci´ on. Se muestran los datos logrados con la mejor combinaci´ on del resto de par´ ametros. de caracter´ ısticas. P. ej.: para una ventana de tama˜ no 14 ×8, se utilizar´ an pasos de submuestreo (sx, sy) = (7,4) y un tama˜ no de orla de vecindad de 7×4 Numero de caracter´ısticas locales (LF). Se han seleccionado distintas cantidades de subim´ agenes que presentan los mejores ´ ındices de contraste (m´ axima varianza) para los conjuntos de entrenamiento y test. Se han probado valores entre 100 y 1000. Para reducir el n´ umero de c´ alculos en la b´ usqueda de candidatos, se ha aplicado submuestreo a las im´ agenes, tanto en la fase de entrenamiento como en la de test. En la fase de entrenamiento, se han incluido en los conjuntos de cada clase las subim´ agenes extraidas de la orla de vecindad de cada p´ ıxel seleccionado. Se ha implementado un clasificador r´ apido basado en la t´ ecnica de b´ usqueda aproximada mediante kd-tree. Se ha obtenido el vecino m´ as pr´ oximo de cada uno de los vectores 17-dimensionales (15 + 2) extraidos de las im´ agenes de test, utilizando un valor de = 2, y se ha empleado la “regla de la suma” descrita en el apartado 2.3 para clasificar estas im´ agenes. Se ha alcanzado un resultado ´ optimo de 0 % de tasa de error en la clasificaci´ on de documentos con la siguiente combinaci´ on de par´ ametros: Dimensi´ on del vector PCA: 15 componentes Tama˜ no de la ventana de caracter´ ısticas (antes de escalado): 80 ×30 Submuestreo (antes de escalado): 40 ×15 Orla de vecindad (antes de escalado): 40 ×15 Factor de escala: 1/6 Optimizaci´on de par´ametros 53 Figura 5.2: Tasa de error a nivel de documento en funci´ on del n´ umero de caracter´ ısticas locales utilizadas en test y entrenamiento. 300 vectores de entrenamiento por clase 500 vectores de test Peso de las coordenadas (αx, αy) = (6,2) El tiempo promedio para la identificaci´ on (fase de test) ha sido de 4,5 documentos/s en un ordenador con procesador AMD de 64 bits y 4 CPU de 3 GHz. La figura 5.1 muestra el error de clasificaci´ on obtenido para los distintos valores de escala del documento, en cada valor obtenido se ha utilizado la mejor combinaci´ on del resto de par´ ametros. El n´ umero de las caracter´ ısticas locales y el peso de las caracter´ ısticas globales (coordenadas de posici´ on de los vectores) son par´ ametros fuertemente relacionados con la aproximaci´ on utilizada. Por esto, en la gr´ afica 5.1 se presenta un an´ alisis de los resultados sobre la variaci´ on de ambos par´ ametros, al mismo tiempo que se fijan los restantes. Se observa un resultado ´ optimo con una tasa de error en la clasificaci´ on de documentos del 0 % para una reducci´ on de escala de 1/6. La curva de color rojo representa la tasa de error de clasificaci´ on de las subim´ agenes seleccionadas. En cada punto representado se han fijado el resto de par´ ametros a los valores que producen un resultado ´ optimo. En la figura 5.2 se muestra el error obtenido en funci´ on del n´ umero de vectores seleccionados en las fases de entrenamiento y test. Generalmente, se han encontrado las mejores combinaciones utilizando unos cuantos vectores m´ as para la fase de test que los seleccionados en la fase de entrenamiento. No se aprecian grandes diferencias entre las distintas combinaciones. Aunque se produce el resultado ´ optimo de 0 % de error en la combinaci´ on de 300 vectores seleccionados en fase de entrenamiento y 500 en fase de test. 54 Experimentos Figura 5.3: Tasa de error a nivel de documento en funci´ on de los pesos de las coordenadas. La figura 5.3 muestra la gran capacidad discriminante que aporta la informaci´ on de las coordenadas de posici´ on de las subim´ agenes. La combinaci´ on de pesos (αx, αy) = (6,2) produce el resultado de 0 % de tasa de error en la clasificaci´ on de documentos. Esto significa una mejora del 5 % (33 documentos) respecto de los resultados obtenidos sin tener en cuenta la posici´ on como una caracter´ ıstica global, valor que se puede observar en el punto (αx, αy) = (0,0) de la gr´ afica. Cabe destacar la distinta influencia en los resultados de la coordenada x, respecto de la coordenada y, que es mucho menos discriminante que la primera. Esto es debido probablemente a que los documentos presentan traslaciones m´ as acusadas en la coordenada ydebido a los defectos mec´ anicos en el proceso de escaneado. 5.4. Opci´on de rechazo Un buen clasificador debe ser robusto ante la entrada de im´ agenes que no pertenecen a ninguna de las clases conocidas, debe ser capaz de detectar estos documentos y rechazarlos. Para ello se ha establecido una medida de calidad de la clasificaci´ on de un documento o “´ ındice de fiabilidad”, de esta forma, se establecer´ a un umbral para este ´ ındice de fiabilidad y se rechazar´ an aquellos documentos que no lo superen. Para un conjunto de test dado, la distribuci´ on de los ´ ındices de fiabilidad de los documentos bien clasificados no deberia solaparse con la distribuci´ on de los ´ ındices de fiabilidad de documentos desconocidos o mal clasificados. Obviamente, cuanto mayor sea la separaci´ on entre ambas distribuciones se esperar´ a una mejor capacidad de generalizaci´ on. Se han seleccionado 200 documentos aleatorios correspondientes al corpus descrito en el apartado 5.1 y se han a˜ nadido al conjunto de test como una clase especial de “documentos desconocidos”. Se ha efectuado una clasificaci´ on con los par´ ametros ´ optimos mostrados en el apartado 5.3 y se han obtenido Opci´on de rechazo 55 los votos recibidos en cada clases para todos los documentos de test. Para un documento cualquiera de test, se ha definido una funci´ on de fiabilidad basada en las dos clases m´ as votadas de la siguiente forma: F=αf + (1 −α)g siendo: f=f1la probilidad a posteriori de la clase m´ as votada, con f1=n1 N, donde n1es el n´ umero de votos obtenidos por la clase m´ as votada y Nel n´ umero de caracter´ ısticas extraidas en un documento. g=f1−f2es la diferencia de probabilidades a posteriori entre las dos clases m´ as votadas. αes un valor entre 0 y 1 con el que se ha experimentado. Los experimentos han demostrado que cualquier valor de αofrec´ ıa los mismos resultados, por lo que la funci´ on de fiabilidad se ha simplificado para el valor de α= 0, es decir, la funci´ on de fiabilidad empleada finalmente ha sido: F=f1=n1 N Aplicando este criterio como ´ ındice de fiabilidad a los resultados de clasificaci´ on del conjunto original de test junto con las im´ agenes de documentos desconocidos se ha obtenido un valor del 99,85 % de exhaustividad al 100 % de precisi´ on (recall at 100 % precision) 2.5.1. Con estos resultados, se puede concluir afirmando que este sistema ser´ a capaz de aceptar con un elevado porcentaje de acierto los documentos conocidos y bien clasificados, y de rechazar los documentos desconocidos y los que han sido clasificados de forma incorrecta. 56 Experimentos Cap´ıtulo 6 Conclusiones En el presente trabajo se ha presentado la aplicaci´ on de una t´ ecnica para la identificaci´ on de im´ agenes de documentos con informaci´ on cumplimentada utilizando una combinaci´ on del uso de caracter´ ısticas locales junto con un sistema de clasificaci´ on basado en un esquema de votaci´ on directa sobre un clasificador de los k-vecinos m´ as pr´ oximos. Se ha recopilado y preparado una base de datos extensa de im´ agenes de documentos con la que se han realizado los experimentos, y que puede servir para futuros trabajos relacionados con documentos con informaci´ on cumplimentada. Los resultados obtenidos son representativos de los que se deber´ ıan obtener en un proceso real de similares caracter´ ısticas. La base de datos de documentos se ha recopilado a partir de facturas, formularios, recibos, y otros tipos de documentos, escaneados mec´ anicamente en un proceso comparable al que seguir´ ıa el workflow habitual de una empresa con necesidad de digitalizaci´ on de documentos. Se ha realizado una experimentaci´ on exhaustiva de los par´ ametros m´ as relevantes, identificando sus valores ´ optimos, con los cuales se ha alcanzado una tasa de error del 0 % en la clasificaci´ on de documentos, y un resultado del 99,85 % de recall at 100 % precision al incluir la opci´ on de rechazo de documentos desconocidos. Los tiempos de proceso requeridos (alrededor de 4,5 documentos por segundo) hacen pensar que este sistema ser´ ıa f´ acilmente integrable en un aplicaci´ on real de identificaci´ on de documentos, incluso para empresas con elevado workflow.