Evolutionary structure recovery

As well as using classical optimization techniques, we have been exploring using evolutionary methods for surface fitting and 3D shape recovery [38,39]. The advantages of evolutionary methods are: 1) Euclidean and robust error metrics are easily incorporated into the evaluation criteria and 2) initializing the optimization is not a big problem with the use of multiple ``chromosomes'' as the initial starting points. The main disadvantage is the larger computational cost that arises in parameter space search instead of parametric surface growing in data space, either in 2D [4] or 3D [19], or for triangulated 3D surfaces [27]. However, since reverse engineering a shape is usually a one-time process, the extra cost (e.g. a few hours rather than a few minutes) is not a problem. Simpler parts like that in Figure 1, with about 20 constraints, required about 30 minutes computation on a 200 Mhz Sun workstation, which is probably equivalent to about 5 minutes on a current PC. As the number of parameters grows, the computation time will grow, in part from the additional terms in the evaluation function, but also minima will be harder to find. On the other hand, the minimization always starts with good feature position estimates coming from the feature fitting, so the the parameter vector is always close to the optimal. Hence, progress can be more rapid. Further, this approach is an ``anytime'' algorithm, meaning it can be stopped at any time with a feasible, if suboptimal, solution.

The key concept to the evolutionary approach is search of the shape and position space: rather than initially finding surface and volumetric features directly from the data and then manipulating their positions, our evolutionary approach starts with the individual surface shapes (initialized by coarser segmentation processes) and manipulates their shape descriptions and positions to minimize the fitting error of all data points. In other words, the algorithm searches the space of numerical part descriptions, rather than the space of model-to-data correspondences.

**Figure 11:** Comparison of three fitting algorithms to a partial cylinder. a) Original data, b) algebraic fit, c) Taubin fit, d) Euclidean fit.
$\begin{figure}\begin{tabular}{cc} a) { \epsfxsize = 0.45\textwidth \epsfbox{FI... ...= 0.45\textwidth \epsfbox{FIGURES/real_EF.eps} }\\ \end{tabular} \end{figure}$

Figure 12 shows how the estimates of the radius of the top cylindrical surface of the object shown in Figure 1 stabilizes as a function of number of parameter evaluations. Typical resulting inter-surface orientation error is about 0.05 $^{\rm o}$ degrees.