Rony Goldenthal and Michel Bercovier
In this project Optimal Control framework was applied in the field of CAGD on spline curves. In particular to the problem of curve fitting to a set of given points. In order to be able to fit a B-spline curve to a set of points, the parameterization and the knot vector must be determined. The optimal control framework suggests an intelligent way to set these degrees of freedom according to a certain design objective which is modeled as the cost function.
The degrees of freedom available during the parameterization and knot vector setup for spline curve fitting were used to obtain design goals such as to minimization the curvature or the length of the curve - while solving the interpolation or approximation problem. Non-linear minimization of the approximation error is also possible by setting it as the design objective.
The behavior of the cost function with respect to knot vector is known to be highly non-linear, and requires special care. Additionally, trying to optimize complex, non-linear, cost functions makes this behavior even more non-linear. Two approaches where examined the first uses constrained gradient based optimization - in the first article. The second approach used genetic algorithm.The genetic algorithm proved to be more robust and generally produced superior results. It also handled highly non-linear cost functions such as elastic energy of a curve better than the gradient based approach.
Optimizing the curve's shape requires modifying both the knot vector and the parameterization, during these modifications a violation of the Schoenberg-Whitney condition may occur. In such case the interpolation and approximation matrices (the collocation matrix) becomes singular, since the optimization process must continue anyway, this situation is handled in both approaches. Additionally, a visualization of the resulting null space of the collocation matrix is given in the the first paper.
Papers:
Spline
Curve Approximation and Design Over the Knots (PDF, 124k) Computing, Vol. 72, No. 1- 2, pp. 53- 64, April 2004
Spline
Curve Approximation and Design Over the Knots Using Genetic Algorithms (PDF, 122k) Evolutionary Methods for Design, Optimization and
Control / EUROGEN 2003, G. Bugeda, J.- A Désidéri, J. Périaux, M. Schoenauer and G. Winter (Eds.) CIMNE 2003, Barcelona
Presentations:
Eurogen 2003