# American Institute of Mathematical Sciences

2014, 8(2): 389-408. doi: 10.3934/ipi.2014.8.389

## A variational algorithm for the detection of line segments

 1 Dipartimento di Matematica "Francesco Brioschi", Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy 2 Norwegian University of Science and Technology, 7491 Trondheim, Norway 3 Institute of Mathematics and Computer Science, Wroclaw University of Technology, Wyb. Wyspianskiego 27, 50-370 Wroclaw, Poland 4 Computational Science Center, University of Vienna, Nordbergstrasse 15, 1090 Wien

Received  June 2013 Revised  February 2014 Published  May 2014

In this paper we propose an algorithm for the detection of edges in images that is based on topological asymptotic analysis. Motivated from the Mumford--Shah functional, we consider a variational functional that penalizes oscillations outside some approximate edge set, which we represent as the union of a finite number of thin strips, the width of which is an order of magnitude smaller than their length. In order to find a near optimal placement of these strips, we compute an asymptotic expansion of the functional with respect to the strip size. This expansion is then employed for defining a (topological) gradient descent like minimization method. As opposed to a recently proposed method by some of the authors, which uses coverings with balls, the usage of strips includes some directional information into the method, which can be used for obtaining finer edges and can also result in a reduction of computation times.
Citation: Elena Beretta, Markus Grasmair, Monika Muszkieta, Otmar Scherzer. A variational algorithm for the detection of line segments. Inverse Problems & Imaging, 2014, 8 (2) : 389-408. doi: 10.3934/ipi.2014.8.389
##### References:
 [1] S. Amstutz, I. Horchani and M. Masmoudi, Crack detection by the topological gradient method,, Control and Cybernetics, 34 (2005), 81. [2] S. Amstutz, Sensitivity analysis with respect to a local perturbation of the material property,, Asymptotic Analysis, 49 (2006), 87. [3] L. Belaid, M. Jaoua, M. Masmoudi and L. Siala, Image restoration and edge detection by topological asymptotic expansion,, C. R. Acad. Sci. Paris, 342 (2006), 313. doi: 10.1016/j.crma.2005.12.009. [4] E. Beretta, Y. Capdeboscq, F. de Gournay and E. Francini, Thin cylindrical conductivity inclusions in a three-dimensional domain: a polarization tensor and unique determination from boundary data., Inverse Probl., 25 (2009). doi: 10.1088/0266-5611/25/6/065004. [5] A. Braides, Approximation of Free-Discontinuity Problems, volume 1694 of Lecture Notes in Mathematics,, Springer-Verlag, (1998). [6] Y. Capdeboscq and M. S. Vogelius, A general representation formula for boundary voltage perturbations caused by internal conductivity inhomogeneities of low volume fraction,, M2AN Math. Model. Numer. Anal., 37 (2003), 159. doi: 10.1051/m2an:2003014. [7] Y. Capdeboscq and M. S. Vogelius, Pointwise polarization tensor bounds, and applications to voltage perturbations caused by thin inhomogeneities,, Asymptot. Anal., 50 (2006), 175. [8] G. Cortesani, Strong approximation of GSBV functions by piecewise smooth functions,, Ann. Univ. Ferrara Sez. VII (N.S.), 43 (1997), 27. [9] G. Cortesani and R. Toader, A density result in SBV with respect to non-isotropic energies,, Nonlinear Anal., 38 (1999), 585. doi: 10.1016/S0362-546X(98)00132-1. [10] G. Dong, M. Grasmair, S. H. Kang and O. Scherzer, Scale and edge detection with topological derivatives of the Mumford-Shah functional,, In A. Kuijper, (7893), 404. [11] D. Gilbarg and N. S. Trudinger, Elliptic Partial Differential Equations of Second Order,, Reprint of the 2nd ed. Springer, (2001). [12] M. Grasmair, M. Muszkieta and O. Scherzer, An approach to the minimization of the Mumford-Shah functional using $\Gamma$-convergence and topological asymptotic expansion,, Interfaces Free Bound., 15 (2013), 141. doi: 10.4171/IFB/298. [13] Y. M. Jung, S. H. Kang and J. Shen, Multiphase image segmentation via Modica-Mortola phase transition,, SIAM J. Appl. Math., 67 (2007), 1213. doi: 10.1137/060662708. [14] O. A. Ladyzhenskaya and N. N. Ural'tseva, Linear and Quasilinear Elliptic Equations,, Translated from the Russian by Scripta Technica, (1968). [15] D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math., 42 (1989), 577. doi: 10.1002/cpa.3160420503. [16] M. S. Vogelius and D. Volkov, Asymptotic formulas for perturbations in the electromagnetic fields due to the presence of inhomogeneities of small diameter,, M2AN Math. Model. Numer. Anal., 34 (2000), 723. doi: 10.1051/m2an:2000101.

