Weighted Symbols-Based Edit Distance for String-Structured Image Classification

Cécile Barat, Christophe Ducottet, Élisa Fromont, Anne-Claire Legrand, Marc Sebban

TL;DR

This paper introduces a novel "weighted symbols-based edit distance" (WED) that allows symbols in string representations of images to carry real-valued weights, inspired by TF-IDF from information retrieval. This approach enhances image classification by capturing both structural information and the importance of visual features, outperforming standard edit distance and competing well with vector-based methods.

What Problem Does This Paper Address?

Traditional image classification often relies on representing images as feature vectors (e.g., histograms). While efficient, these methods can lose crucial structural information about how image elements relate to each other. Recent trends explore representing images as structured data like strings, trees, or graphs, and comparing them using edit distances. However, standard edit distances treat all symbols equally. This paper addresses the limitation of existing methods by proposing a way to incorporate the importance of individual symbols (visual words) into the string comparison process, moving beyond simple symbol matching. This is particularly relevant for "bag-of-visual-words" models, where visual words are derived from image patches and their significance can vary greatly.

Methods

The core contribution is a Weighted Symbols-based Edit Distance (WED). Instead of treating symbols as binary (present or absent), WED allows symbols to have real-valued weights.

  • Weighted Symbols: Images are represented as strings where each symbol (a visual word) is paired with a real-valued weight. This weight is derived using a TF-IDF (Term Frequency-Inverse Document Frequency) scheme, similar to text document analysis, to quantify the importance and discriminative power of a visual word within an image and across a collection.
  • Novel Edit Cost Function: A new edit cost function c(a, b) is defined for comparing two weighted symbols a = (symbol_a, weight_a) and b = (symbol_b, weight_b). The cost is max(weight_a, weight_b) if the symbols are different, and |weight_a - weight_b| if they are the same. This function is proven to maintain the properties of a distance metric.
  • Dynamic Programming Algorithm: The WED is computed using a dynamic programming approach, similar to the standard Levenshtein distance, but incorporating the new weighted edit cost function. This allows for efficient computation in O(T × V) time, where T and V are the lengths of the strings.
  • Learned Substitution Costs: An extension is proposed where substitution costs are learned based on the relationships between visual words. A Minimum Spanning Tree (MST) is built on the visual vocabulary (cluster centers), and the number of edges between two symbols in the MST determines their substitution cost. This aims to favor substitutions between visually similar words.

Datasets

The experiments were conducted on the SIMPLIcity collection, which contains 1000 images from the COREL database. These images are categorized into 10 meaningful classes (African people, beaches, buildings, buses, dinosaurs, elephants, flowers, food, horses, and mountains), with 100 images per category. The dataset is used for evaluating classification accuracy using a 10-fold cross-validation.

Key Insights and Ideas

  • Symbol Importance Matters: The paper demonstrates that simply treating symbols as equal in edit distance calculations discards valuable information. By assigning weights (like TF-IDF) to symbols, the classification performance significantly improves.
  • Bridging Vector and Structured Approaches: WED offers a way to combine the strengths of vector-based representations (which capture feature importance via weights) with structured representations (which capture spatial relationships).
  • TF-IDF for Visual Words: Adapting the TF-IDF concept from text to visual words provides a principled way to quantify the significance of visual features in image classification.
  • Learned Costs Enhance Performance: Learning substitution costs based on visual similarity (via MST) further boosts classification accuracy, suggesting that the "cost" of changing one visual word to another should reflect their inherent similarity.

Key Results

  • WED outperforms Standard ED: The proposed WED consistently achieved higher classification accuracy than the standard edit distance (ED), even when ED was modified to simulate weights by repeating symbols. The difference was statistically significant.
  • Competitive with Vector Metrics: WED showed strong performance compared to traditional vector space metrics like normalized dot product and Minkowski distances (L1, L2, L∞), especially for smaller vocabulary sizes. It often provided the best global behavior.
  • MST-based Costs Improve Accuracy: Incorporating MST-based learned substitution costs further improved WED's classification accuracy and increased the performance gap compared to the L1 distance.

Limitations and Future Work

  • Alphabet Size Impact: While WED performs well, its performance is influenced by the alphabet size (number of visual words). The paper explores this variation in experiments.
  • Generalization to Trees/Graphs: The current WED is for string-structured data. The authors suggest that the approach could be extended to tree and graph edit distances for more complex structured data.
  • Integration with Other Classifiers: While tested with a 1-NN classifier, the authors note that WED can be integrated into edit kernels for Support Vector Machines and other advanced classifiers.
  • Application to Other Fields: The authors propose that this weighted edit distance could be valuable in other domains dealing with sequential or structured data, such as molecular biology.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{barat2010weighted,
  author = {Cécile Barat and Christophe Ducottet and Élisa Fromont and Anne-Claire Legrand and Marc Sebban},
  title = {{Weighted Symbols-Based Edit Distance for String-Structured Image Classification}},
  booktitle = {ECML/PKDD},
  year = {2010},
  doi = {10.1007/978-3-642-15880-3\_11},
}

Loading related content...

Figure