The coarea formula for BV functions

Today, we will discuss the coarea formula for $BV$ functions, established by Fleming and Rishel in 1960 (W. Fleming, R. Rishel, An integral formula for total gradient variation, Arch. Math. 11 (1960), 218-222.)

Let us first recall the lower semicontinuity property of the total variation with respect to the strong convergence in $L^1(\Omega)$:
Let $\{u_n\}_{n\in\Omega}$ be a sequence in $BV(\Omega)$ strongly converging to some $u$ in $L^1(\Omega)$ and satisfying $|u_{n}|_{BV} < \infty$. Then $u\in BV(\Omega)$ and $$|u|_{BV(\Omega)} \leq \lim\inf_{n\rightarrow \infty} |u_n|_{BV(\Omega)}.$$ The coarea formula is as stated as follows:

Coarea formula: Let $u$ be a given function in $BV(\Omega)$. Then for almost every $t$ in $\mathbb{R}$, the level set $E_t=\{ x\in \Omega \subset \mathbb{R}^N: u(x) > t\}$ of $u$ is a set of finite perimeter in $\Omega$, and
\begin{align}
&Du=\int_{-\infty}^{\infty} D\chi_{E_t}\, dt,\\
&|u|_{BV(\Omega)}=|Du|(\Omega)=\int_{-\infty}^{\infty} \int_{\Omega}|D\chi_{E_t}|\, dt.
\end{align}
The second assertion above is often written in terms of the perimeter of level sets as follows:
\begin{align}
|u|_{BV(\Omega)}=\int_{-\infty}^{\infty} Per(E_t, \Omega) dt,
\end{align}
where $Per(E_t, \Omega)=\mathcal{H}^{N-1}(\Omega \cap \partial E_t)$ is the perimeter of the level set $E_t$.

Proof of the coarea formula: We follow the treatment of Variational Analysis in Sobolev and BV spaces by Attouch et al.

Part I: Proof of $|Du|(\Omega) \leq \int_{-\infty}^{\infty}\int_{\Omega}|D\chi_{E_t}|\, dt$:

Let us assume that $D\chi_{E_t}$ belongs to $\mathbf{M}(\Omega, \mathbb{R}^N)$, the set of all $\mathbb{R}^N-$ valued Borel measures which is the set of all the $\sigma-$ additive set functions $\mu:\mathcal{B}(\Omega)\rightarrow \mathbb{R}^N$, with $\mu(\emptyset)=0$. For all $t$ in $\mathbb{R}$ set
\begin{equation}
f_t=\left\{
\begin{array}{ll}
\chi_{E_t} & \mbox{if } t \geq 0 \\
-\chi_{\Omega \backslash E_t} & \mbox{if } t < 0 \end{array} \right. \end{equation} It is easy to see that $u(x)=\int_{-\infty}^{\infty}f_t(x)\,dt$ for all $x\in \Omega$. For all $\bar{\phi} \in C_c^1(\Omega, \mathbb{R}^N)$ we have \begin{align*} &\langle Du, \bar{\phi} \rangle \\ &= -\int_{\Omega} u \, \mbox{div} \,\bar{\phi} \, dx \\ & = - \int_{\Omega} \int_{-\infty}^{\infty} f_t \, \mbox{div} \,\bar{\phi} \, dt\,dx\\ &= - \int_{\Omega} \int_{-\infty}^{0} f_t \, \mbox{div} \,\bar{\phi} \, dt\,dx -\int_{\Omega} \int_{0}^{\infty} f_t \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= \int_{\Omega} \int_{-\infty}^{0} \chi_{\Omega \backslash E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx -\int_{\Omega} \int_{0}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &=\int_{\Omega} \int_{-\infty}^{0} (1-\chi_{E_t}) \, \mbox{div} \,\bar{\phi} \, dt\,dx -\int_{\Omega} \int_{0}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &=\int_{\Omega} \int_{-\infty}^{0} \mbox{div} \,\bar{\phi} \, dt\,dx - \int_{\Omega} \int_{-\infty}^{0} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx-\int_{\Omega} \int_{0}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= \int_{\Omega} \int_{-\infty}^{0} \mbox{div} \,\bar{\phi} \, dt\,dx-\int_{\Omega} \int_{-\infty}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= 0-\int_{\Omega} \int_{-\infty}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= \int_{-\infty}^{\infty} \langle D\chi_{E_t}, \bar{\phi}\rangle \,dt \end{align*} Hence, $Du=\int_{-\infty}^{\infty} D\chi_{E_t}\, dt$, and $|Du|(\Omega) \leq \int_{-\infty}^{\infty}\int_{\Omega}|D\chi_{E_t}|\, dx dt$.

Part II: (coverse) Proof of $\int_{-\infty}^{\infty}\int_{\Omega}|D\chi_{E_t}|\, dxdt\leq |Du|(\Omega) $:


Step i. We first assume that $u$ belongs to the space $\mathcal{A}(\Omega)$ of piecewise linear and continuous functions in $\Omega$. By linearity, one can assume that $u=a\cdot x+b$ with $a\in \mathbb{R}^N$ and $b\in \mathbb{R}$, so that

\begin{align*}
&\int_{\Omega} |D\chi_{E_t}|\\
&=\mathcal{H}(\Omega \cap \partial E_t)\\
&=\mathcal{H}(\Omega \cap \{x| a\cdot x +b=t\})\\
&=\int_{\Omega \cap \{x| a\cdot x +b=t\}} d\mathcal{H}^{N-1}(x)\\
&=\int_{\{x| a\cdot x +b=t\}}\chi_{\Omega}(x)\, d\mathcal{H}^{N-1}(x)
\end{align*}
Thus we get,
\begin{align*}
&\int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_t}|\, dx dt\\
&=|a|\mathcal{L}(\Omega)\\
&=\int_{\{x| a\cdot x +b=t\}}\chi_{\Omega}(x)\, d\mathcal{H}^{N-1}(x)\\
&=\int_{\Omega} |Du|
\end{align*}
Hence we have,
\begin{align*}
\int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_t}|\, dx dt=|Du|(\Omega) \dots \mbox{ if } u=a\cdot x+b.
\end{align*}

