This study presents a new local feature matching approach that relies upon Reeb graph (RG)-based representation as well as a simple and accurate similarity estimation. The central contribution of this work is to reinforce the topological consistency conditions of the graph-based description. Formally, the RGs are enriched with geometry signatures based on parameterisation approaches. After RG construction, the shape is segmented into Reeb charts of controlled topology mapped to its canonical planar domain. Then, two stretching signatures, corresponding to the area and angle distortion, are determined and taken as three-dimensional-shape descriptor. The similarity estimation is performed in two steps. The first one consists in forming the pairs of similar Reeb charts, according to the minimal distance between their corresponding signatures. The second step is to measure the global similarity which quantifies the similitude degree between all the matched Reeb charts. Retrieval experiments conducted on four publicly available databases have shown that the proposed matching scheme yields satisfactory results. Among observations, it can be noticed that despite its rapidity, the method provides an overall retrieval efficiency gain compared to very recent state-of-the-art methods.

References

1. 1)
  - 34. Floater, M.S., Hormann, K.: ‘Parameterization of triangulations and unorganized points’. Tutorials on Multiresolution in Geometric Modelling, 2002, pp. 287–316.
2. 2)
  - 39. Ohbuchi, R., Osada, K., Furuya, T., Banno, T.: ‘Salient local visual features for shape-based 3D model retrieval’. Proc. of Shape Modeling Int., 2008, pp. 93–102.
3. 3)
  - 2. Osada, R., Funkhouser, T., Chazelle, B., Dobkin, A.: ‘Shape distributions’, ACM Trans. Graph. (TOG), 2002, 21, (4), pp. 807–832 (doi: 10.1145/571647.571648).
4. 4)
  - 13. Bronstein, A.M., Bronstein, M.M., Kimmel, R.: ‘A Gromov-Hausdorff framework with diffusion geometry for topologically-robust nonrigid shape matching’, Int. J. Comput. Vis., 2009, 89, (2–3), pp. 266–286 (doi: 10.1007/s11263-009-0301-6).
5. 5)
  - 31. Ni, X., Garland, M., Hart, J.: ‘Fair Morse functions for extracting the topological structure of a surface mesh’, ACM Trans. Graph., 2004, 23, pp. 613–622 (doi: 10.1145/1015706.1015769).
6. 6)
  - 38. Agathos, A., Pratikakis, I., Papadakis, P., Perantonis, S., Azariadis, P., Sapidis, N.: ‘Retrieval of 3D articulated objects using a graph-based representation’. Eurographics Workshop on Shape Retrieval, 2009, pp. 1–8.
7. 7)
  - 8. Hilaga, M., Shinagawa, Y., Kohmura, T., Kuni, T.L.: ‘Topology matching for fully automatic similarity estimation of 3D shapes’. ACM SIGGRAPH, 2001, pp. 203–212.
8. 8)
  - 18. Li, B., Godil, A., Aono, M., et al: ‘SHREC'12 track: generic 3D shape retrieval’. Eurographics Workshop on 3D Object Retrieval, 2012, pp. 119–126.
9. 9)
  - 22. Tung, T., Schmitt, F.: ‘SHREC'08 entry: shape retrieval of noisy watertight models using aMRG’. IEEE Int. Conf. on Shape Modeling and Applications, 2008, pp. 229–230.
10. 10)
  - 1. Tangelder, J.W., Veltkamp, R.C.: ‘A survey of content based 3D shape retrieval methods’, J. Multimedia Tools Appl., 2008, 39, (3), pp. 441–471 (doi: 10.1007/s11042-007-0181-0).
11. 11)
  - 12. Jain, V., Zhang, H.: ‘A spectral approach to shape-based retrieval of articulated 3D models’, Comput. Aided Des., 2007, 39, (5), pp. 398–407 (doi: 10.1016/j.cad.2007.02.009).
12. 12)
  - 33. Floater, M.S., Hormann, K.: ‘Surface parameterization: a tutorial and survey’. Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, 2005, pp. 157–186.
13. 13)
  - 26. Reeb, G.: ‘Sur les points singuliers d'une forme de Pfaff complétement intégrable ou d'une fonction numérique’, Comptes Rendus Acad. Sci., 1946, 222, pp. 847–849.
14. 14)
  - 14. Sun, J., Chen, X., Funkhouser, T.: ‘Fuzzy geodesics and consistent sparse correspondences for deformable shapes’, J. Comput. Graph. Forum, 2010, 29, (5), pp. 1535–1544 (doi: 10.1111/j.1467-8659.2010.01762.x).
15. 15)
  - 36. Shilane, P., Min, P., Kazhdan, M., Funkhouser, T.: ‘The Princeton shape benchmark’. Proc. Shape Modeling Int. (SMI'04), 2004, pp. 167–178.
16. 16)
  - 19. Tung, T., Schmitt, F.: ‘The augmented multiresolution Reeb graph approach for content-based retrieval of 3D shapes’, Int. J. Shape Model. (IJSM), 2005, 11, (1), pp. 91–120 (doi: 10.1142/S0218654305000748).
17. 17)
  - 27. Tierny, J., Vandeborre, J.P., Daoudi, M.: ‘Invariant high level Reeb graphs of 3D polygonal meshes’. Third Int. Symp. on 3D Data Processing, Visualization, and Transmission, 2006, pp. 105–112.
18. 18)
  - 32. Tierny, J., Vandeborre, J.P., Daoudi, M.: ‘Enhancing 3D mesh topological skeletons with discrete contour constrictions’, Vis. Comput., 2008, 24, pp. 155–172 (doi: 10.1007/s00371-007-0181-0).
