Building surfaces of evolution: The Weaving Wall

VS: a surface-based system for topological analysis, quantization and visualization of voxel data

VS is a simple system consisting of several techniques for various volumetric problems. Based on the marching cubes algorithm, it operates with one space sweep through the voxels and extracts all topological information: detection of all isosurfaces, partitioning the data into connected components on the basis of surface connectivity, and association of surfaces with any internal surfaces to arbitrary levels of nesting. VS extends Baker's "Weaving Wall" method by associating topological cavities with their outer surface, and by using efficient data structures for the voxel traversal and for the connected component detection. Its runtime, on average, is only about 2% more than the speeded-up marching cubes algorithm. VS operates on the original voxels without using the contour tree required by other approaches. Using linear-time preprocessing, VS constructs a data structure which can be utilized for any isovalue or interval of isovalues. An accurate estimate of each component's volume is based on the volume enclosed by the outer surface, minus the volume of any internal cavities. VS enables noise reduction by eliminating components (and cavities) with a small volume. Different components can be rendered with different visual attributes, and cutaway views by arbitrary cut-planes are displayed as if the objects were solid, without adding any new surface patches to match the intersection.

Marching cube algorithm: review and trilinear interpolation adaptation for image-based dosimetric models

Current internal organ dose assessment methodologies utilize three-dimensional (3D) medical images of the body to model organ shapes and tissue interfaces. These models are coupled to computer programs that measure radionuclide energy deposition or chord-length distributions directly within these images. Previous studies have shown that the rectangular shape of image voxels generates voxel effects that alter the outcome of these calculations. To minimize voxel effects, the present study proposes to use the Marching Cube (MC) algorithm to generate isosurfaces delineating tissue interfaces from the gray-level images. First, a review of the different techniques surrounding the MC algorithm is presented. Next, an adaptation of the algorithm is proposed in which a trilinear interpolation of the gray levels is used to generate a hyperboloid surface within the MCs. This new technique is shown to solve the classic ambiguity problem of the MC algorithm and also to reduce the data size inherent to the triangulated surface. It also provides a simple algorithm to accurately measure distances within the image. The technique is then tested with a mathematical model of trabecular bone. The trilinear interpolation method is shown to remove voxel effects and to produce reliable chord-length distributions across image regions. The technique is thus recommended for use with digital medical images needed for internal radiation transport simulations. The current study is performed for a single isosurface that separates two media within the same image, but it is proposed that the technique can be extended to multiple isosurfaces that delineate several organs or organ regions within 3D tomographic voxels of human anatomy.

Growing-cube isosurface extraction algorithm for medical volume data

In medical applications, three-dimensional volume data such as CT and MRI are gathered from medical-imaging devices. Marching cube (MC) algorithm is a common routine to extract isosurfaces from volume data. The MC algorithm generates the massive number of triangles to represent an isosurface. It is difficult to render this amount of triangles in real-time on general workstations. In this paper, we present a growing-cube algorithm to reduce the number of triangles generated by the MC algorithm. Growing-cube algorithm uses a surface tracker to avoid exhaustive searching isosurfaces cell-by-cell and, therefore, it saves computation time. During surface tracking, the growing-cube algorithm adaptively merges surfaces contained in the tracked cells to reduce the number of triangles. Surfaces are merged as long as the error is within user-specified error thresholds. Therefore, the proposed algorithm can generate a variable resolution of isosurfaces according to these error parameters.

A novel and efficient implementation of the marching cubes algorithm

In this paper, a novel and efficient implementation of the marching cubes (MC) algorithm is presented for the reconstruction of anatomical structures from real three-dimensional medical data. The proposed approach is based on a generic rule, able to triangulate all 15 standard cube configurations used in the classical MC algorithm as well as additional cases presented in the literature. The proposed implementation of the MC algorithm can handle the Type A 'hole problem' which occurs when at least one cube face has an intersection point in each of its four edges. Theoretical and experimental results demonstrate the ability of the new implementation to reproduce standard MC results, resolving Type A 'hole problem'. Finally, the proposed implementation was applied to real medical date to reconstruct anatomical structures. The output of the proposed technique is in WWW compliant format.

A shape representation for computer vision based on differential topology

We describe a shape representation for use in computer vision, after a brief review of shape representation and object recognition in general. Our shape representation is based on graph structures derived from level sets whose characteristics are understood from differential topology, particularly singularity theory. This leads to a representation which is both stable and whose changes under deformation are simple. The latter allows smoothing in the representation domain ('symbolic smoothing'), which in turn can be used for coarse-to-fine strategies, or as a discrete analog of scale space. Essentially the same representation applies to an object embedded in 3-dimensional space as to one in the plane, and likewise for a 3D object and its silhouette. We suggest how this can be used for recognition.