CN101464909A - Fast robust approximately same video detection and exclusion method - Google Patents

Abstract

The invention relates to a fast and robust near-identical video detection and exclusion method, which belongs to the technical field of information mining. The method includes extracting the key frame features of the video to be detected, and the video feature generation stage of the generated video global features. The global feature vector of the video to be detected and the global feature vector of the existing video complete the pattern matching stage of the detection of nearly the same video. The video feature generation stage includes dividing the key frame image into blocks and extracting the average gray level of each block as the key Frame features, and use the principal component analysis method to binarize and quantize the key frame features, and generate global features based on the quantized key frame features. The invention is used for detection and elimination of nearly identical videos in a large-scale network video database, and has higher speed and ideal results.

Description

A Fast and Robust Near-Identical Video Detection and Rejection Method

technical field

The invention belongs to the technical field of information mining, and relates to a method for detecting and eliminating nearly identical videos in a large-scale network video database.

Background technique

In recent years, with the development of Internet technology, especially the rapid growth of bandwidth accessible to ordinary users, more and more video-based multimedia applications have become Internet hotspots. They have excellent interactive characteristics in information retrieval and digital entertainment, which greatly enrich people's Internet experience. Nowadays, people can easily obtain a large amount of video information from the Internet. While the content of online video has become rich and colorful, there is also a large amount of redundant information, especially the repeated uploading of popular videos. Many online videos contain basic content. Consistent, but due to differences in encoding rate, encoding quality, color transformation, post-manual editing, and frame rate, content-based methods need to be used to compare and exclude these videos. These videos are called near-identical videos. The existence of near-identical videos has brought great waste to network storage. In the past, there are roughly three types of methods to solve this problem, which are based on global features, shot (shot)-level features, and image region-level feature detection based on feature points. method. All in all, global features, such as using video color histograms, have the advantages of simple features and less calculation, but they are only suitable for detecting videos with almost the same content. Shot-level features can detect more edited videos. Recently, feature point detection such as SIFT and other matching methods have appeared, which can measure similarity more accurately. However, these methods are not too computationally expensive to generate features, and the matching method is too complicated. Due to the large number of online videos, these large amounts of near-identical content have high performance requirements for video detection and exclusion algorithms. Therefore, it is imperative to design a fast and robust method to detect and exclude near-identical videos.

Contents of the invention

The purpose of the present invention is to design a fast and robust near-identical video detection and elimination method for overcoming the deficiencies of the prior art. The method first generates corresponding key-based The accurate and robust signature information of the frame, and then by matching the abstracted signature information, it is used for the detection and exclusion of nearly identical videos in a large-scale network video database, with higher speed and ideal results.

A fast and robust near-identical video detection and exclusion method proposed by the present invention includes extracting the key frame features of the video to be detected, the video feature generation stage of the generated video global features, and comparing the global feature vector of the video to be detected with the existing There is a global feature vector of video to complete the pattern matching stage of the detection of nearly the same video, the video feature generation stage includes key frame image segmentation, extracting the average gray level of each block as key frame feature, and using the principal component analysis method ( PCA) performs binary quantization on the key frame features, and generates global features based on the quantized key frame features.

The above method mainly includes the following steps:

(1) generate a key frame of the video to be detected;

(2) block the key frame to obtain the average gray feature vector of the key frame;

(3) Utilize the principal component analysis method to reduce the dimension of this gray-scale feature vector to the average gray-scale feature vector obtained;

(4) Using the average value obtained from the statistical results of a large number of pictures as a threshold to perform binarization and quantization on the average gray feature vector after dimensionality reduction;

(5) Generate the global feature vector of the video to be detected based on the key frame average grayscale feature vector after binarization and quantification;

(6) compare the global feature vector of the video to be detected and the global feature vector of the existing video, get rid of the larger existing video with this video feature difference to be detected in the database;

(7) For videos that cannot be excluded with global features in the database, use the similarity based on video key frame level feature vectors to build a bipartite graph;

(8) Calculate the maximum matching value of this bipartite graph with the maximum matching approximation algorithm, compare the maximum matching value with the threshold Th, and get rid of the larger existing video with this video difference to be detected in the database again;

