%gmChap09.tex

\graphicspath{{./figures/}}

\begin{slide}
\section{Median Filters and Mathematical Morphology}



All of the median operators (or filters) will be defined in terms of a nonnegative measurable weight function $k:\RR^N\to[0,+\infty)$ that is normalized:
\[
\int_{\RR^N}k(\fxy)\,\rmd\fxy=1.
\]
The $k$-measure of a subset $B\subset\RR^N$ is denoted by $|B|_k$ and defined by
\[
|B|_k=\int_Bk(\fxy)\,\rmd\fxy=\int_{\RR^N}k(\fxy)\bmone_B(\fxy)\,\rmd\fxy.
\]
Clearly, $0\leq|B|_k\leq1$.  Example :
$k=c^{-1}_N(r)\bmone_{B(0,r)}$, where $B(0,r)$ denotes the ball of
radius $r$ centered at the origin and $c_N(r)$ is the Lebesgue
measure of $B(0,r)$.

\end{slide}
\begin{slide}

\section[The median operators ${\setM_k}$ and ${\fcnM_k}$]{The median operators \boldmath${\setM_k}$ and ${\fcnM_k}$\unboldmath}

As we did for the erosions and dilations, we first define the set operators.

\begin{definition}Let $X$ be a measurable subset of $\RR^N$ and let $k$ be a weight function. The median set of $X$ weighted by $k$, which we denote by $\setM_kX$, is defined by
\begin{equation}
\setM_kX=\{\fxx\mid |X-\fxx|_k\geq\textstyle{\frac{1}{2}}\}.
\end{equation}
\end{definition}
When $k $ is a Gaussian : Koenderink and van Dorn. If
$k=(1/{\pi}r^2)\bmone_{B(0,r)}$. Then $\fxx$ belongs to $\setM_kX$
if and only if the Lebesgue measure of $X\cap B(\fxx,r)$ is
greater than or equal to half the measure of $B(0,r)$.
Intuitively, $\fxx\in\setM_kX$ if points of $X$ are in the
majority around $\fxx$.

\end{slide}
\begin{slide}



\begin{lemma}
The set operator $\setM_k$ is upper semicontinuous on the measurable sets $\mathcal L$.
\end{lemma}


\end{slide}
\begin{slide}


\begin{proof}  $
\setM_kX=\{\fxx\mid |X-\fxx|_k\geq\textstyle{\frac{1}{2}}\}.$
Given a descending  sequence $(X_{n})_{n\in\mathbb N}$ in
$\mathcal L$, we must show that
\[
\setM_k\bigcap_{n\in\mathbb N}X_{n}=\bigcap_{n\in\mathbb N}\setM_kX_{n}.
\]
Since $\setM_k$ is clearly monotone, it is always true that $\setM_k\bigcap_{n\in\mathbb N}X_{n}\subset\bigcap_{n\in\mathbb N}\setM_kX_{n}$. To prove the other inclusion, assume that $\fxx\in\bigcap_{n\in\mathbb N}\setM_kX_{n}$. Then by the definition of $\setM_k$, $|X_n-\fxx|\geq1/2$ for all $n\in\mathbb N$. Since $X_n-\fxx\downarrow \bigcap_{n\in\mathbb N}(X_{n}-\fxx)$, we know from the countable additivity of Lebesgue measure that  $|X_n-\fxx|_k\downarrow |\bigcap_{n\in\mathbb N}(X_{n}-\fxx)|_k$. This means that $|\bigcap_{n\in\mathbb N}(X_{n}-\fxx)|_k\geq1/2$, and hence that $\fxx\in\setM_k \bigcap_{n\in\mathbb N}(X_{n}-\fxx)$.
\end{proof}


\end{slide}
\begin{slide}



\begin{definition}The function operator $\fcnM_k$ is defined on the set of all measurable functions $\mathcal F$ by the superposition principle:
\[
\fcnM_ku(\fxx)=\sup\{\lambda\mid\fxx\in\setM_k\levelset_{\lambda}u\}.
\]
\end{definition}




\end{slide}
\begin{slide}


\begin{proposition}The median operator $\fcnM_k$ has the sup-inf representation
\begin{equation}\label{eq93}
\fcnM_ku(\fxx)=\sup_{B\in\mathcal B}\inf_{\fxy\in\fxx+B}u(\fxy),
\end{equation}
where $\mathcal B=\{B\mid B\in\mathcal L, |B|_k=1/2\}$. Furthermore,
\begin{equation}\label{eq94}
\levelset_{\lambda}\fcnM_ku=\setM_k\levelset_{\lambda}u
\end{equation}
for all $\lambda\in\barR$.
\end{proposition}


\end{slide}
\begin{slide}


\begin{proof}
We mention again that $\setM_k$  is   monotone. It
 is also clearly translation invariant. Thus, by the sup-inf representation theorem,
    $\fcnM_k$ satisfies
\[
\fcnM_ku(\fxx)=\sup_{B\in\fxx+\mathcal B_0}\inf_{\fxy\in B}u(\fxy),
\]
where $\mathcal B_0=\{B\mid0\in\setM_kB\}$.
\end{proof}

