“Geometrically deformed models: a method for extracting closed geometric models form volume data” by Miller, Breen, Lorensen, O’Bara and Wozny

We propose a new approach to the problem of generating a simple topologically-closed geometric model from a point-sampled volume data set. We call such a model a Geometrically Deformed Model or GDM. A GDM is created by placing a ‘seed’ model in the volume data set. The model is then deformed by a relaxation process that minimizes a set of constraints that provides a measure of how well the model fits the features in the data. Constraints are associated with each vertex in the model that control local deformation, interaction between the model and the data set, and the shape and topology of the model. Once generated, a GDM can be used for visualization, shape recognition, geometric measurements, or subjected to a series of geometric operations. This technique is of special importance because of the advent of nondestructive sensing equipment (CT, MRI) that generates point samples of true three-dimensional objects.

1. J. Serra. Image Analysis and Mathematic~al Morphology Volume !. Academic Press, 1982.]]
2. S,R, Sternberg. Gray.scale morphology. Computer ~Tsion. Graphits, and Image Processing, (35):333-355, 1986.]]
3. R.A Drebin, L. Carpenter, and P, Hanrahan. Volume rendering. Computer Graphics, 22(4):65-74, 1988.]]
4. E, Artzy, G. Frieder, and G. Herman. The theory, design, implementation, and evaluation of a three-dimensional surface detection algorithm. Computer Graphits and Image Prot’essing, 15″ 1-24, 1980.]]
5. W.C. Lin, S.Y. Chen, and C.T. Chen. A new surface interpolation technique for reconstructing 3d objects from serial cross-sections. Computer Vision, Graphie’s. and Image Prot’essing, 48:124-143, 1989.]]
6. H. Fuchs, Kedem Z.M., and Uselton S.P. Optimal surface reconstruction from planar contours. Comm. ACM, 20( 10):693-702, 1977.]]
7. W.E. Lorensen and H.E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. Computer Graphit’s, 21(4):163-169, 1987.]]
8. H.E. Cline, W.E. Lorensen, S. Ludke, Crawford C.R., and B.C. Teeter. Two algorithms for the three-dimensional reconstruction of tomograms. Medit’al Physics, 15(3):320- 327, 1988.]]
9. M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. International Journal of Computer Vision, pages 321-331, 1988.]]
10. D. Terzopoulus, A. Witkin, and M. Kass. Symmetry-seeking models and 3d object reconstruction. International Journal of Computer Vision, 1(3):211-221, October 1987.]]
11. J,V. Miller, D.E. Breen, and M.J. Wozny. Extracting geometric models through constraint minimization. Visualization ’90 Proceedings, pages 74-82, 1990.]]
12. R. Bajcsy and S. Kova~,i6. Multiresolution elastic matching. Computer Vision, Graphics and Image Processing, (46):1- 21, 1989.]]
13. A. Witkin, K. Fleischer, and A. Barr. Energy constraints on parameterized models. Computer Graphics, 21(4):225-232, July 1987.]]
14. D.E. Breen. Choreographing goal-oriented motion using cost functions. State-of-the-Art in Computer Animation (Computer Animation ’89 Conference Proceedings), pages 141-151. eds N. Magnenat-Thalmann and D. Thalmann (Springer-Verlag, Tokyo, June 1989).]]
15. D. Terzopoulos and K. Fieischer. Deformable models. The Visual Computer, 4:306–311, 1988.]]
16. R.C. Gonzalez and P. Wintz. Digital Image Processing. Addison-Wesley, 1987.]]
17. J.F. Canny. Finding edges and lines in images. Masters thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, June 1983.]]
18. S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.]]
19. M.J. Wennington. Spherical Models. Cambridge Univerity Press.]]
20. J.V. Miller. On gdm’s: Geometrically deformed models for the extraction of closed shapes from volume data. Masters thesis, Rensselaer Polytechnic Institute, Troy, New York, December 1990.]]