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 tour explores the use of Fast Marching methods in 2-D.
from __future__ import division
import nt_toolbox as nt
from nt_solutions import fastmarching_1_2d as solutions
%matplotlib inline
%load_ext autoreload
%autoreload 2
Shortest paths are 2D curves that minimize a weighted length according to a given metric $W(x)$ for $x \in [0,1]^2$. The metric is usually computed from an input image $f(x)$.
The length of a curve $ t \in [0,1] \mapsto \gamma(t) \in [0,1]^2 $ is $$ L(\gamma) = \int_0^1 W(\gamma(t)) \norm{\gamma'(t)} \text{d} t. $$
Note that $L(\gamma)$ is invariant under re-parameterization of the curve $\gamma$.
A geodesic curve $\gamma$ between two points $x_0$ and $x_1$ has minimum length among curves joining $x_0$ and $x_1$, $$ \umin{\ga(0)=x_0, \ga(1)=x_1} L(\ga). $$ A shortest curve thus tends to pass in areas where $W$ is small.
The geodesic distance between the two points is then $d(x_0,x_1)=L(\gamma)$ is the geodesic distance according to the metric $W$.
The geodesic distance map $D(x)=d(x_0,x)$ to a fixed starting point $x_0$ is the unique viscosity solution of the Eikonal equation $$ \norm{ \nabla D(x)} = W(x) \qandq D(x_0)=0. $$
This equation can be solved numerically in $O(N \log(N))$ operation on a discrete grid of $N$ points.
We load the input image $f$.
clear options
n = 300
name = 'road2'
f = rescale(load_image(name, n))
Display the image.
imageplot(f)
Define start and end points $x_0$ and $x_1$ (note that you can use your own points).
x0 = [14; 161]
x1 = [293; 148]
The metric is defined according to $f$ in order to be low at pixel whose value is close to $f(x)$. A typical example is $$ W(x) = \epsilon + \abs{f(x_0)-f(x)} $$ where the value of $ \epsilon>0 $ should be increased in order to obtain smoother paths.
epsilon = 1e-2
W = epsilon + abs(f-f(x0(1), x0(2)))
Display the metric $W$.
imageplot(W)
Set options for the propagation: infinite number of iterations, and stop when the front hits the end point.
options.nb_iter_max = Inf
options.end_points = x1
Perform the propagation, so that $D(a,b)$ is the geodesic distance between the pixel $x_1=(a,b)$ and the starting point $x_0$. Note that the function |perform_fast_marching| takes as input the inverse of the metric $1/W(x)$.
[D, S] = perform_fast_marching(1./ W, x0, options)
Display the propagated distance map $D$. We display in color the distance map in areas where the front has propagated, and leave in black and white the area where the front did not propagate.
hold on
imageplot(convert_distance_color(D, f))
h = plot(x0(2), x0(1), '.r'); set(h, 'MarkerSize', 25)
h = plot(x1(2), x1(1), '.b'); set(h, 'MarkerSize', 25)
Exercise 1
Using |options.nb_iter_max|, display the progressive propagation. This corresponds to displaying the front $ \enscond{x}{D(x) \leq t} $ for various arrival times $t$.
solutions.exo1()
## Insert your code here.
Once the geodesic distance map $D(x)$ to a starting point $x_0$ is computed, the geodesic curve between any point $x_1$ and $x_0$ extracted through gradient descent $$ \ga'(t) = - \eta_t \nabla D(\ga(t)), $$ where $\eta_t>0$ controls the parameterization speed of the resulting curve. To obtain unit speed parameterization, one can use $\eta_t = \norm{\nabla D(\ga(t))}^{-1}$.
Recompute the geodesic distance map $D$ on the whole grid.
options.nb_iter_max = Inf
options.end_points = []
[D, S] = perform_fast_marching(1./ W, x0, options)
Display $D$.
imageplot(D)
colormap jet(256)
Compute the gradient $G_0(x) = \nabla D(x) \in \RR^2$ of the distance map. Use centered differences.
options.order = 2
G0 = grad(D, options)
Normalize the gradient to obtained $G(x) = G_0(x)/\norm{G_0(x)}$, in order to have unit speed geodesic curve (parameterized by arc length).
G = G0 ./ repmat(sqrt(sum(G0.^2, 3)), [1 1 2])
Display $G$.
imageplot(G)
colormap jet(256)
The geodesic is then numerically computed using a discretized gradient descent, which defines a discret curve $ (\ga_k)_k $ using $$ \ga_{k+1} = \ga_k - \tau G(\ga_k) $$ where $\ga_k \in \RR^2$ is an approximation of $\ga(t)$ at time $t=k\tau$, and the step size $\tau>0$ should be small enough.
Step size $\tau$ for the gradient descent.
tau = .8
Initialize the path with the ending point.
gamma = x1
Define a shortcut to interpolate $G$ at a 2-D points. Warning: the |interp2| switches the role of the axis ...
Geval = lambda G, x: [interp2(1: n, 1: n, G(: , : , 1), x(2), x(1)); ...
interp2(1: n, 1: n, G(: , : , 2), x(2), x(1))]
Compute the gradient at the last point in the path, using interpolation.
g = Geval(G, gamma(: , end))
Perform the descent and add the new point to the path.
gamma(: , end + 1) = gamma(: , end) - tau*g
Exercise 2
Perform the full geodesic path extraction by iterating the gradient descent. You must be very careful when the path become close to $x_0$, because the distance function is not differentiable at this point. You must stop the iteration when the path is close to $x_0$.
solutions.exo2()
## Insert your code here.
Display the curve on the image background.
clf; hold on
imageplot(f)
h = plot(gamma(2, : ), gamma(1, : ), '.b'); set(h, 'LineWidth', 2)
h = plot(x0(2), x0(1), '.r'); set(h, 'MarkerSize', 25)
h = plot(x1(2), x1(1), '.b'); set(h, 'MarkerSize', 25)
axis ij
Display the curve on the distance background.
clf; hold on
imageplot(D); colormap jet(256)
h = plot(gamma(2, : ), gamma(1, : ), '.b'); set(h, 'LineWidth', 2)
h = plot(x0(2), x0(1), '.r'); set(h, 'MarkerSize', 25)
h = plot(x1(2), x1(1), '.b'); set(h, 'MarkerSize', 25)
axis ij
Exercise 3
Study the influence of the $\epsilon$ parameter.
solutions.exo3()
## Insert your code here.
Exercise 4
Perform the shortest path extraction for various images such as 'cavern' or 'mountain'. oad radient isplay
solutions.exo4()
## Insert your code here.
It is possible to extract the boundary of an object using shortest paths that follows region of high gradient.
First we load an image $f$.
n = 256
name = 'cortex'
f = rescale(sum(load_image(name, n), 3))
Display it.
imageplot(f)
An edge-attracting potential $W(x)$ should be small in regions of high gradient. A popular choice is $$ W(x) = \frac{1}{\epsilon + G_\si \star G(x)} \qwhereq G(x) = \norm{\nabla f(x)}, $$ and where $G_\si$ is a Gaussian kernel of variance $\si^2$.
Compute the gradient norm $G(x)$.
G = grad(f, options)
G = sqrt(sum(G.^2, 3))
Smooth it by $G_\si$.
sigma = 3
Gh = perform_blurring(G, sigma)
Display the smoothed gradient $ G \star G_\si $.
imageplot(Gh)
Compute the metric.
epsilon = 0.01
W = 1./ (epsilon + Gh)
Display it.
imageplot(W)
Set two starting point $ \Ss = \{x_0^1,x_0^2\} $ (you can use other points).
x0 = [[136; 53] [123; 205]]
Compute the Fast Marching from these two base points.
options.nb_iter_max = Inf
options.end_points = []
[D, S, Q] = perform_fast_marching(1./ W, x0, options)
Display the geodesic distance (with color normalization).
clf; hold on
imageplot(perform_hist_eq(D, 'linear'))
h = plot(x0(2, : ), x0(1, : ), '.r'); set(h, 'MarkerSize', 25)
colormap jet(256)
The Voronoi segmentation associated to $\Ss$ is $$ \Cc_i = \enscond{x}{ \forall j \neq i, \; d(x_0^i,x) \leq d(x_0^j,x) }. $$
This Voronoi segmentation is computed during the Fast Marching propagation and is encoded in the partition function $Q(x)$ using $\Cc_i = \enscond{x}{Q(x)=i}$.
Display the distance and the Voronoi segmentation.
clf; hold on
A = zeros(n, n, 3); A(: , : , 1) = rescale(Q); A(: , : , 3) = f
imageplot(A)
h = plot(x0(2, : ), x0(1, : ), '.g'); set(h, 'MarkerSize', 25)
Exercise 5
Extract the set of points that are along the boundary of the Voronoi region. This corresponds for instance to the points of the region $ \enscond{x}{Q(x)=1} $ that have one neighbor inside the region $ \enscond{x}{Q(x)=2} $. Compute the geodesic distance $D(x)$ at these points, and choose two points $a$ and $b$ on this boundary that have small values of $D$. int: you can use a convolution |U=conv2(double(Q==2),h,'same')| with a ell chose kernel |h| to located the points |U>0| with at least 1 eighbor.
ubplot(2,1,1);
solutions.exo5()
## Insert your code here.
Exercise 6
Extract the geodesics joining $a$ and $b$ to the two starting points (this makes 4 geodesic curves). Use them to perform segmentation. D1 = D; D1(D1==Inf) = max(D1(D1~=Inf)); isplay the curves
solutions.exo6()
## Insert your code here.
One can extract a network of geodesic curve starting from a central point to detect vessels in medical images.
Load an image. This image is extracted from the <http://www.isi.uu.nl/Research/Databases/DRIVE/ DRIVE database> of retinal vessels.
n = 256
name = 'vessels'
f = rescale(load_image(name, n))
Display it.
imageplot(f)
We clean the image by substracting the smoothly varying background $$ f_1 = f - G_\si \star f, $$ where $G_\si$ is a Gaussian kernel of variance $\si^2$. Computing $f_1$ corresponds to a high pass filtering.
sigma = 20
f1 = perform_blurring(f, sigma) - f
Display this normalized image.
imageplot(f1)
We compute a metric tthat is small for large values of $f_1$: $$ W(x) = \epsilon + \abs{f_1(x)-c} \qwhereq c = \umax{x} f_1(x). $$
c = max(f1(: ))
epsilon = 1e-2
W = epsilon + abs(f1-c)
Display the metric.
imageplot(W)
Select a central point $x_0$ for the network.
x0 = [142; 226]
Exercise 7
Perform partial propagations from $x_0$.
solutions.exo7()
## Insert your code here.
Exercise 8
Extract geodesics joining several points $x_1$ to the central point $x_0$. radient xtract centerlines isplay the curves
solutions.exo8()
## Insert your code here.
In order to speed up geodesic extraction, one can perform the propagation from both the start point $x_0^1$ and end point $x_0^2$.
Boundary points.
x0 = [[143; 249] [174; 9]]
Exercise 9
Perform the dual propagation, and stop it when the front meet. Extract the two half geodesic curves. ual propagation. xtract first the geodesic paths terations
solutions.exo9()
## Insert your code here.