%gmChap09.tex

\graphicspath{{./figures/}}

\chapter{Median Filters and Mathematical Morphology\label{Chap9}}

This entire chapter is devoted to median filters.  They are among the most characteristic and numerically efficient
contrast-invariant monotone operators. The denoising effects of median filters are illustrated in Figures
\ref{figure9.1} and \ref{figure9.2}; the smoothing effect of a median filter is illustrated in Figure \ref{figure9.3}.
They also are extremely useful in 3D-image or movie denoising.

As usual, there will be two associated operators, a set  operator
and a function operator. 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 measurable 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\leq 1$.  The simplest example for $k$ is given by the function $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)$.
Another classical example to think of is the Gaussian.

\section[Set and function medians]
{Set and function medians}

We first define the set operators, whose form is simpler. We define them on $\mathcal M(\RR^N)$, the set of measurable
subsets of $\RR^N$ and then apply the standard extension to $\mathcal M(S_N)$ given in Definition
\ref{defstandardextension}.

\begin{definition}\label{definitionsetM}Let $X\in \mathcal M(\RR^N)$ and let
 $k$ be a weight function.
The median set of $X$ weighted by $k$
 is defined by
\begin{equation}
\setM_kX=\{\fxx\mid |X-\fxx|_k\geq\textstyle{\frac{1}{2}}\}
\end{equation}
and its standard extension to $\mathcal M(S_N)$ by
\begin{equation}
\setM_kX=\{\fxx\mid |X-\fxx|_k\geq\textstyle{\frac{1}{2}}\}\cup
(X\cap{\{\infty\}}).
\end{equation}
\end{definition}
The extension amounts to add $\infty$ to $\setM_kX$  if $\infty$ belongs to $X$.   Note that we have already
encountered the median operator in Section \ref{sectiondynamicshape}.
 Koenderink and van Doorn defined the
dynamic shape of $X$ at scale $t$ to be the set of $\fxx$ such
that $G_t*\bmone_X(\fxx)\geq 1/2$. The dynamic shape is, in our
terms, a Gaussian-weighted median filter.

To gain some intuition about median filters, we suggest considering the weight $k$ defined on $\RR^2$  by
$k=(1/{\pi}r^2)\bmone_{B(0,r)}$. Then $\fxx\in\RR^2$ 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)$. Thus, $\fxx\in\setM_kX$ if points of $X$
are in the majority around $\fxx$.

\begin{lemma}\label{medianstandardmonotone}
 $\setM_k$ is a standard monotone operator on
$\mathcal M$.
 \end{lemma}
\begin{proof} Obviously $\setM_k(\emptyset)=\emptyset$ and
$\setM_k(\SN)=\SN$. By definition,
$\infty\in\setM_k  X\Leftrightarrow\infty\in X$. If $X$ is bounded, it is a direct
application of Lebesgue  theorem that
$$|X-\fxx|_k=\int k(\fxy)\bmone_{X-\fxx}(\fxy)d\fxy\to 0\hbox{ as
} \fxx\to\infty.$$  Thus $|X-\fxx|_k<\frac  12$  for $\fxx$ large
enough and $\setM_kX$  is therefore bounded.   In  the same way,
if $X^c$  is  bounded $|X-\fxx|_k\to 1$  as $\fxx\to\infty$  and
therefore $(\setM_X)^c$  is bounded.
 %%%%%%%%%%%%%% ATTENTION NADA%%%%%%%%%%%%%%
 \nada{
\newline  CETTE PARTIE DE LA PREUVE INUTILE A VERIFIER :
\newline
We have not proved yet that $\setM_k X\in \mathcal L$ if $X\in
\mathcal L$. This set is the set of compact  subsets of $\SN$ and
also  the set of closed subsets of $\SN$. Let $\fxx_n\to \fxx$ a
converging sequence in $\setM_k X$. We want to prove that $\fxx\in
\setM_k X$. If $\fxx\in\RR^N$, we have $|X-\fxx_n|\geg\frac 12$
and by the inverse Fatou  lemma, we get $|X-\fxx|_k\geq 12$, which
proves $\fxx\in \setM_k X$.  If $\fxx=\infty$, then
$\fxx_n\to\infty$ and $\fxx_n\in\setM_k X$ imply that $\setM_kX$
is  unbounded in $\RR^N$. We have just proved that this implies
that  $X$ is unbounded. Since  $X$ is closed in $\mathcal L$, we
deduce that $\infty\in X$ and therefore $\infty\in \setM_k X$.}
%%%%%%%%%%%%%%%%% Fin de NADA%%%%%%%%%%%%%%%%%
\end{proof}