Step ii. Now we prove that $\int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_t}|\, dx dt\leq|Du|(\Omega)$ for all $u\in BV(\Omega)$. We know that the space of piecewise linear and continuous functions $\mathcal{A}(\Omega)$ is dense in $W^{1, 1}(\Omega)$ when equipped with the strong topology. We also know that the space $C^{\infty}\cap W^{1, 1}(\Omega)$ is dense in $BV$ when equipped with the intermediate convergence. Thus, there exists a sequence $\{u_n\}_{n\in \mathbb{N}} \in \mathcal{A}(\Omega)$ such that $u_n\rightharpoonup u$ for the intermediate convergence. For each of the functions $u_n$ we set $E_{n, t}:=\{x\in \Omega: u_n(x) > t\}$. Due to the intermediate convergence, we have
\begin{align*}
&\int_{\Omega}|Du|=\lim_{n\rightarrow \infty}\int_{\Omega}|Du_n| \dots \mbox{the intermediate convergence}\\
&=\lim_{n\rightarrow \infty} \int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_{n,t}}|\, dx dt \dots \mbox{from step i}\\
&\geq \int_{-\infty}^{\infty} \lim\inf_{n\rightarrow \infty} \int_{\Omega} |D\chi_{E_{n,t}}|\, dx dt \dots \mbox{Fatou's lemma}\\
\end{align*}
From the intermediate convergence we also have $u_n\rightarrow u$ in $L^1(\Omega)$. i.e.
\begin{align*}
\int_{\Omega} |u_n-u|=\int_{\Omega} \int_{-\infty}^{\infty} |\chi_{E_{n,t}}-\chi_{E_t}|\ dt dx = \int_{-\infty}^{\infty} \Big(\int_{\Omega} |\chi_{E_{n,t}}-\chi_{E_t}|\ dx \Big) dt=0.
\end{align*}
Thus, for a subsequence $E_{n_m, t}$, and for almost all $t \in \mathbb{R}$, $\chi_{E_{n_m, t}}\rightarrow \chi_{E_{n, t}}$ strongly in $L^1(\Omega)$. The lower semicontinuity of the total variation with respect to the strong convergence in $L^1(\Omega)$ we get $\lim\inf_{n\rightarrow \infty} \int_{\Omega} |D\chi_{E_{n_m,t}}|\, dx \geq \int_{\Omega} |D\chi_{E_{t}}|\, dx$. Thus, we get,
$$ \int_{\Omega}|Du| \geq \int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_{t}}|\, dx dt. $$
This completes the proof!

(By the way, step ii also proves that $D\chi_{E_t} \in \mathbf{M}(\Omega, \mathbb{R}^N)$ for a.e. $t\in \mathbb{R}$, something that we used in Part I of the proof.)

Hausdorff measure and dimension

Let us talk about Hausdorff measure $\mathcal{H}^s$ named after Felix Hausdorff, which comes up in image processing often. These measures allow us to measure very small subsets of $\mathbb{R}^n$. The idea is that $A$ is an $s-$ dimensional subset of $\mathbb{R}^n$ if $0<\mathcal{H}^s(A)<\infty$. We will follow the notation and treatment of Evans and Gariepy.

Felix Hausdorff

Definitions:
(i) Let $A\subset \mathbb{R}^n$, $0\leq s < \infty$, $0<\delta\leq \infty$. Define $$\mathcal{H}^s_{\delta}(A)=\inf \Big\{ \sum_{j=1}^{\infty} \alpha(s) \Big( \frac{\mbox{diam}(C_j)}{2} \Big)^s \, \Big\vert \,A\subset \cup_{j=1}^{\infty}C_j, \mbox{diam}(C_j)\leq \delta \Big\},$$ where $\{C_j\}\subset \mathbb{R}^n$ is the covering of the set $A$ and $\alpha(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma(\frac{s}{2}+1)}.$ Here $\Gamma(s)=\int_0^{\infty}e^{-x}x^{s-1}\,dx,\,\,(0< s<\infty),$ is the usual gamma function. (ii) The $s-$dimensional Hausdorff measure of $A$ is denoted by $\mathcal{H}^s(A)$ and it is defined as the limit:
$$ \mathcal{H}^s(A)=\lim_{\delta\rightarrow 0}\mathcal{H}^s_{\delta}(A)=\sup_{\delta >0} \mathcal{H}^s_{\delta}(A).$$

The book: 'Measure theory and fine properties of functions' by Evans and Gariepy includes the normalizing constant $\alpha(s)$ in the definition, whereas some other authors do not include this constant. The constant $\alpha(s)$ is included because if $s$ is an integer, then $\mathcal{H}^s(A)$ is equal to the $s-$dimensional surface area for nice sets (graph of Lipschitz function).


Some properties of Hausdorff measure:
1.$\mathcal{H}^s$ is a Borel regular measure. Refer to E.G. for the proof.

2. Let us consider a Hausdorff measure $\mathcal{H}^0$ of a singleton $\{a\}\in \mathbb{R}^n$. First note that $\alpha(0)=1$. So, $\mathcal{H}^0(\{a\})=\mathcal{H}^0_{\delta}(\{a\})=1$. Thus, $\mathcal{H}^0$ is a counting measure.

3. $\mathcal{H}^1=\mathcal{L}^1$ on $\mathbb{R}^1$, i.e. $\mathcal{H}^1$ measure of a line segment is its length.

4. Since $\mathbb{R}^n$ is not $\sigma-$finite, $\mathcal{H}^s$ is not a Radon measure for $0\leq s < n$.

5. If $s > n$ then $\mathcal{H}^s\equiv 0$ on $\mathbb{R}^n$.
To see this is easy. Let us consider a unit cube $Q$ in $\mathbb{R}^n$, fix an integer $m \geq 1$. The unit cube can be decomposed into $m^n$ cubes with sides $1/m$ and diameter ${n^{1/2}}/{m}$. Therefore,
$$ \mathcal{H}^s_{{\sqrt{n}}/{m}}(Q)\leq \sum_{i=1}^{m^n} \alpha(s) (n^{1/2}/m)^s = \alpha(s) n^{s/2} m^{n-s}.$$If $s >n$, then $m^{n-s}\rightarrow 0$ as $m\rightarrow \infty$ i.e. as the size of the covering vanishes. Thus, $\mathcal{H}^s(Q)=0$, so $\mathcal{H}^s(\mathbb{R}^n)=0$ for $s >n$.

6. Scaling: $\mathcal{H}^s(\lambda A)=\lambda^s\mathcal{H}^s(A)$ for all $\lambda > 0$, $A \subset \mathbb{R}^n$. (Easy to prove.)

7. Invariance under affine transformation: $\mathcal{H}^s(L(A))=\mathcal{H}^s(A)$ for each affine isometry $L:\mathbb{R}^n\rightarrow \mathbb{R}^n, \, A \subset \mathbb{R}^n$.

8. $\mathcal{H}^n=\mathcal{L}^n$ on $\mathbb{R}^n$.


Hausdorff-Besicovitch dimension:
The hausdorff dimension of a set $A\subset \mathbb{R}^n$ is defined to be

$$\mathcal{H}_{\mbox{dim}}(A)=\inf\{ 0\leq s < \infty | \mathcal{H}^s(A)=0 \}.$$

The following assertions follow from the definition:
Countable sets have Hausdorff dimension $0$. The Euclidean space has Hausdorff dimension $n$.
The circle has Hausdorff dimension $1$.
The Cantor set (a zero-dimensional topological space) is a union of two copies of itself, each copy shrunk by a factor 1/3; this fact can be used to prove that its Hausdorff dimension is ${\ln 2}/{\ln 3}$.

Rudin-Osher-Fatemi image denoising model

