Partitioning 3D surface meshes using watershed segmentation #4
Description
Work to Replicate
Mangan, A. & Whitaker, R.
Partitioning 3D surface meshes using watershed segmentation
IEEE Transactions on Visualization and Computer Graphics, Institute of Electrical and Electronics Engineers (IEEE), 1999, 5, 308-321
https://doi.org/10.1109/2945.817348
http://teacher.en.rmutt.ac.th/ktw/Resources/Full%20paper%20PDF/Partitioning%203D%20surface%20meshes%20using%20watershed%20segmentation.pdf
Mangan, A. P. & Whitaker, R. T.
Surface Segmentation Using Morphological Watersheds
IEEE Visualization '98: Late Breaking Topics, 1998, 4
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.464.2788
Motivation
This call for replication is for the implementation of the described algorithm not the specific results of its application described in the paper.
Any code implementing the idea of partitioning/segmenting meshes with a watershed (on meshes) seems to be lost. My motivation to look for an implementation arises from the problem to separate alveoli from ductal airspaces represented by a binary segmentations of the airspaces of 3D dataset of lung tissue, see Fig. 2 of the poster showing perpendicular slices through the labeled dataset:
Using the curvature of a marching cubes mesh of such binary segmentations to separate alveoli seems more promising than the current voxel based approach, as e.g. described in:
Grothausmann, R.; Mühlfeld, C.; Ochs, M. & Knudsen, L.
Shape and Facet Analyses of Alveolar Airspaces of the Lung
Shape in Medical Imaging, Springer International Publishing, 2018, 49-64
https://doi.org/10.1007/978-3-030-04747-4_5
or this poster:
https://gitlab.com/romangrothausmann/sa-alv_poster/blob/master/res/SA-alv_poster.pdf
in particular Fig. 2, where the annotation A marks alveoli which are separated as anatomically expected while Ac marks alveolar cluster that ideally would be separated further and probably would be with a watershed on meshes.
For example the surface of the beige colored Ac with a 2 and dashed lines annotation in the lower image can be seen in this image:
Expected sub-partitions are marked with black lines, optional ones with grey lines.
The surface coloring originates from the following analyses (e.g. a facet analysis) which are based on meshes (i.e. surface representation) rather than on a volumetric voxel representation, so switching from voxel to meshes for the separation would not be a problem.
Apart from emails, I discussing the problem with Ross Whitaker at MICCAI2018 but he does not see a chance to recover the code. I also contacted authors of other articles citing the ones above having used that algorithm but sadly none (David Page, Anshuman Razdan, Ariel Shamir, Guillaume Lavoué @glavoue, Iurie Chiosa) seem to have the code (any more).
Other kind of mesh partitioning using
VSA (in MEPP: https://github.com/MEPP-team/MEPP/tree/e48ca4272d9c74519230889b1acffe338f425716/src/components/Segmentation/VSA),
SDF (in cgal: https://doc.cgal.org/latest/Surface_mesh_segmentation/index.html) or MRF (https://perso.liris.cnrs.fr/guillaume.lavoue/rech/soft.html)
do not seem appropriate for the very varying and irregular structures of alveoli.
Replies on the ITK/VTK mailing-lists (from @richardbeare, @dzenanz and @thewtex) gave some ideas and directions on how to implement it (http://itk-users.7.n7.nabble.com/ITK-users-watershed-on-surface-meshs-tt38813.html) but I do not feel confident to be able to implement this on my own, motivating this post here.
Challenges
Apart from the ideas from the mailing lists, there is no concrete base to start with. An implementation in C/C++ for a common library for graph/mesh processing (e.g. boost, VTK, MEPP, cgal) would probably be most useful but an implementation in matlab/octave or R would possibly help too.