Video copy detection by fast sequence matching

Mei Chen Yeh*, Kwang Ting Cheng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationCIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval
Number of pages7
Publication statusPublished - 2009
Externally publishedYes
EventACM International Conference on Image and Video Retrieval, CIVR 2009 - Santorini Island, Greece
Duration: 2009 Jul 82009 Jul 10

Publication series

NameCIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval


OtherACM International Conference on Image and Video Retrieval, CIVR 2009
CitySantorini Island


  • Local alignment
  • Similarity measure
  • Video copy detection
  • Vocabulary tree

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Computer Vision and Pattern Recognition


Dive into the research topics of 'Video copy detection by fast sequence matching'. Together they form a unique fingerprint.

Cite this