×

On geodesic curvature flow with level set formulation over triangulated surfaces. (English) Zbl 1391.65041

Let \(M\) be a compact smooth surface in \({\mathbb R}^3\). In the geodesic curvature flow problem, one wishes to find a one parameter set of curves \(C_t\) on \(M\), for \(0\leq t\leq L\), where \(C_0\) is a given initial curve, and \(C_L\) is a local minimum of the length functional; i.e., a geodesic. By the work of S. Osher and J. A. Sethian [J. Comput. Phys. 79, No. 1, 12–49 (1988; Zbl 0659.65132)], this may be recast into a level-set problem. Here one evolves a function \(\phi:M\rightarrow{\mathbb R}\) by solving a particular evolution equation with specified initial function \(\phi_0\) for which \(C_0\) is the zero set. The curve \(C_t\) is the zero set of \(\phi_t\).
Now suppose that \(M\) is triangulated by a collection of nondegenerate triangles. The authors discretize the evolution equation for \(\phi\) under the assumption that \(\phi_t\) is constant on each triangle of \(M\), obtaining a discrete implicit integration scheme. The resulting sequence \(\Phi^{(0)},\Phi^{(1)},\dots\) of solutions is termed the discrete geodesic curvature flow with initial flow function \(\Phi_0=\Phi^{(0)}\). It is shown that, for a given initial flow function, the discrete geodesic curvature flow exists and is unique. Moreover, the integration scheme is numerically stable. The zero set of the flow function is taken to be the discontinuity set of \(\Phi^{(n)}\): the set of all edges \(e\) for which the values of \(\Phi^{(n)}\) at the two triangles that share \(e\) have the opposite sign. Numerical experiments indicate that the discrete geodesic curvature flow converges to a discrete function whose discontinuity set consists of closed discrete geodesics.
Using discrete geodesic curvature flow, the authors go on to develop an efficient algorithm for multi-phase segmentation. That is, given an initial collection of discrete curves that partition \(M\) into various regions, the curves are evolved using a single level-set function to a collection of discrete geodesics that partition \(M\).

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 0659.65132
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adalsteinsson, D., Sethian, J.A.: A fast level set method for propagating interfaces. J. Comput. Phys. 118(2), 269-277 (1995) · Zbl 0823.65137 · doi:10.1006/jcph.1995.1098
[2] Adalsteinsson, D., Sethian, J.A.: The fast construction of extension velocities in level set methods. J. Comput. Phys. 148(1), 2-22 (1999) · Zbl 0919.65074 · doi:10.1006/jcph.1998.6090
[3] Brox, T., Weickert, J.: Level set segmentation with multiple regions. IEEE Trans. Image Process. 15(10), 3213-3218 (2006) · doi:10.1109/TIP.2006.877481
[4] Caselles, V., Catté, F., Coll, F., Dibos, F.: A geometric model for active contours in image processing. Numer. Math. 66(1), 1-31 (1993) · Zbl 0804.68159 · doi:10.1007/BF01385685
[5] Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. In: Proceedings of the Fifth International Conference on Computer Vision, 1995, pp. 694-699 (1995) · Zbl 0894.68131
[6] Caselles, V., Kimmel, R., Sapiro, G., Sbert, C.: Minimal surfaces: a geometric three dimensional segmentation approach. Numer. Math. 77(4), 423-451 (1997) · Zbl 0891.68093 · doi:10.1007/s002110050294
[7] Chan, T., Vese, L.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266-277 (2001) · Zbl 1039.68779 · doi:10.1109/83.902291
[8] Cheng, L.T., Burchard, P., Merriman, B., Osher, S.: Motion of curves constrained on surfaces using a level-set approach. J. Comput. Phys. 175(2), 604-644 (2002) · Zbl 0996.65013 · doi:10.1006/jcph.2001.6960
[9] Chopp, D.L.: Computing minimal surfaces via level set curvature flow. J. Comput. Phys. 106(1), 77-91 (1993) · Zbl 0786.65015 · doi:10.1006/jcph.1993.1092
[10] Chopp, D.L., Sethian, J.A.: Flow under curvature: singularity formation, minimal surfaces, and geodesics. Exp. Math. 2(4), 235-255 (1993) · Zbl 0806.53004 · doi:10.1080/10586458.1993.10504566
[11] Davis, H.T., Thomson, K.T.: Linear Algebra and Linear Operators in Engineering: With Applications in Mathematica. Academic Press, New York (2000) · Zbl 0959.65001
[12] Dubrovina, A., Rosman, G., Kimmel, R.: Multi-region active contours with a single level set function. IEEE Trans. Pattern Anal. Mach. Intell. 37(8), 1585-1601 (2015) · doi:10.1109/TPAMI.2014.2385708
[13] Evans, L.C., Spruck, J.: Motion of level sets by mean curvature: I. J. Differ. Geom. 33(3), 635-681 (1991) · Zbl 0726.53029
[14] Fu, Z., Jeong, W., Pan, Y., Kirby, R., Whitaker, R.: A fast iterative method for solving the eikonal equation on triangulated surfaces. SIAM J. Sci. Comput. 33(5), 2468-2488 (2011) · Zbl 1298.65164 · doi:10.1137/100788951
[15] Gage, M.: Curve shortening makes convex curves circular. Invent. Math. 76(2), 357-364 (1984) · Zbl 0542.53004 · doi:10.1007/BF01388602
[16] Gage, M.: Curve shortening on surfaces. Ann. Sci. École Norm. Sup. 23(2), 229-256 (1990) · Zbl 0713.53022
[17] Gage, M., Hamilton, R.S.: The heat equation shrinking convex plane curves. J. Differ. Geom. 23(1), 69-96 (1986) · Zbl 0621.53001
[18] Goldenberg, R., Kimmel, R., Rivlin, E., Rudzsky, M.: Fast geodesic active contours. IEEE Trans. Image Process. 10(10), 1467-1475 (2001) · doi:10.1109/83.951533
[19] Grayson, M.A.: The heat equation shrinks embedded plane curves to round points. J. Differ. Geom. 26(2), 285-314 (1987) · Zbl 0667.53001
[20] Grayson, M.A.: Shortening embedded curves. Ann. Math. 129(1), 71-111 (1989) · Zbl 0686.53036 · doi:10.2307/1971486
[21] Hoffman, D.D., Richards, W.A.: Parts of recognition. Cognition 18, 65-96 (1984) · doi:10.1016/0010-0277(84)90022-2
[22] Kass, M., Witkin, A., Terzopoulos, D.: Snakes: active contour models. Int. J. Comput. Vis. 1(4), 321-331 (1988) · Zbl 0646.68105 · doi:10.1007/BF00133570
[23] Kimia, B.B., Siddiqi, K.: Geometric heat equation and nonlinear diffusion of shapes and images. In: Proceedings of the 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1994 (CVPR’94.), pp. 113-120 (1994) · Zbl 1298.65164
[24] Kimmel, R.; Romeny, BH (ed.); Florack, L. (ed.); Koenderink, J. (ed.); Viergever, M. (ed.), Intrinsic scale space for images on surfaces: the geodesic curvature flow, 212-223 (1997), Berlin · doi:10.1007/3-540-63167-4_52
[25] Lai, R., Shi, Y., Sicotte, N., Toga, A.: Automated corpus callosum extraction via laplace-beltrami nodal parcellation and intrinsic geodesic curvature flows on surfaces. In: Proceedings of the 2011 International Conference on Computer Vision, pp. 2034-2040 (2011)
[26] Lai, Y., Hu, S., Martin, R., Rosin, P.: Fast mesh segmentation using random walks. In: Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling, pp. 183-191 (2008)
[27] Lie, J., Lysaker, M., Tai, X.C.: A variant of the level set method and applications to image segmentation. Math. Comput. 75(255), 1155-1174 (2006) · Zbl 1096.35034 · doi:10.1090/S0025-5718-06-01835-7
[28] Ma, L., Chen, D.: Curve shortening flow in a riemannian manifold. 2003. arXiv:math/0312463 · Zbl 1012.68706
[29] Malladi, R., Sethian, J.A., Vemuri, B.C.: Shape modeling with front propagation: a level set approach. IEEE Trans. Pattern Anal. Mach. Intell. 17(2), 158-175 (1995) · doi:10.1109/34.368173
[30] Meyer, M.; Desbrun, M.; Schröder, P.; Barr, A.; Hege, H-C (ed.); Polthier, K. (ed.), Discrete differential-geometry operators for triangulated 2-manifolds, 35-57 (2003), Berlin, Heidelberg · Zbl 1069.53004 · doi:10.1007/978-3-662-05105-4_2
[31] Mikula, K., Sevcovic, D.: Evolution of curves on a surface driven by the geodesic curvature and external force. Appl. Anal. 85(4), 345-362 (2006) · Zbl 1097.35084 · doi:10.1080/00036810500333604
[32] Osher, S., Sethian, J.A.: Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79(1), 12-49 (1988) · Zbl 0659.65132 · doi:10.1016/0021-9991(88)90002-2
[33] Poole, G., Boullion, T.: A survey on M-matrices. SIAM Rev. 16(16), 419-427 (1974) · Zbl 0292.15009 · doi:10.1137/1016079
[34] Qian, J., Zhang, Y., Zhao, H.: Fast sweeping methods for eikonal equations on triangular meshes. SIAM J. Numer. Anal. 45(1), 83-107 (2007) · Zbl 1149.65087 · doi:10.1137/050627083
[35] Samson, C., Blanc-Féraud, L., Aubert, G., Zerubia, J.: A level set model for image classification. Int. J. Comput. Vis. 40(3), 187-197 (2000) · Zbl 1012.68706 · doi:10.1023/A:1008183109594
[36] Saye, R.I., Sethian, J.A.: The Voronoi implicit interface method for computing multiphase physics. Proc. Natl. Acad. Sci. 108(49), 19498-19503 (2011) · Zbl 1256.65082 · doi:10.1073/pnas.1111557108
[37] Saye, R.I., Sethian, J.A.: Analysis and applications of the Voronoi implicit interface method. J. Comput. Phys. 231(18), 6051-6085 (2012) · doi:10.1016/j.jcp.2012.04.004
[38] Sethian, J.A.: Level Set Methods and Fast Marching Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision and Materials Sciences. Cambridge University Press, Cambridge (1999) · Zbl 0973.76003
[39] Spira, G., Kimmel, R.: Geometric curve flows on parametric manifolds. J. Comput. Phys. 223(1), 235-249 (2007) · Zbl 1118.53004 · doi:10.1016/j.jcp.2006.09.008
[40] Tsai, A., Yezzi, A., Willsky, A.: Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification. IEEE Trans. Image Process. 10(8), 1169-1186 (2001) · Zbl 1062.68595 · doi:10.1109/83.935033
[41] Vese, L., Chan, T.: A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vis. 50(3), 271-293 (2002) · Zbl 1012.68782 · doi:10.1023/A:1020874308076
[42] Wu, C., Tai, X.C.: A level set formulation of geodesic curvature flow on simplicial surfaces. IEEE Trans. Vis. Comput. Graph. 16(4), 647-662 (2010) · doi:10.1109/TVCG.2009.103
[43] Zhang, H., Wu, C., Zhang, J., Deng, J.: Variational mesh denoising using total variation and piecewise constant function space. IEEE Trans. Vis. Comput. Graph. 21(7), 873-886 (2015) · doi:10.1109/TVCG.2015.2398432
[44] Zhang, J., Wu, C., Cai, J., Zheng, J., Tai, X.C.: Mesh snapping: robust interactive mesh cutting using fast geodesic curvature flow. Comput. Graph. Forum 29(2), 517-526 (2010) · doi:10.1111/j.1467-8659.2009.01621.x
[45] Zhao, H., Chan, T., Merriman, B., Osher, S.: A variational level set approach to multiphase motion. J. Comput. Phys. 127(1), 179-195 (1996) · Zbl 0860.65050 · doi:10.1006/jcph.1996.0167
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.