×

Global minimum for a Finsler elastica minimal path approach. (English) Zbl 1477.68341

Summary: In this paper, we propose a novel curvature penalized minimal path model via an orientation-lifted Finsler metric and the Euler elastica curve. The original minimal path model computes the globally minimal geodesic by solving an Eikonal partial differential equation (PDE). Essentially, this first-order model is unable to penalize curvature which is related to the path rigidity property in the classical active contour models. To solve this problem, we present an Eikonal PDE-based Finsler elastica minimal path approach to address the curvature-penalized geodesic energy minimization problem. We were successful at adding the curvature penalization to the classical geodesic energy [V. Caselles et al., Int. J. Comput. Vis. 22, No. 1, 61–79 (1997; Zbl 0894.68131); the last author and R. Kimmel, “Global minimum for active contour models: a minimal path approach”, ibid. 24, No. 1, 57–78 (1997; doi:10.1023/A:1007922224810)]. The basic idea of this work is to interpret the Euler elastica bending energy via a novel Finsler elastica metric that embeds a curvature penalty. This metric is non-Riemannian, anisotropic and asymmetric, and is defined over an orientation-lifted space by adding to the image domain the orientation as an extra space dimension. Based on this orientation lifting, the proposed minimal path model can benefit from both the curvature and orientation of the paths. Thanks to the fast marching method, the global minimum of the curvature-penalized geodesic energy can be computed efficiently. We introduce two anisotropic image data-driven speed functions that are computed by steerable filters. Based on these orientation-dependent speed functions, we can apply the proposed Finsler elastica minimal path model to the applications of closed contour detection, perceptual grouping and tubular structure extraction. Numerical experiments on both synthetic and real images show that these applications of the proposed model indeed obtain promising results.

MSC:

68T45 Machine vision and scene understanding
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 0894.68131

References:

