Curve-skeleton properties, applications, and algorithms

Tree Recovery by Dynamic Programming

Tree-like structures are common, naturally occurring objects that are of interest to many fields of study, such as plant science and biomedicine. Analysis of these structures is typically based on skeletons extracted from captured data, which often contain spurious cycles that need to be removed. We propose a dynamic programming algorithm for solving the NP-hard tree recovery problem formulated by (Estrada et al. 2015), which seeks a least-cost partitioning of the graph nodes that yields a directed tree. Our algorithm finds the optimal solution by iteratively contracting the graph via node-merging until the problem can be trivially solved. By carefully designing the merging sequence, our algorithm can efficiently recover optimal trees for many real-world data where (Estrada et al. 2015) only produces sub-optimal solutions. We also propose an approximate variant of dynamic programming using beam search, which can process graphs containing thousands of cycles with significantly improved optimality and efficiency compared with (Estrada et al. 2015).

How to make sense of 3D representations for plant phenotyping: a compendium of processing and analysis techniques

Computer vision technology is moving more and more towards a three-dimensional approach, and plant phenotyping is following this trend. However, despite its potential, the complexity of the analysis of 3D representations has been the main bottleneck hindering the wider deployment of 3D plant phenotyping. In this review we provide an overview of typical steps for the processing and analysis of 3D representations of plants, to offer potential users of 3D phenotyping a first gateway into its application, and to stimulate its further development. We focus on plant phenotyping applications where the goal is to measure characteristics of single plants or crop canopies on a small scale in research settings, as opposed to large scale crop monitoring in the field.

BowelNet: Joint Semantic-Geometric Ensemble Learning for Bowel Segmentation From Both Partially and Fully Labeled CT Images

Accurate bowel segmentation is essential for diagnosis and treatment of bowel cancers. Unfortunately, segmenting the entire bowel in CT images is quite challenging due to unclear boundary, large shape, size, and appearance variations, as well as diverse filling status within the bowel. In this paper, we present a novel two-stage framework, named BowelNet, to handle the challenging task of bowel segmentation in CT images, with two stages of 1) jointly localizing all types of the bowel, and 2) finely segmenting each type of the bowel. Specifically, in the first stage, we learn a unified localization network from both partially- and fully-labeled CT images to robustly detect all types of the bowel. To better capture unclear bowel boundary and learn complex bowel shapes, in the second stage, we propose to jointly learn semantic information (i.e., bowel segmentation mask) and geometric representations (i.e., bowel boundary and bowel skeleton) for fine bowel segmentation in a multi-task learning scheme. Moreover, we further propose to learn a meta segmentation network via pseudo labels to improve segmentation accuracy. By evaluating on a large abdominal CT dataset, our proposed BowelNet method can achieve Dice scores of 0.764, 0.848, 0.835, 0.774, and 0.824 in segmenting the duodenum, jejunum-ileum, colon, sigmoid, and rectum, respectively. These results demonstrate the effectiveness of our proposed BowelNet framework in segmenting the entire bowel from CT images.

Computational methods for the characterization of Apis mellifera comb architecture

The architecture of honey bee combs embodies a range of expressions associated with swarm intelligence, emergent behaviors, and social organization, which has drawn scientists to study them as a model of collective construction processes. Until recently, however, the development of models to characterize comb-building behavior has relied heavily on laborious manual observations and measurements. The use of high-throughput multi-scale analyses to investigate the geometric features of Apis mellifera comb therefore has the potential to vastly expand our understanding of comb-building processes. Inspired by this potential, here we explore connections between geometry and behavior by utilizing computational methods for the detailed examination of hives constructed within environments designed to observe how natural building rule sets respond to environmental perturbations. Using combs reconstructed from X-ray micro-computed tomography source data, we introduce a set of tools to analyze geometry and material distributions from these scans, spanning from individual cells to whole-hive-level length scales. Our results reveal relationships between cell geometry and comb morphology, enable the generalization of prior research on build direction, demonstrate the viability of our methods for isolating specific features of comb architecture, and illustrate how these results may be employed to investigate hive-level behaviors related to build-order and material distributions.

Geometry-Driven Detection, Tracking and Visual Analysis of Viscous and Gravitational Fingers

Viscous and gravitational flow instabilities cause a displacement front to break up into finger-like fluids. The detection and evolutionary analysis of these fingering instabilities are critical in multiple scientific disciplines such as fluid mechanics and hydrogeology. However, previous detection methods of the viscous and gravitational fingers are based on density thresholding, which provides limited geometric information of the fingers. The geometric structures of fingers and their evolution are important yet little studied in the literature. In this article, we explore the geometric detection and evolution of the fingers in detail to elucidate the dynamics of the instability. We propose a ridge voxel detection method to guide the extraction of finger cores from three-dimensional (3D) scalar fields. After skeletonizing finger cores into skeletons, we design a spanning tree based approach to capture how fingers branch spatially from the finger skeletons. Finally, we devise a novel geometric-glyph augmented tracking graph to study how the fingers and their branches grow, merge, and split over time. Feedback from earth scientists demonstrates the usefulness of our approach to performing spatio-temporal geometric analyses of fingers.

A Simple and Stable Centeredness Measure for 3D Curve Skeleton Extraction

