| With the development of the computer technology and popularity of network, the multimedia data increases surprisingly. And people are facing an ocean of multimedia. The following problems are storage, management and retrieval of the multimedia, which leads to the production of multimedia database. The multimedia database is different from traditional database because of special characteristic of multimedia data. Multimedia data is not formatted including plenty of information, which challenges us with how to construct the model of storage, description, and query. As the manual labeling depends on subjectivity of individual,and makes a heavy workload. So it is very difficult to achieve a good description and retrieval of multimedia information by only the keywords, which needs a effective and efficient method for multimedia data. The key issue is to find the methods by which people can get the information they interest quickly and exactly. As a result, content-based multimedia description and retrieval was proposed. Content-base retrieval is different from traditional information retrieval (IR). It works with the content and context description of multimedia, such as color, texture, shape and space relationship. For video, it works with similarity measure of the features of scene in video and slip in video.In content-based multimedia retrieval, the feature extracted from image or video is usually described by a feature vector. The feature vector is usually high-dimensional in order to describe multimedia information as exactly as possible. Take the color feature of image extracted by HSV histogram for example, it is expressed as a 256-dimensional vector. These feature vectors are much less than multimedia they described, however they are still high-dimensional, which make great influence upon the organization, indexing, similarity measure and retrieval of database. That is what we called disaster of dimensionality.Actually the feature extraction of image also involves the process of dimensionality reduction in a broad sense, in order to describe generalized feature of the image as exactly as possible. In fact, take the specific sets of high-dimensional feature vectors into consideration, and the high-dimensional space they produce, there is a great deal of redundancy. The precision of retrieval is not completely determined by the number of dimensionality at all, but influenced at a certain extent by the pertinence of high-dimensional vectors between each other. Furthermore, too large number of dimensionality also increases the complexity of clustering, indexing and retrieval, as speed as well. So it is significant to conduct the dimensionality reduction to the high-dimensional feature vectors, in order to eliminate the pertinence of vectors in high-dimensional space, and then to improve the precision and speed of the retrieval.A method dealing with the high-dimensional problem is to reduce the dimensionality by character combination, since it is easy to calculate the linear combination and to conduct analysis. Actually method of linearity is to project high-dimensional data to a low-dimensional space. Principal Component Analysis (PCA) is a traditional method to find the effective linear transform by K-L transform which is a linear orthogonal transform. It works well in eliminating the pertinence of vectors between each other. PCA aims at finding the projection or linear subspace which can best represent the original data under the minimum variance. However, there's no evidence to believe that PCA can work well in partitioning different sorts of data. Give a data set with different sort, such as the sets of image database, the direction eliminated by PCA may be the direction which can partition the different sorts of image data. That is apparently not helpful to clustering and retrieval. It can work well in linear space for its character of linear transform. However the high-dimensional space of image feature vectors is highly nonlinear. Great overlaps occur in lower-dimensional space after being projected from original high-dimensional space by PCA, which destroy the separability and topology structure of original data space. So it leads to great error for similarity retrieval and clustering, which is proved by the experiments.Locally linear Embedding (LLE) is method of nonlinear dimensionality reduction. It reconstructs the feature vectors by its nearest neighbors to describe the global nonlinear structure. Firstly the algorithm finds the k-nearest neighbors of the vector. Then it calculates the matrix of weights with which neighbors of the vector can best reconstruct it. At last, the algorithm computes the low-dimensional embedding vectors best reconstruct by the local matrix of weights. LLE is based on the similarity function consistent with clustering and retrieval. It takes the k-nearest neighbors into consideration, and computes the local reconstructing matrix of weights, which preserves the topology structure of original space after being embedded in to low-dimensional space.In LLE algorithm, the precision of retrieval varies greatly with different k-values. We take experiments with our image database. The results show the best precision when k-value is 20. If k is set too small, the embedding will not reflect the topology structure. If it is set too high, the embedding will lose its nonlinear and character, and produce overlaps in low-dimensional space. All of that will influence the precision of clustering and retrieval. This is caused by the fixed k-value without considering the distribution of each feature vector and its neighbors.Instead of the fixed k-value, considering the distributions of the vector and its neighbors, this paper proposes a dimensionality reduction algorithm of variable k-nn locally linear embedding (VK-LLE). The VK-LLE method is modified based on LLE method, but considering different distributions of each vector and its neighbors. It gives the method of computing the k-value of each feature vector. In VK-LLE, the algorithm adopts a method of computing the matrix of local reconstruction weights different from LLE. This method consistent with the clustering avoids the regularization parameter of LLE, and preserves the cluster structure of original space. The approximate algorithm in VK-LLE decreases the computing complexity of eigenvalue and eigenvector. Our experiments with the multimedia high-dimensional feature vectors show that VK-LLE outperforms the LLE with better clustering and retrieval.This paper researches on clustering and indexing structure of image high-dimensional feature vectors. Clustering aims at optimize the precision of classification of image, and supports similarity measure of Non-Euclidean distance. It can conduct partitioning without overlap in metric space. However the traditional clustering method usually involves repeated iteration with re-clustering when new items are inserted into image database, which makes great cost to multimedia database. It is not conducive to the establishment of efficient multimedia retrieval system. Another although clustering methods can work well in k nearest neighbor (K-NN) query, has no advantage in range query. The high-dimensional indexing has advantages in dynamic ability and queries. So it is very significant to combine the clustering method to high-dimensional tree-like indexing, and establish a more efficient structure of the high-dimensional index of multimedia database.This paper modifies the traditional fuzzy c-means (FCM), and gives a analysis of high-dimensional indexing structure, such as spatial access methods and metric access methods. Combining the modified FCM to tree-like indexing structure, this paper introduce a novel dynamic high-dimensional indexing structure based on metric space, called HC-Tree (Hierarchical Clustering Tree). It is built with hierarchical clustering by FCM, and indexed by tree-like structure. The insertion methods of HC-Tree make the tree balance and dynamic. We give a method to determine whether a node reach the qualification of splitting operation. Then we give the methods of nodes splitting strategy, which make the nodes of HC-Tree are much more compact, uniform and symmetrical, and then make much less overlaps. We implement the K-NN queries and Range queries. Especially we give a method of heuristic browsing and retrieval, by which We realize the visualization of database structure with HC-Tree. The experimental results show that the HC-Tree outperforms the M-Tree and Slim-Tree with more efficient retrieval and browsing.At last, this paper makes the research on content-base multimedia information retrieval system and multimedia database. We design and implement a web-based Multimedia Information Retrieval System (MIRSYS), with the dimensionality reduction algorithm and HC-Tree proposed in this paper and the research results of other members of our group. MIRSYS takes a structure of B/S three-tier network architecture. MIRSYS consists of image retrieval sub-system and video retrieval sub-system. In this paper, we make an attempt about the combination of lower visual features and higher semantic retrieval. We supply the text-base and content-based retrieval with video retrieval. MIRSYS provides a completed and integrated solution for content-based multimedia retrieval. MIRSYS supply a platform for our further research.Multimedia information retrieval involves knowledge of Cross-discipline, such as multimedia database, computer vision, pattern recognition, computer network, human-computer interaction techniques, and human perception est. Their developments are mutually reinforcing. It is believed that through the corporate efforts of researchers, the multimedia information retrieval will change people's lives and make people no longer confused with the oceans of information. |
PDF Full Text Request