📄 tp3.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=iso-8859-1"><link rel=File-List href="index_files/filelist.xml"><title>Lecture 3 - Geodesic Computation on 3D Meshes</title><link href="styles.css" rel="stylesheet" type="text/css"></head><body bgcolor="#FFFFFF" lang=FR><div > <h1>Lecture 3 - Geodesic Computations<br> on 3D Meshes</h1></div><blockquote> <blockquote> <blockquote> <blockquote> <blockquote> <p align="justify"><strong>Abstract : </strong>The goals of this lecture is to manipulate the fast marching algorithm on triangulated meshes. Application to geodesic extraction, Voronoi segmentation, remeshing and bending invariants are presented.</p> </blockquote> </blockquote> </blockquote> </blockquote></blockquote><h2> Setting up Matlab. </h2><ul> <li>First download the Matlab toolbox <a href="matlab/toolbox_fast_marching.zip"><font face="Courier New, Courier, mono">toolbox_fast_marching.zip</font></a> and <a href="matlab/toolbox_graph.zip"><font face="Courier New, Courier, mono">toolbox_graph.zip</font></a>. Unzip it into your working directory. You should have directories <font face="Courier New, Courier, mono">toolbox_fast_marching/</font> and <font face="Courier New, Courier, mono">toolbox_graph</font>/ in your path. </li> <li>The first thing to do is to install these toolboxes in your path.</li> <blockquote> <p><font face="Courier New, Courier, mono">path(path, 'toolbox_fast_marching/');<br> path(path, 'toolbox_fast_marching/toolbox/');<br> </font><font face="Courier New, Courier, mono">path(path, 'toolbox_graph/');<br> path(path, 'toolbox_graph/off/');</font></p> </blockquote> <li>Recompile the mex files for your machine (this can produce some warning). If it does not work, either use the already compiled mex file (they should be available in <font face="Courier New, Courier, mono">toolbox_fast_marching/</font> for MacOs and Unix) or try to set up matlab with a C compiler (e.g. gcc) using '<font face="Courier New, Courier, mono">mex -setup</font>'. </li> <blockquote> <p><font face="Courier New, Courier, mono">cd toolbox_fast_marching<br> compile_mex;<br> cd ..</font></p> </blockquote></ul><h2> Distance Computation on Triangulated Surface. </h2><ul> <li>Using the fast marching on a triangulated surface, one can compute the distance from a set of input points. This function also returns the segmentation of the surface into geodesic Voronoi cells.</li> <blockquote> <p><font face="Courier New, Courier, mono">name = 'elephant'; % other choices includes 'skull' or 'bunny'<br> [vertex,faces] = read_mesh([name '.off']);<br> nverts = max(size(vertex)); % number of vertices<br> nstart = 8; % number of starting points<br> start_points = floor(rand(nstart,1)*nverts)+1;<br> options.end_points = end_points(:);<br> % perform the front propagation<br> [D,S,Q] = perform_fast_marching_mesh(vertex, faces, start_points, options);<br> % display the distance function<br> col = D; col(col==Inf) = 0; % the color of the vertices<br> clf; hold on;<br> options.face_vertex_color = col;<br> plot_mesh(vertex, faces, options);<br> h = plot3(vertex(1,start_points),vertex(2,start_points), vertex(3,start_points), 'r.');<br> set(h, 'MarkerSize', 25);<br> hold off;<br> colormap jet(256);<br> axis tight; shading interp;<br> % you can now display the segmentation function Q<br> ... </font></p> </blockquote> <table width="1100" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp2/skull-dist-3.jpg" width="250"/> <img src="images/tp2/skull-dist-6.jpg" width="250"/> <img src="images/tp2/skull-dist-16.jpg" width="250"/> <img src="images/tp2/skull-dist-50.jpg" width="250"/> <br/> <img src="images/tp2/skull-segm-3.jpg" width="250"/> <img src="images/tp2/skull-segm-6.jpg" width="250"/> <img src="images/tp2/skull-segm-16.jpg" width="250"/> <img src="images/tp2/skull-segm-50.jpg" width="250"/> </td> </tr> <tr> <td align="center">Example of distance function from a set of random <br> starting points (upper row), and the corresponding<br> Voronoi segmentation (bottom row).</td> </tr> </table> <br> <li>You can even stop the propagation after a fixed number of steps and see the resulting partially propagated front.</li> <blockquote> <p><br> <font face="Courier New, Courier, mono">options.nb_iter_max = ...; % trying with a varying number of iterations<br> [D,S,Q] = perform_fast_marching_mesh(vertex, faces, start_points, options);<br> % display the distance<br> ... </font></p> </blockquote> <table width="950" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp2/elephant-prop-1.jpg" width="300"/> <img src="images/tp2/elephant-prop-2.jpg" width="300"/> <img src="images/tp2/elephant-prop-3.jpg" width="300"/><br/> <img src="images/tp2/elephant-prop-4.jpg" width="300"/> <img src="images/tp2/elephant-prop-5.jpg" width="300"/> <img src="images/tp2/elephant-prop-6.jpg" width="300"/> </td> </tr> <tr> <td align="center">Example of front propagation.</td> </tr> </table></ul><h2> Geodesic Remeshing. </h2><ul> <li>A regular sampling of the surface can be performed by seeding in a greedy farthest fashion samples. These points can be linked according to the Voronoi cells adjacency which gives a powerful but yet simple remeshing scheme.</li> <blockquote> <p><font face="Courier New, Courier, mono">nbr_landmarks = ...; % number of points, eg. 400<br> W = ones(nverts,1); % the speed function, for now constant speed to perform uniform remeshing<br> % perform the sampling of the surface<br> landmark = farthest_point_sampling_mesh( vertex,faces, [], nbr_landmarks, options );<br> % compute the associated triangulation<br> [D,Z,Q] = perform_fast_marching_mesh(vertex, faces, landmark);<br> [vertex_voronoi,faces_voronoi] = compute_voronoi_triangulation_mesh(Q,vertex,faces);<br> % display the distance function (same as before)<br> ... <br> % display the remeshed triangulation (same but with vertex_voronoi and faces_voronoi)<br> ...</font></p> </blockquote> <table width="1100" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp2/hand-50kv-cst-sampl-300.jpg" width="250"> <img src="images/tp2/hand-50kv-cst-sampl-500.jpg" width="250"> <img src="images/tp2/hand-50kv-cst-sampl-800.jpg" width="250"> <img src="images/tp2/hand-50kv-cst-sampl-1500.jpg" width="250"><br/> <img src="images/tp2/hand-50kv-cst-remesh-300.jpg" width="250"> <img src="images/tp2/hand-50kv-cst-remesh-500.jpg" width="250"> <img src="images/tp2/hand-50kv-cst-remesh-800.jpg" width="250"> <img src="images/tp2/hand-50kv-cst-remesh-1500.jpg" width="250"> </td> </tr> <tr> <td align="center">Farthest point sampling with an increasing number of points <br> (upper row) and corresponding remeshing (bottom row).<br></td> </tr> </table> <li>One can use a non-constant speed function in order to have an adapted remeshing. The sampling will be denser in area where the speed function is low.</li> <blockquote> <p><font face="Courier New, Courier, mono">% first kind of speed: low on the left, high on the right <br> v = rescale(vertex(1,:));<br> options.W = rescale(v>0.5, 1, 3); options.W = options.W(:);<br> % do the remeshing<br> ...<br> % second kind of speed: continuously increasing<br> v = rescale(-vertex(1,:),1,8);<br> options.W = v(:);<br> % do the remeshing<br> ...</font></p> </blockquote> <table width="1100" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp2/bunny-cst-sampl-300.jpg" width="250"> <img src="images/tp2/bunny-cst-sampl-500.jpg" width="250"> <img src="images/tp2/bunny-cst-sampl-800.jpg" width="250"> <img src="images/tp2/bunny-cst-sampl-1400.jpg" width="250"> <br> <img src="images/tp2/bunny-cst-remesh-300.jpg" width="250"> <img src="images/tp2/bunny-cst-remesh-500.jpg" width="250"> <img src="images/tp2/bunny-cst-remesh-800.jpg" width="250"> <img src="images/tp2/bunny-cst-remesh-1400.jpg" width="250"> <br> <img src="images/tp2/bunny-split-sampl-300.jpg" width="250"> <img src="images/tp2/bunny-split-sampl-500.jpg" width="250"> <img src="images/tp2/bunny-split-sampl-800.jpg" width="250"> <img src="images/tp2/bunny-split-sampl-1400.jpg" width="250"> <br> <img src="images/tp2/bunny-split-remesh-300.jpg" width="250"> <img src="images/tp2/bunny-split-remesh-500.jpg" width="250"> <img src="images/tp2/bunny-split-remesh-800.jpg" width="250"> <img src="images/tp2/bunny-split-remesh-1400.jpg" width="250"> <br> <img src="images/tp2/bunny-grad-sampl-300.jpg" width="250"> <img src="images/tp2/bunny-grad-sampl-500.jpg" width="250"> <img src="images/tp2/bunny-grad-sampl-800.jpg" width="250"> <img src="images/tp2/bunny-grad-sampl-1400.jpg" width="250"> <br> <img src="images/tp2/bunny-grad-remesh-300.jpg" width="250"> <img src="images/tp2/bunny-grad-remesh-500.jpg" width="250"> <img src="images/tp2/bunny-grad-remesh-800.jpg" width="250"> <img src="images/tp2/bunny-grad-remesh-1400.jpg" width="250"> <br> </td> </tr> <tr> <td align="center">Rows 1&2: uniform sampling and remeshing.<br> Rows 3&4: adapted (split left/right) remeshing.<br> Rows 5&6: adapted (continuously increasing) remeshing.</td> </tr> </table></ul><h2> Bending Invariants of a Surface.</h2><ul> <li>One can use the Isomap procedure in order to modify the surface to get bending invariant signature, useful to perform articulation-invariant recognition of 3D surfaces. One first need to compute the pairwise geodesic distances between points on the surfaces. One then look for new 3D positions of the vertices so that the new Euclidean distances matches closely the geodesic distances. In order to speed up computation, the geodesic distances are computed only on a reduced set of landmarks points. The 3D new locations are then interpolated.</li> <blockquote> <p><br> <font face="Courier New, Courier, mono">nlandmarks = 300; % number of landmarks (low to speed up)<br> landmarks = floor(rand(nlandmarks,1)*nverts)+1; % samples landmarks at random<br> % compute the distance between landmarks and the rest of the vertices<br> Dland = zeros(nverts,nlandmarks);<br> for i=1:nlandmarks<br> fprintf('.');<br> [d,S,Q] = perform_fast_marching_mesh(vertex, faces, landmarks(i)); <br> Dland(:,i) = d(:);<br> end<br> fprintf('\n');<br> % perform isomap on the reduced set of points<br> D1 = Dland(landmarks,:); % reduced pairwise distances<br> D1 = (D1+D1')/2; % force symmetry<br> J = eye(nlandmarks) - ones(nlandmarks)/nlandmarks; % centering matrix<br> K = -1/2 * J*D1*J; % inner product matrix<br> % compute the rank-3 approximation of the inner product to compute embedding<br> opt.disp = 0; <br> [xy, val] = eigs(K, 3, 'LR', opt); <br> xy = xy .* repmat(1./sqrt(diag(val))', [nlandmarks 1]);% interpolation on the full set of points<br> % extend the embeding using geodesic interpolation<br> vertex1 = zeros(nverts,3);<br> deltan = mean(Dland,1);<br> for x=1:nverts<br> deltax = Dland(x,:);<br> vertex1(x,:) = 1/2 * ( xy' * ( deltan-deltax )' )';<br> end<br> % display both the original mesh and the embedding</font> <table width="800" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp2/beetle-bending-original.jpg" width="300"> <img src="images/tp2/beetle-bending-transf.jpg" width="400"> </td> </tr> <tr> <td align="center">Original mesh (left) and bending invariant (right).</td> </tr> </table> </blockquote> <br/> Copyright © 2006 <a href="http://www.cmap.polytechnique.fr/%7Epeyre/">Gabriel Peyré</a> </li></ul></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -