# 2008 Winter Project Week Geometry and Topology processing of Meshes

- 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 : current and future ITK Implementations (QuadEdge, Parametrization, ...)
- 05 mn Luca Antiga : current 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. Depending on the rapidity of the US embassy in China to give him a visa to go back, he 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 summarized as

- For genus zero surface in the first column, the mapping can be computed 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 computed 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 computed 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 license, its complexity, the lack of support of several key platform, and the lack of support for Images was ruling it out for Image processing oriented 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 data structure 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 (http://hdl.handle.net/1926/1315) 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. We 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 with a 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, Delaunay triangulations. http://iorich.caltech.edu/guithoughts/wiki/itkQuadEdgeMesh

- 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 Vascular Modelling Toolkit (vmtk, http://vmtk.sourceforge.net), developed in collaboration with David Steinman, University of Toronto. In vmtk he is working on the detection and quantification of vessels, as well as on pre- and post-processing for computational fluid dynamics (CFD), aimed at population studies on the relationships between geometry, hemodynamics and physio-pathology of the cardiovascular system. 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, bifurcation detection, vessel reconstruction, and vessels / branch analysis) and how the tools discussed in this breakout session would solve current problems and allow further investigations on different 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, 3-manifolds (volume meshes) / 2-manifolds (surface meshes) algorithms, and ultimately to have computational and differential geometry infrastructure available in ITK. And Python and vmtk in Slicer, but that's another story (we're almost there with that!).

- 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.
- Thomas JB, Antiga L, Che S, Milner JS, Hangan Steinman DA, Spence JD, Rutt BK and Steinman DA. Variation in the carotid bifurcation geometry of young vs. older adults: Implications for "geometric risk" of atherosclerosis. Stroke, 36(11): 2450-2456, Nov 2005.
- 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