Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2019 | Book

Introduction Read chapter Read first chapter

Fitting Splines to a Parametric Function

Author: Alvin Penner

Publisher: Springer International Publishing

Book Series : SpringerBriefs in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This Brief investigates the intersections that occur between three different areas of study that normally would not touch each other: ODF, spline theory, and topology.
The Least Squares Orthogonal Distance Fitting (ODF) method has become the standard technique used to develop mathematical models of the physical shapes of objects, due to the fact that it produces a fitted result that is invariant with respect to the size and orientation of the object. It is normally used to produce a single optimum fit to a specific object; this work focuses instead on the issue of whether the fit responds continuously as the shape of the object changes. The theory of splines develops user-friendly ways of manipulating six different splines to fit the shape of a simple family of epiTrochoid curves: two types of Bézier curve, two uniform B-splines, and two Beta-splines. This work will focus on issues that arise when mathematically optimizing the fit. There are typically multiple solutions to the ODF method, and the number of solutions can often change as the object changes shape, so two topological questions immediately arise: are there rules that can be applied concerning the relative number of local minima and saddle points, and are there different mechanisms available by which solutions can either merge and disappear, or cross over each other and interchange roles. The author proposes some simple rules which can be used to determine if a given set of solutions is internally consistent in the sense that it has the appropriate number of each type of solution.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
When creating images for use in vector graphics it is usually necessary to approximate complex shapes with simpler shapes which are more easily rendered. When doing so, one typically uses the least squares fitting error to judge the quality of the conversion. However, if the purpose of the conversion is to produce an animated sequence of images, then one might also be concerned with whether the parameters in the fitted curve are changing smoothly as the original shape changes, so that the resulting animation does not appear to be jerky. To investigate this issue, a family of hypoTrochoid curves was created which can morph continuously from being highly asymmetric, skewed towards one endpoint, to an intermediate shape which is symmetric, and then to a final shape which is skewed towards the other endpoint. The Least Squares Orthogonal Distance Fitting method was used to fit this family of curves using a variety of spline curves of differing complexity. The splines fall into the general categories of being either Bézier, uniform B-spline, or Beta-spline. The performance of the splines was compared with respect to quality of the fit, as well as their response to changes in the shape of the hypoTrochoid.
Alvin Penner
Chapter 2. Least Squares Orthogonal Distance Fitting
Abstract
The Least Squares Orthogonal Distance Fitting method has been motivated by the desire to produce a fitted result that is independent of the location and orientation of the object being fitted. It is typically used to fit various types of spline curves to a set of discrete experimental measurements of an object’s shape, but we will use it instead to fit a smooth parametric function whose shape can be continuously changed. We begin with a definition of residual error, and the corresponding error functional, which is to be optimized. The nature of the optimized solution can be characterized using the eigenvalues of the second order response matrix. The solution method can be decomposed into two nonlinear, nested, subproblems. The first problem is to minimize the distance to the spline curve at any given point. The second problem is to calculate the response to changes in the spline’s parameters, while maintaining the minimization of this distance at all points. The interaction between these two subproblems is described. Numerical convergence issues are outlined.
Alvin Penner
Chapter 3. General Properties of Splines
Abstract
Basic properties of Bézier curves and B-splines are summarized. These are piecewise continuous functions of a given degree, except where they meet at breakpoints. The individual segments are defined in terms of the basis functions which operate on each interval. The level of continuity at breakpoints is determined by a knot vector. The individual segments can be adjusted using control points. Relationships between different representations of a B-spline can be obtained using knot insertion. These relationships can be used to either initialize a complex spline using a simpler type, or to decompose a B-spline into a sequence of Bézier curves which may be more easily drawn on a computer.
Alvin Penner
Chapter 4. ODF Using a Cubic Bézier
Abstract
Construction and manipulation of a cubic Bézier using control points is described. A family of hypoTrochoid curves, to which we will fit the Bézier spline, is defined. The hypoTrochoid curves can range from being highly asymmetric to symmetric, based on their relative curvatures at the endpoints. The ODF calculation is initialized by fitting the curvature exactly at the endpoints. Two classes of ODF solutions are found, one of which is qualitatively similar to the result obtained by fitting the endpoint curvature, while the other class is fundamentally different. Continuity of the rms error as the shape changes can only be obtained by jumping from one class to another. The eigenvalues of the response matrix are used to define more clearly the nature of the solution when these jumps occur.
Alvin Penner
Chapter 5. Topology of Merges/Crossovers
Abstract
The topology of the solutions when two classes of cubic Bézier solutions meet is described. The solutions obtained by fitting curvature at the endpoints do not adequately describe this juncture. A better description is proposed based on the behavior of the center of mass of the object, plus the extrema of the center of mass function. This is shown to be topologically correct, but too restrictive an explanation. A more detailed inspection of the ODF data shows that two types of event can occur: a merge of two solutions, plus a crossover of two other solutions. The merge event is an example of a fold catastrophe, and is associated with a zero in the determinant of the response matrix. The crossover event is much less common, and is associated with a simultaneous zero in the determinants of both this matrix and an augmented matrix containing additional information on how the spline responds to changes in the shape of the hypoTrochoid.
Alvin Penner
Chapter 6. ODF Using a 5-Point B-Spline
Abstract
A 5-point uniform B-spline is fit to a hypoTrochoid shape. The B-spline is initialized using a cubic Bézier. The B-spline basis functions are derived and re-expressed as Bernstein polynomials. It is shown how this relationship is analogous to the relationship between the B-spline control points and the set of cubic Bézier control points that we get when we use knot insertion to decompose the B-spline to a set of Béziers for purposes of rendering them. The ODF results are significantly simpler than the corresponding cubic Bézier ODF results, in that there is only one main solution branch. However, there is still a parameter discontinuity as the hypoTrochoid shape changes. The discontinuity is due to a simple merge of two solutions, which can be diagnosed using the eigenvalues of the second-order response matrix.
Alvin Penner
Chapter 7. ODF Using a 6-Point B-Spline
Abstract
A 6-point uniform B-spline is fit to a hypoTrochoid shape. The B-spline is initialized using a cubic Bézier. The B-spline basis functions are derived and re-expressed as Bernstein polynomials. The ODF results are very similar to the results obtained from the 5-point B-spline, and significantly simpler than the corresponding cubic Bézier ODF results, in that there is only one main solution branch. However, there is still a parameter discontinuity as the hypoTrochoid shape changes. The discontinuity is due to a simple merge of two solutions. In addition, there is a very narrowly avoided crossing in which two solutions almost interchange roles. The eigenvalues of the augmented response matrix are used to help diagnose the avoided crossing.
Alvin Penner
Chapter 8. ODF Using a Quartic Bézier
Abstract
A quartic Bézier is fit to a hypoTrochoid shape. The quartic Bézier is initialized using a cubic Bézier. The ODF results are much more complex than either the cubic Bézier or B-spline results. However, the solution set can be separated into two disjoint sets of solutions, one of which is topologically identical to the cubic Bézier, while the other is of little practical interest due to its’ high rms error. There is evidence of temporary branches which are double saddle points, in addition to the more common single saddle points. A pair of rules is developed to test the internal consistency of the solution set, based on the number of symmetric and anti-symmetric solutions, and on the number and types of saddle points versus local minima. A tentative link with Euler’s characteristic is proposed. Reasons for abnormal termination of solutions are discussed. The minimum rms error is almost uniformly the best of all the splines studied here, but the spline is not supported by standard graphics rendering packages.
Alvin Penner
Chapter 9. ODF Using a Beta2-Spline
Abstract
The concept of second degree geometric continuity is defined. This leads to the introduction of two new degrees of freedom at a breakpoint, called β 1 and β 2. A 5-point B-spline is cast into the form of two Bézier segments with internal constraints on the parameters in order to implement these new degrees of freedom. The β 2 parameter is described in more detail. This parameter breaks \( \mathcal {C}^2 \) continuity and replaces it with \(\mathcal {G}^2\) continuity. We develop a new relationship between β 2 and the symmetric Bézier arm lengths at the splice. Nonlinear coupling between the Bézier parameters is defined. ODF results from fitting this spline to a hypoTrochoid shape are presented and compared to the original 5-point B-spline. The new parameter β 2 is shown to be quite advantageous when fitting a symmetric shape. However, it also introduces a significant amount of complexity to the solution set, included unwanted discontinuities as we switch from one branch to another in order to minimize the error.
Alvin Penner
Chapter 10. ODF Using a Beta1-Spline
Abstract
A 5-point B-spline is cast into the form of two Bézier segments with internal constraints on the parameters. A new parameter, β 1, is introduced. This parameter breaks \( \mathcal {C}^1 \) continuity and replaces it with \( \mathcal {G}^1\) continuity at the breakpoint. It defines an asymmetric change in the Bézier arm lengths at the splice. We develop a relationship between the dimensionless β 1 and the Bézier arm lengths. Nonlinear coupling introduced by β 1 is defined. Discontinuities in the response functions, introduced by β 1, are described and shown to have no net effect. ODF results from fitting this spline to a hypoTrochoid shape are presented and compared to the original 5-point B-spline. The new parameter β 1 is shown to be quite advantageous when fitting an asymmetric shape, but leads to very little improvement for a symmetric shape. It also introduces a considerable amount of complexity to the solution set, including a number of new causes of abnormal termination of the solution due to numerical convergence problems. These are classified by type.
Alvin Penner
Chapter 11. Conclusions
Abstract
The Least Squares Orthogonal Distance Fitting method can be represented as two nested sub-problems: a minimization of the distance from a point on the curve to be fit to the spline curve we are using to perform the fit, and a subsequent minimization with respect to changes in the parameters of the spline. The solutions can be characterized as being either local minima or saddle points of different degree. The classification is based on the eigenvalues of the second-order response matrix. This matrix will contain Hessian terms only when using Beta-splines for the curve fit. The single most difficult aspect of the curve fit is the smooth conversion from an asymmetric shape to a symmetric shape, which invariably causes discontinuities in the parameters of the fit, although not in the rms error. During this transformation process it is typical for solutions to merge and disappear, or to cross over each other, or to narrowly avoid such crossings. These events can be classified according to the behavior of the eigenvalues of the response matrix, as well as the augmented matrix obtained by calculating the response to the parameter that controls the shape of the curve to be fit.
Alvin Penner
Metadata
Title
Fitting Splines to a Parametric Function
Author
Alvin Penner
Copyright Year
2019
Electronic ISBN
978-3-030-12551-6
Print ISBN
978-3-030-12550-9
DOI
https://doi.org/10.1007/978-3-030-12551-6