Existing methods for extracting 3D curve skeletons mostly suffer from the difficulty of finding the center points of 3D shapes and tedious manual adjustments of the thresholds for pruning spurious branches due to the influence of shape boundary perturbations. In this article, we present a method based on medial surfaces of 3D shapes for the convenient and fast extraction of high-quality curve skeletons. Our main contribution is a simple and stable centeredness measure. It is based on simulating fire propagation via the scheme of inside-out evolution from the interior to the boundary, differentiating it from existing methods that use the scheme of outside-in evolution from the boundary to the interior. Thus, our measure is much more localized, and it can be implemented with a high degree of parallelism. In addition, we propose measures to effectively suppress the influence of details to obtain a stable measurement, and employ minimum set covers to optimize the center points to generate compact skeletons, which enables spurious branches to be effectively excluded without the tedious work of manually adjusting thresholds. Our experiments show the superiority of our method over existing methods, including its convenient generation of clean, compact and centered curve skeletons while running much faster than state-of-the-art methods.

Representing living architecture through skeleton reconstruction from point clouds

Living architecture, changing in structure with annual growth, requires precise, regular characterisation. However, its geometric irregularity and topological complexity make documentation using traditional methods difficult and presents challenges in creating useful models for mechanical and physiological analyses. Two kinds of living architecture are examined: historic living root bridges grown in Meghalaya, India, and contemporary ‘Baubotanik’ structures designed and grown in Germany. These structures exhibit common features, in particular network-like structures of varying complexity that result from inosculations between shoots or roots. As an answer to this modelling challenge, we present the first extensive documentation of living architecture using photogrammetry and a subsequent skeleton extraction workflow that solves two problems related to the anastomoses and varying nearby elements specific to living architecture. Photogrammetry was used as a low cost method, supplying detailed point clouds of the structures’ visible surfaces. A workflow based on voxel-thinning (using deletion templates and adjusted p-simplicity criteria) provides efficient, accurate skeletons. A volume reconstruction method is derived from the thinning process. The workflow is assessed on seven characteristics beneficial in representing living architecture in comparison with alternative skeleton extraction methods. The resulting models are ready for use in analytical tools, necessary for functional, responsible design.

Visualizing Acoustic Imaging of Hydrothermal Plumes on the Seafloor

Hydrothermal plumes are ongoing venting of hot solutions, on a time scale of months to years, relating to volcanic activities on the seafloor. Recent developments in acoustical observational techniques have produced images to support the scientific investigation of such plumes. However, understanding the complex behavior of plumes in a long-time series poses a challenge to the existing analysis approaches. The motivation of this work is to use visualization techniques to facilitate the visual exploration and analysis of plumes and to help domain scientists compare the actual behavior of plumes predicted by tidal interaction models and buoyant plume models incorporating forced entrainment effects. Methods of geovisualization are combined with time-varying feature-based techniques to create visualizations of plumes which are applied to an acoustic imaging dataset collected using the Cabled Observatory Vent Imaging Sonar in the Northeast Pacific. The results give new insights to the data and confirm the hypothesis of plumes.

Mass-Driven Topology-Aware Curve Skeleton Extraction from Incomplete Point Clouds

We introduce a mass-driven curve skeleton as a curve skeleton representation for 3D point cloud data. The mass-driven curve skeleton presents geometric properties and mass distribution of a curve skeleton simultaneously. The computation of the mass-driven curve skeleton is formulated as a minimization of Wasserstein distance, with an entropic regularization term, between mass distributions of point clouds and curve skeletons. Assuming that the mass of one sampling point should be transported to a line-like structure, a topology-aware rough curve skeleton is extracted via the optimal transport plan. A Dirichlet energy regularization term is then used to obtain a smooth curve skeleton via geometric optimization. Given that rough curve skeleton extraction does not depend on complete point clouds, our algorithm can be directly applied to curve skeleton extraction from incomplete point clouds. We demonstrate that a mass-driven curve skeleton can be directly applied to an unoriented raw point scan with significant noise, outliers and large areas of missing data. In comparison with state-of-the-art methods on curve skeleton extraction, the performance of the proposed mass-driven curve skeleton is more robust in terms of extracting a correct topology.

Geometrical and Topological Analysis of Pore Space in Sandstones Based on X-ray Computed Tomography

The pore geometry and topology properties of pore space in rocks are significant for a better understanding of the complex hydrologic and elastic properties. However, geometry and topology information about the sandstone pore structures is not fully available. In this study, we obtained the topological and geometrical pore parameters from a representative elementary volume (REV) for fluid flow in sandstone samples. For comparison, eight types of sandstones with various porosities were studied based on the X-ray micro-computed tomography technique. In this study, the REV size was selected based on the parameters from the respective pore network models (PNM), not just the porosity. Our analysis indicates that despite different porosity, all the sandstone samples have highly triangular-shaped pores and a high degree of pore structural isotropy. The high porosity group sandstones exhibit wider ranges of pore sizes than the low porosity group sandstones. Compared to the high porosity group sandstones, the low porosity group sandstones samples showing a higher global aspect ratio, indicating some pores exist in the form of bottlenecks. The pore topological properties of different sandstones show a high dependence of the porosity. The high porosity group sandstones obtain large coordination numbers, large connectivity densities and low tortuosities. The results from this study will help better understand the complex pore structure and the fluid flow in sandstone.

