7.2. Chan-Vese model

To overcome the discussed numerical challenges of the Mumford-Shah model we will discuss a better model for segmentation by [CV01]. Regarding the asymptotic behaviour of the Mumford-Shah model for \(\alpha \to +\infty\) yields the Chan-Vese segmentation model, which we discuss in the following.

We can reformulate the approximation of \(f\) with a piecewise constant function \(u_c \in H^1(\Omega \setminus \Gamma)\) by finding optimal constants \(c_1, \dots , c_n \in \R\) for each subregion \(\Omega_i \subset \Omega\). This leads to the following simplified energy functional:

\[E(u, \Gamma) \ = \ E(c_1, \dots , c_m, \Gamma) \ = \ \frac{1}{2} \sum_{i=1}^n \int_\Omega | f(x) - c_i|^2 \, \mathrm{d}x + \beta|\Gamma|.\]

Again, for a fixed segmentation boundary \(\Gamma\) we can compute the optimality condition for one of the optimal constants \(c_j \in \R\) via:

\[\begin{split} \frac{\partial}{\partial c_j} E(c_1, \ldots, c_m, \Gamma) \ &= \ \frac{\partial}{\partial c_j} \left( \frac{1}{2} \sum_{i=1}^n \int_{\Omega_i} | f(x) - c_i|^2 \, \mathrm{d}x + \beta|\Gamma| \right) \\ &= \ \frac{1}{2} \frac{\partial}{\partial c_j} \int_{\Omega_j} | f(x) - c_j|^2 \, \mathrm{d}x \\ &= \ - \int_{\Omega_j} f(x) - c_j \, \mathrm{d}x \ \overset{!}{=} \ 0. \end{split}\]

Since we have assumed \(\Omega_j \neq \emptyset\) we can reformulate this optimality condition to

\[c_j \underbrace{\int_{\Omega_j} 1\, \mathrm{d}x}_{\: = |\Omega_j|} \ = \ \int_{\Omega_j} f(x) \, \mathrm{d}x \quad \Leftrightarrow \quad c_j = \frac{1}{| \Omega_j |} \int_{\Omega_j} f(x) \, \mathrm{d}x,\]

which is the mean value of the image \(f\) in the respective subregion \(\Omega_j\).

Since it is cumbersome to optimize the Chan-Vese energy functional with respect to the segmentation boundary \(\Gamma\) (which is a set), we introduce an indicator function \(\chi\) (for the case of \(m=2\) subregions) via:

\[\chi (x) \ \coloneqq \ \begin{cases} 1 \quad &x \in \Omega_1, \\ 0 \quad &\text{else}. \end{cases}\]

The optimal piecewise constant approximation \(\hat{u}_c\) then becomes:

\[\hat{u}_c \ = \ \chi (x) \cdot \hat{c}_1 + (1 - \chi (x)) \cdot \hat{c}_2,\]

Furthermore, the Chan-Vese segmentation model can now be written with integrals over the full domain \(\Omega\) as:

\[E(c_1, c_2, \chi) \ = \ \frac{\lambda_1}{2} \int_\Omega \chi(x)(f(x) - c_1)^2 \, \mathrm{d}x + \frac{\lambda_2}{2} \int_\Omega(1 - \chi(x))(f(x)-c_2)^2 \, \mathrm{d}x + | \chi |_{TV}.\]

Note, that since \(\chi\) is a discrete function taking only values in \(\{0, 1\}\) it is not differentiable (in a strong sense) and the optimization in the function space \(BV(\Omega; \{0,1\})\) is nonconvex. This problem can be alleviated by the following convex relaxation proposed by [CEN06].

Theorem 7.1 (Convex relaxation)

For any fixed \(c_1, c_2 \R\) a global minimum of the problem above can be found by computing:

\[\min_{\overline{\chi} \in BV (\Omega, [0,1]} E( \overline{\chi}),\]

and then setting for any \(\Omega_1 = \{x \in \Omega : \overline{\chi} \geq \mu \}\) for any \(\mu \in [0,1]\)

Now the relaxed Chan-Vese segmentation model can be minimized alternatingly with an initial indicator function \(\chi_0\) (which can be computed for example with thresholing) via:

\[\begin{split} c_1^{k+1} \ &= \ \mathop{\arg \min}\limits_{c_1 \in \R} \frac{\lambda_1}{2} \int_\Omega \chi^{k}(x) (c_1 - f(x))^2 \, \mathrm{d}x \ = \ \frac{\lambda_1}{|\Omega_1|} \int_{\Omega_1} f(x) \, \mathrm{d}x,\\ c_2^{k+1} \ &= \ \mathop{\arg \min}\limits_{c_2 \in \R} \frac{\lambda_2}{2} \int_\Omega (1-\chi^{k}(x)) (c_2 - f(x))^2 \, \mathrm{d}x \ = \ \frac{\lambda_2}{|\Omega_2|} \int_{\Omega_2} f(x) \, \mathrm{d}x,\\ \chi^{k+1} \ &= \ \mathop{\arg \min}\limits_{\chi \in BV(\Omega; [0,1])} \frac{\lambda_1}{2} \int_\Omega \chi(x)(f(x) - c_1^{k+1})^2 \, \mathrm{d}x \\ & \qquad \qquad \qquad \qquad + \frac{\lambda_2}{2} \int_\Omega(1 - \chi(x))(f(x)-c_2^{k+1})^2 \, \mathrm{d}x + | \chi |_{TV}. \end{split}\]

The last step for computing the current segmentation via the indicator function \(\chi\) can be interpreted as minimal surface problem. Luckily, there is a helpful connection to the already discussed ROF denoising model shown by [CCN07] that allows us to perform segmentation using the primal-dual optimization approach from Primal-dual optimization.

Theorem 7.2 (Connection to ROF model)

Let \(\beta > 0, g \in L^2 (\Omega)\) and let \(\hat{u}\) be the unique solution of the ROF denoising problem. Then for almost any \(t \in \R\), the indicator function:

\[\hat{\chi}(x) \; = \; \begin{cases} 1 \quad \quad \hat{u}(x) > t, \\ 0 \quad \quad \hat{u}(x) \leq t, \end{cases}\]

is a solution to the minimal surface problem:

\[\min_{\overline{\chi} \in BV(\Omega, [0,1]} \int_\Omega \chi (x) (t - g(x)) \mathrm{d}x + \beta| \chi|_{TV},\]

With the help of Theorem 7.2 we can perform the segmentation step of the alternating Chan-Vese minimization method by setting

\[g(x) \ \coloneqq \ - \frac{\lambda_1}{2}(c_1 - f(x))^2 + \frac{\lambda_2}{2}(c_2 - f(x))^2,\]

and thresholding the resulting approximation via the ROF denoising method with \(t=0\).