A variational algorithm for the detection of line segments

Previous Article
An inner-outer regularizing method for ill-posed problems
IPI Home
This Issue
Next Article
Minimal partitions and image classification using a gradient-free perimeter approximation

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

Abstract
Related Papers

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 and 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-101.
[2]	S. Amstutz, Sensitivity analysis with respect to a local perturbation of the material property, Asymptotic Analysis, 49 (2006), 87-108.
[3]	L. Belaid, M. Jaoua, M. Masmoudi and L. Siala, Image restoration and edge detection by topological asymptotic expansion, C. R. Acad. Sci. Paris, Ser., 342 (2006), 313-318. 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), 065004, 22pp. 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, Berlin, 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-173. 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-204.
[8]	G. Cortesani, Strong approximation of GSBV functions by piecewise smooth functions, Ann. Univ. Ferrara Sez. VII (N.S.), 43 (1997), 27-49 (1998).
[9]	G. Cortesani and R. Toader, A density result in SBV with respect to non-isotropic energies, Nonlinear Anal., 38 (1999),(5, Ser. B: Real World Appl.), 585-604. 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, editor, SSVM'13: Proceedings of the fourth International Conference on Scale Space and Variational Methods in Computer Vision, volume 7893 of Lecture Notes in Computer Science, pages 404-415, Berlin, Heidelberg, 2013. Springer-Verlag.
[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-166. 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-1232. 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, Inc. Translation editor: Leon Ehrenpreis. Academic Press, New York, 1968.
[15]	D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685. 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-748. 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-101.
[2]	S. Amstutz, Sensitivity analysis with respect to a local perturbation of the material property, Asymptotic Analysis, 49 (2006), 87-108.
[3]	L. Belaid, M. Jaoua, M. Masmoudi and L. Siala, Image restoration and edge detection by topological asymptotic expansion, C. R. Acad. Sci. Paris, Ser., 342 (2006), 313-318. 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), 065004, 22pp. 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, Berlin, 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-173. 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-204.
[8]	G. Cortesani, Strong approximation of GSBV functions by piecewise smooth functions, Ann. Univ. Ferrara Sez. VII (N.S.), 43 (1997), 27-49 (1998).
[9]	G. Cortesani and R. Toader, A density result in SBV with respect to non-isotropic energies, Nonlinear Anal., 38 (1999),(5, Ser. B: Real World Appl.), 585-604. 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, editor, SSVM'13: Proceedings of the fourth International Conference on Scale Space and Variational Methods in Computer Vision, volume 7893 of Lecture Notes in Computer Science, pages 404-415, Berlin, Heidelberg, 2013. Springer-Verlag.
[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-166. 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-1232. 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, Inc. Translation editor: Leon Ehrenpreis. Academic Press, New York, 1968.
[15]	D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685. 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-748. 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 and 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 and Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645
[3]	Fan Jia, Xue-Cheng Tai, Jun Liu. Nonlocal regularized CNN for image segmentation. Inverse Problems and Imaging, 2020, 14 (5) : 891-911. doi: 10.3934/ipi.2020041
[4]	Ye Yuan, Yan Ren, Xiaodong Liu, Jing Wang. Approach to image segmentation based on interval neutrosophic set. Numerical Algebra, Control and Optimization, 2020, 10 (1) : 1-11. doi: 10.3934/naco.2019028
[5]	Matthew S. Keegan, Berta Sandberg, Tony F. Chan. A multiphase logic framework for multichannel image segmentation. Inverse Problems and Imaging, 2012, 6 (1) : 95-110. doi: 10.3934/ipi.2012.6.95
[6]	Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems and Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030
[7]	Jianping Zhang, Ke Chen, Bo Yu, Derek A. Gould. A local information based variational model for selective image segmentation. Inverse Problems and Imaging, 2014, 8 (1) : 293-320. doi: 10.3934/ipi.2014.8.293
[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]	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 and Imaging, 2013, 7 (3) : 1099-1113. doi: 10.3934/ipi.2013.7.1099
[10]	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 and Continuous Dynamical Systems - S, 2021, 14 (3) : 971-985. doi: 10.3934/dcdss.2020351
[11]	Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems and Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048
[12]	Á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 and Applied Analysis, 2021, 20 (2) : 511-532. doi: 10.3934/cpaa.2020278
[13]	N. Maaroufi. Topological entropy by unit length for the Ginzburg-Landau equation on the line. Discrete and Continuous Dynamical Systems, 2014, 34 (2) : 647-662. doi: 10.3934/dcds.2014.34.647
[14]	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 and Heterogeneous Media, 2015, 10 (1) : 1-16. doi: 10.3934/nhm.2015.10.1
[15]	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 and Continuous Dynamical Systems - S, 2021, 14 (3) : 881-891. doi: 10.3934/dcdss.2020233
[16]	Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems and Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022
[17]	Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems and Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037
[18]	Qianting Ma, Tieyong Zeng, Dexing Kong, Jianwei Zhang. Weighted area constraints-based breast lesion segmentation in ultrasound image analysis. Inverse Problems and Imaging, 2022, 16 (2) : 451-466. doi: 10.3934/ipi.2021057
[19]	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 and Imaging, 2016, 10 (2) : 327-367. doi: 10.3934/ipi.2016003
[20]	Audric Drogoul, Gilles Aubert. The topological gradient method for semi-linear problems and application to edge detection and noise removal. Inverse Problems and Imaging, 2016, 10 (1) : 51-86. doi: 10.3934/ipi.2016.10.51

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Elena Beretta Markus Grasmair Monika Muszkieta Otmar Scherzer
on Google Scholar
Elena Beretta Markus Grasmair Monika Muszkieta Otmar Scherzer

[Back to Top]