Automatic Fiber Length Measurements with a Multi-Stencil Fast Marching Method on Microscopy Images

Fiber length has a strong impact on the mechanical properties of composite materials. It is one of the most important quantitative features in characterizing microstructures for understanding the material performance. Studies conducted to determine fiber length distribution have primarily focused on sample preparation and fiber dispersion. However, the subsequent image analysis is frequently performed manually or semi-automatically, which either requires careful sample preparation or manual intervention in the image analysis and processing. In this article, an image processing and analysis method has been developed based on medial axis transformation via the multi-stencil fast marching method for fiber length measurements on acquired microscopy images. The developed method can be implemented fully automatically and without any user induced delays. This method offers high efficiency, sub-pixel accuracy, and excellent statistical representativity.

Skeletonization of Plant Point Cloud Data in Stochastic Optimization Framework.. [DOI: 10.1101/2020.02.15.950519] [Citation(s) in RCA: 0] [Impact Index Per Article: 0]

Skeleton extraction from 3D plant point cloud data is an essential prior for myriads of phenotyping studies. Although skeleton extraction from 3D shapes have been studied extensively in the computer vision and graphics literature, handling the case of plants is still an open problem. Drawbacks of the existing approaches include the zigzag structure of the skeleton, nonuniform density of skeleton points, lack of points in the areas having complex geometry structure, and most importantly the lack of biological relevance. With the aim to improve existing skeleton structures of state-of-the-art, we propose a stochastic framework which is supported by the biological structure of the original plant (we consider plants without any leaves). Initially we estimate the branching structure of the plant by the notion of β-splines to form a curve tree defined as a finite set of curves joined in a tree topology with certain level of smoothness. In the next phase, we force the discrete points in the curve tree to move towards the original point cloud by treating each point in the curve tree as a center of Gaussian, and points in the input cloud data as observations from the Gaussians. The task is to find the correct locations of the Gaussian centroids by maximizing a likelihood. The optimization technique is iterative and is based on the Expectation Maximization (EM) algorithm. The E-step estimates which Gaussian the observed point cloud was sampled from, and the M-step maximizes the negative log-likelihood that the observed points were sampled from the Gaussian Mixture Model (GMM) with respect to the model parameters. We experiment with several real world and synthetic datasets and demonstrate the robustness of the approach over the state-of-the-art.

Accurate Cross-Section Estimation of Blood Vessels in Choroidal Haller's Layer: An Iterative Method based on 3D Tensor Voting

Various eye diseases, including polypoidal choroidal vasculopathy (PCV) and age-related macular degeneration (AMD), affect choroidal vasculature early, but possibly minutely. However, due to the complex networked structure of the vasculature, it becomes hard to visualize, analyze and detect such changes in 2D OCT B-scan images. In contrast, algorithmic evaluation of cross-section facilitates clinicians in tracing minute variations in the vessel network, and quantifying those correlated with pathologies, potentially leading to early diagnosis. In this context, we proposed a novel method of estimating vessel cross-sections in choroidal Haller's layer. Accuracy of our method was evaluated on synthetic as well as clinical data by trained optometrists, and earned a confidence score of 90%, marking about 60% improvement over estimates based on a well-known tree-based method.

Skeletonization of Plant Point Cloud Data Using Stochastic Optimization Framework

Skeleton extraction from 3D plant point cloud data is an essential prior for myriads of phenotyping studies. Although skeleton extraction from 3D shapes have been studied extensively in the computer vision and graphics literature, handling the case of plants is still an open problem. Drawbacks of the existing approaches include the zigzag structure of the skeleton, nonuniform density of skeleton points, lack of points in the areas having complex geometry structure, and most importantly the lack of biological relevance. With the aim to improve existing skeleton structures of state-of-the-art, we propose a stochastic framework which is supported by the biological structure of the original plant (we consider plants without any leaves). Initially we estimate the branching structure of the plant by the notion of β-splines to form a curve tree defined as a finite set of curves joined in a tree topology with certain level of smoothness. In the next phase, we force the discrete points in the curve tree to move toward the original point cloud by treating each point in the curve tree as a center of Gaussian, and points in the input cloud data as observations from the Gaussians. The task is to find the correct locations of the Gaussian centroids by maximizing a likelihood. The optimization technique is iterative and is based on the Expectation Maximization (EM) algorithm. The E-step estimates which Gaussian the observed point cloud was sampled from, and the M-step maximizes the negative log-likelihood that the observed points were sampled from the Gaussian Mixture Model (GMM) with respect to the model parameters. We experiment with several real world and synthetic datasets and demonstrate the robustness of the approach over the state-of-the-art.

Systematic Method for Morphological Reconstruction of the Semicircular Canals Using a Fully Automatic Skeletonization Process

We present a novel method to characterize the morphology of semicircular canals of the inner ear. Previous experimental works have a common nexus, the human-operator subjectivity. Although these methods are mostly automatic, they rely on a human decision to determine some particular anatomical positions. We implement a systematic analysis where there is no human subjectivity. Our approach is based on a specific magnetic resonance study done in a group of 20 volunteers. From the raw data, the proposed method defines the centerline of all three semicircular canals through a skeletonization process and computes the angle of the functional pair and other geometrical parameters. This approach allows us to assess the inter-operator effect on other methods. From our results, we conclude that, although an average geometry can be defined, the inner ear anatomy cannot be reduced to a single geometry as seen in previous experimental works. We observed a relevant variability of the geometrical parameters in our cohort of volunteers that hinders this usual simplification.

