Detection of video sequences using compact signatures

ABSTRACT

Digital representations are widely used for audiovisual content, enabling the creation of large online repositories of video, allowing access such as video on demand. However, the ease of copying and distribution of digital video makes piracy a growing concern for content owners. We investigate methods for identifying coderivative video content---that is, video clips that are derived from the same original source. By using dynamic programming to identify regions of similarity in video signatures, it is possible to efficiently and accurately identify coderivatives, even when these regions constitute only a small section of the clip being searched. We propose four new methods for producing compact video signatures, based on the way in which the video changes over time. The intuition is that such properties are likely to be preserved even when the video is badly degraded. We demonstrate that these signatures are insensitive to dramatic changes in video bitrate and resolution, two parameters that are often altered when reencoding. In the presence of mild degradations, our methods can accurately identify copies of clips that are as short as 5 s within a dataset 140 min long. These methods are much faster than previously proposed techniques; using a more compact signature, this query can be completed in a few milliseconds.

REFERENCES

• 1: Donald A. Adjeroh , I. King , Moon-Chuen Lee, Video Sequence Similarity Matching, Proceedings of the IAPR International Workshop on Multimedia Information Analysis and Retrieval, p.80-95, August 13-14, 1998
• 2: Adjeroh, D. A., Lee, M. C., and King, I. 1998. A distance measure for video sequence similarity matching. In Proceedings of International Workshop on Multimedia Database Management Systems (Dayton, OH). 72--79.
• 3: Ahanger, G., Benson, D., and Little, T. D. C. 1995. Video query formulation. In Proceedings of the Conference on Storage and Retrieval for Image and Video Databases (SPIE). 280--291.
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 6: Boreczky, J. S. and Rowe, L. A. 1996. Comparison of video shot boundary detection techniques. In Proceedings of the SPIE Conference on Storage and Retrieval for Image and Video Databases. 170--179.
• 7: 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]
• 8: Chang, S., Chen, W., Meng, H., Sundaram, H., and Zhong, D. 1998. A fully automated content based video search engine supporting spatio-temporal queries. IEEE Trans. Circ. Syst. Video Tech. 8, 5, 602--615.
• 9: Cheung, S. and Zakhor, A. 2000. Estimation of web video multiplicity. In Proceedings of the SPIE Conference on Internet Imaging (San Jose, CA).
• 10: DeMenthon, D. 2003. Video retrieval of near-duplicates using k-nearest neighbor retrieval of spatio-temporal descriptors. In Proceedings of the Third International Workshop on Content-Based Multimedia Indexing (CBMI 2003, Rennes, France).
• 11: 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]
• 12: Hideyo Waki, A Content-Based Video Query Agent Using Feature-Based Image Search Engine, Proceedings of the 3rd International Conference on Computational Intelligence and Multimedia Applications, p.181, September 23-26, 1999
• 13: Amarnath Gupta , Ramesh Jain, Visual information retrieval, Communications of the ACM, v.40 n.5, p.70-79, May 1997 [doi>10.1145/253769.253798]
• 14: Hampapur, A. and Bolle, R. 2001. Comparison of distance measures for video copy detection. In Proceedings of the International Conference on Multimedia and Expo.
• 15: Hampapur, A. and Bolle, R. M. 2002. VideoGREP: Video copy detection using inverted file indices. Tech. rep. IBM Exploratory Computer Vision Group, Yorktown Heights, NY.
• 16: Hampapur, A., Bolle, R. M., and Hyun, K.-H. 2001. Comparison of sequence matching techniques for video copy detection. In Proceedings of SPIE: Storage and Retrieval for Media Databases.
• 17: 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]
• 18: Hartung, F., Su, J. K., and Girod, B. 1999. Spread spectrum watermarking: Malicious attacks and counterattacks. In Proceedings of the SPIE, Security and Watermarking of Multimedia Contents, Electronic Imaging (San Jose, CA). 147--158.
• 19: Alexander G. Hauptmann , Michael G. Christel , Norman D. Papernick, Video retrieval with multiple image search strategies, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA [doi>10.1145/544220.544323]
• 20: Alexander G. Hauptmann , Rong Jin , Tobun Dorbin Ng, Multi-modal information retrieval from broadcast video using OCR and speech recognition, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA [doi>10.1145/544220.544252]
• 21: Alexander G. Hauptmann , Norman D. Papernick, Video-cuebik: adapting image search to video shots, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA [doi>10.1145/544220.544250]
• 22: 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]
• 23: 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]
• 24: 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
• 25: Hoi, C.-H. 2002. Similarity measurement and detection of video sequences. Tech. rep. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong.
• 26: Hoi, C.-H., Wang, W., and Lyu, M. R. 2003. A novel scheme for video similarity detection. In Proceedings of the Conference on Image and Video Retrieval. 373--382.
• 27: Ichiro Ide , Reiko Hamada , Shuichi Sakai , Hideohiko Tanaka, An attribute based news video indexing, Proceedings of the 2001 ACM workshops on Multimedia: multimedia information retrieval, October 05-05, 2001, Ottawa, Ontario, Canada [doi>10.1145/500933.500955]
• 28: Alejandro Jaimes , Shih-Fu Chang , Alexander C. Loui, Duplicate detection in consumer photography and news video, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641098]
• 29: Langelaar, G. C., Lagendijk, R. L., and Biemond, J. 1998. Removing spatial spread spectrum watermarks by nonlinear filtering. In Proceedings of the European Signal Processing Conference. vol. 4. 2281--2284.
• 30: Lee, S.-L., Chun, S.-J., and Lee, J.-H. 2003. Effective similarity search methods for large video data streams. In Proceedings of the International Conference on Computational Science. 1030--1039.
• 31: Li, D. and Lu, H. 2000. Avoiding false alarms due to illumination variation in shot detection. In Proceedings of the IEEE Workshop on Signal Processing Systems.
• 32: Lienhart, R. 2001. Reliable transition detection in videos: A survey and practitioner's guide. Int. J. Image Graph. 1, 3, 469--486.
• 33: Lienhart, R., Effelsberg, W., and Jain, R. 1998. VisualGREP: A systematic method to compare and retrieve video sequences. In Proceedings of the Conference on Storage and Retrieval for Image and Video Databases (SPIE). 271--283.
• 34: C. Kuhmunch, On the detection and recognition of television commercials, Proceedings of the 1997 International Conference on Multimedia Computing and Systems (ICMCS '97), p.509, June 03-06, 1997 [doi>10.1109/MMCS.1997.609763]
• 35: Liu, T., Zhang, X., Wang, D., Feng, J., and Lo, K.-T. 2000. Inertia-based cut detection technique: A step to the integration of video coding and content-based retrieval. In Proceedings of the International Conference on Signal Processing (Beijing, China). Vol. 2. 1018--1025.
• 36: 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]
• 37: Mohan, R. 1998. Video sequence matching. In Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP, Seattle, WA).
• 38: Akio Nagasaka , Yuzuru Tanaka, Automatic Video Indexing and Full-Video Search for Object Appearances, Proceedings of the IFIP TC2/WG 2.6 Second Working Conference on Visual Database Systems II, p.113-127, September 30-October 03, 1991
• 39: Naphade, M. R., Mehrotra, R., Ferman, A. M., Warnick, J., Huang, T. S., and Tekalp, A. M. 1998. A high performance shot boundary detection algorithm using multiple cues. In Proceedings of the IEEE International Conference on Image Processing (Chicago, IL).
• 40: Milind R. Naphade , Roy Wang , Thomas S. Huang, Supporting audiovisual query using dynamic programming, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500202]
• 41: Naphade, M. R., Yeung, M. M., and Yeo, B.-L. 2000. A novel scheme for fast and efficient video sequence matching using compact signatures. In Proceedings of SPIE, Storage and Retrieval for Media Databases (San Jose, CA). Vol. 3972. 564--572.
• 42: Ng, C. W., King, I., and Lyu, M. R. 2001. Video comparison using tree matching algorithms. In Proceedings of the International Conference on Imaging Science, Systems and Technology (Las Vegas, NV). Vol. 1. 184--190.
• 43: Chong-Wah Ngo , Ting-Chuen Pong , Hong-Jiang Zhang, On clustering and retrieval of video shots, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500151]
• 44: Park, S., Cho, J.-S., and Hyun, K.-H. 2002. Indexing technique for similarity matching in large video databases. In Proceedings of the SPIE Conference on Storage and Retrieval for Media Databases (San Jose, CA). 214--222.
• 45: Sanghyun Park , Ki-Ho Hyun, Trie for similarity matching in large video databases, Information Systems, v.29 n.8, p.641-652, December 2004 [doi>10.1016/S0306-4379(03)00046-2]
• 46: Patel, N. V. and Sethi, I. K. 1997. Video shot detection and characterization for video databases. Patt. Recog. 30, 4 (Apr.), 583--592.
• 47: Fabien A. P. Petitcolas , Ross J. Anderson , Markus G. Kuhn, Attacks on Copyright Marking Systems, Proceedings of the Second International Workshop on Information Hiding, p.218-238, April 14-17, 1998
• 48: Kok Meng Pua , John M. Gauch , Susan E. Gauch , Jedrzej Z. Miadowicz, Real time repeated video sequence identification, Computer Vision and Image Understanding, v.93 n.3, p.310-327, March 2004 [doi>10.1016/j.cviu.2003.10.005]
• 49: Shan, M.-K. and Lee, S.-Y. 1998. Content-based video retrieval based on similarity of frame sequence. In Proceedings of the International Workshop on Multimedia Database Management Systems (Dayton, OH). 72--79.
• 50: Swanberg, D., Shu, C.-F., and Jain, R. 1993. Knowledge guided parsing in video databases. In Proceedings of the Conference on Electronic Imaging: Science and Technology (San Jose, CA).
• 51: Tan, Y. P., Kulkarni, S. R., and Ramadge, P. J. 1999. A framework for measuring video similarity and its application to video query by example. In Proceedings of the IEEE International Conference on Image Processing (Kobe, Japan).
• 52: Hirotada Ueda , Takafumi Miyatake , Satoshi Yoshizawa, IMPACT: an interactive natural-motion-picture dedicated multimedia authoring system, Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, p.343-350, April 27-May 02, 1991, New Orleans, Louisiana, United States [doi>10.1145/108844.108939]
• 53: Yi Wu , Yueting Zhuang , Yunhe Pan, Content-based video similarity model, Proceedings of the eighth ACM international conference on Multimedia, p.465-467, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.376380]
• 54: Jun Yang , Qing Li , Yueting Zhuang, OCTOPUS: aggressive search of multi-modality data using multifaceted knowledge base, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511454]
• 55: Yukinobu Yasugi , Noboru Babaguchi , Tadahiro Kitahashi, Detection of identical events from broadcasted sports video by comparing camera works, Proceedings of the 2001 ACM workshops on Multimedia: multimedia information retrieval, October 05-05, 2001, Ottawa, Ontario, Canada [doi>10.1145/500933.500954]
• 56: Boon-Lock Yeo , Minerva M. Yeung, Retrieving and visualizing video, Communications of the ACM, v.40 n.12, p.43-52, Dec. 1997 [doi>10.1145/265563.265571]
• 57: 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
• 58: Hybrid Video System Supporting Content-Based Retrieval, Proceedings of the 3rd International Conference on Computational Intelligence and Multimedia Applications, p.258, September 23-26, 1999
• 59: Ramin Zabih , Justin Miller , Kevin Mai, A feature-based algorithm for detecting and classifying scene breaks, Proceedings of the third ACM international conference on Multimedia, p.189-200, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215266]
• 60: Ramin Zabih , Justin Miller , Kevin Mai, A feature-based algorithm for detecting and classifying production effects, Multimedia Systems, v.7 n.2, p.119-128, March 1999 [doi>10.1007/s005300050115]
• 61: HongJiang Zhang , Atreyi Kankanhalli , Stephen W. Smoliar, Automatic partitioning of full-motion video, Multimedia Systems, v.1 n.1, p.10-28, June 1993 [doi>10.1007/BF01210504]
• 62: Zhao, L., Qi, W., Li, S. Z., Yang, S. Q., and Zhang, H. J. 2001. Content-based retrieval of video shot using the improved nearest feature line method. In Proceedings of the IEEE International Conference on Acoustics Speech and Signal Processing (Salt Lake City, UT).

INDEX TERMS

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
Video similarity detection, dynamic programming, local alignment