Clustering near-duplicate images in large collections

ABSTRACT

Near-duplicate images introduce problems of redundancy and copyright infringement in large image collections. The problem is acute on the web, where appropriation of images without acknowledgment of source is prevalent. In this paper, we present an effective clustering approach for near-duplicate images, using a combination of techniques from invariant image local descriptors and an adaptation of near-duplicate text-document clustering techniques; we extend our earlier approach of near-duplicate image pairwise identification for this clustering approach. We demonstrate that our clustering approach is highly effective for collections of up to a few hundred thousand images. We also show --- via experimentation with real examples --- that ourapproach presents a viable solution for clustering near-duplicate images on the Web.

REFERENCES

• 1: Mayank Bawa , Tyson Condie , Prasanna Ganesan, LSH forest: self-tuning indexes for similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060840]
• 2: H. Bay, T. Tuytelaars, and L. V. Gool. Surf: Speeded up robust features. In Proc. ECCV, May 2006.
• 3: Y. Bernstein and J. Zobel. A scalable system for identifying co-derivative documents. In Proc. SPIRE, pages 55--67, October 2004.
• 4: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Computer Networks and ISDN Systems, v.29 n.8-13, p.1157-1166, Sep. 1997
• 5: E. Y. Chang, C. Li, J. Z. Wang, P. Mork, and G. Wiederhold. Searching near-replicas of images via clustering. In Proc. SPIE, pages 281--292, September 1999.
• 6: Y. Chen, J. Z. Wang, and R. Krovetz. CLUE: Cluster-based retrieval of images by unsupervised learning. IEEE Trans. on Image Processing, 14(8):1187--1201, 2005.
• 7: Ondřej Chum , James Philbin , Michael Isard , Andrew Zisserman, Scalable near identical image and shot detection, Proceedings of the 6th ACM international conference on Image and video retrieval, p.549-556, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282359]
• 8: Jun Jie Foo , Ranjan Sinha, Pruning SIFT for scalable near-duplicate image matching, Proceedings of the eighteenth conference on Australasian database, p.63-71, January 30-February 02, 2007, Ballarat, Victoria, Australia
• 9: J. J. Foo, R. Sinha, and J. Zobel. Discovery of image versions in large collections. In Proc. MMM, pages 433--442, Jaunary 2007.
• 10: Jun Jie Foo , Justin Zobel , Ranjan Sinha , S. M. M. Tahaghoghi, Detection of near-duplicate images for web search, Proceedings of the 6th ACM international conference on Image and video retrieval, p.557-564, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282360]
• 11: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 12: Kristen Grauman , Trevor Darrell, Efficient Image Matching with Distributions of Local Invariant Features, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.627-634, June 20-26, 2005 [doi>10.1109/CVPR.2005.138]
• 13: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 14: Alejandro Jaimes , Shih-Fu Chang , Alexander C. Loui, Duplicate detection in consumer photography and news video, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641098]
• 15: Hideo Joho , Mark Sanderson, The SPIRIT collection: an overview of a large web collection, ACM SIGIR Forum, v.38 n.2, p.57-61, December 2004 [doi>10.1145/1041394.1041395]
• 16: Y. Ke and R. Sukthankar. PCA-SIFT: A more distinctive representation for local image descriptors. In Proc. CVPR, pages 506--513, June 2004.
• 17: Yan Ke , Rahul Sukthankar , Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027729]
• 18: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 19: C.-S. Lu and C.-Y. Hsu. Geometric distortion-resilient image hashing scheme and its applications on copy detection and authentication. Multimedia Systems, 11(2):159--173, 2005.
• 20: Y. Meng, E. Y. Chang, and B. Li. Enhancing DPF for near-replica image recognition. In Proc. CVPR, pages 416--423, June 2003.
• 21: K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. In Proc. CVPR, pages 257--263, June 2003.
• 22: Krystian Mikolajczyk , Cordelia Schmid, Scale & Affine Invariant Interest Point Detectors, International Journal of Computer Vision, v.60 n.1, p.63-86, October 2004 [doi>10.1023/B:VISI.0000027790.02288.f2]
• 23: Arun Qamra , Yan Meng , Edward Y. Chang, Enhanced Perceptual Distance Functions and Indexing for Image Replica Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.379-391, March 2005 [doi>10.1109/TPAMI.2005.54]
• 24: Narayanan Shivakumar , Hector Garcia-Molina, Finding Near-Replicas of Documents and Servers on the Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.204-212, March 27-28, 1998
• 25: Josef Sivic , Andrew Zisserman, Video Google: A Text Retrieval Approach to Object Matching in Videos, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1470, October 13-16, 2003
• 26: Dong-Qing Zhang , Shih-Fu Chang, Detecting image near-duplicate by stochastic attributed relational graph matching with learning, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027730]
• 27: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clustering near-duplicates, image clustering, near-duplicate detection