A Convex Approach to K-Means Clustering and Image Segmentation

Laurent Condat

TL;DR

This paper introduces a novel convex formulation for K-means clustering and image segmentation, which can be solved efficiently using a primal-dual optimization algorithm. This approach offers a principled way to find global optima for these problems, overcoming limitations of traditional heuristic methods.

What Problem Does This Paper Address?

The paper tackles the classic K-means clustering problem and its extension to image segmentation. K-means aims to partition data points into a fixed number of clusters (K) by minimizing the sum of squared distances to cluster centroids. Image segmentation extends this by adding a spatial regularization term, penalizing the perimeter of regions to encourage smoother boundaries, akin to the Mumford-Shah model. While K-means is NP-hard for dimensions greater than 2, and image segmentation is even more challenging, existing methods often rely on heuristics that converge to local minima and are sensitive to initialization. The authors seek a method that can find the global optimum for these problems.

Methods

The core contribution is a convex formulation of the K-means and image segmentation problems. This is achieved by:

  • Discretizing the Search Space: Instead of allowing centroids to be anywhere in $\mathbb{R}^d$, the authors restrict them to a finite set of candidate points ($\Gamma$). This transforms the problem into finding an assignment of data points to these candidates.
  • Lifting and Convex Relaxation: The problem is reformulated using an "assignment array" ($z$) and then relaxed into a convex optimization problem. This involves replacing the discrete assignment constraint with its convex hull (a simplex) and introducing a ball constraint for the $L_{1,\infty}$ norm to control the number of active clusters.
  • Primal-Dual Splitting Algorithm: To solve the resulting convex problem efficiently, the authors adapt the Chambolle-Pock primal-dual algorithm. This algorithm is well-suited for problems involving sums of convex functions and linear operators, and it's designed to handle the specific constraints and terms introduced in their formulation. They also propose a simplified version for the pure K-means case ($\lambda=0$).

Datasets

The paper evaluates its method on:

  • Synthetic Point Cloud Data: A dataset of $N=3000$ points in $d=2$ dimensions is used for K-means clustering experiments.
  • Real-World Images: Three standard images (sunflower, ladybug, parrot) are used for color image quantization and segmentation experiments. The color space used is CIELAB, chosen for its perceptual uniformity.

No new datasets are introduced; existing standard datasets are used for evaluation.

Key Insights and Ideas

  • Convexity as a Path to Global Optima: By reformulating the problem into a convex optimization framework, the authors provide a theoretical guarantee of finding the global optimum, a significant improvement over heuristic K-means algorithms.
  • The Power of Lifting: The "lifting" technique, by introducing auxiliary variables that represent assignments, is crucial for enabling the convex relaxation.
  • Efficient Solvability: The development of a specialized primal-dual algorithm makes the proposed convex formulation computationally tractable, even for image-sized problems.
  • Soft vs. Hard Assignments: For segmentation, the method naturally produces "soft" assignments (pixel belonging to multiple regions with different proportions), which can be beneficial at edges. This can be post-processed to obtain hard assignments if needed.
  • Candidate Set Importance: The choice of the candidate set $\Gamma$ is important. While the method can find the global optimum for the discretized problem, the quality of the solution for the original problem depends on how well $\Gamma$ represents the true cluster centers.

Key Results

  • Exact K-Means Solutions: For K-means clustering on synthetic data, the algorithm converges to the exact solution of the discretized problem, and in cases where the solution is binary (meaning centroids coincide with data points or grid points), it finds the global optimum.
  • Accurate Image Quantization: For color image quantization, the method consistently finds binary solutions, meaning the palette of $K$ colors is effectively selected, and the resulting quantized images are global solutions.
  • Successful Image Segmentation: For image segmentation, the method generally produces good results, yielding segmented images with appropriate colors and smooth boundaries. In most cases, the method successfully finds a solution with $K$ dominant colors.
  • Computational Efficiency: The algorithm, while complex, is shown to be efficient enough to handle image-sized problems, taking "several tenths of minutes" to generate results over "several thousands of iterations."

Limitations and Future Work

  • Dependence on Candidate Set: The paper acknowledges that the quality of the solution for the original K-means problem depends on the choice of the candidate set $\Gamma$. If $\Gamma$ does not contain the true centroids, the solution will be suboptimal for the original problem.
  • Soft Assignments in Segmentation: While soft assignments are a feature, they can result in "blur" at edges. The paper mentions that this can be removed by rounding, but it's a point of consideration.
  • Failure Cases in Segmentation: In one specific segmentation example (parrot with K=6), the method did not yield a clear set of 6 dominant colors, suggesting limitations in cases with complex color distributions or when the number of dominant colors is hard to discern.
  • Future Work: The paper implies that further exploration of candidate set selection strategies and potential improvements to the rounding process for segmentation could be valuable. The efficiency of the algorithm could also be a subject of further optimization.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{condat2017convex,
  author = {Laurent Condat},
  title = {{A Convex Approach to K-Means Clustering and Image Segmentation}},
  booktitle = {EMMCVPR},
  year = {2017},
  doi = {10.1007/978-3-319-78199-0\_15},
}
Figure