Distilling Structure from Imagery: Graph-based Models for the Interpretation of Document Images

Abstract

Des del seu inici, la comunitat investigadora sobre reconeixement de patrons i visió per computador ha reconegut la importància d’aprofitar la informació estructural de les imatges. Els grafs s’han seleccionat com el marc adequat per representar aquest tipus d’informació a causa de la seva flexibilitat i poder de representació capaç de codificar, tant els components, objectes i entitats com les seves relacions. Tot i que els grafs s’han aplicat amb èxit a una gran varietat de tasques -com a resultat de la seva naturalesa simbòlica i relacional- sempre han patit d’algunes limitacions comparats amb mètodes estadístics. Això es deu al fet que algunes operacions matemàtiques trivials no tenen una equivalència en el domini dels grafs. Per exemple, en la base de moltes aplicacions de reconeixement de patrons hi ha la necessitat de comparar objectes. No obstant això, aquesta operació trivial no està degudament definida per grafs quan considerem vectors de característiques. Al llarg d’aquesta recerca, el principal domini d’aplicació està basat en el tema de l’Anàlisi i Reconeixement d’Imatges de Documents. Aquest és un subcamp de la Visió per Computador que té com a objectiu compendre imatges de documents. En aquest context, l’estructura -particularment la representació en forma de graf- proporciona una dimensió complementària al contingut de la imatge. En Visió per Computador la primera dificultat que ens trobem recau en construir una representació significativa de grafs capaç de codificar les característiques rellevants d’una imatge donada. Això es deu al fet que és un procés que ha de trobar un equilibri entre la simplicitat de la representació i la flexibilitat, per tal de representar les diferents deformacions que apareixen en cada domini d’aplicació. Hem estudiat aquest tema en l’aplicació de la recerca de paraules, dividint els diferents traços en grafemes –les unitats més petites d’un alfabet manuscrit&-. També, hem investigat diferents metodologies per accelerar el procés de comparació entre grafs perquè la recerca de paraules o, inclús, de forma més general, l’aplicació en la recerca de grafs, pugui incloure grans col·leccions de documents. Aquestes metodologies han estat principalment dues: (a) un sistema d’indexació de grafs combinat amb un sistema de votació en l’àmbit de nodes capaç d’eliminar resultats improbables i (b) usant representacions jeràrquiques de grafs que duen a terme la majoria de les comparacions en una versió reduïda del graf original, mitjançant comparatives entre els nivells més abstractes i els més detallats. A més a més, la representació jeràrquica també ha demostrat obtenir una representació més robusta que el graf original, lidiant amb el soroll i les deformacions de manera elegant. Per tant, proposem explotar aquesta informació en forma de codificació jeràrquica del graf que permeti utilitzar tècniques estadístiques clàssiques. Els nous avenços en aprenentatge profund geomètric han aparegut com una generalització de les metodologies d’aprenentatge profund aplicades a dominis no Euclidians –com grafs i varietats–, i han promogut un gran interès en la comunitat científica per aquests esquemes de representació. Així doncs, proposem una distància de grafs capaç d’obtenir resultats comparables a l’estat de l’art en diferents tasques aprofitant aquests nous desenvolupaments, però considerant les metodologies tradicionals com a base. També hem realitzat una col·laboració industrial amb la finalitat d’extreure informació automàtica de les factures de l’empresa (amb dades anònimes). El resultat ha estat el desenvolupament d’un sistema de detecció de taules en documents administratius. D’aquesta manera les xarxes neuronals basades en grafs han demostrat ser aptes per detectar patrons repetitius, els quals, després d’un procés d’agregació, constitueixen una taula.

