Adaptive reconstruction of pipe-shaped human organs from 3D ultrasonic volume

In this paper, we introduce an adaptive scheme for reconstructing pipe-shaped human organs from the volume data acquired by 3D ultrasonic devices. No other methods but the contour-based scheme was used in the process of reconstructing the volume data into a 3D polygonal surface. In the first step, the algorithm extracts contours from the sampled slices of the volume data using the modified radial gradient method, in which the points are sampled on the boundary of the region of interest by radiating rays and connected through making use of the chain code algorithm. The contours are represented as the context-free grammar, and their parsing trees are traversed during the reconstruction. The generated polygonal surface is refined as the contours are being refined at the casting of the new rays between the existing rays to sample new points and to modify the contours according to these newly derived points. An adaptive scheme is achieved in casting the rays adaptively on the slices. The proposed algorithm is to be applied in reconstructing the pipe-shaped human organs, such as arteries or blood vessels, to a polygonal surface. In this paper, we present an innovative tiling algorithm that reconstructs pipe-shaped human organ from 3D ultrasonic datasets. A set of contours on slices through the ultrasonic datasets is extracted using a modified radial gradient method, and our algorithm tiles these to make a polygonal surface. The tiling is performed by traversing a set of parsing trees which represent the contours in a context-free grammar. This makes our algorithm more efficient than previous algorithms that reconstruct surfaces from a set of contours. The first step of the algorithm is to determine a contour on each slice of the 3D ultrasonic dataset. After removing unwanted artifacts from the slice by applying several noise-removing operators, the centroid pixel of region of interest on the slice is designated. A radial gradient method casts a set of rays from the centroid pixel to the boundary of the slice and computes the intersection points between the rays and the boundary cells of the object so as to determine the contours. The second step uses context-free grammar that represents the contours. Each edge of a contour can be classified into six categories according to its relation with the rays cast from the centroid pixel, and the contour can then be represented by a string in a context-free grammar whose terminal symbols are the six types of the edges. A polygonal surface between two contours is constructed by traversing the parsing trees of the contours and determining the corresponding edges. The third step is to refine the smooth surface constructed in the second step by casting more rays. Additional rays refine the contour by decomposing the edges on the contour and convert leaf node of the parsing tree to the root of a new sub-tree whose leaf nodes denote the newly created edges. Our algorithm was tested on a phantom object and an artery from the neck. Results show that the performance of the algorithm and the quality of the resulting surface are better than those of existing algorithms. We have implemented a navigation facility that allows users to investigate the pipe-shaped human organs interactively.