IntroductionIn the numerical analysis, curve interpolationis a method of approximating the value of a function that can satisfy adiscrete set of non-noisy data points. Another method that is quite similar tointerpolation but mostly applied to noisy data points is the curve approximation.
In interpolation, exact fit to the data is obtained while in approximating, asmooth function is constructed that approximates the data or in other word, thecurve constructed will pass through not all data points. There are numerous typesof interpolation method that have been introduced such as Bezier curveinterpolation, B-spline curve interpolation and Lagrange curve interpolation. Thispaper will focus on Bezier curve interpolation method because they are easy tocompute and can be stitched together to represent any shape desired. It is alsofrequently used in graphics animation. One way of achieving Bezier curveinterpolation is by making each data points as end points of Bezier curve ofdesired degree and put control point (number of control points depends ondegree desired) in between each data point.
Another way to achieve this is byusing parameterization method. There are a lot of parameterization methods thathad been proposed and we review several types of parameterization method. Themain focus of this paper is to discuss parameterization on road curve toconstruct on interpolating curve that pass through data points. LITERATURE REVIEWBézier curve has been originally developedby Pierre Bézier and Paul de Casteljau as a result of continuous researches onimproving curve fitting process. Since then, there are researchers who proposednew interpolating curve based on the blending function of Bézier curve. Forexample, Abbas et al.
(2014) hasproposed Timmer’s Parametric Cubic which better represent the circular arccompared to rational cubic Bézier. Another interpolating curve arise in thisfield is proposed by Catmull et al.(1974) which is the Catmull-Rom Curve that manages to interpolate all of itscontrol points. Anotherway of curve fitting is by using the parameterization method which also hadbeen studied by researchers of related field. Parameterization method do notdeal with blending function but instead, it deal with the way the control pointis defined with respect to the node. Ahlberg et al. (1967) had proposed the chordalparameterization in which length of line segment between each node is takeninto parameterization.
After that, Lee (1989) had proposed centripetal parameterizationmethod that is claimed to produce a much better curve compared to the previousmethods introduced by Ahlberg et al..Yuksel (2010) had studied Lee’s approach and shows that for cubic Catmull-Romcurves, centripetal parameterization ensures that the curves do not form cuspsor self-intersections.
Geometric method by Juhász et al. (2007) is one of recent parameterization method introducedfocusing on geometric aspect of parameter alteration.The curve fitting process is useful in reconstructingan image. Ibrahim et al.
(2016) has used Rational Cubic Ball curve togenerate Arabic Fonts. To estimate design speed from curvature value, Misro et al. (2015) fit a road map in BalikPulau, Malaysia using Piecewise Cubic Bézier Curve.
To interpolate data points, a piecewiseBézier curve will choose the data point as its end points as Bézier curve doesnot interpolate its control points. In this paper, we propose Bézier curveinterpolation with uniform, chordal and centripetal parameterization. PARAMETERIZATION TECHNIQUE In this section, wereview the general concept of Bezier curve. The general Bezier curve is definedby control points and equals (1) where are the Bernstein polynomials or Bernsteinbasis functions of degree n defined by and is the Binomial coefficient; A parameterization method has beenexplained by Juhász etal.
(2007). Consider a set of points obtained as a structured data points. It is assumed that no two consecutive points are the same. We wantto consider the problem of passing a planar Bezier curve through these datapoints such that (2) where are certain chosen parameters values calledinterpolating nodes. Equation (2) can be expanded as follows; Since Bezier curve always interpolate theend points, and then and . Hence, the system ofequations above can be reduced into; So, we only need to solve the system ofequation for control points .
The system ofequation above can be converted into matrix form; (3) where and . The system has unique solution if thedeterminant of matrix is non-zero. Otherwise, matrix is non-invertible. Otherwise, can be obtained bysolving FIGURE1: Different kind of Bezier curve that passthrough the ordered data points is generated depend on how interpolation node, is defined; uniform parameterization (Top), chordalparameterization (Middle) and centripetal (Bottom) parameterization. The dottedline represents the control polygon for the curve. Basically, instead of choosing itmanually, we are actually generating the control points based on theinformation from .
Then, by substitutingthese generated control point into the defining equation for Bezier curve in(1), we can produce a curve that lies exactly on each data points. This methodof generating Bezier curve from data points has been discussed a lot byresearchers and can be found in many comprehensive books of the field. Figure 1 shows the effect of differentparameterization on curve generated. In this figure, different construction of ‘s will affect thebehavior of the curve.
We still cannot guarantee that the curve constructed tobehave in a specific way as desired by designer. Lee (1989) believed that thisproblem may be caused by the parameterization of the data points or in otherwords, how is defined. It is alsobelieved that the greater number of input points chosen, the higher the tendency for the curveto become perturbed especially near the end points. This problem will beillustrated in the next section. This paper will discuss about several methodsof parameterization that have been invented by previous researchers. A typical way to choose parameter valueis to set and recursively let for some chosen interval lengths .
This simplest choiceis the uniform parameterization defined by , so that the values are uniformly spaced. This approach does notproduce a satisfactory result because the nodes have nothing to do with thedistribution of the data. We can see from Figure 2 (left) that the curve pathmay overshoot or wander far off after pass in through a control point beforeeventually goes to the next control point. An improvement has been made by Ahlberg et al.
(1967) which is the chordalparameterization in which is taken to be the length of the line segment(‘chord’) , i.e, where is the Euclidean norm in Rd. The reason behind this parameterization is that the chord lengthmay serve as a good indicator to approximate the arc length of the curvebetween and . As shown in Figure 2 (left), chordalparameterization does better job in minimizing overshooting that sometimesoccur in uniform parameterization when there is a lot of variation in thedistance between the points . It was discoveredthat the uniform and chordal parameterization are the special cases and of the more general parameterization with acting as blending parameter.
The choice was termed by Lee (1989) as the centripetalparameterization. Figure 2 (left) shows the differencebetween each parameterization in the curve generated. Previous researchers pointout that centripetal parameterization produced better curves compared touniform and chordal parameterization (Yuksel, 2010). However Figure 1 showsthat chordal parameterization produce more visually-pleasing result compared tothe other two parameterization method discussed in this paper. This shows that thebest choice of parameterization method may depend on the distribution of datapoints itself. overshoot overshoot (a) (b) FIGURE2 (a): Quadratic Bezier curve through 3 points; with Uniform (Top), Chordal (Middle) and Centripetal parameterization (Bottom). (b): Map of a part of PLUS Expresswayat Kepala Batas obtained from Google Maps with 14 randomly chosen data points.
ROAD MAP INTERPOLATION We have applied the parameterizationmethods discussed above on road curve fitting by using a portion of road PLUSExpressway at Kepala Batas. 14 locations on the road is marked as data pointsas shown in Figure 2. In the selection of data points, we do not have anyspecific pattern or guidance as this reflects the behavior of designers in reallife. The results are shown in Figure 3. The curves appear to be perturbedespecially at both end of the curve and it occurred for all parameterizationdiscussed above. The problem is called as Runge’s Phenomenon and it occurs ifparameterization is done with too many data points (Epperson, 1987). It showsthat for parameterization, increasing the degree of curve does not alwaysimprove the interpolation. It is still possible to generate goodcurve of higher degree but it require tedious effort to manually adjust thedata point so that it fits with the node (See Figure 4).
It is because nodes have a global effect on the shape of Beziercurve generated. By changing a node value assigned to a data point or bychanging the data point itself, the shape of the curve could change entirely asit will generate a different set of control point in Equation (3). CONCLUSIONParameterization method may not producesatisfying result if there are too many control points. More researches can be done to investigate thecorrelation between the number of control points and best curve fitting. Oneway to interpolate such high amount of control point is by making several piecewiseBezier curve of optimum degree that is connected at each end.
In this case,continuity properties must be satisfied to produce smooth curve at the each endpoints which result in the first approach in interpolation as discussedearlier. Parameterization method has been very helpful in improving the waycurve interpolation is done. The fitting technique used in this paper can beused as an alternative for such applications such as the design speed estimationby Misro et al..