A practical spatial re-ranking method for instance search from videos

Spatial re-ranking has proved to be successful in image retrieval. Yet no work on spatial re-ranking has been systematically reported for instance search from videos so far: As videos are composed of multiple frames, and frame-by-frame spatial verification is too prohibitive, till now we lack an efficient spatial re-ranking method designed for the purpose of video instance search. The effectiveness is unclear as well. This paper proposes a practical spatial re-ranking method for video instance search. We make two contributions to speed up the algorithm: One is to select the most representative image/frame for spatial verification, based on the available Bag-of-Words representation; the other is to efficiently build tentative matching feature pairs, which serve as the input of the RANSAC algorithm, by regarding features quantized to the same visual word as matches, thus avoid the costly nearest-neighbor search. These two modifications lead one order of magnitude speedup without compromising the performance. Another contribution is a ROI-originated RANSAC method, which improves the re-ranking performance significantly. Experiments were carried out on the TrecVid Instance Search 2013 dataset, and the new state-of-the-art performance was achieved by the proposed method, at a much faster speed.