tp4.html

流形学习算法库

        t=200.</td>
    </tr>
  </table>
  <li>Another way to smooth a mesh is to perform the following quadratic regularization 
    for each componnent f=vertex(i,:)<br>
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;F = argmin_g |f-g|^2 
    + t * |G*f|^2<br>
    The solution of this optimization is given in closed form using the Laplacian 
    L=G'*G as the solution of the following linear system:<br>
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Id+t*L)*F = f<br>
    Solve this problem for various t on a 3D mesh. You can use the operator \ 
    to solve a system. How does this method compares with the heat diffusion ?<br>
  </li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% solve the equation<br>
      vertex1 = ...;<br>
      % display<br>
      ...</font></p>
  </blockquote>
</ul>

<h2> Combinatorial Laplacian: Spectral Decomposition and Compression. </h2>
<ul>
  <li>The combinatorial laplacian is a linear operator (thus a NxN matrix where 
    N is the number of vertices). It depends only on the connectivity of the mesh, 
    thus on <font face="Courier New, Courier, mono">face</font> only. The eigenvector 
    of this matrix (which is symmetric, thus can be decomposed by SVD) forms an 
    orthogonal basis of the vector space of signal of NxN values (one real value 
    per vertex). Those functions are the extension of the Fourier oscillating functions 
    to surfaces. </li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% combinatorial laplacian computation 
      <br>
      options.symmetrize = 1;<br>
      options.normalize = 0;<br>
      L0 = compute_mesh_laplacian(vertex,face,'combinatorial',options);<br>
      %% Performing eigendecomposition<br>
      [U,S,V] = svd(L0);<br>
      % extract one of the eigenvectors<br>
      c = U(:,end-10); % you can try with other vector with higher frequencies<br>
      % assign a color to each vertex<br>
      options.face_vertex_color = rescale(c, 0,255);<br>
      % display<br>
      clf;<br>
      plot_mesh(vertex,face, options);<br>
      </font><font face="Courier New, Courier, mono">shading interp; lighting 
      none; </font></p>
  </blockquote>
  <table width="1100" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td> <img src="images/tp3/L1-eigv-1.jpg" height="200"/> <img src="images/tp3/L1-eigv-3.jpg" height="200"/> 
        <img src="images/tp3/L1-eigv-5.jpg" height="200"/> <img src="images/tp3/L1-eigv-7.jpg" height="200"/><br/> 
        <img src="images/tp3/sphere-eigv-1.jpg" height="200"/> <img src="images/tp3/sphere-eigv-3.jpg" height="200"/> 
        <img src="images/tp3/sphere-eigv-5.jpg" height="200"/> <img src="images/tp3/sphere-eigv-7.jpg" height="200"/><br/> 
        <img src="images/tp3/mushroom-eigv-1.jpg" height="180"/> <img src="images/tp3/mushroom-eigv-3.jpg" height="180"/> 
        <img src="images/tp3/mushroom-eigv-5.jpg" height="180"/> <img src="images/tp3/mushroom-eigv-7.jpg" height="180"/> 
      </td>
    </tr>
    <tr> 
      <td align="center">Eigenvectors of the combinatorial laplacian with <br>
        increasing frequencies from left to right.<br></td>
    </tr>
  </table>
  <br>
  <li>Like the Fourier basis, the laplacian eigenvector basis can be used to perform 
    an orthogonal decomposition of a function. In order to perform mesh compression, 
    we decompose each coordinate X/Y/Z of the mesh into this basis. Once this 
    decomposition has been performed, a compression is achieved by keeping only 
    the biggest coefficients (in magnitude).</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% Warning : vertex should be of 
      size 3 x nvert<br>
      keep = 5; % number of percents of coefficients kept<br>
      vertex2 = (U'*vertex')'; % projection of the vector in the laplacian basis<br>
      % set threshold to remove coefficients<br>
      vnorm = sum(vertex2.^2, 1);<br>
      vnorms = sort(vnorm); vnorms = vnorms(end:-1:1);<br>
      nvert = size(vertex,2);<br>
      thresh = vnorms( round(keep/100*nvert) );<br>
      % remove small coefs by thresholding<br>
      vertex2 = vertex2 .* repmat( vnorm&gt;=thresh, [3 1] ); <br>
      % reconstruction<br>
      vertex2 = (U*vertex2')';<br>
      % display<br>
      clf;<br>
      plot_mesh(vertex2,face);<br>
      shading interp; camlight;<br>
      axis tight;</font></p>
  </blockquote>
  <table width="1000" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td> <img src="images/tp3/venus-compress-1.jpg" height="300"/> <img src="images/tp3/venus-compress-3.jpg" height="300"/> 
        <img src="images/tp3/venus-compress-5.jpg" height="300"/> <img src="images/tp3/venus-compress-7.jpg" height="300"/> 
        <br/> <img src="images/tp3/mushroom-compress-1.jpg" height="160"/> <img src="images/tp3/mushroom-compress-3.jpg" height="160"/> 
        <img src="images/tp3/mushroom-compress-5.jpg" height="160"/> <img src="images/tp3/mushroom-compress-7.jpg" height="160"/> 
      </td>
    </tr>
    <tr> 
      <td align="center">Spectral mesh compression performed<br>
        by decomposition on the eigenvectors of the laplacian.</td>
    </tr>
  </table>
</ul>


<h2> Mesh Flattening and Parameterization. </h2>
<ul>
  <li>The eigenvector of the combinatorial laplacian can also be used to perform 
    mesh flattening. Flattening means finding a 2D location for each vertex of 
    the mesh. These two coordinates are composed by the eigenvectors n&deg;2 and 
    n&deg;3 of the laplacian.</li>
  <blockquote> 
    <p> <font face="Courier New, Courier, mono">% load a mesh<br>
      name = 'nefertiti';<br>
      [vertex,face] = read_mesh([name '.off']);<br>
      A = triangulation2adjacency(face);<br>
      % perform the embedding using the combinatorial eigendecomposition<br>
      xy = perform_spectral_embedding(2,A); <br>
      % display the flattened mesh<br>
      gplot(A,xy,'k.-');<br>
      axis tight; axis square; axis off; </font></p>
  </blockquote>
  <li>This combinatorial flattening does not use geometric information since it 
    only use the connectivity of the mesh. So any mesh with the same connectivity 
    will have the same 2D embedding. In order to improve the quality of the embedding, 
    one can use a conformal laplacian, who approximate the Laplace Beltrami operator 
    of the continuous underlying surface.</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% this time, we use the information 
      from vertex to compute flattening<br>
      xy = perform_spectral_embedding(2,A,vertex,face);<br>
      % display<br>
      gplot(A,xy,'k.-');<br>
      axis tight; axis square; axis off; </font></p>
  </blockquote>
  <li>Another way to compute the flattening is to use the Isomap algorithm. This 
    algorithm is not based on local differential operator such as laplacian. Instead, 
    the geodesic distance between points on the mesh graph is first computed (see 
    the <a href="tp4.html">course 4</a> for example of geodesic computations on 
    graphs). Then the 2D layout of point is computed in order to match the geodesic 
    distance with the distance in the plane.</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% the embedding is now computed 
      with isomap<br>
      xy = perform_spectral_embedding(2,A,vertex);<br>
      % display<br>
      gplot(A,xy,'k.-');<br>
      axis tight; axis square; axis off; </font></p>
  </blockquote>
  <table width="1000" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td>
	  	<img src="images/tp3/nefertiti-original.jpg" height="200"> 
	  	<img src="images/tp3/nefertiti-flat-combi.jpg" height="200"> 
	  	<img src="images/tp3/nefertiti-flat-confo.jpg" height="200"> 
        <img src="images/tp3/nefertiti-flat-isomap.jpg" height="200"> </td>
    </tr>
    <tr> 
      <td align="center"><p>Comparison of the flattening obtained with the combinatorial 
          laplacian,<br>
          the conformal laplacian and isomap.<br>
        </p></td>
    </tr>
  </table>
  <br/>
  <li>Mesh parameterization is similar to flattening, except that we fix the boundary 
    of the mesh to be flattened onto some given convex 2D curve. The flattening 
    can then be proved to be 1:1 (no triangle flip) and long as the curve is convex 
    and Id+laplacian is positive. While flattening involve spectral computation 
    (eigenvectors extraction), which is very slow, mesh parameterization involve 
    the solution of a sparse linear system, which is quite fast (even if the Laplacian 
    matrix is ill-conditioned).</li>
  <blockquote> 
    <p><font face="Courier New, Courier, mono">% pre-compute 1-ring, i.e. the neighbors 
      of each triangle.<br>
      ring = compute_1_ring(face);<br>
      lap_type = 'combinatorial'; % the other choice is 'conformal'<br>
      boundary_type = 'circle'; % the other choices are 'square' and 'triangle'<br>
      % compute the parameterization by solving a linear system<br>
      xy = compute_parametrization(vertex,face,lap_type,boundary_type,ring);<br>
      % display<br>
      clf;<br>
      gplot(A,xy,'k.-');<br>
      axis tight; axis square; axis off;</font></p>
  </blockquote>
  <table width="1000" border="0" cellspacing="0" cellpadding="0" align="center">
    <tr align="center"> 
      <td> <img src="images/tp3/nefertiti-param-ccomb.jpg" width="250"> <img src="images/tp3/nefertiti-param-scomb.jpg" width="250"> 
        <img src="images/tp3/nefertiti-param-tcomb.jpg" width="250"> <br/> <img src="images/tp3/nefertiti-param-cconf.jpg" width="250"> 
        <img src="images/tp3/nefertiti-param-sconf.jpg" width="250"> <img src="images/tp3/nefertiti-param-tconf.jpg" width="250"> 
      </td>
    </tr>
    <tr> 
      <td align="center">The first row shows parameterization using the combinatorial 
        laplacian<br>
        (with various boundary conditions). This assumes that the edge lengths 
        is 1.<br>
        To take into account the geometry of the mesh, the second<br>
        row uses the conformal laplacian.</td>
    </tr>
  </table>
  <br/>  
  Copyright &copy; 2006 <a href="http://www.cmap.polytechnique.fr/%7Epeyre/">Gabriel 
  Peyr&eacute;</a> 
</ul>




</body>

</html>