and can be solved even by $\mathcal{O}(N)$ operations. A popular selection algorithm is Quick-Select which has $\mathcal{O}(N)$ average complexity but $\mathcal{O}(N^2)$ worst-case complexity. By using the *median of medians* procedure [@Blum-JCSS73] for selecting the so-called *pivot* element in Quick-Select, its worst-case complexity can be improved to $\mathcal{O}(N)$.

**Weighted median.**

The median of a finite set $\mathcal{X}$ with weights $w:\mathcal{X}\to\mathbb{R}^+$ can be computed by sorting $\mathcal{X}$, which takes $\mathcal{O}(N\log N)$ operations, followed by cumulating the weights for the members of $\mathcal{X}$ in ascending order, which requires $\mathcal{O}(N)$ effort, yielding an overall $\mathcal{O}(N\log N)$ complexity, both worst-case and average. In [@Rauh-icip10] an algorithm with $\mathcal{O}(N)$ average complexity is proposed.

Univariate Median Filtering of Images {#sec-medf}
=====================================

The definition of median filters for grey-value images and some important properties of these are discussed in this section.

Standard Discrete Median Filtering
----------------------------------

A discrete grey-value image $u$ is an array of intensities $u_{i,j}$ where $i=1,\ldots,N_x$ and $j=1,\ldots,N_y$ enumerate the locations (pixels) of a regular grid in horizontal and vertical direction, respectively.

The classical median filter [@Tukey-Book71] processes a discrete grey-value image $u$ using a *sliding window*. A sliding window can be described by a set $S=\{(\Delta i_1,\Delta j_1),\ldots,(\Delta i_r,\Delta j_r)\}$ of integer pairs $(\Delta 