19. 19)
  - 25. El Khoury, R., Vandeborre, J.P., Daoudi, M.: ‘Indexed heat curves for 3D-model retrieval’. Int. Conf. on Pattern Recognition, Tsukuba, Japon, 2012, pp. 1964–1967.
20. 20)
  - 4. Dutagaci, H., Cheung, C.P., Godil, A.: ‘Evaluation of 3D interest point detection techniques via human-generated ground truth’, J. Vis. Comput., 2012, 28, (9), pp. 901–917 (doi: 10.1007/s00371-012-0746-4).
21. 21)
  - 5. Chen, D., Tian, X., Shen, Y., Ouhyoung, M.: ‘On visual similarity based 3D model retrieval’, Comput. Graph. Forum, 2003, 22, (3), pp. 223–232 (doi: 10.1111/1467-8659.00669).
22. 22)
  - 9. Biasotti, S., Marini, S., Spagnuolo, M., Falcidieno, B.: ‘Sub-part correspondence by structural descriptors of 3D shapes’, Comput. Aided Des., 2006, 38, (9), pp. 1002–1019 (doi: 10.1016/j.cad.2006.07.003).
23. 23)
  - 10. Dey, T.K., Jian, S.: ‘Defining and computing curve skeletons with medial geodesic function’. Eurographics Symp. on Geometry Processing, 2006, pp. 143–152.
24. 24)
  - 35. Wang, S., Wang, Y., Jin, M., Gu, X., Samaras, D.: ‘3D surface matching and recognition using conformal geometry’. IEEE Conf. in Computer Vision and Pattern Recognition, 2006, pp. 2453–2460.
25. 25)
  - 20. Biasotti, S., Giorgi, D., Spagnuolo, M., Falcidieno, B.: ‘Reeb graphs for shape analysis and application’, Theor. Comput. Sci., 2008, 392, pp. 5–22 (doi: 10.1016/j.tcs.2007.10.018).
26. 26)
  - 3. Lian, Z., Godil, A., Bustos, B., et al: ‘A comparison of methods for non-rigid 3D shape retrieval’, Pattern Recognit. J., 2013, 46, (1), pp. 449–461 (doi: 10.1016/j.patcog.2012.07.014).
27. 27)
  - 20. Lowe, D.G.: ‘Distinctive image features from scale-invariant keypoints’, Int. J. Comput. Vis., 2004, 60, pp. 91–110 (doi: 10.1023/B:VISI.0000029664.99615.94).
28. 28)
  - 24. Tam, G.K.L., Lau, R.W.H.: ‘Deformable model retrieval based on topological and geometric signatures’, IEEE Trans. Vis. Comput. Graph., 2007, 13, pp. 470–482 (doi: 10.1109/TVCG.2007.1011).
29. 29)
  - 11. Reuter, M., Biasotti, S., Giorgi, D., Patané, G., Spagnuolo, M.: ‘Discrete Laplace-Beltrami operators for shape analysis and segmentation’, Comput. Graph., 2009, 33, (3), pp. 381–390 (doi: 10.1016/j.cag.2009.03.005).
30. 30)
  - 28. Biasotti, S., Marini, S., Mortara, M., Patané, G., Spagnuolo, M., Falcidieno, B.: ‘3D Shape matching through topological structures’. Discrete Geometry for Computer Imagery, Berlin Heidelberg, 2003 (LNCS, 2886), pp. 194–203.
31. 31)
  - 30. Kanai, T., Suzuki, H.: ‘Approximate shortest path on polyhedral surface based on selective refinement of the discrete graph and its applications’. IEEE Proc. Geometric Modeling and Processing, 2000, pp. 241–250.
32. 32)
  - 29. Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: ‘The discrete geodeic problem’, SIAM J. Comput., 1987, 16, pp. 647–667 (doi: 10.1137/0216045).
33. 33)
  - 23. Tierny, J., Vandeborre, J.P., Daoudi, M.: ‘Reeb chart unfolding based 3D shape signatures’ (Eurographics, 2007), pp. 13–16.
34. 34)
  - 15. Smeets, D., Fabry, T., Hermans, J., Vandermeulen, D., Suetens, P.: ‘Inelastic deformation invariant modal representation for non-rigid 3D object recognition’. Int. Conf. on Articulated Motion and Deformable Objects, AMDO, 2010, pp. 162–171.
35. 35)
  - 21. Tierny, J., Vandeborre, J.P., Daoudi, M.: ‘Partial 3D shape retrieval by Reeb pattern unfolding’, Comput. Graph. Forum – Eurograph. Assoc., 2009, 28, (1), pp. 41–55 (doi: 10.1111/j.1467-8659.2008.01190.x).
36. 36)
  - 17. Furuya, T., Ohbuchi, R.: ‘Dense sampling and fast encoding for 3D model retrieval using bag-of-visual features’. Proc. of the ACM Int. Conf. on Image and Video Retrieval, 2009.
37. 37)
  - 6. Ohbuchi, R., Minamitani, T., Takei, T.: ‘Shape similarity search of 3D models by using enhanced shape functions’. Theory and Practice of Computer Graphics, 2003, pp. 97–104.
38. 38)
  - 7. Daoudi, M., Filali Ansary, T., Tierny, J., Vandeborre, J.P.: ‘3D-mesh models: view-based indexing and structural analysis’. DELOS Conf., 2007, pp. 298–307.
39. 39)
  - 16. Lavoué, G.: ‘Bag of words and local spectral descriptor for 3D partial shape retrieval’. Eurographics Workshop on 3D Object Retrieval, May 2011.

Global three-dimensional-mesh indexing based on structural analysis and geometrical signatures

References

Related content