Research On Near-Duplicate Video Detection Algorithm

With broadband transmission network improved steadily and the rapid develop-ment and the wide range of applications of video software and hardware processing technology, especially with the rapid development of WEB2.0technology, the video can be very easily published and shared through various forms. It makes online video content explosively grow accompanied by a large number of near-duplicate videos. The advent of a large number of near-duplicate videos bring various tech-nical challenges to the video copyright-protected, content monitoring, video search results ranking and so on. In this context, the content-based near-duplicate video detection technology came into being.This thesis presents a classification and comparative study of methods for near-duplicate video detection. Although these methods have their own scenarios, the technical details are not the same, but their detection processes can be summarized into four key steps:1) extract video key frame;2) extract video key frame fea-ture;3) carry out the similarity query based on the video key frame features;4) perform video subsequence matching based on the similarity query results of video key frame features, and achieve the identification and location of the near-duplicate video. In these four steps, the key frame extraction method is relatively mature, and the current research focuses on the stable, high degree of distinction between the stable and high distinctive video feature extraction, the efficient feature similar-ity query method and the accurate video subsequence matching for content-based near-duplicate video detection. This thesis proposes our approaches base on the summarization of these three aspects of technology.In the feature research for near-duplicate video detection, this thesis does the work in two aspects:1) we propose to apply the singular value decomposition (SVD) method for feature matching and extract the new features from the set of SIFT fea-ture points. The extracted feature is termed as SVD-SIFT;2) we improve the de-scription of the standard SIFT descriptor and propose the gradient ordinal signature, referred to as the GOS. Compared to the standard SIFT descriptor, SVD-SIFT and GOS is basically preserved the good characteristics of the original SIFT descriptor with scale invariance. rotation invariance. GOS has also added the mirror reflec-tion invariance characteristic, has better adaptability. However, the calculations of SVD-SIFT and the GOS is easier, the dimension is also greatly reduced, and thus improve the detection speed.In the research of the video key frame feature similarity query for near-duplicate video detection, this thesis analyses some intrinsic properties of the ordinal feature and combine with the embedding theory of metric spaces to proposes an efficient similarity search method based on the fixed-point embedding, referred to as the FE. A main advantage of FE is that its parameters have good controllability, and its performance is stable and not sensitive to dataset changes. FE is based on a simple idea that, if two points are close together, then after an "embedding" operation these two points will remain close together. The contractive property of the embedding method can ensure the establishment of this assumption. By the fixed-point embedding, the similar data points in high dimensional space is projected onto the same bin, and then through the establishment of an inverted index structure to perform efficient similarity search.In the research of the video subsequence matching for near-duplicate video de-tection, this thesis presents the graph-based video subsequence matching algorithm. This method constructs a matching results graph from the similarity search results based on the key frame features, and then the problem of near-duplicate video detec-tion is converted into the problem of finding the longest path in the matching results graph. The method has three main advantages:1) Graph-based method can find the best matching sequence in many messy match results, which effectively excludes false "high similarity" noise and compensate the limited description of image low level visual features.2) The graph-based method takes fully into account the spa-tiotemporal characteristic of video sequence, and has high location accuracy.3) The graph-based sequence matching method can automatically detect the discrete paths in the matching result graph. Thus, it can detect more than one near-duplicate video.Finally, this thesis evaluates the proposed methods by the experiments. The experimental results show that the proposed methods get close to the performance of the best methods in the single technical indicators. But, for near-duplicate video detection, these methods obtain a better overall performance.