Combining Clustering Methods For Indexing 3D Model Database

As the amount of 3D models on the Web grows, there is an increasing need for a 3D model retrieval system to help people find them. The design of 3D model retrieval system has become an active research area. Efficient indexing structure can improve the performance of 3D model retrieval greatly. Unfortunately, traditional research on 3D model retrieval always focused on shape feature extraction and comparability calculation. Right now there is no fundamental theory on the indexing structure of 3D models database that could be used for a 3D model retrieval system. Surveying the existing 3D model retrieval systems, they all use scan to index 3D model database. As the new 3D models are rapidly increasing, scan could not satisfy the client in the near future.However, the feature vector (FV) which is extracted to capture important characteristics of 3D models and used to determine the most similar models to a given query by performing a nearest neighbor (NN) search always be high-dimensional data. The increase of the dimension leads to the Dimensional Curse that most existing indexing techniques degrade rapidly when dimensionality goes higher. At the same time, 3D model database has 2 semantic gaps. One is between a 3D model's shape and its FV, the other is between a 3D model's shape and its pragmatic meanings. Due to the complex situation of 3D model database, it lacks the valuable information to build the indexing structure. Otherwise, along with the maturity of modeling, some kinds of new techniques are integrated into the 3D model retrieval systems. For example, the technique of 3D model mesh segmentation (abbreviate as the mesh segmentation) which decompose the 3D model into simple sub-models was planed to integrate into our Jilin university 3D model retrieval systems. Mesh decomposition benefits many applications, such as 3D model reuse. But it becomes a complex problem because of the complex relationship between 3D models and 3D sub-models. Summarily, we need to design an efficient indexing structure for the special high-dimensional feature vector data. It's not a simple task.Clustering is an analysis technique for discovering interesting data distributions and patterns in the database. Recently, clustering analysis technique often is used to handle the large high-dimensional databases. Cluster analysis techniques have shown a fine performance in the research area of content-based 2D image retrieval. Content-based 3D model retrieval has the similarity with content-based 2D image retrieval, so cluster analysis techniques could also been used in 3D model retrieval. As an unsupervised technique, cluster analysis technique is capable of narrowing semantic gap, analyzing the relationship among the shape feature of 3D models and grouping the similar features together without training information. From what have been mentioned above, we can draw a conclusion that we can build an index tree which roots in the process of hierarchical clustering algorithm.The study in this paper is fallen into three phases. We have used 3 kinds of indexing structure for 3D model retrieval system, and compared their efficiency and effectiveness.Firstly, we present an approach termed Cluster-index which uses cluster result simply to organize 3D model database. For a given query, Cluster-index only search within the nearest cluster from the query point. Obviously, Cluster-index can speed up the time spent on query dramatically, but the accuracy of the retrieval results is low. So the Cluster-index can not be used in 3D model retrieval system.Then, we choose an existing indexing approach which integrates cluster representation and nearest-neighbor search for large data sets with high dimensions to build indexing structure for 3D model database. The indexing structure called ClusterTree is a hierarchy of clusters and sub-clusters which incorporates the cluster representation into the index structure to achieve efficient retrieval. The experiments on Princeton Shape Benchmark (PSB) indicate that the ClusterTree achieved 100 percent accuracy on searching the nearest-neighbors, namely, same retrieval results as scan. At the same time ClusterTree spends 2 third less time than scan to perform a 16 nearest-neighbor search on 3D model retrieval system. ClusterTree also can dynamically reconstruct when new data points are added. However, ClusterTree also have a few shortcomings. ClusterTree is incapable of dealing with outliers, require the user specified parameter, and can not integrate sub-models which were outputted after mesh segmentation. All in all, the flexibility of ClusterTree is low. This kind of indexing structure can not fulfill the new functions and satisfy the complete demands of 3D model retrieval system.Finally, we have presented an indexing structure termed C+-tree which was designed to fit for 3D model database of 3D model retrieval system. C+-tree ameliorates the ClusterTree indexing approach. The proposed algorithm cancels the parameter k where k is the number of sub-clusters split form a cluster or a sub-cluster and auto-calculates k. C+-tree extends the meaning of a indexing tree. It affiliates the sub-model-index tree with the whole indexing structure. 3D model database and 3D sub-model database build their own indexing tree separately. The sub-models can find their father models which had been segmented into sub-models by the attribute Fa in the 3D model database. It keeps the independence of two different databases and saves the connection of two kinds of 3D models. C+-tree does not waste the valuable information of outliers but reserves them and makes clustering work together with outliers. C+-tree considers the outlier set as an input cluster and inserts it into the first level of C+-tree. This leaf node was named outlier-node. Outlier-node doesn't participate in searches until obtain p results on other part of C+-tree. Then the outlier-node will be scanned to update the retrieval results. To perform a dynamically reconstruction, C+-tree does not abandon the added random points but insert them into outlier-node or random data space.The experiments on PSB indicate that the C+-tree had inherited all the excellence of ClusterTree or even better and made up what the ClusterTree lacks. C+-tree spends 1 fifth scan time to perform a 16 nearest-neighbor search on 3D model retrieval system. At the same time, C+-tree is capable of dealing with outliers and sub-models, and cancels the parameter k to build better shape of indexing tree. The function of retrieval sub-models had been integrated into our Jilin university 3D model retrieval systems. The overall results show that the C+-tree outperforms several of the other index structures for 3D model database.