Abstract
Near-duplicate image detection is a necessary operation to refine image search results for efficient user exploration. The existences of large amounts of near duplicates require fast and accurate automatic near-duplicate detection methods. We have designed a coarse-to-fine near duplicate detection framework to speed-up the process and a multi-modal integration scheme for accurate detection. The duplicate pairs are detected with both global feature (partition based color histogram) and local feature (CPAM and SIFT Bag-of-Word model). The experiment results on large scale data set proved the effectiveness of the proposed design.
Introduction: The Challenge of Near-Duplicate Detection
In the era of massive digital image repositories like Flickr and Google Images, search results are often cluttered with "near-duplicates"—images that are nearly identical but vary slightly in lighting, framing, or minor edits. Detecting these duplicates is essential for a clean user experience, but it presents a significant computational challenge.
Global features, such as overall color histograms, are fast but often fail to distinguish between images with similar color palettes but different subjects. Conversely, local features like SIFT are highly accurate but computationally expensive, making brute-force pairwise comparisons ($O(n^2)$ complexity) impractical for large datasets. This paper proposes a solution that bridges this gap using a coarse-to-fine framework.
The Coarse-to-Fine Framework
The proposed system utilizes a two-stage pipeline to minimize redundant computations by filtering out obvious non-matches before performing deep analysis.
Stage 1: Coarse Clustering (The Filter)
To avoid comparing every image pair, the system first partitions the collection into groups using inexpensive global features. The researchers employ a global color histogram in the HSV (Hue, Saturation, Value) color space. To improve robustness against framing changes, each image is divided into five regions—four corners and a center—and the color data is concatenated.
These features are then processed using Affinity Propagation clustering. Unlike traditional K-means, this algorithm automatically discovers the optimal number of clusters based on the data density, effectively grouping similar images for the next stage.
Stage 2: Fine Detection (The Deep Dive)
Within each cluster, the system performs a rigorous "multi-modal" check using two types of local features:
- CPAM (Color Pattern Appearance Model): This captures the spatial patterns of color and texture.
- SIFT Bag-of-Words (BoW): A standard computer vision technique that treats an image as a collection of "visual words" (interest points), allowing for object-specific matching even if lighting or backgrounds change.
To integrate these modalities, the authors use a statistical approach where non-duplicate matches are modeled via linear regression. Images that significantly deviate from this expected distribution are flagged as true near-duplicate outliers.
Experimental Results
The framework was evaluated on a dataset of 15,000 images with 190 manually extracted queries across 20 labeled categories.
- Efficiency: The cluster-based approach significantly reduced computational overhead. For an "outdoor commercial" category, the method took 22 seconds compared to 69 seconds for brute-force matching—a 68% reduction in runtime.
- Accuracy: The combined multi-modal model achieved a Mean Average Precision (mAP) of 0.8836, significantly outperforming SIFT alone (0.5650) or global color features alone (0.3540).
- Recall: The system maintained a high recall of 0.9007, successfully identifying over 90% of actual near-duplicates in the test set.
Conclusion
By combining fast global partitioning with detailed local feature fusion, this coarse-to-fine framework provides a scalable and accurate solution for managing near-duplicates in large-scale image search applications. Future work may involve adapting this framework to modern deep-learning-based embeddings and web-scale datasets containing billions of images.
Summary updated