\end{slide}
\begin{slide}



\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig09.01.1.eps}
}
\caption[Denoising based on the median filter I \label{medianofoperatorimage}]{\label{operatrois}Example of denoising with a median filter. Left to right: scanned picture of the word ``operator'' with perturbations and noise made with black or white lines and dots; the image after one application of a median filter with a circular neighborhood of radius 2; the image after a second application of the same filter. Compare with the denoising  using openings and closings (Figure \ref{POPERATORDEUX}).
}
\end{figure}


\end{slide}
\begin{slide}



\begin{exercise}
Let $k=(1/2)\bmone_{[-1,1]}$. This implies that $|B|_k=1/2$ if and
only
  if $\mathrm{meas}\,([-1,1]\cap B)=1$.

Let  $u(x)=x$ if $x\leq0$, and $u(x)=0$ if $x>0$. Check that
$\fcnM_ku(0)=0$, so that
   the median value coincides with the supremum and
is different from the mean value on the neighborhood $[-1,1]$.
 \end{exercise}


\end{slide}
\begin{slide}


\section[The median operators ${\setM^-_k}$ and ${\fcnM^-_k}$]{The median operators \boldmath${\setM^-_k}$ and $\bm{\fcnM^-_k}$\unboldmath}

The median operator $\fcnM_k$, as defined,  is not invariant under
``reverse contrast,'' that is, it does not satisfy
$-\fcnM_ku=\fcnM_k(-u)$ for all measurable $u$.   We define
$\fcnM^-_k$ by
\begin{equation}\label{eq95}
\fcnM^-_ku(\fxx)=\inf_{|B|_k\geq\frac1{2}}\sup_{\fxy\in\fxx+B}u(\fxy).
\end{equation}
Then we clearly have the relation
\begin{equation}\label{eq96}
\fcnM^-_ku=-\fcnM_k(-u),
\end{equation}  If we now define $\setM^-_k$ in terms
of $\fcnM^-_k$ by $\setM^-_kX=\levelset_1\fcnM^-_k\bmone_X$, then
using \eqref{eq96} and the relation $\bmone_X+\bmone_{X^c}=1$,
\begin{equation}\label{eq97}
\setM^-_kX=(\setM_kX^c)^c.
\end{equation}
It is easily checked that
 \begin{equation}
\setM^-_kX=\{\fxx\mid |X-\fxx|_k>\textstyle{\frac1{2}}\}.
\end{equation}


\end{slide}
\begin{slide}


