Relational models for visual understanding of graphical documents. Application to architectural drawings.

Abstract

Els documents gráfics són documents que expressen continguts semántics utilitzant majoritáriament un llenguatge visual. Aquest llenguatge está format per un vocabulari (símbols) i una sintaxi (relacions estructurals entre els símbols) que conjuntament manifesten certs conceptes en un context determinat. Per tant, la interpretació dun document gráfic per part dun ordinador implica tres fases. (1) Ha de ser capadçe detectar automáticament els símbols del document. (2) Ha de ser capadç extreure les relacions estructurals entre aquests símbols. I (3), ha de tenir un model del domini per tal poder extreure la semántica. Exemples de documents gráfics de diferents dominis són els planells darquitectural i d’enginyeria, mapes, diagrames de flux, etc. El Reconeixement de Gráfics, dintre de lárea de recerca de Análisi de Documents, neix de la necessitat de la indústria dinterpretar la gran quantitat de documents gráfics digitalitzats a partir de laparició de lescáner. Tot i que molts anys han passat daquests inicis, el problema de la interpretació automática de documents sembla encara estar lluny de ser solucionat. Básicament, aquest procés sha alentit per una raó principal: la majoria dels sistemes dinterpretació que han estat presentats per la comunitat són molt centrats en una problemática específica, en el que el domini del document marca clarament la implementació del mètode. Per tant, aquests mètodes són difícils de ser reutilitzats en daltres dades i marcs daplicació, estancant així la seva adopció i evolució en favor del progrés. En aquesta tesi afrontem el problema de la interpretació automática de documents gráfics a partir dun seguit de models relacionals que treballen a tots els nivells del problema, i que han estat dissenyats des dun punt de vista genèric per tal de que puguin ser adaptats a diferents dominis. Per una part, presentem 3 mètodes diferents per a lextracció dels símbols en un document. El primer tracta el problema des dun punt de vista estructural, en el que el coneixement general de lestructura dels símbols permet trobar-los independentment de la seva aparença. El segon és un mètode estad ístic que aprèn laparença dels símbols automáticament i que, per tant, sadapta a la gran variabilitat del problema. Finalment, el tercer mètode és una combinació dambdós, heretant els beneficis de cadascun dels mètodes. Aquesta tercera implementaci ó no necessita de un aprenentatge previ i a més sadapta fácilment a múltiples notacions gráfiques. D’altra banda, presentem dos mètodes per a la extracció del context visuals. El primer mètode segueix una estratègia bottom-up que cerca les relacions estructurals en una representació de graf mitjançant algorismes dintel_ligència artificial. La segona en canvi, és un mètode basat en una gramática que mitjançant un model probabilístic aprèn automáticament lestructura dels planells. Aquest model guia la interpretació del document amb certa independència de la implementació algorísmica. Finalment, hem definit una base del coneixement fent confluir una definició ontol`ogica del domini amb dades reals. Aquest model ens permet raonar les dades des dun punt de vista contextual i trobar inconsistències semántiques entre les dades. Leficiència daquetes contribucions han estat provades en la interpretació de planells darquitectura. Aquest documents no tenen un estándard establert i la seva notació gráfica i inclusió dinformació varia de planell a planell. Per tant, és un marc rellevant del problema de reconeixement gráfic. A més, per tal de promoure la recerca en termes de interpretació de documents gráfics, fem públics tant les dades, leina per generar les dades i els evaluadors del rendiment.

Graphical documents express complex concepts using a visual language. This language consists of a vocabulary (symbols) and a syntax (structural relations among symbols) that articulate a semantic meaning in a certain context. Therefore, the automatic interpretation of these sort of documents by computers entails three main steps: the detection of the symbols, the extraction of the structural relations among these symbols, and the modeling of the knowledge that permits the extraction of the semantics. Different domains in graphical documents include: architectural and engineering drawings, maps, flowcharts, etc. Graphics Recognition in particular and Document Image Analysis in general are born from the industrial need of interpreting a massive amount of digitalized documents after the emergence of the scanner. Although many years have passed, the graphical document understanding problem still seems to be far from being solved. The main reason is that the vast majority of the systems in the literature focus on a very specific problems, where the domain of the document dictates the implementation of the interpretation. As a result, it is difficult to reuse these strategies on different data and on different contexts, hindering thus the natural progress in the field. In this thesis, we face the graphical document understanding problem by proposing several relational models at different levels that are designed from a generic perspective. Firstly, we introduce three different strategies for the detection of symbols. The first method tackles the problem structurally, wherein general knowledge of the domain guides the detection. The second is a statistical method that learns the graphical appearance of the symbols and easily adapts to the big variability of the problem. The third method is a combination of the previous two inheriting their respective strengths, i.e. copes the big variability and does not need of annotated data. Secondly, we present two relational strategies that tackle the problem of the visual context extraction. The first one is a full bottom up method that heuristically searches in a graph representation the contextual relations among symbols. Contrarily, the second is syntactic method that models probabilistically the structure of the documents. It automatically learns the model, which guides the inference algorithm to counter the best structural representation for a given input. Finally, we construct a knowledge-based model consisting of an ontological definition of the domain and real data. This model permits to perform contextual reasoning and to detect semantic inconsistencies within the data. We evaluate the suitability of the proposed contributions in the framework of floor plan interpretation. Since there is no standard in the modeling of these documents, there exists an enormous notation variability and the sort of information included in the documents also varies from plan to plan. Therefore, floor plan understanding is a relevant task in the graphical document understanding problem. It is also worth to mention that, we make freely available all the resources used in this thesis (the data, the tool used to generate the data, and the evaluation scripts) aiming at fostering the research in graphical document understanding task.