\begin{lemma}\label{structurantsmedian} We can represent $\setM_k$ by
\begin{equation}
\setM_kX=\{\fxx\mid \fxx+B\subset X, \text{ for some }B\in\mathcal
B\},\end{equation}
 where $\mathcal
B=\{B\mid |B|_k\geq \frac 12\}$  or $\mathcal B=\{B\mid |B|_k=
\frac 12\}$.
\end{lemma}

\begin{proof}
 By Lemma \ref{medianstandardmonotone}, $\setM_k$ is  standard
 monotone and it is obviously
translation invariant.  So we can apply Theorem \ref{theorem7.1}. The canonical set of structuring elements  of
$\setM_k$ is
$$\mathcal B= \{B\mid0\in\setM_kB\}=\{B\mid |B|_k\geq \frac 12\}.$$
 The
second  set $\mathcal B$ mentioned in the lemma, which we call now for convenience $\mathcal B'$, is a subset of
$\mathcal B$ such that for every $B\in \mathcal B$, there is some $B'\in \mathcal B'$ such that $B'\subset B$. Thus by
Proposition \ref{reductiondeselementstructurants}, $\setM_k$ can be defined from $\mathcal B'$.
\end{proof}


The  next lemma will  help defining the function operator
$\fcnM_k$ associated with the set operator $\setM_k$.

\begin{lemma}\label{semicontinuitemedian}
The set operator $\setM_k$ is translation invariant and upper semicontinuous on  $\mathcal M$.
\end{lemma}
\begin{proof} The first  property is straightforward.
 Consider a nonincreasing
 sequence $(X_{n})_{n\in\mathbb N}$ in $\mathcal M$ and let us
 show that
\[
\setM_k\bigcap_{n\in\mathbb N}X_{n}=\bigcap_{n\in\mathbb N}\setM_kX_{n}.
\]
Since $\setM_k$ is   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}$. If $\fxx\in\RR^N$,
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 deduce from Lebesgue Theorem 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)$. If $\fxx=\infty$, it belongs to $\setM_kX_n$ for
all $n$ and therefore to $X_n$ for  all $n$. Thus, it belongs to
$\bigcap_{n\in\mathbb N}X_n$ and therefore to
$\setM_k(\bigcap_{n\in\mathbb N}X_n)$.
\end{proof}


\begin{definition}[and proposition]
\label{definitionmedianfonctions}
Define the function operator
$\fcnM_k$
 from $\setM_k$ as a stack filter,
\[
\fcnM_ku(\fxx)=\sup\{\lambda\mid\fxx\in\setM_k\levelset_{\lambda}u\}.
\]
Then $\fcnM_k$ is standard monotone, contrast invariant and
translation invariant from $\mathcal F$ to $\mathcal F$. $\fcnM_k$
and $\setM_k$ commute with thresholds,
\begin{equation}\label{eq94}
\levelset_{\lambda}\fcnM_ku=\setM_k\levelset_{\lambda}u.
\end{equation}
If $k$  is radial, $\fcnM_k$  therefore is  $\SMTCII$.
\end{definition}
\begin{proof} By Lemma \ref{semicontinuitemedian}, $\setM_k$
is upper semicontinuous and by Lemma \ref{medianstandardmonotone} it  is standard monotone and translation invariant.
So we can apply Theorem \ref{3.5bis}, which yields all announced properties for $\fcnM_k$.
\end{proof}

