%gmChap09.tex

\graphicspath{{./figures/chapter09/}}

\chapter{Median Filters and Mathematical Morphology}

This entire chapter is devoted to median filters. They are among the most characteristic and numerically efficient of the contrast-invariant monotone operators. The denoising effects of median filters are illustrated in Figures 9.1 and 9.2; the smoothing effect of a median filter is illustrated in Figure 9.3. 

As usual, there will be two associated operators, a set operator and a function operator. The only restrictions we make are the measurability assumptions, which are by now familiar: The domain of definition of the set operators will always be a family of measurable sets $\mathcal L$ that is closed under descending chains. Similarly, we require any domain $\mathcal F$ of the function operators to consist of measurable functions.

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$. We have already encountered weight functions, both specifically and generally: The operator $M_h$ in section 1.1 and the Gaussian $G_t$ are specific examples, while the operators introduced in Definition 2.1 (although they were not required to be positive) are general examples. By far the simplest example is the generalization of $M_h$ to $N$ dimensions. This 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)$.

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

Note that we have already encountered this idea in section 2.4. Koendernik 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$. Their 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$ 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$.

We are going to define the function operator $\fcnM_k$ associated with the set operator $\setM_k$, but as preparation we will show that $\setM_k$ is upper semicontinuous on the set of measurable sets $\mathcal L$.

\begin{lemma}
The set operator $\setM_k$ is upper semicontinuous on the measurable sets $\mathcal L$.
\end{lemma}
\begin{proof}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}

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

It is important to note that $\mathcal F$, the set of all measurable functions $u:\RR^N\to\barR$, is exactly the set of all functions $u$ defined by $u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\}$, where $(X_\lambda)_{\lambda\in\RR}$ is a closed descending chain in $\mathcal L$, the set of all measurable subsets of $\RR^N$. Expressed another way, the  measurable functions are in one-to-one correspondence with the closed descending chains of measurable sets. Here is another useful observation, which we set as an exercise.

\begin{exercise} If we represent $\setM_k$ by
\begin{equation}
\setM_kX=\{\fxx\mid \fxx+B\subset X, \text{ for some }B\in\mathcal B\},
\end{equation}
then $\mathcal B$ can be taken to be the set of all measurable sets $B$ such that $|B|_k=1/2$. (Note the similarity with Exercise 7.6.) \finex
\end{exercise}

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

\begin{proof}We mention again that $\setM_k$ is clearly monotone. It is also clearly translation invariant. The proof of \eqref{eq94} is read directly from Theorem 6.12. Equation \eqref{eq94} implies that $\fcnM_k$ commutes with all thresholds $\gamma_\lambda$, that is, $\fcnM_k\gamma_\lambda(u)= \gamma_\lambda(\fcnM_ku)$ for all $\lambda\in\RR$. This implies by Corollary 7.4 that $\fcnM_k$ has the sup-inf representation
\[
\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\}$. It is easy to see that $\mathcal B_0$ and $\mathcal B$ are equivalent sets of structuring elements (see Exercise 7.4), and thus we have \eqref{eq93}.
\end{proof}

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


We are going to consider three simple examples to gain some understanding about the action of $\fcnM_k$ on functions that have ``flat'' parts and jumps. The functions will be defined on $\RR$, and $k=(1/2)\bmone_{[-1,1]}$. This implies that $|B|_k=1/2$ if and only if $\mathrm{meas}\,([-1,1]\cap B)=1$. This is useful for computing the value of $\fcnM_ku(0)$ in the three  examples.

\begin{enumerate}[Ex{a}mple (1):]\setlength\itemsep{2pt}
\item $u(x)=x$ if $x\leq0$, and $u(x)=0$ if $x>0$. Then $\fcnM_ku(0)=0$, and the median value coincides with the supremum.

\item $u(x)=-1$ if $x\leq0$, and $u(x)=1$ if $x>0$. Then $\fcnM_ku(0)=1$, and we notice that the operator $\fcnM_k$ as we have defined it favors the value $+1$, although $-1$ and $+1$ would seem to be equally good candidates.

\item $u(x)=0$ if $x\leq-1/4$, $u(x)=1$ if $-1/4<x<1/3$, and $u(x)=2$ if $x\geq1/3$. Then $\fcnM_ku(0)=1$.
\end{enumerate}Notice that the median value in all three examples is different from the mean value on the neighborhood $[-1,1]$.

\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$. This is clear from Example (2) above, where $\fcnM_ku(0)=1$ and $\fcnM_k(-u)(0)=1$. As we have done elsewhere for other operators (the extrema killer, the Evans--Spruck extension, dilations, and erosions), we are going to define the ``lower'' forms of $\setM_k$ and $\fcnM_k$. 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}
which we have used previously as the definition for the lower form of a function operator. 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$ it is easily seen that 
\begin{equation}\label{eq97}
\setM^-_kX=(\setM_kX^c)^c.
\end{equation}
Since $\int_{X-\fxx}k(\fxy)\,\rmd \fxy+\int_{X^c-\fxx}k(\fxy)\,\rmd \fxy=1$ for all $\fxx$, we infer from \eqref{eq97} that
\begin{equation}
\setM^-_kX=\{\fxx\mid |X-\fxx|_k>\textstyle{\frac1{2}}\}.
\end{equation}

Although $\setM_k$ and $\setM^-_k$ both map measurable sets into measurable sets, remarkably $\setM_k$ maps measurable sets into closed sets and $\setM^-_k$ maps measurable sets into open sets.

