Computer Aided Design (Proceedings of SPM 2011), accepted
The medial axis is an important shape descriptor first introduced by Blum via a grassfire burning analogy. However, the medial axes are sensitive to boundary perturbations, which calls for global shape measures to identify meaningful parts of a medial axis. On the other hand, a more compact shape representation than the medial axis, such as a "center point", is needed in various applications ranging from shape alignment to geography. In this paper, we present a uniform approach to define a global shape measure (called extended distance function, or EDF) along the 2D medial axis as well as the center of a 2D shape (called extended medial axis, or EMA). We reveal a number of properties of the EDF and EMA that resemble those of the boundary distance function and the medial axis, and show that EDF and EMA can be generated using a fire propagation process similar to Blum's grassfire analogy, which we call the extended grassfire transform. The EDF and EMA are demonstrated on many 2D examples, and are related to and compared with existing formulations. Finally, we demonstrate the utility of EDF and EMA in pruning medial axes, aligning shapes, and shape description.
Proceedings of 23rd Canadian Conference on Computational Geometry, accepted
We are interested in defining a distance measure between two (homeomorphic) shapes, which has a number of potential applications in computer graphics and vision. We propose a new distance measure which intuitively is the least effort of morphing a source shape into a target shape, such that each intermediate shape during the morph is homeomorphic to the source. For a given morph, this "effort" is measured as the maximum distance traveled by any point on the source shape. Our measure is closely related to Frechet distance as well as the homotopic Frechet distance, yet can better characterize the dissimilarity between two curves. This paper discusses the formulation of the distance measure, compares with previous measures, and touches on the challenges in computing the measure.
Journal of Clinical Densitometry, to appear
Diabetic foot diseases, such as ulcerations, infections, and neuropathic (Charcot's) arthropathy, are major complications of diabetes mellitus (DM) and peripheral neuropathy (PN) and may cause osteolysis (bone loss) in foot bones. The purposes of our study were to make computed tomography (CT) measurements of foot-bone volumes and densities and to determine measurement precision (percent coefficients of variation for root-mean-square standard deviations) and least significant changes (LSCs) in these percentages that could be considered biologically real with 95% confidence. Our study shows that volumetric quantitative CT provides precise measurements of volume and BMD for metatarsal and tarsal bones, where diabetic foot diseases commonly occur.
Computer Graphics Forum (Proceedings of Pacific Graphics 2010), accepted
Thinning is a commonly used approach for computing skeleton descriptors. Traditional thinning algorithms often have a simple, iterative structure, yet producing skeletons that are overly sensitive to boundary perturbations. We present a novel thinning algorithm, operating on objects represented as cell complexes, that preserves the simplicity of typical thinning algorithms but generates skeletons that more robustly capture global shape features. Our key insight is formulating a skeleton significance measure, called medial persistence, which identify skeleton geometry at various dimensions (e.g., curves or surfaces) that represent object parts with different anisotropic elongations (e.g., tubes or plates). The measure is generally defined in any dimensions, and can be easily computed using a single thinning pass. Guided by medial persistence, our algorithm produces a family of topology and shape preserving skeletons whose shape and composition can be flexible controlled by desired level of medial persistence.
Proceedings of Symposium of Solid and Physical Modeling (SPM) 2010, accepted
Extremal surfaces are a class of implicit surfaces that have been found useful in a variety of geometry reconstruction applications. Compared to iso-surfaces, extremal surfaces are particularly challenging to construct in part due to the presence of boundaries and the lack of a consistent orientation. We present a novel, grid-based algorithm for constructing polygonal approximations of extremal surfaces that may be open or unorientable. The algorithm is simple to implement and applicable to both uniform and adaptive grid structures. More importantly, the resulting discrete surface preserves the structural property of the extremal surface in a grid-independent manner. The algorithm is applied to extract ridge surfaces from intensity volumes and reconstruct surfaces from point set with unoriented normals.
As biomedical images and volumes are being collected at an increasing speed, there is a growing demand for efficient means to organize spatial information for comparative analysis. In many scenarios, such as determining gene expression patterns by in situ hybridization, the images are collected from multiple subjects over a common anatomical region, such as the brain. A fundamental challenge in comparing spatial data from different images is how to account for the shape variations among subjects, which make direct image-to-image comparisons meaningless. In this paper, we describe subdivision meshes as a geometric means to efficiently organize 2D images and 3D volumes collected from different subjects for comparison. The key advantages of a subdivision mesh for this purpose are its light-weight geometric structure and its explicit modeling of anatomical boundaries, which enable efficient and accurate registration. The multi-resolution structure of a subdivision mesh also allows development of fast comparison algorithms among registered images and volumes.
Sixth Eurographics Workshop on Sketch Based Interfaces and Modeling, Accepted
In this paper, we take the first steps towards bridging the gap between the new surface reconstruction technologies and putting those methods to use in practice. We develop a novel interface for modeling surfaces from volume data by allowing the user to sketch contours on arbitrarily oriented cross-sections of the volume, and we examine the users' ability to contour the same structures using oblique cross-sections with similar consistency as they can using parallel cross-sections. We measure the inter-observer and intra-observer variability of trained physicians contouring on oblique cross-sections of real patient data as compared to the traditional parallel cross-sections, and show that the variation is much higher for oblique contouring. We then show that this variability can be greatly reduced by integrating a collection of training images into the interface.
Lecture Notes in Computer Science (Proceedings of MICCAI 2008), 5241:296-304
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.
Computer Graphics Forum (Proceedings of Eurographics 2008), 27(2):155-163
Second place in SIGGRAPH 2007 SRC (student research competition).
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.
Journal of Digital Imaging, To appear
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.
One of the 25 semi-finalist in SIGGRAPH 2009 SRC (student research competition).
Often times, the shape of an object may be better described using
medial structures at even lower dimensions than the MA. For example,
consider the 3D model in the left figure. The head
has a plate-like shape and can be naturally described by the MA,
which consists of medial surfaces. The back handle, on the other hand,
have tube-like shapes and would be more appropriately represented
by medial curves. In the latter case, the MA may not be the desirable
In this paper, we propose for the first time a unified approach of defining medial geometry at different dimensions and evaluating their suitability for shape description. Based on the definition, we describe a discrete distance transform that approximates the medial geometry at various dimensions, which leads to a simple and robust algorithm for constructing a multi-dimensional skeleton.
Second place in SIGGRAPH 2008 SRC (student research competition).
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.
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.