A fast edge detection algorithm using binary labels

Yuying Shi; Ying Gu; Li-Lian Wang; Xue-Cheng Tai

doi:10.3934/ipi.2015.9.551

Article Contents

2015, Volume 9, Issue 2: 551-578. Doi: 10.3934/ipi.2015.9.551

This issue Previous Article A study of the one dimensional total generalised variation regularisation problem Next Article Modulated luminescence tomography

A fast edge detection algorithm using binary labels

1.
Department of Mathematics and Physics, North China Electric Power University, Beijing, 102206
2.
Institute for Infocomm Research, Agency for Science, Technology and Research (A*STAR), 138632
3.
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 637371
4.
Department of Mathematics, University of Bergen, P. O. Box 7800, N-5020, Bergen

Received: March 31, 2013

Revised: March 31, 2014

Published: April 2015

Abstract Related Papers Cited by

Abstract

Edge detection (for both open and closed edges) from real images is a challenging problem. Developing fast algorithms with good accuracy and stability for noisy images is difficult yet and in demand. In this work, we present a variational model which is related to the well-known Mumford-Shah functional and design fast numerical methods to solve this new model through a binary labeling processing. A pre-smoothing step is implemented for the model, which enhances the accuracy of detection. Ample numerical experiments on grey-scale as well as color images are provided. The efficiency and accuracy of the model and the proposed minimization algorithms are demonstrated through comparing it with some existing methodologies.

Keywords:

Mathematics Subject Classification: Primary: 65D15, 68W40, 90C90; Secondary: 65M32.

Citation:

Related Papers

Cited by

References

