A Fixed Point Formulation Of The k-Means Algorithm And A Connection To Mumford-Shah
Johnathan M. Bardsley, Aaron Luttman · 2009
In this note, we present a fixed point formulation of the k-means segmentation algorithm and show that the iteration’s fixed points are solutions of the Euler-Lagrange equation for the k-phase Mumford-Shah energy functional. This short note illustrates a connection between the k-means algorithm and Mumford-Shah segmentation via a fixed point formulation of k-means. This connection is ex-plicitly mentioned in [3, 10], but is made theoretically concrete here. However, since k-means itself has been extensively studied, any further analysis of the method would be redundant, hence the shortness of the discussion. Let D ⊂ L∞(Ω) be nonnegative, where Ω ⊂ Rd is a closed, bounded set. The k-means algorithm is a well-known method for segmenting D into k regions [5, 6, 7]. Its formulation is simple: let ess sup x∈Ω D(x) = `0> `1> `2> · · ·> `k−1> `k = ess inf x∈Ω D(x), (1) then the k-means segmentation of D is defined by Ωi = {x ∈ Ω | `i−1 ≥ D> `i}, 1 ≤ i ≤ k, (2) with the `i’s satisfying∫