tp2.html

流形学习算法库

    <tr align="center"> 
      <td> <img src="images/tp1/brain-front-1.png" width="240"/> <img src="images/tp1/brain-front-2.png" width="240"/> 
        <img src="images/tp1/brain-front-3.png" width="240"/> <img src="images/tp1/brain-front-5.png" width="240"/> 
      </td>
    </tr>
    <tr> 
      <td align="center">Exploration of the distance function using <font face="Courier New, Courier, mono">vol3d</font>.</td>
    </tr>
  </table>
  <br/>
  <li>In order to extract a geodesic, we need to select an ending point and perform 
    a descent of the distance function D from this starting point. The selection 
    is done by choosing a point of low distance value in the slice <font face="Courier New, Courier, mono">D(:,:,end-delta)</font>.</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% extract a slice<br>
      d = D(:,:,n-delta);<br>
      % select the point (x,y) of minimum value of d<br>
      % hint: use functions 'min' and 'ind2sub'<br>
      ...<br>
      [x,y] = ...;<br>
      end_point = [x;y;n-delta];</font><font face="Courier New, Courier, mono"><br>
      ... <br>
      % extract the geodesic by discrete descent<br>
      path = compute_discrete_geodesic(D,end_point);<br>
      % draw the path<br>
      Dend = D(end_point(1),end_point(2),end_point(3));<br>
      D1 = double( D&lt;=Dend );<br>
      clf;<br>
      plot_fast_marching_3d(M,D1,path,start_point,end_point);</font> </p>
  </blockquote>
  <table width="1000" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td> <img src="images/tp1/brain-geodesic-1.png" width="400"/> <img src="images/tp1/brain-geodesic-2.png" width="400"/> 
      </td>
    </tr>
    <tr> 
      <td align="center">Exploration of the distance function using <font face="Courier New, Courier, mono">vol3d</font>.<br>
        The red surface indicates the region of the volume that has been explored<br>
        before hitting the ending point.</td>
    </tr>
  </table></p>
  
</ul>




