Publications
Text queries can be conducted by Author, Title, or Keyword.
Three Dimensional Skeleton and centerline generation based on an approximate minimum distance field
Source: Journal of Neurophysiology 2000;80:1522-1532.
Author: Zhou Y, Kaufman A, Toga AW.
Abstract:
We propose an algorithm for generating 18-connected skeletons and centerlines of 3D binary volume data sets. With of an approximate minimum distance field, we express skeletons as a set of clusters with a set of local maximum paths (LMpaths). Each cluster consists of geometrically adjacent voxels with the same local maximum value. Distinct clusters are connected by all possible LMpaths formed by local maximum voxels snaking along, at most, three fixed directions until they meet other clusters. As a 3D extension, we discuss an LMpath traveling on a straight line before and after reaching a saddle point. We generate the shortest centerline connecting two given points with another similar minimum field over skeletal point sets. The results generated by the algorithms on an experimental data set and colon CT and brain MRI data sets demonstrate their efficiency. INTRODUCTION: Due to their compact shape representations, skeletons have been studied for over 30 years in computer vison and pattern recognition. Skeletonization is a powerful tool for intermediate representations for a number of geometric operations on solid models. In this paper, we propose an efficient algorithm for extracting the skeleton and centerline from 3D binary volume data sets. We apply it to image data describing the human colon and brain. IMPLEMENTATION & RESULTS: Three data sets are used to test our algorithm. One set consists of 2 cylinders and a torus. The torus is penetrated vertically by these 2 cylinders. The second set is a CT data set showing a whole human colon. The 3rd set is a 384x256x383 MRI data set representing the human brain. Before the data sets are input, they are preprocessed to generate the inside voxels. The entire implementation includes 5 sequential steps. Our program starts with reading the inside voxels' data files, followed by detecting the boundary voxels. The second step is a voxel layer-by-layer coding beginning with boundary voxels. Then, in the 3rd step, the clusters are generated by first picking up all local maximum voxels and then collecitng all geometrically adjacent voxels as a single cluster. The fourth step generates paths that connect all possible isolated clusters. In this step, before a generated voxel sequence is taken as a path, a check is made to see whether it is a valid path. Once all possible paths are found,the implementation of skeleton generation ends. CONCLUSIONS: We have presented distance transform-based skeleton extraction and centerline generation algorithms. Our skeletons consist of clusters and LMpaths. The advantage for introducing the concept of clusters is that the spatial coherence of the same value point is employed for testing whether the cluster is isolated or connected with other clusters. In order to meet the connectivity of skeletons, the definition of a LMpath is given, and its properties are discussed. Also, basic algorithm and implementation details are given. Theoretical proof and experimental results show the efficieny and usefulness of our algorithm. The algorithm complexity is linear. A simple and less accurate distance approximation mechanism is used in the present algorithm, but fortunately, resampling techniques can be applied at a small voxel size to reduce such errors. We are currently applying these techniques to MRI data sets for the comprehensive generation of medial surfaces of cerebral sulci.
Source: Journal of Neurophysiology 2000;80:1522-1532.
Author: Zhou Y, Kaufman A, Toga AW.
Abstract:
We propose an algorithm for generating 18-connected skeletons and centerlines of 3D binary volume data sets. With of an approximate minimum distance field, we express skeletons as a set of clusters with a set of local maximum paths (LMpaths). Each cluster consists of geometrically adjacent voxels with the same local maximum value. Distinct clusters are connected by all possible LMpaths formed by local maximum voxels snaking along, at most, three fixed directions until they meet other clusters. As a 3D extension, we discuss an LMpath traveling on a straight line before and after reaching a saddle point. We generate the shortest centerline connecting two given points with another similar minimum field over skeletal point sets. The results generated by the algorithms on an experimental data set and colon CT and brain MRI data sets demonstrate their efficiency. INTRODUCTION: Due to their compact shape representations, skeletons have been studied for over 30 years in computer vison and pattern recognition. Skeletonization is a powerful tool for intermediate representations for a number of geometric operations on solid models. In this paper, we propose an efficient algorithm for extracting the skeleton and centerline from 3D binary volume data sets. We apply it to image data describing the human colon and brain. IMPLEMENTATION & RESULTS: Three data sets are used to test our algorithm. One set consists of 2 cylinders and a torus. The torus is penetrated vertically by these 2 cylinders. The second set is a CT data set showing a whole human colon. The 3rd set is a 384x256x383 MRI data set representing the human brain. Before the data sets are input, they are preprocessed to generate the inside voxels. The entire implementation includes 5 sequential steps. Our program starts with reading the inside voxels' data files, followed by detecting the boundary voxels. The second step is a voxel layer-by-layer coding beginning with boundary voxels. Then, in the 3rd step, the clusters are generated by first picking up all local maximum voxels and then collecitng all geometrically adjacent voxels as a single cluster. The fourth step generates paths that connect all possible isolated clusters. In this step, before a generated voxel sequence is taken as a path, a check is made to see whether it is a valid path. Once all possible paths are found,the implementation of skeleton generation ends. CONCLUSIONS: We have presented distance transform-based skeleton extraction and centerline generation algorithms. Our skeletons consist of clusters and LMpaths. The advantage for introducing the concept of clusters is that the spatial coherence of the same value point is employed for testing whether the cluster is isolated or connected with other clusters. In order to meet the connectivity of skeletons, the definition of a LMpath is given, and its properties are discussed. Also, basic algorithm and implementation details are given. Theoretical proof and experimental results show the efficieny and usefulness of our algorithm. The algorithm complexity is linear. A simple and less accurate distance approximation mechanism is used in the present algorithm, but fortunately, resampling techniques can be applied at a small voxel size to reduce such errors. We are currently applying these techniques to MRI data sets for the comprehensive generation of medial surfaces of cerebral sulci.