Cognitive and White-Matter Compartment Models Reveal Selective Relations between Corticospinal Tract Microstructure and Simple Reaction Time

The speed of motor reaction to an external stimulus varies substantially between individuals and is slowed in aging. However, the neuroanatomical origins of interindividual variability in reaction time (RT) remain unclear. Here, we combined a cognitive model of RT and a biophysical compartment model of diffusion-weighted MRI (DWI) to characterize the relationship between RT and microstructure of the corticospinal tract (CST) and the optic radiation (OR), the primary motor output and visual input pathways associated with visual-motor responses. We fitted an accumulator model of RT to 46 female human participants' behavioral performance in a simple reaction time task. The non-decision time parameter (T _er) derived from the model was used to account for the latencies of stimulus encoding and action initiation. From multi-shell DWI data, we quantified tissue microstructure of the CST and OR with the neurite orientation dispersion and density imaging (NODDI) model as well as the conventional diffusion tensor imaging model. Using novel skeletonization and segmentation approaches, we showed that DWI-based microstructure metrics varied substantially along CST and OR. The T _er of individual participants was negatively correlated with the NODDI measure of the neurite density in the bilateral superior CST. Further, we found no significant correlation between the microstructural measures and mean RT. Thus, our findings suggest a link between interindividual differences in sensorimotor speed and selective microstructural properties in white-matter tracts.SIGNIFICANCE STATEMENT How does our brain structure contribute to our speed to react? Here, we provided anatomically specific evidence that interindividual differences in response speed is associated with white-matter microstructure. Using a cognitive model of reaction time (RT), we estimated the non-decision time, as an index of the latencies of stimulus encoding and action initiation, during a simple reaction time task. Using an advanced microstructural model for diffusion MRI, we estimated the tissue properties and their variations along the corticospinal tract and optic radiation. We found significant location-specific correlations between the microstructural measures and the model-derived parameter of non-decision time but not mean RT. These results highlight the neuroanatomical signature of interindividual variability in response speed along the sensorimotor pathways.

An Accurate Skeleton Extraction Approach From 3D Point Clouds of Maize Plants

Accurate and high-throughput determination of plant morphological traits is essential for phenotyping studies. Nowadays, there are many approaches to acquire high-quality three-dimensional (3D) point clouds of plants. However, it is difficult to estimate phenotyping parameters accurately of the whole growth stages of maize plants using these 3D point clouds. In this paper, an accurate skeleton extraction approach was proposed to bridge the gap between 3D point cloud and phenotyping traits estimation of maize plants. The algorithm first uses point cloud clustering and color difference denoising to reduce the noise of the input point clouds. Next, the Laplacian contraction algorithm is applied to shrink the points. Then the key points representing the skeleton of the plant are selected through adaptive sampling, and neighboring points are connected to form a plant skeleton composed of semantic organs. Finally, deviation skeleton points to the input point cloud are calibrated by building a step forward local coordinate along the tangent direction of the original points. The proposed approach successfully generates accurately extracted skeleton from 3D point cloud and helps to estimate phenotyping parameters with high precision of maize plants. Experimental verification of the skeleton extraction process, tested using three cultivars and different growth stages maize, demonstrates that the extracted matches the input point cloud well. Compared with 3D digitizing data-derived morphological parameters, the NRMSE of leaf length, leaf inclination angle, leaf top length, leaf azimuthal angle, leaf growth height, and plant height, estimated using the extracted plant skeleton, are 5.27, 8.37, 5.12, 4.42, 1.53, and 0.83%, respectively, which could meet the needs of phenotyping analysis. The time required to process a single maize plant is below 100 s. The proposed approach may play an important role in further maize research and applications, such as genotype-to-phenotype study, geometric reconstruction, functional structural maize modeling, and dynamic growth animation.

Nanoporous gold: a hierarchical and multiscale 3D test pattern for characterizing X-ray nano-tomography systems

Full-field transmission X-ray microscopy (TXM) is a well established technique, available at various synchrotron beamlines around the world as well as by laboratory benchtop devices. One of the major TXM challenges, due to its nanometre-scale resolution, is the overall instrument stability during the acquisition of the series of tomographic projections. The ability to correct for vertical and horizontal distortions of each projection image during acquisition is necessary in order to achieve the effective 3D spatial resolution. The effectiveness of such an image alignment is also heavily influenced by the absorption properties and strong contrast of specific features in the scanned sample. Here it is shown that nanoporous gold (NPG) can be used as an ideal 3D test pattern for evaluating and optimizing the performance of a TXM instrument for hard X-rays at a synchrotron beamline. Unique features of NPG, such as hierarchical structures at multiple length scales and high absorbing capabilities, makes it an ideal choice for characterization, which involves a combination of a rapid-alignment algorithm applied on the acquired projections followed by the extraction of a set of both 2D- and 3D-descriptive image parameters. This protocol can be used for comparing the efficiency of TXM instruments at different synchrotron beamlines in the world or benchtop devices, based on a reference library of scanned NPG samples, containing information about the estimated horizontal and vertical alignment values, 2D qualitative parameters and quantitative 3D parameters. The possibility to tailor the ligament sizes of NPG to match the achievable resolution in combination with the high electron density of gold makes NPG an ideal 3D test pattern for evaluating the status and performance of a given synchrotron-based or benchtop-based TXM setup.