\begin{lemma}If $X$ is a measurable subset of $\RR^N$, then $\setM_kX$ is closed and $\setM^-_kX$ is open.
\end{lemma}
\begin{proof}
If $\fxx_n\in\setM_kX$, then $|X-\fxx_n|_k\geq1/2$, which by definition of $k$-measure means that $\int_X k(\fxy-\fxx_n)\,\rmd\fxy\geq1/2$. If $\fxx_n\to\fxx$, then $\int_X k(\fxy-\fxx_n)\,\rmd\fxy\to\int_X k(\fxy-\fxx)\,\rmd\fxy$ by Proposition 1.2. Thus $|X-\fxx|_k\geq1/2$, and $\fxx\in\setM_kX$. That $\setM^-_kX$ is open follows from \eqref{eq97}.
\end{proof}

\begin{theorem}
If $u$ is a measurable function, then $\fcnM_ku$ is upper semicontinuous and $\fcnM^-_ku$ is lower semicontinuous.
\end{theorem}
\begin{proof}
If $u$ is a measurable function on $\RR^N$, then $\fcnM_ku(\fxx)=\sup\{\lambda\mid\fxx\in\setM_k\levelset_{\lambda}u\}$ by definition. Since $\setM_k$ is upper semicontinuous, we know that the upper level sets of $\fcnM_ku$ are the sets $\setM_k\levelset_{\lambda}u$, which by Lemma 9.5 are closed. Thus $\fcnM_ku$ is upper semicontinuous. The relation \eqref{eq96} implies that $\fcnM^-_ku$ is lower semicontinuous.
\end{proof}

Knowing this result, it is reasonable to ask, Are there conditions on $k$ that ensure $\fcnM_k$ maps continuous functions into continuous functions? The next result shows that a quite general condition on $k$ is sufficient to guarantee that not only is $\fcnM_ku$ continuous when $u$ is continuous, but also that $\fcnM_k$ and $\fcnM^-_k$ agree on continuous functions.

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

\begin{proposition}\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. If $u$ is continuous, then $\fcnM_ku=\fcnM^-_ku$ and $\fcnM_ku$ is continuous.
\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}<\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.
\]
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)$. 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).
\]
From this last inequality and $(i)$, we conclude that $\fcnM_ku=\fcnM^-_ku$ when $u$ is continuous. This means by Theorem 9.6 that $\fcnM_ku$ is both upper and lower continuous, which means that it is continuous.
\end{proof}

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

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

\begin{exercise}Prove the following inequalities:
\[
\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).
\]
\end{exercise}


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

We define a discrete median filter by considering a uniform discrete measure $k$ defined on a finite number of points $\{\fxx_i\mid i=1,\ldots,N\}$. This means that $k$ is defined by $|\{x_i\}|_k=1$, which is to say that Dirac masses $\delta_i$ exist at each point $\fxx_i$, $i\in\{1,\dots,N\}$. 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. Here are the definitions of the two discrete median filters:

\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 9.7. 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 9.5 shows how $\fcnM$ and $\fcnM^-$ relate to this functional.

The discrete median filters can also be defined in terms of a nonuniform measure $k$ that places different weights on the points $\fxx_i$. To see what this does, assume that the weights are integers $k_i$, so $|\{x_i\}|_k=k_i$.  
Then $k$ has total mass $\sum_{i=1}^N k_i=K$, and the condition $\text{card}(P)\geq N/2$ is replaced with $|P|_k\geq K/2$. As before, let $y_i=u(\fxx-\fxx_i)$ and display the data set as $y_1\leq y_2\leq\cdots\leq y_N$. Then $\fcnM_ku(\fxx)=y_j$, where $j$ is the largest index such that $k_j+\cdots+k_N\geq N/2$. To see this, transform the original ordered sequence  into the expanded ordered sequence
\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}
Then by the definition of $j$, $y_j\in\{\inf_{i\in P}y_i\mid |P|_k\geq K/2\}$, but $y_i$ for $i>j$ is not in this set. Thus, $\fcnM_ku(\fxx)=y_j$. Conversely, if $\fcnM_ku(\fxx)=y_j$, then $y_j$ is the largest member of the set $\{\inf_{i\in P}y_i\mid |P|_k\geq K/2\}$. This implies that $k_j+\cdots+k_N\geq N/2$, but that $k_i+\cdots+k_N<K/2$ for $i>j$. 

If $K$ is odd, what we have just done implies that $\fcnM^-_k=\fcnM_k$, and that $\fcnM_ku(\fxx)$ is equal to the ordinary median of the ordered set \eqref{newseq}. The following exercise completes this part of the theory.

\begin{exercise}It is clear that $\fcnM^-_ku\leq\fcnM_ku$, either by Proposition 9.7, or by the above discussion. 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 $K$ is odd, then $\fcnM^-_ku=\fcnM_ku$. \finex
\end{exercise}

\begin{exercise}Let $\text{arginf}_m g(m)$ denote the value of $m$, if it exists, at which $g$ attains its infimum. Consider the $N$ real numbers $\{\fxx_i\mid i=1,2,\ldots,N\}$.
\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).
\]
\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}

Finally, we wish to show that the discrete median filter $\fcnM$ is a cyclic operator on discrete images. To be precise, we assume that the digital image $u$ has been periodized so that we have a $C$-periodic digital image. Assume that the original image defined on he hypercube $[0,1]^N$ contained $n$ pixels. Then the total number of gray levels is bounded by $n$. Since a median filter $\fcnM$ is contrast invariant, the grey levels of $\fcnM u$ are   among the original ones. The same is true for the $k$th iteration $\fcnM^ku$. Since that maximum number of different realizations is $n^n$, after $n^n$ iterations, there will be two identical images among the images $\fcnM^ku$, $k\in\{1,2,\ldots,n^n\}$. Thus, $\fcnM$ is cyclic. 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.

\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[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}
