# American Institute of Mathematical Sciences

August  2013, 7(3): 1099-1113. doi: 10.3934/ipi.2013.7.1099

## Four color theorem and convex relaxation for image segmentation with any number of regions

 1 Hong Kong University of Science and Technology, Hong Kong, China, China 2 City University of Hong Kong, Department of Computer Science, Hong Kong 3 University of Bergen, University of Bergen Bergen

Received  June 2012 Revised  March 2013 Published  September 2013

Image segmentation is an essential problem in imaging science. One of the most successful segmentation models is the piecewise constant Mumford-Shah minimization model. This minimization problem is however difficult to carry out, mainly due to the non-convexity of the energy. Recent advances based on convex relaxation methods are capable of estimating almost perfectly the geometry of the regions to be segmented when the mean intensity and the number of segmented regions are known a priori. The next important challenge is to provide a tight approximation of the optimal geometry, mean intensity and the number of regions simultaneously while keeping the computational time and memory usage reasonable. In this work, we propose a new algorithm that combines convex relaxation methods with the four color theorem to deal with the unsupervised segmentation problem. More precisely, the proposed algorithm can segment any a priori unknown number of regions with only four intensity functions and four indicator (labeling") functions. The number of regions in our segmentation model is decided by one parameter that controls the regularization strength of the geometry, i.e., the total length of the boundary of all the regions. The segmented image function can take as many constant values as needed.
Citation: 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
##### References:

show all references

##### References:
 [1] Li Shen, Eric Todd Quinto, Shiqiang Wang, Ming Jiang. Simultaneous reconstruction and segmentation with the Mumford-Shah functional for electron tomography. Inverse Problems & Imaging, 2018, 12 (6) : 1343-1364. doi: 10.3934/ipi.2018056 [2] Esther Klann, Ronny Ramlau, Wolfgang Ring. A Mumford-Shah level-set approach for the inversion and segmentation of SPECT/CT data. Inverse Problems & Imaging, 2011, 5 (1) : 137-166. doi: 10.3934/ipi.2011.5.137 [3] Antonin Chambolle, Francesco Doveri. Minimizing movements of the Mumford and Shah energy. Discrete & Continuous Dynamical Systems - A, 1997, 3 (2) : 153-174. doi: 10.3934/dcds.1997.3.153 [4] Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems & Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001 [5] Giovanna Citti, Maria Manfredini, Alessandro Sarti. Finite difference approximation of the Mumford and Shah functional in a contact manifold of the Heisenberg space. Communications on Pure & Applied Analysis, 2010, 9 (4) : 905-927. doi: 10.3934/cpaa.2010.9.905 [6] Zhenhua Zhao, Yining Zhu, Jiansheng Yang, Ming Jiang. Mumford-Shah-TV functional with application in X-ray interior tomography. Inverse Problems & Imaging, 2018, 12 (2) : 331-348. doi: 10.3934/ipi.2018015 [7] Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas. A new proof of the four-colour theorem. Electronic Research Announcements, 1996, 2: 17-25. [8] Tomáš Roubíček. On certain convex compactifications for relaxation in evolution problems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (2) : 467-482. doi: 10.3934/dcdss.2011.4.467 [9] Jean-François Babadjian, Clément Mifsud, Nicolas Seguin. Relaxation approximation of Friedrichs' systems under convex constraints. Networks & Heterogeneous Media, 2016, 11 (2) : 223-237. doi: 10.3934/nhm.2016.11.223 [10] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [11] 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 [12] 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 [13] Weiran Sun, Min Tang. A relaxation method for one dimensional traveling waves of singular and nonlocal equations. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1459-1491. doi: 10.3934/dcdsb.2013.18.1459 [14] Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543 [15] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [16] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [17] Zhenlin Guo, Ping Lin, Guangrong Ji, Yangfan Wang. Retinal vessel segmentation using a finite element based binary level set method. Inverse Problems & Imaging, 2014, 8 (2) : 459-473. doi: 10.3934/ipi.2014.8.459 [18] Yukie Goto, Danielle Hilhorst, Ehud Meron, Roger Temam. Existence theorem for a model of dryland vegetation. Discrete & Continuous Dynamical Systems - B, 2011, 16 (1) : 197-224. doi: 10.3934/dcdsb.2011.16.197 [19] Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038 [20] J. Delon, A. Desolneux, Jose-Luis Lisani, A. B. Petro. Automatic color palette. Inverse Problems & Imaging, 2007, 1 (2) : 265-287. doi: 10.3934/ipi.2007.1.265

2018 Impact Factor: 1.469