We get a sup-inf formula for the median as a direct application of
Theorem \ref{fullequivalence}.

\begin{proposition}\label{proposition9.4}
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 M, |B|_k=1/2\}$.
\end{proposition}




\begin{figure}[!t]\label{figure9.1}
\setkeys{Gin}{width=12cm} \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}

A median value is a kind of average, but with quite different
results, as is illustrated in Exercise \ref{medianegalfonction}.


\section{Self-dual median filters}
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  $u\in \mathcal F$. This is clear from the example in the next exercise. Self-duality
is a conservative requirement which is true for all linear filters. It means that the white and black balance is
respected by the operator. We have seen that dilations favor whites and erosions favor black colors: These operators
are not self-dual.
\begin{exercise}  Consider the one-dimensional median filter with
 $k=\frac 12\bmone_{[-2, -1]\cup[1,2]}$.  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}
As we did with erosions and dilations, one can define a dual version of the median $\fcnM^-_k$ by
\begin{equation}\label{eq96} \fcnM^-_ku=-\fcnM_k(-u), \hbox{ so
that}
\end{equation}
\begin{equation}\label{eq95}
\fcnM^-_ku(\fxx)=\inf_{|B|_k\geq\frac1{2}}\sup_{\fxy\in\fxx+B}u(\fxy).
\end{equation}

A quite general condition on $k$ is sufficient to guarantee  that
$\fcnM_k$ and $\fcnM^-_k$ agree on continuous functions.

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

\begin{proposition}\label{egalitedemedianmoinsetplus}\leavevmode
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item For every measurable function $u$, $\fcnM_ku\geq\fcnM^-_ku$.
\item Assume that $k$ is not separable. Then for every $u\in
\mathcal F$,  $\fcnM_ku=\fcnM^-_ku$ and $\fcnM_k$ is  self-dual.
\end{enumerate}
\end{proposition}
\begin{proof}
Both operators are translation invariant,  so without loss of generality we may assume that $\fxx=0$. To prove $(i)$,
let $\lambda=\fcnM_ku(0)=\sup_{|B|_k\geq1/2}\inf_{y\in B}u(\fxy)$. Take $\varepsilon>0$ and 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}\leq\lambda$ for any set $B$ such that
$|B|\geq1/2$. Thence $|(\levelset_{\lambda+\varepsilon}u)^c|_k\geq1/2$. By the definition of level sets,
$\sup_{\fxy\in(\levelset_{\lambda+\varepsilon}u)^c}u(\fxy)\leq\lambda+\varepsilon$. These two last relations imply that
\[
\inf_{|B|_k\geq\frac1{2}}\sup_{\fxy\in B}u(\fxy)\leq\lambda+\varepsilon.
\]
Since $\varepsilon>0$ was arbitrary, this proves $(i)$.

The assumption that $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)$.
Since $u\in \mathcal F$ is continuous,
$\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).
\]
From this last inequality and $(i)$, we conclude  that
$\fcnM_ku=\fcnM^-_ku$.
\end{proof}

\begin{figure}[!t]\label{figure9.2}
\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}

\subsection{Chessboard dilemma and fattening effect}


\medskip  In Figure \ref{fatteningeffect}, the median filter  has been applied iteratively to a function $u$ whose grid values
 are equal to 255 at the white pixels
 and to 0 at the black pixels. The function is continuous, being (e.g.) interpolated by standard bilinear interpolation.
 The iso-level set $I_{127.5}u:=\{\fxx\mid u(\fxx)=127.5\}$ consists of the line segments separating the squares and
