Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2006

Abstract

The identification of near-duplicate keyframe (NDK) pairs is a useful task for a variety of applications such as news story threading and content-based video search. In this paper, we propose a novel approach for the discovery and tracking of NDK pairs and threads in the broadcast domain. The detection of NDKs in a large data set is a challenging task due to the fact that when the data set increases linearly, the computational cost increases in a quadratic speed, and so does the number of false alarms. This paper explores the symmetric and transitive nature of near-duplicate for the effective detection and fast tracking of NDK pairs based upon the matching of local keypoints in frames. In the detection phase, we propose a robust measure, namely pattern entropy (PE), to measure the coherency of symmetric keypoint matching across the space of two keyframes. This measure is shown to be effective in discovering the NDK identity of a frame. In the tracking phase, the NDK pairs and threads are rapidly propagated and linked with transitivity without the need of detection. This step ends up with a significant boost in speed efficiency. We evaluate our proposed approach against a month of the TRECVID2004 broadcast videos. The experimental results indicate that our approach outperforms other techniques in terms of recall and precision with a large margin. In addition, by considering the transitivity and the underlying distribution of NDK pairs along time span, a speed-up of 3 to 5 times is achieved when keeping the performance close enough to the optimal one obtained by exhaustive evaluation.

Keywords

Keyframe tracking, Keypoint matching, Near-duplicate detection, Pattern entropy, Transitivity propagation

Discipline

Databases and Information Systems | Graphics and Human Computer Interfaces | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 14th ACM international conference on Multimedia, MM 2006, Santa Barbara, California, October 23-27

First Page

845

Last Page

854

ISBN

9781595934475

Identifier

10.1145/1180639.1180827

Publisher

ACM

City or Country

Santa Barbara, California

Download

Share

COinS