A K-means clustering-based shape retrieval technique for 3D mesh models

3D mesh models are used in various applications in mechanical engineering, medical science and computer science and so on. Due to the large size of shape databases, searching and browsing of the shape collections is a challenging task. There is a need to retrieve desired models effectively and robustly. Many methods have been suggested for this purpose Shape retrieval methods can be divided into three main groups: Feature-based techniques, graph-based techniques and view-based techniques. Feature-based techniques mainly focus on topology and geometry of the 3D models. Global feature distribution based technique and sector/shell-based distribution histograms are the most popular feature-based techniques. Graph-based techniques represent topology of the model by connecting the meaningful parts of the 3D shapes. The most popular graph-based methods are reeb graphs and skeleton-based techniques. View-based techniques utilize completely different approach from other two pre-mentioned techniques. In this approach, two models are similar if they look same from all viewpoints. Researchers mainly focus on finding descriptors, which is suitable for rigid models. Retrieval of non-rigid models is a still challenging field that needs to be studied more. For non-rigid models, descriptors that are designed should be insensitive to different poses. For non-rigid model retrieval, a new method is proposed, which first divides a model into clusters using geodesic distance metric and then computes the descriptor using these clusters. Mesh segmentation is performed using a skeleton-based K-means clustering method. Weak point of K-means clustering is its sensitivity to the selected initial seed points. To solve this problem, K-furthest seeds are calculated by means of 3D model skeleton to increase the speed of the K-means algorithm. Additionally, two furthest points of model are selected as initial two seeds to make K-means algorithm more accurate. For the selection of next seed points, a greedy approach is chosen. Moreover, implementing Geodesic distance instead of Euclidean distance makes skeleton-based K-means method insensitive to different poses. After clustering the model via skeleton-based K-means approach, an area-based descriptor is computed for all models in database in an off-line step. The descriptor used is invariant to scale and orientation. The descriptor is in the vector form, which denotes the sorted normalized area for clusters. Finally, similar objects for the selected input model are retrieved. Similarity rate between two models are computed based on Euclidean distance between two descriptors. For the validation of the proposed retrieval algorithm, we prepared a testing model, which consists of 56 3D models. These models are taken from Princeton shape benchmark and SHREC'11 benchmark. Articulated objects from human to animals exist in the model database that are used for this study's experiments.