Quadruplet-Wise Image Similarity Learning

Marc T. Law, Nicolas Thome, Matthieu Cord

Abstract

Traditional similarity learning relies on pairwise or triplet constraints, which often fail to capture the nuances of complex semantic structures like class hierarchies or relative attributes. This paper introduces a novel framework based on quadruplet-wise constraints. By modeling the relationship between four images simultaneously—specifically, comparing the dissimilarity between two pairs—the proposed method achieves more robust distance metrics. The approach is validated across tasks including face attribute ranking, hierarchical image classification, and unsupervised webpage change detection, demonstrating significant improvements over existing state-of-the-art methods.

Introduction

Similarity learning is fundamental to computer vision applications such as face verification and image retrieval. Most existing methods utilize pairwise constraints (determining if two images belong to the same class) or triplet constraints (determining if image A is more similar to B than to C).

However, these approaches can be "brittle" when dealing with complex data. For instance, in a biological hierarchy, a "Husky" is semantically closer to a "Wolf" than to a "Poodle," yet both are far more similar to each other than to an inanimate object like a "Car." Standard triplet methods often struggle to encode such multi-level relationships without introducing noise. Similarly, in "relative attribute" tasks—such as ranking faces by the intensity of a smile—pairwise labels are often inconsistent due to human annotator subjectivity. This paper addresses these challenges by learning a robust distance metric that exploits rich semantic structures efficiently.

Methodology: The Quadruplet-Wise Strategy

The core innovation is the Quadruplet-wise (Qwise) strategy. Rather than comparing images directly, the framework compares dissimilarities between pairs.

The Qwise Constraint

The model learns a Mahalanobis-like distance function $D_W$ such that for a given quadruplet $(p_i, p_j, p_k, p_l)$, the dissimilarity between the first pair is strictly smaller than that of the second: $$D(p_i, p_j) < D(p_k, p_l)$$

Metric Formulation and Optimization

To prevent overfitting, the authors employ a diagonal Positive Semi-Definite (PSD) matrix $W$. This choice ensures the number of parameters remains linear relative to the input dimension. The learning process is formulated as a convex optimization problem using a differentiable surrogate loss to approximate the hinge loss, allowing the model to handle millions of constraints efficiently.

Experimental Evaluation

The Qwise method was evaluated across three distinct domains:

  1. Relative Attributes: Using the OSR (Outdoor Scene Recognition) and Pubfig (Public Figure Face) datasets, the model ranked attributes like "naturalness" or "smiling." By comparing the "gap" between extreme classes against intermediate ones, the Qwise strategy effectively filters out noise from ambiguous middle-ground labels.
Example of a smiling face from the Pubfig dataset used for relative attribute ranking.
  1. Hierarchical Learning: The method was tested on 9 subtrees from ImageNet (e.g., Amphibians, Fruit) to learn metrics respecting taxonomic distances.
  2. Webpage Dynamics: A new dataset was created by crawling news homepages. Time served as a proxy for similarity, allowing the model to learn a spatial weighting map unsupervised.

Key Results and Insights

  • Performance Gains: On the Pubfig dataset, Qwise combined with Large Margin Nearest Neighbor (LMNN) achieved 77.6% accuracy, significantly outperforming the 71.3% baseline.
  • Hierarchical Accuracy: The method achieved a global accuracy of 36.4% across ImageNet subtrees, setting a new benchmark.
  • Semantic Spatial Weighting: In the webpage task, the model automatically learned to assign low weights to "noisy" regions like advertisements and high weights to primary news content, improving Mean Average Precision (MAP) by 14.3% over Euclidean baselines.

Conclusion

The Quadruplet-wise framework provides a robust and efficient way to learn similarity metrics from complex semantic data. By focusing on the relative differences between pairs, it overcomes the limitations of traditional pairwise and triplet-based approaches.

Summary updated

Abstract

This paper introduces a novel similarity learning framework. Working with inequality constraints involving quadruplets of images, our approach aims at efficiently modeling similarity from rich or complex semantic label relationships. From these quadruplet-wise constraints, we propose a similarity learning framework relying on a convex optimization scheme. We then study how our metric learning scheme can exploit specific class relationships, such as class ranking (relative attributes), and class taxonomy. We show that classification using the learned metrics gets improved performance over state-of-the-art methods on several datasets. We also evaluate our approach in a new application to learn similarities between web page screenshots in a fully unsupervised way.
BibTeX
@inproceedings{law2013quadruplet,
  author = {Marc T. Law and Nicolas Thome and Matthieu Cord},
  title = {{Quadruplet-Wise Image Similarity Learning}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  doi = {10.1109/iccv.2013.38},
}
Figure