has therefore zero measure.  As we know,  the median filter tends to smooth, to round off the level lines of the image.
Yet we have with a chessboard a fundamental ambiguity : are these iso-level lines
 surrounding the black squares, or are they surrounding the white squares? In  other terms,
  do we see in a chessboard a set of white squares on
 black background, or conversely?

 Since our operator is self-dual it doesn't  favor
 any of the  considered interpretations: it  rounds off simultaneously the lines  surrounding the
 black squares and the level lines surrounding the white squares (second image of Figure \ref{fatteningeffect}).
  This results in the
 ``fattening" of the level lines separating white and black, which have the mid-level $127.5$. Hence the appearance in the
 second image of a grey zone separating the smoothed out black and white squares. If we take a level set
 $\levelset_\varepsilon Tu$ of this image with $\varepsilon <0$ (third image), the fattened set joins the level set and we observe black squares on white
 background. Symmetrically if  $\varepsilon>0$ the level set shows white squares on black background.

\begin{figure}[!t]\label{fatteningeffect}
\setkeys{Gin}{width=3cm} \centerline{
\includegraphics{fig07.01.1.eps}
\includegraphics{fig07.01.2.eps}
\includegraphics{fig07.01.3.eps}
\includegraphics{fig07.01.4.eps}
} \caption[Level set  extensions and the chessboard dilemma] {The chessboard dilemma. Left: a chessboard image. The
next  image is obtained by a self-dual median filter.  Notice the expansion of the median grey level, 127.5, who was
invisible in the original image and grows in the second one. This effect is called ``fattening effect''. The third and
fourth image show the evolution of the level sets at levels 127 and  128 respectively.  This experiment illustrates a
dilemma as to whether we consider the chessboard as black squares on white background, or conversely.}
 \end{figure}



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

We define a  discrete median filter by considering, instead of a function, a uniform discrete measure
$k=\sum_{i=1,\ldots,N}\delta_{\fxx_i},$ where $\delta_{\fxx_i}$ denotes the Dirac mass at $\fxx_i$.   We could
normalize $k$, but this is not necessary, as will become clear. Translates of the points $\fxx_i$ create the discrete
neighborhood that is used to compute the median value of a function $u$ at a point $\fxx$. We denote the set of subsets
of $\{1,\dots,N\}$ by $\mathcal P(N)$ and the number of elements in $P\in\mathcal P(N)$ by $\text{card}(P)$. Since
$\text{card}(P)=|P|_k$, we will suppress the $k$-notation is favor of the more transparent ``$\text{card}(P)$,'' but
one should remember that the $k$-measure is still there. An immediate generalization of the definition of the median
filters to the case where $k$ is such a discrete measure yields
\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*}
When $k$ was continuous, we could replace  ``$|B|_k\geq1/2$'' with
``$|B|_k=1/2$,'' but this is not directly possible in the discrete
case, since $N/2$ is not an integer if $N$ is odd. To fix this, we
define the function $M$ by $M(N)=N/2$ if $N$ is even and
$M(N)=(N/2) +(1/2)$ if $N$ is odd. Now we have

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

The fact that we can replace ``$\text{card}(P)\geq N/2$'' with ``$\text{card}(P)=M(N)$'' has been argued elsewhere for the continuous case; for the discrete case, it is a matter of simple combinatorics. Given any $\fxx$, let $y_i=u(\fxx-\fxx_i)$. After a suitable permutation of the $i$'s, we can order the $y_i$ as follows: $y_1\leq,\cdots,\leq y_M\leq,\cdots\leq y_N$. Then for $N$ even,
\begin{align*}
\{\inf_{i\in P}y_i\mid \text{card}(P)\geq N/2\}&=\{\inf_{i\in P}y_i\mid \text{card}(P)=M\}=\{y_1,\ldots,y_{M+1}\},\\
\{\sup_{i\in P}y_i\mid \text{card}(P)\geq N/2\}&=\{\sup_{i\in P}y_i\mid \text{card}(P)=M\}=\{y_M,\ldots,y_N\},
\end{align*}
and $\fcnM u(\fxx)=y_{M+1}\geq y_M=\fcnM^-u(\fxx)$. If $N$ is odd, we have
\begin{align*}
\{\inf_{i\in P}y_i\mid \text{card}(P)\geq N/2\}&=\{\inf_{i\in P}y_i\mid \text{card}(P)=M\}=\{y_1,\ldots,y_{M}\},\\
\{\sup_{i\in P}y_i\mid \text{card}(P)\geq N/2\}&=\{\sup_{i\in P}y_i\mid \text{card}(P)=M\}=\{y_M,\ldots,y_N\},
\end{align*}
and $\fcnM u(\fxx)=\fcnM^-u(\fxx)= y_M$. This shows that $\fcnM
=\fcnM^-$ if and only if $N$ is odd. What we see here is  the
discrete version of Proposition \ref{egalitedemedianmoinsetplus}.
When $N$ is odd, the measure is not separable, since two sets $P$
and $P'$ with $\text{card}(P)\geq N/2$ and $\text{card}(P')\geq
N/2$ always have a nonempty intersection. In general, a median
filter with an odd number of pixels is preferred, since $\fcnM
=\fcnM^-$ in this case.

