Video Retrieval Based On Graph

With the popularity of digital acquisition equipment and the development of multimedia technology, the video data on the Internet grows rapidly. Facing the massive video data, how to conduct video storage, organization, management and analysis effectively, has become the main research in the field of video. Video search engines at a practical level are based on the text strategies, such as Google Video Search, Yahoo Video Search, Bing Video Search and baidu. However, as the video presents diversified forms and rich semantics, it is usually difficult to use the language to describe and express precisely. In order to solve the defects of this text retrieval, content-based video retrieval technique is put forward. Domestic and oversea Universities, research organizations have joined in one after another to do related research.Clustering is a method which is often used in video analysis. In this thesis, we divide the existing clustering algorithms into five categories:Partitioning method, density method, hierarchical method, grid method and affinity propagation clustering method, and summarize their advantages and disadvantages. Kmeans is one of the most typical clustering algorithms, and it is used widely as it is simple and fast. Because the traditional Kmeans algorithm is sensitive to the initial clustering center and is hard to identify clustering parameter k, this thesis puts forward the Kmeans algorithm which is based on relation graph partition. The algorithm not only can select initial cluster centers effectively according to the data distribution characteristics, but also can determine the clustering numbers adaptively along with the specified data intensive degree. A large number of experiments show that the improved Kmeans algorithm has high accuracy and stability.The video is a kind of unstructured data, how to organize the video database is the primary work of video retrieval. High dimensional indexing technology of video database is the key method of these aspects. Firstly we describe a kind of video retrieval framework based on video content, including four parts:video database module, query module, retrieval module and the retrieval result’s optimization module; Secondly, we conduct video structural analysis:the video is divided into shot through the shot segmentation algorithm, then a number of shot clusters are generated through Kmeans algorithm based on relation graph partition. The similarities between each pairs of clusters are then calculated. The shots in the same shot cluster are consistency in the visual. The hierarchical structure is an important way of information organization. This thesis adopts hierarchical structure to organize shot clusters, and describes a query mechanism combining with coarse query and fine query. In coarse query phase, the shot cluster is the basic unit to do approximate query. In fine query phase, the shot cluster is expanded to find the former K shots which are the most similar. The mechanism compresses data greatly, reduces the amount of data accessed and the comparing number. Experimental results show that the clustering index in this thesis has high recall, precision and fast retrieval efficiency.A good video retrieval system can return the correct and related video, but also the result is concise. There is often a lot of redundancy video in video database, especially when the video has a great deal of similarity in the same index directory, even exists multiple copies of the same video. How to improve the simplicity of video retrieval’s results is another starting point of this article. According to the characteristics of video copy, this thesis proposed a shot similarity measurement based on the two partite graphs. Firstly, the algorithm extracts key frame sequences of two shots and selects a color histogram as the global feature of the key frame, Harris corner as a local feature, then constructs two partite graphs of two shots, finds out the maximum matching sequence of the two partite graphs, and thus calculates the video similarity. Based on the above proposed video database clustering indexing techniques and the two level searching mechanism, in coarse query phase, we detect copy video in shot cluster level. In fine query phase, we compute shot similarity based on the two partite graphs. Finally, judge out whether it is a copy of the source video compared with the given threshold. Experimental results show that the video copy detecting algorithm has good results for variety of copy forms:changes in luminance, picture noise, different frame rate, adding captions and so on.