Abstract
Application of multimedia technologies to visual data, like still images and videos, is receiving an increasing attention especially for the large number of potential innovative solutions which are expected to emerge in the next years. In this context, techniques for retrieval by visual similarity are expected to boost the interest of users through the definition of novel paradigms to access digital repositories of visual data. In this paper, we define a novel model for active graph matching and describe its application to content based retrieval of images. The proposed solution fits with the class of edit distance based techniques and supports active node merging during the graph matching process. A theoretical analysis of the computational complexity of the proposed solution is presented and a prototype system is experimented on the images of two sample image collections.
Introduction
In the field of computer vision and Content-Based Image Retrieval (CBIR), representing images as graphs is a powerful paradigm. Images are typically segmented into regions, which are represented as nodes, while the spatial relationships between these regions are captured as edges. However, image segmentation is inherently imprecise. Factors such as lighting variations, sensor noise, and viewpoint changes can cause a single semantic object to be segmented differently across images. For example, a single object in a query image might be "over-segmented" into multiple regions in a database image.
Standard graph matching algorithms, which often seek isomorphisms or rigid inexact matches, struggle with these structural discrepancies. When topologies do not align perfectly, similarity scores drop, leading to poor retrieval performance. This paper addresses the rigidity of traditional graph representations by introducing Active Graph Matching, a technique that allows for dynamic structural adjustments during the matching process.
Active Graph Matching Framework
The proposed solution extends the standard Graph Edit Distance (GED) framework. Traditionally, GED measures the similarity between two graphs by calculating the minimum cost of transforming one into the other using three primary operations: insertion, deletion, and substitution of nodes and edges.
The core innovation of this work is the introduction of the Node Merging Operator. Unlike static GED, which treats the graph structure as fixed, Active Graph Matching allows the algorithm to identify and fuse "compatible" adjacent nodes—such as regions sharing similar color or texture properties—on the fly.
The Merging Process
During matching, the algorithm generates "virtual nodes" that represent the union of compatible neighboring regions. This "active" approach enables the graph to evolve toward a common structure that better reflects the underlying semantic content. For instance, if merging two nodes in a database graph creates a better match for a single node in the query graph, the algorithm performs the merge.
From a cost perspective, merging is designed to be "cheaper" than the traditional sequence of deletion and substitution. This is because merging preserves visual information rather than discarding it. The authors utilize a "context dissimilarity function" to determine when a merge is appropriate, considering both the intrinsic features of the nodes (e.g., color, area) and their local neighborhood context. When nodes are merged, features are propagated: the new virtual node's area is the sum of its components, and its color is calculated as the weighted mean.
To manage the computational complexity—since graph matching is NP-complete—the authors employ a greedy search strategy. For each node in the query graph, the system searches for the optimal match in the target graph by evaluating both existing nodes and potential virtual nodes created through merging.
Experimental Evaluation
The effectiveness of the Active Graph Matching approach was evaluated using two distinct image collections:
- WebMuseum: A dataset of 1,000 paintings characterized by diverse artistic styles and complex segmentations.
- ALOI (Amsterdam Library of Object Images): A large-scale collection of physical objects. A subset of 12,000 images was used to test robustness against variations in illumination and viewing angles.
Key Results
The experimental results demonstrate that "Active" matching consistently outperforms "Static" matching methods. On the WebMuseum dataset, the inclusion of the node merging operator significantly boosted precision, particularly for top-ranked retrieval results. In the ALOI experiments, the system achieved a high precision of 0.91 at 0.5 recall, proving its robustness against segmentation errors caused by shadows and highlights. Despite the overhead of considering virtual nodes, the greedy implementation maintained practical retrieval times for databases of this scale.
Conclusion
Active Graph Matching provides a flexible and robust framework for image retrieval by addressing the limitations of static graph representations. By allowing nodes to merge dynamically, the system effectively "heals" over-segmentation errors that typically degrade matching performance.
While the current greedy approach is efficient, it may occasionally miss globally optimal matches. Future work could explore more sophisticated feature propagation rules, incorporating texture or shape descriptors that combine in non-linear ways. Additionally, scaling the approach to even larger datasets while maintaining computational efficiency remains an area for further optimization.
Summary updated