# 2008 Winter Project Week Geometry and Topology processing of Meshes

- Proposal for AHM 2008 Breakout session (Tue, Jan 8th 1-2pm): Geometry and Topology processing of Meshes by Alex G of Caltech:
- 30 mn Prof. GU : Discrete Algorithms for Surface mesh processing
- 05 mn Alex G : curent and future ITK Implementations (QuadEdge, Param., ..)
- 05 mn Luca Antiga : curent and potential uses in his research
- 20 mn : interactions

Professor David Xianfeng GU and/or students (http://www.cs.sunysb.edu/~gu/)

Prof. GU will be in china mid-december. Depeneding on the rapidity of the US embassy in china to give him a visa to go back, I will be able to attend the meeting or not. In the unfortunate case he wouldn't be able to attend, one or two of his postdoc students would be there in replacement.

Ricci flow is a powerful geometric analytic tool, which has been applied to prove Poincare conjecture. Ricci flow is a parabolic system of partial differential equations which acts like the heat equation to spread the curvature of a Riemannian metric evenly over the surface to produce a metric of constant curvature. Computational Ricci flow has been invented and applied for computing hyperbolic structures and conformal surface parameterizations, it is expected to play important roles in both mathematics and engineering fields.

Algorithms for computing conformal structure can be summaried as

- For genus zero surface in the first column, the mapping can be commputed using spherical harmonic maps, in paper "Genus Zero Surface Conformal Mapping and Its Application to Brain Surface Mapping". Spherical geometry can be defined on the surface.
- For genus one surface in the second column, the mapping can be commputed using holomorphic one forms, in paper "Global Conformal Surface Parameterization". Another algorithm is to use Euclidean Ricci flow, in paper "Conformal Surface Parameterization Using Euclidean Ricci Flow". Euclidean geometry can be defined on the surface.
- For higher genus surfaces in the third column, the mapping can be commputed using hyperbolic Ricci flow, in paper "Computing Surface Hyperbolic Structure and Real Projective Structure". Hyperbolic geometry can be defined on the surface.

Applications of conformal geometry in engineering fields are innumerous, the followings are the most directly related ones, Graphics: surface global conformal parameterization. Medical Imaging: conformal brain mapping and colon flattening. Geometric Modeling: manifold splines. Vision: Surface matching and recognition.

Alex. Hanfei Gouaillard (http://www.itk.org/Wiki/User:Agouaillard) and Arnaud Gelas (www.creatis.insa-lyon.fr/~gelas)

For the past 5 years, both A.G. have been working on applying gometry and topology processing to medical / biological image processing problems, some of them in collaboration for some with Prof. David GU.

They identified very early that surface processing could only be done rigorously using at least an Half-Edge Structure, and even better in the case of image procesing, a Quad-Edge datastructure. They also concluded from their experiment that, even though C-GAL was the best tool out there to do geometry and topology processing, its licence, its complexity, the lack of support of several key platform, and the lack of support of Images was ruling it out for Image procesing orriented applications. They decided to go for ITK, and to re-implement whatever would be necessary. It was a long term project, done on spare time, which started around 2002.

Nowadays, the datasrtucture is available under the name itkQuadEdgeMesh and is fairly stable and compliant with existing itkMesh API. The original submission can be read here: http://hdl.handle.net/1926/306. The code is available in ITK since 3.2, if compiled with the USE_REVIEW option. Most of the surface processing algorithms can be more easily implemented on top of euler operators. Their second work has been to implement those on top of itkQuadEdgeMesh to ease further implementations. The code is available in ITK since 3.4, still with the compilation condition. There is still a lot of algorithms waiting to be transfered in ITK, of which the recent submission of the parameterization code is but a small example.

During this presentation, they will list the features they already have a prototype for and try to give a release timeline. ne can expect most of the processing features of VTK to be transfered very soon in ITK, and then some more advanced features to come in. They hope to provide ITK witha complete geometrical and topological toolkit. They dream, in a distant future to be able to implement an exact kernel in ITK to be able to compute in a robust manner voronoi tesselations and their duals, delauney triangulations.

- A. GOUAILLARD, C. Odet, X. GU, “Computing Shortest Cycles on Discrete Surfaces for Acurate Topological Modifications of Medical Image Isosurfaces”, In Proceedings of IEEE EMBC’05, Shanghai, September 11th-14th 2005.
- A. GOUAILLARD, T. Kanai, C. Odet, X. GU, “Optimal Localization of Topological Artefacts on 3D Meshes”, The 11th Int. Conf. on Geometry and Graphics, 1-5 Aug., 2004, Guangzhou, China.

- A. GELAS, Olivier Bernard, Denis Friboulet, Rémy Prost. "Compactly Supported Radial Basis Functions Collocation Method for Image Segmentation". IEEE Transaction on Image Processing, vol. 16(7), pp.1873--1887 2007.
- A. GELAS, Yutaka Ohtake, Takashi Kanai, Rémy Prost. "Surface Reconstruction Using Radial Basis Functions With Support Adapted to the Medial Axis." Elsevier Computer & Graphics, 2006 (submitted).

- A.GELAS, Joel Schaerer, Olivier Bernard, Denis Friboulet, Patrick Clarysse, Isabelle Magnin, Rémy Prost. "Radial basis functions collocation methods for model based level-set segmentation". IEEE ICIP 2007 Proceedings, vol. 2, pp.237--240, San Antonio, Texa, USA, September 2007.
- A. GELAS, Yutaka Ohtake, Takashi Kanai, Rémy Prost. "Approximation of unorganized point set with composite implicit surface". IEEE ICIP 2006 Proceedings, pp.1217--1220, Atlanta, Georgia, USA, October 2006.
- A. GELAS, Rémy Prost. "Multi-resolution reconstruction of irregularly sampled signals with compactly supported radial basis functions". IEEE ICASSP 2006's Proceedings, vol. 3, pp.388--391, Toulouse, France, May 2006.
- A. GOUAILLARD, A. GELAS, S. Valette, E. Boix and R. Prost, “Curvature-based Adaptive Remeshing for Wavelet-Based Multiresolution 3D Meshes”. In Proc. of International Conference on Image Processing ICIP’05, Genova, September 11th-14th 2005. To appear.
- A. GOUAILLARD, A. GELAS, S. Valette, E. Boix, R. Prost, “Remeshing Algorithm for Multiresolution Prior Model in Segmentation. In Proc. of International Conference on Image Processing, ICIP‘04, Singapore, October 24~27 October 2003, pp. 2753-2756.

Luca Antiga (http://villacamozzi.marionegri.it/~luca/)

luca antiga submitted several vessel detection filters to ITK, and is also in charge of the vmtk toolkit (http://villacamozzi.marionegri.it/~luca/vmtk/doku.php). In vmtk he is working on the detection and quantification of vascular vessels. Using vtk so far to represent and handle the vessel representation and further quantification, he will talk about the geometrical problems he is facing (medial axis detection, biffurcation detection, vessel reconstruction, and vessels / branches analyis) and how the tools introduced before would solve current problems and even give him access to further medical problems.

Using voronoi/delaunay a lot, he also witnessed a great improvement in the robustness of the solutions when he changed to an exact kernel. Interested today in ricci flows and other nice discrete algorithms introduced from abstract mathematics by Prof. GU, he is thinking about moving to itkQuadEdge and itkMesh to implement those algorithms. His dreams would be an exact kernel in ITK, and common 3-manifolds (volume meshes) / 2-manifolds (surface meshes) algorithms.

- Piccinelli M, Bacigaluppi S, Boccardi E, Ene-Iordache B, Remuzzi A, Veneziani A, Antiga L Influence of internal carotid artery geometry on aneurysm location and orientation: a computational geometry study. Submitted.
- Antiga L, Steinman DA. Robust and objective decomposition and mapping of bifurcating vessels. IEEE Transactions on Medical Imaging, 23(6): 704-713, June 2004.
- Antiga L, Ene-Iordache B and Remuzzi A. Computational geometry for patient-specific reconstruction and meshing of blood vessels from MR and CT angiography. IEEE Transactions on Medical Imaging, 22(5): 674-684, May 2003.
- Antiga L, Ene-Iordache B, Caverni L, Cornalba GP and Remuzzi A. Geometric reconstruction for computational mesh generation of arterial bifurcations from CT angiography. Computerized Medical Imaging and Graphics, 26(4): 227-235, June 2002.

Back to AHM_2008, Events