Free-boundary conformal parameterization of point clouds. (English) Zbl 1483.65032
Summary: With the advancement in 3D scanning technology, there has been a surge of interest in the use of point clouds in science and engineering. To facilitate the computations and analyses of point clouds, prior works have considered parameterizing them onto some simple planar domains with a fixed boundary shape such as a unit circle or a rectangle. However, the geometry of the fixed shape may lead to some undesirable distortion in the parameterization. It is therefore more natural to consider free-boundary conformal parameterizations of point clouds, which minimize the local geometric distortion of the mapping without constraining the overall shape. In this work, we develop a free-boundary conformal parameterization method for disk-type point clouds, which involves a novel approximation scheme of the point cloud Laplacian with accumulated cotangent weights together with a special treatment at the boundary points. With the aid of the free-boundary conformal parameterization, high-quality point cloud meshing can be easily achieved. Furthermore, we show that using the idea of conformal welding in complex analysis, the point cloud conformal parameterization can be computed in a divide-and-conquer manner. Experimental results are presented to demonstrate the effectiveness of the proposed method.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52C26 | Circle packings and discrete conformal geometry |
| 68W10 | Parallel algorithms in computer science |
Keywords:
conformal parameterization; point cloud; free-boundary; Laplace-Beltrami operator; conformal weldingReferences:
| [1] | Rusu, R.B., Cousins, S.: 3D is here: point cloud library (PCL). In: Proceedings of the 2011 IEEE International Conference on Robotics and Automation, pp. 1-4 (2011) |
| [2] | Remondino, F., From point cloud to surface: the modeling and visualization problem, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., 34, 5, W10 (2003) |
| [3] | Mitra, N.J., Gelfand, N., Pottmann, H., Guibas, L.: Registration of point cloud data from a geometric optimization perspective. In: Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, pp. 22-31 (2004) |
| [4] | Schnabel, R.; Wahl, R.; Klein, R., Efficient ransac for point-cloud shape detection, Comput. Graph. Forum, 26, 214-226 (2007) |
| [5] | Collins, A.; Zomorodian, A.; Carlsson, G.; Guibas, LJ, A barcode shape descriptor for curve point cloud data, Comput. Graph., 28, 6, 881-894 (2004) |
| [6] | Shen, Y., Feng, C., Yang, Y., Tian, D.: Mining point cloud local structures by kernel correlation and graph pooling. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4548-4557 (2018) |
| [7] | Zhou, Y., Tuzel, O.: Voxelnet: End-to-end learning for point cloud based 3D object detection. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4490-4499 (2018) |
| [8] | Shi, S., Wang, X., Li, H.: PointRCNN: 3D object proposal generation and detection from point cloud. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-779 (2019) |
| [9] | Liu, Y., Fan, B., Xiang, S., Pan, C.: Relation-shape convolutional neural network for point cloud analysis. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8895-8904 (2019) |
| [10] | Zou, G.; Hu, J.; Gu, X.; Hua, J., Authalic parameterization of general surfaces using Lie advection, IEEE Trans. Vis. Comput. Graph., 17, 12, 2005-2014 (2011) |
| [11] | Zhao, X.; Su, Z.; Gu, XD; Kaufman, A.; Sun, J.; Gao, J.; Luo, F., Area-preservation mapping using optimal mass transport, IEEE Trans. Vis. Comput. Graph., 19, 12, 2838-2847 (2013) |
| [12] | Su, K.; Cui, L.; Qian, K.; Lei, N.; Zhang, J.; Zhang, M.; Gu, XD, Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation, Comput. Aided Geom. Des., 46, 76-91 (2016) · Zbl 1418.65036 |
| [13] | Pumarola, A., Sanchez-Riera, J., Choi, G. P. T., Sanfeliu, A., Moreno-Noguer, F.: 3DPeople: Modeling the geometry of dressed humans. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 2242-2251 (2019) |
| [14] | Giri, A.; Choi, GPT; Kumar, L., Open and closed anatomical surface description via hemispherical area-preserving map, Signal Process., 180, 107867 (2021) |
| [15] | Choi, GPT; Rycroft, CH, Density-equalizing maps for simply connected open surfaces, SIAM J. Imag. Sci., 11, 2, 1134-1178 (2018) · Zbl 1401.68347 |
| [16] | Choi, GPT; Chiu, B.; Rycroft, CH, Area-preserving mapping of 3D carotid ultrasound images using density-equalizing reference map, IEEE Trans. Biomed. Eng., 67, 9, 1507-1517 (2020) |
| [17] | Yueh, M-H; Lin, W-W; Wu, C-T; Yau, S-T, A novel stretch energy minimization algorithm for equiareal parameterizations, J. Sci. Comput., 78, 3, 1353-1386 (2019) · Zbl 1417.65112 |
| [18] | Pinkall, U.; Polthier, K., Computing discrete minimal surfaces and their conjugates, Exp. Math., 2, 1, 15-36 (1993) · Zbl 0799.53008 |
| [19] | Gu, X.; Wang, Y.; Chan, TF; Thompson, PM; Yau, S-T, Genus zero surface conformal mapping and its application to brain surface mapping, IEEE Trans. Med. Imaging, 23, 8, 949-958 (2004) |
| [20] | Lévy, B.; Petitjean, S.; Ray, N.; Maillot, J., Least squares conformal maps for automatic texture atlas generation, ACM Trans. Graph., 21, 3, 362-371 (2002) |
| [21] | Desbrun, M.; Meyer, M.; Alliez, P., Intrinsic parameterizations of surface meshes, Comput. Graph. Forum, 21, 209-218 (2002) |
| [22] | Sheffer, A.; de Sturler, E., Parameterization of faceted surfaces for meshing using angle-based flattening, Eng. Comput., 17, 3, 326-337 (2001) · Zbl 0983.68566 |
| [23] | Sheffer, A.; Lévy, B.; Mogilnitsky, M.; Bogomyakov, A., ABF++: fast and robust angle based flattening, ACM Trans. Graph., 24, 2, 311-330 (2005) |
| [24] | Luo, F., Combinatorial Yamabe flow on surfaces, Commun. Contemp. Math., 6, 5, 765-780 (2004) · Zbl 1075.53063 |
| [25] | Kharevych, L.; Springborn, B.; Schröder, P., Discrete conformal mappings via circle patterns, ACM Trans. Graph., 25, 2, 412-438 (2006) |
| [26] | Mullen, P.; Tong, Y.; Alliez, P.; Desbrun, M., Spectral conformal parameterization, Comput. Graph. Forum, 27, 1487-1494 (2008) |
| [27] | Marshall, DE; Rohde, S., Convergence of a variant of the zipper algorithm for conformal mapping, SIAM J. Numer. Anal., 45, 6, 2577-2609 (2007) · Zbl 1157.30006 |
| [28] | Jin, M.; Kim, J.; Luo, F.; Gu, X., Discrete surface Ricci flow, IEEE Trans. Vis. Comput. Graph., 14, 5, 1030-1043 (2008) |
| [29] | Yang, Y-L; Guo, R.; Luo, F.; Hu, S-M; Gu, X., Generalized discrete Ricci flow, Comput. Graph. Forum, 28, 2005-2014 (2009) |
| [30] | Sawhney, R.; Crane, K., Boundary first flattening, ACM Trans. Graph., 37, 1, 1-14 (2017) |
| [31] | Yueh, M-H; Lin, W-W; Wu, C-T; Yau, S-T, An efficient energy minimization for conformal parameterizations, J. Sci. Comput., 73, 1, 203-227 (2017) · Zbl 1380.65049 |
| [32] | Floater, MS; Hormann, K., Surface parameterization: a tutorial and survey, Advances in multiresolution for geometric modelling, 157-186 (2005), New York: Springer, New York · Zbl 1065.65030 |
| [33] | Sheffer, A.; Praun, E.; Rose, K., Mesh parameterization methods and their applications, Found. TrendsR Comput. Graph. Vis., 2, 2, 105-171 (2006) · Zbl 1112.68130 |
| [34] | Hormann, K., Lévy, B., Sheffer, A.: Mesh parameterization: Theory and practice. ACM SIGGRAPH 2007 courses (2007) |
| [35] | Choi, PT; Lam, KC; Lui, LM, FLASH: fast landmark aligned spherical harmonic parameterization for genus-0 closed brain surfaces, SIAM J. Imag. Sci., 8, 1, 67-94 (2015) · Zbl 1316.65028 |
| [36] | Choi, PT; Lui, LM, Fast disk conformal parameterization of simply-connected open surfaces, J. Sci. Comput., 65, 3, 1065-1090 (2015) · Zbl 1329.65050 |
| [37] | Choi, GPT; Chen, Y.; Lui, LM; Chiu, B., Conformal mapping of carotid vessel wall and plaque thickness measured from 3D ultrasound images, Med. Biol. Eng. Comput., 55, 12, 2183-2195 (2017) |
| [38] | Choi, GP-T; Lui, LM, A linear formulation for disk conformal parameterization of simply-connected open surfaces, Adv. Comput. Math., 44, 1, 87-114 (2018) · Zbl 1425.68431 |
| [39] | Choi, GPT; Leung-Liu, Y.; Gu, X.; Lui, LM, Parallelizable global conformal parameterization of simply-connected surfaces via partial welding, SIAM J. Imag. Sci., 13, 3, 1049-1083 (2020) · Zbl 1456.65014 |
| [40] | Choi, GPT, Efficient conformal parameterization of multiply-connected surfaces using quasi-conformal theory, J. Sci. Comput., 87, 3, 70 (2021) · Zbl 1465.65019 |
| [41] | Choi, GP-T; Man, MH-Y; Lui, LM, Fast spherical quasiconformal parameterization of genus-\(0\) closed surfaces with application to adaptive remeshing, Geom. Imag. Comput., 3, 1, 1-29 (2016) · Zbl 1396.65027 |
| [42] | Choi, CP; Gu, X.; Lui, LM, Subdivision connectivity remeshing via teichmüller extremal map, Inverse Probl. Imag., 11, 5, 825-855 (2017) · Zbl 1368.94008 |
| [43] | Lui, LM; Lam, KC; Yau, S-T; Gu, X., Teichmüller mapping (T-map) and its applications to landmark matching registration, SIAM J. Imag. Sci., 7, 1, 391-426 (2014) · Zbl 1296.65028 |
| [44] | Yung, CP; Choi, GPT; Chen, K.; Lui, LM, Efficient feature-based image registration by mapping sparsified surfaces, J. Vis. Commun. Image Repres., 55, 561-571 (2018) |
| [45] | Choi, GPT; Mahadevan, L., Planar morphometrics using Teichmüller maps, Proc. R. Soc. A, 474, 2217, 20170905 (2018) · Zbl 1407.92016 |
| [46] | Choi, GPT; Chan, HL; Yong, R.; Ranjitkar, S.; Brook, A.; Townsend, G.; Chen, K.; Lui, LM, Tooth morphometry using quasi-conformal theory, Pattern Recognit., 99, 107064 (2020) |
| [47] | Choi, GPT; Qiu, D.; Lui, LM, Shape analysis via inconsistent surface registration, Proc. R. Soc. A, 476, 2242, 20200147 (2020) · Zbl 1472.53108 |
| [48] | Choi, GPT; Dudte, LH; Mahadevan, L., Programming shape using kirigami tessellations, Nat. Mater., 18, 9, 999-1004 (2019) |
| [49] | Zwicker, M., Gotsman, C.: Meshing point clouds using spherical parameterization. In: Proceedings of the Eurographics Symposium on Point-Based Graphics, pp. 173-180 (2004) |
| [50] | Tewari, G.; Gotsman, C.; Gortler, SJ, Meshing genus-1 point clouds using discrete one-forms, Comput. Graph., 30, 6, 917-926 (2006) |
| [51] | Zhang, L.; Liu, L.; Gotsman, C.; Huang, H., Mesh reconstruction by meshless denoising and parameterization, Comput. Graph., 34, 3, 198-208 (2010) |
| [52] | Meng, Q.; Li, B.; Holstein, H.; Liu, Y., Parameterization of point-cloud freeform surfaces using adaptive sequential learning rbfnetworks, Pattern Recognit., 46, 8, 2361-2375 (2013) |
| [53] | Choi, GP-T; Ho, KT; Lui, LM, Spherical conformal parameterization of genus-0 point clouds for meshing, SIAM J. Imag. Sci., 9, 4, 1582-1618 (2016) · Zbl 1354.65034 |
| [54] | Meng, TW; Choi, GP-T; Lui, LM, TEMPO: Feature-endowed Teichmüller extremal mappings of point clouds, SIAM J. Imag. Sci., 9, 4, 1922-1962 (2016) · Zbl 1369.30046 |
| [55] | Sharp, N.; Crane, K., A Laplacian for nonmanifold triangle meshes, Comput. Graph. Forum, 39, 69-80 (2020) |
| [56] | Belkin, M.; Niyogi, P., Towards a theoretical foundation for Laplacian-based manifold methods, J. Comput. Syst. Sci., 74, 8, 1289-1308 (2008) · Zbl 1157.68056 |
| [57] | Belkin, M., Sun, J., Wang, Y.: Constructing Laplace operator from point clouds in \({\mathbb{R}}^d\). In: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pp. 1031-1040 (2009) · Zbl 07051273 |
| [58] | Wendland, H., Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Adv. Comput. Math., 4, 1, 389-396 (1995) · Zbl 0838.41014 |
| [59] | Liang, J., Lai, R., Wong, T.W., Zhao, H.: Geometric understanding of point clouds using Laplace-Beltrami operator. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 214-221 (2012) |
| [60] | Liang, J.; Zhao, H., Solving partial differential equations on point clouds, SIAM J. Sci. Comput., 35, 3, A1461-A1486 (2013) · Zbl 1275.65080 |
| [61] | Lai, R.; Liang, J.; Zhao, H-K, A local mesh method for solving PDEs on point clouds, Inverse Probl. Imag., 7, 3, 737-755 (2013) · Zbl 1273.65034 |
| [62] | Reuter, M.; Biasotti, S.; Giorgi, D.; Patanè, G.; Spagnuolo, M., Discrete Laplace-Beltrami operators for shape analysis and segmentation, Comput. Graph., 33, 3, 381-390 (2009) |
| [63] | Clarenz, U., Rumpf, M., Telea, A.: Finite elements on point-based surfaces. In: Proceedings of Symposium on Point-Based Graphics, pp. 201-211 (2004) |
| [64] | Cao, J., Tagliasacchi, A., Olson, M., Zhang, H., Su, Z.: Point cloud skeletons via Laplacian based contraction. In: Proceedings of the 2010 Shape Modeling International Conference, pp. 187-197 (2010) |
| [65] | The Stanford 3D scanning repository. http://graphics.stanford.edu/data/3Dscanrep/ |
| [66] | AIM@Shape shape repository. http://visionair.ge.imati.cnr.it/ontologies/shapes/ |
| [67] | Meng, T.; Lui, LM, PCBC: Quasiconformality of point cloud mappings, J. Sci. Comput., 77, 1, 597-633 (2018) · Zbl 06993434 |
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.
