Efficient Near-duplicate Detection and Sub-image Retrieval
by Yan Ke, Rahul Sukthankar,
and Larry Huston
We introduce a system for near-duplicate detection and sub-image retrieval. Such a system
useful for finding copyright violations and detecting forged images.
We define near-duplicates as images altered with common transformations such
as changing contrast, saturation, scaling, cropping, framing, etc.
Our system builds a parts-based representation of images using
distinctive local descriptors which give high quality
matches even under severe transformations. To cope with the
large number of features extracted from the images, we employ
locality-sensitive hashing to index the local descriptors.
This allows us to make approximate similarity queries
that only examine a small fraction of the database. Although
locality-sensitive hashing has excellent theoretical performance
properties, a standard implementation would still be unacceptably
slow for this application. We show that, by optimizing layout and
access to the index data on disk, we can efficiently query indices
containing millions of keypoints. Our system achieves near-perfect
accuracy (100% precision at 99.85% recall) on the tests used by
Meng et al., and consistently strong results
on our own, significantly more challenging experiments. Query
times are interactive even for collections of thousands of images.
Y. Ke, R. Sukthankar, and L. Huston. ACM Multimedia,
2004. [PDF 560KB]
Datasets used in the experiments are available
Page maintained by Yan Ke < y k e @ c m u . e d u >