(9) Modify the bipartite graph of videos that cannot be ruled out into a general graph with source nodes and sink nodes, use the graph segmentation algorithm to calculate the maximum matching value of the graph, and use the matching value as a threshold to complete nearly identical videos detection.

Features and effects of the present invention:

The method for eliminating nearly identical videos in a large-scale network video database proposed by the invention is used for content monitoring of large-scale network videos. This method performs feature reconstruction on video, an effective representation of dimensionality reduction. Simple grayscale features can effectively retain most of the information of the image, and the same block method can bring a unified measurement for comparison of key frames with different resolutions. The method of principal component analysis further retains the main features of the key frame and maintains the largest part of the similarity. At the same time, due to the method of statistical quantification from a large number of pictures, the binary feature that best represents the key frame-level characteristics is directly extracted. It greatly facilitates later computer processing and ensures efficient processing speed. At the same time, the present invention adopts key frame-level features to generate global features, so that the hierarchical detection method using both global and local features can quickly find non-nearly identical videos, avoiding a large calculation burden in the later stage. It can be foreseen that this method can be widely used in network video storage, indexing and can be used in the post-processing stage of search engine search results reordering, and the method of the present invention also provides a practical and feasible framework for the detection of near-identical videos , which facilitates the fusion of image features with less computational complexity and higher discrimination.

Detailed ways

A fast and robust near-identical video detection and exclusion method proposed by the present invention is described in detail in conjunction with the embodiments as follows:

A fast and robust near-identical video detection and exclusion method proposed by the present invention includes extracting the key frame features of the video to be detected, the video feature generation stage of the generated video global features, and comparing the global feature vector of the video to be detected with the existing There is a global feature vector of video to complete the pattern matching stage of the detection of nearly the same video, the video feature generation stage includes key frame image segmentation, extracting the average gray level of each block as key frame feature, and using the principal component analysis method ( PCA) performs binary quantization on the key frame features, and generates global features based on the quantized key frame features.

Method of the present invention mainly comprises the following steps:

(1) generate a key frame of the video to be detected;

(2) block the key frame to obtain the average gray feature vector of the key frame;

(3) Utilize the principal component analysis method to reduce the dimension of this gray-scale feature vector to the average gray-scale feature vector obtained;

(4) Using the average value obtained from the statistical results of a large number of pictures as a threshold to perform binarization and quantization on the average gray feature vector after dimensionality reduction;

(5) Generate the global feature vector of the video to be detected based on the key frame average grayscale feature vector after binarization and quantification;

(6) compare the global feature vector of the video to be detected and the global feature vector of the existing video, get rid of the larger existing video with this video feature difference to be detected in the database;

(7) For videos that cannot be excluded with global features in the database, use the similarity based on video key frame level feature vectors to build a bipartite graph;

(8) Calculate the maximum matching value of this bipartite graph with the maximum matching approximation algorithm, compare the maximum matching value with the threshold Th, and get rid of the larger existing video with this video difference to be detected in the database again;

(9) Modify the bipartite graph of videos that cannot be ruled out into a general graph with source nodes and sink nodes, use the graph segmentation algorithm to calculate the maximum matching value of the graph, and use the matching value as a threshold to complete nearly identical videos detection.

The above steps (1)-(5) are the video feature generation stage, and steps (6)-(9) are the pattern matching stage

In the above method, the maximum matching approximation algorithm in step (8) is a known algorithm.

The embodiment of above-mentioned method specifically comprises the following steps:

(1) adopt the method for sampling every 20 frames to generate the key frame of video;

(2) Divide the key frame into blocks, and the number of blocks is 8*8 and 7*7 respectively (the size of each block is the same); for each block to calculate the average gray level in the block, the gray value of each block is concatenated Become a 113 (64+49) dimension feature vector as the average gray feature vector of the key frame;

