×

QCMC: quasi-conformal parameterizations for multiply-connected domains. (English) Zbl 1337.65017

Summary: This paper presents a method to compute the quasi-conformal parameterization (QCMC) for a multiply-connected 2D domain or surface. QCMC computes a quasi-conformal map from a multiply-connected domain \(S\) onto a punctured disk \(D_S\) associated with a given Beltrami differential. The Beltrami differential, which measures the conformality distortion, is a complex-valued function \(\mu :S\to \mathbb {C}\) with supremum norm strictly less than 1. Every Beltrami differential gives a conformal structure of \(S\). Hence, the conformal module of \(D_S\), which are the radii and centers of the inner circles, can be fully determined by \(\mu\), up to a Möbius transformation. In this paper, we propose an iterative algorithm to simultaneously search for the conformal module and the optimal quasi-conformal parameterization. The key idea is to minimize the Beltrami energy with the conformal module of the parameter domain incorporated. The optimal solution is our desired quasi-conformal parameterization onto a punctured disk. The parameterization of the multiply-connected domain simplifies numerical computations and has important applications in various fields, such as in computer graphics and vision. Experiments have been carried out on synthetic data together with real multiply-connected Riemann surfaces. Results show that our proposed method can efficiently compute quasi-conformal parameterizations of multiply-connected domains and outperforms other state-of-the-art algorithms. Applications of the proposed parameterization technique have also been explored.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

References:

