Rank Filters for Image Processing¶

Important: Please read the installation page for details about how to install the toolboxes. $\newcommand{\dotp}[2]{\langle #1, #2 \rangle}$ $\newcommand{\enscond}[2]{\lbrace #1, #2 \rbrace}$ $\newcommand{\pd}[2]{ \frac{ \partial #1}{\partial #2} }$ $\newcommand{\umin}[1]{\underset{#1}{\min}\;}$ $\newcommand{\umax}[1]{\underset{#1}{\max}\;}$ $\newcommand{\umin}[1]{\underset{#1}{\min}\;}$ $\newcommand{\uargmin}[1]{\underset{#1}{argmin}\;}$ $\newcommand{\norm}[1]{\|#1\|}$ $\newcommand{\abs}[1]{\left|#1\right|}$ $\newcommand{\choice}[1]{ \left\{ \begin{array}{l} #1 \end{array} \right. }$ $\newcommand{\pa}[1]{\left(#1\right)}$ $\newcommand{\diag}[1]{{diag}\left( #1 \right)}$ $\newcommand{\qandq}{\quad\text{and}\quad}$ $\newcommand{\qwhereq}{\quad\text{where}\quad}$ $\newcommand{\qifq}{ \quad \text{if} \quad }$ $\newcommand{\qarrq}{ \quad \Longrightarrow \quad }$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\EE}{\mathbb{E}}$ $\newcommand{\Zz}{\mathcal{Z}}$ $\newcommand{\Ww}{\mathcal{W}}$ $\newcommand{\Vv}{\mathcal{V}}$ $\newcommand{\Nn}{\mathcal{N}}$ $\newcommand{\NN}{\mathcal{N}}$ $\newcommand{\Hh}{\mathcal{H}}$ $\newcommand{\Bb}{\mathcal{B}}$ $\newcommand{\Ee}{\mathcal{E}}$ $\newcommand{\Cc}{\mathcal{C}}$ $\newcommand{\Gg}{\mathcal{G}}$ $\newcommand{\Ss}{\mathcal{S}}$ $\newcommand{\Pp}{\mathcal{P}}$ $\newcommand{\Ff}{\mathcal{F}}$ $\newcommand{\Xx}{\mathcal{X}}$ $\newcommand{\Mm}{\mathcal{M}}$ $\newcommand{\Ii}{\mathcal{I}}$ $\newcommand{\Dd}{\mathcal{D}}$ $\newcommand{\Ll}{\mathcal{L}}$ $\newcommand{\Tt}{\mathcal{T}}$ $\newcommand{\si}{\sigma}$ $\newcommand{\al}{\alpha}$ $\newcommand{\la}{\lambda}$ $\newcommand{\ga}{\gamma}$ $\newcommand{\Ga}{\Gamma}$ $\newcommand{\La}{\Lambda}$ $\newcommand{\si}{\sigma}$ $\newcommand{\Si}{\Sigma}$ $\newcommand{\be}{\beta}$ $\newcommand{\de}{\delta}$ $\newcommand{\De}{\Delta}$ $\newcommand{\phi}{\varphi}$ $\newcommand{\th}{\theta}$ $\newcommand{\om}{\omega}$ $\newcommand{\Om}{\Omega}$

This numerical tour explores non-linear local filters that proceeds by ordering the pixels in a neighboorhood and selecting a given ranked entry.

In [2]:

options(warn=-1) # turns off warnings, to turn on: "options(warn=0)"


library(imager)
library(png)

for (f in list.files(path="nt_toolbox/toolbox_general/", pattern="*.R")) {
    source(paste("nt_toolbox/toolbox_general/", f, sep=""))
}

for (f in list.files(path="nt_toolbox/toolbox_signal/", pattern="*.R")) {
    source(paste("nt_toolbox/toolbox_signal/", f, sep=""))
}

source("nt_toolbox/toolbox_wavelet_meshes/meshgrid.R")
options(repr.plot.width=3.5, repr.plot.height=3.5)

Continuous Rank Filtering¶

We consider an image $f : [0,1]^2 \rightarrow \RR$.

For any $\beta \in [0,1]$, we define the rank filter $\phi_\be^B$ of order $\beta$ associated to a set $B$ to be $$ g = \phi_\beta^B(f) \qwhereq g(x) = \inf \: \enscond{t \in \RR}{ \mu( f^{-1}(]-\infty,t]) \cap x+B ) \geq \mu(B)/2 }. $$ where $\mu$ is the Lebesgue measure on $\RR$.

One usually assumes that $B$ is the ball of radius $\epsilon>0$ $$ B = B_\epsilon = \enscond{x}{\norm{x} \leq \epsilon}. $$

When $\be=0$ (resp. $\be=1$, resp. $\be=1/2$), then $g(x)$ is the miniminimum (resp. maximum, resp. median) value of $f$ in a small neighboorhood of radius $\epsilon$ $$ \phi_0^{B_\epsilon}(f)(x) = \umin{\norm{y-x} \leq \epsilon} f(y), $$ $$ \phi_{1/2}^{B_\epsilon}(f)(x) = \umax{\norm{y-x} \leq \epsilon} f(y), $$ $$ \phi_{1}^{B_\epsilon}(f)(x) = \underset{\norm{y-x} \leq \epsilon}{\text{median}} f(y). $$

The operator $\phi_\beta^B$ is contrast-invariant, meaning that it computes with increasing functions $ \psi : \RR \rightarrow \RR $ $$ \phi_\beta^B \circ \psi = \psi \circ \phi_\beta^B. $$ The axiomatic study of contrast invariant operator was initiated in the comunity of mathematical morphology, see Matheron75, Tukey77, Serra82.

