A K-MEANS CLUSTERING BASED SHAPE RETRIEVAL TECHNIQUE FOR 3D MESH MODELS

Mohammadhassan REZAEI; Erkan GUNPİNAR

A K-MEANS CLUSTERING BASED SHAPE RETRIEVAL TECHNIQUE FOR 3D MESH MODELS

Mohammadhassan REZAEI, Erkan GUNPİNAR

Öz

Due to the large size of shape databases, importance of effective and robust method in shape retrieval has been increased. Researchers mainly focus on finding descriptors which is suitable for rigid models. Retrieval of non-rigid models is a still challenging field which needs to be studied more. For non-rigid models, descriptors that are designed should be insensitive to different poses. For non-rigid model retrieval, we propose a new method 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. Each cluster is represented by an area based descriptor which is invariant to scale and orientation. Finally, similar objects for the input model are retrieved. Articulated objects from human to animals are used for this study’s experiments for the validation of the proposed retrieval algorithm.

Anahtar Kelimeler

Shape Retrieval; K-means Clustering; Mesh Skeleton; Geodesic distance

Tam Metin:

PDF (English)

Referanslar

Agarwal, P. K., Mustafa, “K-means projective clustering” ,In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , ACM, pp. 155-165, June 2004.

Ankerst, M., Kastenmüller, G., Kriegel, H. P. , Seidl, T. “3D shape histograms for similarity search and classification in spatial databases”, In International Symposium on Spatial Databases, pp. 207-226,Springer Berlin Heidelberg, July 1999.

Ansary, T. F., Vandeborre, J. P.,Daoudi, M., “3d-model search engine from photos”,In Proceedings of the 6th ACM international conference on Image and video retrieval, pp. 89-92, ACM, July 2007.

Au, O. K. C., Tai, C. L., Chu, H. K., Cohen-Or, D., Lee, T. Y., 2008, “Skeleton extraction by mesh contraction”, ACM Transactions on Graphics (TOG), Vol. 27 (3), 44.

Bespalov, D., Regli, W. C., Shokoufandeh, A. , “Reeb graph based shape retrieval for CAD”, In ASME 2003 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, pp. 229-238, American Society of Mechanical Engineers, January 2003.

Biasotti, S., Marini, S., Mortara, M., Patane, G., Spagnuolo, M., Falcidieno, B., “3D shape matching through topological structures”, In International Conference on Discrete Geometry for Computer Imagery ,pp. 194-203, Springer Berlin Heidelberg, November 2003.

Bommes, D., Zimmer, H., Kobbelt, L., 2009, “Mixed-integer quadrangulation”, ACM Transactions on Graphics (TOG), Vol.28 (3), 77.

Chen, D. Y., Tian, X. P., Shen, Y. T., Ouhyoung, M., “On visual similarity based 3D model retrieval” ,In Computer graphics forum ,Vol. 22, No. 3, pp. 223-232, Blackwell Publishing, Inc, September 2003.

Corney, J., Rea, H., Clark, D., Pritchard, J., Breaks, M., MacLeod, R., “Coarse filters for shape matching”, IEEE Computer Graphics and Applications, 22(3), 65-74, 2002.

Dey, T. K., Sun, J., “Defining and computing curve-skeletons with medial geodesic function”,In Symposium on geometry processing ,Vol. 6, pp. 143-152, June 2006.

Dijkstra, E. W. 1959, “A note on two problems in connexion with graphs”, Numerische mathematik, 1(1), 269-271.

Eppstein, D., Goodrich, M. T., Kim, E., Tamstorf, R., “Motorcycle graphs: canonical quad mesh partitioning” ,In Computer Graphics Forum , Vol. 27, No. 5, pp. 1477-1486, Blackwell Publishing Ltd , July 2008.

Funkhouser, T., Min, P., Kazhdan, M., Chen, J., Halderman, A., Dobkin, D., Jacobs, D., 2003, “A search engine for 3D models”, ACM Transactions on Graphics (TOG), 22(1), 83-105.

Gagvani, N., Silver, D. 1999,”Parameter-controlled volume thinning”, Graphical Models and Image Processing, 61(3), 149-164.

Gibou, F., Fedkiw, R., “A fast hybrid k-means level set algorithm for segmentation”, In 4th Annual Hawaii International Conference on Statistics and Mathematics, pp. 281-291, January 2005.