[1] Dominitz, A., Tannenbaum, A.: Texture mapping via optimal mass transport. IEEE Trans. Vis. Comput. Graph 16(3), 419-433 (2010) · doi:10.1109/TVCG.2009.64
[2] Tutte, W.: Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph 21(3), 362-371 (2002)
[3] Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., Stuetzle, W.: Multiresolution analysis of arbitrary meshes. In: SIGGRAPH ’95 Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, pp. 173-182 (1995) · Zbl 1195.30011
[4] Lévy, B., Petitjean, S., Ray, N., Maillot, J.: Convex representation of graphs. In: Proceeding of London Mathematical Society, vol. 10 (1960) · Zbl 0726.76075
[5] Floater, M.: Parametrization and smooth approximation of surface triangulations. Comput. Aided Geom. Des. 14(3), 231-250 (1997) · Zbl 0906.68162 · doi:10.1016/S0167-8396(96)00031-3
[6] Haker, S., Angenent, S., Tannenbaum, A., Kikinis, R., Sapiro, G., Halle, M.: Conformal surface parameterization for texture mapping. IEEE Trans. Vis. Comput. Graph. 6, 181-189 (2000) · doi:10.1109/2945.856998
[7] Gardiner, F., Lakic, N.: Quasiconformal Teichmuller Theory. American Mathematics Society (2000) · Zbl 0949.30002
[8] Fischl, B., Sereno, M., Tootell, R., Dale, A.: High-resolution intersubject averaging and a coordinate system for the cortical surface. Human Brain Mapping 8, 272-284 (1999) · doi:10.1002/(SICI)1097-0193(1999)8:4<272::AID-HBM10>3.0.CO;2-4
[9] Gu, X., Wang, Y., Chan, T.F., Thompson, P.M., Yau, S.-T.: Genus zero surface conformal mapping and its application to brain, surface mapping. IEEE Trans. Med. Imag. 23(8), 949-958 (2004) · doi:10.1109/TMI.2004.831226
[10] Wang, Y., Lui, L.M., Gu, X., Hayashi, K.M., Chan, T.F., Toga, A.W., Thompson, P.M., Yau, S.-T.: Brain surface conformal parameterization using Riemann surface structure. IEEE Trans. Med. Imag. 26(6), 853-865 (2007) · doi:10.1109/TMI.2007.895464
[11] Gu, X., Yau, S.: Computing conformal structures of surfaces. Comm. Inf. Syst. 2(2), 121-146 (2002) · Zbl 1092.14514
[12] Hurdal, M.K., Stephenson, K.: Discrete conformal methods for cortical brain flattening. Neuroimage 45, 86-98 (2009) · doi:10.1016/j.neuroimage.2008.10.045
[13] Tenenbaum, J.B., Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290(5500), 2319-2323 (2000) · Zbl 0955.37025 · doi:10.1126/science.290.5500.2319
[14] Lui, L.M., Wong, T.W., Gu, X.F., Chan, T.F., Yau, S.T.: Compression of surface diffeomorphism using beltrami coefficient. IEEE Comput. Vis. Pattern Recog. (CVPR), 2839-2846 (2010)
[15] Lui, L.M., Wong, T.W., Zeng, W., Gu, X.F., Thompson, P.M., Chan, T.F., Yau, S.T.: Optimization of surface registrations using Beltrami holomorphic flow. J. Sci. Comput. 50(3), 557-585 (2012) · Zbl 1244.65096 · doi:10.1007/s10915-011-9506-2
[16] Lui, L.M., Wong, T.W., Gu, X.F., Thompson, P.M., Chan, T.F., Yau, S.T.: Hippocampal shape registration using Beltrami Holomorphic flow. In; Medical Image Computing and Computer Assisted Intervention (MICCAI), Part II, (LNCS), vol. 6362, pp. 323-330 (2010) · Zbl 0906.68162
[17] Ng, T.C., Gu, X.F., Lui, L.M.: Computing extremal teichm?ller map of multiply-connected domains via beltrami holomorphic flow. J. Sci. Comput. doi:10.1007/s10915-013-9791-z (2013) · Zbl 0996.30006
[18] Zeng, W., Lui, L.M., Luo, F., Chan, T.F., Yau, S.T., Gu, X.F.: Computing quasiconformal maps using an auxiliary metric and discrete curvature flow. Numerische Mathematik 121(4), 671-703 (2012) · Zbl 1246.30037 · doi:10.1007/s00211-012-0446-z
[19] Lui, L.M., Lam, K.C., Wong, T.W., Gu, X.F.: Texture map and video compression using Beltrami representation. SIAM J. Imag. Sci. 6(4), 1880-1902 (2013) · Zbl 1281.65036 · doi:10.1137/120866129
[20] Lui, L.M., Zeng, W., Yau, S.T., Gu, X.F.: Shape analysis of planar multiply-connected objects using conformal welding. IEEE Trans. Pattern Anal. Mach. Intell. doi:10.1109/TPAMI.2013.215 (2013) · Zbl 1111.30007
[21] Mullen, P.; Tong, Y.; Alliez, P.; Desbrun, M., No article title, Spectral conformal parameterization. computer graphics forum, 27, 1487-1494 (2008) · doi:10.1111/j.1467-8659.2008.01289.x
[22] Zeng, W., Gu, X.: Registration for 3D surfaces with large deformations using quasi-conformal curvature flow. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR?11). Colorado Springs (2011)
[23] Jin, M., Kim, J., Luo, F., Gu, X.: Discrete surface Ricci flow. IEEE Trans. Vis. Comput. Graph. 14(5), 1030-1043 (2008) · doi:10.1109/TVCG.2008.57
[24] Yang, Y.L., Guo, R., Luo, F., Hu, S.M., Gu, X.F.: Generalized discrete Ricci flow. Comput Graph Forum 28(7), 2005-2014 (2009) · doi:10.1111/j.1467-8659.2009.01579.x
[25] Zeng, W., Lui, L.M., Shi, L., Wang, D., Chu, W.C., Cheng, J.C., Hua, J., Yau, S.T., Gu, X.F.: Shape analysis of vestibular systems in adolescent idiopathic scoliosis using geodesic spectra. Med. Image Comput. Comput. Assisted Interv. 13(3), 538-546 (2010)
[26] Lui, L.M., Lam, K.C., Yau, S.T., Gu, X.F.: Teichmüller mapping (T-Map) and its applications to landmark matching registration. SIAM J. Imag. Sci. 7(1), 391-326 (2014) · Zbl 1296.65028 · doi:10.1137/120900186
[27] Porter, R.M.: An interpolating polynomial method for numerical conformal mapping. SIAM J. Sci. Comput. 23(3), 1027-?1041 (2001) · Zbl 0996.30006 · doi:10.1137/S1064827599355256
[28] Hale, N., Tee, T.W.: Conformal maps to multiply-slit domains and applications. SIAM J. Sci. Comput 31(4), 3195-3215 (2009) · Zbl 1195.30011 · doi:10.1137/080738325
[29] DeLillo, T.K., Kropf, E.H.: Numerical computation of the Schwarz-? Christoffel transformation for multiply connected domains. SIAM J. Sci. Comput. 33(3), 3195-3215 (2011) · Zbl 1267.30022 · doi:10.1137/100816912
[30] Zeng, W., Lui, L.M., Gu, X.F., Yau, S.T.: Shape analysis by conformal modules. Methods Appl. Anal. 15(4), 539-556 (2008) · Zbl 1184.30035
[31] Lui, L.M., Gu, X., Chan, T.F., Yau, S.-T.: Variational method on Riemann surfaces using conformal parameterization and its applications to image processin. J. Methods Appl. Anal. 15(4), 513-538 (2008) · Zbl 1185.68807
[32] Wang, Y., Gu, X.F., Chan, T.F., Yau, S.T.: Brain surface conformal parameterization with algebraic functions. medical image computing and computer-assisted intervention. In: MICCAI 2006: 9th international conference, vol. 4191, pp. 946-954. LNCS, Copenhagen (2006)
[33] Wang, Y., Shi, J., Yin, X., Gu, X.F., Chan, T.F., Yau, S.T., Toga, A.W., Thompson, P.M.: Brain surface conformal parameterizaiton with the Ricci flow. IEEE Trans. Med. Imag. 31(2), 251-264 (2012) · doi:10.1109/TMI.2011.2168233
[34] Mastin, C.W., Thompson, J.F.: Quasiconformal mappings and grid generation. SIAM J. Sci. Stat. Comput 5(2), 305-310 (1984) · Zbl 0542.65075 · doi:10.1137/0905022
[35] Daripa, P.: On a numerical method for quasiconformal grid generation. J. Comput. Phys. 96, 229-236 (1991) · Zbl 0726.76075 · doi:10.1016/0021-9991(91)90274-O
[36] Daripa, P.: A fast algorithm to solve nonhomogeneous Cauchy-Riemann equations in the complex plane. SIAM J. Sci. Stat. Comput. 13(6), 1418-1432 (1992) · Zbl 0762.65013 · doi:10.1137/0913080
[37] Aigerman, N., Lipman, Y.: Injective and bounded distortion mappings in 3D. In: SIGGRAPH (2013) · Zbl 1305.68301
[38] Lipman, Y.: Bounded distortion mapping spaces for triangular meshes. ACM SIGGRAPH 31(4), 2012 (2012) · doi:10.1145/2185520.2185604
[39] Weber, M.Z.: Computing extremal quasiconformal maps. Computer Graphics Forum (2012)
[40] Wang, Y., Gu, X.F., Chan, T.F., Thompson, P.M.: Shape analysis with conformal invariants for multiply connected domains and its application to analyzing brain morphology. In: Proceeding of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Miami Beach (2009)
[41] Wong, T., Zhao, H.: Computing surface uniformizations using discrete Beltrami flow. UCLA CAM report (2013)
[42] Krichever, I., Mineev-Weinstein, M., Wiegmannd, P., Zabrodin, A.: Laplacian growth and Whitham equations of soliton theory. Physica D: Nonlinear Phenomena 198(1-2), 1-28 (2004) · Zbl 1078.76025 · doi:10.1016/j.physd.2004.06.003
[43] Krichever, I., Marshakov, A.: A Zabrodin integrable structure of the Dirichlet boundary problem in multiply-connected domains. Commun. Math. Phys 259(1), 1-44 (2005) · Zbl 1091.37019 · doi:10.1007/s00220-005-1387-5
[44] Crowdy, D.: SchwarzChristoffel mappings to unbounded multiply connected polygonal regions. Math. Proc. Camb. Phil. Soc. 142, 319-339 (2007) · Zbl 1111.30007 · doi:10.1017/S0305004106009832
[45] Crowdy, D., Marshall, J.: Analytical formulae for the KirchhoffRouth path function in multiply connected domains. Proc. Royal Soc. A 461, 2477-2501 (2005) · Zbl 1186.76630 · doi:10.1098/rspa.2005.1492
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.