Fast video matching with signature alignment

ABSTRACT

Video data is stored and distributed in large quantities and a wide variety of formats. As the amount of material increases, so too does the need to manage and search it. In previous work, we addressed the problem of rapidly locating a given clip in a large stream of video by analysing the pattern of edits or cuts, a method that is fast and as effective as a standard search method based on image comparison, but is not very robust, particularly for short clips. In this paper we describe two new methods that address the limitations of the cut-based approach. We show that the new video representations are more robust than any previous method and vastly superior at identifying similar content when the cut-based signature is not sufficiently discriminatory.

REFERENCES

• 1: D. A. Adjeroh, M. C. Lee, and I. King. A distance measure for video sequence similarity matching. In Proc. of Intl. Workshop on Multimedia Database Management Systems, pages 72--79, Dayton, OH, August 1998.
• 2: P. Aigrain, H. Zhang, and D. Petkovic. Content-based representation and retrieval of visual media: A state-of-the-art review. Multimedia Tools and Applications, 3(3):179--202, 1996.
• 3: R. M. Bolle, B. L. Yeo, and M. M. Yeung. Content-based digital video retrieval. In Proc. of Intl. Broadcasting Convention, pages 160--165, Amsterdam, September 1997.
• 4: Shih-Fu Chang , William Chen , Horace J. Meng , Hari Sundaram , Di Zhong, VideoQ: an automated content based video search system using visual cues, Proceedings of the fifth ACM international conference on Multimedia, p.313-324, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266382]
• 5: S. Cheung and A. Zakhor. Efficient video similarity measurement and search. In Proc of International Conference on Image Processing, pages 85--89, British Columbia, Canada, September 2000.
• 6: N. Day and J. M. Martinez. Introduction to MPEG-7, 2001.
• 7: Daniel DeMenthon , David Doermann, Video retrieval using spatio-temporal descriptors, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957124]
• 8: W. A. C. Fernando, C. N. Canagarajah, and D. R. Bull. A unified approach to scene change detection in uncompressed and compressed video.
• 9: Mohand-Saïd Hacid , Cyril Decleir , Jacques Kouloumdjian, A Database Approach for Modeling and Querying Video Data, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.729-750, September 2000 [doi>10.1109/69.877505]
• 10: A. Hampapur , T. Weymouth , R. Jain, Digital video segmentation, Proceedings of the second ACM international conference on Multimedia, p.357-364, October 15-20, 1994, San Francisco, California, United States [doi>10.1145/192593.192699]
• 11: Timothy C. Hoad , Justin Zobel, Methods for identifying versioned and plagiarized documents, Journal of the American Society for Information Science and Technology, v.54 n.3, p.203-215, February 1, 2003 [doi>10.1002/asi.10170]
• 12: Timothy C. Hoad , Justin Zobel, Video similarity detection for digital rights management, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.237-245, February 01, 2003, Adelaide, Australia
• 13: Q. Huang and A. Puri. Multimedia search and retrieval: New concepts, system implementation and application. IEEE Transactions on Circuits and Systems for Video Technology, 10(5):679--692, August 2000.
• 14: Vikrant Kobla , David Doermann , Christos Faloutsos, VideoTrails: representing and visualizing structure in video sequences, Proceedings of the fifth ACM international conference on Multimedia, p.335-346, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266384]
• 15: R. Lienhart, W. Effelsberg, and R. Jain. VisualGREP: A systematic method to compare and retrieve video sequences. In Storage and Retrieval for Image and Video Databases (SPIE), pages 271--283, 1998.
• 16: Xiaoming Liu , Yueting Zhuang , Yunhe Pan, A new approach to retrieve video by example video clip, Proceedings of the seventh ACM international conference on Multimedia (Part 2), p.41-44, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319878.319889]
• 17: U. Manber. Finding similar files in a large file system. In 1994 Winter USENIX Technical Conference, pages 1--10, San Francisco, CA, Jan. 1994.
• 18: Johngho Nang , Seungwook Hong , Youngin Ihm, An efficient video segmentation scheme for MPEG video stream using macroblock information, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.23-26, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.320047]
• 19: N. V. Patel and I. K. Sethi. Video shot detection and characterization for video databases. Pattern Recognition, 30(4):583--592, April 1997.
• 20: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 21: M.-K. Shan and S.-Y. Lee. Content-based video retrieval based on similarity of frame sequence. In Proc. of Intl. Workshop on Multimedia Database Management Systems, pages 72--79, Dayton, OH, August 1998.
• 22: N. Shivakumar and H. Garcia-Molina. SCAM: a copy detection mechanism for digital documents. In Proceedings of the Second International Conference on Teory and Practice of Digital Libraries, Austin, Texas, June 1995.
• 23: Y. P. Tan, S. R. Kulkarni, and P. J. Ramadge. A framework for measuring video similarity and its application to video query by example. In Proc. of ICIP, Kobe, Japan, 1999.
• 24: M. M. Yeung , Bede Liu, Efficient matching and clustering of video shots, Proceedings of the 1995 International Conference on Image Processing (Vol. 1)-Volume 1, p.338, October 23-26, 1995

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases

General Terms:
Algorithms, Performance

Keywords:
copy detection, video representations, video retrieval, video similarity