(chan-vese-model)=
# Chan-Vese model

To overcome the discussed numerical challenges of the Mumford-Shah model
we will discuss a better model for segmentation by {cite:p}`chan_2001`.
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:
```{math}
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:
```{math}
\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
```{math}
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:
```{math}
\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:
```{math}
\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:
```{math}
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 {cite:p}`chan_2006`.

````{prf:theorem} Convex relaxation
For any fixed $c_1, c_2 \R$ a global minimum of the problem above can be
found by computing:
```{math}
\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:
```{math}
\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 {cite:p}`caselles_2007` that allows us to
perform segmentation using the primal-dual optimization approach from
{ref}`s:primal-dual`.

````{prf:theorem} Connection to ROF model
:label: thm:connection_rof
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:
```{math}
\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:
```{math}
\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 {prf:ref}`thm:connection_rof` we can perform the
segmentation step of the alternating Chan-Vese minimization method by
setting
```{math}
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$.