Processing math: 1%

Monday, August 20, 2012

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 L1(Ω):
Let {un}nΩ be a sequence in BV(Ω) strongly converging to some u in L1(Ω) and satisfying |un|BV<. Then uBV(Ω) and |u|BV(Ω)lim 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.)



Thursday, August 9, 2012

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}.




Thursday, July 26, 2012

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.

Thursday, May 31, 2012

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|.


Friday, February 24, 2012

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.


Tuesday, February 21, 2012

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.

Tuesday, January 24, 2012

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