Research On Organization Model Of Video Data And Dimensionality Reduction Algorithm

With the development of multimedia, compute technology and internet, our society is moving towards the information age. People are no longer satisfied with the information described by the text or the image. They demand multimedia information, which contain more information than any other. Multimedia information is increasing so rapidly that people now are facing an ocean of information. But it also brings a lot of problem, such as storage, management and retrieval. Among all sort of multimedia data, video data proportion more and more. How to build a data organization model which is suited for storing, describing and retrieving video data is urgently question. The traditional database and relation data organization model are good at describing structured data and retrieving data based on key words and text. But it fails in video data because it is unstructured and spatial. So a special technology is needed for retrieving video information.Content-based video retrieval(CBVR) emerges as the times require. CBVR works with the similarity measure of the feature of the scene, key-frame and segment, through which the database finds the video needed by the user. That is greatly different from the traditional one. It is a synthetically technology based on multimedia database, internet, image processing and pattern recognition est. Nowadays, the main research of CBVR focuses on video shot segmentation, feature extraction and description(including vision feature, texture feature, color feature, shape feature, motion feature, object information and so on), key-frame extraction and video structural analysis. All technologies are based on image process except video structural analysis. The main goal of video structural analysis technology is to extract the main content of the video, and then make a structural description up-to-down.The efficient contented-based retrieval video system should organized the data reasonably, so that the user can find the key-frame similar to the provided image and find the interested video though it.This paper first study the theory of Data Cube. The multi-dimension data model based on it is a logical concept. It is used to solve the problem of data quick retrieval and exposition in multi-angle. The information here will be regarded as a cube by introducing dimension, level, content, data and aggregate. Dimension, regarded as an aspect of an object, contain attribute and level. An object can be organized by more than three dimensions. Data and content is the set of data or content of the dimension attribute. Aggregate means congregating the data or the content using the aggregate function.Data Cube is advanced on multi-dimension data model. To organize the video data reasonable, this paper introduces it in video data organization and redefines it, regarded it as a set of Dimension, Hiberarchy, Measurement and Aggregate. In this model, video data is regarded as a set of key-frame, remark, caption and time. The measurement of the attribution of these four(including the color feature, texture feature, shape feature, space feature and content) are used in Data Cube measurement and is congregated by aggregate function.The Data Cube has so much advantage because of great congregation. But the traditional aggregate function fails in the video data because it contain much space characteristic. Unlike traditional aggregate function, the aggregate function this paper introduces here, clustering, congregates the video data based on the nature similarity and rules of the object. This processing don't have any apriori knowledge while clustering so that it reflects the trait of the video data impersonality. To attain the goal of aggregate, this paper uses K-means clustering means cluster the key-frame image and then uses the leadimage representing the clustered key-frame. This is not enough any way. This paper also introduce an suitable index rule.When a user retrieve a key-frame, the data base index the image using Range Query between classes and K Nearest Neighbor Query in class. It takes the advantage of the RQ and KNNQ. Less time is used while recall ratio and precision ratio do not decrease.Because the precision of retrieval is not completely determined by the number of dimensionality, this paper proposes the dimensionality reduction algorithm—LPP(Locality Preserving Projections) to remove redundancy and relation of the high dimension feature of the key-frame image. It is linear, but it not only has many linear algorithm merit, such as nice derelevance, calculating quickly and reliable result, but also considers the neighbor of the image feature vector based on the similarity function consistent with clustering and retrieval, so that it maintain the original global topology construct. The algorithm is described as follow: first, it find k nearest neighbors of every vector; then it reconstructs the matrix of weights based on the distance between the vector and its neighbor; at last, low dimension vectors are gotten when high- dimension vector project to low-dimension space though that matrix.During the study of the LPP, I found that the number of the dimension we get after dimensionality reduction affect the retrieval result greatly. The retrieval result of =23 is nicer than the others in experiment. If the is set too large, the relevance of high-dimension vectors can't be clearly removed. On the opposite, if the is set too small, the overlap occurs when high-dimension vector projects to low-dimension and the original topological structure will be destroyed. All these do harm to the precisions of the retrieval.With the consideration of the relation of the dimension and the error cost function, this paper proposes a dimensionality reduction algorithm of variable dimension locality preserving projections—VD-LPP. It reduces variable dimensions of different databases whose classes of key-frames are different using clustering. The method of VD-LPP is modified based on LPP method, but it considers the relation between every vector and its neighbors. After studying the effect of the Bayes error in image processing area, the optimal dimension of feature space of classes video data base is found. It also adopts a method of computing the matrix of weights and uses K-means in establishing the dimension. In that way, the redundancy and relation between the high-dimension vector can be maximum removed. The approximate algorithm in VD-LPP does not destroy the original topological structure and meantime it decreases the computing complexity of eigenvalue and eigenvector. The experiment shows that the retrieval using in video database based on VD-LPP introduced here is more reasonable and excellence.At last, this paper makes the research of the content-based video retrieval system. This retrieval system provides retrieval means based on key-frame while using the theory of the Data Cube and the VD-LPP dimensionality reduction and the research achievement of the other member of the project. The experiment of it displays that the time cost in retrieval really shorten while the recall ratio and precision ratio do not decrease. After analysing the result of the experiment, we get the relation between the class and the retrieval time and the optimal number of the class to achieve the optimal retrieval efficient, which set a platform for our further research.