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