Video copy detection by fast sequence matching

ABSTRACT

Sequence matching techniques are effective for comparing two videos. However, existing approaches suffer from demanding computational costs and thus are not scalable for large-scale applications. In this paper we view video copy detection as a local alignment problem between two frame sequences and propose a two-level filtration approach which achieves significant acceleration to the matching process. First, we propose to use an adaptive vocabulary tree to index all frame descriptors extracted from the video database. In this step, each video is treated as a "bag of frames." Such an indexing structure not only provides a rich vocabulary for representing videos, but also enables efficient computation of a pyramid matching kernel between videos. This vocabulary tree filters those videos that are dissimilar to the query based on their histogram pyramid representations. Second, we propose a fast edit-distance-based sequence matching method that avoids unnecessary comparisons between dissimilar frame pairs. This step reduces the quadratic runtime to a linear time with respect to the lengths of the sequences under comparison. Experiments on the MUSCLE VCD benchmark demonstrate that our approach is effective and efficient. It is 18X faster than the original sequence matching algorithms. This technique can be applied to several other visual retrieval tasks including shape retrieval. We demonstrate that the proposed method can also achieve a significant speedup for the shape retrieval task on the MPEG-7 shape dataset.

References

1. D. A. Adjeroh, M. -C. Lee, and I. King. A distance measure for video sequence similarity matching. In Proceedings of the International Workshop on Multi-Media Database Management Systems, pages 72--79, 1998.
2. S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI'98), 24(4): 509--522, 2002.
3. M. Bertini, A. D. Bimbo, and W. Nunziati. Video clip matching using MPEG-7 descriptors and edit distance. In Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR'07), pages 133--142, 2006.
4. S. -C Cheung, and A. Zakhor. Fast similarity search and clustering of video sequences on the world-wide-web. IEEE Transactions on Multimedia, 7(3): 524--537, 2004.
5. O. Chum, J. Philbin, M. Isard, and A. Zisserman. Scalable near identical image and shot detection. In Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR'07), pages 549--556, 2007.
6. A. Joly, O. Buisson, and C. Frelicot. Content-based copy retrieval using distortion-based probabilistic similarity search. IEEE Transactions on Multimedia, 9(2): 293--306, 2007.
7. Y. Ke, R. Sukthankar, and L. Houston. Efficient near-duplicate detection and sub-image retrieval. In Proceedings of the ACM International Conference on Multimedia (MM'04), pages 1150--1157, 2004.
8. Y. Kim, and T. -S. Chua. Retrieval of news video using video sequence matching. In Proceedings of the International Multimedia Modelling Conference (MMM'05), pages 68--75, 2005.
9. J. Law-To, A. Joly, and N. Boujemaa. Muscle-VCD-2007: a live benchmark for video copy detection, 2007. http://www-rocq.inria.fr/imedia/civr-bench/.
10. J. Law-To, O. Buisson, V. Gouet-Brunet, and N. Boujemaa. Robust voting algorithm based on labels of behavior for video copy detection. In Proceedings of the ACM International Conference on Multimedia (MM'06), pages 835--844, 2006.
11. J. Law-To, L. Chen, A. Joly, I. Laptev, O. Buisson, V. Gouet-Brunet, N. Boujemaa, and F. Stentiford. Video copy detection: a comparative study. In Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR'07), pages 371--378, 2007.
12. J. Li, W. Wu, T. Wang, and Y. Zhang. One step beyond histograms: Image representation using Markov stationary features. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR'08), pages 1--8, 2008.
13. D. Nister, and H. Stewenius. Scalable recognition with a vocabulary tree. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR'06), pages 2161--2168, 2006.
14. W. R. Pearson, and D. J. Lipman. Improved tools for biological sequence comparison. In Proceedings of the National Academy of Sciences of the United States of America, 85(8): 2444--2448, 1988.
15. S. Poullot, M. Crucianu, and O. Buisson. Scalable mining of large video databases using copy detection. In Proceedings of the ACM International Conference on Multimedia (MM'08), pages 61--70, 2008.
16. S. Poullot, O. Buisson, and M. Crucianu. Z-grid-based probabilistic retrieval for scaling up content-based copy detection. In Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR'07), pages 348--355, 2007.
17. J. Sivic, and A. Zisserman. Video Google: A text retrieval approach to object matching in videos. In Proceedings of the IEEE International Conference on Computer Vision (ICCV'03), pages 1470--1477, 2003.
18. T. F. Smith, and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1): 195--197, 1981.
19. P. Viola, and M. Jones. Robust real-time face detection. International Journal of Computer Vision, 57(2), pages 137--154, 2004.
20. X. Wu, A. G. Hauptmann, and C. -W. Ngo. Practical elimination of near-duplicates from web video search. In Proceedings of the ACM International Conference on Multimedia (MM'07), pages 218--227, 2007.
21. M. Yeh, and K. -T. Cheng. A string matching for visual retrieval and classification. In Proceedings of the ACM International Conference on Multimedia Information Retrieval (MIR'08), pages 52--58, 2008.
22. T. Yeh, J. Lee, and T. Darrell. Adaptive vocabulary forests for dynamic indexing and category learning. In Proceedings of the IEEE International Conference on Computer Vision (ICCV'07), pages 1--8, 2007.
23. D. -Q. Zhang, and S. -F. Chang. Detecting image near-duplicate by stochastic attributed relational graph matching with learning. In Proceedings of the ACM International Conference on Multimedia (MM'04), pages 877--884, 2004.
24. J. Zhou, X. -P. Zhang. Automatic identification of digital video based on shot-level sequence matching. In Proceedings of the ACM International Conference on Multimedia (MM'05), pages 515--518, 2005.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision tasks

• Information systems

  • Information retrieval

    • Information retrieval query processing

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction