{"worksheets": [{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["Shape Retrieval with Geodesic Descriptors", "=========================================", "", "*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 numerical tour explores the use of geodesic distances within shapes", "to perform shape retrieval.", "", "", "This tour is mostly inspired from the following work:", "", "", "_Matching 2D and 3D Articulated Shapes using Eccentricity_,", "A. Ion, N. M. Artner, G. Peyre, W. G. Kropatsch and L. Cohen,", "Preprint Hal-00365019, January 2009."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["from __future__ import division", "import nt_toolbox as nt", "from nt_solutions import shapes_5_geodesic_descriptors as solutions", "%matplotlib inline", "%load_ext autoreload", "%autoreload 2"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Geodesic Distances Within a Binary Shape", "----------------------------------------", "By restricting shortest path to lie within a shape, one create a geodesic", "metric that is different from the Euclidean one if the shape is not", "convex.", "", "", "A binary shape is represented as a binary image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["n = 200", "name = 'centaur1'", "M = load_image(name, n)", "M = perform_blurring(M, 5)", "M = double(rescale(M) >.5)", "if M(1) = =1 ", "    M = 1-M"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the shape."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(-M)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute its boundary"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["bound = compute_shape_boundary(M)", "nbound = size(bound, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Parameters for the Fast Marching: constant speed |W|, but retricted using |L| to the", "inside of the shape."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["W = ones(n)", "L = zeros(n)-Inf; L(M = =1) = + Inf"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Initial point for the geodesic computation."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["start_points = [95; 20]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the geodesic distance without constraint using Fast Marching.", "It is simply the Euclidean distance."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.constraint_map = []", "D0 = perform_fast_marching(W, start_points, options)", "D0(M = =0) = Inf"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display Euclidean distance."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.display_levelsets = 1", "options.pstart = start_points", "options.nbr_levelsets = 30", "display_shape_function(D0, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute the geodesic distance with constraints using Fast Marching."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.constraint_map = L", "D = perform_fast_marching(W, start_points, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display geodesic distance."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["options.nbr_levelsets = 60", "display_shape_function(D, options)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 1__", "", "Using |options.nb_iter_max| display the progression of the Fast", "Marching."]}, {"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": ["Compute a geodesic curve."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["end_points = [27; 112]", "p = compute_geodesic(D, end_points)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the path."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["ms = 30; lw = 3", "clf; hold on", "imageplot(1-M)", "h = plot(end_points(2), end_points(1), '.b'); set(h, 'MarkerSize', ms)", "h = plot(start_points(2), start_points(1), '.r'); set(h, 'MarkerSize', ms)", "h = plot(p(2, : ), p(1, : ), 'g'); set(h, 'LineWidth', lw)", "axis ij"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 2__", "", "Compute curves joining the start point to several points along the", "boundary."]}, {"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": ["Local Geodesic Descriptors", "--------------------------", "In order to build shape signatures, we compute geodesic distance to all", "the points on the boundary. We then retrieve some caracteristics from", "these geodesic distance map.", "", "", "Select a uniform set of points on the boundary."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["nb_samples = 600", "sel = round(linspace(1, nbound + 1, nb_samples + 1)); sel(end) = []", "samples = bound(: , sel)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 3__", "", "Build a collection |E| of distance maps, so that |E(:,:,i)| is the", "geodesic distance to |samples(:,i)|."]}, {"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": ["normalize distances."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["E = E/ mean(E(: ))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display some locations"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["points = [[80; 20] [95; 112] [156; 42]]", "col = {'r', 'g', 'b', 'k'}", "clf; hold on", "imageplot(-M)", "for i in 1: 3:", "    h = plot(points(2, i), points(1, i), [col{i} '.'])", "    set(h, 'MarkerSize', 40)", "", "axis('ij')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display three different features at some locations."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["col = {'r', 'g', 'b', 'k'}", "for i in 1: 3:", "    subplot(3, 1, i)", "    d = E(points(1, i), points(2, i), : )", "    u = hist(d(: ), 15); axis tight", "    h = bar(u, col{i}); axis('tight')", "    set(gca, 'XTickLabel', [])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Global Geodesic Descriptors", "---------------------------", "One can retain a single statistic from the local descriptors, such as the", "min, max, mean or median values. The histogram of these values are the", "global descriptors.", "", "", "Compute several statistics."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["clear A", "A{1} = max(E, [], 3)", "A{2} = min(E, [], 3)", "A{3} = mean(E, 3)", "A{4} = median(E, 3)", "titles = {'Max', 'Min', 'Mean', 'Median'}"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display as images."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["nbr = [20 5 30 30]", "options.pstart = []", "", "for i in 1: 4:", "    subplot(2, 2, i)", "    options.nbr_levelsets = nbr(i)", "    display_shape_function(A{i}, options)", "    title(titles{i})", "", "colormap jet(256)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display histograms of the statistics."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["for i in 1: 4:", "    u = A{i}(M = =1); u = u(u >0)", "    subplot(4, 1, i)", "    hist(u, 40); axis('tight')", "    title(titles{i})"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Shape Retrieval using Geodesic Historams.", "-----------------------------------------", "One can use the histograms of Eccentricity for shape retrieval."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 4__", "", "Load a library of shapes. Compute the different histograms for these", "shapes."]}, {"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__", "", "Perform the retrieval by comparing the histogram. Test diffetent metrics", "for the retrieval."]}, {"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."]}]}], "nbformat": 3, "metadata": {"name": ""}, "nbformat_minor": 0}