A novel approach for partial shape matching and similarity based on data envelopment analysis
Arhid K.,  Zakani F.R., Bouksim M.,  Sirbal B.,  Aboulfatah M.,  Gad T.

Laboratory of Informatics, Imaging, and Modeling of Complex Systems (LIIMSC) Faculty of Sciences and Techniques, Hassan 1st University, Settat, Morocco;
Laboratory of Analysis of Systems and Treatment of Information (LASTI) Faculty of Sciences and Techniques, Hassan 1st University, Settat, Morocco

 PDF

Abstract:
Due to the growing number of 3D objects in digital libraries, the task of searching and browsing models in an extensive 3D database has been the focus of considerable research in the area. In the last decade, several approaches to retrieve 3D models based on shape similarity have been proposed. The majority of the existing methods addresses the problem of similarity between objects as a global matching problem. Consequently, most of these techniques do not support a part of the object as a query, in addition to their poor performance for classes with globally non-similar shape models and also for articulated objects. The partial matching technique seems to be a suitable solution to these problems. In this paper, we address the problem of shape matching and retrieval. We propose a new approach based on partial matching in which each 3D object is segmented into its constituent parts, and shape descriptors are computed from these elements to compare similarities.  Several experiments investigated that our technique enables fast computing for content-based 3D shape retrieval and significantly improves the results of our method based on Data Envelopment Analysis descriptor for global matching.

Keywords:
partial shape matching, shape retrieval, 3D descriptor, indexation.

Citation:
Arhid K, Zakani FR, Bouksim M, Sirbal B, Aboulfatah M, Gadi T. A novel approach for partial shape matching and similarity based on data envelopment analysis. Computer Optics 2019; 43(2): 316-323. DOI: 10.18287/2412-6179-2019-43-2-316-323.

