• Kaufman, A. et al. :
• Penalized-Distance Volumetric Skeleton Algorithm, 2001.
• Distance-Field Based Skeletons for Virtual Navigation, 2001
  
• 3D skeleton & centerline generation based on an approximate minimum distance field, 1998.
• Paik, D.S. et al. :
• Automated flight path planning for virtual endoscopy, 1998.

Distance-Field Based Skeletons for Virtual Navigation

Abstract

Three-Dimensional skeleton and centerline generation based on an approximate minimum distance field

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.

Key words: 3D skeleton and centerline · Volume visualization · Navigation · Distance transformation

Based on 3D-DT:

1. Find local extrema clusters (in distance value)
2. Link these cluster by a sort of 3D ridge following:
   • uphill climbing from saddle points, defined as local minima among skeletal points;
   • "uphill climbing" is implemented as finding sets of local maximum paths (LMpaths).

The particular 3D-DT used is very coarse: city-block-like version in 3D (based on 6 direct ngbs. only: faces of voxels).

In this paper, a novel technique for rapid and automatic computation of flight paths for guiding virtual endoscopic exploration of 3D medical images is described. While manually planning flight paths is a tedious and time consuming task, our algorithm is automated and fast. Our method for positioning the virtual camera is based on the medial axis transform but is much more computationally efficient. By iteratively correcting a path toward the medial axis, the necessity of evaluating simple point criteria during morphological thinning is eliminated. The virtual camera is also oriented in a stable viewing direction, avoiding sudden twists and turns. We tested our algorithm on volumetric data sets of eight colons, one aorta and one bronchial tree. The algorithm computed the flight paths in several minutes per volume on an inexpensive workstation with minimal computation time added for multiple paths through branching structures (10%-13% per extra path). The results of our algorithm are smooth, centralized paths that aid in the task of navigation in virtual endoscopic exploration of three-dimensional medical images.

Aorta & virtual camera pose along the computed path.	One shot of the virtual angiography sequence produced.

Previous approaches

Key framing :

• The user specifies manually the pose of a small subset of the total number of frames to be rendered. Interpolating curves are fitted to generate a continuous path and set of frames.
  • Manual task very time consuming, prone to human errors.

Distance mapping :

• Comes from robotic path planning. A goal voxel being selected, a distance transform ("map" in the text) is computed from it within the medium of interest. A path is determined by following the gradient of the DT.
  • Tends to "hug the wall of the organ" (not central).
  • Requires large amount of memeory to store the DT.

Iterative adjustment towards a central axis :

• Starting frame (2D slice) is chosen. Subsequent frames are determined based on a 2D center of mass (in a plane perpendicular to the previously determined position).
  • Only approximates the 3D medial axis loci.
  • Does not guarantee that the path will stay within the lumen of the organ.
  • No simple way of dealing with branching structure.

Thinning techniques to determine a medial axis :

• Iterative peeling off of voxels to determine a central 3D axis structure (skeleton).
  • Computationally expensive.
  • Connectivity criteria is variable ("complex" in the text).

Proposed Path Planning Algorithm

Connectivity of voxels :

• 26-ngb for identified voxels (part of region/tissues of interest).
• 6-ngb for nonidentified voxels (background).
• Surface voxels: identified voxels which have 6-ngb connectivity with nonidentified voxels.

Segmentation :

• Region growing algorithm [Cline90].
• Hand corrections

Initial Path Selection :

• User specifies Start and End points: initial path members.
• A surface-based path (2D) is then determined between these 2 points.

Euclidean Distance Mapping (EDM):

• You start by assigning the start voxel a distance of 0. Then you do a breadth-first search marking each voxel as the current voxel's distance plus the Euclidean distance from the current voxel to the voxel in consideration. Since voxels may be visited several times, you only mark the distance if it is less than the current distance (or hasn't been marked yet at all).

Thinning (based on EDM) :

• Step 1 of each iteration: Parallel "removal" (become nonidentified) of all surface voxels (except path members) from the structure of interest.
• Step 2 of each iteration: EDM computation:
  • For the union of previous path voxels and actual surface voxels.
• Step 3 of each iteration: Determine a new voxel path through the EDM.
  • The new path follows the new eroded surface whenever possible.
  • The new path traverses voxels of the old path only where erosion has disconnected components of the surface.
• The previous 3 steps of thinning are repeated until the structure of interest is thinned away and only the centralized path remains.

Path sampling :

• The voxel path needs to be smoothed to void nonuiform camera velocity.

Virtual Camera Orientation :

• Compute a viewing direction (look vector) that points toward corners for the path ahead.
  • Determine visibility by ray tracing
• Sequence of look vectors are smoothed.
• Camera roll (twist) is minimized frame-to-frame (through projection in a picture plane).

Bronchus & virtual camera pose along the computed path.	One shot of the virtual bronchoscopy sequence produced.

Colon & virtual camera pose along the computed path.	One shot of the virtual colonoscopy sequence produced.