This discussion shows that 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$, them by
definition, 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|$.  Exercise \ref{variationalmedian} shows how
$\fcnM$ and $\fcnM^-$ relate to this functional.


Finally, we wish to show that the discrete median filter $\fcnM$
can be a cyclic operator on discrete images.   As a simple
example, consider the chessboard image, where $u(i,j)=255$ if
$i+j$ is even and $u(i,j)=0$ otherwise. When we apply the median
filter that takes the median of the four values surrounding a
pixel and the pixel value, it is clear that the filter
``reverses'' the chessboard pattern. Indeed, any white pixel
(value 255) is surrounded by four black pixels (value zero), so
the median filter transforms the white pixel into a black pixel.
In the same way, a black pixel is transformed into a white pixel
and this can go for ever.

\section{Exercises}

\begin{exercise} Check that $\setM_k$ as defined in Definition
\ref{definitionsetM} is monotone and translation invariant. \finex
\end{exercise}

\begin{exercise}  Koenderink and van Doorn defined the
dynamic shape of $X$ at scale $t$ to be the set of $\fxx$ such
that $G_t*\bmone_X(\fxx)\geq 1/2$. Check that this is  a
Gaussian-weighted median filter. \finex
\end{exercise}


\begin{exercise} \label{medianegalfonction}
 Consider the weighted median filter
defined on $S_1$ with $k=(1/2)\bmone_{[-1,1]}$. Compute $\fcnM_ku$
for   $u(x)= \frac 1{1+x^2}$. Compare the  result with the local
average $M_1u(x)=\frac 12\int_{-1}^1u(x+y)dy.$ What happens on
intervals where $u$ is monotone? \finex
\end{exercise}


\begin{exercise}\label{exercise9.2}
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}

\begin{exercise}Prove the following inequalities for any
measurable function :
\[
\sup_{|B|_k\geq\frac1{2}}\inf_{\fxy\in{\fxx+B}}u(\fxy)\geq\sup_{|B|_k>\frac1{2}}\inf_{\fxy\in{\fxx+B}}u(\fxy)\geq\inf_{|B|_k\geq\frac1{2}}\sup_{\fxy\in{\fxx+B}}u(\fxy),
\]
\[
\sup_{|B|_k\geq\frac1{2}}\inf_{\fxy\in{\fxx+B}}u(\fxy)
\geq\inf_{|B|_k>\frac1{2}}\sup_{\fxy\in{\fxx+B}}u(\fxy)
\geq\inf_{|B|_k\geq\frac1{2}}\sup_{\fxy\in{\fxx+B}}u(\fxy).
\]
\finex
\end{exercise}

\begin{exercise}{\bf Median filter on measurable  sets and functions}.
 The aim of the  exercise is to study the properties of the
 median filter extended to the set $\mathcal M$ of
