Last update, Dec. 22, 1998

Publications on Virtual Endoscopy :

• Automated flight path planning for virtual endoscopy, D.S. Paik et al., 1998.

BibTeX references.

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.

Page created & maintained by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu