Accelerating near-duplicate video matching by combining visual similarity and alignment distortion

ABSTRACT

In this paper, we investigate a novel approach to accelerate the matching of two video clips by exploiting the temporal coherence property inherent in the keyframe sequence of a video. Motivated by the fact that keyframe correspondences between near-duplicate videos typically follow certain spatial arrangements, such property could be employed to guide the alignment of two keyframe sequences. We set the alignment problem as an integer quadratic programming problem, where the cost function takes into account both the visual similarity of the corresponding keyframes as well as the alignment distortion among the set of correspondences. The set of keyframe-pairs found by our algorithm provides our proposal on the list of candidate keyframe-pairs for near-duplicate detection using local interest points. This eliminates the need for exhaustive keyframe-pair comparisons, which significantly accelerates the matching speed. Experiments on a dataset of 12,790 web videos demonstrate that the proposed method maintains a similar near-duplicate video retrieval performance as the hierarchical method proposed in [12] but with a significantly reduced number of keyframe-pair comparisons.

REFERENCES

• 1: Donald A. Adjeroh , M. C. Lee , Irwin King, A distance measure for video sequences, Computer Vision and Image Understanding, v.75 n.1-2, p.25-45, July/Aug. 1999 [doi>10.1006/cviu.1999.0764]
• 2: Alexander C. Berg , Tamara L. Berg , Jitendra Malik, Shape Matching and Object Recognition Using Low Distortion Correspondences, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.26-33, June 20-26, 2005 [doi>10.1109/CVPR.2005.320]
• 3: A. Hampapur and R. Bolle. Comparison of sequence matching techniques for video copy detection. In Conf. on Storage and Retrieval for Media Databases, 2002.
• 4: Yu-Gang Jiang , Chong-Wah Ngo , Jun Yang, Towards optimal bag-of-features for object categorization and semantic video retrieval, Proceedings of the 6th ACM international conference on Image and video retrieval, p.494-501, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282352]
• 5: A. Joly, O. Buisson, and C. Frelicot. Content-based copy retrieval using distortion-based probabilistic similarity search. In IEEE Trans. on Multimedia, volume 9, pages 835--844, 2007.
• 6: 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]
• 7: Julien Law-To , Olivier Buisson , Valerie Gouet-Brunet , Nozha Boujemaa, Robust voting algorithm based on labels of behavior for video copy detection, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180826]
• 8: Rainer Lienhart , Wolfgang Effelsberg , Ramesh Jain, VisualGREP: A Systematic Method to Compare and RetrieveVideo Sequences, Multimedia Tools and Applications, v.10 n.1, p.47-72, January 2000 [doi>10.1023/A:1009663921899]
• 9: James A. McHugh, Algorithmic graph theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 10: 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]
• 11: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Novelty detection for cross-lingual news stories with visual duplicates and speech transcripts, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291274]
• 12: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Practical elimination of near-duplicates from web video search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291280]
• 13: 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]
• 14: W.-L. Zhao, C.-W. Ngo, H.-K. Tan, and X. Wu. Near-duplicate keyframe identification with interest point matching and pattern learning. In IEEE Trans. on Multimedia, volume 9, Aug 2007.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
keyframe alignment, near-duplicate web video retrieval