Advisor: Jeff Ondich
Meeting time: TTh 10:10-11:55
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.
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:
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).