American Institute of Mathematical Sciences

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

A variational algorithm for the detection of line segments

Elena Beretta 1, , Markus Grasmair 2, , Monika Muszkieta 3, and  Otmar Scherzer 4,

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.
Keywords: topological minimization, Line segment detection, image segmentation..
Mathematics Subject Classification: Primary: 35C20; Secondary: 65K1.
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. Google Scholar

[2]

S. Amstutz, Sensitivity analysis with respect to a local perturbation of the material property,, Asymptotic Analysis, 49 (2006), 87. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

A. Braides, Approximation of Free-Discontinuity Problems, volume 1694 of Lecture Notes in Mathematics,, Springer-Verlag, (1998). Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

G. Cortesani, Strong approximation of GSBV functions by piecewise smooth functions,, Ann. Univ. Ferrara Sez. VII (N.S.), 43 (1997), 27. Google Scholar

[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. Google Scholar

[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. Google Scholar

[11]

D. Gilbarg and N. S. Trudinger, Elliptic Partial Differential Equations of Second Order,, Reprint of the 2nd ed. Springer, (2001). Google Scholar

[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. Google Scholar

[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. Google Scholar

[14]

O. A. Ladyzhenskaya and N. N. Ural'tseva, Linear and Quasilinear Elliptic Equations,, Translated from the Russian by Scripta Technica, (1968). Google Scholar

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[2]

S. Amstutz, Sensitivity analysis with respect to a local perturbation of the material property,, Asymptotic Analysis, 49 (2006), 87. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

A. Braides, Approximation of Free-Discontinuity Problems, volume 1694 of Lecture Notes in Mathematics,, Springer-Verlag, (1998). Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

G. Cortesani, Strong approximation of GSBV functions by piecewise smooth functions,, Ann. Univ. Ferrara Sez. VII (N.S.), 43 (1997), 27. Google Scholar

[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. Google Scholar

[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. Google Scholar

[11]

D. Gilbarg and N. S. Trudinger, Elliptic Partial Differential Equations of Second Order,, Reprint of the 2nd ed. Springer, (2001). Google Scholar

[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. Google Scholar

[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. Google Scholar

[14]

O. A. Ladyzhenskaya and N. N. Ural'tseva, Linear and Quasilinear Elliptic Equations,, Translated from the Russian by Scripta Technica, (1968). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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]

Ye Yuan, Yan Ren, Xiaodong Liu, Jing Wang. Approach to image segmentation based on interval neutrosophic set. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019028
[5]

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
[6]

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
[7]

Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030
[8]

Lu Tan, Ling Li, Senjian An, Zhenkuan Pan. Nonlinear diffusion based image segmentation using two fast algorithms. Mathematical Foundations of Computing, 2019, 2 (2) : 149-168. doi: 10.3934/mfc.2019011
[9]

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
[10]

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
[11]

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
[12]

Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

Monika Muszkieta. A variational approach to edge detection. Inverse Problems & Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009
[20]

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

2018 Impact Factor: 1.469

Tools

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences