×

A fast edge detection algorithm using binary labels. (English) Zbl 1332.65027

Summary: 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.

MSC:

65D15 Algorithms for approximation of functions
68W40 Analysis of algorithms
90C90 Applications of mathematical programming
65M32 Numerical methods for inverse problems for initial value and initial-boundary value problems involving PDEs

Software:

RecPF
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Alvarez, Image selective smoothing and edge detection by nonlinear diffusion II,, SIAM J. Numer. Anal., 29, 845 (1992) · Zbl 0766.65117
[2] L. Ambrosio, Approximation of functions depending on jumps by elliptic functions via \(\Gamma \)-convergence,, Comm. Pure Appl. Math., 43, 999 (1990) · Zbl 0722.49020
[3] L. Ambrosio, <em>On the Approximation of Functionals Depending on Jumps by Quadratic, Elliptic Functionals,</em>, Boll. Un. Mat. Ital. (1992)
[4] N. Badshah, Image selective segmentation under geometrical constraints using an active contour approach,, Commun. Comput. Phys., 7, 759 (2010) · Zbl 1365.65038
[5] S. Basu, Implicit evolution of open ended curves,, in IEEE International Conference on Image Processing, 261 (2007)
[6] B. Berkels, Extracting grain boundaries and macroscopic deformations from images on atomic scale,, J. Sci. Comput., 35, 1 (2008) · Zbl 1203.65039
[7] A. Braides, <em>Approximation of Free-Discontinuity Problems</em>,, Springer-Verlag (1998) · Zbl 0909.49001
[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, 620 (1967) · Zbl 0186.23807
[9] X. Bresson, Fast dual minimization of the vectorial total variation norm and applications to color image processing,, Inverse Probl. Imag., 2, 455 (2008) · Zbl 1188.68337
[10] A. Brook, Variational restoration and edge detection for color images,, J. Math. Imaging Vis., 18, 247 (2003) · Zbl 1020.68079
[11] E. S. Brown, <em>A Convex Relaxation Method for a Class of Vector-Valued Minimization Problems with Applications to Mumford-Shah Segmentation</em>,, UCLA cam report, 10 (2010)
[12] J. F. Cai, Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise,, Inverse Probl. Imag., 2, 187 (2008) · Zbl 1154.94306
[13] J. F. Cai, Split Bregman methods and frame based image restoration,, Multiscale Model. Sim., 8, 337 (2009) · Zbl 1189.94014
[14] X. Cai, A two-stage image segmentation method using a convex variant of the Mumford-Shah model and thresholding,, SIAM J. Imaging Sci., 6, 368 (2013) · Zbl 1283.52011
[15] J. Canny, A computational approach to edge detection,, IEEE T. Pattern Anal., PAMI-8, 679 (1986)
[16] V. Caselles, Geodesic active contours,, Computer Vision, 694 (1995) · Zbl 0894.68131
[17] F. Catté, Image selective smoothing and edge detection by nonlinear diffusion,, SIAM J. Numer. Anal., 29, 182 (1992) · Zbl 0746.65091
[18] A. Chambolle, Image segmentation by variational methods: Mumford and shah functional and the discrete approximations,, SIAM J. Appl. Math., 55, 827 (1995) · Zbl 0830.49015
[19] A. Chambolle, An algorithm for total variation minimization and applications,, J. Math. Imaging Vis., 20, 89 (2004) · Zbl 1366.94048
[20] R. H. Chan, Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers,, SIAM J. Imaging Sci., 6, 680 (2013) · Zbl 1279.68322
[21] T. F. Chan, Algorithms for finding global minimizers of image segmentation and denoising models,, SIAM J. Appl. Math., 66, 1632 (2006) · Zbl 1117.94002
[22] G. Dal Maso, <em>Introduction to \(\Gamma \)-Convergence,</em>, Birkhäuser (1993) · Zbl 0816.49001
[23] R. Deriche, Using Canny’s criteria to derive a recursively implemented optimal edge detector,, Int. J. Comput. Vis., 1, 167 (1987)
[24] R. T. Farouki, Analytic properties of plane offset curves,, Computer Aided Geometric Design, 7, 83 (1990) · Zbl 0718.53003
[25] A. Giacomini, Ambrosio-Tortorelli approximation of quasi-static evolution of brittle fractures,, Calc. Var. Partial Differ. Equ., 22, 129 (2005) · Zbl 1068.35189
[26] T. Goldstein, Geometric applications of the split Bregman method: Segmentation and surface reconstruction,, J. Sci. Comput., 45, 272 (2010) · Zbl 1203.65044
[27] T. Goldstein, The split Bregman method for L1 regularized problems,, SIAM J. Imaging Sci., 2, 323 (2009) · Zbl 1177.65088
[28] W. Guo, Box spline wavelet frames for image edge analysis,, SIAM J. Imaging Sci., 6, 1553 (2013) · Zbl 1278.62100
[29] Y. Huang, Two-step approach for the restoration of images corrupted by multiplicative noise,, SIAM J. Sci. Comput., 35 (2013) · Zbl 1291.65061
[30] M. Kass, Snakes: Active contour models,, Int. J. Comput. Vis., 1, 321 (1988)
[31] R. Lai, A framework for intrinsic image processing on surfaces,, Comput. Vis. Image Underst., 115, 1647 (2011)
[32] S. Lee, Efficient \(l_1\) regularized logistic regression,, in Proceedings of the National Conference on Artificial Intelligence (1999)
[33] S. Leung, A grid based particle method for evolution of open curves and surfaces,, J. Comput. Phys., 228, 7706 (2009) · Zbl 1173.65307
[34] B. Llanas, Edge detection by adaptive splitting,, J. Sci. Comput., 46, 485 (2011) · Zbl 1270.94020
[35] W. Y. Ma, Edgeflow: A technique for boundary detection and image segmentation,, IEEE T. Image Process., 9, 1375 (2000) · Zbl 0968.68176
[36] R. March, A variational method for the recovery of smooth boundaries,, Image Vis. Comput., 15, 705 (1997)
[37] E. Meinhardt, 3D edge detection by selection of level surface patches,, J. Math. Imaging Vis., 34, 1 (2009) · Zbl 1493.68383
[38] C. A. Micchelli, Proximity algorithms for image models: Denoising,, Inverse Probl. Imag., 27 (2011) · Zbl 1216.94015
[39] C. A. Micchelli, Proximity algorithms for the L1/TV image denoising model,, Adv. Comput. Math., 38, 401 (2013) · Zbl 1275.65014
[40] R. Mohieddine, An open level set framework for image segmentation and restoration using the Mumford and Shah model,, in Proc. SPIE 7873 (7873)
[41] J. J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien,, C.R. Acad. Sci. Paris Sér. A Math., 255, 2897 (1962) · Zbl 0118.10502
[42] J. J. Moreau, Proximité et dualité dans un espace hilbertien,, Bull. Soc. Math. France, 93, 273 (1965) · Zbl 0136.12101
[43] D. Mumford, Optimal approximations by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math, 42, 577 (1989) · Zbl 0691.49036
[44] M. Nikolova, Fast image reconstruction algorithms combining half-quadratic regularization and preconditioning,, in Proceedings of 2001 International Conference on Image Processing, 277 (2001)
[45] M. Nikolova, Analysis of half-quadratic minimization methods for signal and image recovery,, SIAM J. Sci. Comput., 27, 937 (2005) · Zbl 1141.49318
[46] S. Osher, An iterative regularization method for total variation-based image restoration,, Multiscale Modeling \(&\) Simulation, 4, 460 (2005) · Zbl 1090.94003
[47] S. Osher, Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations,, J. Comput. Phys., 79, 12 (1988) · Zbl 0659.65132
[48] P. Perona, Scale-space and edge-detection using anisotropic diffusion,, IEEE T. Pattern Anal., 12, 629 (1990)
[49] T. Pock, An algorithm for minimizing the Mumford-Shah functional,, in 12th International Conference on Computer Vision, 1133 (2009)
[50] R. Ramlau, A Mumford-Shah level-set approach for the inversion and segmentation of X-ray tomography data,, J. Comput. Phys., 221, 539 (2007) · Zbl 1114.68077
[51] L. I. Rudin, Nonlinear total variation based noise removal algorithms,, Physica D: Nonlinear Phenomena, 60, 259 (1992) · Zbl 0780.49028
[52] G. Sapiro, Anisotropic diffusion of multivalued images with applications to color filtering,, IEEE T. Image Process., 5, 1582 (1996)
[53] H. Schaeffer, Active contours with free endpoints,, J. Math. Imaging Vis., 49, 20 (2014) · Zbl 1291.68423
[54] S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage,, in Scale Space and Variational Methods in Computer Vision, 464 (5567)
[55] J. Shah, A common framework for curve evolution, segmentation and anisotropic diffusion,, in IEEE Conference on Computer Vision and Pattern Recognition, 136 (1996)
[56] J. Shen, A stochastic-variational model for soft Mumford-Shah segmentation,, Int. J. Biome., 2006, 2 (2006)
[57] Y. Y. Shi, Geometry of total variation regularized \(L^p\)-model,, J. Comput. Appl. Math., 236, 2223 (2012) · Zbl 1259.94020
[58] P. Smereka, Spiral crystal growth,, Physica D: Nonlinear Phenomena, 138, 282 (2000) · Zbl 0957.80002
[59] S. M. Smith, <em>Edge Thinning Used in the SUSAN Edge Detector,</em>, Technical Report (1995)
[60] Y. Sun, Evolution-operator-based single-step method for image processing,, Int. J. Biomed. Imaging, 2006, 1 (2006)
[61] Y. Suzuki, 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, 20 (2007)
[62] X. C. Tai, Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model,, in Scale Space and Variational Methods in Computer Vision, 502 (5567) · Zbl 1371.94362
[63] B. Tang, Color image enhancement via chromaticity diffusion,, IEEE T. Image Process., 10, 701 (2001) · Zbl 1037.68792
[64] W. Tao, Interactively multiphase image segmentation based on variational formulation and graph cuts,, Pattern Recogn., 43, 3208 (2010) · Zbl 1206.68281
[65] Z. Tari, Extraction of shape skeletons from grayscale images,, Computer Vis. Image Und., 66, 133 (1997)
[66] V. Toponogov, <em>Differential Geometry of Curves and Surfaces: A Concise Guide</em>,, Birkhäuser (2006) · Zbl 1092.53003
[67] M. Upmanyu, Atomistic simulation of curvature driven grain boundary migration,, Interface Sci., 6, 41 (1998)
[68] L. L. Wang, Robust edge detection using Mumford-Shah model and binary level set method,, in Scale Space and Variational Methods in Computer Vision, 291 (6667)
[69] Y. L. Wang, A new alternating minimization algorithm for total variation image reconstruction,, SIAM J. Imaging Sci., 1, 248 (2008) · Zbl 1187.68665
[70] G. W. Wei, Synchronization-based image edge detection,, EPL (Europhysics Letters), 59, 814 (2002)
[71] C. Wu, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models,, SIAM J. Imaging Sci., 3, 300 (2010) · Zbl 1206.90245
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.