As connectomic datasets exceed hundreds of terabytes in size, accurate and efficient skeleton generation of the label volumes has evolved into a critical component of the computation pipeline used for analysis, evaluation, visualization, and error correction. We propose a novel topological thinning strategy that uses biological-constraints to produce accurate centerlines from segmented neuronal volumes while still maintaining biologically relevant properties. Current methods are either agnostic to the underlying biology, have non-linear running times as a function of the number of input voxels, or both. First, we eliminate from the input segmentation biologically-infeasible bubbles, pockets of voxels incorrectly labeled within a neuron, to improve segmentation accuracy, allow for more accurate centerlines, and increase processing speed. Next, a Convolutional Neural Network (CNN) detects cell bodies from the input segmentation, allowing us to anchor our skeletons to the somata. Lastly, a synapse-aware topological thinning approach produces expressive skeletons for each neuron with a nearly one-to-one correspondence between endpoints and synapses. We simultaneously estimate geometric properties of neurite width and geodesic distance between synapse and cell body, improving accuracy by 47.5% and 62.8% over baseline methods. We separate the skeletonization process into a series of computation steps, leveraging data-parallel strategies to increase throughput significantly. We demonstrate our results on over 1250 neurons and neuron fragments from three different species, processing over one million voxels per second per CPU with linear scalability.

Thinning is a frequently applied technique for extracting centerlines from 2D binary objects. Parallel thinning algorithms can remove a set of object points simultaneously, while sequential algorithms traverse the boundary of objects, and consider the actually visited single point for possible removal. Two thinning algorithms are called equivalent if they produce the same result for each input picture. This paper presents the very first pair of equivalent 2D sequential and parallel subiteration-based thinning algorithms. These algorithms can be implemented directly on a conventional sequential computer or on a parallel computing device. Both of them preserve topology for (8, 4) pictures sampled on the square grid.

A reduction transforms a binary picture only by changing some black points to white ones, which is referred to as deletion. Sequential reductions traverse the black points of a picture, and consider a single point for possible deletion, while parallel reductions can delete a set of black points simultaneously. Two reductions are called equivalent if they produce the same result for each input picture. A deletion rule is said to be equivalent if it yields a pair of equivalent parallel and sequential reductions. This paper introduces a class of equivalent deletion rules that allows us to establish a new sufficient condition for topology-preserving parallel reductions in arbitrary binary pictures. In addition we present a method of verifying that a deletion rule given by matching templates is equivalent, a necessary and sufficient condition for order-independent deletion rules, and a sufficient criterion for order-independent and translation-invariant parallel subfield-based algorithms.

Matching of corresponding branchpoints between two human airway trees, as well as assigning anatomical names to the segments and branchpoints of the human airway tree, are of significant interest for clinical applications and physiological studies. In the past, these tasks were often performed manually due to the lack of automated algorithms that can tolerate false branches and anatomical variability typical for in vivo trees. In this paper, we present algorithms that perform both matching of branchpoints and anatomical labeling of in vivo trees without any human intervention and within a short computing time. No hand-pruning of false branches is required. The results from the automated methods show a high degree of accuracy when validated against reference data provided by human experts. 92.9% of the verifiable branchpoint matches found by the computer agree with experts' results. For anatomical labeling, 97.1% of the automatically assigned segment labels were found to be correct.

PURPOSE: Demonstration of a technique for three-dimensional (3-D) assessment of tracheal-stenoses, regarding site, length and degree, based on spiral computed tomography (S-CT). PATIENTS AND METHODS: S-CT scanning and automated segmentation of the laryngo-tracheal tract (LTT) was followed by the extraction of the LTT medial axis using a skeletonization algorithm. Orthogonal to the medial axis the LTT 3-D cross-sectional profile was computed and presented as line charts, where degree and length was obtained. Values for both parameters were compared between 36 patients and 18 normal controls separately. Accuracy and precision was derived from 17 phantom studies. RESULTS: Average degree and length of tracheal stenoses was found to be 60.5% and 4.32 cm in patients compared with minor caliber changes of 8.8% and 2.31 cm in normal controls (p << 0.0001). For the phantoms an excellent correlation between the true and computed 3-D cross-sectional profile was found (p << 0.005) and an accuracy for length and degree measurements of 2.14 mm and 2.53% respectively could be determined. The corresponding figures for the precision were found to be 0.92 mm and 2.56%. CONCLUSION: LTT 3-D cross-sectional profiles permit objective, accurate and precise assessment of LTT caliber changes. Minor LTT caliber changes can be observed even in normals and, in case of an otherwise normal S-CT study, can be regarded as artifacts.