Fuzzy Intervals for Designing Structural Signature: An Application to Graphic Symbol Recognition

Muhammad Muzzamil Luqman, Mathieu Delalandre, Thierry Brouard, Jean-Yves Ramel, Josep Lladós

TL;DR

This paper introduces a novel method for graphic symbol recognition by combining structural representations with fuzzy logic and Bayesian networks. It addresses the challenge of noise and deformations in graphic documents by using fuzzy intervals to create robust "structural signatures," which are then classified using a learned Bayesian network.

What Problem Does This Paper Address?

Recognizing graphic symbols in documents (like architectural plans or electronic schematics) is a challenging task due to variations in drawing styles, noise, and deformations. Traditional methods often struggle with these imperfections. While structural approaches capture the relationships between graphic elements well, they can be sensitive to noise. Statistical methods are more robust to noise but may not capture the rich structural information as effectively. This paper aims to bridge this gap by developing a system that leverages the strengths of both structural and statistical approaches, specifically focusing on creating robust representations that can handle real-world imperfections.

Methods

The proposed method consists of three main phases:

  1. Representation Phase: Graphic symbols are first vectorized and then represented as an Attributed Relational Graph (ARG). Nodes in the ARG represent primitives (like lines), and arcs represent their topological and geometric relationships (e.g., connection type, relative length, relative angle).
  2. Description Phase (Fuzziness of Signature): To enhance robustness against noise and deformations, the paper introduces "fuzzy intervals" for feature extraction. Instead of using rigid numerical boundaries for features like primitive length or connection angles, fuzzy intervals (overlapping ranges) are used. This allows the system to be more tolerant to slight variations. These features are then combined into a "structural signature."
  3. Learning and Classification Phase: A Bayesian network is learned from the structural signatures of known symbols. This network models the joint probability distribution of the features. For recognition, a query symbol's signature is fed into the learned Bayesian network, which then computes the posterior probability of the query symbol belonging to each class. This probabilistic approach helps in handling uncertainty and can implicitly prune irrelevant features.

Datasets

The experiments were conducted using datasets derived from the GREC (Graphics Recognition) contests, specifically:

  • GREC2005 and GREC2007 databases (which contain similar sets of models).
  • GREC2003 database (a subset of GREC2005).

The authors generated their own learning and test sets by applying various deformations (rotations, scaling, hand-drawn distortions) and degradations (binary noise, simulated photocopying/scanning) to the original GREC models. They also created a new benchmark for "contextual noise" by cropping symbols from complete documents.

Key Insights and Ideas

  • Fuzzy Intervals for Robustness: The core innovation is the use of overlapping fuzzy intervals to represent features in the structural signature. This directly addresses the sensitivity of structural representations to noise and deformations, making the signatures more resilient.
  • Hybrid Approach Synergy: Combining the descriptive power of structural representations (ARGs) with the probabilistic reasoning and uncertainty handling of Bayesian networks creates a powerful recognition system.
  • Bayesian Networks for Feature Selection: The learned Bayesian network implicitly handles feature selection by identifying conditional independencies, allowing the system to focus on the most discriminative features.
  • Scalability through Uncertainty Management: By managing uncertainty at the signature design and classification stages, the system aims for improved scalability to a larger number of symbol models.

Key Results

  • High Accuracy on Clean Symbols: The method achieved 100% recognition rates on clean symbols (rotated and scaled), demonstrating invariance to these transformations.
  • Competitive Performance on Deformations: The system performed competitively with GREC contest participants for low levels of deformation and degradation.
  • Robustness to Contextual Noise: Experiments with symbols cropped from documents showed promising results, indicating the system's ability to handle "contextual noise" without explicit pre-processing.
  • Scalability Demonstrated: The paper shows the system's performance across varying numbers of symbol classes (from 20 to 150), demonstrating its scalability.

Limitations and Future Work

  • Sensitivity to High Degradations: Recognition rates decreased significantly with higher levels of deformation and binary degradations, which the authors attribute to irregularities introduced during vectorization.
  • Handling of Arcs and Circles: The vectorization technique used has limitations in handling arcs and circles, impacting recognition rates for symbols with these features.
  • Future Work: The authors plan to extend this method for symbol spotting and indexation of line drawing documents, leveraging its efficiency and scalability. They also suggest that recognition rates could be further improved with real learning sets that include deformed and degraded examples.

Summary updated

Abstract

The motivation behind our work is to present a new methodology for symbol recognition. The proposed method employs a structural approach for rep-resenting visual associations in symbols and a statistical classifier for recognition. We vectorize a graphic symbol, encode its topological and geometrical informa-tion by an attributed relational graph and compute a signature from this structural graph. We have addressed the sensitivity of structural representations to noise, by using data adapted fuzzy intervals. The joint probability distribution of signa-tures is encoded by a Bayesian network, which serves as a mechanism for pruning irrelevant features and choosing a subset of interesting features from structural signatures of underlying symbol set. The Bayesian network is deployed in a su-pervised learning scenario for recognizing query symbols. The method has been evaluated for robustness against degradations & deformations on pre-segmented 2D linear architectural & electronic symbols from GREC databases, and for its recognition abilities on symbols with context noise i.e. cropped symbols. Key words: symbol recognition, overlapping fuzzy interval, structural signature, Bayesian network. 1
BibTeX
@inproceedings{luqman2009fuzzy,
  author = {Muhammad Muzzamil Luqman and Mathieu Delalandre and Thierry Brouard and Jean-Yves Ramel and Josep Lladós},
  title = {{Fuzzy Intervals for Designing Structural Signature: An Application to Graphic Symbol Recognition}},
  booktitle = {GREC},
  year = {2009},
  doi = {10.1007/978-3-642-13728-0\_2},
}

Loading related content...

Figure