Üç Boyutlu Çözüm Ağları için K-Means Kümeleme Tabanlı Şekil Araması

Öz

Şirketlerin veri tabanlarında çok fazla şekil bulunmaktadır. İstenilen şekillerin bu veri tabanından bulunup getirilmesi için etkili ve güçlü şekil arama metodlarının kullanılması gerekmektedir. Araştırmacılar genelde rijit (esnemeyen) modellere uygun geometrik tanımlayıcılar üzerine odaklanmışlardır. Rijit olmayan modellerin bulunması daha zor olmakta ve bu konuda daha çok çalışılması gerekmektedir. Rijit olmayan modeller için tasarlanan geometrik tanımlayıcılar değişik model pozlarında (insan modeli için yürüme, oturma gibi pozlar) çalışabilmesi gerekmektedir. Rijit olmayan model araması için, öncelikle model jeodezik metrik kullanarak parçalara bölünür. Sonra her bir parçanın alanı toplam alana bölünerek geometrik tanımlayıcı hesaplar. İskelet-bazlı K-means metodu kullanarak model parçalara ayrılmıştır. Her parça alan-bazlı tanımlayıcılar kullanılarak tanımlanmıştır. Bu tanımlayıcıların ölçek ve oryantasyon değişikliklerine hassasiyeti yoktur. Çalışmanın testlerinde insandan hayvanlara eklemli canlılar kullanılmış, önerilen model arama metodunun performansı doğrulanmıştır.

Anahtar Kelimeler

• Jeodezik uzaklık,K-means kümeleri,Çözüm ağı iskeletleri,Model bulma

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

Abstract

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 its descriptor using the area of these clusters. A skeleton-based K-means clustering method is utilized for dividing the model into clusters. Each cluster is represented by an area based descriptor which is invariant to scale and orientation. Articulated objects from human to animals are employed in this study’s experiments for the validation of the proposed retrieval algorithm.

Keywords

• Geodesic distance,K-means clustering,Mesh skeleton,Shape retrieval

Kaynakça

1. Agarwal, P. K., Mustafa, N. H., “K-means Projective Clustering” ,In Proceedings of The Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , ACM, Paris, France, pp. 155-165, 14 – 16 June 2004.
2. 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.
3. 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, Amsterdam, The Netherlands, pp. 89-92, ACM, 09 - 11 July 2007.
4. 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.
5. 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 , Chicago, Illinois, USA, pp. 229-238, American Society of Mechanical Engineers, 2–6 September 2003.
6. 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.
7. Bommes, D., Zimmer, H., Kobbelt, L., 2009, “Mixed-integer Quadrangulation”, ACM Transactions on Graphics (TOG), Vol.28 (3), 77.
8. Chen, D. Y., Tian, X. P., Shen, Y. T., Ouhyoung, M., 2003, “On Visual Similarity Based 3D Model Retrieval” ,In Computer Graphics Forum, Vol. 22, No. 3, pp. 223-232, Blackwell Publishing, Inc, September 2003.

9. Corney, J., Rea, H., Clark, D., Pritchard, J., Breaks, M., MacLeod, R., 2002, “Coarse Filters for Shape Matching”, IEEE Computer Graphics and Applications, Vol. 22(3), pp. 65-74, 2002.
10. 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.
11. Dijkstra, E. W. 1959, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, Vol. 1(1), pp. 269-271.
12. Eppstein, D., Goodrich, M. T., Kim, E., Tamstorf, R., 2008, “Motorcycle Graphs: Canonical Quad Mesh Partitioning”, In Computer Graphics Forum , Vol. 27, No. 5, pp. 1477-1486, Blackwell Publishing Ltd , July 2008.
13. 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), Vol. 22(1), pp. 83-105.
14. Gagvani, N., Silver, D. 1999,”Parameter-Controlled Volume Thinning”, Graphical Models and Image Processing, Vol. 61(3), pp. 149-164.
15. Gibou, F., Fedkiw, R., “A fast hybrid k-means level set algorithm for segmentation”, In 4th Annual Hawaii International Conference on Statistics and Mathematics, Honolulu, Hawaii, pp. 281-291, 9-11 January 2005.
16. Gunpinar, E., Suzuki, H., Ohtake, Y., Moriguchi, M. 2013, “Generation of Bi-Monotone Patches from Quadrilateral Mesh for Reverse Engineering”, Computer-Aided Design, Vol. 45(2), pp. 440-450.
17. Gunpinar, E., Moriguchi, M., Suzuki, H., Ohtake, Y., 2014a,”Feature-Aware Partitions from the Motorcycle Graph”, Computer-Aided Design, Vol. 47, pp. 85-95.
18. Gunpinar, E., Moriguchi, M., Suzuki, H., Ohtake, Y. 2014b, “Motorcycle Graph Enumeration from Quadrilateral Meshes for Reverse Engineering” ,Computer-Aided Design, Vol. 55, pp. 64-80.
19. 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, Vol. 9(11), pp. 1093-1105.
20. 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, Los Angeles, CA, USA, pp. 203-212, ACM, 12 - 17 August 2001.
21. Horn, B. K. P., 1984, “Extended Gaussian Images”, Proceedings of the IEEE, Vol. 72(12), pp. 1671-1686.
22. 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, Saarbrucken, Germany, pp. 273-280, ACM, 17 - 21 June 2002.
23. 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.
24. Kazhdan, M., Chazelle, B., Dobkin, D., Funkhouser, T., Rusinkiewicz, S, 2004, ”A Reflective Symmetry Descriptor for 3D models”, Algorithmica, Vol. 38(1), pp. 201-225.
25. Kazhdan, M., Funkhouser, T., Rusinkiewicz, S., “Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors”, In Symposium on Geometry Processing, Vol. 6, pp. 156-164, June 2003.
26. 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).
27. Lloyd, S. 1982, “Least Squares Quantization in PCM”, IEEE transactions on Information Theory”, Vol. 28(2), pp. 129-137.
28. 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, St. Malo, France, pp. 7-ff, ACM, 09 – 12 March 2003.
29. 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.
30. Osada, R., Funkhouser, T., Chazelle, B., Dobkin, D., 2002 “Shape distributions”, ACM Transactions on Graphics, (TOG), 21(4), 807-832.
31. 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, Vol. 16(1), pp. 103-122.
32. Shen, Y. T., Chen, D. Y., Tian, X. P., Ouhyoung, M., 2003,”3D Model Search Engine based on Lightfield Descriptors”, In Proc. Eurographics, Granada, Spain, 1–6 September 2003.
33. Shilane, P., Min, P., Kazhdan, M., Funkhouser, T., “The Princeton Shape Benchmark”, In Shape Modeling Applications, 2004. Proceedings, Genova, Italy, pp. 167-178, IEEE, 7-9 June 2004.
34. Sundar, H., Silver, D., Gagvani, N., Dickinson, S., “Skeleton Based Shape Matching and Retrieval”, In Shape Modeling International, Seoul, South Korea, pp. 130-139I, EEE, 12-15 May 2003.
35. 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.
36. Vranic, D. V., Saupe, D., Richter, J., “Tools for 3D-Object Retrieval: Karhunen-Loeve Transform and Spherical Harmonics”, In Multimedia Signal Processing, 2001 IEEE Fourth Workshop on (pp. 293-298), Cannes, France, 3-5 Oct. 2001.
37. Zhang, C., Chen, T., 2001, “Efficient Feature Extraction for 2D/3D Objects in Mesh Representation”, In Image Processing, 2001. Proceedings. 2001 International Conference on, Thessaloniki, Greece, Vol. 3, pp. 935-938, 7-10 Oct. 2001.