Analyse de documents graphiques réalisés à main levée par combinaison de techniques de correspondance de graphes et de transformée de Hough : application au domaine de l'architecture
Institution:
Paris 8Disciplines:
Directors:
Abstract EN:
This thesis deals with the high-level automatic interpretation of paper documents. We have studied two of the major problems of graphics recognition: hatched pattern discrimination and symbol recognition. An application illustrates the proposed methods: a system to understand hand drawn architectural floor plans as an alternative cad input technique. The documents have been represented in basis of an attributed graph structure. Hatched patterns are detected in terms of their defining attributes: orientation, length and frequency of the filling segments. A hough-based transform is defined to map the edges of a graph to a parameter space where clusters define the attribute values of the hatched areas. The main advantage of this method is its flexibility since the attribute values of hatched patterns are computed from the document itself and they are not previously set. A second stage is the development of a symbol recognition algorithm using graph match, ing techniques. Since symbols to be recognized and the input document are represented by attributed graphs, symbol recognition is performed by looking for a subgraph isomorphism be, tween model and input graphs. To increase the robustness of the method against distortions the graph matching is computed by an error-tolerant subgraph isomorphism between region adja, cency graphs instead of plain graphs. This involves the definition of a region similarity criterion in terms of the string edit distance between region boundary strings. Finally, a last contribution is the design of a simple and fast method to detect perfect and distorted rotational and reflectional symmetries of 2d objects. The boundary of a shape is polygonally approximated and represented as a string. The set of minimum cost edit sequences that transform the shape string to a cyclically shifted version of itself define the rotational symmetry and its order. A modification of the algorithm is proposed to detect reflectional symmetries.
Abstract FR:
Cette these s'adresse a l'interpretation automatique a haut niveau de documents papier. On a etudie deux des plus importants problemes en reconnaissance de graphiques: la segmentation de parties hachurees et la reconnaissance de symboles. Une aplication sur plans d'architecture saisis de maniere bruitee ou a main levee a ete developee pour illustrer les methodes proposees. Les documents ont ete representes par rapport a une structure de graphe d'attributs. Les zones hachurees sont extraites grace aux attributs qui les definissent: orientation, longueur et frequence des droites de remplissage. On a defini une transformation de hough qui met en correspondance les aretes d'un graphe avec les points d'un espace de parametres ou les nuages de points determinent les valeurs des attributs des zones hachurees. C'est une methode flexible puisque les valeurs des attributs des zones hachurees sont calculees a partir du meme document, sans besoin de les etablir a priori. Une deuxieme phase est le developpement d'un algorithme de reconnaissance de symboles. Puisque les symboles a reconnaitre et le document d'entree sont representes par des graphes d'attributs, la reconnaissance est effectuee en cherchant un isomorphisme de sous-graphes entre un graphe modele et un graphe candidat. Pour ameliorer la robustesse de la methode par rapport au bruit la correspondance est plutot calculee avec un isomorphisme de graphes avec tolerance a l'erreur entre des graphes d'adjacence de regions. Il nous faut donc definir un critere de ressemblance entre regions, a partir de la distance d'edition entre deux chaines de primitives decrivant les contours des regions. Une derniere contribution est de proposer une methode simple et rapide pour detecter des symetries de rotation et axiales, parfaites ou avec du bruit, dans des objets 2d. Le contour d'une, forme est approche par un polygone et decrit avec une chaine. L'ensemble des sequences d'edition de moindre cout qui transforment la chaine decrivant la forme en une autre chaine, qui est la meme, mais cycliquement deplacee, definit la symetrie de rotation et son ordre.