<h2> Voronoi segmentation and geodesic Delaunay triangulation in 2D. </h2>
<ul>
  <li>With the same code as above, one can use multiple starting points. The function 
    perform_fast_marching_2d returns a segmentation map Q that contains the Voronoi 
    segmentation. </li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">n=300;<br>
      name = 'constant'; % other possibility is 'mountain'<br>
      W = load_potential_map(name, n);<br>
      m = 20; % number of center points<br>
      % compute the starting point at random.<br>
      start_points = floor( rand(2,m)*(n-1) ) +1;<br>
      [D,Z,Q] = perform_fast_marching_2d(W, start_points);<br>
      % display the sampling with the distance function<br>
      clf; hold on;<br>
      imagesc(D'); axis image; axis off;<br>
      plot(start_points(1,:), start_points(2,:), '.');<br>
      hold off;<br>
      colormap gray(256); <br>
      % display the segmentation<br>
      figure; clf; hold on;<br>
      imagesc(Q'); axis image; axis off;<br>
      plot(start_points(1,:), start_points(2,:), '.');<br>
      hold off;<br>
      colormap gray(256); </font></p>
  </blockquote>
  <table width="900" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td> <img src="images/tp1/constant-voronoi-dist.jpg" width="300"/> <img src="images/tp1/mountain-voronoi-dist.jpg" width="300"/> 
      </td>
    </tr>
    <tr> 
      <td align="center">Example of Voronoi cells (distance functions) obtained 
        with <br>
        a constant speed W (left) and the mountain map (right).<br>
        Note how the cell on the left have polygonal boundaries whereas cells on 
        the right<br>
        have curvy boundaries.<br></td>
    </tr>
  </table>
  <br>
  <li>A geodesic Delaunay triangulation is obtained by linking starting points 
    whose Voronoi cells touch. This is the dual of the original Voronoi segmentation.</li>
  <blockquote> 
    <p><br>
      <font face="Courier New, Courier, mono">faces = compute_voronoi_triangulation(Q);<br>
      hold on;<br>
      imagesc(Q'); axis image; axis off;<br>
      plot(start_points(1,:), start_points(2,:), 'b.', 'MarkerSize', 20);<br>
      plot_edges(compute_edges(faces), start_points, 'k');<br>
      hold off;<br>
      axis tight; axis image; axis off;<br>
      colormap jet(256);</font></p>
  </blockquote>
  <table width="900" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td> <img src="images/tp1/constant-voronoi-tr.jpg" width="300"/> <img src="images/tp1/mountain-voronoi-tr.jpg" width="300"/> 
      </td>
    </tr>
    <tr> 
      <td align="center">Examples of triangulations. Notice how the canonical 
        euclidean Delaunay triangulation (left) <br>
        differs from the geodesic one (right) when the metric is not constant.</td>
    </tr>
  </table>
</ul>



<h2> Farthest point sampling. </h2>
<ul>
  <li>We are now back to computations in 2D. The function <font face="Courier New, Courier, mono">farthest_point_sampling</font> 
    iteratively compute the distance to the already computed set of points, and 
    add to the list (initialized as empty) the farthest point. You should read 
    the function so that you fully understand what it is doing. You can also try 
    different speed functions to see the resulting sampling.</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">n=300;<br>
      name = 'mountain';<br>
      W = load_potential_map(name, n);<br>
      % perform sampling<br>
      landmark = [];<br>
      landmark = farthest_point_sampling( W, landmark, nbr_landmarks-size(landmark,2) 
      );<br>
      % display<br>
      hold on;<br>
      imagesc(M');<br>
      plot(landmark(1,:), landmark(2,:), 'b.', 'MarkerSize', 20);<br>
      hold off;<br>
      axis tight; axis image; axis off;<br>
      colormap gray(256);<br/>
	% try with other metric W, like 'constant' <br>
	...</font> 
    <table width="920" border="0" cellspacing="0" cellpadding="0" align="center">
      <tr align="center"> 
        <td> <img src="images/tp1/mountain-sampling-50.jpg" width="300"> <img src="images/tp1/mountain-sampling-100.jpg" width="300"> 
          <img src="images/tp1/mountain-sampling-150.jpg" width="300"><br/> <img src="images/tp1/mountain-sampling-200.jpg" width="300"> 
          <img src="images/tp1/mountain-sampling-250.jpg" width="300"> <img src="images/tp1/mountain-sampling-300.jpg" width="300"> 
        </td>
      </tr>
      <tr> 
        <td align="center">Farthest point sampling with 50, 100, 150, 200, 250 and 
          <br>
          300 points respectively. </td>
      </tr>
    </table>
  </blockquote>
  <li>Now you can compute the corresponding triangulation using the already given 
    code. </li>
  <blockquote> 
    <table width="920" border="0" cellspacing="0" cellpadding="0" align="center">
      <tr align="center"> 
        <td> <img src="images/tp1/mountain-sampling-tr-100.jpg" width="300"> <img src="images/tp1/mountain-sampling-tr-200.jpg" width="300"> 
          <img src="images/tp1/mountain-sampling-tr-300.jpg" width="300"> </td>
      </tr>
      <tr> 
        <td align="center">Farthest point triangulations. </td>
      </tr>
    </table>
  </blockquote>
</ul>
<h2>Heuristically driven front propagation. </h2>
<ul>
  <li>The function perform_fast_marching_2d can be used with a fourth argument 
    that gives an estimation of the distance to the end point. It helps the algorithm 
    to reduce the number of explored pixels. This remaining distance H should 
    be estimated quickly (hence the name &quot;heuristic&quot;). Here we propose 
    to cheat and use directly the true remaining distance using a classical propagation. 
    You have to test this code with various values of <font face="Courier New, Courier, mono">weight</font>.</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">[start_points,end_points] = pick_start_end_point(W);<br>
      % compute the heuristic<br>
      [H,S] = perform_fast_marching_2d(W, end_points);<br>
      % perform the propagation<br>
      options.end_points = end_points;<br>
      weight = 0.5; % should be between 0 and 1.<br>
      [D,S] = perform_fast_marching_2d(W, start_points, options, H*weight);<br>
      % compute the path<br>
      p = extract_path_2d(D,end_points, options);<br>
      % display<br>
      clf;<br>
      plot_fast_marching_2d(W,S,p,start_points,end_points);<br>
      colormap jet(256);<br>
      saveas(gcf, [rep name '-heuristic' num2str(weight) '.jpg'], 'jpg');</font> 
  </blockquote>
  <li>As a final question, try to devise a fast way to estimate the remaining 
    distance function. If you have no idea, you can use the function <font face="Courier New, Courier, mono">perform_fmstar_2d</font> 
    which implement two methods to achieve this.</li>
  <table width="1200" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td><img src="images/tp1/road2-heuristic0.jpg" width="300"/> <img src="images/tp1/road2-heuristic0.5.jpg" width="300"/> 
        <img src="images/tp1/road2-heuristic0.9.jpg" width="300"/> </td>
    </tr>
    <tr> 
      <td align="center">Heuristic front propagation with a weight parameter of 
        0, 0.5 and 0.9 respectively.<br>
        Notice how the explored area shrinks around the true path.</td>
    </tr>
  </table>
  <br/>
  Copyright &copy; 2006 <a href="http://www.cmap.polytechnique.fr/%7Epeyre/">Gabriel 
  Peyr&eacute;</a> 
</ul>
</body>

</html>