Advances in Discrete Geometry Applied to the Extraction of Planes and Surfaces from 3D Volumes

O. Figueiredo

Ecole Polytechnique Fédérale de Lausanne, Ph.D. Thesis No 1944, 1999

A wide range of human activities relies on 2D and 3D image processing, synthesis and display. Medicine is for instance one of the fields where imaging has gained particular importance in the recent past because of the strong demand for non-invasive exploration techniques primarily based on tomographic imaging.

With the advent of computers and digital technologies, the vast majority of the images manipulated today in medicine as well as in other disciplines is composed of discrete samples, called pixels (or voxels in the case of volumic images). In order to exploit these images on computers efficiently, several challenges must be met:

• traditional euclidean geometry, based on continuous concepts, appears not to be well-suited to computers and images which are intrisically discrete. Geometric operations based on floating-point arithmetic often lead to inconsistent results and algorithmic instability
• the increasing size of the images, especially three-dimensional, creates an I/O bandwidth problem: images that do not entirely fit in memory must be read from comparatively slow mass storage devices

In this context, a solid theoretical basis is needed to solve the problems introduced by the inadequacy of traditional euclidean geometry with respect to digital images. Discrete geometry is a young and active branch of mathematics that aims at building such a theoretical foundation for a consistent description of digital objects and operations. By nature, the results it establishes are particularly well-suited to computer processing and lead to simple and efficient integer-based algorithms that can be parallelized including at the I/O level, thus bringing increased performance and a solution to the I/O bottleneck problem.

In the first half of this work, we propose new theoretical results and definitions for objects like three-dimensional digital lines, digital spline curves and surface patches as well as algorithms for rigorously solving problems like the intersection of 3D digital lines and planes or the determination of the covering of digital lines and parallelograms by rectangular plane tesselations. In the second half, we emphasize the strengths of this approach by introducing two concrete applications of these results in the field of medical imaging, namely the extraction of planes of arbitrary orientation and of ruled surfaces from very large 3D discrete volumes (several Gigabytes). These algorithms derived from discrete geometry are implemented on parallel architectures consisting of commodity components (standard PCs with multiple SCSI disks connected through Fast Ethernet). They achieve remarkable performance and scalability. Thus, on a configuration consisting of a master and five slave nodes (Dual PentiumPro at 200MHz with 12 disks each), the plane extraction algorithm is able to extract close to 5 slices per second (512x512 pixels, 24 bits color). On a more modest configuration consisting of a Dual-Pentium II at 300MHz with 16 disks, the same algorithm has also proven its stability and performance by serving Internet users and performing approximately 160’000 plane extraction requests from the Visible Human body (13 GB) in 6 months (see The Visible Human Slice and Surface Server).

Download the full paper: PDF 5 MB