Reconocimiento de Sellos en Legajos de Archivo Histórico

Equation Chapter 1 Section 1 Trabajo de Fin de Grado Ingeniería de Tecnologías Industriales Reconocimiento de Sellos en Legajos de Archivo Histórico Autor: Miguel Ángel Rodrigo de Lisbona Tutor: Daniel Limón Marruedo Dep. de Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 Trabajo de Fin de Grado Ingeniería de Tecnologías Industriales Reconocimiento de Sellos en Legajos de Archivo Histórico Autor: Miguel Ángel Rodrigo de Lisbona Tutor: Daniel Limón Marruedo Profesor titular Dep. de Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 Proyecto Fin de Carrera: Reconocimiento de Sellos en Legajos de Archivo Histórico Autor: Miguel Ángel Rodrigo de Lisbona Tutor: Daniel Limón Marruedo El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2017 El Secretario del Tribunal A mi familia A mis maestros Resumen La Fundación Osborne posee un archivo de documentos relacionados con la empresa que datan desde principios de 1800. Previas investigaciones han permitido descubrir información sobre la vida de Tolkien en el archivo. Se sabe además, que existe correspondencia con casas reales o el Vaticano. También existe correspondencia de personajes públicos como Washington Irving. Los inicios de la empresa están estrechamente relacionados con otros personajes históricos como Fernán Caballero, cuñada del fundador, o “Frasquita” Larrea, su suegra. Por ello, podría haber información importante por descubrir sobre dichos personajes que podría ser de valor histórico. Para extraer dicha información, se ha optado por desarrollar una web donde se suben los archivos escaneados junto con su transcripción. Además de ello, se quiere desarrollar un sistema que realice dichas transcripciones de manera autónoma mediante detección de los caracteres manuscritos. En este trabajo se describe el desarrollo de un sistema que reconozca los escudos en las cartas para clasificar su autor de manera automática. Además, el sistema debe calcular la posición de dichos escudos con el objetivo de eliminarlos. Esto es necesario ya que los sistemas de detección de caracteres necesitan que los elementos que no son texto sean eliminados del documento antes de empezar cualquier análisis. Figura 6.1. Una esquina deja de serlo al aumentar su escala. 42 Figura 6.2. Proceso de obtención de la diferencia de gaussianos. 44 Figura 6.3. Búsqueda de extremos locales en el espacio de escalas. 44 Figura 6.4. Matriz de evidencias de celdas 100x100px, 10 veces mayores que las empleada. 53 Figura A.1. Árbol de dependencias de Ground Truth GUI 59 1 1 LA IMPORTANCIA DE PRESERVAR NUESTRA HISTORIA a Historia. Alrededor de 6000 años de documentos escritos, miles de generaciones plasmando pensamientos y vivencias para aquellos que aún están por venir, haciendo posible el ciclo motor del progreso de todas las sociedades: intentar, fracasar, aprender y repetir. Parafraseando a Warren Buffet, si hay algo más importante que aprender de los errores de uno mismo, es aprender de los errores de los demás. Vivimos en un mundo en el que todos aparentan (o incluso creen) saber qué hacer para resolver los problemas. Pero cuando dos personas tienen opiniones incompatibles, al menos uno debe estar equivocado. La realidad es que ni políticos, ni científicos, ni guías espirituales de ningún tipo saben con absoluta certeza la mejor solución a todo. Es aquí donde la historia nos proporciona la más valiosa de las fuentes de conocimiento para permitir tanto a sociedades como a individuos tomar decisiones un poco menos a ciegas. Nadie duda de la importancia de la investigación, preservación y difusión de la historia además de garantizar la no distorsión de la misma. Por todo ello, la digitalización y catalogación de la totalidad de textos escritos por la humanidad a lo largo de su paso por este mundo tendría un incuestionable gran valor. Realizar esta tarea de manera manual es evidentemente inviable. Es por ello que existen multitud de líneas de investigación a lo largo y ancho del globo con el objetivo de conseguir automatizar esta tarea. Este trabajo describe parte del proyecto llevado a cabo por Talemtum Lab Osborne mediante la colaboración de la Fundación Osborne1, Telefónica Talemtum Labs2 y la Fundación SEPI3. El objetivo del proyecto es la digitalización del archivo histórico que posee el Grupo Osborne almacenado en sus primeras bodegas en El Puerto de Santa María. Dicho archivo contiene, por un lado, facturas, notas de pago y demás documentación de carácter administrativo y, por otro, correspondencia entre miembros de la familia y con otros personajes públicos de la época de la fundación de la empresa en 1772. Entre estos personajes se encuentran Washington Irving, J.R.R. Tolkien o Isaac Peral, quien ofrece sus servicios a la empresa en una de sus cartas, así como miembros de distintas casas reales o El Vaticano. El archivo ya ha sido utilizado en una reciente investigación sobre la biografía de Tolkien, muy relacionado con la familia Osborne al ser criado y educado por uno de sus miembros, y existen múltiples indicios de que podrían existir en él más documentos de importante valor histórico. La suegra de Thomas Osborne Mann, fundador de la empresa, fue Francisca Javiera Ruiz de Larrea y Aherán, Frasquita Larrea. Esta señora fue una escrtora gaditana impulsora de la tertulia literaria que se cree que tuvo una gran influencia en la Constitución de 1812. La cuñada de Thomas fue la escritora Cecilia Böhl de Faber y Larrea, Fernán Caballero. Gran parte de la documentación que se posee tiene un contenido desconocido, de ahí nace la motivación por 1 Fundación Osborne es el vehículo canalizador de la Responsabilidad Social Corporativa del Grupo Osborne. Posee dos fines fundamentales: la preservación y difusión del patrimonio histórico de la compañía y la promoción de la formación y el emprendimiento en las áreas de influencia del Grupo Osborne [1]. 2 La Fundación Telefónica tiene por misión mejorar las oportunidades de desarrollo de las personas a través de proyectos educativos, sociales y culturales, adaptados a los retos del mundo digital [2]. 3 La Fundación SEPI, entre otras actividades, promueve y gestiona un extenso Programa de Becas de Inserción Laboral que cada año facilita la formación práctica en las empresas a más de 300 jóvenes titulados [3]. L Un pueblo sin conocimientos de su historia, origen y cultura es como un árbol sin raíces. - Marcus Garvey - La importancia de preservar nuestra historia 2 digitalizarlo para permitir agilizar su investigación. Para ello, se desarrolla una página web donde se muestran los documentos escaneados junto con su transcripción. Esta transcripción es necesaria por un doble motivo: por un lado, los documentos tienen en su mayoría una caligrafía de muy difícil reconocimiento lo cual ralentiza enormemente la lectura e interpretación. Por otro lado, si se quiere realizar algún tipo de búsqueda en función de algún término que forme parte del texto, sería imposible sin transcripción previa. 3 2 DESCRIPCIÓN DEL PROBLEMA ste trabajo forma parte de un proyecto mayor que pretende extraer información de los documentos del archivo descrito mediante técnicas de visión artificial. El problema al que se dedica esta memoria consiste en localizar la posición de posibles escudos o sellos en correspondencia con un doble objetivo:  Localizar la posición de dicho sello con el objetivo de eliminarlo de la imagen y que no suponga un problema para otros sistemas de reconocimiento, como por ejemplo la transcripción automatizada del texto.  Reconocer de qué sello se trata y clasificar el documento en cuestión de acuerdo con la información disponible de dicho sello. Algunos ejemplos de documentos se muestran a continuación. Figura 2.1. Ejemplo de tipos de documentos que pueden presentarse En la figura anterior pueden apreciarse dos tipos de documentos distintos. Uno presenta texto en vertical además del texto horizontal. Esto es una gran dificultad añadida como se verá más adelante, ya que el texto en diferentes direcciones que intersecta se detecta como un único objeto en la imagen. E Somos como enanos a los hombros de gigantes. Podemos ver más, y más lejos que ellos, no porque la agudeza de nuestra vista ni por la altura de nuestro cuerpo, sino porque somos levantados por su gran altura. - Bernard de Chartres - Descripción del problema 4 Figura 2.2. Dos ejemplos más de documentos Puede verse en el documento de la izquierda como existen varias manchas además de las marcas de pliegues oscurecidas por el envejecimiento. Todos estos elementos dificultan la detección. En concreto, la mancha roja es particularmente difícil de diferenciar de un sello. El caso de la derecha representa la situación ideal, donde el documento presenta un sello claramente separado del texto, mientras que el resto del papel apenas presenta envejecimiento o imperfección alguna. El problema del reconocimiento automático de elementos en documentos escritos, ya sean caracteres, firmas, logos o cualquier otro elemento, es un tema de gran interés, y por lo tanto, existe una extensa bibliografía con muy diversos métodos para atajar el problema. En [4] se estudia cómo extraer y reconocer sellos estampados con el objetivo de clasificar documentos. En un primer paso se realiza una segmentación mediante una Transformada de Hough para círculos para hallar regiones de sellos. Después se detectan los caracteres aislados hallados en las regiones se aplica un sistema de clasificación basado en características invariantes a la rotación y la escala. Después se utiliza la información de la posición relativa de cada pareja de caracteres para clasificar el sello. En nuestro caso, los sellos carecen de texto alguno, por lo tanto no pueden clasificarse así. Sin embargo, el método de segmentación mediante TdH sí que podría resultar de interés. En [5], se estudia un método para la segmentación y clasificación de firmas. El algoritmo propuesto extrae el contorno de las regiones de las firmas y utiliza información de la posición relativa de los puntos de ese contorno para la clasificación. En nuestro caso, el deterioro del papel con el paso de los años, además de que los sellos tienen forma mucho más compleja que tan solo trazos hacen que la detección de contornos no siempre devuelva el mismo resultado para el mismo sello. Nandedkar, Mukhopadhyay y Sural [6] aplican un método mucho más sencillo en el cual utilizan una convolución gaussiana a la imagen como filtro de paso bajo para separar texto de logotipos. Esto se basa en el hecho de que el texto añade componentes de alta frecuencia al espectro de una imagen, mientras que un logotipo tan solo posee componentes de baja frecuencia. Como se verá más adelante, este método tan sólo funciona para sellos con grandes regiones homogéneas, mientras que falla para aquellos con trazos más delgados. Antes de desarrollar ningún método, necesitamos alguna forma de medir cómo de efectivo resulta. Para medir la calidad de los resultados obtenidos con cada experimento se ha construido un ground truth. Un detalle muy importante es que el conjunto total de documentos se considera cerrado. Es decir, se supone que la totalidad de documentos del archivo ha sido escaneado y que no van a descubrirse documentos nuevos. Esto es de gran relevancia en el algoritmo final desarrollado. En caso de que se contemplase la posibilidad de continuar añadiendo nuevos documentos, deberían agregarse pasos adicionales (además de triviales) al algoritmo que definieran cómo clasificar los nuevos documentos que se incorporasen a la colección. Esto no significa en cambio que este algoritmo sólo sea funcional para este conjunto cerrado de documentos, sino que se diseña con el objetivo de que sea útil para cualquier conjunto cerrado de documentos manuscritos, siempre y cuando presenten una estructura suficientemente similar. No se considera que deba 5 5 Reconocimiento de Sellos en Legajos de Archivo Histórico funcionar por ejemplo para imágenes que presenten más de dos páginas de un documento. Las tecnologías que se han utilizado son:  Python y en menor medida C++ para codificar los algoritmos.  OpenCV, librería de visión artificial de código abierto por excelencia.  Pygame junto con Tkinter para desarrollar una aplicación que nos permita agilizar el proceso de crear un ground truth.  MySQL para todas las necesidades de base de datos del proyecto, tanto almacenar resultados, como la información del ground truth o la ruta de las imágenes de cada uno de los sellos. 7 3 CONSTRUCCIÓN DE UN GROUND TRUTH En machine learning se denomina ground truth a la colección de datos supervisados que se realiza con el objetivo de someter a prueba una hipótesis. Este ground truth consiste en una base de datos que relaciona cada documento con el sello que contiene, si contuviese alguno. En tal caso, se almacenan además las coordenadas de dicho sello en la imagen. Para llevar a cabo este procedimiento se ha desarrollado un software que permite agilizar la tarea. En él puede visualizarse el documento en cuestión, acercar o alejar el zoom además de desplazar la imagen. Una vez localizado el sello, se seleccionan dos esquinas opuestas de este, eligiendo cada una con el click de cada uno de los dos botones del ratón. Esta interfaz se ha creado utilizando la librería Pygame, que permite dibujar gráficos sencillos en una ventana mediante un script de Python. Figura 3.1. Software para la elaboración de un ground truth Una vez que el sello ha sido encuadrado, se utiliza el panel de control que se muestra en la imagen para seleccionar cuál es el tipo de sello que se ha encuadrado. Para esto, el panel de control se comunica con una base de datos MySQL donde se almacenan tanto la ruta de la imagen como un nombre arbitrario que se ha escogido para describir cada sello. El usuario puede seleccionar el sello deseado de la lista desplegable y pulsar “Change” para que cambie la vista en el panel de control a una imagen del sello que se ha seleccionado y así asegurarse de que ha elegido el nombre de sello correcto. Puede darse el caso de que el sello encontrado en el documento sea la primera vez que se locacaliza y por tanto no exista ningún registro de él en la base de datos. Si esto ocurriera, se utiliza el botón “New” y se abrería una ventana emergente donde se le da un nombre al Saber qué conoces y qué no conoces. Ese es el verdadero conocimiento. - Confucio - Esquema general de un ocr 14 4.2.1 Segmentación mediante enfoque frecuencial Como ya se mencionó, en [6] se desarrolla un método para separar texto de elementos gráficos en documentos escaneados. La idea se basa en el hecho de que el texto introduce componentes armónicas de alta frecuencia a la imagen. Por lo tanto, un filtro de paso bajo eliminaría ese texto. En el algoritmo, se utiliza un filtro de Gauss para eliminar las componentes de alta frecuencia. El resultado es una imagen con los elementos de texto eliminados casi en su totalidad mientras que los elementos gráficos (en el artículo incluye también logos) permanecerían en la imagen, idealmente, en su totalidad. El algoritmo expuesto por Nandedkar, Mukhopadhyay y Sural es el siguiente: Figura 4.7. Algoritmo espectral de seccionamiento El algoritmo original presenta algunos pasos adicionales para separar distintos tipos de elementos gráficos, pero para nuestro problema, son pasos innecesarios. Filtrado frecuencial El filtrado frecuencial es el paso más importante del método, y es donde se elimina la mayor parte del texto. Es una evidencia fácilmente comprobable que el texto contribuye a componentes espectrales de muy alta frecuencia en imágenes de documentos. Por ello, se convoluciona con un kernel gausiano como filtrado de paso bajo y se utiliza un post procesado para eliminar restos residuales de texto. El algoritmo puede verse en la figura X. Figura 4.8. Filtrado frecuencial El proceso consiste en: 1. Se toma la imagen original convertida a escala de grises, X. 2. Se le aplica un filtrado gaussiano, G(X). 15 15 Reconocimiento de Sellos en Legajos de Archivo Histórico 3. Se calcula la imagen la imagen de paso alto Y, restándole G(X) a la original. 𝑌= 𝑋−𝐺(𝑋) 4. Un filtrado selectivo en frecuencias sencillo sería entonces FL= I i,j ,si Y i,j <𝑇 Bk,En caso contrario Donde I es la imagen original de dimensiones NxM, 1≤ i ≤ N y 1≤ j ≤ M. T es el umbral de frecuencias. Los valores que superan un cierto valor en la imagen filtrada Y se consideran de alta frecuencia, los que no, de baja frecuencia. Por último, Bk es el valor del color considerado de fondo. En el artículo utilizan una media de los colores de fondo del papel, obtenidos sumando los píxeles de la imagen original I, que han quedado como fondo en una binarización de la imagen en escala de grises X. En este trabajo se ha considerado innecesario ya que no se pretende reconstruir los huecos dejados por los elementos de eliminados del documento, y se ha tomado Bk como blanco directamente. Hay que destacar que un filtrado solamente en frecuencias no es apto para elementos cromáticos cuyos tonos cambien de manera abrupta, ya que también introducen componentes de alta frecuencia y dicho filtro los eliminaría. Para solventar este problema, se conservan también aquellos elementos que tengan una cantidad de color suficientemente alta, esto se consigue cuantificar mediante la cromaticidad. Definición cromaticidad: Se entiende por cromaticidad de un tono de color a la medida de cómo de alejado se encuentre ese color de tonos grises, independientemente de su luminancia, es decir, de cómo de claro u oscuro sea. En un espacio de colores YCrCb, la cromaticidad R se cuantifica como 𝑅= 𝐶𝑟2+ 𝐶𝑏2 Por tanto, dada nuestra imagen original, se define la matriz de cromaticidad aquella que contiene para cada píxel el valor de su cromaticidad. Figura 4.9. Espacios de color YCrCb para valores de luma (Y) de 0, 0.5 y 1 respectivamente. En la figura anterior puede verse como aquellos colores con una menor R, es decir, aquellos más cercanos al origen de coordenadas, poseen tonos más grises. Volviendo al problema anterior, queremos evitar que al filtrar componentes de alta frecuencia eliminemos elementos gráficos que posean cambios bruscos en los colores. Para ello, imponemos un umbral V. Aquellos píxeles cuya cromaticidad sea superior a dicho umbral serán conservados en la imagen filtrada. Esto no supone ningún problema para la eliminación de texto ya que los caracteres tienen generalmente una cromaticidad muy baja. Los resultados obtenidos mediante este procedimiento son los siguientes. Esquema general de un ocr 16 Figura 4.10. Ejemplo de correcto funcionamiento del filtrado frecuencial. Figura 4.11. Ejemplo en el cual el filtrado frecuencial falla. Como puede verse, los resultados en el primer caso son verdaderamente alentadores. Sin embargo, en el segundo caso el filtrado frecuencial elimina buena parte del sello además del texto. Esto se debe a que el sello está compuesto de trazos finos y una zona más gruesa pero que en realidad son franjas estrechas con diferencias tonales entre colores de muy baja cromaticidad. Este método es muy bueno cuando los gráficos a separar del texto poseen regiones amplias de colores uniformes, como logotipos, y que, si poseen algún trazo estrecho, éste posee una alta cromaticidad o no supone una porción importante del elemento en cuestión. Para nuestro caso por tanto, no supone una solución robusta. Por todo eso, se procederá a probar otro método. 4.2.2 Extracción y descripción de características Para describir en qué consiste este enfoque, trate el lector de localizar la posición de cada uno de los fragmentos en la imagen inferior. 17 17 Reconocimiento de Sellos en Legajos de Archivo Histórico De manera inconsciente habrá tratado de buscar los elementos que pudieran ser más fácilmente reconocibles en cada uno de los fragmentos, como bordes o esquinas, para luego intentar localizar esos elementos en la imagen completa. Puede observarse que, generalmente, el primer fragmento resulta más difícil de localizar, mientras que el último es el más sencillo. La facilidad o dificultad de localizar cada fragmento de manera correcta depende de lo diferente que sea de sus alrededores cercanos el elemento que inconscientemente usamos para comparar. Típicamente, las esquinas de objetos ofrecen la mayor facilidad. Este elemento que inadvertidamente seleccionamos como pivote se denomina, en el ámbito de la visión artificial, característica. Característica: Porción de la imagen que posee alguna propiedad que la hace muy distinta al resto de imagen que la rodea, típicamente alguna medida relacionada con el gradiente. Realmente no existe una definición global que pueda ser concreta sobre qué es una característica en visión artificial, ya que depende del algoritmo en concreto del que se hable. Pueden ser bordes, esquinas, blobs (o regiones de interés) o lo que se conoce como ridges, en español crestas. Estas últimas son regiones alargadas. Por ejemplo, una imagen de un avión visto desde la planta está compuesta por dos ridges que se cruzan entre sí. Es importante destacar que no se ha incluido en la definición ninguna referencia a la dimensión de una característica con respecto a la dimensión de la imagen. Esto es así ya que en muchos algoritmos (SIFT, SURF, BRIEF…) se busca definir una característica como invariante a la escala, es decir, sigue siendo una característica independientemente del tamaño que tenga dentro de la imagen. Esto no es cierto en la totalidad de algoritmos, como es el caso del detector de esquinas Harris. Existen multitud de algoritmos para esta tarea, pero en esta sección nos limitaremos a emplear uno de ellos: SURF. Nuestro objetivo de momento es simplemente ver si merece la pena invertir en este enfoque o, por el contrario, sería mejor descartarlo y buscar una nueva solución a nuestro problema. Para nuestro experimento vamos a tomar dos imágenes de dos sellos extraídas de la base de datos de documentos. Después se comparará un documento con ambos sellos. Uno de ellos es el mismo que aparece en el documento, el otro no. Esquema general de un ocr 18 Figura 4.12. Comparación de características entre el documento y su mismo sello. Figura 4.13. Comparación de características entre el documento y un sello distinto. El sistema calcula primero qué puntos de la imagen son mucho más distintos del resto (esquinas de objetos en este caso) y se han dibujado en azul. Después compara los puntos de la imagen del sello con los del documento y empareja aquellos que determina que más se parecen. Estos emparejamientos se han dibujado en verde. Más adelante se explicará en detalle todo el proceso. Este primer experimento parece indicar que este sistema es bastante bueno para resolver el problema. Hay dos consideraciones importantes que hacer antes de continuar. 1. Este sistema no solo puede ser útil para segmentar estimando la posición del sello, sino que además se puede emplear en la fase de reconocimiento, para saber qué sello es. 2. Aunque los resultados parecen muy positivos no hay que olvidar que para el correcto funcionamiento de este sistema es necesario estar en posesión de una imagen de cada sello. Este no es un requisito absolutamente utópico, pero preferiría salvarse si fuera posible. Esto se debe a que en una aplicación real no es posible disponer de esta información ya que, si así fuera, significaría que la totalidad de 19 19 Reconocimiento de Sellos en Legajos de Archivo Histórico documentos han sido clasificados y por lo tanto este proceso carecería de utilidad. 4.2.3 Segmentación mediante componentes conexas En visión artificial, la búsqueda de componentes conexas se refiere a la familia de algoritmos que pretende localizar grupos de píxeles que cumplan una determinada condición y que se encuentren en contacto directo. La idea es agrupar los píxeles oscuros que aparezcan conexos en la imagen e identificar qué propiedades poseen los que pertenecen a un sello con respecto a los que no. OpenCV ofrece un detector de blobs que implementa componentes conexas utilizando como condición múltiples binarizados a distinto umbral y agrupando aquellos píxeles conexos en cada umbral. Este sistema es muy útil cuando existen objetos muy distintos en forma y/o color y que poseen mucho contraste con respecto del fondo. En nuestro caso, los objetos que queremos detectar son sellos y palabras. No están claramente diferenciados y, en muchos casos, el contraste con el fondo es escaso. Por todo esto el bajo control que ofrece este algoritmo no es suficiente. Por ello se ha empleado el detector de componentes conexas sencillo sin funcionalidad adicional. Este algoritmo toma una imagen binarizada y devuelve una imagen de etiquetas. Esto consiste en que cada píxel se sustituye por una etiqueta de manera que aquellos píxeles que se encuentren conexos posean todos la misma etiqueta, única para cada conjunto conexo. Una etiqueta no es más que un valor entero incremental a partir de 0, valor que se reserva para los píxeles del fondo. Una vez que sabemos qué píxeles pertenecen al mismo objeto de la imagen binaria se pueden hacer todo tipo de operaciones. Cabe destacar que, una vez más, aún no se pretende desarrollar un sistema perfectamente funcional y capaz de resolver el problema, sino un prototipo rápido del algoritmo que nos permita juzgar si merece la pena seguir desarrollándolo o si en cambio debe ser descartado y sustituido. En esta primera prueba se ha calculado el área de cada región conexa como el número de píxeles que se incluyen dentro de ésta, y se ha descartado como posible candidato a sello aquellas regiones demasiado pequeñas. Además, es frecuente que palabras de diferentes líneas en las que aparecen caracteres con pronunciada verticalidad como podrían ser una “p” y una “t” se unifiquen en una misma región al aparecer solapados dichos caracteres. Para eliminar este común error, se ha calculado el bounding box o cuadro delimitador de cada región y se ha calculado el área de éste cuadro como el área geométrica del rectángulo que lo compone. A continuación se ha obtenido el ratio del área de la región (es decir, el conteo de puntos que forman parte de esta región) con respecto al área de su cuadro. A este ratio se le ha denominado ratio de relleno. Si el ratio de relleno es demasiado pequeño, la región es descartada también. Figura 4.14. Ejemplo de ratio de relleno para dos regiones detectadas Se ha dejado al sistema correr sin filtrar según el ratio y manualmente se ha seleccionado cuáles de las regiones devueltas corresponden a un sello y cuáles no. Estos son los datos recogidos. Esquema general de un ocr 20 Figura 4.15. Distribución de ratios de relleno. En rojo aquellas regiones que no son un sello y en azul las que sí. Los resultados son claros: el filtrado de regiones según estos parámetros parece efectivo, mientras los sellos cumplan la condición de estar claramente separados del texto (sin ningún solapamiento) y con una morfología diferenciable a la que típicamente presenta el texto. A continuación se muestra un ejemplo de una correcta identificación de un sello seguido de otro en el cual el sistema prototipo no es capaz de localizarlo. Figura 4.16. Ejemplo del correcto funcionamiento del algoritmo. Figura 4.17. Ejemplo de sello incapaz de ser detectado por el algoritmo actual En el segundo ejemplo, la región detectada incluye además del sello todo el texto que le rodea por encontrarse demasiado próximo. Esto invalida todas las pruebas siguientes. 21 21 Reconocimiento de Sellos en Legajos de Archivo Histórico 4.2.4 Conclusiones sobre segmentación Por un lado disponemos de detección de características, un sistema que parece funcionar muy bien pero que requiere una imagen previa de cada sello. Por otro lado tenemos componentes conexas, que no es robusto para la totalidad de los casos. La solución propuesta final consiste en utilizar componentes conexas para extraer una muestra de cada sello y a continuación emplear detección de características a partir de la base de datos de sellos obtenida para localizar la posición del sello a la vez que clasificarlo. El algoritmo se divide de esta manera en dos fases: 1. Fase heurística, en la que se emplea componentes conexas y una serie de filtros heurísticos con el objetivo de conseguir al menos una muestra de cada uno de los sellos 2. Fase de extracción de características, donde se emplean los prototipos de sellos hallados para localizar y reconocer los sellos, si los hubiera, de cada uno de los documentos. 4.2.5 Notas sobre la segmentación mediante transformada de Hough Con inspiración en la literatura especializada [4] se experimentó con un método basado en la transformada de Hough. Los sellos no presentan, en un caso general ninguna curva de parametrización sencilla. Aun así, pueden estar presentes en algunos casos elementos similares a circunferencias o elipses. Se prueba a buscar estas formas geométricas en los documentos y se obtienen los resultados siguientes. Figura 4.18. Resultados de la transformada de Hough para círculos. Bajando lo suficiente el umbral, el sistema detecta correctamente algunas de las formas en el sello, sin embargo, esto hace aparecer formas por toda la imagen. Como cabía esperar, la transformada de Hough no supone un método robusto para abordar el problema que se presenta. Esto se debe a que los sellos no presentan, en el caso general, formas geométricas sencillas. Menos aún existe parametrización alguna de alguna curva que sea útil en la generalidad de los casos presentes. 4.3 Pasos restantes de un OCR estándar. Separación de líneas y palabras y sistema de reconocimiento En el caso del problema expuesto, no estamos tratando de transcribir un texto. Es por ello que, supuesta resuelta la segmentación, no parece necesario estudiar sistemas para separar líneas, y menos palabras. En cuanto al sistema de reconocimiento, en el caso dado debe clasificar de qué sello en cuestión se trata. Como ya se ha mencionado el sistema de extracción de características realizará esta función. Como se aclaró al exponer el esquema estándar de un sistema de OCR, rara vez se implementa el modelo tal Esquema general de un ocr 22 cual. Es bastante frecuente que se omita alguno de los pasos o incluso que se agreguen pasos adicionales. En general en el campo de la visión artificial es poco frecuente encontrar soluciones multipropósito para un problema y por lo tanto, tampoco es común que todas las soluciones se adapten a un esquema rígido. 23 5 FASE HEURÍSTICA l objetivo de esta fase es encontrar al menos una muestra de todos y cada uno de los sellos que aparecen en el archivo de documentos. Estas muestras van destinadas a alimentar el sistema de extracción de características. La idea es que se cataloguen manualmente antes de la siguiente fase una vez extraídas. Esto no supone un trabajo redundante ya que la primera fase reduce el proceso de catalogación manual a unas pocas imágenes que además se encuentran ya recortadas de los documentos. Nótese que para el correcto funcionamiento del sistema global el hecho de que existan algunos falsos positivos en esta primera fase no es un gran problema mientras que el hecho de que algún sello no sea encontrado supone un fallo insalvable. Los falsos positivos pueden eliminarse durante la catalogación siempre y cuando supongan un número razonablemente pequeño. La descripción de esta etapa se hará describiendo cronológicamente su desarrollo, los resultados que se obtuvieron y cómo evolucionó en complejidad para mejorarlos. El algoritmo comienza con los siguientes pasos. 5.1 Crear e inicializar objeto documento class Documento: img = np.array([]) path = "" bin_img = np.array([]) bin_thresh = 0 kernel = np.ones((11, 11), np.uint8) label_img = np.array([]) regions = [] seals = [] has_2_pages = False lines_y = np.array([]) def __init__(self): del self.regions[:] del self.seals[:] self.lines_y = np.array([[]]) Las variables miembro se han creado como variables de clase y no de objeto ya que sólo va a haber una instancia de la clase Documento en todo momento. Esto no significa que se vaya a definir como singleton, ya que los mecanismos que el lenguaje provee para construir este patrón lo hacen engorroso sin gran ventaja para el caso expuesto. Para la inicialización es necesario vaciar las listas y arrays mostrados ya que éstos se van a construir añadiendo elementos en forma de cola. E Que las matemáticas son una ciencia deductiva es un cliché. En realidad consisten en prueba y error. - Paul Halmos - Fase heurística 30 30 5. Si fuera mayor de lo deseado, se procedería a repetir los pasos 2 a 4, con la diferencia de que el nuevo umbral a utilizar sería uno menos "symm_recheck_thresh". El motivo por el que son necesarias estas comprobaciones adicionales es porque el test de simetría es altamente sensible al ruido. Cualquier mancha adicional añadida a la región hace que la división vertical no coincida con la mitad del sello y por tanto se obtienen ratios muy inferiores a los esperados. Igualmente, cualquier elemento que le falte al sello debido a un umbral demasiado restrictivo produce el mismo efecto. def symmetry(self): minr = self.region.minr maxr = self.region.maxr minc = self.region.minc maxc = self.region.maxc seal_img = self.document.bin_img[minr:maxr, minc:maxc] ratio = self.symmetry_ratio(seal_img) if ratio < Region.settings.get("symmetry_ratio_thresh"): thickness = Region.settings.get("symm_recheck_enlargement_px") enlarged_img = self.document.img[abs(minr - thickness):maxr + thickness, abs(minc - thickness):maxc + thickness] enlarged_img_coords = [minr - thickness, maxr + thickness, minc - thickness, maxc + thickness] dark_thresh = self.document.bin_thresh * (1 + Region.settings.get("symm_recheck_thresh")) darker_seal_img = (enlarged_img < dark_thresh).astype('uint8') * 255 cropped_img, new_coords = Region.Bbox.detectar_bbox(darker_seal_img, enlarged_img_coords) ratio = self.symmetry_ratio(cropped_img) if ratio < Region.settings.get("symmetry_ratio_thresh"): light_thresh = self.document.bin_thresh * (1 - Region.settings.get("symm_recheck_thresh")) lighter_seal_img = (enlarged_img < light_thresh).astype('uint8') * 255 cropped_img, new_coords = Region.Bbox.detectar_bbox(lighter_seal_img, enlarged_img_coords) ratio = self.symmetry_ratio(cropped_img) if ratio < Region.settings.get("symmetry_ratio_thresh"): self.passed_tests.update({"filled_area": False}) else: self.passed_tests.update({"filled_area": True}) self.region.minr = new_coords[0] self.region.maxr = new_coords[1] self.region.minc = new_coords[2] self.region.maxc = new_coords[3] else: self.passed_tests.update({"filled_area": True}) self.region.minr = new_coords[0] self.region.maxr = new_coords[1] self.region.minc = new_coords[2] self.region.maxc = new_coords[3] Una vez que tenemos los cuatro filtros, se procede a aplicar los que hubiese activos. def apply_active_tests(self): """ Aplica aquellos test que hubiera activos. En caso de que la región supere todos, es añadida a la lista de sellos del documento al que pertenece la 31 31 Reconocimiento de Sellos en Legajos de Archivo Histórico región en cuestión. """ self.region.region_is_seal = True if self.region.test.active_tests.get("area") is True: self.region.test.area() self.region.region_is_seal *=/ self.region.test.passed_tests.get("area") if self.region.test.active_tests.get("aspect_ratio") is True: self.region.test.aspect_ratio() self.region.region_is_seal *=/ self.region.test.passed_tests.get("aspect_ratio") if self.region.test.active_tests.get("filled_area") is True: self.region.test.filled_area_ratio() self.region.region_is_seal *=/ self.region.test.passed_tests.get("filled_area") if self.region.test.active_tests.get("symmetry") is True: self.region.test.symmetry() self.region.region_is_seal *=/ self.region.test.passed_tests.get("symmetry") if self.region.region_is_seal: self.document.seals.append(self.region) 5.6 Primeros resultados obtenidos Los primeros resultados ofrecen una evidencia clara: el test de simetría no es útil. No sólo existen múltiples sellos que no tienen una gran simetría sino que es frecuente que palabras o grupos de palabras que poseen una simetría anormalmente elevada. Para expresar los resultados se han utilizado las siguientes definiciones:  Precisión: Porcentaje de los elementos detectados que suponen detecciones acertadas.  Exhaustividad: Porcentaje de la totalidad de casos positivos que han sido detectados. Por tanto, tras desactivar dicho filtrado se obtienen los siguientes resultados. Precisión 35.9% Exhaustividad 84.85% Protitipos de sellos encontrados4 100% Ya se ha conseguido el objetivo principal, obtener una copia de cada sello. Sin embargo, el número de falsos positivos es demasiado alto lo que podría ser un engorro a la hora de emplear este método. Esto se refleja en una bajísima precisión. El objetivo ahora es disminuir el número de falsos positivos sin eliminar positivos reales. 5.7 Test de posición Una buena parte de los sellos se encuentra en la parte superior del documento. Por ello, se planteó eliminar falsos positivos mediante un nuevo filtro que eliminase todos los positivos que se tuviesen una coordenada “y” superior a un cierto umbral. Sin embargo, existen algunos pocos sellos que no cumplen esta condición. Ya que se quiere priorizar localizar el mayor número posible de sellos sobre eliminar falsos positivos y que no se puede garantizar que esta condición vaya a cumplirse para otros conjuntos de documentos, se desestima el uso 4 Porcentaje de los distintos tipos sello existente de los cuales se ha encontrado al menos una copia. Fase heurística 32 32 de este filtro. 5.8 Eliminación de sellos contenidos en otros Existe un caso concreto en el cual dos regiones son detectadas como sello estando una contenida dentro de la otra. Figura 5.5. Sello detectado contenido dentro de otro sello. Esto ocurre porque la mayor es lo suficientemente grande como para contener otra región que también lo sea. Existe una pequeña probabilidad de que la detección de colisiones unifique por separado dos conjuntos de regiones, uno contenido dentro de otro. Una segunda pasada del detector eliminaría el problema. Tendría coherencia eliminar estos casos en la propia detección de colisiones, sin embargo, allí aún no se ha eliminado ninguna región y el número total suele ser del orden de 103-104 antes del filtrado por área. Esto significa que unificar sellos que están contenidos en otros como uno solo supone realizar un número mucho mayor de operaciones en esa sección del código. Por lo tanto, se elimina aquí, después de pasar los test. En este caso se prioriza eficiencia sobre coherencia del código por el gran beneficio obtenido. Figura 5.6 Sello detectado contenido eliminado. 5.9 Transformaciones morfológicas Existen multitud de imágenes que presentar ruido que se corresponden con suciedad o envejecimiento del papel y que no contienen información. También se dan casos en los que la binarización elimina demasiada tinta y quedan regiones separadas que deberían estar juntas. Este último caso se solventa en cierta medida en el detector de colisiones entre regiones. Sin embargo, la capacidad para resolverlo ahí es limitada ya que unificar regiones demasiado separadas es propenso a la unificación de regiones que deberían estar separadas, especialmente cuando ambas regiones en cuestión poseen grandes dimensiones. Para resolver todos estos problemas se realizan transformaciones morfológicas sobre la imagen binarizada con el objetivo tanto de eliminar ruido como de unificar regiones que no deben estar separadas. Para no eliminar demasiados píxeles o no unificar en exceso, es necesario ajustar los parámetros de manera adecuada. Esto se ha llevado a cabo con la ayuda del siguiente script 33 33 Reconocimiento de Sellos en Legajos de Archivo Histórico import cv2 import paths img_path = paths.path_to_imgs + '/1863-L119.M13/107/IMG_0002.png' img = cv2.imread(img_path, cv2.IMREAD_GRAYSCALE) img2 = cv2.GaussianBlur(img, (3, 3), 0) bin_thresh, bin_img = (cv2.threshold(img, 0, 1, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)) bin_thresh, bin_img2 = cv2.threshold(img2, 0, 1, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU) se1 = cv2.getStructuringElement(cv2.MORPH_RECT, (25, 25)) se2 = cv2.getStructuringElement(cv2.MORPH_RECT, (10, 10)) mask = cv2.morphologyEx(bin_img, cv2.MORPH_CLOSE, se1) mask = cv2.morphologyEx(mask, cv2.MORPH_OPEN, se2) out = img * mask out = (out > 5).astype('uint8') cv2.namedWindow("img", cv2.WINDOW_NORMAL) cv2.imshow("img", bin_img*255) cv2.namedWindow("img2", cv2.WINDOW_NORMAL) cv2.imshow("img2", bin_img2*255) cv2.waitKey() El código permite modificar los parámetros de las transformaciones además de la imagen escogida para los experimentos y visualizar los resultados obtenidos. Copiar y pegar código en distintas partes de un proyecto nunca es buena idea ya que cualquier edición necesaria en dicho código se vuelve muy engorrosa. Se hace necesario ir buscando todos los lugares donde ese código aparece y pegar la nueva solución. La situación es aún peor cuando algunos de esos sitios son pasados por alto, lo que hace que existan distintas versiones de lo que debería ofrecer el mismo comportamiento. El resultado es lo que se conoce como spaghetti code, que genera un proyecto muy difícil de hacer evolucionar y con múltiples errores. Dicho esto, nuestro script para testear parámetros no va a formar parte del código del proyecto y hubiese sido eliminado de no ser por la necesidad de añadirlo aquí. En este caso copiar y pegar es perfectamente aceptable mientras que importar este archivo sería erróneo. 5.10 Separación de líneas Es muy frecuente que los falsos positivos provengan de conjuntos de palabras de varias líneas. Como se vio en la figura de los ratios de relleno, no existe un umbral para este parámetro que nos permita eliminar la totalidad de falsos positivos y quedarnos con todos los sellos reales. Por ello, se ha implementado un sistema capaz de estimar las coordenadas verticales de los huecos que separan líneas de texto. Para realizar esta tarea, se realiza un conteo de cuántos píxeles blancos existen en la imagen binaria en cada una de sus filas. Con esta información se construye un histograma de píxeles por fila. Fase heurística 34 34 Figure 5.7. Documento junto con su histograma horizontal. De este histograma nos interesa hallar los mínimos locales. Sin embargo puede verse que existe un gran número de mínimos que no nos resultan interesantes. Antes de realizar ninguna operación necesitamos definir qué necesitamos para poder obtener los mínimos que queremos.  Que la serie de puntos tuviese una derivada más o menos continua (dentro del hecho de que tanto en dominio como en imagen la función se encuentra muestreada).  Que los mínimos que localicemos se encuentren al menos separados una cierta distancia, para garantizarnos que no corresponden a la misma línea. Para conseguir estos objetivos, hacemos pasar los datos por un filtro de paso bajo. Se ha escogido el filtro de Savitzky-Golay ya que posee la ventaja de mantener la forma y características de la señal original mejor que otros tipos de filtrados, como los basados en técnicas relacionadas con medias móviles [9]. La idea detrás del enfoque de este filtro es hacer para cada punto un ajuste por mínimos cuadrados con un polinomio de alto orden sobre una ventana de dimensión impar centrada en el punto [10]. @staticmethod def savitzky_golay(y, window_size, order, deriv =0, rate=1): """ Parameters ---------- y : array_like (numpy, lista...), forma (N,) valores de la señal. window_size : int tamaño de la imagen. Debe ser un entero impar. order : int orden del polinomio a utilizar. Debe de ser menor de `window_size` - 1. deriv: int orden de la derivada a calcular (por defecto = 0 significa sólo ajustar, no derivar) Returns ------- ys : ndarray, forma (N) señal suavizada (o su n-ésima derivada). """ from math import factorial 35 35 Reconocimiento de Sellos en Legajos de Archivo Histórico try: window_size = np.abs(np.int(window_size)) order = np.abs(np.int(order)) except ValueError as msg: raise ValueError("window_size and order have to be of type int") if window_size % 2 != 1 or window_size < 1: raise TypeError("window_size size must be a positive odd number") if window_size < order + 2: raise TypeError("window_size is too small for the polynomials order") order_range = range(order + 1) half_window = (window_size - 1) // 2 # precomputar coeficientes b = np.mat([[k ** i for i in order_range] for k in range(-half_window, half_window + 1)]) m = np.linalg.pinv(b).A[deriv] * rate ** deriv * factorial(deriv) # acomodar la señal en los extremos con valores tomados de la propia señal firstvals = y[0] - np.abs(y[1:half_window + 1][::-1] - y[0]) lastvals = y[-1] + np.abs(y[-half_window - 1:-1][::-1] - y[-1]) y = np.concatenate((firstvals, y, lastvals)) return np.convolve(m[::-1], y, mode='valid') Figure 5.8. Detalle del histograma ajustado. En rojo la señal original y en azul la señal filtrada. Una vez tenemos la señal filtrada, procedemos a encontrar los mínimos, eliminando aquellos que estén demasiado próximos. Para lograr esto, primero se toman todos los puntos que cumplen la condición de que son menores que sus dos puntos vecinos. Después, se ordenan de menor a mayor. El primero se toma como mínimo garantizado y se añade a una lista de mínimos. A partir de ahí, se recorre la lista y para cada siguiente elemento se comprueba su distancia con todos aquellos que ya han sido añadidos a la lista de mínimos. Si la distancia con todos ellos es mayor que un umbral prefijado se añade este punto a la lista de mínimos. Para calcular este umbral, se ha visto cuáles son las separaciones típicas entre líneas en píxeles, y se ha dividido por la mitad este valor. @staticmethod def find_min(a): """ Encontrar el mínimos en array 'a'. Si entre mínimo y mínimo hay menos de min_lin_dist_px píxeles se ignora el más grande de los dos. :param a: Array to find local minima in. :return: Indexes of local minima in array Fase heurística 36 36 """ # take those points which are smaller than their immediate neighbours is_min = np.r_[True, a[1:] < a[:-1]] & np.r_[a[:-1] < a[1:], True] min_points = [] true_mins = [] min_dist = LineSeparator.settings.get("min_lin_dist_px") for i, value in enumerate(a): if is_min[i]: min_points.append((i, value)) min_points.sort(key=lambda p: p[1]) # lambda function tells sort() which number of the tuple to use. We want to sort using y value. if len(min_points) > 0: true_mins.append(min_points[0]) for point in min_points[1:]: too_close = False for true_min in true_mins: dist = abs(point[0] - true_min[0]) if dist < min_dist: too_close = True if not too_close: true_mins.append(point) return true_mins Esta búsqueda de mínimos devuelve los siguientes resultados: Figura 5.9. En verde, mínimos encontrados en la señal filtrada En rojo, falsos positivos (seleccionados manualmente). Como puede verse, existen algunos falsos positivos. Éstos tienen valores claramente diferentes y además no son numerosos. Estas cualidades hacen fácil su eliminación. Para conseguirlo se ha empleado un método basado en la desviación de la mediana [11]. def is_outlier(points, thresh=2.0035): """ Returns a boolean array with True if points are outliers and False otherwise. Parameters: 37 37 Reconocimiento de Sellos en Legajos de Archivo Histórico ----------- points : An numobservations by numdimensions array of observations thresh : The modified z-score to use as a threshold. Observations with a modified z-score (based on the median absolute deviation) greater than this value will be classified as outliers. NOTE: Thresh estimated from average of min and max thresholds that would filter properly for test image. Returns: -------- mask : A numobservations-length boolean array. if len(points.shape) == 1: points = points[:, None] median = np.median(points, axis=0) diff = np.sum((points - median) ** 2, axis=-1) diff = np.sqrt(diff) med_abs_deviation = np.median(diff) if med_abs_deviation == 0: return np.ones(len(points), dtype=np.bool) else: modified_z_score = 0.6745 * diff / med_abs_deviation return modified_z_score > thresh Como indica la docstring, el parámetro thresh se ha obtenido probando distintos umbrales. El umbral empleado resulta de la media entre el mayor y menor umbral que filtraban correctamente en una imagen de prueba. Los resultados de este filtrado se muestran a continuación. Figura 5.10. En rojo los mínimos que no han pasado el filtro. Aún no hemos terminado. Muchos de los documentos poseen dos páginas. Las páginas de cada uno de los documentos no tienen porqué tener líneas coincidentes, de hecho rara vez ocurre. Por lo tanto es necesario dividir el documento en dos si este fuera el caso. Esto se hace calculando el histograma de píxeles, esta vez sobre el eje horizontal. Sólo se hace en el tercio central de la imagen, ya que fuera de este intervalo nunca Fase heurística 38 38 estará la separación buscada. Se convierte en cero entonces todo valor del histograma menor de 10, para eliminar el efecto del ruido. Entonces se busca la mayor racha consecutiva de valores. Si ésta resulta ser de ceros y además es mayor que 1/7 del ancho de la imagen, se establece que es una separación entre páginas. def longest_streak(a): """ Finds longest streak in a list or numpy array :param a: list or numpy array :return: longest streak found """ lst = [] for n, c in groupby(a): streak = list(c) if len(streak) > len(lst): lst = streak return lst def has_two_pages(bin_img): """ Return true if the longest streak in a vertical projection is made on zeros and is longer than 1/7 of the document width :param bin_img: Document image to compute if it has two pages or not, in binary format :return: True if it has 2 pages, False otherwise. It is based on the assumption of 2 pages max per image. """ first_col = int(bin_img.shape[1] / 3) last_col = int(2 * bin_img.shape[1] / 3) hist = LineSeparator.proyect(bin_img[:, first_col:last_col], LineSeparator.axis["vertical"]) for i, el in enumerate(hist): if el <= 10: hist[i] = 0 max_streak = LineSeparator.longest_streak(hist) if max_streak[0] == 0 and len(max_streak) > int(bin_img.shape[1] / 7): return True else: return False Figura 5.11. Resultado de division en páginas y líneas. 39 39 Reconocimiento de Sellos en Legajos de Archivo Histórico 5.11 Algoritmo final para la fase heurística El algoritmo definitivo quedaría así. Para cada imagen de documento al que se le quiera detectar su/s posible/s sello/s. El resultado tras este proceso son las coordenadas de los posibles sellos del documento dado. En el código mostrado a continuación, se han utilizado estos datos obtenidos para almacenarlos en la base de datos (y así poder extraer estadísticas sobre la calidad de los resultados). Además, se almacena una copia de cada fragmento de imagen que se halla determinado que podría ser un sello. Esto es necesario para poder efectuar la fase dos. import os import cv2 from Database import DatabaseHeur import SellosHeuristica as Sh import paths path = paths.path_to_imgs walk = os.walk(path) db = DatabaseHeur('docs_osborne', 'testuser', 'test123', 'heur_results6') i = 0 for root, dirs, files in walk: for curr_file in files: if not curr_file.endswith(".png") or curr_file.startswith("."): continue img_path = root + '/' + curr_file print(img_path) documento = Sh.Documento() documento.load_img(img_path) documento.get_bin_img() documento.get_lines() documento.get_regions() for region in documento.regions: Crear e inicializar documento Cargar la imagen al documento Obtener imagen binaria Obtener coordenadas de las líneas del documento Obtener regiones Para cada región -> Aplicar test activos Eliminar regiones contenidas dentro de otras Fase de extracción y comparación de características 46 46 6.3.1 Búsqueda de puntos clave En SIFT, Lowe aproxima el laplaciano del gaussiano mediante una diferencia de gaussianos con el objetivo de trasladar la búsqueda de puntos clave al espacio de escalas. SURF va un paso más allá aproximando el LdG mediante lo que denominan ellos un filtro de cajas. La imagen inferior ilustra una demostración de dicha aproximación. En la imagen derecha se muestra el resultado de cada una de las dos derivadas segundas parciales de la imagen original y a la izquierda la matriz utilizada como kernel de convolución para aproximar dicha derivada. Una gran ventaja de esta aproximación es que la convolución con estas “cajas” puede calcularse de manera muy rápida con ayuda de imágenes integrales. También puede realizarse en paralelo de manera independiente para distintas escalas. Por otra parte, SURF utiliza el determinante de la matriz Hessiana tanto para la escala como para la localización, disminuyendo por tanto el número de cálculos necesarios. 6.3.2 Cálculo de la orientación Para asignar una orientación, SURF utiliza las respuestas a wavelets (en concreto la Transformada de Wavelet de Haar o HWT por sus siglas en inglés) en las direcciones tanto en horizontal como vertical para una vecindad de dimensión 6*s, donde s es la dimensión del punto calculado (no necesariamente tiene que ser un único píxel). A cada una de esas respuestas se las pondera con una adecuada función gaussiana. A continuación, se las sitúa en el espacio tal y como se aprecia en la imagen inferior. La orientación dominante se calcula sumando las respuestas que se encuentran en una abertura de 60º. Es interesante destacar que las respuestas a wavelets también se pueden calcular fácilmente mediante el uso de imágenes integrales para cualquier escala. También cabe destacar que los descriptores son independientes de esta orientación, por lo tanto, se puede prescindir de este cálculo. En nuestro caso, la invariancia a la rotación no es necesaria ya que se trata de documentos que siempre van a ser escaneados con la misma orientación. Este método es denominado Upright-SURF, o U-SURF. Mejora la velocidad de manera notable y proporciona robustez con una precisión de ±15º. Ese será el método que utilizaremos nosotros ya que los sellos pueden estar ligeramente rotados pero no nos importa calcular cuál es el valor de dicha rotación. 6.3.3 Asignación de descriptores Para la descripción de características, SURF utiliza respuestas a wavelet de Haar en las direcciones horizontal y vertical, nuevamente con ayuda de las imágenes integrales. Se toma una vecindad de 20sx20s alrededor del punto (donde s es nuevamente la dimensión del punto calculado). Esta región se divide en subregiones de 4x4. Para cada una de ellas, se calcula la respuesta a wavelet nuevamente en ambas direcciones y se crea un vector de la siguiente manera: 𝑣= ( 𝑑𝑥, 𝑑𝑦, 𝑑𝑥 , 𝑑𝑦 ) Todos estos vectores colocados de manera consecutiva como un único vector suponen un descriptor del punto con una dimensión de 64 valores. Menor dimensión significa mayor velocidad en computación además de en el emparejamiento posterior. Si mayor distinción para los descriptores de cada punto fuera necesaria, SURF proporciona la posibilidad de aumentar la dimensión de dichos descriptores a 128 calculando por separado las sumas de las distintas respuestas: tanto dx como |dx| se suman por separado en función de si su respectivo dy es positivo o negativo. Para dy se hace lo mismo. 6.3.4 Afinamiento de emparejamiento de puntos Para mejorar el futuro emparejamiento SURF ofrece además otra mejora. Utilizando el signo del laplaciano (que es el mismo que la traza de la matriz hessiana) para cada punto de interés. No supone ningún aumento del coste computacional ya que dicha matriz ha sido ya calculada durante la fase de detección. El signo del 47 47 Reconocimiento de Sellos en Legajos de Archivo Histórico laplaciano sirve para distinguir si el punto de interés supone una región clara sobre fondo oscuro o al contrario. Durante el emparejamiento sólo tenemos que comparar puntos en los cuales este valor coincida, mejorando tanto la precisión del emparejamiento como la velocidad con la que se ejecuta. 6.3.5 Comparativa con SIFT Las pruebas demuestran que SURF supone un incremento de velocidad considerable con una precisión comparable con SIFT. SURF demuestra ser robusto ante rotación y desenfoque, sin embargo, no es muy bueno ante cambios de iluminación y de cambios en puntos de vista [18]. Esto no supone ningún problema para nuestro caso. 6.4 ORB Como alternativa a ambos expuestos anteriormente, se desarrolló un algoritmo que fuera libre. En 2011 Ethan Rublee, Vincent Rabaud, Kurt Konolige y Gary R. Bradski publicaron un artículo titulado “ORB: An efficient alternative to SIFTor SURF” [19]. Básicamente ORB supone una fusión entre el detector de puntos clave FAST y el generador de descriptores BRIEF con modificaciones múltiples con el objetivo de mejorar el rendimiento. En un primer paso, utiliza FAST para encontrar los puntos. Después, aplica un detector de esquinas Harris con el objetivo de localizar los máximos N valores entre los puntos obtenidos previamente. Esto elimina los puntos encontrados con FAST que no posean suficiente contraste. Se utiliza además una pirámide para calcular propiedades multiescala. Un problema importante es que FAST no computa ningún valor que nos proporcione información sobre la orientación. Para conseguir invarianza ante la rotación los autores añadieron la siguiente modificación. Se computa el centroide ponderado de la región en cuyo centro se encuentra el punto clave en cuestión. El vector que va desde el centro hasta este centroide nos proporciona la orientación. Para mejorar este valor, se computan además los momentos dentro de una región circular centrada en el punto. Ahora, para los descriptores se hace uso de BRIEF. Nuevamente, BRIEF responde de manera pobre con respecto a la rotación, esto para el caso expuesto no supone un problema. Aún así, ORB soluciona este problema “orientando” BRIEF en la dirección calculada previamente. Para cada punto, se toma la vecindad necesaria y se rota multiplicando las coordenadas por la matriz de rotación correspondiente. ORB discretiza en incrementos de 12º y construye una tabla de búsqueda de patrones BRIEF precomputados. Siempre y cuando la orientación utilizada inicialmente sea correcta, los valores del descriptor serán robustos con respecto a la rotación. Una propiedad importante de BRIEF es que cada propiedad binaria obtenida tiene una alta varianza pero la media permanece cerca de 0.5. Pero una vez orientado con respecto a la dirección del punto clave esta propiedad se pierde y se vuelve más distribuido. Alta varianza significa que es el descriptor mucho más distintivo ya que responde de manera distinta ante la entrada de distintos puntos. Otra propiedad deseable sería que los test no estuvieran correlados ya que entonces cada test realizado contribuiría al resultado final. Para resolver todo esto ORB realiza una búsqueda voraz entre todos los posibles test binarios para encontrar aquellos que tienen gran varianza y media cercana a 0.5, además de no tener correlación entre sí. El resultado se denomina rBRIEF. Para el emparejamiento de descriptores, se utiliza un LSH (del inglés Locality-Sensitive Hashing) el cual mejora los resultados con respecto al LSH original. Fase de extracción y comparación de características 48 48 6.5 Elección del método Para determinar qué método emplear, se han realizado dos pruebas. La primera escogiendo sellos modelo y documentos que coinciden y contabilizando la cantidad de matches de puntos clave con cada uno de los métodos, además del porcentaje de puntos emparejados erróneamente. Es decir, se han tenido en cuenta tanto la habilidad para detectar puntos clave como la calidad de los descriptores asignados a cada uno de esos puntos. Los falsos emparejamientos se han medido contando los matches que se realizan fuera del sello. Esta medida no es completamente precisa ya que puede haber matches erróneos dentro del sello, sin embargo, supone una aproximación bastante práctica y ahorra la necesidad de revisar los cientos de matches uno por uno. La segunda prueba consiste en hacer pasar a cada uno de los métodos de extracción de características por la totalidad de imágenes de documentos escaneadas ignorando la calidad de los resultados sin implementar nigún sistema para eliminar los emparejamientos erróneos, con el único objetivo de medir el tiempo de ejecución. Las conclusiones a las que se han llegado son las siguientes: SIFT Puntos clave detectados 372 Porcentaje de matches erróneos 5.38% Tiempo total de ejecución 7.41h SURF Puntos clave detectados 309 Porcentaje de matches erróneos 4.85% Tiempo total de ejecución 2.65h ORB Puntos clave detectados 110 Porcentaje de matches erróneos 7.27% Tiempo total de ejecución 8.21*10−2h Puede verse como ORB se ejecuta varios órdenes de magnitud más rápido que sus dos competidores. Sin embargo, la calidad de los resultados obtenidos no es tan buena. Cabe destacar que se ha empleado un matcher de fuerza bruta para hallar los descriptores más parecidos en el caso de ORB, que es mucho más lento. En cuanto a SURF, se ejecuta varias veces más rápido sin que eso repercuta en la calidad de los datos que devuelve con respecto a SIFT. Es el resultado que cabía esperar de acuerdo a la literatura, ya que no se esperan grandes cambios en la perspectiva o iluminación de los sellos [18]. Por todo esto, se ha optado por elegir SURF como método para abordar el problema. Para eliminar los falsos positivos, en el algoritmo final se ha empleado información sobre la posición en la que se han encontrado los puntos clave y se ha decidido que aquellos que se alejen de la nube de puntos principal, son outliers. En caso de que esa nube principal no contenga suficientes puntos con respecto al total extraído de cada sello modelo original, se considera que el documento no posee ningún sello. A continuación se define en profundidad el proceso final diseñado. 49 49 Reconocimiento de Sellos en Legajos de Archivo Histórico 6.6 Descripción del algoritmo Los objetivos son: detectar de qué sello se trata, localizar su posición y devolver una imagen sin sello. Esto es así porque para otras tareas de reconocimiento es deseable disponer de una imagen sin elementos gráficos. Una vez que disponibles los prototipos de sellos, se necesita tener una base de datos de los keypoints y descriptores de cada sello para después emplear esta información para comparar con cada uno de los documentos. De esta manera, esta fase se divide a su vez en dos pasos: la obtención de la base de datos de características y el uso de esta base para resolver el problema. Para obtener la base de datos se extraen los datos de cada una de las imágenes de sellos guardadas y se serializan y almacenan en un archivo utilizando Numpy. La siguiente clase permite la escritura y lectura de estos datos. import numpy as np import os import cv2 class FeaturesIO: @staticmethod def write_features_to_file(filename, locs, desc, shape): np.savez(filename, np.hstack((locs, desc)), shape) @staticmethod def pack_keypoint(keypoints, descriptors): kpts = np.array([[kp.pt[0], kp.pt[1], kp.size, kp.angle, kp.response, kp.octave, kp.class_id] for kp in keypoints]) desc = np.array(descriptors) return kpts, desc @staticmethod def unpack_keypoint(file): seals_kps = [] seals_des = [] array = file['arr_0'] num_elements = len(array) for i in range(0, int(num_elements/2)): kpts = array[i] keypoints = [cv2.KeyPoint(x, y, _size, _angle, _response, int(_octave), int(_class_id)) for x, y, _size, _angle,_response, _octave, _class_id in list(kpts)] seals_kps.append(keypoints) for i in range(int(num_elements/2), num_elements): desc = np.array(array[i]).astype(np.float32) # float32 for surf; uint8 for ORB seals_des.append(desc) seal_shps = file['arr_1'] return seals_kps, seals_des, seal_shps @staticmethod def process_and_save(path, resultname, detector): walk = os.walk(path) all_k = [] all_d = [] all_s = [] Fase de extracción y comparación de características 50 50 for root, dirs, files in walk: for curr_file in files: if not curr_file.endswith(".png") or curr_file == "no_seal.png": continue # print(curr_file) img = cv2.imread(path + '/' + curr_file, 0) k = detector.detect(img, None) if len(k) > 0: k, des = detector.compute(img, k) else: des = [] k, des = FeaturesIO.pack_keypoint(k, des) all_k.append(k.tolist()) all_d.append(des.tolist()) all_s.append(img.shape) FeaturesIO.write_features_to_file(resultname, all_k, all_d, all_s) @staticmethod def load_features(filename): file = np.load(filename) kp, des, shps = FeaturesIO.unpack_keypoint(file) return kp, des, shps Su uso para almacenar puntos se muestra a continuación: from FeaturesIO import FeaturesIO as FtIO import FeaturesDetector import paths path = paths.path_to_prototypes surf = FeaturesDetector.create_detector() FtIO.process_and_save(path, "car_sellos", surf) Para empleado una clase que se ha denominado EliminacionSellos y se ha creado una instancia de dicha clase para cada sello. Esta clase se describe un poco más adelante. Se recuerda que las variables de clase poseen un valor común para todos los objetos de la clase y editarlas en uno de ellos afecta a todas las instancias de la clase, mientras que las variables de objeto son únicas para cada instancia. Se ha creado una estructura a la que se ha denominado matriz de acumulación de evidencias o matriz de evidencias por simplicidad. Para crear esta matriz, la imagen original se subdivide por una constante N prefijada. De esta forma, cada una de sus celdas de la nueva matriz corresponderá a un grupo de píxeles (H/N)x(W/N) del documento (salvo el borde final, que podrá ser menor), donde H y W son el alto y ancho de la imagen respectivamente. Cada celda de esta matriz poseerá un valor entero igual al número de keypoints que han sido emparejados dentro de esta celda. 6.6.1 Descripción de la clase EliminacionSellos class EliminacionSellos: doc_img = 0 doc_kps = [] doc_des = [] kps_saved = [] 51 51 Reconocimiento de Sellos en Legajos de Archivo Histórico desc_saved = [] seals_dims = [] surf = FeaturesDetector.create_detector() def __init__(self, img, index): EliminacionSellos.doc_img = img.copy() self.kp_matched = [] self.evidence_matrix = em.EvidenceMatrix(img.shape) self.position = (0, 0) # position is (rows, cols), therefore, (y, x) self.max_occurrences = 0 self.index = index self.total_matches = 0 def get_keypoints_from_db(self, path): EliminacionSellos.kps_saved, EliminacionSellos.desc_saved, EliminacionSellos.seals_dims\ = FeaturesIO.load_features(path) def get_document_features(self): EliminacionSellos.doc_kps, EliminacionSellos.doc_des =\ EliminacionSellos.surf.detectAndCompute(EliminacionSellos.doc_img, None) def get_matched_keypoints(self): # FLANN parameters FLANN_INDEX_KDTREE = 0 index_params = dict(algorithm=FLANN_INDEX_KDTREE, trees=5) search_params = dict(checks=50) # or pass empty dictionary flann = cv2.FlannBasedMatcher(index_params, search_params) aux_kp = [] matches = flann.knnMatch(EliminacionSellos.desc_saved[self.index], EliminacionSellos.doc_des, k=2) for j, (m, n) in enumerate(matches): if m.distance < 0.7 * n.distance: aux_kp.append(EliminacionSellos.doc_kps[m.trainIdx]) self.kp_matched = aux_kp self.total_matches = len(self.kp_matched) def compute_evidence_matrix(self): self.evidence_matrix.calc_occurrences(self.kp_matched) def compute_position_and_max_occurences(self): num_cells = int(self.evidence_matrix.SEAL_DIMENSION / self.evidence_matrix.DIVISION_SIZE) kernel = np.ones((num_cells, num_cells)) occurrences = cv2.filter2D(self.evidence_matrix.evidence_matrix, -1, kernel) self.max_occurrences = np.amax(occurrences) max_index = np.where(occurrences == self.max_occurrences) avg_index = (np.average(max_index[0]), np.average(max_index[1])) final_coords = (int(avg_index[0].item()), int(avg_index[1].item())) self.position = (final_coords[0] * self.evidence_matrix.DIVISION_SIZE, final_coords[1] * Fase de extracción y comparación de características 52 52 self.evidence_matrix.DIVISION_SIZE) def remove_seal(self): cv2.circle(EliminacionSellos.doc_img, (self.position[1], self.position[0]), 200, (255, 0, 255), -1) 6.6.2 Descripción de matriz de acumulación evidencias import numpy as np class EvidenceMatrix: DIVISION_SIZE = 10 SEAL_DIMENSION = 300 # seals are about 300x300px def __init__(self, shape): fils, cols = shape self.evidence_matrix = np.array([]) self.evidence_matrix.resize((fils / EvidenceMatrix.DIVISION_SIZE, cols / EvidenceMatrix.DIVISION_SIZE)) self.evidence_matrix.fill(0) def calc_occurrences(self, keypoints): for kp in keypoints: # points are x, y instead of rows and columns normal = (int(kp.pt[1] / EvidenceMatrix.DIVISION_SIZE), int(kp.pt[0] / EvidenceMatrix.DIVISION_SIZE)) self.evidence_matrix[normal[0], normal[1]] += 1 Variables de objeto •kp_matched: lista de keypoints que han sido emparejados •evidence_matrix: matriz de acumulación de evidencias •position: coordenadas de las dos esquinas opuestas del sello encontrado •max_occurrences: número de emparejamientos máximo en la matriz de evidencias Variables de clase •doc_img: Imagen del documento •doc_kps: Keypoints totales encontrados en el documento •kps_saved: Keypoints almacenados en la base de datos •desc_saved: Descriptores correspondientes a esos keypoints •seals_dims: Dimensiones de los sellos guardados •detector: Detector de características configurado 53 53 Reconocimiento de Sellos en Legajos de Archivo Histórico Figura 6.4. Matriz de evidencias de celdas 100x100px, 10 veces mayores que las empleada. 6.6.3 Algoritmo final Una vez que poseemos un objeto de tipo EliminacionSellos para cada prototipo de sello almacenado, se efectúan las siguientes operaciones. 1. Se cargan los datos de sellos guardados en la base de datos de características. 2. Se calcula la matriz de evidencias para cada uno de ellos y se guarda en cada uno de los objetos creados. 3. Se obtiene el valor máximo de cada matriz de evidencias. 4. Para cada sello almacenado se calcula el ratio de máximo de su correspondiente matriz de evidencias dividido por el número total de correspondencias de puntos obtenidas en el documento. 5. Aquel sello que obtenga el mayor ratio, es el sello que aparece en el documento. Si el mayor ratio es demasiado pequeño, es que no aparece ninguno. import EliminacionSellos as ElimSe def detectar_sello(img, num_elements): elim_sellos = [] for i in range(0, num_elements): elim_sellos.append(ElimSe.EliminacionSellos(img, i)) elim_sellos[0].get_keypoints_from_db('car_sellos.npz') elim_sellos[0].get_document_features() real_seal = -1 max_ratio = 0 for i in range(0, num_elements): elim_sellos[i].get_matched_keypoints() elim_sellos[i].compute_evidence_matrix() elim_sellos[i].compute_position_and_max_occurences() if elim_sellos[i].total_matches > 0: if elim_sellos[i].max_occurrences / elim_sellos[i].total_matches > max_ratio: max_ratio = elim_sellos[i].max_occurrences / len(elim_sellos[i].desc_saved[i]) real_seal = i Fase de extracción y comparación de características 54 54 elim_sellos[real_seal].remove_seal() center_coords = elim_sellos[real_seal].position # (row,col) = (y,x) real_seal_height, real_seal_width = ElimSe.EliminacionSellos.seals_dims[real_seal] div_size = elim_sellos[real_seal].evidence_matrix.DIVISION_SIZE pt1 = (int(center_coords[1] * div_size - real_seal_width / 2), int(center_coords[0] * div_size - real_seal_height / 2)) pt2 = (int(center_coords[1] * div_size + real_seal_width / 2), int(center_coords[0] * div_size + real_seal_height / 2)) corner_coords = [pt1, pt2] if max_ratio < 0.2: real_seal = -1 return elim_sellos[real_seal].doc_img, corner_coords, real_seal, max_ratio 55 7 RESULTADOS Y CONCLUSIONES Ya que el algoritmo consta de dos fases, se discutirá primero los resultados obtenidos en cada una de éstas, para así identificar con mayor facilidad posibles mejoras. 7.1 Resultados de la fase heurística El objetivo principal de esta fase es adquirir de manera automática al menos un prototipo de cada tipo de sello existente en el conjunto de documentos. Sería deseable además, que no se detectase ningún falso positivo. De esta forma el sistema sería totalmente automático. También sería de gran valor que el sistema pudiese distinguir cuáles de los sellos encontrados suponen distintas muestras de el mismo sello, pero para esto es necesario disponer de un sistema eficaz para reconocer qué tipo de sello corresponde a cada uno. Ya que en un primer desarrollo se quiere separar ambar funcionalidades, no se contemplará esta característica a pesar de que en un sistema completamente autónomo sería imprescindible. Se obtienen los siguientes resultados, ya recogidos en el capítulo 5: Precisión 46.67% Exhaustividad 84.85% Prototipos de sellos encontrados 100% La precisión es muy baja debido al elevado número de falsos positivos. La exhaustividad no es del 100% ya que existen algunos sellos que se escapan de la detección, en su mayoría por tener texto escrito encima. El objetivo principal, que es obtener al menos una imagen de cada tipo de sello, se ha conseguido. De hecho, se obtienen múltiples copias de todos aquellos sellos que aparecen en varios documentos (existen algunos que solo aparecen una sola vez). Puede verse que esta fase cumple con los objetivos para nuestro caso en concreto. Para un caso general existe una probabilidad de un 15.15% de que un sello sea erróneamente detectado como que no lo es. Teniendo en cuenta que en nuestro caso existe una probabilidad de un 34.48% de que un sello solo aparezca una sola vez, tenemos que la probabilidad de que un prototipo de sello que solo aparezca una vez sea omitido es de 5.22%. La probabilidad de omitir los sellos que aparecen múltiples veces es aún mucho menor. Por tanto podemos decir que, aunque la enorme cantidad de falsos positivos impide la absoluta autonomía del algoritmo, esta fase funciona de manera satisfactoria. 7.1.1 Posibles mejoras al método heurístico Una mejora clara que podría llevarse a cabo es incrementar el número de parámetros que se miden, esto permite hacer más permisivos el resto de filtros eliminando menos falsos negativos, además de obtener un nuevo filtro que elimine alguno de los falsos positivos existentes. No se ha llevado a cabo ninguna medida sobre los los momentos de las regiones. A pesar de que se haya tenido en cuenta la forma de la región, una región muy alargada puede serlo por la presencia de un pequeño trazo que represente una parte muy La conclusión es aquel punto en el que uno se cansa de pensar. - Martin H. Fischer - Anexos 62 62 self.clock.tick(60) def update_img(self, path): self.doc_img = pygame.image.load(path) self.img_c = self.doc_img.copy() self.scale = 1 self.originx, self.originy = (0, 0) def save_seal(self, name): width = self.pt2x - self.pt1x height = self.pt2y - self.pt1y cropped = pygame.Surface((abs(width), abs(height))) cropped.blit(self.doc_img, (0, 0), (self.pt1x, self.pt1y, width, height)) pygame.image.save(cropped, path_to_seals_db + name + '.png') if __name__ == "__main__": win = WinPygame() while 1: win.main_loop() pygame_functions.py import pygame class PygameFunctions: MOVEMENT_SPEED = 10 SCALE_INCREMENT = 0.05 @staticmethod def move_image(orx, ory): if pygame.key.get_pressed()[pygame.K_LEFT] != 0: orx += PygameFunctions.MOVEMENT_SPEED elif pygame.key.get_pressed()[pygame.K_RIGHT] != 0: orx -= PygameFunctions.MOVEMENT_SPEED if pygame.key.get_pressed()[pygame.K_UP] != 0: ory += PygameFunctions.MOVEMENT_SPEED elif pygame.key.get_pressed()[pygame.K_DOWN] != 0: ory -= PygameFunctions.MOVEMENT_SPEED return orx, ory @staticmethod def calc_rect(coords): minx = min(coords[0], coords[2]) maxx = max(coords[0], coords[2]) miny = min(coords[1], coords[3]) maxy = max(coords[1], coords[3]) return minx, miny, maxx, maxy @staticmethod def clear_old_rect(img, model_img, coords, button): rect_coords = PygameFunctions.calc_rect(coords) img.blit(model_img, (rect_coords[0] - 5, rect_coords[1] - 5), area=(rect_coords[0] - 5, rect_coords[1] - 5, rect_coords[2] - rect_coords[0] + 10, 63 63 Reconocimiento de Sellos en Legajos de Archivo Histórico rect_coords[3] - rect_coords[1] + 10)) if button == 1: pygame.draw.circle(img, (0, 0, 255), (coords[2], coords[3]), 5) elif button == 3: pygame.draw.circle(img, (255, 0, 0), (coords[0], coords[1]), 5) @staticmethod def draw_new_rect(coords, img, img_origin, scale, mouse_coords, button): newx, newy = (int((mouse_coords[0] - img_origin[0]) / scale), int((mouse_coords[1] - img_origin[1]) / scale)) new_coords = 0 if button == 1: pygame.draw.circle(img, (255, 0, 0), (newx, newy), 5) pygame.draw.rect(img, (0, 255, 0), (newx, newy, coords[2] - newx, coords[3] - newy), 3) new_coords = (newx, newy, coords[2], coords[3]) elif button == 3: pygame.draw.circle(img, (0, 0, 255), (newx, newy), 5) pygame.draw.rect(img, (0, 255, 0), (newx, newy, coords[0] - newx, coords[1] - newy), 3) new_coords = (coords[0], coords[1], newx, newy) return new_coords @staticmethod def scale_img(scale, button): if button == 4: scale += PygameFunctions.SCALE_INCREMENT elif button == 5 and scale > 0: scale -= PygameFunctions.SCALE_INCREMENT return scale win_tkinter.py import tkinter as tk from tkinter import messagebox import database import widgets import os from config import path_to_documents from config import db_credentials from config import path_to_index class WinControlPanel: def __init__(self, img_window, coords, paths, index=0): self.root = tk.Tk() self.root.geometry("500x570+30+30") self.db = database.Database(db_credentials['db_name'], db_credentials['user_name'], db_credentials['pwd'], db_credentials['tables']) self.db.load_seals() self.coords = coords self.paths = paths self.path_index = index Anexos 64 64 # POINT 1 DISPLAY self.pt1_label = tk.Label(self.root, text="Point 1:") self.pt1_label.place(x=20, y=10) self.pt1x_value = tk.IntVar() self.pt1x_info = tk.Entry(self.root, state=tk.DISABLED, textvariable=self.pt1x_value) self.pt1x_info.place(x=70, y=10, width=50) self.pt1x_value.set(str(coords[0])) self.pt1y_value = tk.IntVar() self.pt1y_info = tk.Entry(self.root, state=tk.DISABLED, textvariable=self.pt1y_value) self.pt1y_info.place(x=130, y=10, width=50) self.pt1y_value.set(str(coords[1])) # POINT 2 DISPLAY self.pt2_label = tk.Label(self.root, text="Point 2:") self.pt2_label.place(x=20, y=30) self.pt2x_value = tk.IntVar() self.pt2x_info = tk.Entry(self.root, state=tk.DISABLED, textvariable=self.pt2x_value) self.pt2x_info.place(x=70, y=30, width=50) self.pt2x_value.set(str(coords[2])) self.pt2y_value = tk.IntVar() self.pt2y_info = tk.Entry(self.root, state=tk.DISABLED, textvariable=self.pt2y_value) self.pt2y_info.place(x=130, y=30, width=50) self.pt2y_value.set(str(coords[3])) # NEW SEAL WINDOW def on_new_seal(): self.new_seal_win = WinNewSeal(self.db, img_window) self.new_seal_butt = tk.Button(self.root, text='New', command=on_new_seal) self.new_seal_butt.place(x=200, y=20) # SEAL SELECTION ITEMS self.seal_type_list = widgets.SealsList(self.root, self.db) self.seal_type_list.x = 20 self.seal_type_list.y = 70 self.seal_type_list.place_items() # OK BUTTON def on_ok_button(): self.db.insert_document(self.paths[self.path_index], self.seal_type_list.curr_seal_type.get(), (self.pt1x_value.get(), self.pt1y_value.get(), self.pt2x_value.get(), self.pt2y_value.get())) if self.path_index < len(self.paths): self.path_index += 1 onlyimages =\ [f for f in os.listdir(self.paths[self.path_index]) if os.path.isfile(os.path.join(self.paths[self.path_index], f)) and f.endswith('.png')] # Llamar método de ventana de pygame que actualiza a la nueva imagen if __name__ != "__main__": 65 65 Reconocimiento de Sellos en Legajos de Archivo Histórico img_window.update_img(self.paths[self.path_index] + '/' + onlyimages[0]) else: messagebox.showinfo("End of classification", "There are no more documents to classify") self.ok_button = tk.Button(self.root, text='OK',command=on_ok_button) self.ok_button.place(x=250, y=20) def on_closing(): if messagebox.askokcancel("Quit", "Do you want to quit?"): index_file = open(path_to_index + '/index.txt', 'w') index_file.write(str(self.path_index)) index_file.close() self.root.destroy() self.root.protocol("WM_DELETE_WINDOW", on_closing) def update_labels(self, new_coords): self.pt1x_value.set(str(new_coords[0])) self.pt1y_value.set(str(new_coords[1])) self.pt2x_value.set(str(new_coords[2])) self.pt2y_value.set(str(new_coords[3])) class WinNewSeal: def __init__(self, db, img_win): self.db = db self.img_win = img_win self.root = tk.Tk() self.width = 300 self.height = 100 geom_str = "%ix%i+30+30" % (self.width, self.height) self.root.geometry(geom_str) # SEAL INFO self.name_label = tk.Label(self.root, text='Nombre') self.name_label.place(x=20, y=10) # self.seal_name = tk.StringVar() self.name_info = tk.Entry(self.root) # , textvariable=self.seal_name) self.name_info.place(x=70, y=10) self.author_label = tk.Label(self.root, text='Autor') self.author_label.place(x=20, y=40) # self.seal_author = tk.StringVar() self.author_info = tk.Entry(self.root) # , textvariable=self.seal_author) self.author_info.place(x=70, y=40) # OK BUTTON self.ok_button = tk.Button(self.root, text='OK', command=self.on_ok_button) self.ok_button.place(x=200, y=20) def on_ok_button(self): self.db.insert_seal(self.name_info.get(), self.author_info.get()) self.img_win.save_seal(self.name_info.get()) self.root.destroy() Anexos 66 66 if __name__ == "__main__": path = path_to_documents walk = os.walk(path) doc_paths = [] for root, dirs, files in walk: there_is_any_img = False for curr_file in files: if curr_file.endswith(".png"): there_is_any_img = True if there_is_any_img: root = root.replace("\\", "/") doc_paths.append(root) win = WinControlPanel(None, (10, 20, 30, 40), doc_paths) while 1: win.root.update_idletasks() win.root.update() widgets.py """ Archivo destinado a agrupar elementos de la interfaz que deban ir todos juntos. Al final tan sólo contiene la lista de sellos incluyendo el menú desplegable, la lista de éstos, la imagen de muestra correspondiente a dicho sello y el botón que sirve para cambiar dicha imagen. """ import tkinter as tk class SealsList: def __init__(self, master, db): self.db = db self.x = 0 self.y = 0 self.label = tk.Label(master, text='Type:') # <--LABEL self.OPTIONS = [seal.name for seal in self.db.seal_list] self.curr_seal_type = tk.StringVar(master) self.curr_seal_type.set(self.OPTIONS[0]) self.option_menu = tk.OptionMenu(master, self.curr_seal_type, *self.OPTIONS) # <--OPTION MENU self.canvas = tk.Canvas(master, width=600, height=400) # <--CANVAS self.img_route = self.db.seal_list[0].img_route self.img_route = self.img_route.replace("\\", "/") photo = tk.PhotoImage(file=self.img_route) self.seal_img = self.canvas.create_image(0, 0, anchor=tk.NW, image=photo) self.canvas.image = photo self.change_button = tk.Button(master, text="Change", command=self.on_change_item) def on_change_item(self): index = self.OPTIONS.index(self.curr_seal_type.get()) # change image path = self.db.seal_list[index].img_route 67 67 Reconocimiento de Sellos en Legajos de Archivo Histórico path = path.replace("\\", "/") photo = tk.PhotoImage(file=path) self.canvas.itemconfig(self.seal_img, image=photo) self.canvas.image = photo def place_items(self): self.label.place(x=self.x, y=self.y) self.option_menu.place(x=self.x + 35, y=self.y) self.canvas.place(x=self.x + 35, y=self.y + 80) self.change_button.place(x=self.x + 160, y=self.y+3) database.py import pymysql import seal from config import path_to_seals class Database: def __init__(self, db_name, user_name, passwd, tables): self.seal_list = [] # list of currently stored seals self.db = pymysql.connect("localhost", user_name, passwd, db_name) self.cursor = self.db.cursor() self.table_names = tables def load_seals(self): sql = "select * from %s" % self.table_names[0] try: self.cursor.execute(sql) result = self.cursor.fetchall() for row in result: name = row[0] author = row[1] route = row[2] new_seal = seal.Seal(route, name, author) self.seal_list.append(new_seal) except RuntimeError: print("error: unable to fetch seals data\n") def insert_seal(self, name, author): path = path_to_seals + name + ".png" sql = """insert into %s(nombre, autor, ruta, añadido_manual) values ('%s', '%s', '%s', 1)""" % (self.table_names[0], name, author, path) try: self.cursor.execute(sql) self.db.commit() except RuntimeError: self.db.rollback() print("unable to insert data into database\n") def insert_document(self, route, seal_name, coords): sql = """insert into %s(ruta, sello, coordenadas_x1, coordenadas_y1, coordenadas_x2, coordenadas_y2) values ('%s', '%s', '%s', '%s', '%s', '%s')"""% Anexos 68 68 (self.table_names[1],route, seal_name, coords[0], coords[1], coords[2], coords[3]) try: self.cursor.execute(sql) self.db.commit() except RuntimeError: self.db.rollback() print("unable to insert data into database\n") seal.py class Seal: def __init__(self, img_route='', name='', author=''): self.img_route = img_route self.name = name self.author = author Anexo B. Tests de elección de umbral de binarizado Para calcular el mejor sistema de binarizado se ha diseñado esta aplicación que permite cargar una imagen de prueba y ver en tiempo real el resultado de cada binarizado distinto que se aplique. El sistema permite probar un umbral fijo, el método de Otsu o el método adaptativo mediante media ponderada con kernel gaussiano. Además permite realizar una distorsión gaussiana para eliminar ruidos. El resultado se puede almacenar pulsando la tecla TAB (elegida arbitrariamente) para así tener almacenados resultados y poder comparar los distintos métodos. Pulsar ESC termina la ejecución. bin_test.py import cv2 import os from paths import path_to_imgs from Umbralizacion import Umbralizacion def do_nothing(x): pass file = path_to_imgs + '1862-L119.M13/109/IMG_0001.png' img = cv2.imread(file) nombre = os.path.splitext(os.path.basename(file))[0] cv2.namedWindow('image_window', cv2.WINDOW_NORMAL) cv2.namedWindow('control_window', cv2.WINDOW_OPENGL) METHODLABEL = '1:OTSU-2:FIX-3:ADAP' cv2.createTrackbar('Vecinity width', 'control_window', 0, 10, do_nothing) cv2.createTrackbar('Vecinity height', 'control_window', 0, 10, do_nothing) cv2.createTrackbar('Sigma X', 'control_window', 0, 100, do_nothing) cv2.createTrackbar('Sigma Y', 'control_window', 0, 100, do_nothing) cv2.createTrackbar(METHODLABEL, 'control_window', 0, 2, do_nothing) cv2.createTrackbar('Bin Threshold', 'control_window', 0, 255, do_nothing) cv2.createTrackbar('SWITCH', 'control_window', 0, 1, do_nothing) gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) filtered_img = gray_img 69 69 Reconocimiento de Sellos en Legajos de Archivo Histórico bin_img = Umbralizacion.umbralizar_imagen(filtered_img, Umbralizacion.MetodoUmbralizado.fixed, 180) while 1: cv2.imshow('image_window', bin_img) vec_w = cv2.getTrackbarPos('Vecinity width', 'control_window') vec_h = cv2.getTrackbarPos('Vecinity height', 'control_window') sigX = cv2.getTrackbarPos('Sigma X', 'control_window') sigY = cv2.getTrackbarPos('Sigma Y', 'control_window') method = cv2.getTrackbarPos(METHODLABEL, 'control_window') threshold = cv2.getTrackbarPos('Bin Threshold', 'control_window') switch = cv2.getTrackbarPos('SWITCH', 'control_window') method_enum = Umbralizacion.MetodoUmbralizado(method) kernel = (vec_w*2 + 1, vec_h*2 + 1) if switch == 1: filtered_img = cv2.GaussianBlur(gray_img, kernel, sigX) bin_img = Umbralizacion.umbralizar_imagen(filtered_img, method_enum, threshold) k = cv2.waitKey(1) & 0xFF if k == 27: break elif k == 9: # TAB key filestring = '../%s_met_%d_vec_%d_sig_%d_thr_%d.png' % (nombre, method, vec_w, sigX, threshold) # cv2.imwrite(filestring, bin_img) cv2.destroyAllWindows() Umbralizacion.py import cv2 from enum import Enum class Umbralizacion: class MetodoUmbralizado(Enum): otsu = 0 fixed = 1 adaptive = 2 @staticmethod def umbralizar_imagen(imagen_grises, metodo_umbralizar, umbral=180): imagen_umbralizada = imagen_grises if metodo_umbralizar == Umbralizacion.MetodoUmbralizado.otsu: ret, imagen_umbralizada = cv2.threshold(imagen_grises, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU) elif metodo_umbralizar == Umbralizacion.MetodoUmbralizado.fixed: ret, imagen_umbralizada = cv2.threshold(imagen_grises, umbral, 255, cv2.THRESH_BINARY) elif metodo_umbralizar == Umbralizacion.MetodoUmbralizado.adaptive: imagen_umbralizada = cv2.adaptiveThreshold(imagen_grises, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 11, 2) return imagen_umbralizada Anexos 70 70 Anexo C. Fase heurística SellosHeuristica.py Este archivo incluye todo el código necesario para llevar a cabo esta etapa. En realidad incluye tres clases distintas: la clase Documento, que define las variables y comportamientos relativos al documento analizado en cuestión; la clase Región, que hace lo propio para cada una de las regiones que se encuentren en el documento y la clase LineSeparator, que tiene la finalidad de calcular las coordenadas de la separación entre las líneas de texto en el documento. La estructura consiste en un objeto de tipo documento que posee una lista de objetos de tipo región. La clase de separación de líneas hace las veces de wrapper y por tanto sólo posee métodos estáticos, que son llamados desde la clase documento sin necesidad de crear ningún objeto. La clase región a su vez posee dos clases: una que se encarga de los test a los que se someten las regiones y otra para los bounding boxes de dicha región. Clase Documento class Documento: """ Clase del documento analizado en cuestión. Sólo va a haber una instancia de documento en todo momento. """ img = np.array([]) path = "" bin_img = np.array([]) bin_thresh = 0 kernel = np.ones((11, 11), np.uint8) label_img = np.array([]) regions = [] seals = [] has_2_pages = False lines_y = np.array([]) def __init__(self): del self.regions[:] del self.seals[:] self.lines_y = np.array([[]]) def load_img(self, path): self.path = path self.img = cv2.imread(self.path, cv2.IMREAD_GRAYSCALE) def get_bin_img(self): self.img = cv2.GaussianBlur(self.img, (3, 3), 0) self.bin_thresh, self.bin_img = cv2.threshold(self.img, 0, 1, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU) def apply_img_corrections(self, img=None): if img is None: aux_img = self.bin_img else: aux_img = img aux_img = cv2.GaussianBlur(aux_img, (11, 11), 0) se1 = cv2.getStructuringElement(cv2.MORPH_RECT, (10, 10)) se2 = cv2.getStructuringElement(cv2.MORPH_RECT, (4, 4)) mask = cv2.morphologyEx(aux_img, cv2.MORPH_CLOSE, se1) mask = cv2.morphologyEx(mask, cv2.MORPH_OPEN, se2) 71 71 Reconocimiento de Sellos en Legajos de Archivo Histórico out = self.img * mask if img is None: self.bin_img = (out > 5).astype('uint8') else: return (out > 5).astype('uint8') def get_lines(self): """ Calcula la coordenada vertical de la separación en líneas del documento. :return: Almacena las coordenadas en self.lines_y """ if LineSeparator.has_two_pages(self.bin_img): self.has_2_pages = True ranges = ((0, self.bin_img.shape[1] // 2), (self.bin_img.shape[1] // 2, self.bin_img.shape[1])) else: self.has_2_pages = False ranges = ((0, self.bin_img.shape[1]),) lines_y = [] for page, rng in enumerate(ranges): hist = LineSeparator.proyect(self.bin_img[:, rng[0]:rng[1]], axis=LineSeparator.axis["horizontal"]) if hist.max() == 0: continue smooth_hist = LineSeparator.savitzky_golay(hist, 51, 3) mins = LineSeparator.find_min(smooth_hist) min_x = [i[0] for i in mins] min_y = [i[1] for i in mins] is_out = LineSeparator.is_outlier(np.array(min_y)) outliers_x = [] outliers_y = [] for i, x in enumerate(is_out): if x: if hist[min_x[i]] > 0: outliers_x.append(min_x[i]) outliers_y.append(min_y[i]) else: is_out[i] = False for i, xs in enumerate(min_x): if not is_out[i]: # cv2.line(self.bin_img, (rng[0], xs), (rng[1], xs), 1, 10) lines_y.append([xs, page]) self.lines_y = np.array(lines_y) def get_regions(self): aux_label_img = measure.label(self.bin_img) regs = measure.regionprops(aux_label_img) aux_label_img = Region.Bbox.eliminar_borde(regions=regs, label_image=aux_label_img) regs = measure.regionprops(aux_label_img) self.label_img = Region.Bbox.reetiquetado(regs, aux_label_img) regs = measure.regionprops(self.label_img) Anexos 78 78 is not a seal. NOTE: Page is stored as the second value in lines_y where --> 0->1st page; 1->2nd page """ if not self.document.has_2_pages: lines_y = self.document.lines_y else: page =\ int(self.region.minc >int(self.document.bin_img.shape[1]/2)) line_list = [] for ly in self.document.lines_y: if ly[1] == page: line_list.append(ly) lines_y = np.array(line_list) height = self.region.maxr - self.region.minr nearest_higher_index =\ np.searchsorted(lines_y[:, 0], self.region.minr + int(height/3)).item() if nearest_higher_index < len(lines_y): nearest_higher = lines_y[nearest_higher_index, 0] else: nearest_higher = 0 # if we reach this condition, the test # should get passed anyway if (self.region.minr + int(height/3) < nearest_higher < self.region.maxr - int(height/3)): self.passed_tests.update({"between_lines": False}) else: self.passed_tests.update({"between_lines": True}) def apply_active_tests(self): """ Aplica todo test que se encuentre activo. Si la región superase todos los test, se añadiría a la lista de sellos """ self.region.region_is_seal = True if self.region.test.active_tests.get("area") is True: self.region.test.area() self.region.region_is_seal *=\ self.region.test.passed_tests.get("area") if self.region.test.active_tests.get("aspect_ratio") is True: self.region.test.aspect_ratio() self.region.region_is_seal *=\ self.region.test.passed_tests.get("aspect_ratio") if self.region.test.active_tests.get("filled_area") is True: self.region.test.filled_area_ratio() self.region.region_is_seal *=\ self.region.test.passed_tests.get("filled_area") if self.region.test.active_tests.get("simmetry") is True: self.region.test.symmetry() self.region.region_is_seal *=\ self.region.test.passed_tests.get("simmetry") if self.region.test.active_tests.get("position") is True: self.region.test.position() self.region.region_is_seal *=\ self.region.test.passed_tests.get("position") if self.region.test.active_tests.get("between_lines") is True: self.region.test.is_between_lines() self.region.region_is_seal *=\ self.region.test.passed_tests.get("between_lines") 79 79 Reconocimiento de Sellos en Legajos de Archivo Histórico if self.region.region_is_seal: self.document.seals.append(self.region) Clase LineSeparator class LineSeparator: settings = { "min_lin_dist_px": 60 } axis = { "vertical": 0, "horizontal": 1, } @staticmethod def proyect(bin_img, axis): """ Cuenta el número de pixels tras proyectar la imagen en la dirección especificada :param bin_img: - :param axis: eje sobre el que proyectar. Utilícese el diccionario axis :return: """ if np.array_equal(bin_img, bin_img.astype(bool)): hist = np.sum(bin_img, axis) else: raise NameError("Image passed to LineSeparator is not binary") return hist @staticmethod def longest_streak(a): """ Encuentra la racha más larga en ya sea un array de numpy o una lista :param a: lista o array de numpy :return: racha más larga encontrada """ lst = [] for n, c in groupby(a): streak = list(c) if len(streak) > len(lst): lst = streak return lst @staticmethod def has_two_pages(bin_img): """ Comprueba si la racha más larga encontrada contiene solo ceros y además es mayor de 1/7 del ancho total de la imagen del documento :param bin_img: Imagen binaria del documento para computer si está compuesta o no de dos páginas :return: True si tiene dos páginas, False en caso contrario. Se basa en la hipótesis de que ningún documento poseerá más de dos páginas. """ first_col = int(bin_img.shape[1] / 3) last_col = int(2 * bin_img.shape[1] / 3) hist = LineSeparator.proyect(bin_img[:, first_col:last_col], LineSeparator.axis["vertical"]) Anexos 80 80 for i, el in enumerate(hist): if el <= 10: hist[i] = 0 max_streak = LineSeparator.longest_streak(hist) if len(max_streak) > int(bin_img.shape[1] / 40): return True else: return False @staticmethod def savitzky_golay(y, window_size, order, deriv=0, rate=1): """Suaviza (y opcionalmente deriva) datos mediante un filtro de Savitzky-Golay. El filtro Savitzky-Golay ruidos de alta frecuencia. Posee la ventajad de preserver la forma y características de la imagen original major que otros enfoques de filtrado como las técnicas basadas en medias móviles Parámetros ---------- y : array_like, shape (N,) Valores de la señal. window_size : int Dimensión de la ventana. Debe ser un entero impar. order : int Orden del polinomio utilizado para el filtrado. Debe ser menor que `window_size` - 1. deriv: int Orden de la derivada a computar (por defecto = 0 tan solo suavizar) Returns ------- ys : ndarray, shape (N) Señal suavizada (o su n-ésima derivada). Notas ----- La idea principal tras este enfoque consiste en realizar, para cada punto, un ajuste mediante mínimos cuadrados a un polinomio de orden elevado sobre una vecindad de dimensión impar centrada en el punto Referencias ---------- .. [1] A. Savitzky, M. J. E. Golay, Smoothing and Differentiation of Data by Simplified Least Squares Procedures. Analytical Chemistry, 1964, 36 (8), pp 1627-1639. .. [2] Numerical Recipes 3rd Edition: The Art of Scientific Computing W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery Cambridge University Press ISBN-13: 9780521880688 """ from math import factorial try: window_size = np.abs(np.int(window_size)) order = np.abs(np.int(order)) except ValueError as msg: raise ValueError("window_size and order have to be of type int") if window_size % 2 != 1 or window_size < 1: raise TypeError("window_size size must be a positive odd number") if window_size < order + 2: raise TypeError("window_size is too small for the polynomials order") order_range = range(order + 1) half_window = (window_size - 1) // 2 # precompute coefficients 81 81 Reconocimiento de Sellos en Legajos de Archivo Histórico b = np.mat([[k ** i for i in order_range] for k in range(-half_window, half_window + 1)]) m = np.linalg.pinv(b).A[deriv] * rate ** deriv * factorial(deriv) # pad the signal at the extremes with # values taken from the signal itself firstvals = y[0] - np.abs(y[1:half_window + 1][::-1] - y[0]) lastvals = y[-1] + np.abs(y[-half_window - 1:-1][::-1] - y[-1]) y = np.concatenate((firstvals, y, lastvals)) return np.convolve(m[::-1], y, mode='valid') @staticmethod def find_min(a): """ Encontrar el mínimos en array 'a'. Si entre mínimo y mínimo hay menos de min_lin_dist_px píxeles se ignora el más grande de los dos. :param a: Array en el cual encontrar los mínimos locales. :return: Índice en el cual se encuentran los mínimos """ # Tomar todos los puntos menores que sus dos puntos contiguos is_min = np.r_[True, a[1:] < a[:-1]] & np.r_[a[:-1] < a[1:], True] min_points = [] true_mins = [] min_dist = LineSeparator.settings.get("min_lin_dist_px") for i, value in enumerate(a): if is_min[i]: min_points.append((i, value)) min_points.sort(key=lambda p: p[1]) # function lambda empleada para # informar a sort() sobre qué # componente de la tupla emplear # para la ordenación if len(min_points) > 0: true_mins.append(min_points[0]) for point in min_points[1:]: too_close = False for true_min in true_mins: dist = abs(point[0] - true_min[0]) if dist < min_dist: too_close = True if not too_close: true_mins.append(point) return true_mins @staticmethod def is_outlier(points, thresh=2.0035): """ Devuelve un array booleano con True en aquellas componentes que sean outliers y False en caso de que no lo sean. Parámetros: ----------- points : Array de tamaño (observaciones x dimension de observaciones) thresh : z-puntuación modificada para emplear como umbral. Aquellas observaciones con una z-puntuación (basada en la desviación mediana absoluta) mayores que este valor, serán clasificadas como outliers NOTA: El valor se ha calculado como la media entre el mayor y Anexos 82 82 menor valor que filtraba a la perfección para una imagen de prueba. Returns: -------- mask : Array de dimensión igual al número de observaciones References: ---------- Boris Iglewicz and David Hoaglin (1993), "Volume 16: How to Detect and Handle Outliers", The ASQC Basic References in Quality Control: Statistical Techniques, Edward F. Mykytka, Ph.D., Editor. """ if len(points.shape) == 1: points = points[:, None] median = np.median(points, axis=0) diff = np.sum((points - median) ** 2, axis=-1) diff = np.sqrt(diff) med_abs_deviation = np.median(diff) if med_abs_deviation == 0: return np.ones(len(points), dtype=np.bool) else: modified_z_score = 0.6745 * diff / med_abs_deviation return modified_z_score > thresh sellos_heuristica_secuencial.py Ahora que disponemos de todas las herramientas necesarias para llevar a cabo esta etapa, tan solo nos falta utilizarlas. A este script se le pasa la ruta donde están las imágenes y va cargando una a una. Para cada una de ellas, crea un objeto documento y llama a todas las funciones de esta clase definidas con anterioridad, con el objetivo de hallar si en este documento existiera alguna región con las características de un sello. Si alguna región se determinase que es un sello, se guarda en la carpeta especificada un recorte de la imagen con las coordenadas de la región y se añade una nueva entrada a la base de datos de prototipos de sellos con la ruta de la imagen y su identificador. import os import numpy as np import cv2 from Database import DatabaseHeur import SellosHeuristica as Sh import paths path = paths.path_to_imgs walk = os.walk(path) db = DatabaseHeur('docs_osborne', 'testuser', 'test123', 'heur_results6') i = 0 for root, dirs, files in walk: for curr_file in files: if not curr_file.endswith(".png") or curr_file.startswith("."): continue img_path = root + '/' + curr_file print(img_path) documento = Sh.Documento() documento.load_img(img_path) documento.get_bin_img() documento.apply_img_corrections() documento.get_lines() documento.get_regions() 83 83 Reconocimiento de Sellos en Legajos de Archivo Histórico for region in documento.regions: region.test.apply_active_tests() documento.elim_self_contain() for seal in documento.seals: seal_img = documento.img[seal.minr:seal.maxr, seal.minc:seal.maxc] width = seal.maxr - seal.minr height = seal.maxc - seal.minc cv2.imwrite(paths.path_to_heur + '/' + str(i) + curr_file, seal_img) db.insert_results({ "path": root.replace("\\", "/"), "reg_id": str(i), }) i += 1 Paths.py Para simplificar el poder trabajar en distintos entornos, se ha creado este archivo que simplemente almacena las distintas rutas necesarias para el funcionamiento del resto de scripts. Este archivo es común para ambas fases del algoritmo. Un ejemplo de este archivo podría ser: path_to_imgs = 'C:/Users/usuario/Desktop/Documents/' path_to_prototypes = 'C:/Users/usuario/Desktop/proto_base/' path_to_heur = 'C:/Users/usuario/Desktop/heur/' Es imprescindible que las tres variables estén definidas. La primera localiza la carpeta raíz de las imágenes de documentos. La segunda, los prototipos de sellos una vez que se han eliminado manualmente los falsos positivos. La tercera, es donde la fase heurística almacena todos los candidatos a sellos encontrados. Database.py Este archivo NO es el mismo que el mencionado en el anexo B, ya que pertenecen a proyectos (y entornos virtuales separados). Sí que es común con la segunda fase del algoritmo (anexo D), al igual que el anterior. import pymysql class Database: sql = "" def __init__(self, db_name, user_name, passwd, tables): self.db = pymysql.connect("localhost", user_name, passwd, db_name) self.cursor = self.db.cursor() self.table_names = tables def run_query(self, query): try: self.cursor.execute(query) self.db.commit() except RuntimeError: self.db.rollback() print("unable to insert data into database\n") def insert_results(self, params): raise NotImplementedError("Method not implemented") class DatabaseFeatures(Database): sql = """insert into %s(ruta, sello, coordenadas_x1, coordenadas_y1, coordenadas_x2, coordenadas_y2, ratio) values ('%s', '%s', '%s', '%s', '%s', Anexos 84 84 '%s', '%s')""" def insert_results(self, params): path = params.get("path") coords = params.get("coords") found_seal_name = params.get("found_seal_name") max_ratio = params.get("max_ratio") query = self.sql % (self.table_names, path, found_seal_name, coords[0][0], coords[0][1], coords[1][0], coords[1][1], max_ratio) super().run_query(query) class DatabaseHeur(Database): sql = "insert into %s(ruta, region_id) values ('%s', '%s')" def insert_results(self, params): path = params.get("path") reg_id = params.get("reg_id") query = self.sql % (self.table_names, path, reg_id) super().run_query(query) Anexo D. Fase de Extracción de Características. Primero es necesario crear una base de datos con las características extraídas de los prototipos de sellos encontrados y luego utilizar esta información para compararla con los documentos. FeaturesIO.py Se encarga de lidiar con la extracción y almacenamiento de características, además de su posterior lectura. import cv2 class FeaturesIO: @staticmethod def write_features_to_file(filename, locs, desc, shape): np.savez(filename, np.hstack((locs, desc)), shape) @staticmethod def pack_keypoint(keypoints, descriptors): kpts = np.array([[kp.pt[0], kp.pt[1], kp.size, kp.angle, kp.response, kp.octave, kp.class_id] for kp in keypoints]) desc = np.array(descriptors) return kpts, desc @staticmethod def unpack_keypoint(file): seals_kps = [] seals_des = [] array = file['arr_0'] num_elements = len(array) for i in range(0, int(num_elements/2)): kpts = array[i] 85 85 Reconocimiento de Sellos en Legajos de Archivo Histórico keypoints = [cv2.KeyPoint(x, y, _size, _angle, _response, int(_octave), int(_class_id)) for x, y, _size, _angle, _response, _octave, _class_id in list(kpts)] seals_kps.append(keypoints) for i in range(int(num_elements/2), num_elements): desc = np.array(array[i]).astype(np.float32) # float32 for surf; uint8 for ORB seals_des.append(desc) seal_shps = file['arr_1'] return seals_kps, seals_des, seal_shps @staticmethod def process_and_save(path, resultname, detector): walk = os.walk(path) all_k = [] all_d = [] all_s = [] for root, dirs, files in walk: for curr_file in files: if (not curr_file.endswith(".png") or curr_file == "no_seal.png"): continue # print(curr_file) img = cv2.imread(path + '/' + curr_file, 0) k = detector.detect(img, None) if len(k) > 0: k, des = detector.compute(img, k) else: des = [] k, des = FeaturesIO.pack_keypoint(k, des) # all_k.append(k.tolist()) all_d.append(des.tolist()) all_s.append(img.shape) FeaturesIO.write_features_to_file(resultname, all_k, all_d, all_s) @staticmethod def load_features(filename): file = np.load(filename) kp, des, shps = FeaturesIO.unpack_keypoint(file) return kp, des, shps FeaturesDetector.py Cumple la finalidad de facilitar la configuración del detector de características import cv2.xfeatures2d as xf def create_detector(): surf = xf.SURF_create(hessianThreshold=400, upright=True, extended=True) return surf Anexos 86 86 creacion_base_datos_sellos.py Técnicamente no es una base de datos, tan solo una serialización. Extrae y almacena en un archivo las características extraídas de los prototipos de sellos. from FeaturesIO import FeaturesIO as FtIO import FeaturesDetector import paths path = paths.path_to_prototypes detector = FeaturesDetector.create_detector() FtIO.process_and_save(path, "car_sellos", detector) EvidenceMatrix.py Este archivo ha sido explicado en profundidad en el capítulo 6. import numpy as np class EvidenceMatrix: DIVISION_SIZE = 10 SEAL_DIMENSION = 300 # seals are about 300x300px def __init__(self, shape): fils, cols = shape self.evidence_matrix = np.array([]) self.evidence_matrix.resize((fils / EvidenceMatrix.DIVISION_SIZE, cols / EvidenceMatrix.DIVISION_SIZE)) self.evidence_matrix.fill(0) def calc_occurrences(self, keypoints): for kp in keypoints: # points are x, y instead of rows and columns normal = (int(kp.pt[1] / EvidenceMatrix.DIVISION_SIZE), int(kp.pt[0] / EvidenceMatrix.DIVISION_SIZE)) self.evidence_matrix[normal[0], normal[1]] += 1 EliminacionSellos.py Detecta el tipo de sello y su posición. Además, permite borrarlo del documento con el objetivo de facilitar otras tareas de visión artificial. import cv2 import numpy as np from FeaturesIO import FeaturesIO import EvidenceMatrix as em import FeaturesDetector class EliminacionSellos: doc_img = 0 doc_kps = [] 87 87 Reconocimiento de Sellos en Legajos de Archivo Histórico doc_des = [] kps_saved = [] desc_saved = [] seals_dims = [] surf = FeaturesDetector.create_detector() def __init__(self, img, index): EliminacionSellos.doc_img = img.copy() self.kp_matched = [] self.evidence_matrix = em.EvidenceMatrix(img.shape) self.position = (0, 0) # position is (rows, cols), therefore, (y, x) self.max_occurrences = 0 self.index = index self.total_matches = 0 def get_keypoints_from_db(self, path): (EliminacionSellos.kps_saved, EliminacionSellos.desc_saved, EliminacionSellos.seals_dims)\ = FeaturesIO.load_features(path) def get_document_features(self): EliminacionSellos.doc_kps, EliminacionSellos.doc_des =\ EliminacionSellos.surf.detectAndCompute(EliminacionSellos.doc_img, None) def get_matched_keypoints(self): # FLANN parameters FLANN_INDEX_KDTREE = 0 index_params = dict(algorithm=FLANN_INDEX_KDTREE, trees=5) search_params = dict(checks=50) # or pass empty dictionary flann = cv2.FlannBasedMatcher(index_params, search_params) aux_kp = [] matches = flann.knnMatch(EliminacionSellos.desc_saved[self.index], EliminacionSellos.doc_des, k=2) for j, (m, n) in enumerate(matches): if m.distance < 0.7 * n.distance: aux_kp.append(EliminacionSellos.doc_kps[m.trainIdx]) self.kp_matched = aux_kp self.total_matches = len(self.kp_matched) def compute_evidence_matrix(self): self.evidence_matrix.calc_occurrences(self.kp_matched) def compute_position_and_max_occurences(self): num_cells = int(self.evidence_matrix.SEAL_DIMENSION / self.evidence_matrix.DIVISION_SIZE) kernel = np.ones((num_cells, num_cells)) occurrences =\ cv2.filter2D(self.evidence_matrix.evidence_matrix, -1, kernel) self.max_occurrences = np.amax(occurrences) max_index = np.where(occurrences == self.max_occurrences) avg_index = (np.average(max_index[0]), np.average(max_index[1])) final_coords = (int(avg_index[0].item()), int(avg_index[1].item())) self.position = (final_coords[0] * self.evidence_matrix.DIVISION_SIZE, final_coords[1] * self.evidence_matrix.DIVISION_SIZE)