Mesh optimization for surface approximation using an efficient coarse-to-fine evolutionary algorithm

Hui Ling Huang, Shinn-Ying Ho*

*Corresponding author for this work

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

The investigated mesh optimization problem C(N, n) for surface approximation, which is NP-hard, is to minimize the global error between a digital surface and its approximating mesh surface by efficiently locating a limited number n of grid points which are a subset of the original N sample points. This paper proposes an efficient coarse-to-fine evolutionary algorithm (CTFEA) with a novel orthogonal array crossover (OAX) for solving the mesh optimization problem. OAX adaptively divides the meshes of parents into a number of parts using a tuning parameter for applying a coarse-to-fine technique. Meshes of children are formed from an intelligent combination of the good parts from their parents rather than the conventional random combination. The better one of two parts in two parents is chosen by evaluating the contribution of the individual parts to the fitness function based on orthogonal experimental design. The coarse-to-fine technique of CTFEA can advantageously solve large mesh optimization problems. Furthermore, CTFEA using an additional inheritance technique can further efficiently locate the grid points in the mesh surface. It is shown empirically that CTFEA outperforms the existing evolutionary algorithm in terms of both approximation quality and convergence speed, especially in solving large mesh optimization problems.

Original languageEnglish
Pages (from-to)1065-1081
Number of pages17
JournalPattern Recognition
Volume36
Issue number5
DOIs
StatePublished - 1 May 2003

Keywords

  • Delaunay triangulation
  • Evolutionary computation
  • Genetic algorithm
  • Mesh optimization
  • Orthogonal array crossover
  • Surface approximation

Fingerprint Dive into the research topics of 'Mesh optimization for surface approximation using an efficient coarse-to-fine evolutionary algorithm'. Together they form a unique fingerprint.

Cite this