[1]	L. Alvarez, P. L. Lions and J. M. Morel, Image selective smoothing and edge detection by nonlinear diffusion II, SIAM J. Numer. Anal., 29 (1992), 845-866.doi: 10.1137/0729052.
[2]	L. Ambrosio and V. M. Tortorelli, Approximation of functions depending on jumps by elliptic functions via $\Gamma$-convergence, Comm. Pure Appl. Math., 43 (1990), 999-1036.doi: 10.1002/cpa.3160430805.
[3]	L. Ambrosio and V. M. Tortorelli, On the Approximation of Functionals Depending on Jumps by Quadratic, Elliptic Functionals, Boll. Un. Mat. Ital., (1992).
[4]	N. Badshah and K. Chen, Image selective segmentation under geometrical constraints using an active contour approach, Commun. Comput. Phys., 7 (2010), 759-778.doi: 10.4208/cicp.2009.09.026.
[5]	S. Basu, D. P. Mukherjee and S. T. Acton, Implicit evolution of open ended curves, in IEEE International Conference on Image Processing, Vol. 1, 2007, 261-264.doi: 10.1109/ICIP.2007.4378941.
[6]	B. Berkels, A. Rätz, M. Rumpf and A. Voigt, Extracting grain boundaries and macroscopic deformations from images on atomic scale, J. Sci. Comput., 35 (2008), 1-23.doi: 10.1007/s10915-007-9157-5.
[7]	A. Braides, Approximation of Free-Discontinuity Problems, Springer-Verlag, 1998.
[8]	L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, (Russian) v'Z. Vyv'cisl. Mat. i Mat. Fiz., 7 (1967), 620-631.
[9]	X. Bresson and T. F. Chan, Fast dual minimization of the vectorial total variation norm and applications to color image processing, Inverse Probl. Imag., 2 (2008), 455-484.doi: 10.3934/ipi.2008.2.455.
[10]	A. Brook, R. Kimmel and N. A. Sochen, Variational restoration and edge detection for color images, J. Math. Imaging Vis., 18 (2003), 247-268.doi: 10.1023/A:1022895410391.
[11]	E. S. Brown, T. F. Chan and X. Bresson, A Convex Relaxation Method for a Class of Vector-Valued Minimization Problems with Applications to Mumford-Shah Segmentation, UCLA cam report, (2010), 10-43.
[12]	J. F. Cai, R. H. Chan and M. Nikolova, Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise, Inverse Probl. Imag., 2 (2008), 187-204.doi: 10.3934/ipi.2008.2.187.
[13]	J. F. Cai, S. Osher and Z. W. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Sim., 8 (2009), 337-369.doi: 10.1137/090753504.
[14]	X. Cai, R. Chan and T. Zeng, A two-stage image segmentation method using a convex variant of the Mumford-Shah model and thresholding, SIAM J. Imaging Sci., 6 (2013), 368-390.doi: 10.1137/120867068.
[15]	J. Canny, A computational approach to edge detection, IEEE T. Pattern Anal., PAMI-8 (1986), 679-698.doi: 10.1109/TPAMI.1986.4767851.
[16]	V. Caselles, R. Kimmel and G. Sapiro, Geodesic active contours, Computer Vision, 1995. Proceedings., Fifth International Conference on, 1995, 694-699.doi: 10.1109/ICCV.1995.466871.
[17]	F. Catté, P. L. Lions, J. M. Morel and T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM J. Numer. Anal., 29 (1992), 182-193.doi: 10.1137/0729012.
[18]	A. Chambolle, Image segmentation by variational methods: Mumford and shah functional and the discrete approximations, SIAM J. Appl. Math., 55 (1995), 827-863.doi: 10.1137/S0036139993257132.
[19]	A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.
[20]	R. H. Chan, M. Tao and X. M. Yuan, Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imaging Sci., 6 (2013), 680-697.doi: 10.1137/110860185.
[21]	T. F. Chan, S. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Appl. Math., 66 (2006), 1632-1648.doi: 10.1137/040615286.
[22]	G. Dal Maso, Introduction to $\Gamma$-Convergence, Birkhäuser, 1993.doi: 10.1007/978-1-4612-0327-8.
[23]	R. Deriche, Using Canny's criteria to derive a recursively implemented optimal edge detector, Int. J. Comput. Vis., 1 (1987), 167-187.doi: 10.1007/BF00123164.
[24]	R. T. Farouki and C. A. Neff, Analytic properties of plane offset curves, Computer Aided Geometric Design, 7 (1990), 83-99.doi: 10.1016/0167-8396(90)90023-K.
[25]	A. Giacomini, Ambrosio-Tortorelli approximation of quasi-static evolution of brittle fractures, Calc. Var. Partial Differ. Equ., 22 (2005), 129-172.doi: 10.1007/s00526-004-0269-6.
[26]	T. Goldstein, X. Bresson and S. Osher, Geometric applications of the split Bregman method: Segmentation and surface reconstruction, J. Sci. Comput., 45 (2010), 272-293.doi: 10.1007/s10915-009-9331-z.
[27]	T. Goldstein and S. Osher, The split Bregman method for L1 regularized problems, SIAM J. Imaging Sci., 2 (2009), 323-343.doi: 10.1137/080725891.
[28]	W. Guo and M. J. Lai, Box spline wavelet frames for image edge analysis, SIAM J. Imaging Sci., 6 (2013), 1553-1578.doi: 10.1137/120881348.
[29]	Y. Huang, D. Lu and T. Zeng, Two-step approach for the restoration of images corrupted by multiplicative noise, SIAM J. Sci. Comput., 35 (2013), A2856-A2873.doi: 10.1137/120898693.
[30]	M. Kass, A. P. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vis., 1 (1988), 321-331.doi: 10.1007/BF00133570.
[31]	R. Lai and T. F. Chan, A framework for intrinsic image processing on surfaces, Comput. Vis. Image Underst., 115 (2011), 1647-1661.doi: 10.1016/j.cviu.2011.05.011.
[32]	S. Lee, H. Lee, P. Abbeel and A. Y. Ng, Efficient $l_1$ regularized logistic regression, in Proceedings of the National Conference on Artificial Intelligence, Vol. 21, Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006, 401.
[33]	S. Leung and H. Zhao, A grid based particle method for evolution of open curves and surfaces, J. Comput. Phys., 228 (2009), 7706-7728.doi: 10.1016/j.jcp.2009.07.017.
[34]	B. Llanas and S. Lantarón, Edge detection by adaptive splitting, J. Sci. Comput., 46 (2011), 485-518.doi: 10.1007/s10915-010-9416-8.
[35]	W. Y. Ma and B. S. Manjunath, Edgeflow: A technique for boundary detection and image segmentation, IEEE T. Image Process., 9 (2000), 1375-1388.doi: 10.1109/83.855433.
[36]	R. March and M. Dozio, A variational method for the recovery of smooth boundaries, Image Vis. Comput., 15 (1997), 705-712.doi: 10.1016/S0262-8856(97)00002-4.
[37]	E. Meinhardt, E. Zacur, A. F. Frangi and V. Caselles, 3D edge detection by selection of level surface patches, J. Math. Imaging Vis., 34 (2009), 1-16.doi: 10.1007/s10851-008-0118-x.
[38]	C. A. Micchelli, L. X. Shen and Y. S. Xu, Proximity algorithms for image models: Denoising, Inverse Probl. Imag., 27 (2011), 045009, 30pp.doi: 10.1088/0266-5611/27/4/045009.
[39]	C. A. Micchelli, L. X. Shen, Y. S. Xu and X. Y. Zeng, Proximity algorithms for the L1/TV image denoising model, Adv. Comput. Math., 38 (2013), 401-426.doi: 10.1007/s10444-011-9243-y.
[40]	R. Mohieddine and L. A. Vese, An open level set framework for image segmentation and restoration using the Mumford and Shah model, in Proc. SPIE 7873, Computational Imaging IX, 787309, 2011, p787309.doi: 10.1117/12.872457.
[41]	J. J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C.R. Acad. Sci. Paris Sér. A Math., 255 (1962), 2897-2899.
[42]	J. J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.
[43]	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.
[44]	M. Nikolova and M. Ng, Fast image reconstruction algorithms combining half-quadratic regularization and preconditioning, in Proceedings of 2001 International Conference on Image Processing, Vol. 1, IEEE, 2001, 277-280.doi: 10.1109/ICIP.2001.959007.
[45]	M. Nikolova and M. Ng, Analysis of half-quadratic minimization methods for signal and image recovery, SIAM J. Sci. Comput., 27 (2005), 937-966.doi: 10.1137/030600862.
[46]	S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, Multiscale Modeling $&$ Simulation, 4 (2005), 460-489.doi: 10.1137/040605412.
[47]	S. Osher and J. A. Sethian, Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), 12-49.doi: 10.1016/0021-9991(88)90002-2.
[48]	P. Perona and J. Malik, Scale-space and edge-detection using anisotropic diffusion, IEEE T. Pattern Anal., 12 (1990), 629-639.doi: 10.1109/34.56205.
[49]	T. Pock, D. Cremers, H. Bischof and A. Chambolle, An algorithm for minimizing the Mumford-Shah functional, in 12th International Conference on Computer Vision, IEEE, 2009, 1133-1140.doi: 10.1109/ICCV.2009.5459348.
[50]	R. Ramlau and W. Ring, A Mumford-Shah level-set approach for the inversion and segmentation of X-ray tomography data, J. Comput. Phys., 221 (2007), 539-557.doi: 10.1016/j.jcp.2006.06.041.
[51]	L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[52]	G. Sapiro and D. L. Ringach, Anisotropic diffusion of multivalued images with applications to color filtering, IEEE T. Image Process., 5 (1996), 1582-1586.doi: 10.1109/83.541429.
[53]	H. Schaeffer and L. Vese, Active contours with free endpoints, J. Math. Imaging Vis., 49 (2014), 20-36.doi: 10.1007/s10851-013-0437-4.
[54]	S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, in Scale Space and Variational Methods in Computer Vision, Vol. 5567, Springer, Berlin, 2009, 464-476.doi: 10.1007/978-3-642-02256-2_39.
[55]	J. Shah, A common framework for curve evolution, segmentation and anisotropic diffusion, in IEEE Conference on Computer Vision and Pattern Recognition, 1996, 136-142.doi: 10.1109/CVPR.1996.517065.
[56]	J. Shen, A stochastic-variational model for soft Mumford-Shah segmentation, Int. J. Biome., 2006 (2006), 2-16.doi: 10.1155/IJBI/2006/92329.
[57]	Y. Y. Shi, L. L. Wang and X. C. Tai, Geometry of total variation regularized $L^p$-model, J. Comput. Appl. Math., 236 (2012), 2223-2234.doi: 10.1016/j.cam.2011.09.043.
[58]	P. Smereka, Spiral crystal growth, Physica D: Nonlinear Phenomena, 138 (2000), 282-301.doi: 10.1016/S0167-2789(99)00216-X.
[59]	S. M. Smith, Edge Thinning Used in the SUSAN Edge Detector, Technical Report, TR95SMS5, 1995.
[60]	Y. Sun, P. Wu, G. W. Wei and G. Wang, Evolution-operator-based single-step method for image processing, Int. J. Biomed. Imaging, 2006 (2006), 1-28.doi: 10.1155/IJBI/2006/83847.
[61]	Y. Suzuki, T. Takayama, I. N. Motoike and T. Asai, A reaction-diffusion model performing stripe-and spot-image restoration and its LSI implementation, Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 90 (2007), 20-29.doi: 10.1002/ecjc.20243.
[62]	X. C. Tai and C. Wu, Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model, in Scale Space and Variational Methods in Computer Vision, Proceedings, Lecture Notes in Computer Science, Elsevier, 5567, Springer, Berlin-Heidelberg, 2009, 502-513.doi: 10.1007/978-3-642-02256-2_42.
[63]	B. Tang, G. Sapiro and V. Caselles, Color image enhancement via chromaticity diffusion, IEEE T. Image Process., 10 (2001), 701-707.doi: 10.1109/83.918563.
[64]	W. Tao, F. Chang, L. Liu, H. Jin and T. Wang, Interactively multiphase image segmentation based on variational formulation and graph cuts, Pattern Recogn., 43 (2010), 3208-3218.doi: 10.1016/j.patcog.2010.04.014.
[65]	Z. Tari, J. Shah and H. Pien, Extraction of shape skeletons from grayscale images, Computer Vis. Image Und., 66 (1997), 133-146.doi: 10.1006/cviu.1997.0612.
[66]	V. Toponogov, Differential Geometry of Curves and Surfaces: A Concise Guide, Birkhäuser, 2006.
[67]	M. Upmanyu, R. W. Smith and D. J. Srolovitz, Atomistic simulation of curvature driven grain boundary migration, Interface Sci., 6 (1998), 41-58.
[68]	L. L. Wang, Y. Y. Shi and X. C. Tai, Robust edge detection using Mumford-Shah model and binary level set method, in Scale Space and Variational Methods in Computer Vision, Lecture Notes in Computer Science, 6667, Springer, Berlin-Heidelberg, 2012, 291-301.doi: 10.1007/978-3-642-24785-9_25.
[69]	Y. L. Wang, J. F. Yang, W. T. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), 248-272.doi: 10.1137/080724265.
[70]	G. W. Wei and Y. Q. Jia, Synchronization-based image edge detection, EPL (Europhysics Letters), 59 (2002), 814-819.doi: 10.1209/epl/i2002-00115-8.
[71]	C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models, SIAM J. Imaging Sci., 3 (2010), 300-339.doi: 10.1137/090767558.