Shape reconstruction

Advisor: Jeff Ondich
Meeting time: TTh 10:10-11:55

Final Results

Background

A few years ago, an expert on medical imaging from the Mayo Clinic visited Carleton, and told us a story. One day, a gentleman arrived at Mayo after an unfortunate encounter involving the lower half of his face and the underside of a running lawnmower. It was clear that the man was going to need a new jaw. So they took some tomographic scans--that is, cross-sectional pictures--of his head. Using these images, their software was able to reconstruct the man's current bone structure, and the software operator was able to design a prosthetic jaw fragment of the right size and shape for the missing parts. Once designed, the jaw part was uploaded to a machining tool. By the time the man was prepped and in the operating room, there was a shiny new jaw piece, custom made for his face, ready to be installed.

This story raises many questions (not least of which is how to get your face under a lawnmower), but we will focus on one: how can you use a collection of two-dimensional cross-sectional images to construct a computer model of the corresponding three-dimensional object? Solutions of this shape reconstruction problem can be used to detect the shapes and positions of tumors and blood clots, to determine whether a Caesarian section should be performed, and to map geological and archaelogical structures.

The Project

For this project, you will implement a system that reconstructs 3D shapes from cross sections, and then allows you to view the shape from any direction. Getting this to work with easy images (cross-sections of spheres and cubes, for example) will be the big first job. Gradually, as you study the literature and implement the algorithms you find there, you should find yourselves able to handle more complex images, such as the cross-sections available from the National Library of Medicine's Visible Human Project.

Your tasks will include:

Review the literature on the subject, and choose one or more algorithms to implement. There are several major approaches to this problem, some of which will be more suitable for this project than others
Find and/or generate test data.
Design and implement a graphical user interface suitable for experimenting with the data and your algorithms. The 2003-2004 motion planning project might give you some good ideas on how to approach this.
Implement the algorithms.
Provide a modular framework that makes it easy to add new algorithms and features.
Develop documentation and examples to introduce people to your tools.
Share your work with the world by preparing a web site and a public presentation. This step will also require you to come up with a cool name for your project.

References

Bernard Chazelle, et. al. Application Challenges to Computational Geometry, Advances in Discrete and Computational Geometry, Contemporary Mathematics, 223, AMS, Providence (1999), 407-463. Also available in hypertext form. Note section 4, "Shape Reconstruction," in particular.

H. Fuchs, Z.M. Kedem, and S.P. Uselton. Optimal Surface Reconstruction from Planar Contours, Communications of the ACM 20 (October 1977), 693-702.

Boissonnat, J.-D. Shape reconstruction from planar cross sections, Computer Vision, Graphics and Image Processing 44 (1988), 1-29.

Lorensen, W.E., Cline, H.E. Marching cubes: A high resolution 3D surface construction algorithm, Computer Graphics 21 (1987), 163-169.

Joseph O'Rourke, "Computational Geometry in C," Cambridge University Press, Cambridge, UK, 1993, Chapter 8 (270-316).