Vascular amounts and dispersion of caliber-classified vessels as key parameters to quantitate 3D micro-angioarchitectures in multiple myeloma experimental tumors

Blood vessel micro-angioarchitecture plays a pivotal role in tumor progression, metastatic dissemination and response to therapy. Thus, methods able to quantify microvascular trees and their anomalies may allow a better comprehension of the neovascularization process and evaluation of vascular-targeted therapies in cancer. To this aim, the development of a restricted set of indexes able to describe the arrangement of a microvascular tree is eagerly required. We addressed this goal through 3D analysis of the functional microvascular network in sulfo-biotin-stained human multiple myeloma KMS-11 xenografts in NOD/SCID mice. Using image analysis, we show that amounts, spatial dispersion and spatial relationships of adjacent classes of caliber-filtered microvessels provide a near-linear graphical “fingerprint” of tumor micro-angioarchitecture. Position, slope and axial projections of this graphical outcome reflect biological features and summarize the properties of tumor micro-angioarchitecture. Notably, treatment of KMS-11 xenografts with anti-angiogenic drugs affected position and slope of the specific curves without degrading their near-linear properties. The possibility offered by this procedure to describe and quantify the 3D features of the tumor micro-angioarchitecture paves the way to the analysis of the microvascular tree in human tumor specimens at different stages of tumor progression and after pharmacologic interventions, with possible diagnostic and prognostic implications.

Vertebral artery fusiform aneurysm geometry in predicting rupture risk

Cerebral aneurysms affect a significant portion of the adult population worldwide. Despite significant progress, the development of robust techniques to evaluate the risk of aneurysm rupture remains a critical challenge. We hypothesize that vertebral artery fusiform aneurysm (VAFA) morphology may be predictive of rupture risk and can serve as a deciding factor in clinical management. To investigate the VAFA morphology, we use a combination of image analysis and machine learning techniques to study a geometric feature set computed from a depository of 37 (12 ruptured and 25 un-ruptured) aneurysm images. Of the 571 unique features we compute, we distinguish five features for use by our machine learning classification algorithm by an analysis of statistical significance. These machine learning methods achieve state-of-the-art classification performance (81.43 ± 13.08%) for the VAFA morphology, and identify five features (cross-sectional area change of aneurysm, maximum diameter of nearby distal vessel, solidity of aneurysm, maximum curvature of nearby distal vessel, and ratio of curvature between aneurysm and its nearby proximal vessel) as effective predictors of VAFA rupture risk. These results suggest that the geometric features of VAFA morphology may serve as useful non-invasive indicators for the prediction of aneurysm rupture risk in surgical settings.

Fuzzy Object Skeletonization: Theory, Algorithms, and Applications

Skeletonization offers a compact representation of an object while preserving important topological and geometrical features. Literature on skeletonization of binary objects is quite mature. However, challenges involved with skeletonization of fuzzy objects are mostly unanswered. This paper presents a new theory and algorithm of skeletonization for fuzzy objects, evaluates its performance, and demonstrates its applications. A formulation of fuzzy grassfire propagation is introduced; its relationships with fuzzy distance functions, level sets, and geodesics are discussed; and several new theoretical results are presented in the continuous space. A notion of collision-impact of fire-fronts at skeletal points is introduced, and its role in filtering noisy skeletal points is demonstrated. A fuzzy object skeletonization algorithm is developed using new notions of surface- and curve-skeletal voxels, digital collision-impact, filtering of noisy skeletal voxels, and continuity of skeletal surfaces. A skeletal noise pruning algorithm is presented using branch-level significance. Accuracy and robustness of the new algorithm are examined on computer-generated phantoms and micro- and conventional CT imaging of trabecular bone specimens. An application of fuzzy object skeletonization to compute structure-width at a low image resolution is demonstrated, and its ability to predict bone strength is examined. Finally, the performance of the new fuzzy object skeletonization algorithm is compared with two binary object skeletonization methods.

The segmentation of bones in pelvic CT images based on extraction of key frames

Background

Bone segmentation is important in computed tomography (CT) imaging of the pelvis, which assists physicians in the early diagnosis of pelvic injury, in planning operations, and in evaluating the effects of surgical treatment. This study developed a new algorithm for the accurate, fast, and efficient segmentation of the pelvis.

Methods

The proposed method consists of two main parts: the extraction of key frames and the segmentation of pelvic CT images. Key frames were extracted based on pixel difference, mutual information and normalized correlation coefficient. In the pelvis segmentation phase, skeleton extraction from CT images and a marker-based watershed algorithm were combined to segment the pelvis. To meet the requirements of clinical application, physician’s judgment is needed. Therefore the proposed methodology is semi-automated.

Results

