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]:
using PyPlot
using NtToolBox

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("NtToolBox/src/data/hibiscus.png", n);

Display $f_0$.

In [5]:
figure(figsize = (5,5))
imageplot(f0)

Noise level $\si$.

In [6]:
sigma = .04;

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

In [7]:
using Distributions
f = f0 .+ sigma.*rand(Normal(), n, n);

Display $f$.

In [8]:
figure(figsize = (5,5))
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 [11]:
# include("NtToolBox/src/ndgrid.jl")
(X, Y) = meshgrid(1 : n, 1 : n)
(dX, dY) = meshgrid(-w : w, -w : w)

dX = reshape(dX, (1, 1, w1, w1))
dY = reshape(dY, (1, 1, w1, w1))
X = repeat(X, inner = [1, 1, w1, w1]) + repeat(dX, inner = [n, n, 1, 1])
Y = repeat(Y, inner = [1, 1, w1, w1]) + repeat(dY, inner = [n, n, 1, 1]);

We handle boundary condition by reflexion.

In [12]:
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 [13]:
I = X + (Y-1)*n
for i in 1 : Base.div(n, w)
    for j in 1 : Base.div(n, w)
        I[i, j, :, :] = transpose(I[i, j, :, :])
    end
end
        
Pi = f -> reshape(f[I], (n, n, w1*w1))
Pi(f);

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 [14]:
P = Pi(f);

Display some example of patches.

In [13]:
figure(figsize = (5,5))

for i in 1:16
    x = rand(1:n)
    y = rand(1:n)
    imageplot(reshape(P[x, y, :], (w1, w1)), "", [4, 4, i])
end

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 [14]:
Pmean = f -> mean(Pi(f), 3)
Pmean(f);
Out[14]:
256×256×1 Array{Float64,3}:
[:, :, 1] =
 0.148283   0.154691   0.16204    …  0.282161   0.296818   0.29694  
 0.147616   0.151984   0.159783      0.286      0.300655   0.303734 
 0.143027   0.146224   0.153917      0.280187   0.296895   0.299887 
 0.141167   0.145997   0.152315      0.280011   0.294418   0.296603 
 0.144704   0.148478   0.15563       0.262443   0.268037   0.265238 
 0.153427   0.15714    0.164824   …  0.244728   0.24601    0.244591 
 0.158687   0.161211   0.172276      0.245359   0.246366   0.244366 
 0.163632   0.16667    0.178831      0.257029   0.257915   0.256602 
 0.17627    0.179749   0.188939      0.267264   0.270653   0.268242 
 0.189338   0.188915   0.198728      0.270065   0.273721   0.273194 
 0.207416   0.200286   0.209368   …  0.249557   0.25288    0.255951 
 0.221554   0.214171   0.216342      0.236418   0.2388     0.240719 
 0.229538   0.221161   0.215968      0.23267    0.235947   0.239135 
 ⋮                                ⋱                        ⋮        
 0.133876   0.130373   0.119092      0.110398   0.0994353  0.0971842
 0.123187   0.121941   0.108918   …  0.108255   0.0968821  0.0955378
 0.105233   0.1042     0.0916193     0.104851   0.0935978  0.0905933
 0.0908436  0.0901411  0.0830293     0.100059   0.0891829  0.0822383
 0.0729072  0.0738451  0.0685899     0.0934663  0.0817375  0.0744956
 0.0611652  0.0600262  0.0574476     0.0927329  0.0830264  0.0773482
 0.0480283  0.0459777  0.0461525  …  0.0894689  0.0814104  0.0763362
 0.0400716  0.0388043  0.040175      0.0909061  0.0838651  0.0806565
 0.0340859  0.0313242  0.0339256     0.0880422  0.0859505  0.0841579
 0.0340277  0.0324301  0.0339947     0.0840658  0.0830444  0.0827583
 0.0324908  0.0306488  0.0309028     0.0822555  0.0821955  0.0827708
 0.0346863  0.031425   0.0310778  …  0.0857721  0.0867293  0.0881238

Display it.

