Edge Detection¶
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 local differential operators (grad, div, laplacian) and their use to perform edge detection.
using PyPlot
using NtToolBox
using Autoreload
arequire("NtToolBox")
Diffusion and Convolution¶
To obtain robust edge detection method, it is required to first remove the noise and small scale features in the image. This can be achieved using a linear blurring kernel.
Size of the image.
n = 256*2;
Load an image $f_0$ of $N=n \times n$ pixels.
f0 = load_image("NtToolBox/src/data/hibiscus.png", n);
Display it.
figure(figsize=(5,5))
imageplot(f0)
Blurring is achieved using convolution: $$ f \star h(x) = \sum_y f(y-x) h(x) $$ where we assume periodic boundary condition.
This can be computed in $O(N\log(N))$ operations using the FFT, since $$ g = f \star h \qarrq \forall \om, \quad \hat g(\om) = \hat f(\om) \hat h(\om). $$
cconv = (f, h) -> real(plan_ifft((plan_fft(f)*f).*(plan_fft(h)*h))*((plan_fft(f)*f).*(plan_fft(h)*h)));
Define a Gaussian blurring kernel of width $\si$: $$ h_\si(x) = \frac{1}{Z} e^{ -\frac{x_1^2+x_2^2}{2\si^2} }$$ where $Z$ ensure that $\hat h(0)=1$.
include("NtToolBox/src/ndgrid.jl")
t = [collect(0 : Base.div(n, 2)); collect(-Base.div(n, 2) + 1 : -1)]
(X2, X1) = meshgrid(t, t)
normalize = h -> h./sum(h)
h = sigma -> normalize(exp(-(X1.^2 + X2.^2)./(2*sigma^2)));
Define blurring operator.
blur = (f, sigma) -> cconv(f, h(sigma));
Exercise 1
Test blurring with several blurring size $\si$.
include("NtSolutions/segmentation_1_edge_detection/exo1.jl");
## Insert your code here.
Gradient Based Edge Detectiors¶
The simplest edge detectors only make use of the first order derivatives.
For continuous functions, the gradient reads $$ \nabla f(x) = \pa{ \pd{f(x)}{x_1}, \pd{f(x)}{x_2} } \in \RR^2. $$
We discretize this differential operator using first order finite differences. $$ (\nabla f)_i = ( f_{i_1,i_2}-f_{i_1-1,i_2}, f_{i_1,i_2}-f_{i_1,i_2-1} ) \in \RR^2. $$ Note that for simplity we use periodic boundary conditions.
Compute its gradient, using (here decentered) finite differences.
s = [[n]; collect(1:n-1)]
nabla = f -> cat(3, f - f[s, :], f - f[:, s]);
One thus has $ \nabla : \RR^N \mapsto \RR^{N \times 2}. $
v = nabla(f0);
One can display each of its components.
figure(figsize = (10, 10))
imageplot(v[:,:,1], L"\frac{d}{dx}", [1,2,1])
imageplot(v[:,:,2], L"\frac{d}{dy}", [1,2,2])
A simple edge detector is simply obtained by obtained the gradient magnitude of a smoothed image.
A very simple edge detector is obtained by simply thresholding the gradient magnitude above some $t>0$. The set $\Ee$ of edges is then $$ \Ee = \enscond{x}{ d_\si(x) \geq t } $$ where we have defined $$ d_\si(x) = \norm{\nabla f_\si(x)}, \qwhereq f_\si = f_0 \star h_\si. $$
Compute $d_\si$ for $\si=1$.
sigma = 1
d = sqrt(sum(nabla(blur(f0, sigma)).^2, 3));
Display it.
figure(figsize=(5,5))
imageplot(d[:, :])