Video Copy Detection Based On Robust Hashing

With the development of computers and information technology, the Internet has become an important part of daily life. Especially with the development of multimedia technology, there are more and more video sites on Internet, and video content becomes more and richer. But the following network information security has become increasingly prominent. There are three main aspects exiting in safety problems of internet videos.First, people can easily copy and edit digital videos on the network, and freely spread them on the network. In 2006, there was a statistics about the most popular videos in Youtube, Google Video and Yahoo Video. It is found that the 27% of the search results are video copies. In particular, there are 85% of video search results contain 1-4 or more video copies in Youtube, and among some hot videos, the ratio of the video reproduction is even up to 93%. The existence of a large number of video copies greatly reduces the efficiency of video retrieval. Moreover, with the increase in video and a wide range of applications in video search site, copies of these videos are becoming the "junk videos" that endanger the video network.Second, the lacks of planning and consistency management of massive Internet videos often cause the disputes of intellectual property. Piracy and illegal downloading of copyrighted are harmful to the benefits of owners, and also dampen the incentive of innovation.Third, the dissemination and proliferation of online pornography, violence, and other adverse reaction information on the Internet seriously undermine the social atmosphere. They greatly affect the healthy growth of youngsters and harmonious development of society. How to ensure the health of minors’online and adverse content filtering has become a very difficult problem, which has attracted widespread concern in society.The three issues above mentioned are essentially video content authentication and identification problems. Robust hashing-based video copy detection is proposed and become the main method to solve these problems. Therefore, with the development of network personal video production and the spread of videos, video copy detection becomes more and more important in theoretical research and application, and it also becomes a research focus in multimedia information processing.This paper reviews the theory and the classical algorithm of the video copy detection system and video content authentication, and proposes a series of methods of video copy detection based on graph theory, manifold learning and dimensionality reduction. Meanwhile, in the sixth chapter of the paper, the three-dimensional digital watermark which is the result of early stages in pursuing the PhD is proposed.The main results of this paper are summarized as follows:(1) Proposed manifold learning-based robust hashing algorithms. Manifold learning is the basic method of pattern recognition. It can effectively find the internal distribution of high-dimensional geometry data in the form of unsupervised, and find the intrinsic information and internal laws hidden in high-dimensional data to achieve dimensionality reduction. In modern society, the video contents are more and more rich, and the capacities are more and more large in a direct view, the video exists in a high-dimensional space composed of a number of pixels. It is bad for the implementation of fast retrieval. We proposed three robust hashing algorithms based on the classical manifold learning algorithm and generate video hashes in the low-dimensional space for video copy detection.(2) Proposed a robust hashing algorithm based on double-layer embedding. For multi-scene video, a robust hashing scheme for video content identification and authentication is proposed, which is called Double-Layer Embedding scheme. Intra-cluster Locally Linear Embedding (LLE) and inter-cluster Multi-Dimensional Scaling (MDS) are used in the scheme. Some dispersive frames of the video are first selected through graph model, and the video is partitioned into clusters based on the dispersive frames and the K-Nearest Neighbor method during the hashing. Then, the intra-cluster LLE and inter-cluster MDS are used to generate local and global hash sequences which can inherently describe the corresponding video.(3) Proposed a video fingerprinting algorithm based on hypergraph model and a double optimal projection method which consists of intra-cluster and inter-clusters projection. Dimensionality reduction especially manifold learning algorithms is the optimization problem, and they try to get the low-dimensional embedding coordinates by maintain the relation between the points in a high dimensional as much as possible. First, the video is equivalent to a hypergraph in a high-dimensional space with frames as its vertices. Then a similarity measure is proposed to compute weights of hyperedges. Subsequently the video frames are partitioned into different clusters based on the hypergraph model. Double optimal projection is used to explore the optimal low-dimensional space for reducing the dimension of video. The statistics fingerprint and geometrical fingerprint are generated in the low-dimensional space to find whether a query video is copied from a video in the video database. The scheme is according to the characteristics of video data, and takes the global and local information of video content into account. Therefore, it has good results for video copy detection.(4) Proposed a robust hashing algorithm based on representative-dispersive frames. Video is composed by a large number of video frames. Frame format may be various, but from a macro point of view, each frame of the video can be taken as a point in high-dimensional space. The coordinates are the time domain or frequency domain attributes, the edge between points is determined by the relation between the frames. As a result, a video can be seen as a weighted graph in a high-dimensional space, in which the classical graph theory can be applied. The scheme uses the classical theory of graph theory to select representative and dispersive frames, and the video tomography image is generated by these frames, the kurtosis of tomography image is used to generate video features for video copy detection.(5) Proposed an independent triangle set-based watermarking algorithm using singular value decomposition (SVD) for 3D models. Each triangle in the independent triangle set has no shared vertexes with each other. In this algorithm, firstly, an independent triangle set is selected using a searching algorithm and a unique index. Then, a Hankel matrix is generated. Finally, SVD is applied into the matrix and the watermark is embedded by modulating singular values. The algorithm is resistant to similarity transformations, random noising and vertex reordering. In addition, during the detection, some keys are used instead of the original model, so it is a blind watermarking algorithm.In summary, this paper has deeply studied content-based video copy detection based on graph theory, manifold learning and dimensionality reduction, a series of robust hashing algorithms, and they provide reliable technical support for video content management and authentication. In addition, the paper also has a preliminary study in three-dimensional digital watermarking. Finally, paper concludes with a summary of the research, and the future research topics are summarized.