(3) Obtain the covariance matrix required for principal component analysis by counting the mean vector of a large number of pictures as the mean vector required by PCA; by calculating the eigenvector and eigenvalue of the covariance matrix, and then selecting the top 64 with the largest eigenvalue Dimensional feature vectors form a new projection matrix A. Use the covariance matrix to perform principal component analysis (PCA) dimensionality reduction on the average gray feature vector of the key frame generated in (2), that is, the average gray feature vector of the key frame is passed Matrix A is projected, and a new 64-dimensional feature vector is obtained;

(4) Compare the value of each dimension of the 64-dimensional feature vector generated in (3) with the mean value vector after principal component analysis obtained from the statistics of a large number of pictures as a threshold. If it is greater than or equal to the mean value vector, then the dimension is set to 1. Otherwise, it is set to 0; in this way, each eigenvector is quantized and converted into a 64-bit binary value as a hash value;

(5) generate 64-dimensional feature vectors to all key frames of a video through the steps described above, and compare the corresponding bits of the feature vectors of all key frames of the video bit by bit, if the corresponding bit is 1 than the corresponding bit is 0 If the number is large, the position of the global feature vector is 1, otherwise it is set to 0; the 64-dimensional global feature vector about the video is obtained;

(6) compare the global feature vector of the video to be checked with the global feature vector of each video in the video database, if they do not match, the two videos are considered not to be nearly similar videos, and they are excluded, and then the next video is compared; otherwise, turn to ( 7)

(7) abstract all the key frames of the two videos to be compared into nodes, and set up the corresponding edge according to the feature vector to finally set up a bipartite graph;

(8) Calculate the bipartite graph established in step (7) with the maximum matching approximation algorithm, if the result of the algorithm is greater than a given threshold Th (preset, the size is related to the number of key frames, the more the number of key frames, the greater the value ), think that these two videos are nearly identical videos, if the result of the algorithm is less than Th/2, then think that these two videos are different, otherwise go to step (9);

(9) On the basis of the bipartite graph, add two new nodes, which are respectively the source node (SOURCE) and the sink node (SINK), and all the nodes to be compared (nodes representing specific video key frames) Connect an edge with the source node, and connect the other nodes with an edge with the sink node to obtain a general graph; use the maximum matching value obtained by the graph segmentation algorithm on the general graph, and compare the result with a given threshold Th, if If it is greater than Th, it is nearly the same video; otherwise, the two videos are considered different, and the next video is compared.

Claims (2)

1. A fast and robust near-identical video detection and exclusion method, characterized in that the method includes extracting the key frame features of the video to be detected, the video feature generation stage of the generated video global features, and comparing the global features of the video to be detected The feature vector and the global feature vector of the existing video complete the pattern matching stage of the detection of nearly the same video. The video feature generation stage includes dividing the key frame image, extracting the average gray level of each block as the key frame feature, and using the main The component analysis method performs binary quantization on key frame features, and generates global features based on the quantized key frame features. 2. The method according to claim 1, characterized in that it mainly comprises the following steps: (1) generate a key frame of the video to be detected; (2) block the key frame to obtain the average gray feature vector of the key frame; (3) Utilize the principal component analysis method to reduce the dimension of this gray-scale feature vector to the average gray-scale feature vector obtained; (4) Using the average value obtained from the statistical results of a large number of pictures as a threshold to perform binarization and quantization on the average gray feature vector after dimensionality reduction; (5) Generate the global feature vector of the video to be detected based on the key frame average grayscale feature vector after binarization and quantification; (6) compare the global feature vector of the video to be detected and the global feature vector of the existing video, get rid of the larger existing video with this video feature difference to be detected in the database; (7) For videos that cannot be excluded with global features in the database, use the similarity based on video key frame level feature vectors to build a bipartite graph; (8) Calculate the maximum matching value of this bipartite graph with the maximum matching approximation algorithm, compare the maximum matching value with the threshold Th, and get rid of the larger existing video with this video difference to be detected in the database again; (9) Modify the bipartite graph of videos that cannot be ruled out into a general graph with source nodes and sink nodes, use the graph segmentation algorithm to calculate the maximum matching value of the graph, and use the matching value as a threshold to complete nearly identical videos detection.