In [15]:
figure(figsize = (5,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 [16]:
p = 100
psi = f -> f.^(1/p)
ipsi = f -> f.^p

figure(figsize = (5,5))
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 [17]:
r = beta -> min(ceil(beta*w1*w1), w1*w1 - 1)
Out[17]:
(::#11) (generic function with 1 method)

Shortcut for the rank filter.

In [18]:
subsample = (x, s) -> x[: , : , s]
phi = (f, beta) -> subsample(sort(Pi(f), 3), Int(r(beta)) + 1)
Out[18]:
(::#15) (generic function with 1 method)

Exercise 1

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

In [21]:
include("NtSolutions/denoisingadv_7_rankfilters/exo1.jl")
Out[21]:
256×256 Array{Float64,2}:
 0.198424  0.240929  0.240929  0.389259  …  0.630043  0.630043  0.630043
 0.198424  0.240929  0.240929  0.389259     0.630043  0.630043  0.630043
 0.198424  0.240929  0.240929  0.389259     0.630043  0.630043  0.630043
 0.198424  0.240929  0.240929  0.389259     0.630043  0.630043  0.630043
 0.198424  0.240929  0.253447  0.407904     0.524932  0.524932  0.524932
 0.262391  0.262391  0.312458  0.407904  …  0.468698  0.468698  0.468698
 0.268735  0.268735  0.463218  0.463218     0.431761  0.431761  0.376411
 0.268735  0.306711  0.463218  0.463218     0.431761  0.431761  0.376411
 0.268735  0.306711  0.463218  0.463218     0.431761  0.431761  0.376411
 0.382722  0.382722  0.463218  0.463218     0.431761  0.431761  0.376411
 0.382722  0.382722  0.463218  0.463218  …  0.348417  0.348417  0.348417
 0.382722  0.382722  0.463218  0.463218     0.348417  0.348417  0.348417
 0.398823  0.398823  0.463218  0.463218     0.348417  0.348417  0.348417
 ⋮                                       ⋱                      ⋮       
 0.219218  0.219218  0.219218  0.219218     0.234103  0.234103  0.234103
 0.219218  0.219218  0.219218  0.219218  …  0.234103  0.234103  0.234103
 0.219218  0.219218  0.219218  0.219218     0.234103  0.234103  0.234103
 0.219218  0.219218  0.219218  0.219218     0.227547  0.227547  0.227547
 0.219218  0.219218  0.219218  0.219218     0.210707  0.172393  0.172393
 0.219218  0.219218  0.219218  0.219218     0.210707  0.172393  0.172393
 0.219218  0.219218  0.219218  0.219218  …  0.210707  0.151441  0.151441
 0.134365  0.134365  0.134365  0.134365     0.210707  0.151441  0.151441
 0.134365  0.134365  0.134365  0.134365     0.151308  0.151308  0.151308
 0.102421  0.102421  0.128846  0.128846     0.151308  0.151308  0.151308
 0.102421  0.102421  0.102421  0.102421     0.151308  0.151308  0.151308
 0.102421  0.102421  0.102421  0.102421  …  0.151308  0.151308  0.151308
In [20]:
## Insert your code here.

The case $\beta=0$ corresponds to the closing operator from mathematical morphology (min filter).

In [29]:
closing = f -> phi(f, 0)
figure(figsize = (5,5))
imageplot(closing(f))

The case $\beta=1$ corresponds to the opening operator from mathematical morphology (max filter).

In [30]:
opening = f -> phi(f, 1)
figure(figsize = (5,5))
imageplot(opening(f))

Exercise 2

Compute a closing followed by an opening.

In [31]:
include("NtSolutions/denoisingadv_7_rankfilters/exo2.jl")
In [24]:
## Insert your code here.

Exercise 3

Compute an opening followed by a closing.

In [32]:
include("NtSolutions/denoisingadv_7_rankfilters/exo3.jl")
In [26]:
## Insert your code here.

Exercise 4

Perform iterated opening and closing.

In [33]:
include("NtSolutions/denoisingadv_7_rankfilters/exo4.jl")