THE 3D MARCHING LINES ALGORITHM

This paper presents a general purpose tool designed to extract charact eristic curves from 3D images. Our algorithm, called the Marching Line s, is inspired by isointensity techniques, such as the Marching Cubes. Marching Lines extracts, with subpixel accuracy, the 3D lines corresp onding to the intersection of two isosurfaces in a 3D grid. The algori thm ensures that each reconstructed curve is formed of a connected set of segments, is closed if the curve is entirely contained in the grid , does not intersect itself, and is oriented. The main idea is to defi ne isosurfaces as interfaces (f greater than or equal to 0, f < 0) ins tead of implicit equation solutions (f = 0). The singularities are sol ved with an offset technique. Results are presented for synthetic data and for 3D medical image applications. (C) 1996 Academic Press, Inc.