Geometrically deformed models: a method for extracting closed geometric models form volume data

ABSTRACT

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.

REFERENCES

• 1: J. Serra. Image Analysis and Mathematic~al Morphology Volume !. Academic Press, 1982.
• 2: Stanley R Sternberg, Grayscale morphology, Computer Vision, Graphics, and Image Processing, v.35 n.3, p.333-355, Sept. 1986 [doi>10.1016/0734-189X(86)90004-6]
• 3: Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 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: Wei-Chung Lin , Shiuh-Yung Chen , Chin-Tu Chen, A new surface interpolation technique for reconstructing 3D objects from serial corss-sections, Computer Vision, Graphics, and Image Processing, v.48 n.1, p.124-143, Oct. 1989 [doi>10.1016/0734-189X(89)90107-2]
• 6: H. Fuchs , Z. M. Kedem , S. P. Uselton, Optimal surface reconstruction from planar contours, Communications of the ACM, v.20 n.10, p.693-702, Oct. 1977 [doi>10.1145/359842.359846]
• 7: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 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: James V. Miller , David E. Breen , Michael J. Wozny, Extracting geometric models through constraint minimization, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
• 12: Ruzena Bajcsy , Stane Kovačič, Multiresolution elastic matching, Computer Vision, Graphics, and Image Processing, v.46 n.1, p.1-21, April 1989 [doi>10.1016/S0734-189X(89)80014-3]
• 13: Andrew Witkin , Kurt Fleischer , Alan Barr, Energy constraints on parameterized models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.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: Rafael C. Gonzales , Paul Wintz, Digital image processing (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms; Viewing algorithms

General Terms:
Algorithms

Keywords:
constraint minimization, deformable models, geometric modelling, volume modelling, volume visualization