Video copy detection by fast sequence matching

Mei-Chen Yeh, Kwang Ting Cheng

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

43 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationCIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval
Pages344-350
Number of pages7
DOIs
Publication statusPublished - 2009 Dec 1
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

Other

OtherACM International Conference on Image and Video Retrieval, CIVR 2009
CountryGreece
CitySantorini Island
Period09/7/809/7/10

Fingerprint

Costs
Experiments

Keywords

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

ASJC Scopus subject areas

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

Cite this

Yeh, M-C., & Cheng, K. T. (2009). Video copy detection by fast sequence matching. In CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval (pp. 344-350). (CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval). https://doi.org/10.1145/1646396.1646449

Video copy detection by fast sequence matching. / Yeh, Mei-Chen; Cheng, Kwang Ting.

CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval. 2009. p. 344-350 (CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval).

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

Yeh, M-C & Cheng, KT 2009, Video copy detection by fast sequence matching. in CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval. CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval, pp. 344-350, ACM International Conference on Image and Video Retrieval, CIVR 2009, Santorini Island, Greece, 09/7/8. https://doi.org/10.1145/1646396.1646449
Yeh M-C, Cheng KT. Video copy detection by fast sequence matching. In CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval. 2009. p. 344-350. (CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval). https://doi.org/10.1145/1646396.1646449
Yeh, Mei-Chen ; Cheng, Kwang Ting. / Video copy detection by fast sequence matching. CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval. 2009. pp. 344-350 (CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval).
@inproceedings{6fad6c27ff734eabacdbcf90d71e157a,
title = "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.",
keywords = "Local alignment, Similarity measure, Video copy detection, Vocabulary tree",
author = "Mei-Chen Yeh and Cheng, {Kwang Ting}",
year = "2009",
month = "12",
day = "1",
doi = "10.1145/1646396.1646449",
language = "English",
isbn = "9781605584805",
series = "CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval",
pages = "344--350",
booktitle = "CIVR 2009 - Proceedings of the ACM International Conference on Image and Video Retrieval",

}

TY - GEN

T1 - Video copy detection by fast sequence matching

AU - Yeh, Mei-Chen

AU - Cheng, Kwang Ting

PY - 2009/12/1

Y1 - 2009/12/1

N2 - 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.

AB - 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.

KW - Local alignment

KW - Similarity measure

KW - Video copy detection

KW - Vocabulary tree

UR - http://www.scopus.com/inward/record.url?scp=74049160269&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=74049160269&partnerID=8YFLogxK

U2 - 10.1145/1646396.1646449

DO - 10.1145/1646396.1646449

M3 - Conference contribution

SN - 9781605584805

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

SP - 344

EP - 350

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

ER -