Using Bags of Symbols for Automatic Indexing of Graphical Document Image Databases

Eugen Barbu, Pierre Héroux, Sébastien Adam, Éric TrupinGREC 2005 · DOI

TL;DR

This paper introduces a novel method for automatically indexing and retrieving graphical document images by representing them as "bags of symbols." This approach overcomes the limitations of text-based indexing by extracting meaningful graphical patterns, akin to "words" in text, allowing for more intuitive and effective querying of complex visual data.

What Problem Does This Paper Address?

Traditional document image analysis and retrieval systems heavily rely on textual content or require extensive manual annotation. This leaves a significant gap when dealing with predominantly graphical documents like maps, architectural plans, or electronic schematics, where the visual layout and relationships between elements are crucial. Existing methods struggle to automatically understand and index the visual information without human intervention, leading to inefficient search and retrieval. The authors aim to bridge this gap by developing an unsupervised method to extract and utilize graphical features for indexing and querying.

Methods

The core of this paper lies in its innovative approach to representing graphical documents. The authors adapt the "bag of words" concept from Information Retrieval to the visual domain, proposing a "bag of symbols" representation.

Here's a breakdown of their methodology:

  • Graph Representation: Document images are first converted into a graph structure. Connected components within the image are identified and represented as nodes in the graph. Features like rotation and translation invariant Zernike moments are extracted for each component. A clustering procedure is then used to assign nominal labels to these components, creating a labeled graph where nodes represent distinct visual elements.
  • Graph Mining for Symbols: Frequent subgraphs within these document graphs are identified using graph mining techniques, specifically the Frequent Subgraph Discovery (FSG) algorithm. These frequent subgraphs are treated as "symbols" – the fundamental building blocks of the graphical documents.
  • Bag of Symbols Representation: Each document is then represented as a "bag of symbols," essentially a collection of the identified symbols and their frequencies within that document. This is complemented by a vector of connected component labels.
  • Dissimilarity Measure: A dissimilarity measure based on cosine correlation is employed to quantify the difference between two document representations (two "bags of symbols"). This measure uses entropy-weighting to assign importance to symbols.
  • Querying: Queries can be made using images, lists of symbols, or lists of connected components. The system then uses graph matching to identify symbols within the query image and retrieves documents with similar symbol compositions.

Datasets

The corpus used for evaluation consists of 60 images categorized into:

  • Electronic schemas (25 images)
  • Architectural schemas (5 images)
  • Engineering maps (30 images)

The paper does not mention the introduction of new benchmark datasets but rather uses this curated corpus for their experiments.

Key Insights and Ideas

  • Visual "Words": The concept of treating frequent subgraphs as "symbols" is a powerful analogy to "words" in text, enabling the application of established IR principles to visual data.
  • Unsupervised Learning: The method's ability to discover these symbols automatically, without human annotation, is a significant advantage, reducing the cost and effort of indexing large graphical document collections.
  • Bridging the Semantic Gap: By moving beyond low-level features to higher-level graphical patterns (symbols), the approach aims to reduce the semantic gap between how users perceive and describe documents and how the system represents them.
  • Robustness to Noise: The paper acknowledges that the discovered symbols might not be perfect due to image noise and clustering imperfections, but demonstrates that the approach still captures meaningful correlations.

Key Results

  • Classification Performance: The "bag of symbols" representation, especially when combined with simple geometric features, significantly improved classification accuracy compared to using only simple geometric features. The combined approach achieved a 96.67% classification rate.
  • Visual Separation: Multidimensional scaling plots (Figure 4) visually demonstrate that the "bag of symbols" representation leads to better separation between document classes in a 2D space compared to using only simple geometric features.
  • Query Examples: Table 4 provides examples of queries and their most relevant retrieved documents, showcasing the system's ability to find similar graphical documents based on symbol composition. Table 5 presents recall and precision metrics for various queries, indicating promising retrieval performance.

Limitations and Future Work

  • Symbol Imperfection: The authors acknowledge that the discovered symbols are not always perfect due to image noise and clustering procedure imperfections.
  • Error Propagation: They plan to investigate how noise affects connected component labeling and how an incorrect number of clusters impacts the graph mining procedure.
  • Error-Tolerant Matching: Future work includes exploring graph-based techniques that can handle error-tolerant graph matching to improve robustness.
  • Textual Document Layouts: The authors intend to apply this approach to layout structures of textual documents in the future.

Summary updated

BibTeX
@inproceedings{barbu2005using,
  author = {Eugen Barbu and Pierre Héroux and Sébastien Adam and Éric Trupin},
  title = {{Using Bags of Symbols for Automatic Indexing of Graphical Document Image Databases}},
  booktitle = {GREC},
  year = {2005},
  doi = {10.1007/11767978\_18},
}
Figure