In this paper, 5 sets of CT data were used to test the overlapping area, and 15 CT images were used to determine the average deviation distance. The average overlapping area of the 5 sets was greater than 94%, and the minimum average deviation distance was approximately 0.58 pixels. In addition, the key frame extraction efficiency and the running time of the proposed method were evaluated on 20 sets of CT data. For each set, approximately 13% of the images were selected as key frames, and the average processing time was approximately 2 min (the time for manual marking was not included).

Conclusions

The proposed method is able to achieve accurate, fast, and efficient segmentation of pelvic CT image sequences. Segmentation results not only provide an important reference for early diagnosis and decisions regarding surgical procedures, they also offer more accurate data for medical image registration, recognition and 3D reconstruction.

New methods for the geometrical analysis of tubular organs

This paper presents new methods to study the shape of tubular organs. Determining precise cross-sections is of major importance to perform geometrical measurements, such as diameter, wall-thickness estimation or area measurement. Our first contribution is a robust method to estimate orthogonal planes based on the Voronoi Covariance Measure. Our method is not relying on a curve-skeleton computation beforehand. This means our orthogonal plane estimator can be used either on the skeleton or on the volume. Another important step towards tubular organ characterization is achieved through curve-skeletonization, as skeletons allow to compare two tubular organs, and to perform virtual endoscopy. Our second contribution is dedicated to correcting common defects of the skeleton by new pruning and recentering methods. Finally, we propose a new method for curve-skeleton extraction. Various results are shown on different types of segmented tubular organs, such as neurons, airway-tree and blood vessels.

Motion Capture With Ellipsoidal Skeleton Using Multiple Depth Cameras

This paper introduces a novel motion capturing framework which works by minimizing the fitting error between an ellipsoid based skeleton and the input point cloud data captured by multiple depth cameras. The novelty of this method comes from that it uses the ellipsoids equipped with the spherical harmonics encoded displacement and normal functions to capture the geometry details of the tracked object. This method is also integrated with a mechanism to avoid collisions of bones during the motion capturing process. The method is implemented parallelly with CUDA on GPU and has a fast running speed without dedicated code optimization. The errors of the proposed method on the data from Berkeley Multimodal Human Action Database (MHAD) are within a reasonable range compared with the ground truth results. Our experiment shows that this method succeeds on many challenging motions which are failed to be reported by Microsoft Kinect SDK and not tested by existing works. In the comparison with the state-of-art marker-less depth camera based motion tracking work our method shows advantages in both robustness and input data modality.

A robust method for high-precision quantification of the complex three-dimensional vasculatures acquired by X-ray microtomography

The quantification of micro-vasculatures is important for the analysis of angiogenesis on which the detection of tumor growth or hepatic fibrosis depends. Synchrotron-based X-ray computed micro-tomography (SR-µCT) allows rapid acquisition of micro-vasculature images at micrometer-scale spatial resolution. Through skeletonization, the statistical features of the micro-vasculature can be extracted from the skeleton of the micro-vasculatures. Thinning is a widely used algorithm to produce the vascular skeleton in medical research. Existing three-dimensional thinning methods normally emphasize the preservation of topological structure rather than geometrical features in generating the skeleton of a volumetric object. This results in three problems and limits the accuracy of the quantitative results related to the geometrical structure of the vasculature. The problems include the excessively shortened length of elongated objects, eliminated branches of blood vessel tree structure, and numerous noisy spurious branches. The inaccuracy of the skeleton directly introduces errors in the quantitative analysis, especially on the parameters concerning the vascular length and the counts of vessel segments and branching points. In this paper, a robust method using a consolidated end-point constraint for thinning, which generates geometry-preserving skeletons in addition to maintaining the topology of the vasculature, is presented. The improved skeleton can be used to produce more accurate quantitative results. Experimental results from high-resolution SR-µCT images show that the end-point constraint produced by the proposed method can significantly improve the accuracy of the skeleton obtained using the existing ITK three-dimensional thinning filter. The produced skeleton has laid the groundwork for accurate quantification of the angiogenesis. This is critical for the early detection of tumors and assessing anti-angiogenesis treatments.

Fast Marching and Runge-Kutta Based Method for Centreline Extraction of Right Coronary Artery in Human Patients

The CT angiography (CTA) is a clinically indicated test for the assessment of coronary luminal stenosis that requires centerline extractions. There is currently no centerline extraction algorithm that is automatic, real-time and very accurate. Therefore, we sought to (i) develop a hybrid approach by incorporating fast marching and Runge-Kutta based methods for the extraction of coronary artery centerlines from CTA; (ii) evaluate the accuracy of the present method compared to Van's method by using ground truth centerline as a reference; (iii) evaluate the coronary lumen area of our centerline method in comparison with the intravascular ultrasound (IVUS) as the standard of reference. The proposed method was found to be more computationally efficient, and performed better than the Van's method in terms of overlap measures (i.e., OV: [Formula: see text] vs. [Formula: see text]; OF: [Formula: see text] vs. [Formula: see text]; and OT: [Formula: see text] vs. [Formula: see text], all [Formula: see text]). In comparison with IVUS derived coronary lumen area, the proposed approach was more accurate than the Van's method. This hybrid approach by incorporating fast marching and Runge-Kutta based methods could offer fast and accurate extraction of centerline as well as the lumen area. This method may garner wider clinical potential as a real-time coronary stenosis assessment tool.

