Reeb graph based segmentation of articulated components of 3D digital objects. (English) Zbl 1338.68264
Summary: Segmentation of the articulated components of digital objects by a fast and efficient algorithm is presented in this paper. Given a 3D object in the form of a triangulated mesh, the approach involves representation of the mesh in a topological space and relating quotient spaces, containing the topologically invariant sections of the object, to weighted Reeb graphs along each of \(yz\)-, \(zx\)-, and \(xy\)-planes. It is followed by segmentation of the Reeb graphs where the concept of exponential averaging for dynamic thresholding ensures natural segmentation with a relatively high degree of accuracy. The segmented quotient spaces corresponding to the three Reeb graphs are subsequently related to each other and transformed topologically to report the segmented object in an appropriate topological space. The segmentation is carried out in a framework of 3D grid so as to exploit the topological relation between the triangulated object and its tight isothetic cover, and hence involves efficient computation and storage. The accuracy of segmentation at different grid resolutions, its robustness w.r.t. rotation, and pose-invariance for a reasonable range of postures are demonstrated by experimental results on a variety of objects.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Katz, S.; Leifman, G.; Tal, A., Mesh segmentation using feature point and core extraction, Vis. Comput., 21, 649-658 (2005) |
| [2] | Golovinskiy, A.; Funkhouser, T., Randomized cuts for 3D mesh analysis, ACM Trans. Graph., 27, 5, 145:1-145:12 (2008) |
| [3] | de Goes, F.; Goldstein, S.; Velho, L., A hierarchical segmentation of articulated bodies, (Proceedings of the Symposium on Geometry Processing. Proceedings of the Symposium on Geometry Processing, SGP ’08 (2008), Eurographics Association), 1349-1356 |
| [4] | Mangan, A.; Whitaker, R., Partitioning 3D surface meshes using watershed segmentation, IEEE Trans. Vis. Comput. Graph., 5, 308-321 (1999) |
| [5] | Cohen-Or, D.; Shamir, A.; Shapira, L., Consistent mesh partitioning and skeletonization using the shape diameter function, Vis. Comput., 24, 249-259 (2008) |
| [6] | Golovinskiy, A.; Funkhouser, T., Technical section: consistent segmentation of 3D models, Comput. Graph., 33, 3, 262-269 (2009) |
| [7] | Ghosh, S.; Loper, M.; Sudderth, E. B.; Black, M. J., From deformations to parts: motion-based segmentation of 3D objects, (Pereira, F.; Burges, C.; Bottou, L.; Weinberger, K., Advances in Neural Information Processing Systems (2012), Curran Associates, Inc.), 2006-2014 |
| [8] | Huang, Q.; Koltun, V.; Guibas, L., Joint shape segmentation with linear programming, ACM Trans. Graph., 30, 6, 125:1-125:12 (2011) |
| [9] | Dupas, A.; Damiand, G., First results for 3D image segmentation with topological map, (Coeurjolly, D.; Sivignon, I.; Tougne, L.; Dupont, F., Proceedings of the 14th IAPR International Conference on Discrete Geometry for Computer Imagery. Proceedings of the 14th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI’08, Lyon, France. Proceedings of the 14th IAPR International Conference on Discrete Geometry for Computer Imagery. Proceedings of the 14th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI’08, Lyon, France, LNCS, vol. 4992 (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 507-518 · Zbl 1138.68573 |
| [10] | Tierny, J.; Vandeborre, J.-P.; Daoudi, M., Topology driven 3D mesh hierarchical segmentation, (Proceedings of the IEEE International Conference on Shape Modeling and Applications. Proceedings of the IEEE International Conference on Shape Modeling and Applications, SMI ’07, Lyon, France (2007), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 215-220 |
| [11] | Lai, Y.-K.; Hu, S.-M.; Martin, R. R.; Rosin, P. L., Rapid and effective segmentation of 3D models using random walks, Comput. Aided Geom. Design, 26, 6, 665-679 (2009) · Zbl 1205.65090 |
| [12] | Dorninger, P.; Nothegger, C., 3D segmentation of unstructured point clouds for building modelling, (Stilla, U.; Mayer, H.; Rottensteiner, F.; Heipke, C.; Hinz, S., Photogrammetric Image Analysis, vol. 35. Photogrammetric Image Analysis, vol. 35, PIA’07, Munich, Germany (2007), ISPRS), 191-196 |
| [13] | Douillard, B.; Underwood, J.; Kuntz, N.; Vlaskine, V.; Quadros, A.; Morton, P.; Frenkel, A., On the segmentation of 3D LIDAR point clouds, (IEEE International Conference on Robotics and Automation. IEEE International Conference on Robotics and Automation, ICRA, Shanghai, China (2011)), 2798-2805 |
| [14] | Campbell, N. D.F.; Vogiatzis, G.; Hernández, C.; Cipolla, R., Automatic 3D object segmentation in multiple views using volumetric graph-cuts, Image Vis. Comput., 28, 1, 14-25 (2010) |
| [15] | Campbell, N. D.F.; Vogiatzis, G.; Hernández, C.; Cipolla, R., Automatic 3D object segmentation in multiple views using volumetric graph-cuts, (British Machine Vision Conference, vol. 1. British Machine Vision Conference, vol. 1, Warwick, UK (2007)), 530-539 |
| [16] | Kohli, P.; Rihan, J.; Bray, M.; Torr, P. H., Simultaneous segmentation and pose estimation of humans using dynamic graph cuts, Int. J. Comput. Vis., 79, 3, 285-298 (2008) |
| [17] | Bray, M.; Kohli, P.; Torr, P. H.S., PoseCut: simultaneous segmentation and 3D pose estimation of humans using dynamic graph-cuts, (Leonardis, A.; Bischof, H.; Pinz, A., Computer Vision. Computer Vision, ECCV 2006, Graz, Austria. Computer Vision. Computer Vision, ECCV 2006, Graz, Austria, LNCS, vol. 3952 (2006), Springer: Springer Berlin, Heidelberg), 642-655 |
| [18] | Attene, M.; Katz, S.; Mortara, M.; Patane, G.; Spagnuolo, M.; Tal, A., Mesh segmentation - a comparative study, (Proceedings of the IEEE International Conference on Shape Modeling and Applications. Proceedings of the IEEE International Conference on Shape Modeling and Applications, SMI ’06, Matsushima, Japan (2006), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 7-18 |
| [19] | Chen, X.; Golovinskiy, A.; Funkhouser, T., A benchmark for 3D mesh segmentation, ACM Trans. Graph., 28, 3, 73:1-73:12 (2009) |
| [20] | Dupas, A.; Damiand, G.; Lachaud, J.-O., Multi-label simple points definition for 3D images digital deformable model, (Brlek, S.; Reutenauer, C.; Proveņcal, X., Proceedings of the 15th IAPR International Conference on Discrete Geometry for Computer Imagery. Proceedings of the 15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI’09, Montreal, Canada. Proceedings of the 15th IAPR International Conference on Discrete Geometry for Computer Imagery. Proceedings of the 15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI’09, Montreal, Canada, LNCS, vol. 5810 (2009), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 156-167 · Zbl 1261.68151 |
| [21] | Zhu, N.; Chung, A. C.S., Graph-based optimization with tubularity Markov tree for 3D vessel segmentation, (Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR’13 (2013), IEEE Computer Society: IEEE Computer Society Portland, USA), 2219-2226 |
| [22] | Benhabiles, H.; Vandeborre, J.-P.; Lavoué, G.; Daoudi, M., A comparative study of existing metrics for 3D-mesh segmentation evaluation, Vis. Comput., 26, 12, 1451-1466 (2010) |
| [23] | Pizer, S. M.; Fletcher, P. T.; Joshi, S.; Thall, A.; Chen, J. Z.; Fridman, Y.; Fritsch, D. S.; Gash, A. G.; Glotzer, J. M.; Jiroutek, M. R.; Lu, C.; Muller, K. E.; Tracton, G.; Yushkevich, P.; Chaney, E. L., Deformable M-reps for 3D medical image segmentation, Int. J. Comput. Vis., 55, 2-3, 85-106 (2003) |
| [24] | Yang, X.; Schuster, D.; Master, V.; Nieh, P.; Fenster, A.; Fei, B., Automatic 3D segmentation of ultrasound images using atlas registration and statistical texture prior, (Wong, K. H.; Holmes, D. R., Medical Imaging 2011: Visualization, Image Guided Procedures, and Modeling. Medical Imaging 2011: Visualization, Image Guided Procedures, and Modeling, Proc. SPIE, vol. 7964 (2011)), Article 796432 pp. |
| [25] | Chazelle, B.; Dobkin, D.; Shourhura, N.; Tal, A., Strategies for polyhedral surface decomposition: an experimental study, Comput. Geom., 7, 327-342 (1997) · Zbl 1133.52305 |
| [26] | Zhang, X.; Ren, Z.; Rajan, D.; Hu, Y., Salient object detection through over-segmentation, (Proceedings of the IEEE International Conference on Multimedia and Expo. Proceedings of the IEEE International Conference on Multimedia and Expo, ICME ’12, Melbourne, Australia (2012), IEEE Computer Society), 1033-1038 |
| [27] | Karmakar, N.; Bhowmick, P.; Biswas, A., Segmentation of 3D articulated components by slice-based vertex-weighted Reeb graph, (Barcucci, E.; Frosini, A.; Rinaldi, S., Proceedings of the 18th International Conference on Discrete Geometry for Computer Imagery. Proceedings of the 18th International Conference on Discrete Geometry for Computer Imagery, DGCI’14, Siena, Italy, Europe. Proceedings of the 18th International Conference on Discrete Geometry for Computer Imagery. Proceedings of the 18th International Conference on Discrete Geometry for Computer Imagery, DGCI’14, Siena, Italy, Europe, LNCS, vol. 8668 (2014), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 370-383 · Zbl 1417.68264 |
| [28] | Karmakar, N.; Biswas, A.; Bhowmick, P.; Bhattacharya, B. B., Construction of 3D orthogonal cover of a digital object, (Aggarwal, J. K.; Barneva, R. P.; Brimkov, V. E.; Koroutchev, K.; Korutcheva, E., Proceedings of the 14th International Workshop on Combinatorial Image Analysis. Proceedings of the 14th International Workshop on Combinatorial Image Analysis, IWCIA’11, Madrid, Spain. Proceedings of the 14th International Workshop on Combinatorial Image Analysis. Proceedings of the 14th International Workshop on Combinatorial Image Analysis, IWCIA’11, Madrid, Spain, LNCS, vol. 6636 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 70-83 · Zbl 1330.68305 |
| [29] | Karmakar, N.; Biswas, A.; Bhowmick, P.; Bhattacharya, B. B., A combinatorial algorithm to construct 3D isothetic covers, Int. J. Comput. Math., 90, 8, 1571-1606 (2013) · Zbl 1276.68160 |
| [30] | Karmakar, N.; Biswas, A.; Bhowmick, P., Fast slicing of orthogonal covers using DCEL, (Barneva, R. P.; Brimkov, V. E.; Aggarwal, J. K., Proceedings of the 15th International Workshop on Combinatorial Image Analysis. Proceedings of the 15th International Workshop on Combinatorial Image Analysis, IWCIA’12, Austin, Texas, USA. Proceedings of the 15th International Workshop on Combinatorial Image Analysis. Proceedings of the 15th International Workshop on Combinatorial Image Analysis, IWCIA’12, Austin, Texas, USA, LNCS, vol. 7655 (2012), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 16-30 · Zbl 1377.68284 |
| [31] | Nurre, J. H., Locating landmarks on human body scan data, (Proc. Intl. Conf. on Recent Advances in 3D Digital Imaging and Modeling. Proc. Intl. Conf. on Recent Advances in 3D Digital Imaging and Modeling, Ottawa, Canada (1997), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 289-295 |
| [32] | Xiao, Y.; Siebert, P.; Werghi, N., A discrete Reeb graph approach for the segmentation of human body scans, (Proc. 4th International Conference on 3-D Digital Imaging and Modeling. Proc. 4th International Conference on 3-D Digital Imaging and Modeling, Banff, Alberta, Canada (2003), IEEE), 378-385 |
| [33] | Xiao, Y.; Werghi, N.; Siebert, P., A topological approach for segmenting human body shape, (Proceedings of 12th International Conference on Image Analysis and Processing. Proceedings of 12th International Conference on Image Analysis and Processing, ICIAP 2003, Mantova, Italy (2003), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 82-87 |
| [34] | Xiao, Y.; Siebert, P.; Werghi, N., Topological segmentation of discrete human body shapes in various postures based on geodesic distance, (Proceedings of the Pattern Recognition, 17th International Conference on, vol. 3. Proceedings of the Pattern Recognition, 17th International Conference on, vol. 3, ICPR’04, Cambridge, England, UK (2004), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 131-135 |
| [35] | Ju, X.; Werghi, N.; Siebert, J. P., Automatic segmentation of 3D human body scans, (Proc. Int. Conf. on Computer Graphics and Imaging 2000. Proc. Int. Conf. on Computer Graphics and Imaging 2000, Las Vegas, USA (2000)), 239-244 |
| [36] | Berretti, S.; Bimbo, A. D.; Pala, P., 3D mesh decomposition using Reeb graphs, Image Vis. Comput., 27, 10, 1540-1554 (2009) |
| [37] | Agathos, A.; Pratikakis, I.; Papadakis, P.; Perantonis, S.; Azariadis, P.; Sapidis, N. S., 3D articulated object retrieval using a graph-based representation, Vis. Comput., 26, 10, 1301-1319 (2010) |
| [38] | Werghi, N., A robust approach for constructing a graph representation of articulated and tubular-like objects from 3D scattered data, Pattern Recogn. Lett., 27, 6, 643-651 (2006) |
| [39] | Mesh basics (2010) |
| [40] | Basic concepts (Fall 2010) |
| [41] | Munkres, J. R., Topology (2000), Prentice Hall: Prentice Hall Upper Saddle River, New Jersey, USA · Zbl 0951.54001 |
| [42] | Edelsbrunner, H.; Harer, J. L., Computational Topology (2009), American Mathematical Society: American Mathematical Society Providence, RI, USA · Zbl 1170.60001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