We say that $k$ is \emph{not separable}  if $|B|_k\geq1/2$ and
$|B'|_k\geq1/2$ imply that
$\overline{B}\cap\overline{B'}\ne\emptyset$.

\begin{proposition}\leavevmode
\begin{enumerate}%[$(i)$]\setlength\itemsep{2pt}
\item For every  function $u$, $\fcnM_ku\geq\fcnM^-_ku$. \item
Assume that  $k$ is not separable.  Then $\fcnM_ku=\fcnM^-_ku$.
\end{enumerate}
\end{proposition}

\end{slide}
\begin{slide}


\begin{proof}
 Let
$\lambda=\fcnM_ku(0)=\sup_{|B|_k\geq1/2}\inf_{y\in B}u(\fxy)$.
Consider the level set $\levelset_{\lambda+\varepsilon}u$. Then
$\inf_{\fxy\in\levelset_{\lambda+\varepsilon}}u(\fxy)\geq\lambda+\varepsilon$.
Thus $|\levelset_{\lambda+\varepsilon}u|_k<1/2$, since
$\inf_{\fxy\in B}<\lambda+\varepsilon$ for any set $B$ such that
$|B|\geq1/2$. Then
$|(\levelset_{\lambda+\varepsilon}u)^c|_k\geq1/2$, and by the
definition of level sets,
$\sup_{\fxy\in(\levelset_{\lambda+\varepsilon}u)^c}u(\fxy)\leq\lambda+\varepsilon$.
This implies that
\[
\inf_{|B|_k\geq\frac1{2}}\sup_{\fxy\in B}u(\fxy)\leq\lambda+\varepsilon.
\]

 $k$  is not separable implies that for all $B$
and $B'$ having $k$-measure greater than or equal to 1/2, we have
$\inf_{\fxy\in\overline{B}}u(\fxy)\leq\sup_{\fxy\in\overline{B'}}u(\fxy)$.
If $u$ is continuous, then we have
$\inf_{\fxy\in{B}}u(\fxy)\leq\sup_{\fxy\in{B'}}u(\fxy)$. Since $B$
and $B'$ were arbitrary except for the conditions $|B|_k\geq1/2$
and $|B'|_k\geq1/2$, the last inequality implies that
\[
\sup_{|B|_k\geq\frac1{2}}\inf_{\fxy\in{B}}u(\fxy)\leq\inf_{|B'|_k\geq\frac1{2}}\sup_{\fxy\in{B'}}u(\fxy).
\]
 This yields
$\fcnM_ku=\fcnM^-_ku$ when $u$ is continuous.
\end{proof}

\end{slide}

\begin{slide}


\begin{exercise}  The non separability  condition is necessary.
Let $k=\frac 12\bmone_{[-2, -1]\cup[1,2]}$  and let $u(x)=-1$ if
$x\leq -1$, $u(x)=1$ if $x\geq 1$, $u(x)=x$ elsewhere.  Check that
$\fcnM_ku(0) \neq \fcnM^-u(0)$. \finex
\end{exercise}
\begin{exercise} Saying that $k$ is not separable is a fairly weak assumption.
It corresponds roughly to saying that the support of $k$ cannot be split
 into two disjoint connected components each having $k$-measure 1/2. Show
 that if $k$ is continuous and if its support is connected, then it is not separable.
 \finex
\end{exercise}

\end{slide}
 \begin{slide}

\begin{slide}
\begin{figure}[!t]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig09.03.1.eps}
} \caption[Denoising based on a median filter]{Denoising based on
a median filter. Left: an image altered on 40\% of its pixels with
salt and pepper noise. Right: the same image after three
iterations of a median filter with a $3 \times 3$ square mask. }
\end{figure}


\end{slide}

\section{Discrete median filters and the "usual" median value}


\begin{align*}
\fcnM u(\fxx)=& \sup_{\stackrel{\scriptstyle{P\in\mathcal P(N)}}{\text{card}(P)\geq N/2}}\inf_{i\in P}u(\fxx-\fxx_i),\\
\fcnM^- u(\fxx)=& \inf_{\stackrel{\scriptstyle{P\in\mathcal P(N)}}{\text{card}(P)\geq N/2}}\sup_{i\in P}u(\fxx-\fxx_i).
\end{align*}

  This shows that $\fcnM =\fcnM^-$ if and only if $N$ is odd.
 In general, a median filter with
    an odd number of pixels is preferred, since $\fcnM =\fcnM^-$ in this case.



\end{slide}
 \begin{slide}


The definition  of the discrete median filter $\fcnM$ corresponds
to the usual statistical definition of the median of a set of
data: If the given data consists of the numbers $y_1\leq
y_2\leq\cdots\leq y_N$ and $N=2n+1$,   the median is $y_{n+1}$. In
case $N=2n$, the median is $(y_n +y_{n+1})/2$. In both cases, half
of the terms are greater than or equal to the median and half of
the terms are less than or equal to the median. The usual median
minimizes the functional $\sum_{i=1}^N|y_i-y|$.
\begin{equation}\label{newseq}
\underbrace{y_1=\cdots =y_1}_{k_1\text{ terms}}\leq\cdots\leq \underbrace{y_i=\cdots=y_i}_{k_i\text{ terms}}\leq\cdots\leq \underbrace{y_N=\cdots=y_N}_{k_N\text{ terms}}.
\end{equation}

If $K$ is odd,   $\fcnM^-_k=\fcnM_k$,   $\fcnM_ku(\fxx)$ is equal
to the ordinary median of the ordered set.


\end{slide}
\begin{slide}


\begin{exercise}

\begin{enumerate}%[(i)]\setlength\itemsep{2pt}
\item Show that
\[
\frac1{N}\sum_{i=1}^Nx_i=\text{arginf}_m  \sum_{i=1}^N(x_i-m)^2.
\]
\item Show that
\[
\fcnM^-(x_i)\leq \text{arginf}_m \sum_{i=1}^N|x_i-m|\leq\fcnM(x_i).
\]

\end{enumerate}
\end{exercise}

\end{slide}
\begin{slide}

\begin{exercise}

\begin{enumerate}%[(i)]\setlength\itemsep{2pt}

\item Let $k=\bmone_B$, where $B$ is set with Lebesgue measurable equal to one. Let $\fcnM_Bu$ denote the \textit{median value of u in $B$}, defined by $\fcnM_Bu=\fcnM_ku(0)$. Consider a bounded measurable function $u$ defined on $B$. Show that
\[
\int_Bu(\fxx)\,\rmd\fxx=\text{arginf}_m\int_B(u(\fxx)-m)^2\,\rmd\fxx
\]
and that
\[
\fcnM_B^-u\leq\text{arginf}_m\int_B|u(\fxx)-m|\,\rmd\fxx=\frac{\fcnM_B^-u+\fcnM_Bu}{2}\leq\fcnM_Bu.
\]
\item Deduce from the above that the mean value is the best constant approximation in the $L^2$ norm and that the median is the best constant approximation in the $L^1$ norm. \finex
\end{enumerate}
\end{exercise}

\end{slide}
\begin{slide}



\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig09.04.1.eps}
}
\caption[Smoothing effect of the median filter on level lines]{Smoothing effect of a median filter on level lines. Above, left to right: original image; all of its level lines (boundaries of level sets) with levels multiple of 12; level lines at level 100. Below,left to right: result of two iterations of a median filter with a disk with radius 2; corresponding level lines (levels multiple of 12); level lines at level 100.
}
\end{figure}
\end{slide}