Post-processing techniques for making reliable measurements from curve-skeletons

Interconnected 3-D networks occur widely in biology and the geometry of such branched networks can be described by curve-skeletons, allowing parameters such as path lengths, path tortuosities and cross-sectional thicknesses to be quantified. However, curve-skeletons are typically sensitive to small scale surface features which may arise from noise in the imaging data. In this paper, new post-processing techniques for curve-skeletons are presented which ensure that measurements of lengths and thicknesses are less sensitive to these small scale surface features. The techniques achieve sub-voxel accuracy and are based on a minimal sphere-network representation in which the object is modelled as a string of minimally overlapping spheres, and as such samples the object on a scale related to the local thickness. A new measure of cross-sectional dimension termed the modal radius is defined and shown to be more robust in comparison with the standard measure (the internal radius), while retaining the desirable feature of capturing the size of structures in terms of a single measure. The techniques are demonstrated by application to trabecular bone and tumour vascular network case studies where the volumetric data was obtained by high resolution computed tomography.

Planar Visualization of Treelike Structures

We present a novel method to create planar visualizations of treelike structures (e.g., blood vessels and airway trees) where the shape of the object is well preserved, allowing for easy recognition by users familiar with the structures. Based on the extracted skeleton within the treelike object, a radial planar embedding is first obtained such that there are no self-intersections of the skeleton which would have resulted in occlusions in the final view. An optimization procedure which adjusts the angular positions of the skeleton nodes is then used to reconstruct the shape as closely as possible to the original, according to a specified view plane, which thus preserves the global geometric context of the object. Using this shape recovered embedded skeleton, the object surface is then flattened to the plane without occlusions using harmonic mapping. The boundary of the mesh is adjusted during the flattening step to account for regions where the mesh is stretched over concavities. This parameterized surface can then be used either as a map for guidance during endoluminal navigation or directly for interrogation and decision making. Depth cues are provided with a grayscale border to aid in shape understanding. Examples are presented using bronchial trees, cranial and lower limb blood vessels, and upper aorta datasets, and the results are evaluated quantitatively and with a user study.

Maximum sphere method for shell patency measurements in viviparous land snails based on X-ray microcomputed tomography imaging

This article presents the working principle of an algorithm designed for the purpose of examining a section of the snail shell canal. The procedure of scanning the specimens is described as well as the tests performed using the proposed algorithm. Also, the digital models used for testing the algorithm are described. The article contains a description of the initial processing of the data, including segmentation and detection of the edges of the image. A flowchart of the algorithm is presented together with its implementation. The data obtained in the course of the microtomographic scanning of one of the snails and a digital model of a canal created for this purpose were subjected to the application of the measurement algorithm. This algorithm was aimed at conducting a spatial analysis of the varying dimensions in the canal section. The process of applying the algorithm and the measurement errors are presented and discussed on the basis of the results.

A Robust and Efficient Curve Skeletonization Algorithm for Tree-Like Objects Using Minimum Cost Paths

Conventional curve skeletonization algorithms using the principle of Blum's transform, often, produce unwanted spurious branches due to boundary irregularities, digital effects, and other artifacts. This paper presents a new robust and efficient curve skeletonization algorithm for three-dimensional (3-D) elongated fuzzy objects using a minimum cost path approach, which avoids spurious branches without requiring post-pruning. Starting from a root voxel, the method iteratively expands the skeleton by adding new branches in each iteration that connects the farthest quench voxel to the current skeleton using a minimum cost path. The path-cost function is formulated using a novel measure of local significance factor defined by the fuzzy distance transform field, which forces the path to stick to the centerline of an object. The algorithm terminates when dilated skeletal branches fill the entire object volume or the current farthest quench voxel fails to generate a meaningful skeletal branch. Accuracy of the algorithm has been evaluated using computer-generated phantoms with known skeletons. Performance of the method in terms of false and missing skeletal branches, as defined by human experts, has been examined using in vivo CT imaging of human intrathoracic airways. Results from both experiments have established the superiority of the new method as compared to the existing methods in terms of accuracy as well as robustness in detecting true and false skeletal branches. The new algorithm makes a significant reduction in computation complexity by enabling detection of multiple new skeletal branches in one iteration. Specifically, this algorithm reduces the number of iterations from the number of terminal tree branches to the worst case performance of tree depth. In fact, experimental results suggest that, on an average, the order of computation complexity is reduced to the logarithm of the number of terminal branches of a tree-like object.

Skeletonization and Partitioning of Digital Images Using Discrete Morse Theory

We show how discrete Morse theory provides a rigorous and unifying foundation for defining skeletons and partitions of grayscale digital images. We model a grayscale image as a cubical complex with a real-valued function defined on its vertices (the voxel values). This function is extended to a discrete gradient vector field using the algorithm presented in Robins, Wood, Sheppard TPAMI 33:1646 (2011). In the current paper we define basins (the building blocks of a partition) and segments of the skeleton using the stable and unstable sets associated with critical cells. The natural connection between Morse theory and homology allows us to prove the topological validity of these constructions; for example, that the skeleton is homotopic to the initial object. We simplify the basins and skeletons via Morse-theoretic cancellation of critical cells in the discrete gradient vector field using a strategy informed by persistent homology. Simple working Python code for our algorithms for efficient vector field traversal is included. Example data are taken from micro-CT images of porous materials, an application area where accurate topological models of pore connectivity are vital for fluid-flow modelling.

