一种基于图的近重复视频子序列匹配算法

Graph-based near-duplicate video subsequence matching algorithm

为了解决近重复视频检测中的效果和效率问题,提出了一种基于图的近重复视频子序列匹配算法。将基于关键帧特征的相似性查询结果构建成匹配结果图,进而将近重复视频检测转换成一个在匹配结果图中查找最长路径的问题。该算法有三个主要优势:a)它能在众多杂乱的匹配结果中找到最佳的匹配序列,有效剔除了某些假"高相似度"匹配带来的噪声,因而能在一定程度上弥补底层特征描述力的不足;b)由于它充分考虑和利用了视频序列的时序特性,具有很高的近重复视频定位准确度;c)它能自动检测出匹配结果图中存在的多条离散路径,从而能一次性检测出两段视频中可能存在多段近重复视频的情形。提出的算法不仅提高了检测的准确度,而且提高了检测效率,取得了良好的实践效果。

In order to improve the effectiveness and efficiency of near-duplicate video detection, this paper proposed the graph-based video subsequence matching algorithm. The algorithm constructed a matching results graph from the similarity search results based on the key frame features, and then converted the problem of near-duplicate video detection into the problem of finding the longest path in the matching results graph. The method has three main advantages： a）Graph-based method could find the best matching sequence in many messy match results, which effectively excluded false ＂high similarity＂ noise and compensated the limited description of image low level visual features, b） The graph-based method took fully into account the spatiotemporal characteristic of video sequence, and had high location accuracy, c） The graph-based sequence matching method could automatically detect the discrete paths in the matching result graph. Thus, it could detect more than one nearduplicate video. The proposed algorithm not only improves the detection accuracy, but improves the efficiency of detection, achieves good practical effect.