La comunidad que investiga el reconocimiento de patrones y la visión por computador ha reconocido la importancia de aprovechar la información estructural de las imágenes. Los grafos se han seleccionado como el marco adecuado para representar este tipo de información a causa de su flexibilidad y poder de representación capaz de codificar los componentes, los objetos, las entidades y sus relaciones. Aunque los grafos se han aplicado con éxito a una gran variedad de tareas –como resultado de su naturaleza simbólica y relacional–, siempre han sufrido algunas limitaciones comparados con los métodos estadísticos. Esto se debe al hecho que algunas operaciones matemáticas triviales no tienen una equivalencia en el dominio de los grafos. Por ejemplo, en la base de la mayoría de aplicaciones de reconocimiento de patrones hay la necesidad de comparar objetos. No obstante, esta operación trivial no está debidamente definida por grafos cuando consideramos vectores de características. Durante la investigación, el principal dominio de aplicación se basa en el Análisis y Reconocimiento de Imágenes de Documentos. Este es un subcampo de la Visión por Computador que tiene como objetivo comprender imágenes de documentos. En este contexto la estructura -particularmente la representación en forma de grafo- proporciona una dimensión complementaria al contenido de la imágen. En Visión por Computador la primera dificultad que nos encontramos se basa en construir una representación significativa de grafos que sea capaz de codificar las características relevantes de una imagen. Esto se debe a que es un proceso que tiene que encontrar un equilibrio entre la simplicidad de la representación y la flexibilidad, para representar las diferentes deformaciones que aparecen en cada dominio de la aplicación. Hemos estudiado este tema en la aplicación de la búsqueda de palabras, dividiendo los diferentes trazos en grafemas –las unidades más pequeñas de un alfabeto manuscrito–. Tambien, hemos investigado diferentes metodologías para acelerar el proceso de comparación entre grafos para que la búsqueda de palabras o, incluso, de forma más general, la aplicación de búsqueda de grafos, pueda incluir grandes colecciones de documentos. Estas metodologías han estado principalmente dos: (a) un sistema de indexación de grafos combinado con un sistema de votación en el ámbito de los nodos capaces de eliminar resultados improbables y (b) usando representaciones jerárquicas de grafos que llevan a término la mayoría de las comparaciones en una versión reducida del grafo original mediante comparativas entre los niveles más abstractos y los más detallados. Asimismo, la representación jerárquica también ha demostrado obtener una representación más robusta que el grafo original, además de lidiar con el ruido y las deformaciones de manera elegante. Así pues, proponemos explotar esta información en forma de codificación jerárquica del grafo que permita utilizar técnicas estadísticas clásicas. Los nuevos avances en el aprendizaje profundo geométrico han aparecido como una generalización de las metodologías de aprendizaje profundo aplicadas a dominios no Euclidianos –como grafos y variedades– y han promovido un gran interés en la comunidad científica por estos esquemas de representación. Proponemos una distancia de grafos capaz de obtener resultados comparables al estado del arte en diferentes tareas aprovechando estos nuevos desarrollos, pero considerando las metodologías tradicionales como base. También hemos realizado una colaboración industrial con la finalidad de extraer información automática de las facturas de la empresa (con datos anónimos). El resultado ha sido el desarrollo de un sistema de detección de tablas en documentos administrativos. Así pues, las redes neuronales basadas en grafos han demostrado ser aptas para detectar patrones repetitivos, los cuales, después de un proceso de agregación, constituyen una tabla.

From its early stages, the community of Pattern Recognition and Computer Vision has considered the importance on leveraging the structural information when understanding images. Usually, graphs have been selected as the adequate framework to represent this kind of information due to their flexibility and representational power able to codify both, the components, objects or entities and their pairwise relationship. Even though graphs have been successfully applied to a huge variety of tasks, as a result of their symbolic and relational nature, graphs have always suffered from some limitations compared to statistical approaches. Indeed, some trivial mathematical operations do not have an equivalence in the graph domain. For instance, in the core of many pattern recognition application, there is the need to compare two objects. This operation, which is trivial when considering feature vectors, is not properly defined for graphs. Along this dissertation the main application domain has been on the topic of Document Image Analysis and Recognition. It is a subfield of Computer Vision aiming at understanding images of documents. In this context, the structure and in particular graph representations, provides a complementary dimension to the raw image contents. In computer vision, the first challenge we face is how to build a meaningful graph representation that is able to encode the relevant characteristics of a given image. This representation should find a trade off between the simplicity of the representation and its flexibility to represent the deformations appearing on each application domain. We applied our proposal to the word spotting application where strokes are divided into graphemes which are the smaller units of a handwritten alphabet. We have investigated different approaches to speed-up the graph comparison in order that word spotting, or more generally, a retrieval application is able to handle large collections of documents. On the one hand, a graph indexing framework combined with a votation scheme at node level is able to quickly prune unlikely results. On the other hand, making use of graph hierarchical representations, we are able to perform a coarse-to-fine matching scheme which performs most of the comparisons in a reduced graph representation. Besides, the hierarchical graph representation demonstrated to be drivers of a more robust scheme than the original graph. This new information is able to deal with noise and deformations in an elegant fashion. Therefore, we propose to exploit this information in a hierarchical graph embedding which allows the use of classical statistical techniques. Recently, the new advances on geometric deep learning, which has emerged as a generalization of deep learning methods to non-Euclidean domains such as graphs and manifolds, has raised again the attention to these representation schemes. Taking advantage of these new developments but considering traditional methodologies as a guideline, we proposed a graph metric learning framework able to obtain state-of-the-art results on different tasks. Finally, the contributions of this thesis have been validated in real industrial use case scenarios. For instance, an industrial collaboration has resulted in the development of a table detection framework in annonymized administrative documents containing sensitive data. In particular, the interest of the company is the automatic information extraction from invoices. In this scenario, graph neural networks have proved to be able to detect repetitive patterns which, after an aggregation process, constitute a table.