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

Ruiliang Zhang, Xavier Bresson, Tony F. Chan, Xue Cheng Tai

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1099-1113
Number of pages15
JournalInverse Problems and Imaging
Issue number3
StatePublished - Aug 2013
Externally publishedYes


  • Convex relaxation method
  • Four color theorem
  • Mumford-Shah model
  • Unsupervised segmentation

ASJC Scopus subject areas

  • Analysis
  • Modeling and Simulation
  • Discrete Mathematics and Combinatorics
  • Control and Optimization


Dive into the research topics of 'Four color theorem and convex relaxation for image segmentation with any number of regions'. Together they form a unique fingerprint.

Cite this