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. We propose a novel approach for the discovery and tracking of NDK pairs and threads in broadcast domain. The detection of NDKs in 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 as 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 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. The measure is shown to be effective in discovering the NDK identity of a frame. In 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 TRECVID-2003 broadcast videos. The experimental results indicate that our approach outperforms other techniques in terms of recall and precision with large margin. In addition, by considering the transitivity and the underlying distribution of NDK pairs along time span, the speed-up of 3 to 5 times is achieved when keeping the performance close enough to the optimal one obtained by exhaustive evaluation.

Figure 1: Automatic discovery of NDK groups from a bunch of keyframes spanned across time.



Figure 2: Framework Overview.


Figure 3: Histograms of matching patterns for three NDK pairs: (a) matching lines between keypoints, (b) vertical histogram, (c) horizontal histogram. (White and red lines indicate the correct and false keypoint matches respectively).

Dataset and Ground-truth:

Binary Executable (new):

  • If you are interested in this near-duplicate image/keyframe detection toolkit. Please send email to: wzhao2@cs.cityu.edu.hk for binary executable.

Publications:

  • Chong-Wah Ngo, Wan-Lei Zhao, Yu-Gang Jiang
    Fast Tracking of Near-Duplicate Keyframes in Broadcast Domain with Transitivity Propagation
    ACM International Conference on Multimedia (ACM-MM), 2006.
    Full Text: [PDF]
  • Wan-Lei Zhao, Chong-Wah Ngo, Hung-Khoon Tan, Xiao Wu
    Near-Duplicate Keyframe Identification with Interest Point Matching and Pattern Learning
    IEEE Transaction on Multimedia, 2007, to appear.
    Full Text: [PDF]