python/todo/fastmarching_9_heuristics.ipynb

{"worksheets": [{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["Heuristically Driven Front Propagation", "======================================", "", "*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 heuristics to speed up Fast Marching methods in 2D.", "", "", "The use of heuristics for the computation of geodesic paths was", "introduced in", "", "", "_Heuristically Driven Front Propagation for Fast Geodesic Extraction_", "Gabriel Peyre and Laurent Cohen,", "International Journal for Computational Vision and Biomechanics, Vol. 1(1), p.55-67, Jan-June 2008."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["from __future__ import division", "import nt_toolbox as nt", "from nt_solutions import fastmarching_9_heuristics as solutions", "%matplotlib inline", "%load_ext autoreload", "%autoreload 2"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Ideal Heuristically Driven Front Propagation", "--------------------------------------------", "The ideal heuristic |H| is the remaining distance to the ending point.", "It is ideal in the sense that it is as difficult to compute this distance", "than to solve for the original problem of extracting the geodesic.", "", "", "One can however study the influence of this heuristic by replacing |H|", "by |weight*H| where |weight<1| is a sub-optimality factor.", "", "", "Load an image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["n = 300", "name = 'road2'", "M = rescale(load_image(name, n))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display it."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(M)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Define start and end points (you can use your own points)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["pstart = [14; 161]", "pend = [293; 148]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute a metric to extact the road."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["W = abs(M-M(pstart(1), pstart(2)))", "W = rescale(W, 1e-2, 1)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display it."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(W)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Perform the full propagation."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[D, S] = perform_fast_marching(1./ W, pstart)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Extract a geodesic curve."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["p = compute_geodesic(D, pend)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the distance and the geodesic curve."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["clf; hold on", "imageplot(convert_distance_color(D, M), 'Distance')", "h = plot(p(2, : ), p(1, : ), '.k'); set(h, 'LineWidth', 2)", "h = plot(pstart(2), pstart(1), '.r'); set(h, 'MarkerSize', 25)", "h = plot(pend(2), pend(1), '.b'); set(h, 'MarkerSize', 25)", "axis ij"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the heuristic."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[H, S] = perform_fast_marching(1./ W, pend)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the ideal heuristic function."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["clf; hold on", "imageplot(convert_distance_color(H, M), 'Distance')", "h = plot(p(2, : ), p(1, : ), '.k'); set(h, 'LineWidth', 2)", "h = plot(pstart(2), pstart(1), '.r'); set(h, 'MarkerSize', 25)", "h = plot(pend(2), pend(1), '.b'); set(h, 'MarkerSize', 25)", "axis ij"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 1__", "", "Display the set of points satisfying |D+H<=T| for several value of the", "threshold |T>=D(pend)|. What do you observe ?"]}, {"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": ["Perform the heuristically driven propagation."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["weight = .9", "options.end_points = pend", "options.heuristic = weight*H", "options.nb_iter_max = Inf", "options.constraint_map = Inf + zeros(n)", "[D, S] = perform_fast_marching(1./ W, pstart, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the region explored by the algorithm."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["I = find(S <0)", "U = cat(3, M, M, M)", "U(I) = 1; U([I + n^2, I + 2*n^2]) = U([I + n^2, I + 2*n^2])*.3", "clf; hold on", "imageplot(U)", "h = plot(p(2, : ), p(1, : ), '.k'); set(h, 'LineWidth', 2)", "h = plot(pstart(2), pstart(1), '.g'); set(h, 'MarkerSize', 25)", "h = plot(pend(2), pend(1), '.b'); set(h, 'MarkerSize', 25)", "axis ij"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 2__", "", "Display the explored region for different values of |weight|."]}, {"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": ["Landmark-based Heuristically Driven Front Propagation", "-----------------------------------------------------", "An heuristic can be derived using a pre-computed set of distance to", "landmark points. The more landmark, the more accurate the heuristic is.", "", "", "Compute randomized landmarks."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["q = 10", "landmarks = floor(rand(2, q)*n) + 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Pre-compute distances to landmarks."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["Dland = zeros(n, n, q)", "for i in 1: q:", "    Dland(: , : , i) = perform_fast_marching(1./ W, landmarks(: , i))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the heuristic."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["Dend = Dland(pend(1), pend(2), : )", "H = max(abs(Dland-repmat(Dend, [n n 1])), [], 3)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the heuristic."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["hold on", "imageplot(H)", "contour(H, 10, 'k', 'LineWidth', 2)", "colormap jet(256)", "h = plot(landmarks(1, : ), landmarks(2, : ), 'y.')", "set(h, 'MarkerSize', 15)", "axis ij"]}, {"cell_type": "markdown", "metadata": {}, "source": ["That should be compared with the optimal ideal heuristic."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[H0, S] = perform_fast_marching(1./ W, pend)", "", "hold on", "imageplot(H0)", "contour(H0, 10, 'k', 'LineWidth', 2)", "colormap jet(256)", "axis ij"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 3__", "", "Display the convergence of the heuristic as the number of landmark", "increases."]}, {"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 heuristically driven propagation with a landmark-based", "heuristic."]}, {"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": ["__Exercise 5__", "", "Find a strategy to find optimal seeding position for the landmarks."]}, {"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": ["Heuristics on 3D Meshes", "-----------------------", "It is possible to use the same heuristics to drive the computation of", "geodesic paths on 3D meshes."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 6__", "", "Perform the landmark-based heuristically driven propagation on a 3D", "mesh."]}, {"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."]}]}], "nbformat": 3, "metadata": {"name": ""}, "nbformat_minor": 0}