Today we will finally touch the subject of the celebrated image denoising model proposed by Rudin, Osher and Fatemi in 1992, ( L. Rudin, S. Osher, E. Fatemi, "Nonlinear total variation based noise removal algorithms", Physica D, vol. 60, pp. 259–268, 1992.)

This model is motivated by the following problem in image restoration:
Given a noisy image $f:\Omega\rightarrow \mathbb{R}$, where $\Omega$ is bounded open subset of $\mathbb{R}^2$, we need to obtain a clean image $u$.

For solving this problem they proposed the following minimization problem:
$$\mbox{ minimize } \int_{\Omega}|\nabla u|\\\mbox{ subject to } \int_{\Omega} u=\int_{\Omega}f \, \hspace{10 pt}\mbox{ and } \hspace{10 pt}\int_{\Omega} |f-u|^2 = \sigma^2.$$ where $\sigma^2$ is the estimated global variance of the additive noise. This can be also formulated in terms of soft constraint minimization:
$$u_{\lambda}=\arg\min_u \{\,|u|_{BV(\Omega)} + \lambda \Vert f-u\Vert_{L^2(\Omega)}^2\}.$$ where $|u|_{BV(\Omega)}$ is the BV-seminorm.
In general, this belongs to the class of minimization problems of the following type
$$u_{\lambda}=\arg\min_u \{\,J(u) + H(f, u) \}$$ where $J$ is a convex nonnegative regularization functional and the fitting functional $H$ is convex nonnegative with respect to $u$ for fixed $f$. Due to convexity there exists a minimizer $u_{\lambda}$ such that '0' is in the sub-differential of $J(u) + H(f, u)$ at $u_{\lambda}$ i.e.
$$0\in\partial_u J(u_{\lambda})+\partial_u H(u_{\lambda}, f).$$
(here subdifferential $\partial_u J$ at $u_{\lambda}$ is the set $\partial_u J(u_{\lambda}):=\{v:J(u)\geq J(u_{\lambda})+\langle v, u-u_{\lambda} \rangle \}$. )

If $H(u, f)=\lambda\Vert f-u\Vert_{L^2(\Omega)}^2$, then $\partial_u H(u, f)=2\lambda (u-f)$. Moreover if $H(u, f)=\lambda\Vert f-Ku\Vert_{L^2(\Omega)}^2$, where $K:L^2(\Omega)\rightarrow \mathcal{H}$, $\mathcal{H}$ being some Hilbert space, then $\partial_u H(u, f)=2\lambda K^*(Ku-f)$, where $K^*$ denotes an adjoint of $K$.

Formally, we can write $\partial J(u)=-\mbox{div}\Big( \frac{\nabla u}{|\nabla u|}\Big)$, and we can write the Euler-Lagrange differential equation for the Rudin Osher Fatemi model as follows:
$$ 0=-\mbox{div}\Big( \frac{\nabla u}{|\nabla u|}\Big)+2\lambda(u-f)$$ or equivalently,
$$ u=f+\frac{1}{2\lambda}\mbox{div}\Big( \frac{\nabla u}{|\nabla u|}\Big)$$
We impose Neumann boundary condition $\nabla u\cdot\nu=0$ in the boundary $\partial \Omega$, this ensures the condition on the mean: $\int_{\Omega}u=\int_{\Omega}f$.

Dependence on the scaling parameter $\lambda$:

The parameter $\lambda$ determines the denoising level. If $\lambda$ is small, then it is equivalent to penalizing the fidelity term more and the minimizer $u_{\lambda}$ is very close to the original image. On the other hand, for large $\lambda$ the minimizer is a cartoon representation of the image $f$.



We perform a few experiments on the image of Lenna:

Original image, Lena.

For $\lambda=0.8$ and the image in the range [0, 255] we get the following result:

The denoised image $u_{\lambda}$ for $\lambda=0.8$

We see above that for this $\lambda=0.8$ the denoising is minimal.


For $\lambda=0.05$ and the image in the range [0, 255] we get the following result:

The denoised image $u_{\lambda}$ for $\lambda=0.05$.

Here we see the details are gone, but we still see a lot of structure. Let's see what happens if we take $\lambda=0.01$, with image in [0, 255].

The denoised image $u_{\lambda}$ for $\lambda=0.01$.

We here see that we get only a cartoon image of Lena. In other words we get only large-scale structures in the image of Lena.

Properties of the ROF denoising:
Let us look at some properties of the ROF model now.

1. The $L^2$-norm of the minimizer $u_{\lambda}$ is bounded, and the bound is independent of $\lambda$.

This nice property can be proven (Nezzar) by realizing that $u_{\lambda}$ is a minimizer of the ROF functional, thus for any $w\in BV(\Omega)$ we have:
$$|u_{\lambda}|_{BV(\Omega)}+\lambda \Vert f-u_{\lambda}\Vert_{L^2(\Omega)}^2\leq |w|_{BV(\Omega)}+\lambda \Vert f-w\Vert_{L^2(\Omega)}^2.$$This is true even if we choose $w \equiv 0$, which gives us:$$|u_{\lambda}|_{BV(\Omega)}+\lambda \Vert f-u_{\lambda}\Vert_{L^2(\Omega)}^2\leq \lambda \Vert f\Vert_{L^2(\Omega)}^2.$$As $0\leq |u_{\lambda}|_{BV(\Omega)}$ we have:$$\Vert f-u_{\lambda}\Vert_{L^2(\Omega)}^2\leq \Vert f\Vert_{L^2(\Omega)}^2.$$By expanding the $L^2$ term and using Cauchy-Schwartz inequality we get $$\int_{\Omega} f^2-2fu_{\lambda}+u_{\lambda}^2 \leq \int_{\Omega}f^2,\\
\int_{\Omega} u_{\lambda}^2 \leq \int_{\Omega}2fu_{\lambda} \leq 2 \Vert u_{\lambda}\Vert_{L^2(\Omega)}\Vert f \Vert_{L^2(\Omega)},\\
\Vert u_{\lambda} \Vert_{L^2(\Omega)}\leq 2 \Vert f \Vert_{L^2(\Omega)}.$$

2. The average of the minimizer $u_{\lambda}$ is the same as the average of the original image $f$.

To prove this it suffices to prove that $\int_{\Omega}u_{\lambda}=\int_{\Omega}f.$ This follows from integrating the Euler-Lagrange differential equation and Neumann boundary condition.

Now let us discuss properties of the ROF minimization proven by Yves Meyer. Let's define a few things first.

Definition: Let $G$ denote the space as follows $G=\{v=\mbox{div } \bar{g}: \bar{g}=(g_1, g_2); \mbox{ with }g_1, g_2 \in L^{\infty}(\mathbb{R}^2)\}.$
The star-norm $\Vert v \Vert_*$ of $v\in G$ is defined as follows:
$$\Vert v \Vert_* =\inf \{\Vert |\bar{g}|_{l^2}\Vert_{L^{\infty}}:v=\mbox{div } \bar{g}\}$$

