Robust short clip representation and fast search through large video collections

Abstract

In this thesis we present a video copy detection method to effectively and efficiently search and locate clip re-occurrences (copies) inside large video collections. Three aspects of video copy detection including (1) feature robustness to coding variations, (2) search efficiency in large datasets and (3) query flexibility are investigated. In order to effectively and robustly characterize the video segments of variable lengths, we design novel global visual signatures combining the spatial-temporal and the color range information together. Different from previous key frame-based shot representations, the ambiguity of key frame selection and the difficulty of detecting gradual shot transitions could be avoided. Experiments have shown that the proposed visual signatures are capable of characterizing short video segments with dynamic content changing, like TV commercials of tens of seconds. And the signatures are also insensitive to color shifting and other variations caused from video compression, such as frame size, frame rate, or bit rate changes. In addition to visual signatures, audio signatures are also used for verification and accurate localization. As our audio and visual signatures can be extracted directly from the MPEG compressed domain, lower computational cost is required. To improve the search efficiency, we propose and compare two fast search schemes: hierarchical sequential similarity search and spatial-index driven similarity search. Considering the video sampling rate (25 or 30 frame per second) is much slower than that of audio (8 to 48 kHZ), the first search scheme applies the coarse search with sub-sampled video frames first, and then potential matches will be verified and accurately located by fine audio signatures. The search efficiency is largely improved by using such hierarchical sequential search. For example, with the signatures extracted in advance, we can search for a short video clip among the 10.5 hours MPEG-1 video database in merely 2 seconds in the case of unknown query length, and in 0.011 seconds when fixing the query length to 10 seconds. On the other hand, different from sequential similarity search, the second search scheme speed up the query process by pruning spatially in the feature space. Fast query speed can thus be achieved in this scheme as well. And another advantage is it can provide more flexible access techniques to the video database by offering different query strategies, such as K-NN (K-Nearest Neighbors), range or point query.