Video linkage: group based copied video detection

ABSTRACT

Sites to share user-created video clips such as YouTube and Yahoo Video have become greatly popular in recent years. One of the challenges of such sites is, however, to prevent video clips that violate copyrights by illegally copying and editing scenes from other videos. Due to the sheer number of clips uploaded every day, automatic methods to detect (illegally) copied video clips in a large collection are desirable. Toward this problem, in this paper, we present a novel framework, termed as Video Linkage, that is based on the record linkage techniques. Our proposal is based on the observations that: (1) a video clip can be represented as a "group" of key frames, (2) two video clips are deemed to be similar if two groups of key frames are similar as a whole - i.e., the similarity of two video clips can be measured by means of graph-based similarity measures such as maximal cardinality bipartite matching, and (3) if a video clip v_a is copied to v_b, then v_a and v_b must be somehow similar, but not all similar video clips are illegally copied ones - i.e., similar videos can be used as a filter for fast detection of copied videos. The validity of our observations and Video Linkage technique is thoroughly evaluated using both real and synthetic data sets - i.e., on average, our proposals achieved 0.94 as precision and 0.93 as recall across 10 genres and 6 editing patterns.

REFERENCES

• 1: I. P. Fellegi and A. B. Sunter. "A Theory for Record Linkage". J. of the American Statistical Society, 64:1183--1210, 1969.
• 2: C. Gianluigi and S. Raimondo. "An Innovative Algorithm for Key frame Extraction in Video Summarization". J Real-Time Image Proc, 1:69--88, 2006.
• 3: Sudipto Guha , Nick Koudas , Amit Marathe , Divesh Srivastava, Merging the results of approximate match operations, Proceedings of the Thirtieth international conference on Very large data bases, p.636-647, August 31-September 03, 2004, Toronto, Canada
• 4: A. Hampapur, K.-H. Hyun, and R. Bolle. "Comparison of Sequence Matching Techniques for Video Copy Detection". In SPIE, Storage and Retrieval for Media Databases, pages 194--201, San Jose, CA, Jan 2002.
• 5: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 6: Alexis Joly , Olivier Buisson , Carl Frelicot, Statistical similarity search applied to content-based video copy detection, Proceedings of the 21st International Conference on Data Engineering Workshops, p.1285, April 05-08, 2005 [doi>10.1109/ICDE.2005.291]
• 7: R. P. Kelley. "Blocking Considerations for Record Linkage Under Conditions of Uncertainty". In Proc. of Social Statistics Section, pages 602--605, 1984.
• 8: C. Kim and B. Vasudev. "Spatiotemporal Sequence Matching for Efficient Video Copy Detection". IEEE TCSVT, 15(1):127--132, 2005.
• 9: Julien Law-To , Li Chen , Alexis Joly , Ivan Laptev , Olivier Buisson , Valerie Gouet-Brunet , Nozha Boujemaa , Fred Stentiford, Video copy detection: a comparative study, Proceedings of the 6th ACM international conference on Image and video retrieval, p.371-378, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282336]
• 10: You-Ru Lin , Hui-Yu Huang , Wen-Hsing Hsu, An embedded watermark technique in video for copyright protection, Proceedings of the 18th International Conference on Pattern Recognition, p.795-798, August 20-24, 2006 [doi>10.1109/ICPR.2006.244]
• 11: Federico Malucelli , Thomas Ottmann , Daniele Pretolani, Efficient labelling algorithms for the maximum noncrossing matching problem, Discrete Applied Mathematics, v.47 n.2, p.175-179, Nov. 30, 1993 [doi>10.1016/0166-218X(93)90090-B]
• 12: Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
• 13: Xavier Naturel , Patrick Gros, A fast shot matching strategy for detecting duplicate sequences in a television stream, Proceedings of the 2nd international workshop on Computer vision meets databases, June 17-17, 2005, Baltimore, MD [doi>10.1145/1160939.1160947]
• 14: B.-W. On, N. Koudas, D. Lee, and D. Srivastava. "Group Linkage". In IEEE ICDE, Istanbul, Turkey, Apr. 2007.
• 15: S. Roy and E.-C. Chang. "Watermarking with Retrieval Systems". Multimedia Systems, 9(5):433--440, 2004.
• 16: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 17: Heng Tao Shen , Xiaofang Zhou , Zi Huang , Jie Shao , Xiangmin Zhou, UQLIPS: a real-time near-duplicate video clip detection system, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 18: W. E. Winkler. "The State of Record Linkage and Current Research Problems". Technical report, US Bureau of the Census, Apr. 1999.
• 19: 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]
• 20: Justin Zobel , Timothy C. Hoad, Detection of video sequences using compact signatures, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.1-50, January 2006 [doi>10.1145/1125857.1125858]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance

Keywords:
copyright, linkage, video