3D Thinning on Cell Complexes for Computing Curve and Surface Skeletons

Master's Thesis

Skeletons are useful shape descriptors in a range of applications such as object recognition, matching, and segmentation. A classical approach for computing skeletons starts from an object represented digitally as a collection of points on a spatial grid and iteratively peels off points on the boundary, a process known as thinning. While simple to implement and efficient to run, existing thinning algorithms have difficulty in generating thin, topology-preserving and shape-preserving skeletons, and some of these difficulties are inherent in the point-based object representation. In this thesis, we propose to perform thinning on an alternative digital representation, a cell complex. We show how thinning on cell complex resolves two problems inherent in the point-based representation, namely not being able to preserve topology using local operators during parallel thinning and not being able to ensure a thin skeleton. In addition, we propose two skeleton significance measures for cell complexes that capture global shape properties and can be computed locally during thinning. Based on the measures, we present a simple and efficient thinning algorithm on 3D cell complexes that guarantees to generate thin, homotopy-preserving skeleton that consists of curves and surfaces reflecting the shape components of the 3D object.

Download: ( Thesis PPT )

Surface reconstruction from point sets using a projection operator

Ly Phan, Lu Liu, Sasakthi Abeysinghe, Tao Ju, Cindy Grimm

Generating surfaces from scattered data points has been of great interest in the geometric processing community due to recent advances in scanning technologies. A mathematical definition of such surfaces was proposed in the seminal work of Amenta 2004 as the extremal surface of an un-oriented vector field and an energy function. Although precisely defined, the surface was constructed indirectly by a projection process that results in a dense point set instead of explicit mesh geometry. While later works have improved the vector field and energy function, the surface construction process remains indirect. We propose a grid-based algorithm that directly extracts the extremal surface geometry, given a smooth vector field and energy function. The key observation that enables this direct construction is that the extremal surface can be considered as the singularity of an oriented vector field, which can be computed directly using a contour-like approach.

Download: ( Poster Abstract )

Interactive Separation of Segmented Bones in CT Volumes Using Graph Cut

Lecture Notes in Computer Science (Proceedings of MICCAI 2008), 5241:296-304
L. Liu, D. Raber, D. Nopachai, P. Commean, D. Sinacore, F. Prior, R. Pless, and T. Ju

We present a fast, interactive method for separating bones that have been collectively segmented from a CT volume. Given userprovided seed points, the method computes the separation as a multiway cut on a weighted graph constructed from the binary, segmented volume. By properly designing and weighting the graph, we show that the resulting cut can accurately be placed at bone-interfaces using only a small number of seed points even when the data is noisy. The method has been implemented with an interactive graphical interface, and used to separate the 12 human foot bones in 10 CT volumes. The interactive tool produced compatible result with a ground-truth separation, generated by a completely manual labelling procedure, while reducing the human interaction time from a mean of 2.4 hours per volume in manual labelling down to approximately 18 minutes.

Download: ( Paper )

Surface Reconstruction From Non-parallel Curve Networks

Computer Graphics Forum (Proceedings of Eurographics 2008), 27(2):155-163
L. Liu, C. Bajaj, J.O. Deasy, D.A. Low, T. Ju

Building surfaces from cross-section curves has wide applications including bio-medical modeling. Previous work in this area has mostly focused on connecting simple closed curves on parallel cross-sections. Here we consider the more general problem where input data may lie on non-parallel cross-sections and consist of curve networks that represent the segmentation of the underlying object by different material or tissue types (e.g., skin, muscle, bone, etc.) on each cross-section. The desired output is a surface network that models both the exterior surface and the internal partitioning of the object. We introduce an algorithm that is capable of handling curve networks of arbitrary shape and topology on cross-section planes with arbitrary orientations. Our algorithm is simple to implement and is guaranteed to produce a closed surface network that interpolates the curve network on each cross-section. Our method is demonstrated on both synthetic and bio-medical examples.

Download: ( Paper Software PPT Video )


Aug 8, 07: This work won Second Place in the ACM Student Research Competition at Siggraph. ( Poster )

Tarsal and Metatarsal Bone Mineral Density Measurement using Volumetric Quantitative Computed Tomography

Journal of Digital Imaging, To appear
P. K. Commean, T. Ju, L. Liu, D. R. Sinacore, M. K. Hastings, M. J. Mueller

A new method for measuring bone mineral density (BMD) of the tarsal and metatarsals is described using volumetric quantitative computed tomography (VQCT) in conjunction with geometric subdivision in subjects with diabetes mellitus and peripheral neuropathy. In addition to whole-bone segmentation and measurement, we performed atlas-based partitioning of sub-regions within the second metatarsal for all subjects, from which the volumes and BMDs were obtained for each sub-region. The sub-region measurement BMD errors (root mean square coefficient of variation) within the shaft, proximal end and distal end were shown to vary by approximately 1% between the two scans of each subject. These methods can provide an important outcome measure for clinical research trials investigating the effects of interventions, aging or disease progression on bone loss or gain in individual foot bones.