all measurable sets of $\SN$ and all  bounded measurable functions ($u\in L^\infty(\SN)$). The definition of $\setM_k$
on $\mathcal M$ is identical to the current definition.


\medskip \noindent 1) Using the result of Exercise
\ref{3.5bismesurable}, show that one can define $\fcnM_k$ from
$\setM_k$ as a stack filter and that it is monotone, translation
and contrast invariant. In addition, $\setM_k$ and $\fcnM_k$ still
satisfy the commutation with thresholds,
$\levelset_{\lambda}\fcnM_ku=\setM_k\levelset_{\lambda}u.$

\medskip \noindent 2) Prove  that $\setM_k$ maps measurable sets
 into closed sets.  Deduce that if
$u$ is a measurable function,  then $\fcnM_ku$ is upper
semicontinuous and $\fcnM_k^-u$ is lower semicontinuous.

\medskip \noindent 3) Assume that $k$ is not  separable. Check
that the proof of Proposition  \ref{egalitedemedianmoinsetplus}
still applies to the more general $\fcnM_k$ and $\fcnM_k^-$,
applied to all measurable  functions.   Deduce that if $k$ is not
separable, then $\setM_k u$ is continuous  whenever $u$ is a
measurable function. \finex
\end{exercise}


\begin{exercise}\label{medmoinsetplusdiscrets}
The discrete median filters can more generally be defined in terms of a nonuniform measure $k$ that places different
weights $k_i$ on the points $\fxx_i$, so $|\{x_i\}|_k=k_i$.   Check that $\fcnM^-_ku\leq\fcnM_ku$. Prove that
$\fcnM^-_ku=\fcnM_ku$ if and only if there is no subset of the numbers $k_1,\ldots,k_N$ whose sum is $K/2$. In
particular,
 if the $k_i$ are integers and $K$ is odd, then $\fcnM^-_ku=\fcnM_ku$. \finex
\end{exercise}

\begin{exercise}\label{variationalmedian} {\bf Variational interpretations of the median
and the average values}.\newline Let $\text{arginf}_m g(m)$ denote
the value of $m$, if it exists, at which $g$ attains its infimum.
Consider   $N$ real numbers $\{\fxx_i\mid i=1,2,\ldots,N\}$ and
denote by $\fcnM((x_i)_i)$ and $\fcnM^-((x_i)_i)$ their usual
lower and upper median values (we already know that both are equal
if $N$ is odd but can be different if $N$ is even).
\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)_i)\leq \text{arginf}_m
\sum_{i=1}^N|x_i-m|\leq\fcnM((x_i)_i).
\]
\item Let $k=\bmone_B$, where $B$ is set with Lebesgue measure
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}




\section{Comments and references}

The remarkable denoising properties and numerical efficiency of median filters for the removal of all kinds of impulse noise in digital images, movies, and video signals are well known and acclaimed \cite{Davies:1988:NSI,Ip:1983:INC,Narendra:1978:NRM,Perlman:1987:AMF,Rawtani:1995:ISM}. The last reference cited as well as the next three all propose simple and efficient implementations of the median filter \cite{Astola:1987:RSM,Danielsson:1981:GMF,Huang:1979:FTD}. An introduction to weighted median filters can be found in \cite{Brownrigg:1984:WMF,Yli-Harja:1991:APM}, and information about some generalizations (conditional median filters, for example) can be found in \cite{Arce:1987:TAM,Lee:1985:GMF,Sun:1994:DPM}. The min, max, and median filters are particular instances of rank order filters; see \cite{Coyle:1988:ROO} for a general presentation of these filters. There are few studies on iterated median filters. The use of iterated median filters as a scale space is, however, proposed in \cite{Bangham:1996:MRM}. The extension of median filtering to multichannel (color) images is problematic, although there have been some interesting attempts \cite{Caselles:2000:VMF,Regazzoni:1997:NAV}.


\begin{figure}[!t]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig09.04.1.eps}
} \caption[\label{figure9.3}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. \label{figure9.3}}
\end{figure}
