Reconstructing occlusal surfaces of teeth using a genetic algorithm with simulated annealing type selection

ABSTRACT

In this paper, we present an application of numerical optimization for surface reconstruction (more precisely: reconstruction of missing parts of a real geometric object represented by volume data) by employing a specially designed genetic algorithm to solve a problem concerning computer-aided design in dentistry. Using a space mapping technique the surface of a given model tooth is fitted by a shape transformation to extrapolate (or reconstruct) the remaining surface of a patient's tooth with occurring damage such as a “drill hole.” Thereby, the genetic algorithm minimizes the error of the approximation by optimizing a set of control points that determine the coefficients for spline functions, which in turn define a space transformation. The fitness function to be minimized by the genetic algorithm is the error between the transformed occlusal surface of the model tooth and the remaining occlusal surface of the damaged (drilled) tooth. The algorithm, that is used, is based upon a proposal by Mahfoud and Goldberg. It uses a simulated-annealing type selection scheme, which is applied sequentially (pair-wise, or one-by-one) to the members in the parent generation and their respective offspring generated by mutation-crossover. We outline a proof of convergence for this algorithm. The algorithm is parallel in regard to computing the fitness-values of creatures.

REFERENCES

• 1: E.H.L. Aarts and P.J.M. van Laarhoven, Simulated Annealing: An Introduction, Statistica Neerlandica 43, 1989, 31-52
• 2: H. Akakie, A new look at the statistical model identification, IEEE Transactions Automatic Control, Vol. AC-19, 6, 1974, 716-723
• 3: Peter J. Bentley, Evolutionary Design by Computers with CDrom, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 4: Lillian Chu , Brian A. Barsky , Stanley A. Klein, Cylindrical Coordinate Representations for Modeling Surfaces of the Cornea and Contact Lenses, Proceedings of the International Conference on Shape Modeling and Applications, p.98, March 01-04, 1999
• 5: F. Duret, J.L. Blouin, and B. Duret, CAD/CAM in dentistry, J. Am. Dent. Assoc., 117(11), 1988, 715-720
• 6: N. S. Goel , R. L. Thompson, Computer simulation of self-organization in biological systems, Macmillan Publishing Co., Inc., Indianapolis, IN, 1988
• 7: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 8: Mark A. Halstead , Brain A. Barsky , Stanley A. Klein , Robert B. Mandell, Reconstructing curved surfaces from specular reflection patterns using spline surface fitting of normals, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.335-342, August 1996 [doi>10.1145/237170.237272]
• 9: T. Hermann, Z. Kovacs, and T. Varady, Special applications in surface fitting, Geometric Modeling: Theory and Practice, W. Strasser, R. Klein and R.Rau (Eds), Springer, 1997, 14-31
• 10: John H. Holland , Keith J. Holyoak , Richard E. Nisbett , Paul R. Thagard, Induction: processes of inference, learning, and discovery, MIT Press, Cambridge, MA, 1986
• 11: D.L. Isaacson and R.W. Madsen, Markov Chains: Theory and Applications, Prentice-Hall, 1961
• 12: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 13: J.R. Koza, Genetic Programming 11, MIT Press, 1994
• 14: J. Loos, G. Greiner, and H.-P. Seidel, A variational approach to progressive lens design, Computer-Aided Design, Vol. 30, No. 8, 1998, 595-602
• 15: J. Loos, Ph. Slusailek, and H.-P. Seidel, Using wavefront tracing for the visualization and optimization of progressive lenses, EUROGRAPHICS'98, Computer Graphics Forum, vol. 17, No. 3, 1998, 255-265
• 16: S.W. Mahfoud and D.E. Goldberg, A Genetic Algorithm for Parallel Simulated Annealing, in: R. Manner, B. Manderick (eds.), Parallel Problem Solving from Nature 2, Elsevier, 1992, 301-310
• 17: Samir W. Mahfoud , David E. Goldberg, Parallel recombinative simulated annealing: a genetic algorithm, Parallel Computing, v.21 n.1, p.1-28, Jan. 1995 [doi>10.1016/0167-8191(94)00071-H]
• 18: Mauro Manela , Nina Thornhill , John A. Campbell, Fitting Spline Functions to Noisy Data Using a Genetic Algorithm, Proceedings of the 5th International Conference on Genetic Algorithms, p.549-556, June 01, 1993
• 19: A. Markus , G. Renner , J. Vancza, Spline Interpolation with Genetic Algorithms, Proceedings of the 1997 International Conference on Shape Modeling and Applications (SMA '97), p.47, March 03-06, 1997
• 20: Karol Myszkowski , Vladimir V. Savchenko , Tosiyasu L. Kunii, Computer Modeling For The Occlusal Surface Of Teeth, Proceedings of the 1996 Conference on Computer Graphics International, p.191, June 24-28, 1996
• 21: A. Pasko, V. Adzhiev, A. Sourin, and V. Savchenko, Function representation in geometric modeling: concepts, implementation and applications, The Visual Computer, 11(6), 1995, 429-446
• 22: V.V. Savchenko, 3-D Geometric Modeller with Haptic Feedback: Engraving Simulation, in proceedings 2 m PHANTOM Users Research Symposium 2000 , M. Harders and S. Huber, (eds.), Zurich, Switzerland, July 6-7, 2000, 35- 42
• 23: V.V. Savchenko and A.A. Pasko, Transformation of functionally defined shapes by extended space mappings, The Visual Computer, 1998,257-270
• 24: Vladimir V. Savchenko , Alexander A. Pasko, Evolutionary Optimization of Functionally Defined Shapes: Case Study of Natural Optical Objects, Proceedings of the International Conference on Computer Graphics, p.20, June 07-11, 1999
• 25: V.V. Savchenko, A.A. Pasko, T.L. Kunii, and A.V. Savchenko, Feature based sculpting of functionally defined 3-D geometric objects, T.S. Chua et al. (eds), Proc. of the MMM'95, Nov. 1995, 341-348
• 26: V.V. Savchenko, A.A. Pasko, O. Okunev and T.L. Kunii, Function representation of solids reconstructed from scattered surface points and countours, Computer Graphics Forum, 14(4), 1995, 181-188
• 27: V. V. Savchenko , A. A. Pasko , A. I. Sourin , T. L. Kunii, Volume Modelling: Representations and Advanced Operations, Proceedings of the Computer Graphics International 1998, p.4, June 22-26, 1998
• 28: Theory of genetic algorithms, Theoretical Computer Science, v.259 n.1-2, p.1-61, May 28, 2001 [doi>10.1016/S0304-3975(00)00406-0]
• 29: Lothar M. Schmitt , Chrystopher L. Nehaniv , Robert H. Fujii, Linear analysis of genetic algorithms, Theoretical Computer Science, v.200 n.1-2, p.101-134, June 28, 1998 [doi>10.1016/S0304-3975(98)00004-8]
• 30: E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, 1981
• 31: Vadim Shapiro, Real functions for representation of rigid solids, Computer Aided Geometric Design, v.11 n.2, p.153-175, April 1994 [doi>10.1016/0167-8396(94)90030-2]
• 32: T. Sohmura and J. Takahashi, Improvement of CAD to produce crown by considering occlusion., Dental Materials Journal, 12(2), 1993, 190-195
• 33: V. A. Vasilenko, Spline functions: theory, algorithms and programs, (in Russian), Nauka (Novosibirsk), 1983
• 34: Michael D. Vose, The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design, Human Factors, Performance, Theory

Keywords:
computer-aided restoration design, constructive solid geometry, genetic algorithm, simulated annealing, space mapping, surface reconstruction, volume modeling