References:

  1. Ioannakis G, Koutsoudis A, Pratikakis I, Chamzas C. RETRIEVAL – An online performance evaluation tool for information retrieval methods. IEEE Transactions on Multimedia 2018; 20(1): 119-127. DOI: 10.1109/TMM.2017.2716193.
  2. Yang Y, Lin H, Zhang Y. Content-based 3-D model retrieval: A survey. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews 2007; 37(6): 1081-1098. DOI: 10.1109/TSMCC.2007.905756.
  3. Lara López G, Pe >a Pérez Negrón A, De Antonio Jiménez A, Ramírez Rodríguez J, Imbert Paredes R. Comparative analysis of shape descriptors for 3D objects. Multimedia Tools and Applications 2017; 76(5): 6993-7040. DOI: 10.1007/s11042-016-3330-5.
  4. Bouksim M, Zakani FR, Arhid K, Aboulfatah M, Gadi T. New approach for 3D Mesh Retrieval using data envelopment analysis. International Journal of Intelligent Engineering and Systems 2018; 11(1): 98-107. DOI: 10.22266/ijies2018.0131.01.
  5. Kazmi IK, You L, Zhang JJ. A survey of 2D and 3D Shape descriptors. In Book: 2013 10th International Conference Computer Graphics, Imaging and Visualization, IEEE, 2013, Macau, China; 1-10. DOI: 10.1109/CGIV.2013.11.
  6. Guo Y, Bennamoun M, Sohel F, Lu M, Wan J, Kwok NM. A comprehensive performance evaluation of 3D local feature descriptors. International Journal of Computer Vision 2016; 116(1): 66-89. DOI: 10.1007/s11263-015-0824-y.
  7. Li B, Lu Y, Li C, et al. A comparison of 3D shape retrieval methods based on a large-scale benchmark supporting multimodal queries. Computer Vision and Image Understanding 2015; 131: 1-27. DOI: 10.1016/J.CVIU.2014.10.006.
  8. Liu A, Li W, Nie W, Su Y. 3D models retrieval algorithm based on multimodal data. Neurocomputing 2017; 259: 176-182. DOI: 10.1016/J.NEUCOM.2016.06.087.
  9. Chen D-Y, Tian X-P, Shen Y-T, Ouhyoung M. On visual similarity based 3D model retrieval. Eurographics 2003; 22(3): 223-232. DOI: 10.1111/1467-8659.00669.
  10. Ohbuchi R, Nakazawa M, Takei T. Retrieving 3D shapes based on their appearance. In Book: 2003 5th ACM SIGMM International Workshop on Multimedia Information Retrieval, ACM, 2003 Berkeley, California, USA; 39-45. DOI: 10.1145/973264.973272.
  11. Papadakis P, Pratikakis I, Theoharis T, Perantonis S. Panorama: A 3D shape descriptor based on panoramic views for unsupervised 3D object retrieval. Int J Comput Vis 2010; 89(2-3): 177-192. DOI: 10.1007/s11263-009-0281-6.
  12. Osada R, Funkhouser T, Chazelle B, Dobkin D. Shape distributions. ACM Transactions on Graphics 2002; 21(4): 807-832. DOI: 10.1145/571647.571648.
  13. Zaharia T, Preteux FJ. 3D-shape-based retrieval within the MPEG-7 framework. Nonlinear Image Processing and Pattern Analysis 2001: 133-145. DOI: 10.1117/12.424969.
  14. Koenderink JJ, van Doorn AJ. Surface shape and curvature scales. Image and Vision Computing 1992; 10(8): 557-564. DOI: 10.1016/0262-8856(92)90076-F.
  15. Akgül CB, Sankur B, Yemez Y, Schmitt F. Density-based 3D shape descriptors. Eurasip Journal on Advances in Signal Processing 2007. DOI: 10.1155/2007/32503.
  16. Funkhouser T, Min P, Kazhdan M, et al. A search engine for 3D models. ACM Transactions on Graphics 2003; 22(1): 83-105. DOI: 10.1145/588272.588279.
  17. Cook WD, Kress M. A data envelopment model for aggregating preference rankings. Management Science 1990; 36(11): 1302-1310. DOI: 10.1287/mnsc.36.11.1302.
  18. Bouksim M, Arhid K, Zakani FR, Aboulfatah M, Gadi T. New approach for 3D Mesh Retrieval using artificial neural network and histogram of features. Scientific Visualization 2018; 10(2): 84-94. DOI: 10.26583/sv.10.2.07.
  19. Suzuki MT, Yaginuma Y, Yamada T, Shimizu Y. A partial shape matching method for 3D model databases. Software Engineering and Applications 2005. Source: < http://www.actapress.com/Abstract.aspx?paperId=23894 >.
  20. Biasotti S, Marini S, Spagnuolo M, Falcidieno B. Sub-part correspondence by structural descriptors of 3D shapes. CAD Computer Aided Design 2006; 38(9): 1002-1019. DOI: 10.1016/j.cad.2006.07.003.
  21. Moumoun L, Chahhou M, El Far M, Haqiq A, Gadi T. 3D object retrieval using a global-partial analogy and the bayesian approach. In Book: 2011 Seventh International Conference on Signal Image Technology {&} Internet-Based Systems, IEEE, 2011, Dijon, France; 314-321. DOI: 10.1109/SITIS.2011.60.
  22. Shapira L, Shamir A, Cohen-Or D. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 2008; 24(4): 249-259. DOI: 10.1007/s00371-007-0197-5.
  23. Rafii Zakani F, Arhid K, Bouksim M, Aboulfatah M, Gadi T. A new evaluation method for mesh segmentation based on the levenshtein distance. International Review on Computers and Software (IRECOS) 2016; 11(12). DOI: 10.15866/irecos.v11i12.10922.
  24. Rafii Zakani F, Arhid K, Bouksim M, Gadi T, Aboulfatah M. Kulczynski similarity index for objective evaluation of mesh segmentation algorithms. In Book: 2016 5th International Conference on Multimedia Computing and Systems (ICMCS), IEEE, 2016, Marrakech Morocco; 12-17. DOI: 10.1109/ICMCS.2016.7905611.
  25. Rafii Zakani F, Arhid K, Bouksim M, Aboulfatah M, Gadi T. New measure for objective evaluation of mesh segmentation algorithms. In Book: 2016 4th IEEE International Colloquium on Information Science and Technology (CiSt), IEEE, 2016, Tanger Morocco; 416-421. DOI: 10.1109/CIST.2016.7805083.
  26. Bouksim M, Zakani FR, Arhid K, Gadi T, Aboulfatah M. Evaluation of 3D mesh segmentation using a weighted version of the Ochiai index. In Book: 2016 IEEE/ACS 13th International Conference of Computer Systems and Applications (AICCSA), IEEE, 2016, Agadir Morocco; 1-7. DOI: 10.1109/AICCSA.2016.7945640.
  27. Arhid K, Bouksim M, Rafii Zakani F, Gadi T, Aboulfatah M. An objective 3D mesh segmentation evaluation using Sokal-Sneath metric. In Book: 2016 5th International Conference on Multimedia Computing and Systems (ICMCS) 2016: 29-34. DOI: 10.1109/ICMCS.2016.7905609.
  28. Bouksim M, Rafii Zakani F, Arhid K, Aboulfatah M, Gadi T. New evaluation method for 3D mesh segmentation. In Book: 2016 4th IEEE International Colloquium on Information Science and Technology (CiSt), IEEE, 2016, Tanger Morocco; 438-443. DOI: 10.1109/CIST.2016.7805087.
  29. Liu Z, Tang S, Bu S, Zhang H. New evaluation metrics for mesh segmentation. Computers and Graphics 2013; 37(6): 553-564. DOI: 10.1016/j.cag.2013.05.021.
  30. Zakani FR, Bouksim M, Arhid K, Aboulfatah M, Gadi T. Segmentation of 3D meshes combining the artificial neural network classifier and the spectral clustering. Computer Optics 2018; 42(2): 312-319. DOI: 10.18287/2412-6179-2018-42-2-312-319.
  31. Golovinskiy A, Funkhouser T. Randomized cuts for 3D mesh analysis. ACM Transactions on Graphics 2008; 27(5): 1. DOI: 10.1145/1409060.1409098.
  32. Attene M, Falcidieno B, Spagnuolo M. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 2006; 22(3): 181-193. DOI: 10.1007/s00371-006-0375-x.
  33. Shymon Shlafman, Ayellet Tal SK, Shlafman S, Tal A, Katz S. Metamorphosis of polyhedral surfaces using decomposition. Computer Graphics Forum 2002; 21: 219-228. DOI: 10.1111/1467-8659.00581.
  34. Arhid K, Rafii Zakani F, Mohcine B, Aboulfatah M, Gadi T. An efficient hierarchical 3D Mesh Segmentation using negative curvature and dihedral angle. International Journal of Intelligent Engineering and Systems 2017; 10(5): 143-152. DOI: 10.22266/ijies2017.1031.16.
  35. Shilane P, Min P, Kazhdan M, Funkhouser T, Street O. The Princeton shape benchmark. SMI '04 Proc Shape Modeling International 2004: 167-178.
  36. Li B, Godil A, Aono M, Bai X, Furuya T, Li L, López-Sastre R, Johan H, Ohbuchi R, Redondo-Cabrera C, Tatsuma A, Yanagimachi T, Zhang S. SHREC’12 Track : Generic 3D shape retrieval. Proc 5th Eurographics conference on 3D Object Retrieval 2012: 119-126. DOI: 10.2312/3DOR/3DOR12/119-126.
  37. Fang R, Godil A, Li X, Wagan A. A new shape benchmark for 3D object retrieval. In Book: Bebis G, Boyle R, Parvin B, Koracin D, Remagnino P, Porikli F, Peters J, Klosowski J, Arns L, Chun YK, Rhyne T-M, Monroe L, eds. Advances in visual computing. Berlin, Heidelberg: Springer-Verlag; 2008: 381-392. DOI: 10.1007/978-3-540-89639-5_37.
  38. Chen X, Golovinskiy A, Funkhouser T. A benchmark for 3D mesh segmentation. ACM Transactions on Graphics 2009; 28(3): 73. DOI: 10.1145/1531326.1531379.
  39. Giorgi D, Biasotti S, Paraboschi L, Imati CNR. SHape REtrieval Contest 2007 : Watertight models track. 2007. Source: < https://pdfs.semanticscholar.org/2b5b/b396160d11da2bc842b58045704cab70aa8c.pdf >.
© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846)332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20