{"worksheets": [{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["Fast Marching in 2D", "===================", "", "*Important:* Please read the [installation page](http://gpeyre.github.io/numerical-tours/installation_python/) 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}$"]}, {"cell_type": "markdown", "metadata": {}, "source": ["This tour explores the use of Fast Marching methods in 2-D."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["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"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Shortest Path for Isotropic Metrics", "-----------------------------------", "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$.", "", "Pixel values-based Geodesic Metric", "----------------------------------", "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$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["clear options", "n = 300", "name = 'road2'", "f = rescale(load_image(name, n))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(f)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Define start and end points $x_0$ and $x_1$ (note that you can use your own points)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["x0 = [14; 161]", "x1 = [293; 148]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["epsilon = 1e-2", "W = epsilon + abs(f-f(x0(1), x0(2)))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the metric $W$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(W)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Set options for the propagation: infinite number of iterations, and stop", "when the front hits the end point."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.nb_iter_max = Inf", "options.end_points = x1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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)$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[D, S] = perform_fast_marching(1./ W, x0, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["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)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__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$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo1()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Geodesic Curve Extraction", "-------------------------", "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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.nb_iter_max = Inf", "options.end_points = []", "[D, S] = perform_fast_marching(1./ W, x0, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display $D$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(D)", "colormap jet(256)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the gradient $G_0(x) = \\nabla D(x) \\in \\RR^2$ of the distance map. Use centered differences."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.order = 2", "G0 = grad(D, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["G = G0 ./ repmat(sqrt(sum(G0.^2, 3)), [1 1 2])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display $G$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(G)", "colormap jet(256)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["tau = .8"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Initialize the path with the ending point."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["gamma = x1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Define a shortcut to interpolate $G$ at a 2-D points.", "_Warning:_ the |interp2| switches the role of the axis ..."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["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))]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the gradient at the last point in the path, using interpolation."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["g = Geval(G, gamma(: , end))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Perform the descent and add the new point to the path."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["gamma(: , end + 1) = gamma(: , end) - tau*g"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__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$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo2()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the curve on the image background."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["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"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the curve on the distance background."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["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"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 3__", "", "Study the influence of the $\\epsilon$ parameter."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo3()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 4__", "", "Perform the shortest path", "extraction for various images such as 'cavern' or 'mountain'.", "oad", "radient", "isplay"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo4()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Edge-based Geodesic Metric", "--------------------------", "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$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["n = 256", "name = 'cortex'", "f = rescale(sum(load_image(name, n), 3))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display it."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(f)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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)$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["G = grad(f, options)", "G = sqrt(sum(G.^2, 3))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Smooth it by $G_\\si$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["sigma = 3", "Gh = perform_blurring(G, sigma)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the smoothed gradient $ G \\star G_\\si $."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(Gh)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the metric."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["epsilon = 0.01", "W = 1./ (epsilon + Gh)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display it."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(W)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Set two starting point $ \\Ss = \\{x_0^1,x_0^2\\} $ (you can use other points)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["x0 = [[136; 53] [123; 205]]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the Fast Marching from these two base points."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.nb_iter_max = Inf", "options.end_points = []", "[D, S, Q] = perform_fast_marching(1./ W, x0, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the geodesic distance (with color normalization)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["clf; hold on", "imageplot(perform_hist_eq(D, 'linear'))", "h = plot(x0(2, : ), x0(1, : ), '.r'); set(h, 'MarkerSize', 25)", "colormap jet(256)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["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)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__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);"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo5()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__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"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo6()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Vessel Segmentation and Centerline Extraction", "---------------------------------------------", "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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["n = 256", "name = 'vessels'", "f = rescale(load_image(name, n))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display it."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(f)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["sigma = 20", "f1 = perform_blurring(f, sigma) - f"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display this normalized image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(f1)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["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). $$"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["c = max(f1(: ))", "epsilon = 1e-2", "W = epsilon + abs(f1-c)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the metric."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(W)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Select a central point $x_0$ for the network."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["x0 = [142; 226]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 7__", "", "Perform partial propagations from $x_0$."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo7()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 8__", "", "Extract geodesics joining several points $x_1$ to the central point", "$x_0$.", "radient", "xtract centerlines", "isplay the curves"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo8()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Dual Propagation", "----------------", "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."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["x0 = [[143; 249] [174; 9]]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__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"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo9()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}]}], "nbformat": 3, "metadata": {"name": ""}, "nbformat_minor": 0}