Gunpinar, E., Suzuki, H., Ohtake, Y., Moriguchi, M. 2013, “Generation of bi-monotone patches from quadrilateral mesh for reverse engineering”, Computer-Aided Design, 45(2), 440-450.

Gunpinar, E., Moriguchi, M., Suzuki, H., Ohtake, Y., 2014a, ”Feature-aware partitions from the motorcycle graph” ,Computer-Aided Design, 47, 85-95.

Gunpinar, E., Moriguchi, M., Suzuki, H., Ohtake, Y. 2014b, “Motorcycle graph enumeration from quadrilateral meshes for reverse engineering” ,Computer-Aided Design, 55, 64-80.

Herwig, R., Poustka, A. J., Müller, C., Bull, C., Lehrach, H., O'Brien, J. 1999, “Large-scale clustering of cDNA-fingerprinting data”, Genome research, 9(11), 1093-1105.

Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T. L., ”Topology matching for fully automatic similarity estimation of 3D shapes”, In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pp. 203-212, ACM, August 2001.

Horn, B. K. P. , 1984, “Extended gaussian images”, Proceedings of the IEEE, 72(12), 1671-1686.

Ip, C. Y., Lapadat, D., Sieger, L., Regli, W. C., ”Using shape distributions to compare solid models”. In Proceedings of the seventh ACM symposium on Solid modeling and applications, pp. 273-280, ACM, June 2002.

Kang, S. B., Ikeuchi, K. ,“Determining 3-D object pose using the complex extended Gaussian image”In Computer Vision and Pattern Recognition, 1991. Proceedings CVPR’91, IEEE Computer Society Conference on, pp. 580-585, IEEE, June 1991.

Kazhdan, M., Chazelle, B., Dobkin, D., Funkhouser, T., Rusinkiewicz, S, 2004, ”A reflective symmetry descriptor for 3D models” , Algorithmica, 38(1), 201-225.

Kazhdan, M., Funkhouser, T., Rusinkiewicz, S., “Rotation invariant spherical harmonic representation of 3 d shape descriptors”, In Symposium on geometry processing ,Vol. 6, pp. 156-164, June 2003.

Lian, Z., Godil, A., Bustos, B., Daoudi, M., Hermans, J., Kawamura, S., ..., Dp Suetens, P., 2011, “Shape Retrieval on Non-rigid 3D Watertight Meshes”, In Eurographics Workshop on 3D Object Retrieval (3DOR).

Lloyd, S. 1982, “Least squares quantization in PCM” ,IEEE transactions on information theory”, 28(2), pp. 129-137.

Min, P., Halderman, J. A., Kazhdan, M., Funkhouser, T. A., ”Early experiences with a 3D model search engine”, In Proceedings of the eighth international conference on 3D Web technology, pp. 7-ff, ACM, March 2003.

Ohbuchi, R., Otagiri, T., Ibato, M., Takei, T., 2002, “Shape-similarity search of three-dimensional models using parameterized statistics”, In Computer Graphics and Applications, 2002. Proceedings, 10th Pacific Conference on, pp. 265-274, IEEE.

Osada, R., Funkhouser, T., Chazelle, B., Dobkin, D., 2002 “Shape distributions”, ACM Transactions on Graphics, (TOG), 21(4), 807-832.

Paquet, E., Rioux, M., Murching, A., Naveen, T., Tabatabai, A., 2000, ”Description of shape information for 2-D and 3-D objects”, Signal processing: Image communication, 16(1), 103-122.

Shilane, P., Min, P., Kazhdan, M., Funkhouser, T. , “The princeton shape benchmark”, In Shape modeling applications, 2004. Proceedings, pp. 167-178, IEEE, June 2004.

Sundar, H., Silver, D., Gagvani, N., Dickinson, S., “Skeleton based shape matching and retrieval”, In Shape Modeling International, 2003 ,pp. 130-139I, EEE, May 2003.

Tagliasacchi, A., Alhashim, I., Olson, M., Zhang, H., “Mean curvature skeletons”, In Computer Graphics Forum ,Vol. 31, No. 5, pp. 1735-1744 ,Blackwell Publishing Ltd, August 2012.

Vranic, D. V., Saupe, D., Richter, J. (2001). “Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics”,In Multimedia Signal Processing, 2001 IEEE Fourth Workshop on (pp. 293-298), IEEE.

Zhang, C., Chen, T., 2001, “Efficient feature extraction for 2D/3D objects in mesh representation”, In Image Processing, 2001. Proceedings. 2001 International Conference on (Vol. 3, pp. 935-938), IEEE