Un modelo sintáctico para la representación, segmentación y reconocimiento de símbolos texturados en doucmentos gráficos

Abstract

El análisis de documentos es una de las áreas científicas de referencia de la Visión por Computador. Se ocupa de la identificación de entidades gráficas en un documento. Dentro de este área el reconocimiento de símbolos es un problema complejo y en el que existen todavía retos importantes, y puede definirse como la extracción de aquellas entidades gráficas con un significado determinado dentro del contexto en el que se enmarque el documento. Los símbolos los podemos dividir en dos clases principalmente, los basados en prototipos y los texturados, es decir símbolos que tienen alguna de sus partes formada por una textura estructurada.<br/><br/>Las texturas estructuradas se definen por uno o varios elementos o texels que se distribuyen en el espacio siguiendo unas reglas de emplazamiento. En nuestro modelo de textura estructurada consideraremos que estos texels son polígonos cerrados o segmentos de línea. Análogamente, un plano o documento a reconocer se modeliza por medio de un grafo de regiones de adyacencia, en el que los nodos representan los polígonos encontrados en el plano y las aristas las relaciones entre ellos.<br/><br/>El trabajo realizado tiene dos partes bien diferenciadas, la segmentación y el reconocimiento de texturas. En la primera, segmentamos texturas por medio de un clustering jerárquico sobre el grafo que representa el plano. De esta manera obtenemos una serie de clusters de polígonos similares con reglas de emplazamiento similares. Así los clusters donde encontramos un número suficiente de elementos están formando una textura y su representante es el polígono y la vecindad medios calculados. Cuando es una textura compuesta y está formada por más de un texel encontramos clusters solapados, y cada uno de ellos nos indica uno de los texels que forman la textura. La segunda fase infiere una representación de la textura a partir de los representantes de los clusters. Esta representación es una gramática de grafo que permite producciones de error. El proceso de inferencia gramatical se realiza teniendo en cuenta los texels que forman la textura y sus reglas de emplazamiento. A partir de ellas se calculan de forma automática los ciclos cerrados que forman estas vecindades y se generan las reglas de la gramática de grafo. Al final se introducen producciones de error para tolerar texturas distorsionadas por texels partidos o fusionados. Una vez la gramática ha sido calculada se reconoce el símbolo representado por ella mediante un parser que analiza un grafo de entrada y recorre los nodos del mismo que cumplen las reglas de la gramática agrupándolos en uno o varios clusters que serán las ocurrencias del símbolo en el grafo presentado.<br/><br/>En resumen, en este trabajo proponemos soluciones para segmentar, mediante el clustering de formas, texturas estructuradas, y modelizar y reconocer un símbolo texturado mediante una gramática de grafo y el análisis sintáctico que podemos realizar con ella sobre un grafo, respectivamente.<br/>Palabras clave: Análisis de documentos gráficos, reconocimiento de símbolos, texturas estructuradas, reconocimiento sintáctico, gramáticas de grafo.

After decades of activity, Document Analysis continues being one of the main scientific areas in Computer Vision. The aim of the graphical document analysis is to identify graphical entities in a document. Symbol recognition is a complex problem in Graphical Document Analysis, and it still have important challenges for the scientific community. Symbol Recognition can be defined as the extraction of graphical entities which have a special meaning in the context of the analyzed document. Symbols<br/>can be mainly divided in two classes, the prototyped-based symbols and the textured symbols, that means symbols with one or more of its parts formed by a structural texture.<br/><br/>Structural textures are defined by one or more elements or texels distributed in the space following placement rules. In our structural texture model we consider texels as closed polygonals or line segments. On the other hand a document or plan to be analyzed is modeled by means of a Region Adjacency Graph, where the nodes represent polygonals found in the original document and the edges the relations among them.<br/><br/>This dissertation has two parts well defined, the segmentation and the recognition of textures. In the first part, textures are segmented by means of a hierarchical clustering over the graph that represents the plan. In that way a set of clusters, formed by similar polygonals placed following similar rules, are obtained. Then the clusters with a certain number of elements are considered to form a texture and their representative is presented by the mean polygonal and the mean neighbourhood, both computed. When the texture is composed of more than one kind of texels, the clusters appear overlapped, one for each kind of texel forming the texture. The second part is devoted to infer the texture representation from the representative of the clusters. This representation is a graph grammar with error productions. The grammar inference process is done bearing in mind the texels forming the texture and their placement rules. From these rules the closed loops are computed automatically and the rules of the graph grammar are generated. At the end the error productions are introduced to tolerate textures distorted by cut or merged texels. Once the grammar is computed the symbol represented by it is recognized by parsing an input graph and visiting all the nodes following the rules of the grammar, and grouping them in one or<br/>several clusters which are the instances of the symbol in the input graph.<br/><br/>To summarize, in this work a solution to segment structural textures, by means of shape clustering, is proposed. Then solutions to modelize a textured symbol by means of a grammar, and to recognize it by parsing with that grammar over an input graph, are presented.<br/><br/>Key words: Graphical Document Analysis, Symbol<br/>Recognition, Structural Textures, Syntactical Pattern Recognition, Graph Grammars.