An Unified Multiscale Framework for Planar, Surface, and Curve Skeletonization.

Computing skeletons of 2D shapes, and medial surface and curve skeletons of 3D shapes, is a challenging task. In particular, there is no unified framework that detects all types of skeletons using a single model, and also produces a multiscale representation which allows to progressively simplify, or regularize, all skeleton types. In this paper, we present such a framework. We model skeleton detection and regularization by a conservative mass transport process from a shape's boundary to its surface skeleton, next to its curve skeleton, and finally to the shape center. The resulting density field can be thresholded to obtain a multiscale representation of progressively simplified surface, or curve, skeletons. We detail a numerical implementation of our framework which is demonstrably stable and has high computational efficiency. We demonstrate our framework on several complex 2D and 3D shapes.

Interactive segmentation and visualization of DTI data using a hierarchical watershed representation.

Magnetic resonance diffusion tensor imaging (DTI) measures diffusion of water molecules and is used to characterize orientation of white matter fibers and connectivity of neurological structures. Segmentation and visualization of DT images is challenging, because of low data quality and complexity of anatomical structures. In this paper, we propose an interactive segmentation approach, based on a hierarchical representation of the input DT image through a tree structure. The tree is obtained by successively merging watershed regions, based on the morphological waterfall approach, hence the name watershed tree. Region merging is done according to a combined similarity and homogeneity criterion. We introduce filters that work on the proposed tree representation, and that enable region-based attribute filtering of DTI data. Linked views between the visualizations of the simplified DT image and the tree enable a user to visually explore both data and tree at interactive rates. The coupling of filtering, semiautomatic segmentation by labeling nodes in the tree, and various interaction mechanisms support the segmentation task. Our method is robust against noise, which we demonstrate on synthetic and real DTI data.

Surface and curve skeletonization of large 3D models on the GPU.

We present a GPU-based framework for extracting surface and curve skeletons of 3D shapes represented as large polygonal meshes. We use an efficient parallel search strategy to compute point-cloud skeletons and their distance and feature transforms (FTs) with user-defined precision. We regularize skeletons by a new GPU-based geodesic tracing technique which is orders of magnitude faster and more accurate than comparable techniques. We reconstruct the input surface from skeleton clouds using a fast and accurate image-based method. We also show how to reconstruct the skeletal manifold structure as a polygon mesh and the curve skeleton as a polyline. Compared to recent skeletonization methods, our approach offers two orders of magnitude speed-up, high-precision, and low-memory footprints. We demonstrate our framework on several complex 3D models.

Fast Sparse Level Sets on Graphics Hardware.

The level-set method is one of the most popular techniques for capturing and tracking deformable interfaces. Although level sets have demonstrated great potential in visualization and computer graphics applications, such as surface editing and physically based modeling, their use for interactive simulations has been limited due to the high computational demands involved. In this paper, we address this computational challenge by leveraging the increased computing power of graphics processors, to achieve fast simulations based on level sets. Our efficient, sparse GPU level-set method is substantially faster than other state-of-the-art, parallel approaches on both CPU and GPU hardware. We further investigate its performance through a method for surface reconstruction, based on GPU level sets. Our novel multiresolution method for surface reconstruction from unorganized point clouds compares favorably with recent, existing techniques and other parallel implementations. Finally, we point out that both level-set computations and rendering of level-set surfaces can be performed at interactive rates, even on large volumetric grids. Therefore, many applications based on level sets can benefit from our sparse level-set method.

Efficient surface reconstruction from noisy data using regularized membrane potentials.

