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]

Álvaro Castañeda, Pablo González, Gonzalo Robledo. Topological Equivalence of nonautonomous difference equations with a family of dichotomies on the half line. Communications on Pure & Applied Analysis, 2021, 20 (2) : 511-532. doi: 10.3934/cpaa.2020278
[2]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048
[3]

Balázs Kósa, Karol Mikula, Markjoe Olunna Uba, Antonia Weberling, Neophytos Christodoulou, Magdalena Zernicka-Goetz. 3D image segmentation supported by a point cloud. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 971-985. doi: 10.3934/dcdss.2020351
[4]

Maika Goto, Kazunori Kuwana, Yasuhide Uegata, Shigetoshi Yazaki. A method how to determine parameters arising in a smoldering evolution equation by image segmentation for experiment's movies. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 881-891. doi: 10.3934/dcdss.2020233
[5]

Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249
[6]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271
[7]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[8]

Tian Ma, Shouhong Wang. Topological phase transition III: Solar surface eruptions and sunspots. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 501-514. doi: 10.3934/dcdsb.2020350
[9]

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020176
[10]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[11]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[12]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021001
[13]

Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308
[14]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[15]

Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389
[16]

Kateřina Škardová, Tomáš Oberhuber, Jaroslav Tintěra, Radomír Chabiniok. Signed-distance function based non-rigid registration of image series with varying image intensity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1145-1160. doi: 10.3934/dcdss.2020386
[17]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127
[18]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[19]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[20]

Bao Wang, Alex Lin, Penghang Yin, Wei Zhu, Andrea L. Bertozzi, Stanley J. Osher. Adversarial defense via the data-dependent activation, total variation minimization, and adversarial training. Inverse Problems & Imaging, 2021, 15 (1) : 129-145. doi: 10.3934/ipi.2020046

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (36)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences