De l'appariement de graphes symboliques à l'appariement de graphes numériques : Application à la reconnaissance de symboles

Rashid-Jalal Qureshi, Jean-Yves Ramel, Hubert CardotHAL 2006

TL;DR

This paper introduces a novel method for recognizing graphical symbols by representing them as attributed graphs. It proposes a new similarity measure that combines numerical and structural information, making it robust to rotation, scaling, and noise, and demonstrates high recognition rates on challenging datasets.

What Problem Does This Paper Address?

Recognizing graphical symbols, like those found in technical drawings or diagrams, is a fundamental task in computer vision. Traditional methods often represent these symbols as structural graphs. However, a major challenge arises during the "graph matching" phase: comparing these graphs to identify a symbol. Standard graph isomorphism algorithms struggle when images are degraded by noise or distortions, leading to poor performance. This paper aims to overcome this limitation by developing a more robust graph matching technique that can handle these imperfections.

Methods

The core of this work lies in two key areas:

  • Symbol Representation: Symbols are first decomposed into structural primitives, specifically quadrilaterals, which are then used to construct an attributed graph.
  • Nodes: Each quadrilateral becomes a node in the graph.
  • Node Attributes: Nodes are assigned numerical attributes like their relative length (invariant to scaling) and angle.
  • Edges: Arcs in the graph represent topological relationships between these quadrilaterals.
  • Edge Attributes: Edges are assigned attributes like the relative angle between connected quadrilaterals (invariant to rotation). This combination of numerical and structural attributes makes the representation robust to affine transformations.
  • Graph Matching: A novel similarity measure is proposed to compare these attributed graphs.
  • Attributed Graph Matching: The method calculates similarity based on the distances between attributes of matched nodes and edges.
  • Penalty Mechanism: A unique feature is a penalty mechanism that allows for imperfect matching, where one node/edge in one graph can correspond to multiple nodes/edges in another. This is crucial for handling noise and distortions.
  • Iterative Matching Algorithm (SimGraph): A greedy-like algorithm is used to find the best possible matching between two graphs, prioritizing matches that maximize the similarity score.

Datasets

The authors evaluated their system using the GREC2003 dataset. They generated a set of 1100 symbol examples with various distortions, including rotations, scaling, noise, and vector distortions.

Key Insights and Ideas

  • Bridging Symbolic and Numerical: The paper effectively bridges the gap between purely symbolic graph representations and purely numerical approaches by creating attributed graphs. This allows for the incorporation of precise numerical information (like lengths and angles) alongside structural relationships.
  • Robustness through Invariance: By using relative lengths and angles as attributes, the graph representation becomes inherently invariant to rotation and scaling, which are common challenges in image recognition.
  • Handling Imperfect Matches: The introduction of a penalty mechanism for imperfect matching is a significant contribution. This allows the system to tolerate noise and distortions that would typically break traditional graph matching algorithms.
  • Learning New Symbols: The proposed system is designed to be easily adaptable to new symbols by simply providing images of the new model, suggesting a path towards a more general symbol recognition system.

Key Results

  • 100% Recognition for Affine Transformations: The system achieved a 100% recognition rate for test images that were only subjected to rotations and scaling.
  • High Performance on Noisy Data: For more complex distortions (noise and vector distortions), the system still achieved high recognition rates, comparable to or better than other participants in the GREC'03 competition. For example, for "Niveau-1" noise, a 96.8% recognition rate was achieved.
  • Strong Discriminative Power: The similarity measure demonstrated a strong ability to discriminate between different symbols, even when they were transformed.

Limitations and Future Work

  • Noise Preprocessing: The authors acknowledge that their system's performance on noisy images could be further improved by incorporating preprocessing steps like filtering or removing small quadrilaterals that might introduce spurious nodes.
  • Complex Shapes: The current method is primarily designed for linear graphical symbols. Future work aims to extend the system to recognize more complex symbols, including those with filled shapes, by adding more numerical and symbolic attributes to nodes and edges.
  • Computational Complexity: While the proposed matching algorithm is more efficient than exhaustive search, the paper hints at the need for further optimization for very large datasets.

Summary updated

Abstract

Les representations sous forme de graphes structurels ont ete appliquees dans un grand nombre de problemes en vision par ordinateur et en reconnaissance de formes. Neanmoins, lors de l'etape d'appariement de graphes, les algorithmes classiques d'isomorphisme de graphes sont peu performants quand l'image est degradee par du bruit ou des distorsions vectorielles. Cet article traite de la reconnaissance de symboles graphiques grâce a la formulation d'une nouvelle mesure de similarite entre leur representation sous forme de graphes etiquetes. Dans l'approche proposee, les symboles sont d'abord decomposes en primitives structurelles et un graphe attribue est alors genere pour decrire chaque symbole. Les nœuds du graphe representent les primitives structurelles tandis que les arcs decrivent les relations topologiques entre les primitives. L'utilisation d'attributs numeriques pour caracteriser les primitives et leurs relations permet d'allier precision et, invariance a la rotation et au changement d'echelle. Nous proposons egalement une nouvelle technique d'appariement de graphes basee sur notre fonction de similarite qui utilise les valeurs numeriques des attributs pour produire un score de similarite. Cette mesure de similarite a de nombreuses proprietes interessantes comme un fort pouvoir de discrimination, une invariance aux transformations affines et une faible sensibilite au bruit.
BibTeX
@inproceedings{qureshi2006de,
  author = {Rashid-Jalal Qureshi and Jean-Yves Ramel and Hubert Cardot},
  title = {{De l'appariement de graphes symboliques à l'appariement de graphes numériques : Application à la reconnaissance de symboles}},
  booktitle = {HAL},
  year = {2006},
}
Figure