[1] Alpert, S., Galun, M., Brandt, A., & Basri, R. (2012). Image segmentation by probabilistic bottom-up aggregation and cue integration. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(2), 315-327. · doi:10.1109/TPAMI.2011.130
[2] Appia, V., & Yezzi, A. (2011). Active geodesics: Region-based active contour segmentation with a global edge-based constraint. In Proceedings of IEEE International Conference on Computer Vision (ICCV 2011) (pp. 1975-1980).
[3] Appleton, B., & Talbot, H. (2005). Globally optimal geodesic active contours. Journal of Mathematical Imaging and Vision, 23(1), 67-86. · Zbl 1478.94005 · doi:10.1007/s10851-005-4968-1
[4] Arbelaez, P., Maire, M., Fowlkes, C., & Malik, J. (2011). Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(5), 898-916. · doi:10.1109/TPAMI.2010.161
[5] Bekkers, E. J., Duits, R., Mashtakov, A., & Sanguinetti, G. R. (2015). A PDE approach to data-driven sub-riemannian geodesics in SE (2). SIAM Journal on Imaging Sciences, 8(4), 2740-2770. · Zbl 1336.58014 · doi:10.1137/15M1018460
[6] Benmansour, F., & Cohen, L. D. (2009). Fast object segmentation by growing minimal paths from a single point on 2D or 3D images. Journal of Mathematical Imaging and Vision, 33(2), 209-221. · Zbl 1523.68142 · doi:10.1007/s10851-008-0131-0
[7] Benmansour, F., & Cohen, L. D. (2011). Tubular structure segmentation Based on minimal path method and anisotropic enhancement. International Journal of Computer Vision, 92(2), 192-210. · doi:10.1007/s11263-010-0331-0
[8] Bornemann, F., & Rasch, C. (2006). Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle. Computing and Visualization in Science, 9(2), 57-69. · Zbl 1511.65119 · doi:10.1007/s00791-006-0016-y
[9] Bougleux, S., Peyré, G., & Cohen, L. (2008). Anisotropic geodesics for perceptual grouping and domain meshing. Proceedings of European Conference on Computer Vision (ECCV 2008) (pp. 129-142). Berlin: Springer.
[10] Canny, J. (1986). A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 679-698. · doi:10.1109/TPAMI.1986.4767851
[11] Caselles, V., Catté, F., Coll, T., & Dibos, F. (1993). A geometric model for active contours in image processing. Numerische Mathematik, 66(1), 1-31. · Zbl 0804.68159 · doi:10.1007/BF01385685
[12] Caselles, V., Kimmel, R., & Sapiro, G. (1997). Geodesic active contours. International Journal of Computer Vision, 22(1), 61-79. · Zbl 0894.68131 · doi:10.1023/A:1007979827043
[13] Chen, D., Mirebeau, J. M., & Cohen, L. D. (2015). Global minimum for curvature penalized minimal path method. In Proceedings of the British Machine Vision Conference (BMVC 2015) (pp. 86.1-86.12).
[14] Cohen, L. (2001). Multiple contour finding and perceptual grouping using minimal paths. Journal of Mathematical Imaging and Vision, 14(3), 225-236. · Zbl 1053.68113 · doi:10.1023/A:1011281928379
[15] Cohen, L. D. (1991). On active contour models and balloons. CVGIP: Image Understanding, 53(2), 211-218. · Zbl 0774.68111 · doi:10.1016/1049-9660(91)90028-N
[16] Cohen, L. D., & Kimmel, R. (1997). Global minimum for active contour models: A minimal path approach. International Journal of Computer Vision, 24(1), 57-78. · doi:10.1023/A:1007922224810
[17] Deschamps, T., & Cohen, L. D. (2001). Fast extraction of minimal paths in 3D images and applications to virtual endoscopy. Medical Image Analysis, 5(4), 281-299. · doi:10.1016/S1361-8415(01)00046-9
[18] Di Zenzo, S. (1986). A note on the gradient of a multi-image. Computer Vision, Graphics, and Image Processing, 33(1), 116-125. · Zbl 0625.68065 · doi:10.1016/0734-189X(86)90223-9
[19] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[20] El-Zehiry, N. Y., & Grady, L. (2010). Fast global optimization of curvature. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010) (pp. 3257-3264).
[21] Jacob, M., & Unser, M. (2004). Design of steerable filters for feature detection using canny-like criteria. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(8), 1007-1019. · doi:10.1109/TPAMI.2004.44
[22] Jbabdi, S., Bellec, P., Toro, R., Daunizeau, J., Pélégrini-Issac, M., & Benali, H. (2008). Accurate anisotropic fast marching for diffusion-based geodesic tractography. International Journal of Biomedical Imaging, 2008, 2. · doi:10.1155/2008/320195
[23] Kass, M., Witkin, A., & Terzopoulos, D. (1988). Snakes: Active contour models. International Journal of Computer Vision, 1(4), 321-331. · Zbl 0646.68105 · doi:10.1007/BF00133570
[24] Kaul, V., Yezzi, A., & Tsai, Y. (2012). Detecting curves with unknown endpoints and arbitrary topology using minimal paths. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(10), 1952-1965. · doi:10.1109/TPAMI.2011.267
[25] Kimmel, R., & Sethian, J. (2001). Optimal algorithm for shape from shading and path planning. Journal of Mathematical Imaging and Vision, 14(3), 237-244. · Zbl 0995.68101 · doi:10.1023/A:1011234012449
[26] Law, M. W. K., & Chung, A. C. S. (2008). Three dimensional curvilinear structure detection using optimally oriented flux. In Proceedings of European Conference on Computer Vision (ECCV 2008) (pp. 368-382). Berlin: Springer.
[27] Li, H., & Yezzi, A. (2007). Vessels as 4-D curves: Global minimal 4-D paths to extract 3-D tubular surfaces and centrelines. IEEE Transactions on Medical Imaging, 26(9), 1213-1223. · doi:10.1109/TMI.2007.903696
[28] Lions, P. L. (1982). Generalized solutions of Hamilton-Jacobi equations (Vol. 69). Boston: Pitman Publishing. · Zbl 0497.35001
[29] Malladi, R., Sethian, J. A., & Vemuri, B. C. (1994). Evolutionary fronts for topology-independent shape modeling and recovery. In Proceedings of European Conference on Computer Vision (ECCV 1994) (pp. 1-13). Berlin: Springer.
[30] Malladi, R., Sethian, J., & Vemuri, B. C. (1995). Shape modeling with front propagation: A level set approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(2), 158-175. · doi:10.1109/34.368173
[31] Mille, J., Bougleux, S., & Cohen, L. (2014). Combination of piecewise-geodesic paths for interactive segmentation. International Journal of Computer Vision, 112(1), 1-22. · Zbl 1360.65075 · doi:10.1007/s11263-014-0751-3
[32] Mirebeau, J. M. (2014a). Anisotropic fast-marching on cartesian grids using lattice basis reduction. SIAM Journal on Numerical Analysis, 52(4), 1573-1599. · Zbl 1312.65172 · doi:10.1137/120861667
[33] Mirebeau, J. M. (2014b). Efficient fast marching with Finsler metrics. Numerische Mathematik, 126(3), 515-557. · Zbl 1297.65074 · doi:10.1007/s00211-013-0571-3
[34] Mumford, D.; Bajaj, CL (ed.), Elastica and computer vision, 491-506 (1994), New York · Zbl 0798.53003 · doi:10.1007/978-1-4612-2628-4_31
[35] Nitzberg, M., & Mumford, D. (1990). The 2.1-D sketch. In Proceedings of IEEE International Conference on Computer Vision (ICCV 1990) (pp. 138-144).
[36] Osher, S., & Sethian, J. A. (1988). Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics, 79(1), 12-49. · Zbl 0659.65132 · doi:10.1016/0021-9991(88)90002-2
[37] Péchaud, M., Keriven, R., & Peyré, G. (2009). Extraction of tubular structures over an orientation domain. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2009) (pp. 336-342).
[38] Petitot, J. (2003). The neurogeometry of pinwheels as a sub-Riemannian contact structure. Journal of Physiology-Paris, 97(2-3), 265-309. · doi:10.1016/j.jphysparis.2003.10.010
[39] Peyré, G., Péchaud, M., Keriven, R., & Cohen, L. D. (2010). Geodesic methods in computer vision and graphics. Foundations and Trends in Computer Graphics and Vision (pp. 197-397). · Zbl 1217.65042
[40] Rouchdy, Y., & Cohen, L. D. (2013). Geodesic voting for the automatic extraction of tree structures. Methods and applications. Computer Vision and Image Understanding, 117(10), 1453-1467. · doi:10.1016/j.cviu.2013.06.001
[41] Sanguinetti, G., Bekkers, E., Duits, R., Janssen, M. H., Mashtakov, A., & Mirebeau, J. M. (2015). Sub-Riemannian fast marching in SE (2). In: Iberoamerican Congress on Pattern Recognition (pp. 366-374). Springer.
[42] Schoenemann, T., Masnou, S., & Cremers, D. (2011). The elastic ratio: Introducing curvature into ratio-based image segmentation. IEEE Transactions on Image Processing, 20(9), 2565-2581. · Zbl 1372.94227 · doi:10.1109/TIP.2011.2118225
[43] Schoenemann, T., Kahl, F., Masnou, S., & Cremers, D. (2012). A linear framework for region-based image segmentation and inpainting involving curvature penalization. International Journal of Computer Vision, 99(1), 53-68. · Zbl 1254.68282 · doi:10.1007/s11263-012-0518-7
[44] Sethian, J. A. (1999). Fast marching methods. SIAM Review, 41(2), 199-235. · Zbl 0926.65106 · doi:10.1137/S0036144598347059
[45] Sethian, J. A., & Vladimirsky, A. (2003). Ordered upwind methods for static Hamilton-Jacobi equations: Theory and algorithms. SIAM Journal on Numerical Analysis, 41(1), 325-363. · Zbl 1040.65088 · doi:10.1137/S0036142901392742
[46] Shen, J., Kang, S. H., & Chan, T. F. (2003). Euler’s elastica and curvature-based inpainting. SIAM Journal on Applied Mathematics, 63(2), 564-592. · Zbl 1028.68185 · doi:10.1137/S0036139901390088
[47] Tai, X. C., Hahn, J., & Chung, G. J. (2011). A fast algorithm for Euler’s elastica model using augmented Lagrangian method. SIAM Journal on Imaging Sciences, 4(1), 313-344. · Zbl 1215.68262 · doi:10.1137/100803730
[48] Tsitsiklis, J. N. (1995). Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control, 40(9), 1528-1538. · Zbl 0831.93028 · doi:10.1109/9.412624
[49] Ulen, J., Strandmark, P., & Kahl, F. (2015). Shortest paths with higher-order regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(12), 2588-2600. · doi:10.1109/TPAMI.2015.2409869
[50] Yezzi, A., Kichenassamy, S., Kumar, A., Olver, P., & Tannenbaum, A. (1997). A geometric snake model for segmentation of medical imagery. IEEE Transactions on Medical Imaging, 16(2), 199-209. · doi:10.1109/42.563665
[51] Zhu, W., Tai, X. C., & Chan, T. (2013). Image segmentation using Euler’s elastica as the regularization. Journal of Scientific Computing, 57(2), 414-438. · Zbl 1282.65037 · doi:10.1007/s10915-013-9710-3
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.