Accelerating near-duplicate video matching by combining visual similarity and alignment distortion

In this paper, we investigate a novel approach to accelerate the matching of two video clips by exploiting the temporal coherence property inherent in the keyframe sequence of a video. Motivated by the fact that keyframe correspondences between near-duplicate videos typically follow certain spatial arrangements, such property could be employed to guide the alignment of two keyframe sequences. We set the alignment problem as an integer quadratic programming problem, where the cost function takes into account both the visual similarity of the corresponding keyframes as well as the alignment distortion among the set of correspondences. The set of keyframe-pairs found by our algorithm provides our proposal on the list of candidate keyframe-pairs for near-duplicate detection using local interest points. This eliminates the need for exhaustive keyframe-pair comparisons, which significantly accelerates the matching speed. Experiments on a dataset of 12,790 web videos demonstrate that the proposed method maintains a similar near-duplicate video retrieval performance as the hierarchical method proposed in [12] but with a significantly reduced number of keyframe-pair comparisons. Copyright 2008 ACM.