Scalable near identical image and shot detection

ABSTRACT

This paper proposes and compares two novel schemes for near duplicate image and video-shot detection. The first approach is based on global hierarchical colour histograms, using Locality Sensitive Hashing for fast retrieval. The second approach uses local feature descriptors (SIFT) and for retrieval exploits techniques used in the information retrieval community to compute approximate set intersections between documents using a min-Hash algorithm.

The requirements for near-duplicate images vary according to the application, and we address two types of near duplicate definition: (i) being perceptually identical (e.g. up to noise, discretization effects, small photometric distortions etc); and (ii) being images of the same 3D scene (so allowing for viewpoint changes and partial occlusion). We define two shots to be near-duplicates if they share a large percentage of near-duplicate frames.

We focus primarily on scalability to very large image and video databases, where fast query processing is necessary. Both methods are designed so that only a small amount of data need be stored for each image. In the case of near-duplicate shot detection it is shown that a weak approximation to histogram matching, consuming substantially less storage, is sufficient for good results. We demonstrate our methods on the TRECVID 2006 data set which contains approximately 165 hours of video (about 17.8M frames with 146K key frames), and also on feature films and pop videos.

REFERENCES

• 1: M. Bertini, A. D. Bimbo, and W. Nunziati. Video clip matching using mpeg-7 descriptors and edit distance. In CIVR, pages 133--142, 2006.
• 2: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 3: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 4: Jan-Mark Geusebroek , Rein van den Boomgaard , Arnold W.M. Smeulders , Hugo Geerts, Color Invariance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.12, p.1338-1350, December 2001 [doi>10.1109/34.977559]
• 5: Monika Henzinger, Finding near-duplicate web pages: a large-scale evaluation of algorithms, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148222]
• 6: Timothy C. Hoad , Justin Zobel, Fast video matching with signature alignment, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California [doi>10.1145/973264.973304]
• 7: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 8: A. Joly, O. Buisson, and C. Frélicot. Content-based copy detection using distortion-based probabilistic similarity search. IEEE Transactions on Multimedia, to appear, 2007.
• 9: A. Joly, C. Frelicot, and O. Buisson. Robust content-based video copy identification in a large reference database. In Proc. CIVR, 2003.
• 10: 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]
• 11: 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]
• 12: K. Mikolajczyk , C. Schmid, An Affine Invariant Interest Point Detector, Proceedings of the 7th European Conference on Computer Vision-Part I, p.128-142, May 28-31, 2002
• 13: K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. In Proc. CVPR, 2003.
• 14: K. Mikolajczyk , T. Tuytelaars , C. Schmid , A. Zisserman , J. Matas , F. Schaffalitzky , T. Kadir , L. Van Gool, A Comparison of Affine Region Detectors, International Journal of Computer Vision, v.65 n.1-2, p.43-72, November 2005 [doi>10.1007/s11263-005-3848-x]
• 15: David Nister , Henrik Stewenius, Scalable Recognition with a Vocabulary Tree, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2161-2168, June 17-22, 2006 [doi>10.1109/CVPR.2006.264]
• 16: T. Quack, V. Ferrari, and L. Van Gool. Video mining with frequent itemset configurations. In Proc. CIVR, 2006.
• 17: Frederik Schaffalitzky , Andrew Zisserman, Multi-view Matching for Unordered Image Sets, or "How Do I Organize My Holiday Snaps?", Proceedings of the 7th European Conference on Computer Vision-Part I, p.414-431, May 28-31, 2002
• 18: F. Schaffalitzky , A. Zisserman, Automated location matching in movies, Computer Vision and Image Understanding, v.92 n.2-3, p.236-264, November/December 2003 [doi>10.1016/j.cviu.2003.06.008]
• 19: 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
• 20: TRECVID. http://trecvid.nist.gov/.
• 21: Wikipedia. Come into my world. http://en.wikipedia.org/wiki/Come_Into_My_World.
• 22: YouTube. http://www.youtube.com/.
• 23: 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]
• 24: Jian Zhou , Xiao-Ping Zhang, Automatic identification of digital video based on shot-level sequence matching, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101265]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
            Subjects: Hierarchical; Statistical

General Terms:
Algorithms, Theory

Keywords:
LSH, large image databases, min hash, near duplicate detection