An image-based near-duplicate video retrieval and localization using improved Edit distance

• DOI: 10.1007/s11042-016-4176-6
• Publication Date: 2016-12-02T01:29:46Z
• Authors: Hao Liu; Qingjie Zhao; Hao Wang; Peng Lv; Yanming Chen
• Keywords: Edit distance; Robustness; Similarity (geometry); Similarity measure; Distance matrix; Video retrieval

The rapid development of social network in recent years has spurred enormous growth of near-duplicate videos. The existence of huge volumes of near-duplicates shows a rising demand on effective near-duplicate video retrieval technique in copyright violation and search result reranking. In this paper, we propose an image-based algorithm using improved Edit distance for near-duplicate video retrieval and localization. By regarding video sequences as strings, Edit distance is used and extended to retrieve and localize near-duplicate videos. Firstly, bag-of-words (BOW) model is utilized to measure the frame similarities, which is robust to spatial transformations. Then, non-near-duplicate videos are filtered out by computing the proposed relative Edit distance similarity (REDS). Next, a detect-and-refine-strategy-based dynamic programming algorithm is proposed to generate the path matrix, which can be used to aggregate scores for video similarity measure and localize the similar parts. Experiments on CC_WEB_VIDEO and TREC CBCD 2011 datasets demonstrated the effectiveness and robustness of the proposed method in retrieval and localization tasks.