Source-linked AI summary
An efficient iterative thresholding method for image segmentation
Dong Wang, Haohan Li, Xiaoyu Wei, Xiaoping Wang
TL;DR
The paper addresses efficient minimization of the piecewise constant Mumford–Shah functional for multi-phase image segmentation. It replaces perimeter terms with a non-local multi-phase energy and alternates convolutions with thresholding. The method has O(N log N) cost per iteration, decaying total energy, and reported stable convergence across tested images and resolutions.
Problem
Numerical minimization of the piecewise constant Mumford–Shah model is difficult because the formulation is non-convex and its Euler–Lagrange equation is nonlinear.
Method
The method approximates perimeter terms with a heat-kernel convolution-based non-local multi-phase energy and minimizes it through iterative convolution and thresholding.
Results
The algorithm has O(N log N) complexity per iteration, decreasing total energy, and converges in reported tests across multiple image resolutions.
Takeaways & Limitations
The numerical results support an efficient, stable iterative method whose iteration count can be independent of spatial resolution for a given image.
Takeaways & Limitations
The method uses a convex relaxation that is stated to be convex when the region constants Ci are fixed.
Abstract
from arXiv · showhide
We proposed an efficient iterative thresholding method for multi-phase image segmentation. The algorithm is based on minimizing piecewise constant Mumford-Shah functional in which the contour length (or perimeter) is approximated by a non-local multi-phase energy. The minimization problem is solved by an iterative method. Each iteration consists of computing simple convolutions followed by a thresholding step. The algorithm is easy to implement and has the optimal complexity $O(N \log N)$ per iteration. We also show that the iterative algorithm has the total energy decaying property. We present some numerical results to show the efficiency of our method.
1. Introduction.
The paper situates its method within variational image segmentation and the piecewise constant Mumford–Shah model, whose numerical minimization is difficult because of non-convexity. It proposes an iterative thresholding approach that replaces perimeter terms with a non-local multi-phase energy and alternates convolution with thresholding.
- Variational segmentation obtains image partitions by minimizing a chosen energy, with Mumford–Shah among the most extensively studied models.
- The piecewise constant Mumford–Shah model represents images using finitely many values, including the two-phase Chan–Vese formulation.
- The Chan–Vese energy combines region-fitting terms with a perimeter penalty, while its region means are averages inside and outside the contour.
- The Euler–Lagrange equation is nonlinear and requires regularization when |∇φ| = 0, motivating more efficient solution strategies.
- Prior approaches include phase-field, MBO threshold dynamics, framelet, split Bregman, clustering, and primal-dual methods for related segmentation problems.
- The proposed method approximates perimeter by a convolution-based non-local multi-phase energy and alternates convolution with thresholding, with O(N log N) complexity per iteration and total-energy decay.
2. An efficient iterative thresholding method for image segmentation.
The method relaxes multi-phase Chan–Vese segmentation into a convex formulation and approximates inter-region boundary lengths using heat-kernel convolutions. Linearizing the approximate energy yields an iterative thresholding scheme whose total energy decreases for every positive time-step parameter.
- The algorithm seeks an n-phase partition of an image domain that minimizes the piecewise constant Chan–Vese functional.
- For δt ≪ 1, heat-kernel convolutions approximate the lengths of boundaries between phase regions.
- A non-convex partition problem is relaxed to a convex problem over functions constrained between 0 and 1.
- The relaxed problem is equivalent to the original problem, so the relaxed formulation can be solved instead.
- The next iterate is obtained by linearizing the approximate energy and minimizing the resulting linear functional over the relaxed feasible set.
- The total energy decreases for every δt > 0, so the iterative algorithm converges to a minimum from any initial partition.
Algorithm: I
Each iteration computes phase-wise convolutions, thresholds the resulting values to update characteristic functions, and stops when successive partitions change below a tolerance. FFT implementation gives O(N log(N)) cost per iteration.
- The algorithm initializes phase characteristic functions and a tolerance parameter before iterating.
- Step 1 computes the required phase-wise convolutions for all n regions.
- Step 2 thresholds the convolution results to update the phase characteristic functions.
- Step 3 measures the normalized L2 difference between successive iterations and uses the tolerance to stop when pixel changes are sufficiently small.
- FFT computes the convolutions with O(Nlog(N)) complexity, making the total cost per iteration O(Nlog(N)).
3. Numerical Results.
The numerical tests show that the iterative thresholding method segments cameraman, synthetic color, and flower images efficiently, with energy decay and stable convergence across tested settings.
- Cameraman: 15 iterations and 0.1188 seconds produced a steady-state two-phase segmentation of the cameraman image.The test used δt = 0.03 and λ = 0.01.
- Cameraman: The normalized energy decays monotonically, rapidly during the first few iterations, and nearly reaches steady state before 10 iterations.
- Parameter study: Changing λ alters segmentation behavior: λ = 0.025 smooths small structures, whereas λ = 0.001 detects more noisy regions.The parameter controls the relative importance of contour length and the data term.
- Synthetic color image: 7–8 iterations were sufficient across resolutions from 128 × 128 to 512 × 512, with runtimes of 0.0444, 0.1333, and 0.6706 seconds.The synthetic color image used four-phase segmentation with δt = 0.01 and λ = 0.003.
- Flower image: The flower image converged in 20 iterations for two-phase segmentation and 18 iterations for four-phase segmentation, taking 0.6751 and 1.1007 seconds respectively.
- Overall findings: The reported experiments support a stable method whose convergence-iteration count is independent of spatial resolution for a given image.The paper also reports O(N log N) computational complexity per iteration.
Appendix A. Proof of Lemma 2.1.
The appendix proves the lemma by contradiction, analyzing perturbations of a minimizer and deriving derivative identities for the relevant phase averages. These calculations establish the stated contradiction that v(x) = u(x, 0) cannot be a minimizer.
- The proof assumes a minimizer v in K and, when v is outside S, constructs a positive-measure set A and perturbation parameter ϵ.
- The perturbation changes only the phase averages C_l and C_k, while the other C_m remain independent of t.
- The appendix evaluates the first- and second-order derivative terms using direct calculations and the independence of the integrand quantities from Ω.
- The resulting contradiction shows that v(x) = u(x, 0) cannot be a minimizer.
- The proof combines identities (B.1), (B.2), and (B.3) to obtain equation (2.17).