Fast near duplicate detection for personal image collections

ABSTRACT

Due to the rapid growth in personal image collections, there is increasing interest on automatic detection of near duplicates. In this paper, we propose a novel fast near duplicate detection framework that takes advantages of heterogeneous features like EXIF data, global image histogram and local features. To improve the accuracy of local feature matching, we have developed a structure matching algorithm that takes into account of a local feature's neighborhood which can effectively reject mismatches. In addition, we developed a computation-sensitive cascade framework to combine stage classifiers trained on different feature spaces with different computational cost. This method can quickly accept easily identified duplicates using only cheap features without the need to extract more sophisticate but expensive ones. Compared with existing approaches, our experiments show very promising results using our new approach in terms of both efficiency and effectiveness.

REFERENCES

• 1: Y. Jing, S. Baluja: PageRank for product image search. WWW 2008: 307--316
• 2: Y. Ke, R. Sukthankar and L. Huston. Efficient near-duplicate detection and sub-image retrieval. ACM Multimedia 2004.
• 3: D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60 (2): 91--110.
• 4: K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir and L. Van Gool, A comparison of affine region detectors. In IJCV, 2005.
• 5: C. Ngo, W. Zhao and Y. Jiang. Fast tracking of nearduplicate keyframes in broadcast domain with transitivity propagation. ACM Multimedia 2006.
• 6: A. Qamra, Y. Meng and E. Chang. Enhanced perceptual distance functions and indexing for image replica recognition. IEEE PAMI, 27(3): 379--391, 2005.
• 7: Y. Rubner, C. Tomasi and L. Guibas. The earth mover distance as a metric for image retrieval. IJCV, 40(2), 2000.
• 8: F. Tang, S. Lim, N. Chang and H. Tao. A Novel Feature Descriptor Invariant to Complex Brightness Changes. CVPR 2009.
• 9: P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. CVPR 2001.
• 10: X. Wu, A. Hauptmann and C. Ngo. Practical elimination of near-duplicates from web video search. ACM Multimedia 2007.
• 11: D. Zhang and S. Chang. Detecting image near-duplicate by stochastic attribute relational graph matching with learning. ACM Multimedia 2004.
• 12: J. Zhu, S. Hoi, M. Lyu and S. Yan. Near--Duplicate keyframe retrieval by nonrigid image matching. ACM Multimedia 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.9 Applications

General Terms:
Algorithms, Experimentation, Performance

Keywords:
computation-sensitive cascade classifier, near duplicate detection, structure image matching