3. If $v\in L^2(\mathbb{R}^2)$, then
$$ \int f\, v \leq |f|_{BV(\Omega)} \Vert v\Vert_{*}.$$
This property is true for $f\in W^{1, 1}(\mathbb{R}^2)$. Then we can use the density of $W^{1, 1}(\mathbb{R}^2)$ in $BV(\mathbb{R}^2)$.

4. Meyer: If $\Vert f \Vert_* \geq \frac{1}{2\lambda}$, then the Rudin-Osher-Fatemi decomposition $f=u_{\lambda}+v_{\lambda}$ is characterized by the following two conditions:$$ \Vert v_{\lambda} \Vert_* = \frac{1}{2\lambda} \mbox{ and } \int u_{\lambda}v_{\lambda}=\frac{1}{2\lambda} |u_{\lambda}|_{BV}.$$
Moreover, if $\Vert f \Vert_* \leq \frac{1}{2\lambda}$, then $u_{\lambda}=0$ and $v_{\lambda}=f$.

To prove this assertion, consider that if $u_{\lambda}$ is the minimizer of the ROF energy then $u_{\lambda}+\epsilon h$ is not! for a constant $\epsilon$ and a function $h$. This gives $|\int vh|\leq \frac{1}{2\lambda}|h|_{BV}$. Secondly, taking $h=u_{\lambda}$ we obtain equality.

More on intermediate convergence

According to the vectorial version of the Riesz-Alexandroff representation theorem, the dual norm $\vert u \vert_{BV}=\Vert Du \Vert=\sup \{\int_{\Omega} u \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}$ is also the total mass $|Du|(\Omega)=\int_{\Omega}|Du|$ of the total variation $|Du|$ of the measure $Du$.

Moreover, from classical integration theory, the integral $\int_{\Omega}\phi \,d(Du)$ is well defined for all $Du$ integrable functions $\phi$ from $\Omega$ into $\mathbb{R}^N$, e.g. for functions in $C_b(\Omega, \mathbb{R}^N)$. For the same reasons, $\int_{\Omega}\phi\, d|Du|$ is well defined for all $|Du|$ integrable functions $\phi$, in particular for functions in $C_b(\Omega)$.

Thus, we can say that $|Du_n|\rightharpoonup |Du|$ narrowly in $M(\Omega)$ if $\int_{\Omega}\phi \, d|Du_n|\rightarrow \int_{\Omega}\phi\,d|Du|$, for all $\phi \in C_b(\Omega)$. If we choose $\phi\equiv 1$ on $\Omega$ then $\Vert Du_n \Vert \rightarrow \Vert Du \Vert$ i.e. $|u_n|_{BV}\rightarrow |u|_{BV}$.

Hence, $u_n\rightarrow u$ in $L^1(\Omega)$ and the narrow convergence of measures, $|Du_n|\rightharpoonup |Du|$ in $M(\Omega)$ implies the intermediate convergence, $u_n\rightharpoonup u$ (i.e. $u_n\rightarrow u$ in $L^1(\Omega)$ and $|u_n|_{BV}\rightarrow |u|_{BV}$).


We have the following proposition regarding the intermediate convergence.

Proposition
The following three assertions are equivalent
(i) $u_n\rightharpoonup u$ in the sense of intermediate convergence.
(ii) $u_n\rightharpoonup u$ in $BV(\Omega)$ and $\vert u_n \vert_{BV}\rightarrow \vert u \vert_{BV}$.
(iii) $u_n\rightarrow u$ strongly in $L^1(\Omega)$ and $\vert Du_n \vert\rightharpoonup \vert Du \vert$ narrowly in $M(\Omega)$.

Proof
The equivalence (i) to (ii) is a consequence of a proposition from the previous post. We have just seen above that (i) and (iii) are equivalent. We only need to prove that (ii) implies (iii).

Recall that $u_n\rightharpoonup u$ weakly in $BV(\Omega)$ means that
(a) $u_n\rightarrow u$ strongly in $L^1(\Omega)$ and
(b) the measures $Du_n\rightharpoonup Du$ weakly in $M(\Omega, \mathbb{R}^N)$.

Also, recall that for non-negative Borel measures $\mu_n$ and $\mu$ in $M(\Omega)$ the following statements are equivalent:
(c) $\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu(U)\leq \lim\inf_{n\rightarrow\infty}\mu_n(U)$ for all open subsets $U\subset \Omega$.
(d) $\mu_n\rightharpoonup \mu$ narrowly in $M(\Omega)$.

Let, $\mu_n=|Du_n|$ and $\mu=|Du|$. We have been given that $|Du_n|(\Omega)\rightarrow |Du|(\Omega)$ i.e. we have $\mu_n(\Omega)\rightarrow \mu(\Omega)$. For showing the narrow convergence $\mu_n\rightharpoonup \mu$ we just need to prove the lower-semicontinuity property on $U\subset\Omega$,
i.e. we need to show that for $\mu(U)\leq \lim\inf_{n\rightarrow\infty}\mu_n(U)$ for all open subsets $U\subset \Omega$,
i.e. we need to show that for $|Du|(U)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(U)$ for all open subsets $U\subset \Omega$.

To this effect we use the proposition from the previous blog which says that if $u_n\in BV(\Omega)$ with $|u_n|_{BV(\Omega)}$ bounded, with $u_n\rightarrow u$ in $L^1(\Omega)$, then we have the lower semicontinuity property i.e. $|Du|(\Omega)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(\Omega)$, and $u\in BV(\Omega)$.

Let $U\subset\Omega$ be any open subset. We have $u_n\in BV(\Omega)$, thus as $U\subset\Omega$, we have $u_n\in BV(U)$. Thus, we have $\sup_n |Du_n|(U)\leq \sup_n |Du_n|(\Omega)<\infty$.

The weak convergence $u_n\rightharpoonup u$ in $L^1(\Omega)$ implies the strong convergence $u_n\rightarrow u$ in $L^1(\Omega)$ and thus the strong convergence $u_n\rightarrow u$ in $L^1(U)$ follows as $U\subset \Omega$.

 Now that we have the conditions in the proposition: $u_n\in BV(U)$, $\sup_n |Du_n|(U)<\infty$, and $u_n\rightarrow u$ in $L^1(U)$ we have the lower semicontinuity property: $|Du|(U)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(U)$ for all open subsets $U\subset \Omega$. 

As we have $|Du_n|(\Omega)\rightarrow |Du|(\Omega)$ and $|Du|(U)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(U)$ for all open subsets $U\subset \Omega$, from the equivalence of (c) and (d) we get the narrow convergence: $|Du_n|\rightharpoonup |Du_n|$ narrowly in $M(\Omega). \,\,\hspace{25pt} \square$.

In conclusion, intermediate convergence implies narrow convergence of $|Du_n|$.

Narrow convergence of measures and intermediate convergence of BV functions