A physically motivated method for surface reconstruction is proposed that can recover smooth surfaces from noisy and sparse data sets. No orientation information is required. By a new technique based on regularized-membrane potentials the input sample points are aggregated, leading to improved noise tolerability and outlier removal, without sacrificing much with respect to detail (feature) recovery. After aggregating the sample points on a volumetric grid, a novel, iterative algorithm is used to classify grid points as exterior or interior to the surface. This algorithm relies on intrinsic properties of the smooth scalar field on the grid which emerges after the aggregation step. Second, a mesh-smoothing paradigm based on a mass-spring system is introduced. By enhancing this system with a bending-energy minimizing term we ensure that the final triangulated surface is smoother than piecewise linear. In terms of speed and flexibility, the method compares favorably with respect to previous approaches. Most parts of the method are implemented on modern graphics processing units (GPUs). Results in a wide variety of settings are presented, ranging from surface reconstruction on noise-free point clouds to grayscale image segmentation.

Efficient surface reconstruction using generalized coulomb potentials.

We propose a novel, geometrically adaptive method for surface reconstruction from noisy and sparse point clouds, without orientation information. The method employs a fast convection algorithm to attract the evolving surface towards the data points. The force field in which the surface is convected is based on generalized Coulomb potentials evaluated on an adaptive grid (i.e., an octree) using a fast, hierarchical algorithm. Formulating reconstruction as a convection problem in a velocity field generated by Coulomb potentials offers a number of advantages. Unlike methods which compute the distance from the data set to the implicit surface, which are sensitive to noise due to the very reliance on the distance transform, our method is highly resilient to shot noise since global, generalized Coulomb potentials can be used to disregard the presence of outliers due to noise. Coulomb potentials represent long-range interactions that consider all data points at once, and thus they convey global information which is crucial in the fitting process. Both the spatial and temporal complexities of our spatially-adaptive method are proportional to the size of the reconstructed object, which makes our method compare favorably with respect to previous approaches in terms of speed and flexibility. Experiments with sparse as well as noisy data sets show that the method is capable of delivering crisp and detailed yet smooth surfaces.

Shape representation and recognition through morphological curvature scale spaces.

A multiscale, morphological method for the purpose of shape-based object recognition is presented. A connected operator similar to the morphological hat-transform is defined, and two scale-space representations are built, using the curvature function as the underlying one-dimensional signal. Each peak and valley of the curvature is extracted and described by its maximum and average heights and by its extent and represents an entry in the top or bottom hat-transform scale spaces. We demonstrate object recognition based on hat-transform scale spaces for three large data sets, a set of diatom contours, the set of silhouettes from the MPEG-7 database and the set of two-dimensional views of three-dimensional objects from the COIL-20 database. Our approach outperforms other methods for which comparative results exist.

Automatic segmentation of diatom images for classification.

A general framework for automatic segmentation of diatom images is presented. This segmentation is a critical first step in contour-based methods for automatic identification of diatoms by computerized image analysis. We review existing results, adapt popular segmentation methods to this difficult problem, and finally develop a method that substantially improves existing results. This method is based on the watershed segmentation from mathematical morphology, and belongs to the class of hybrid segmentation techniques. The novelty of the method is the use of connected operators for the computation and selection of markers, a critical ingredient in the watershed method to avoid over-segmentation. All methods considered were used to extract binary contours from a large database of diatom images, and the quality of the contours was evaluated both visually and based on identification performance.

CPM: a deformable model for shape recovery and segmentation based on charged particles.

A novel, physically motivated deformable model for shape recovery and segmentation is presented. The model, referred to as the charged-particle model (CPM), is inspired by classical electrodynamics and is based on a simulation of charged particles moving in an electrostatic field. The charges are attracted towards the contours of the objects of interest by an electrostatic field, whose sources are computed based on the gradient-magnitude image. The electric field plays the same role as the potential forces in the snake model, while internal interactions are modeled by repulsive Coulomb forces. We demonstrate the flexibility and potential of the model in a wide variety of settings: shape recovery using manual initialization, automatic segmentation, and skeleton computation. We perform a comparative analysis of the proposed model with the active contour model and show that specific problems of the latter are surmounted by our model. The model is easily extendable to 3D and copes well with noisy images.