Parallelizable global quasi-conformal parameterization of multiply connected surfaces via partial welding. (English) Zbl 1499.65068
Summary: Conformal and quasi-conformal mappings have widespread applications in imaging science, computer vision, and computer graphics and can be used in surface registration, segmentation, remeshing, and texture map compression. While various conformal and quasi-conformal parameterization methods for simply connected surfaces have been proposed, efficient parameterization algorithms for multiply connected surfaces have been less explored. In this paper, we propose a novel parallelizable algorithm for computing the global conformal and quasi-conformal parameterizations of multiply connected surfaces onto a 2D circular domain using variants of the partial welding method and the Koebe’s iteration. The main idea is to first partition a multiply connected surface into several subdomains and compute the free-boundary conformal and quasi-conformal parameterizations of them, respectively, and then apply a variant of the partial welding algorithm to reconstruct the global mapping. We apply the Koebe’s iteration, together with the geodesic algorithm, to the boundary points and welding paths before and after the global welding to transform all the boundaries into circles conformally. After getting all the updated boundary conditions, we obtain the global parameterization of the multiply connected surface by solving the Laplace equation for each subdomain. Using this divide-and-conquer approach, the global conformal and quasi-conformal parameterizations of surfaces can be efficiently computed. Experimental results are presented to demonstrate the effectiveness of our proposed algorithm. More broadly, the proposed shift in perspective from solving a global quasi-conformal mapping problem to solving multiple local mapping problems paves a new way for computational quasi-conformal geometry.
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 |
| 30C20 | Conformal mappings of special domains |
Keywords:
conformal parameterization; quasi-conformal parameterization; partial welding; multiply connected surface; Koebe’s iterationReferences:
| [1] | L. Ahlfors and L. Bers, Riemann’s mapping theorem for variable metrics, Ann. of Math. (2), 72 (1960), pp. 385-404. · Zbl 0104.29902 |
| [2] | D. An, X. Gu, and S.-T. Yau, Geometric variational framework for computing optimal transportation maps, Math. Comput. Geom. Data, 1 (2022), pp. 1-37. |
| [3] | S. Angenent, S. Haker, A. Tannenbaum, and R. Kikinis, On the Laplace-Beltrami operator and brain surface flattening, IEEE Trans. Med. Imaging, 18 (1999), pp. 700-711. |
| [4] | K. Astala, T. Iwaniec, and G. Martin, Elliptic Partial Differential Equations and Quasiconformal Mappings in the Plane, Princeton Math. Ser. 48, Princeton University Press, 2009. · Zbl 1182.30001 |
| [5] | A. I. Bobenko, S. Sechelmann, and B. Springborn, Discrete conformal maps: Boundary value problems, circle domains, Fuchsian and Schottky uniformization, in Advances in Discrete Differential Geometry, Springer, 2016, pp. 1-56. · Zbl 1354.30042 |
| [6] | E. Chien, Z. Levi, and O. Weber, Bounded distortion parametrization in the space of metrics, ACM Trans. Graphics, 35 (2016), pp. 1-16. |
| [7] | G. P. T. Choi, Efficient conformal parameterization of multiply-connected surfaces using quasi-conformal theory, J. Sci. Comput., 87 (2021), pp. 1-19. · Zbl 1465.65019 |
| [8] | G. P. T. Choi, H. L. Chan, R. Yong, S. Ranjitkar, A. Brook, G. Townsend, K. Chen, and L. M. Lui, Tooth morphometry using quasi-conformal theory, Pattern Recognition, 99 (2020), 107064. |
| [9] | G. P. T. Choi, B. Chiu, and C. H. Rycroft, Area-preserving mapping of \textup3D carotid ultrasound images using density-equalizing reference map, IEEE Trans. Biomed. Engrg., 67 (2020), pp. 1507-1517. |
| [10] | G. P.-T. Choi, K. T. Ho, and L. M. Lui, Spherical conformal parameterization of genus-0 point clouds for meshing, SIAM J. Imaging Sci., 9 (2016), pp. 1582-1618, https://doi.org/10.1137/15M1037561. · Zbl 1354.65034 |
| [11] | G. P. T. Choi, Y. Leung-Liu, X. Gu, and L. M. Lui, Parallelizable global conformal parameterization of simply-connected surfaces via partial welding, SIAM J. Imaging Sci., 13 (2020), pp. 1049-1083, https://doi.org/10.1137/19M125337X. · Zbl 1456.65014 |
| [12] | G. P. T. Choi, Y. Liu, and L. M. Lui, Free-boundary conformal parameterization of point clouds, J. Sci. Comput., 90 (2022), pp. 1-26. · Zbl 1483.65032 |
| [13] | G. P.-T. Choi and L. M. Lui, A linear formulation for disk conformal parameterization of simply-connected open surfaces, Adv. Comput. Math., 44 (2018), pp. 87-114. · Zbl 1425.68431 |
| [14] | G. P.-T. Choi, M. H.-Y. Man, and L. M. Lui, Fast spherical quasiconformal parameterization of genus-0 closed surfaces with application to adaptive remeshing, Geom. Imaging Comput., 3 (2016), pp. 1-29. · Zbl 1396.65027 |
| [15] | G. P. T. Choi, D. Qiu, and L. M. Lui, Shape analysis via inconsistent surface registration, Proc. Roy. Soc. A, 476 (2020), 20200147. · Zbl 1472.53108 |
| [16] | G. P. T. Choi and C. H. Rycroft, Density-equalizing maps for simply connected open surfaces, SIAM J. Imaging Sci., 11 (2018), pp. 1134-1178, https://doi.org/10.1137/17M1124796. · Zbl 1401.68347 |
| [17] | P. T. Choi, K. C. Lam, and L. M. Lui, FLASH: Fast landmark aligned spherical harmonic parameterization for genus-0 closed brain surfaces, SIAM J. Imaging Sci., 8 (2015), pp. 67-94, https://doi.org/10.1137/130950008. · Zbl 1316.65028 |
| [18] | P. T. Choi and L. M. Lui, Fast disk conformal parameterization of simply-connected open surfaces, J. Sci. Comput., 65 (2015), pp. 1065-1090. · Zbl 1329.65050 |
| [19] | D. Crowdy, The Schwarz-Christoffel mapping to bounded multiply connected polygonal domains, Proc. Roy. Soc. A, 461 (2005), pp. 2653-2678. · Zbl 1186.30005 |
| [20] | D. Crowdy, Schwarz-Christoffel mappings to unbounded multiply connected polygonal regions, Math. Proc. Cambridge Philos. Soc., 142 (2007), pp. 319-339. · Zbl 1111.30007 |
| [21] | D. Crowdy and J. Marshall, Conformal mappings between canonical multiply connected domains, Comput. Methods Funct. Theory, 6 (2006), pp. 59-76. · Zbl 1101.30010 |
| [22] | L. Cui, X. Qi, C. Wen, N. Lei, X. Li, M. Zhang, and X. Gu, Spherical optimal transportation, Comput.-Aided Des., 115 (2019), pp. 181-193. |
| [23] | M. Desbrun, M. Meyer, and P. Alliez, Intrinsic parameterizations of surface meshes, Comput. Graphics Forum, 21 (2002), pp. 209-218. |
| [24] | M. S. Floater and K. Hormann, Surface parameterization: A tutorial and survey, in Advances in Multiresolution for Geometric Modelling, Math. Vis., Springer, 2005, pp. 157-186. · Zbl 1065.65030 |
| [25] | J. J. Garcia-Luna-Aceves and S. Murthy, A path-finding algorithm for loop-free routing, IEEE/ACM Trans. Networking, 5 (1997), pp. 148-160. |
| [26] | F. P. Gardiner and N. Lakic, Quasiconformal Teichmüller Theory, Math. Surveys Monogr. 76, American Mathematical Society, 2000. · Zbl 0949.30002 |
| [27] | A. Giri, G. P. T. Choi, and L. Kumar, Open and closed anatomical surface description via hemispherical area-preserving map, Signal Process., 180 (2021), 107867. |
| [28] | D. Gu, RiemannMapper: A Mesh Parameterization Toolkit, https://www3.cs.stonybrook.edu/ gu/software/RiemannMapper/. |
| [29] | D. Gu, Stony Brook 3D Scanning Laboratory, https://www3.cs.stonybrook.edu/ gu/software/holoimage/index.html. |
| [30] | X. Gu, Y. Wang, T. F. Chan, P. M. Thompson, and S.-T. Yau, Genus zero surface conformal mapping and its application to brain surface mapping, IEEE Trans. Med. Imaging, 23 (2004), pp. 949-958. |
| [31] | X. Gu and S.-T. Yau, Global conformal surface parameterization, in Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 2003, pp. 127-137. |
| [32] | S. Haker, S. Angenent, A. Tannenbaum, R. Kikinis, G. Sapiro, and M. Halle, Conformal surface parameterization for texture mapping, IEEE Trans. Vis. Comput. Graphics, 6 (2000), pp. 181-189. |
| [33] | P. Henrici, Applied and Computational Complex Analysis, Vol. 3: Discrete Fourier Analysis-Cauchy Integrals-Construction of Conformal Maps-Univalent Functions, Wiley Classics, John Wiley & Sons, Inc., 1993. · Zbl 1107.30300 |
| [34] | K. T. Ho and L. M. Lui, QCMC: Quasi-conformal parameterizations for multiply-connected domains, Adv. Comput. Math., 42 (2016), pp. 279-312. · Zbl 1337.65017 |
| [35] | K. Hormann, B. Lévy, and A. Sheffer, Mesh parameterization: Theory and practice, in SIGGRAPH ’07: ACM SIGGRAPH 2007 Courses, ACM, New York, 2007. |
| [36] | J. E. Hutchinson, Computing conformal maps and minimal surfaces, in Workshop on Theoretical and Numerical Aspects of Geometric Variational Problems, Proceedings of the Workshop held in Canberra, September 24-28, 1990, G. Dziuk, G. Huisken, and J. Hutchinson, eds., Proc. Centre Math. Appl. Austral. Nat. Univ. 26, Australian National University, Centre for Mathematics and Its Applications, 1991, pp. 140-161. · Zbl 0737.53012 |
| [37] | M. Jin, J. Kim, F. Luo, and X. Gu, Discrete surface Ricci flow, IEEE Trans. Vis. Comput. Graphics, 14 (2008), pp. 1030-1043. |
| [38] | L. Kharevych, B. Springborn, and P. Schröder, Discrete conformal mappings via circle patterns, ACM Trans. Graphics, 25 (2006), pp. 412-438. |
| [39] | P. Koebe, Über die konforme Abbildung mehrfach zusammenhängender Bereiche, Jahresber. Deutsch. Math.-Verein., 19 (1910), pp. 339-348. · JFM 41.0747.07 |
| [40] | I. Koutis, G. L. Miller, and D. Tolliver, Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing, Comput. Vis. Image Understanding, 115 (2011), pp. 1638-1646. |
| [41] | E. Kropf, X. Yin, S.-T. Yau, and X. D. Gu, Conformal parameterization for multiply connected domains: Combining finite elements and complex analysis, Engrg. Comput., 30 (2014), pp. 441-455. |
| [42] | R. Kühnau, Numerische Realisierung konformer Abbildungen durch “Interpolation,” Z. Angew. Math. Mech., 63 (1983), pp. 631-637. · Zbl 0529.30010 |
| [43] | R. Lai, Z. Wen, W. Yin, X. Gu, and L. M. Lui, Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization, J. Sci. Comput., 58 (2014), pp. 705-725. · Zbl 1298.30007 |
| [44] | K. C. Lam and L. M. Lui, Landmark- and intensity-based registration with large deformations via quasi-conformal maps, SIAM J. Imaging Sci., 7 (2014), pp. 2364-2392, https://doi.org/10.1137/130943406. · Zbl 1309.65019 |
| [45] | J. Ławrynowicz and J. Krzyż, Quasiconformal Mappings in the Plane: Parametrical Methods, Lecture Notes in Math. 978, Springer, 1983. · Zbl 0503.30013 |
| [46] | O. Lehto and K. I. Virtanen, Quasiconformal Mappings in the Plane, 2nd ed., translated from the German by K. W. Lucas, Grundlehren Math. Wiss. 126, Springer-Verlag, 1973. · Zbl 0267.30016 |
| [47] | B. Lévy, S. Petitjean, N. Ray, and J. Maillot, Least squares conformal maps for automatic texture atlas generation, ACM Trans. Graphics, 21 (2002), pp. 362-371. |
| [48] | Y. Lipman, Bounded distortion mapping spaces for triangular meshes, ACM Trans. Graphics, 31 (2012), pp. 1-13. |
| [49] | L. M. Lui, K. C. Lam, T. W. Wong, and X. Gu, Texture map and video compression using Beltrami representation, SIAM J. Imaging Sci., 6 (2013), pp. 1880-1902, https://doi.org/10.1137/120866129. · Zbl 1281.65036 |
| [50] | L. M. Lui, K. C. Lam, S.-T. Yau, and X. Gu, Teichmüller mapping (T-map) and its applications to landmark matching registration, SIAM J. Imaging Sci.., 7 (2014), pp. 391-426, https://doi.org/10.1137/120900186. · Zbl 1296.65028 |
| [51] | L. M. Lui, T. W. Wong, W. Zeng, X. Gu, P. M. Thompson, T. F. Chan, and S.-T. Yau, Optimization of surface registrations using Beltrami holomorphic flow, J. Sci. Comput., 50 (2012), pp. 557-585. · Zbl 1244.65096 |
| [52] | F. Luo, Combinatorial Yamabe flow on surfaces, Commun. Contemp. Math., 6 (2004), pp. 765-780. · Zbl 1075.53063 |
| [53] | D. E. Marshall, Conformal welding for finitely connected regions, Comput. Methods Function Theory, 11 (2012), pp. 655-669. · Zbl 1252.30002 |
| [54] | D. E. Marshall and J. A. Morrow, Compositions of Slit Mappings, manuscript. |
| [55] | D. E. Marshall and S. Rohde, Convergence of a variant of the zipper algorithm for conformal mapping, SIAM J. Numer. Anal., 45 (2007), pp. 2577-2609, https://doi.org/10.1137/060659119. · Zbl 1157.30006 |
| [56] | T. W. Meng, G. P.-T. Choi, and L. M. Lui, TEMPO: Feature-endowed Teichm̈uller extremal mappings of point clouds, SIAM J. Imaging Sci., 9 (2016), pp. 1922-1962, https://doi.org/10.1137/15M1049117. · Zbl 1369.30046 |
| [57] | M. M. S. Nasser, PlgCirMap: A MATLAB toolbox for computing conformal mappings from polygonal multiply connected domains onto circular domains, SoftwareX, 11 (2020), 100464. |
| [58] | T. C. Ng, X. Gu, and L. M. Lui, Teichmüller extremal map of multiply-connected domains using Beltrami holomorphic flow, J. Sci. Comput., 60 (2014), pp. 249-275. · Zbl 1316.65036 |
| [59] | R. Peng and D. A. Spielman, An efficient parallel solver for SDD linear systems, in Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, 2014, pp. 333-342. · Zbl 1315.65028 |
| [60] | P.-O. Persson and G. Strang, A simple mesh generator in MATLAB, SIAM Rev., 46 (2004), pp. 329-345, https://doi.org/10.1137/S0036144503429121. · Zbl 1061.65134 |
| [61] | V. A. Pfluger, Ueber die Konstruktion Riemannscher Flächen durch Verheftung, J. Indian Math. Soc. (N.S.), 24 (1960), pp. 401-412. · Zbl 0112.05303 |
| [62] | U. Pinkall and K. Polthier, Computing discrete minimal surfaces and their conjugates, Exp. Math., 2 (1993), pp. 15-36. · Zbl 0799.53008 |
| [63] | D. Qiu, K.-C. Lam, and L.-M. Lui, Computing quasi-conformal folds, SIAM J. Imaging Sci., 12 (2019), pp. 1392-1424, https://doi.org/10.1137/18M1220042. |
| [64] | D. Qiu and L. M. Lui, Inconsistent surface registration via optimization of mapping distortions, J. Sci. Comput., 83 (2020), pp. 1-31. · Zbl 1435.65042 |
| [65] | R. Sawhney and K. Crane, Boundary first flattening, ACM Trans. Graphics, 37 (2017), pp. 1-14. |
| [66] | M. Shaqfa, G. P. T. Choi, and K. Beyer, Spherical cap harmonic analysis (SCHA) for characterising the morphology of rough surface patches, Powder Technology, 393 (2021), pp. 837-856. |
| [67] | E. Sharon and D. Mumford, 2D-shape analysis using conformal mapping, Int. J. Comput. Vis., 70 (2006), pp. 55-75. · Zbl 1477.68492 |
| [68] | A. Sheffer and E. de Sturler, Parameterization of faceted surfaces for meshing using angle-based flattening, Engrg. Comput., 17 (2001), pp. 326-337. · Zbl 0983.68566 |
| [69] | A. Sheffer, B. Lévy, M. Mogilnitsky, and A. Bogomyakov, ABF++: Fast and robust angle based flattening, ACM Trans. Graphics, 24 (2005), pp. 311-330. |
| [70] | A. Sheffer, E. Praun, and K. Rose, Mesh parameterization methods and their applications, Found. Trends Comput. Graphics Vis., 2 (2006), pp. 105-171. · Zbl 1112.68130 |
| [71] | Y. Wang, L. M. Lui, X. Gu, K. M. Hayashi, T. F. Chan, A. W. Toga, P. M. Thompson, and S.-T. Yau, Brain surface conformal parameterization using Riemann surface structure, IEEE Trans. Med. Imaging, 26 (2007), pp. 853-865. |
| [72] | O. Weber, A. Myles, and D. Zorin, Computing extremal quasiconformal maps, Comput. Graphics Forum, 31 (2012), pp. 1679-1689. |
| [73] | T. W. Wong and H.-k. Zhao, Computation of quasi-conformal surface maps using discrete Beltrami flow, SIAM J. Imaging Sci., 7 (2014), pp. 2675-2699, https://doi.org/10.1137/14097104X. · Zbl 1307.30050 |
| [74] | T. W. Wong and H.-K. Zhao, Computing surface uniformization using discrete Beltrami flow, SIAM J. Sci. Comput., 37 (2015), pp. A1342-A1364, https://doi.org/10.1137/130939183. · Zbl 1317.30064 |
| [75] | Y.-L. Yang, R. Guo, F. Luo, S.-M. Hu, and X. Gu, Generalized discrete Ricci flow, Comput. Graphics Forum, 28 (2009), pp. 2005-2014. |
| [76] | P. Yap, Grid-based path-finding, in Advances in Artificial Intelligence, Canadian AI 2002, Lecture Notes in Comput. Sci. 2338, R. Cohen and B. Spencer, eds., Springer, 2002, pp. 44-55. · Zbl 1048.68602 |
| [77] | M.-H. Yueh, W.-W. Lin, C.-T. Wu, and S.-T. Yau, An efficient energy minimization for conformal parameterizations, J. Sci. Comput., 73 (2017), pp. 203-227. · Zbl 1380.65049 |
| [78] | M.-H. Yueh, W.-W. Lin, C.-T. Wu, and S.-T. Yau, A novel stretch energy minimization algorithm for equiareal parameterizations, J. Sci. Comput., 78 (2019), pp. 1353-1386. · Zbl 1417.65112 |
| [79] | C. P. Yung, G. P. T. Choi, K. Chen, and L. M. Lui, Efficient feature-based image registration by mapping sparsified surfaces, J. Vis. Comm. Image Represent., 55 (2018), pp. 561-571. |
| [80] | R. Zayer, B. Lévy, and H.-P. Seidel, Linear angle based parameterization, in Proceedings of the Fifth Eurographics Symposium on Geometry Processing (SGP 2007), Eurographics Association, 2007, pp. 135-141. |
| [81] | W. Zeng, L. M. Lui, F. Luo, T. F.-C. Chan, S.-T. Yau, and D. X. Gu, Computing quasiconformal maps using an auxiliary metric and discrete curvature flow, Numer. Math., 121 (2012), pp. 671-703. · Zbl 1246.30037 |
| [82] | W. Zeng, F. Luo, S.-T. Yau, and X. D. Gu, Surface quasi-conformal mapping by solving Beltrami equations, in Proceedings of the IMA International Conference on Mathematics of Surfaces, Springer, 2009, pp. 391-408. · Zbl 1259.65032 |
| [83] | W. Zeng, X. Yin, M. Zhang, F. Luo, and X. Gu, Generalized Koebe’s method for conformal mapping multiply connected domains, in Proceedings of the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, ACM, 2009, pp. 89-100. |
| [84] | M. Zhang, R. Guo, W. Zeng, F. Luo, S.-T. Yau, and X. Gu, The unified discrete surface Ricci flow, Graphical Models, 76 (2014), pp. 321-339. |
| [85] | X. Zhao, Z. Su, X. D. Gu, A. Kaufman, J. Sun, J. Gao, and F. Luo, Area-preservation mapping using optimal mass transport, IEEE Trans. Vis. Comput. Graphics, 19 (2013), pp. 2838-2847. |
| [86] | G. Zou, J. Hu, X. Gu, and J. Hua, Authalic parameterization of general surfaces using Lie advection, IEEE Trans. Vis. Comput. Graphics, 17 (2011), pp. 2005-2014. |
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.