Recall By the Riesz-Alexandroff representation theorem the dual of the space $C_0(\Omega,\mathbb{R}^N)$ (and thus of $C_c(\Omega,\mathbb{R}^N)$ can be isometrically identified with $M(\Omega,\mathbb{R}^N)$. i.e. any Borel measure $\mu$ is a bounded linear functional (continuous linear form if you like that) on $C_0(\Omega,\mathbb{R}^N)$ or $C_c(\Omega,\mathbb{R}^N)$. Thus, the weak convergence of a sequence of Borel measures $\mu_n$ is defined as follows.

Weak convergence of Borel measures: We say that a sequence of Borel measures $\mu_n$ converges weakly to $\mu$ i.e. $\mu_n\rightharpoonup \mu$ if $\langle\mu_n, \phi \rangle \rightarrow \langle \mu, \phi\rangle $ for all $\phi \in C_0(\Omega,\mathbb{R}^N)$.

Here, $\langle \mu, \,\phi\rangle\equiv\mu(\phi)\equiv\int_{\Omega} \phi \, d\mu \equiv \sum_{i=1}^N\int_{\Omega} \phi_i d\mu_i$.

Narrow convergence: A sequence $\{\mu_n\}$ in $M(\Omega, \mathbb{R}^N)$ narrowly converges to $\mu$ ($\mu_n\rightharpoonup \mu$ narrowly) in $M(\Omega, \mathbb{R}^N)$ if and only if $$\int_{\Omega} f\, d\mu_n \rightarrow \int_{\Omega} f d\mu,$$ for all $f \in C_b(\Omega, \mathbb{R}^N)$.

Narrow convergence is stronger than weak convergence.
If $\Omega=(0, 1)$ and $\mu_n=\delta_{\frac{1}{n}}$ then $\mu_n\rightharpoonup 0$ weakly. This is because for all $\phi \in C_0(\Omega)$, we have, $\mu_n(\phi)=\phi(\frac{1}{n})\rightarrow \phi(0)=0=\mu(\phi)$.

On the other hand, if $\phi\equiv1$ on $\Omega$, (note that $\phi \not\in C_0(\Omega)$ but $\phi \in C_b(\Omega)$), then we see that $\int_{\Omega} d\mu_n=\mu_n(\Omega)=1$ for all $n$. Essentially what happened with $\mu_n=\delta_{\frac{1}{n}}$ is that it converges weakly to $\mu=0$, but $\mu_n(\Omega)$, the size of $\Omega$ measured in $\mu_n$ does not converge to the size of $\Omega$ in measure $\mu(=0)$, that is $\mu_n\rightharpoonup \mu$ but $\mu_n(\Omega)\nrightarrow \mu(\Omega)$.

We have the following compactness result for the narrow topology.

PROKHOROV's sequential compactness theorem
If for a bounded subset $\mathcal{H}$ of $M^+(\Omega)$ it is true that for all $\epsilon$ there exists a compact subset $K_{\epsilon}\subset \Omega$ such that $\sup\{\mu(\Omega\ K_{\epsilon}):\mu\in \mathcal{H}\}\leq \epsilon$, then $\mathcal{H}$ is sequentially compact for the narrow topology.

The following equivalence proposition says that the convergence $\mu_n(\Omega)\rightarrow \mu(\Omega)$ is precisely what we need to ensure narrow convergence of measures.

Proposition
Let $\mu_n$ and $\mu$ be in $M^+(\Omega)$, non-negative Borel measures, then the following assertions are equivalent:
(i) $\mu_n\rightharpoonup \mu$ narrowly.
(ii)$\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu \rightharpoonup \mu$ weakly.

Proof
Note that as narrow convergence is stronger than weak convergence, it is clear that if $\mu_n\rightarrow \mu$ narrowly then $\mu \rightharpoonup \mu$. Also, $\mu_n(\Omega)\rightarrow \mu(\Omega)$ follows by taking $f\equiv 1$.

So, we need to only prove that if $\mu \rightharpoonup \mu$ weakly and $\mu_n(\Omega)\rightarrow \mu(\Omega)$ then $\mu_n\rightharpoonup \mu$ narrowly. That is, we need to show that for any function $f$ in $C_b(\Omega, \mathbb{R}^N)$ we have $\big| \int_{\Omega} fd\mu_n - \int_{\Omega} fd\mu \big|\rightarrow 0$. To do this we add and subtract $\int_{\Omega} f\,\phi d\mu_n$ and $\int_{\Omega} f\,\phi d\mu$ where $\phi$ is continuous function that is compactly supported in $\Omega$. The result follows as $f$ is bounded i.e. $\Vert f \Vert_{\infty}$ is a finite number and $\int_{\Omega} f\phi d\mu_n \rightarrow \int_{\Omega} f\phi d\mu$ due to compact support of $\phi$ in $\Omega . \hspace{25pt}\square$

More equivalence proposition
Let $\mu_n$ and $\mu$ be in $M^+(\Omega)$, non-negative Borel measures, then the following assertions are equivalent:
(i) $\mu_n\rightharpoonup \mu$ narrowly.
(ii) $\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu(U)\leq \lim\inf_{n\rightarrow \infty} \mu_n(U)$ for all open subsets $U\subset \Omega$.
(iii) $\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu(F)\geq \lim\inf_{n\rightarrow \infty} \mu_n(F)$ for all closed subsets $F\subset \Omega$.
(iv) $\mu_n(B)\rightarrow \mu(B)$ for all Borel subsets $B\subset\Omega.\,\,\hspace{25pt}\square$

Ok, so far so good. But images are not necessarily continuous functions. They might have jump discontinuities, i.e. edges. For this the following result due to Marle (Measure et probabilities) is helpful:

Proposition
Let $\mu_n$ and $\mu$ be non-negative Borel measures $M^+(\Omega)$, with $\mu_n\rightharpoonup \mu$ narrowly and let $f$ be a $\mu_n$ measurable bounded function for all $n$, such that it is discontinuous only on a set of null $\mu-$ measurable set then
$$\hspace{25pt}\int_{\Omega} f\, d\mu_n \rightarrow \int_{\Omega} f\, d\mu \hspace{25pt}\square$$

Now, that we have seen a notion of convergence for sequence of measures that is stronger than weak convergence, let's look at the a notion of convergence for sequence of functions in $BV$ space that is stronger than weak convergence.

Intermediate convergence
Let $\{u_n\}$ be a sequence in $BV(\Omega)$ and $u\in BV(\Omega)$. we say that $u_n\rightharpoonup u$ intermediately (or in the sense of intermediate convergence) if and only if
$$u_n\rightarrow u \mbox{ in } L^1(\Omega),$$
$$\hspace{25pt}\vert u_n\vert_{BV}\rightarrow \vert u\vert_{BV}\,\,\hspace{25pt}\square$$

Recall, from the previous post that for $\{u_n\}\in BV(\Omega)$ with bounded TV mass and $u_n\rightarrow u$ strongly in $L^1(\Omega)$, then we have $u_n\rightharpoonup u$ in $BV$, but $\vert u \vert_{BV}\leq \lim\inf_{n\rightarrow \infty}\vert u_n \vert_{BV}$ i.e. some of the mass is lost.

Ok, now I am hungry, so more about this tomorrow.

There is something about the $BV$ space

I have been putting it off for a while. But now that I can write Latex in the blogger I can talk about $BV$ spaces.
Solutions of some mathematical problems which have discontinuities along one-codimensional manifolds where the first distributional derivatives are measures prompt us to consider the $BV$ space. I will refer to Attouch et al's book: Variational Analysis in Sobolev and BV spaces.

Definition of $BV$ space: We say that a function $u:\Omega\rightarrow \mathbb{R}$ is a function of bounded variations i.e. $u\in BV \,$ if and only if it belongs to $L^1(\Omega)$ and its gradient $Du$ in the distributional sense is in $M(\Omega, \mathbb{R}^N)$.

The following statements are equivalent.
(i) $u\in BV(\Omega)$
(ii) $u \in L^1(\Omega)$ and $u_{x_i}\in M(\Omega)$ for all $i=1, 2, ..., N$.
(iii) $u \in L^1(\Omega)$ and $\vert u \vert_{BV}<\infty$, where $\vert u\vert_{BV}:=\sup \{\langle Du, \,\mathbf{\phi}\rangle: \mathbf{\phi} \in C_c(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}.$
(here $\langle Du, \,\mathbf{\phi}\rangle:=\sum_{i=1}^N \int_{\Omega}\, \mathbf{\phi}_i u_{x_i}$.)
(iv) $u \in L^1(\Omega)$ and $\vert u \vert_{BV}=\sup \{\int_{\Omega} u \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}<\infty$.

The implication (ii)$\implies $(iii) follows as $C_c(\Omega, \mathbb{R}^N)$ is dense in $C_0(\Omega, \mathbb{R}^N)$. The implication (ii)$\implies $(iii) follows as $C_c^{\infty}(\Omega, \mathbb{R}^N)$ is dense in $C_0(\Omega, \mathbb{R}^N)$ and $C_c(\Omega, \mathbb{R}^N)$.

Notations and facts:
$\Omega \subset \mathbb{R}^N$.
$C_0(\Omega, \mathbb{R}^N)$ is the space of all continuous functions that vanish at infinity. i.e. for a function $\phi\in C_0(\Omega, \mathbb{R}^N)$ the following is true: Given any $\epsilon > 0 $ there exists a compact set $K_{\epsilon} \subset \Omega$ such that $\sup_{x\in\Omega \backslash K_{\epsilon}}|\phi(x)|\leq \epsilon$.
The functions $\mathbf{\phi}$ in $C_0(\Omega, \mathbb{R}^N)$ are equipped with the uniform norm
$\Vert \phi \Vert_{\infty}:= \sup_{x \in \Omega}\{ |\phi(x)|\}$.
$C_c(\Omega, \mathbb{R}^N)$ is the subspace of $C_0(\Omega, \mathbb{R}^N)$ with a compact support in $\Omega$.
$C_b(\Omega,\mathbb{R}^N)$ is the subset of all bounded continuous functions from $\Omega$ into $\mathbb{R}^N$.

Density results:
$C_c(\Omega, \mathbb{R}^N)$ is dense in $C_0(\Omega, \mathbb{R}^N)$.
The space of infinitely differentiable and compactly supported functions $C_c^{\infty}(\Omega, \mathbb{R}^N)$ is dense is $C_0(\Omega, \mathbb{R}^N)$ and $C_c(\Omega, \mathbb{R}^N)$.

Duality results:
$M(\Omega, \mathbb{R}^N)$ denotes the space of all $\mathbb{R}^N$ valued Borel measures.
$M(\Omega, \mathbb{R}^N)$ is isomorphic to the product space $M^N(\Omega)$.
By the Riesz-Alexandroff representation theorem the dual of the space $C_0(\Omega, \mathbb{R}^N)$ (and thus of $C_c(\Omega, \mathbb{R}^N)$) can be isometrically identified with $M(\Omega, \mathbb{R}^N)$. i.e. any Borel measure $\mu$ is a bounded linear functional (continuous linear form if you like that) on $C_0(\Omega, \mathbb{R}^N)$ or $C_c(\Omega, \mathbb{R}^N)$ and the dual norms $\Vert\cdot \Vert_{C_{0}^{'}(\Omega, \mathbb{R}^N)}$ and $\Vert \cdot \Vert_{C_{c}^{'}(\Omega, \mathbb{R}^N)}$ are equal to the total mass $|\cdot|(\Omega)$ :
$$|\mu|(\Omega)\equiv \int_{\Omega}|\mu|=\sup\{ \langle \mu, \,\mathbf{\phi}\rangle: \mathbf{\phi} \in C_0(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1 \} =\sup\{ \langle \mu, \,\mathbf{\phi}\rangle: \mathbf{\phi} \in C_c(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1 \}.$$ Here, $\langle \mu, \,\phi\rangle\equiv\mu(\phi)\equiv\int_{\Omega} \phi \, d\mu \equiv \sum_{i=1}^N\int_{\Omega} \phi_i d\mu_i.$

The relation between $BV$ and the Sobolev space $W^{1, 1}$:

According to Radon-Nykodym theorem there exists $\nabla u \in L^1(\Omega, \mathbb{R}^N)$ and measure $D_s u$ that is singular with respect to $\mathcal{L}^N|_{\Omega}$, the $N-$ dimensional Lebesgue measure restricted to $\Omega$, such that: $$Du=\nabla u \, \mathcal{L}^N|_{\Omega}+ D_s u.$$ Thus, $W^{1, 1}$ is a subspace of the $BV-$ space and for functions in $W^{1, 1}$ we can write $Du=\nabla u$.

Norm on the $BV$ space:

The $BV$ space is equipped with the norm $\Vert u \Vert_{BV}=\Vert u \Vert_{L^1}+\vert u\vert_{BV}$.
Equipped with this norm the space of $BV$ functions is complete. The completeness of the $BV$ space follows from the completeness of $L^1$ and lower semicontinuity property which is stated below.

Proposition about the lower semicontinuity property of $BV-$ seminorm:
If $\{u_n\}$ is a sequence in $BV(\Omega)$ with $\sup_n |u_n|_{BV}< \infty$ that converges strongly $u_n \rightarrow u$ in $L^1(\Omega)$ then $|u|_{BV}\leq\lim \inf_{n\rightarrow \infty} |u_n|_{BV}$ and $u\in BV(\Omega)$.
Proof:
We use the following definition of BV seminorm here: $u \in L^1(\Omega)$ and $\vert u \vert_{BV}=\sup \{\int_{\Omega} u \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}<\infty$.
Let $\phi\in C_c^1(\Omega, \mathbb{R}^N)$ with $\Vert \phi \Vert_{\infty}\leq 1$.
We first observe that
$$\lim_{n\rightarrow \infty}\int_{\Omega} u_n\, \mbox{ div } \phi =\int_{\Omega} u\, \mbox{ div } \phi. \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(1)$$
This follows as $u_n\rightarrow u$ in $L^1(\Omega)$ strongly, and that $\phi\in C_c^1(\Omega, \mathbb{R}^N)$. Indeed, $$ \big\vert \int_{\Omega} u_n\, \mbox{ div } \phi - u\, \mbox{ div } \phi\, \big\vert \leq \int_{\Omega} |u_n-u|\cdot |\mbox{ div } \phi | \rightarrow 0,\mbox{ as } n \rightarrow \infty.$$ Note that $ \int_{\Omega}u_n \mbox{ div } \phi \leq \sup\{\int_{\Omega} u_n \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}$, i.e. $$\int_{\Omega}u_n \mbox{ div } \phi \leq |u_n|_{BV}.$$ Taking $\lim\inf$ of both sides, we get $$\lim_{n\rightarrow \infty}\int_{\Omega}u_n \mbox{ div } \phi \leq \lim\inf_{n\rightarrow \infty} |u_n|_{BV}\,.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(2)$$ From (1) and (2) we get
$$\int_{\Omega}u \mbox{ div } \phi \leq \lim\inf_{n\rightarrow \infty} |u_n|_{BV}\,.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(3)$$
Taking supremum on the left side of (3) over all $\mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1$, we get $|u|_{BV}\leq\lim \inf_{n\rightarrow \infty} |u_n|_{BV}$. Moreover, if $|u_n|_{BV}<\infty$ for all $n$ we get $|u|_{BV}<\infty$, i.e. $u\in BV$.

The weak convergence of $u_n\rightharpoonup u$ in $BV\,$ :
We say that a sequence $u_n$ in $BV(\Omega)$ converges weakly to some $u$ in $BV(\Omega)$ (i.e. $u_n\rightharpoonup u$ in $BV(\Omega)$) if and only if the following two convergences hold:
(i) $u_n\rightarrow u$ strongly in $L^1(\Omega)$
(ii) $Du_n \rightharpoonup Du$ weakly in $M(\Omega, \mathbb(R)^N)$.

Proposition: If $\{u_n\}$ is a sequence in $BV(\Omega)$ with $\sup_n |u_n|_{BV}< \infty$ that converges strongly $u_n \rightarrow u$ in $L^1(\Omega)$ then $u_n\rightharpoonup u$ in $BV$.
Proof:
As $u_n\rightarrow u$ in $L^1$ we only have to show the weak convergence $Du_n\rightharpoonup Du$.

For $\phi\in C_c^{\infty}(\Omega, \mathbb{R}^N)$ we have that $\langle Du_n, \phi\rangle =-\int_{\Omega}u_n \mbox{ div }\phi\rightarrow -\int_{\Omega}u \mbox{ div }\phi =\langle Du, \phi\rangle$.

As result of the density of $C_c^{\infty}(\Omega, \mathbb{R}^N)$ in $C_0(\Omega, \mathbb{R}^N)$ and the boundedness of $|u_n|_{BV}$ we conclude that $Du_n\rightharpoonup Du$.

APPENDIX: Basic definitions

Let $X$ be some set, and $2^X$ symbolically represent its power set, the collection of all subsets of $X$.

Measure: A mapping $\mu:2^X\rightarrow [0, \infty]$ is called a measure on $X$ if
(i) $\mu(\emptyset)=0$ and
(ii) $\mu(A)\leq \sum_{k=1}^{\infty} \mu(A_k)$, whenever $A \subset \cup_{k=1}^{\infty} A_k$.

$\mu-$ measurable set: A set $A\subset X$ is $\mu-$ measurable if for each set $B\subset X$,
$\mu(B)=\mu(B\cap A)+\mu(B\setminus A)$.


$\sigma$-algebra: A subset $\mathcal{A} \subset 2^X$ is called a $\sigma$-algebra if it satisfies the following three properties:
(i) $\mathcal{A}$ contains the null set and the set $X$, i.e. $\emptyset, X \in \mathcal{A}$.
(ii) $\mathcal{A}$ is closed under complementation: $A \in \mathcal{A}$ implies $X\setminus A \in \mathcal{A}$.
(iii) $\mathcal{A}$ is closed under countable unions: If $A_k \in \mathcal{A}$ for $k=1, 2, \dots$, then so is the union, $\cup_{k=1}^{\infty}A_k $.

Borel $\sigma$-algebra of $\mathbb{R}^n$ is the smallest $\sigma$-algebra of $\mathbb{R}^n$ containing the open subsets of $\mathbb{R}^n$.

Regular measure: A measure $\mu$ on $X$ is regular if for each set $A\subset X$ there exists a $\mu-$ measurable set $B$ such that $A\subset B$ and $\mu(A)=\mu(B)$.

Borel set: A Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement.

Borel measure: A measure $\mu$ on $\mathbb{R}^n$ is called Borel measure if every Borel set is $\mu-$ measurable.

Borel regular measure: A measure $\mu$ on $\mathbb{R}^n$ is called Borel regular measure if $\mu$ is Borel and for each $A \subset \mathbb{R}^n$ there exists a Borel set $B$ such that $A\subset B$ and $\mu(A)=\mu(B)$.

Radon measure: A measure $\mu$ on $\mathbb{R}^n$ is called Radon measure if $\mu$ is Borel regular and $\mu(K)< \infty$ for each compact set $K \subset \mathbb{R}^n$.

Segmentation of Boo's book

Segmentation is one of the most difficult problems in image processing, where the meaning of the problem depends on the context. For example, for the image of Boo, I want to segment only the book that he is reading in the following image.

Boo: the cutest dog in the world! 

Here is the segmentation result. I will talk about the code some other day.

The book that Boo reads

Red Rose in 3D

Today, we will see how to produce 3D images from normal images.

There are many ways to create  3D images. One of the ancient ways is to shift the colors in the images and used differently colored pair of glasses.

Today I bought a two dollar pair of 3D glasses from Indiglo's childrens' section.
The left glass is red and the right is blue, which means that we have to shift the red channel to the right by a few pixels depending on how far you are sitting from your computer. Can you generate this 5 lines of code in Matlab?

Here is the image that works for my glasses, enjoy:
(You will not see the rose in 3D using the 3D movie glasses where the 3D is obtained using differently polarized light, which I can not do on a computer screen.)

Red rose in 3D

Three 3 is most effective if we have two objects, out of which one is more close to you. In these cases one segments the objects which are closer and apply 3d shift in these objects alone.

Here is an example:

Stars in 3D

Stars in 2D

Gamma correction: seeing in the darkness!

Here is an example where we can see what is hidden in the background of a picture. The gamma correction in its basic form is: $u=f^{\gamma}$.

The following is an illustration where I used a picture I took in Washington DC, the picture of the World War II memorial, with a $\gamma=0.5$ I got the trees in the background.

Original picture of the world war II memorial

Gamma corrected image with $\gamma=0.5$

Wine & Cheese visited again

A while back we talked about the jpeg artifacts in an image give to me by my good friend Justin Lau. Apparently, my solution did not please him very much. So, I am revisiting the poster again. Here is the output I got with my new algorithm. I will revisit the algorithm again as I know Justin's objections in advance.

The code that generated the following output is up for auction. (Minimum bid is $2500)

Meanwhile, I will keep thinking about how to approach the quality of the poster obtained in pdf format.

Output of my new algorithm that corrects jpeg artifacts

Compare the above result to the original image below ...

The original image with severe jpeg artifacts.

Automatic makeup!

Today, I will post results of my new algorithm called 'automatic make up'.
Below is the original image and the image produced by my automatic make up algorithm.

Original image

Automatic make up!

Nordstrom

Anisosotropic diffusion may be awesome, but as we have seen, we don't know where to stop. Nordstrom an electrical engineer showed (1992) that if by adding f-u on the right hand of the Perona Malik equation makes its steady state non-trivial. Below is the steady state that was reached at t=1.05.

Non-trivial steady state

Difference between the original and the steady state of Norstrom eq.

Anisotropic diffusion is awesome

We know that the heat equation diffuses an image isotropically. This is not good, because it destroys the edges too.  Somehow one must find a way for isotropic diffusion, only in a flat region and stop the diffusion near the edges. This is the motivation for Peitro Perona and Jitendra Malik's original formulation of anisotropic diffusion.

The heat equation is $\frac{\partial u}{\partial t}=\Delta u$ i.e. $\frac{\partial u}{\partial t}=\mbox{div}\,(\nabla u)$ with $u(0)=f$.

The idea behind the anisotropic diffusion is to multiply the gradient by a function g that equals 1 when the $\nabla u=0$ i.e. flat regions and goes to 0 as the gradient increases, i.e. near the edges. A typical function that works is $g(x)=\frac{1}{1+(x/b)^2}$. for some constant $b$.

That is $\frac{\partial u}{\partial t}= \mbox{div}\,(g(\Vert\nabla u \Vert^2) \nabla u)$.

Alternatively, this can also be viewed as the gradient descent for the minimization of the energy
$$E(u):=\frac{1}{2}\int_{\Omega} g(\Vert\nabla u\Vert^2).$$
Let us look at some experiments, now.


Here is an experiment with Perona Malik model with b=0.01, at t=4.

Perona Malik at t=4.

There is hardly any loss of visual quality of the image. Compare it to the original below. Notice there is some loss of quality in her hair.

The original

Let us see what happens as we continue to t=10 below. Ok, the image is a bit too smooth, rather artistic.

Perona Malik at t=10

Comparison with heat equation



Compare these results with the heat equation at t=4 below. Very smooth, edges are lost. Not good.

Heat equation at t=4.

Holiday wine & cheese event is fun

Today, my dear friend Justin Lau, showed me a jpeg poster that he complained was not very good.Of course ! It produces strange artifacts. Below is the poster he showed me:

Original poster

Here is the detail of the artifact:

Details of the artifact

So, I asked him if I could try to correct the image. And this is what I got with the parameters: 0.01, 6 and 8 in my new algorithm, which is also for auction ($1000 minimum bid).

Details of the artifact removal algorithm

Complete poster corrected ... sort of see this post also!

Boo, the sharpest dog in the world !

I do not like Matlab's unsharp filter. Aside from the fact that the name is stupid, this filter overshoots the edges.

Here is today's fun assignment: design a filter using linear combination of derivatives of the image that does not overshoot.

Here is the output where I sharpen Boo, without overshooting him.

Boo, the sharpest dog in the world

Compare the above image with the original below. There is a subtle change in the image, which I personally believe makes it pleasing to look at.

Original Boo

A new fast denoising algorithm for auction

Here is a novel denoising algorithm. It denoises a 256x256 color image in 2.17 seconds, grayscale in 0.58 seconds (should this be plural or singular?) in Matlab.

I will give the code with explanation to the highest bidder. Minimum bid $1000 USD.

Noisy image

Denoised image

Details of the noisy image

Details of denoised image:
Notice the texture of the wig is almost perfectly maintained.

Nostaligia

It is snowing in Toronto and it is depressing and gloomy to look outside my window. This is a perfect time to think about the past. When I was a child we used to have a film camera. Tricky contraption, if you ask me. The light would be imparted on a film, we would call it a 'negative'. This film is then developed into a photograph. For some reason, I was more fascinated by the negative. Somehow I would think that all my negativity is captured in that. So, on this gloomy day I found an old picture of mine and made its negative. Can you figure out a one line code to do this?

Me and my alter ego

A quick divergence to the cutest Laplacian in the world.

Let $\mathbf{u}=(u_1, u_2)$ be a vector valued function. Then the divergence operator: $\mbox{div }\mathbf{u}:=\frac{du_1}{dx}+\frac{du_2}{dx}$ is a very useful thing to have on our side. Again, I will leave this little code upto you. It is really a one liner!

Note, that if $\nabla u=(u_x, u_y)$ then $\mbox{div}(\nabla u)$ gives the Laplacian $\Delta u$ of the image $u$. This could be useful.

Here is the Laplacian of Boo displayed between -50 to 50.
i.e. use the commands to display the Laplacian d :
>> m=-50; M=50; figure; imshow((d-m)/(M-m));

Laplacian of Boo (-50 to 50)

Here is the original.

Boo, the cutest dog in the world

The edge of darkness is upon us!

I assume that now we know how to find edges in a given image u. It's simple, just take the derivative!

Today, I want to find the smooth regions. Well, it's kind of silly, as now that we have edges, the rest of the image is kind of edgeless. Right... but I would like to assign a number from 0 to 1 to it ... where 1 indicates a flat region and zero indicates an edge, in other words I want to make the edges appear dark.

There are many ways to do it. One of the ways to do it is to look at the function $$g(x, y):=\frac{1}{\sqrt{1+|K*\nabla u(x, y)|}}.$$Where, K is your favourite smoothing kernel. (I will leave it to you to code this as an exercise. It is a four liner.)

Staring at this function is a refreshing activity, something that I love to do in my spare time.

Boo in the edge of darkness

Lenna in the edge of darkness

Barbara in the edge of darkness

Boo, the smoothest dog in the world!

Yesterday night I was too sleepy to code, so I wrote a code for filtering with a kernel that is more than 3x3. Btw, I still like my kernel to be of odd sized and square.

Let's use the image of Boo, the cutest dog in the world and make it the smoothest dog in the world. By using a 5x5 averaging kernel.


>> h=ones(5)/25;
>> u=double(imread('boo.jpg'));
>> uf=ifilter(u, h);m=min(min(min(uf))); M=max(max(max(uf))); figure; imshow((uf-m)/(M-m));

Boo, the cutest dog in the world!

Boo, after smoothing with a 5x5 kernel becomes the smoothest dog in the world!