Note also that there exist generalization of rank filters (and in particular the median filter) to vector valued images $ f : [0,1]^2 \rightarrow \RR^d$. Since the notion of rank does not exists anymore, one has to rely on variational caracteriation of the median, see for instance CasSapChu00.

The medial filtering is the most popular rank filter. It is particularly efficient to remove impulse noise, see for instance Piterbarg84, FanHall94. See also AriasDon99 for a theoritical analysis of median filtering and of a two-stage iterated version.

Patches in Images¶

We apply rank filters to discretized images by interpreting them as piecewise constant functions.

Size $N = n \times n$ of the image.

In [3]:

n <- 256

We load an image $f_0 \in \RR^N$.

In [4]:

f0 = load_image("nt_toolbox/data/hibiscus.png",n)

Display $f_0$.

In [5]:

imageplot(f0)

Noise level $\si$.

In [6]:

sigma <- 0.04

Generate a noisy image $f=f_0+\epsilon$ where $\epsilon \times \Nn(0,\si^2\text{Id}_N)$.

In [7]:

f <- as.cimg(f0) + sigma*as.cimg(rnorm(n**2))

Display $f$.

In [8]:

imageplot(clamp(f))

For simplicity, we consider the case where the set $B$ is a square of $w_1 \times w_2$ pixels. where we denote $w$ to be the half width of the patches, and $w_1=2w+1$ the full width.

In [9]:

w <- 3
w1 <- 2*w + 1

We define the patch extraction operator $$ p = p_x(f) \in \RR^{w_1 \times w_1} \qwhereq \forall -w \leq s_1,s_2 \leq w, \quad p(s) = f(x+s). $$

We now define the function $\Pi(f) = (p_x(f))_x $ that extracts all possible patches.

We set up large $(n,n,w_1,w_1)$ matrices to index the the X and Y position of the pixel to extract.

In [10]:

grid <- meshgrid_4d(1:n, 1:n, (-w):w, (-w):w)
X <- grid$X ; Y <- grid$Y ; dX <- grid$Z ; dY <- grid$S
X <- X + dX
Y <- Y + dY

We handle boundary condition by reflexion.

In [11]:

X[X < 1] <- 2-X[X < 1] 
Y[Y < 1] <- 2-Y[Y < 1]
X[X > n] <- 2*n-X[X > n]
Y[Y > n] <- 2*n-Y[Y > n]

Patch extractor operator $\Pi$.

In [12]:

I <- (X-1) + (Y-1)*n
for (i in 1:(n%/%w)){
    for (j in 1:(n%/%w)){
        I[i,j,,] <- t(I[i,j,,])
    }
}

Pi <- function(f){ array(as.vector(f)[I+1], c(n,n,w1*w1)) }

We store the patches $\Pi(f)$ as a $n \times n \times w_1^2$ matrix $P$ such that, for each pixel $x$, $P(x)$ is a vector of size $w_1^2$ storing the entries of $p_x(f)$.

In [13]:

P <- Pi(f)

Display some example of patches.

In [14]:

options(repr.plot.width=7, repr.plot.height=7)

for (i in 1:16){
    x <- sample(1:n, 1)
    y <- sample(1:n, 1)
    imageplot(array(P[x, y,],c(w1,w1)), '', c(4, 4, i))
}

Linear Filter¶

A linear filter (convolution) can be computed using this patch representation as $$ g(x) = \sum_{i} \la_i p_x(f)_i. $$

In the case where $\la_i=1/w_1^2$, this defines the mean value inside the patch: $$ g(x) = \frac{1}{w_1^2} \sum_{i} p_x(f)_i. $$

In [15]:

Pmean <- function(f){ array(apply(Pi(f), c(2,1), mean), c(n,n)) }

Display it.

In [16]:

options(repr.plot.width=3.5, repr.plot.height=3.5)

imageplot(Pmean(f))

Note that this is not a rank filter (this a linear filter) and that it is not contrast invariant. This is shown by displaying $$ \phi_\beta^B(f) - \psi^{-1} \circ \phi_\beta^B \circ \psi(f) $$ which is non-zero.

In [17]:

p <- 100
psi <- function(f){ f**(1/p) }
ipsi <- function(f){ f**p }

imageplot(Pmean(abs(f)) - ipsi(Pmean(psi(abs(f)))))

Opening and Closing Rank Filters¶

We now come back to the discrete computation of a rank filter $\phi_\be^B$ for $B$ a square of width $w_1 \times w_1$ pixels.

It is defined as $g=\phi_\beta^B(f)$ where $$ g(x) = \text{rank}_{r(\beta)}( p_x(f) ) $$ where $\text{rank}_r(v)$ extracted the element of order $k$ in the sorted value of $v \in \RR^Q$ (here $Q=w_1^2$). More precisely, we denote $$ v_{\si(1)} \leq v_{\si(2)} \leq \ldots \leq v_{\si(Q)} $$ where $\si \in \Sigma_Q$ is an ordering permutation, which can be computed in $ O(N \log(N)) $ operations with the QuickSort algorithm. Then the ranked valued is $$ \text{rank}_r(v) = v_{\si(r)}. $$

In order to be consistent with the continuous definition of the rank filter, one should define the rank as $$ r=r(\beta) = \lfloor Q r \rfloor. $$

In [18]:

r <- function(beta){ min(ceiling(beta*w1*w1), w1*w1-1) }

Shortcut for the rank filter.

In [19]:

subsample <- function(x,s){ x[ , , s+1] }
phi <- function(f, beta){ subsample(aperm(apply(Pi(f), c(2,1), sort), c(2,3,1)), r(beta)) }

Exercise 1

Compute the rank filter for several values of $\beta$.

In [20]:

options(repr.plot.width=7, repr.plot.height=5)

source("nt_solutions/denoisingadv_7_rankfilters/exo1.R")