Myosin II controls cellular branching morphogenesis and migration in three dimensions by minimizing cell-surface curvature

In many cases cell function is intimately linked to cell shape control. We utilized endothelial cell branching morphogenesis as a model to understand the role of myosin-II in shape control of invasive cells migrating in 3D collagen gels. We applied principles of differential geometry and mathematical morphology to 3D image sets to parameterize cell branch structure and local cell surface curvature. We find that Rho/ROCK-stimulated myosin-II contractility minimizes cell-scale branching by recognizing and minimizing local cell surface curvature. Utilizing micro-fabrication to constrain cell shape identifies a positive feedback mechanism in which low curvature stabilizes myosin-II cortical association, where it acts to maintain minimal curvature. The feedback between myosin-II regulation by and control of curvature drives cycles of localized cortical myosin-II assembly and disassembly. These cycles in turn mediate alternating phases of directionally biased branch initiation and retraction to guide 3D cell migration.

Topology preserving thinning of cell complexes

A topology preserving skeleton is a synthetic representation of an object that retains its topology and many of its significant morphological properties. The process of obtaining the skeleton, referred to as skeletonization or thinning, is a very active research area. It plays a central role in reducing the amount of information to be processed during image analysis and visualization, computer-aided diagnosis, or by pattern recognition algorithms. This paper introduces a novel topology preserving thinning algorithm, which removes simple cells-a generalization of simple points-of a given cell complex. The test for simple cells is based on acyclicity tables automatically produced in advance with homology computations. Using acyclicity tables render the implementation of thinning algorithms straightforward. Moreover, the fact that tables are automatically filled for all possible configurations allows to rigorously prove the generality of the algorithm and to obtain fool-proof implementations. The novel approach enables, for the first time, according to our knowledge, to thin a general unstructured simplicial complex. Acyclicity tables for cubical and simplicial complexes and an open source implementation of the thinning algorithm are provided as an additional material to allow their immediate use in the vast number of applications arising in medical imaging and beyond.

A practical introduction to skeletons for the plant sciences

Before the availability of digital photography resulting from the invention of charged couple devices in 1969, the measurement of plant architecture was a manual process either on the plant itself or on traditional photographs. The introduction of cheap digital imaging devices for the consumer market enabled the wide use of digital images to capture the shape of plant networks such as roots, tree crowns, or leaf venation. Plant networks contain geometric traits that can establish links to genetic or physiological characteristics, support plant breeding efforts, drive evolutionary studies, or serve as input to plant growth simulations. Typically, traits are encoded in shape descriptors that are computed from imaging data. Skeletons are one class of shape descriptors that are used to describe the hierarchies and extent of branching and looping plant networks. While the mathematical understanding of skeletons is well developed, their application within the plant sciences remains challenging because the quality of the measurement depends partly on the interpretation of the skeleton. This article is meant to bridge the skeletonization literature in the plant sciences and related technical fields by discussing best practices for deriving diameters and approximating branching hierarchies in a plant network.

A Web platform for the interactive visualization and analysis of the 3D fractal dimension of MRI data

This study presents a Web platform (http://3dfd.ujaen.es) for computing and analyzing the 3D fractal dimension (3DFD) from volumetric data in an efficient, visual and interactive way. The Web platform is specially designed for working with magnetic resonance images (MRIs) of the brain. The program estimates the 3DFD by calculating the 3D box-counting of the entire volume of the brain, and also of its 3D skeleton. All of this is done in a graphical, fast and optimized way by using novel technologies like CUDA and WebGL. The usefulness of the Web platform presented is demonstrated by its application in a case study where an analysis and characterization of groups of 3D MR images is performed for three neurodegenerative diseases: Multiple Sclerosis, Intrauterine Growth Restriction and Alzheimer's disease. To the best of our knowledge, this is the first Web platform that allows the users to calculate, visualize, analyze and compare the 3DFD from MRI images in the cloud.

IVUS validation of patient coronary artery lumen area obtained from CT images

AIMS

Accurate computed tomography (CT)-based reconstruction of coronary morphometry (diameters, length, bifurcation angles) is important for construction of patient-specific models to aid diagnosis and therapy. The objective of this study is to validate the accuracy of patient coronary artery lumen area obtained from CT images based on intravascular ultrasound (IVUS).

METHODS AND RESULTS

Morphometric data of 5 patient CT scans with 11 arteries from IVUS were reconstructed including the lumen cross sectional area (CSA), diameter and length. The volumetric data from CT images were analyzed at sub-pixel accuracy to obtain accurate vessel center lines and CSA. A new center line extraction approach was used where an initial estimated skeleton in discrete value was obtained using a traditional thinning algorithm. The CSA was determined directly without any circular shape assumptions to provide accurate reconstruction of stenosis. The root-mean-square error (RMSE) for CSA and diameter were 16.2% and 9.5% respectively.

CONCLUSIONS

The image segmentation and CSA extraction algorithm for reconstruction of coronary arteries proved to be accurate for determination of vessel lumen area. This approach provides fundamental morphometric data for patient-specific models to diagnose and treat coronary artery disease.

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.