show all references

##### References:
 [1] S. Amstutz, I. Horchani and M. Masmoudi, Crack detection by the topological gradient method,, Control and Cybernetics, 34 (2005), 81. [2] S. Amstutz, Sensitivity analysis with respect to a local perturbation of the material property,, Asymptotic Analysis, 49 (2006), 87. [3] L. Belaid, M. Jaoua, M. Masmoudi and L. Siala, Image restoration and edge detection by topological asymptotic expansion,, C. R. Acad. Sci. Paris, 342 (2006), 313. doi: 10.1016/j.crma.2005.12.009. [4] E. Beretta, Y. Capdeboscq, F. de Gournay and E. Francini, Thin cylindrical conductivity inclusions in a three-dimensional domain: a polarization tensor and unique determination from boundary data., Inverse Probl., 25 (2009). doi: 10.1088/0266-5611/25/6/065004. [5] A. Braides, Approximation of Free-Discontinuity Problems, volume 1694 of Lecture Notes in Mathematics,, Springer-Verlag, (1998). [6] Y. Capdeboscq and M. S. Vogelius, A general representation formula for boundary voltage perturbations caused by internal conductivity inhomogeneities of low volume fraction,, M2AN Math. Model. Numer. Anal., 37 (2003), 159. doi: 10.1051/m2an:2003014. [7] Y. Capdeboscq and M. S. Vogelius, Pointwise polarization tensor bounds, and applications to voltage perturbations caused by thin inhomogeneities,, Asymptot. Anal., 50 (2006), 175. [8] G. Cortesani, Strong approximation of GSBV functions by piecewise smooth functions,, Ann. Univ. Ferrara Sez. VII (N.S.), 43 (1997), 27. [9] G. Cortesani and R. Toader, A density result in SBV with respect to non-isotropic energies,, Nonlinear Anal., 38 (1999), 585. doi: 10.1016/S0362-546X(98)00132-1. [10] G. Dong, M. Grasmair, S. H. Kang and O. Scherzer, Scale and edge detection with topological derivatives of the Mumford-Shah functional,, In A. Kuijper, (7893), 404. [11] D. Gilbarg and N. S. Trudinger, Elliptic Partial Differential Equations of Second Order,, Reprint of the 2nd ed. Springer, (2001). [12] M. Grasmair, M. Muszkieta and O. Scherzer, An approach to the minimization of the Mumford-Shah functional using $\Gamma$-convergence and topological asymptotic expansion,, Interfaces Free Bound., 15 (2013), 141. doi: 10.4171/IFB/298. [13] Y. M. Jung, S. H. Kang and J. Shen, Multiphase image segmentation via Modica-Mortola phase transition,, SIAM J. Appl. Math., 67 (2007), 1213. doi: 10.1137/060662708. [14] O. A. Ladyzhenskaya and N. N. Ural'tseva, Linear and Quasilinear Elliptic Equations,, Translated from the Russian by Scripta Technica, (1968). [15] D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math., 42 (1989), 577. doi: 10.1002/cpa.3160420503. [16] M. S. Vogelius and D. Volkov, Asymptotic formulas for perturbations in the electromagnetic fields due to the presence of inhomogeneities of small diameter,, M2AN Math. Model. Numer. Anal., 34 (2000), 723. doi: 10.1051/m2an:2000101.
 [1] Dominique Zosso, Jing An, James Stevick, Nicholas Takaki, Morgan Weiss, Liane S. Slaughter, Huan H. Cao, Paul S. Weiss, Andrea L. Bertozzi. Image segmentation with dynamic artifacts detection and bias correction. Inverse Problems & Imaging, 2017, 11 (3) : 577-600. doi: 10.3934/ipi.2017027 [2] Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645 [3] Matthew S. Keegan, Berta Sandberg, Tony F. Chan. A multiphase logic framework for multichannel image segmentation. Inverse Problems & Imaging, 2012, 6 (1) : 95-110. doi: 10.3934/ipi.2012.6.95 [4] Jianping Zhang, Ke Chen, Bo Yu, Derek A. Gould. A local information based variational model for selective image segmentation. Inverse Problems & Imaging, 2014, 8 (1) : 293-320. doi: 10.3934/ipi.2014.8.293 [5] Ruiliang Zhang, Xavier Bresson, Tony F. Chan, Xue-Cheng Tai. Four color theorem and convex relaxation for image segmentation with any number of regions. Inverse Problems & Imaging, 2013, 7 (3) : 1099-1113. doi: 10.3934/ipi.2013.7.1099 [6] N. Maaroufi. Topological entropy by unit length for the Ginzburg-Landau equation on the line. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 647-662. doi: 10.3934/dcds.2014.34.647 [7] Eva Barrena, Alicia De-Los-Santos, Gilbert Laporte, Juan A. Mesa. Transferability of collective transportation line networks from a topological and passenger demand perspective. Networks & Heterogeneous Media, 2015, 10 (1) : 1-16. doi: 10.3934/nhm.2015.10.1 [8] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [9] Fabien Caubet, Carlos Conca, Matías Godoy. On the detection of several obstacles in 2D Stokes flow: Topological sensitivity and combination with shape derivatives. Inverse Problems & Imaging, 2016, 10 (2) : 327-367. doi: 10.3934/ipi.2016003 [10] Audric Drogoul, Gilles Aubert. The topological gradient method for semi-linear problems and application to edge detection and noise removal. Inverse Problems & Imaging, 2016, 10 (1) : 51-86. doi: 10.3934/ipi.2016.10.51 [11] Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925 [12] Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems & Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455 [13] Ke Chen, Yiqiu Dong, Michael Hintermüller. A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration. Inverse Problems & Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323 [14] Hans J. Wolters. A Newton-type method for computing best segment approximations. Communications on Pure & Applied Analysis, 2004, 3 (1) : 133-148. doi: 10.3934/cpaa.2004.3.133 [15] Monika Muszkieta. A variational approach to edge detection. Inverse Problems & Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009 [16] Michael Dellnitz, O. Junge, B Thiere. The numerical detection of connecting orbits. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 125-135. doi: 10.3934/dcdsb.2001.1.125 [17] Micol Amar, Andrea Braides. A characterization of variational convergence for segmentation problems. Discrete & Continuous Dynamical Systems - A, 1995, 1 (3) : 347-369. doi: 10.3934/dcds.1995.1.347 [18] P. C. Jha, Sugandha Aggarwal, Anshu Gupta, Ruhul Sarker. Multi-criteria media mix decision model for advertising a single product with segment specific and mass media. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1367-1389. doi: 10.3934/jimo.2016.12.1367 [19] Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899 [20] Baolin He. Entropy of diffeomorphisms of line. Discrete & Continuous Dynamical Systems - A, 2017, 37 (9) : 4753-4766. doi: 10.3934/dcds.2017204

2017 Impact Factor: 1.465