Interpolation (779809), страница 3
Текст из файла (страница 3)
In general the jth order divided difference can be formulated interms of the divided differences of order j–1, in an order-update equationgiven asd j −1 (t i − j +1 , t i )−d j −1 (t i − j , t i −1 )d j (t i − j , t i ) =(10.30)ti − ti− jNote that a1 = d1 (t 0 , t1 ) , a 2 = d 2 (t 0 , t 2 ) and a3 = d 3 (t 0 , t 3 ) , and ingeneral the Newton polynomial coefficients are obtained from the divideddifferences using the relationai = d i (t 0 , t i )(10.31)A main advantage of the Newton polynomial is its computationalefficiency, in that a polynomial of order N–1 can be easily extended to ahigher-order polynomial of order N.
This is a useful property in theselection of the best polynomial order for a given set of data.10.2.3 Hermite Polynomial InterpolationHermite polynomials are formulated to fit not only to the signal samples,but also to the derivatives of the signal as well. Suppose the data consists ofN+1 samples and assume that all the derivatives up to the Mth orderderivative are available. Let the data set, i.e.
the signal samples and the(M )(t i ), i = 0, , N ] . Therederivatives, be denoted as [ x(t i ), x ′(t i ), x ′′(t i ),, x310Interpolationare altogether K=(N+1)(M+1) data points and a polynomial of order K–1can be fitted to the data asp(t ) = a0 +a1t +a 2 t 2 + a3t 3 + + a K −1t K −1(10.32)To obtain the polynomial coefficients, we substitute the given samples inthe polynomial and its M derivatives as====(M )p(t i ) =p (t i )p ′(t i )p ′′(t i )x(t i )x ′(t i )x ′′(t i )(10.33)x(M )(t i ),i =0,1,..., NIn all, there are K=(M+1)(N+1) equations in (10.33), and these can be usedto calculate the coefficients of the polynomial Equation (10.32). In theory,the constraint that the polynomial must also fit the derivatives should resultin a better interpolating polynomial that passes through the sampled pointsand is also consistent with the known underlying dynamics (i.e.
thederivatives) of the curve. However, even for moderate values of N and M,the size of Equation (10.33) becomes too large for most practical purposes.10.2.4 Cubic Spline InterpolationA polynomial interpolator of order N is constrained to pass through N+1known samples, and can have N–1 maxima and minima. In general, theinterpolation error increases rapidly with the increasing polynomial order,as the interpolating curve has to wiggle through the N+1 samples. When alarge number of samples are to be fitted with a smooth curve, it may bebetter to divide the signal into a number of smaller intervals, and to fit a loworder interpolating polynomial to each small interval.
Care must be taken toensure that the polynomial curves are continuous at the endpoints of eachinterval. In cubic spline interpolation, a cubic polynomial is fitted to eachinterval between two samples. A cubic polynomial has the formp(t ) = a0 + a1 t + a 2 t 2 + a3 t 3(10.34)311Polynomial Interpolationx(t)ti–1Ti–1tiTiti+1tFigure 10.6 Illustration of cubic spline interpolation.A cubic polynomial has four coefficients, and needs four conditions for thedetermination of a unique set of coefficients. For each interval, twoconditions are set by the samples at the endpoints of the interval.
Twofurther conditions are met by the constraints that the first derivatives of thepolynomial should be continuous across each of the two endpoints.Consider an interval t i ≤ t ≤ t i +1 of length Ti=ti+1–ti as shown in Figure 10.6.Using a local coordinate τ=t–ti , the cubic polynomial becomesp (τ ) = a 0 + a1τ + a 2 τ 2 + a3τ 3(10.35)At τ=0, we obtain the first coefficient a0 asa 0 = p(τ = 0) = x(t i )(10.36)The second derivative of p(τ) is given byp ′′(τ )= 2a 2 +6a3τ(10.37)Evaluation of the second derivative at τ =0 (i.e.
t=ti) gives the coefficient a2312Interpolationa2 =pi′′(τ = 0) pi′′=22(10.38)Similarly, evaluating the second derivative at the point ti+1 (i.e. τ=Ti ) yieldsthe fourth coefficientp ′′ − p ′′a3 = i +1 i(10.39)6TiNow to obtain the coefficient a1, we evaluate p(τ) at τ=Ti:p (τ =Ti ) = a 0 + a1Ti + a 2 Ti 2 + a3 Ti 3 = x(t i +1 )(10.40)and substitute a0, a2 and a3 from Equations (10.36), (10.38) and (10.39) in(10.40) to obtaina1 =x(t i +1 ) − x(t i )Ti−pi′′+1 + 2 pi′′6Ti(10.41)The cubic polynomial can now be written as x(t )− x(t i ) pi′′+1 + 2 pi′′ pi′′ 2 pi′′+1 − pi′′ 3τ (10.42)p (τ ) = x(t i ) + i +1Ti τ + τ +−Ti626TiTo determine the coefficients of the polynomial in Equation (10.42), weneed the second derivatives and pi′′+1 .
These are obtained from theconstraint that the first derivatives of the curves at the endpoints of eachinterval must be continuous. From Equation (10.42), the first derivatives ofp(τ) evaluated at the endpoints ti and ti+1 arep′i ′pi′ = p ′(τ = 0) = −Ti1[ pi′′+1 + 2 pi′′]+ [x(ti +1 ) − x(t i )]Ti6(10.43)Ti1[2 pi′′+1 + pi′′ ]+ [x(t i +1 ) − x(t i )]Ti6(10.44)pi′+1 = p ′(τ =Ti ) =313Model-Based InterpolationSimilarly, for the preceding interval, ti–1<t<ti, the first derivative of thecubic spline curve evaluated at τ=ti is given bypi′ = p ′(τ = t i ) =Ti −11[2 pi′′+ pi′′−1 ]+[x(ti ) − x(ti −1 )]Ti −16(10.45)For continuity of the first derivative at ti, p′i at the end of the interval (ti–1,ti) must be equal to the p′i at the start of the interval (ti ,ti+1).
Equating theright-hand sides of Equations (10.43) and (10.45) and repeating thisexercise yields 1 111Ti −1 p i′′−1 + 2 (Ti −1 + Ti ) p i′′ + Ti p i′′+1 = 6 x (t i −1 ) − + x(t i ) + x (t i +1 )Ti Ti −1 Ti Ti −1i = 1, 2, . . ., N–1(10.46)In Equation (10.46), there are N–1 equations in N+1 unknowns pi′′ . For aunique solution we need to specify the second derivatives at the points t0and tN. This can be done in two ways: (a) setting the second derivatives atthe endpoints t0 and tN (i.e. p0′′ and p ′N′ ), to zero, or (b) extrapolating thederivatives from the inside data.p′0′p N′ ′10.3 Model-Based InterpolationThe statistical signal processing approach to interpolation of a sequence oflost samples is based on the utilisation of a predictive and/or a probabilisticmodel of the signal. In this section, we study the maximum a posterioriinterpolation, an autoregressive model-based interpolation, a frequency–time interpolation method, and interpolation through searching a signalrecord for the best replacement.Figures 10.7 and 10.8 illustrate the problem of interpolation of a sequenceof lost samples.
It is assumed that we have a signal record of N samples,and that within this record a segment of M samples, starting at time k,xUk={x(k), x(k+1), ..., x(k+M–1)} are missing. The objective is to make anoptimal estimate of the missing segment xUk, using the remaining N–ksamples xKn and a model of the signal process. An N-sample signal vector314InterpolationLostsamplesInput signal ySignal estimator(Interpolator)Restored signal x^θParameterestimatorFigure 10.7 Illustration of a model-based iterative signal interpolation system.x Ukx Kn1x Kn2??…?timeP samples beforeM missingsamplesP samples afterFigure 10.8 A signal with M missing samples and N–M known samples.
On eachside of the missing segment, P samples are used to interpolate the segment.x, composed of M unknown samples and N–M known samples, can bewritten as x Kn1 x Kn1 0 x = xU = 0 + xUk = K x Kn + U xUk x Kn2 x Kn2 0 (10.47)where the vector xKn=[xKn1 xKn2]T is composed of the known samples, andthe vector xUk is composed of the unknown samples, as illustrated in Figure10.8. The matrices K and U in Equation (10.47) are rearrangement matricesthat assemble the vector x from xKn and xUk.315Model-Based Interpolation10.3.1 Maximum A Posteriori InterpolationThe posterior pdf of an unknown signal segment xUk given a number ofneighbouring samples xKn can be expressed using Bayes’ rule asf X ( x Kn , x Uk )f X ( x Kn )f ( x = K x Kn + U x Uk )= Xf X ( x Kn )f X ( x Uk x Kn ) =(10.48)In Equation (10.48), for a given sequence of samples xKn, fX(xKn) is aconstant. Therefore the estimate that maximises the posterior pdf, i.e.
theMAP estimate, is given byMAP= arg max f X ( K x Kn + U x Uk )xˆ Ukx Uk(10.49)Example 10.2 MAP interpolation of a Gaussian signal. Assume that anobservation signal x=KxKn+UxUk, from a zero-mean Gaussian process, iscomposed of a sequence of M missing samples xUk and N–M knownneighbouring samples as in Equation (10.47). The pdf of the signal x isgiven byf X ( x) =1(2π )N /2Σ xx1/ 21−1 exp − x T Σ xxx 2(10.50)where Σxx is the covariance matrix of the Gaussian vector process x.Substitution of Equation (10.50) in Equation (10.48) yields the conditionalpdf of the unknown signal xUk given a number of samples xKn:f X ( xUk x Kn ) =11×1/ 2N/2f X ( xKn ) (2π )Σ xx 1T−1exp − (K xKn +U xUk ) Σ xx(K xKn +U xUk ) 2(10.51)316Interpolationx(t)tFigure 10.9 Illustration of MAP interpolation of a segment of 20 samples.The MAP signal estimate, obtained by setting the derivative of the loglikelihood function ln fX(x|xKn) of Equation (10.51) with respect to xUk tozero, is given by(−1x Uk = − U T Σ xxU)−1U T Σ xx−1 K x Kn(10.52)An example of MAP interpolation is shown in Figure 10.9.10.3.2 Least Square Error Autoregressive InterpolationIn this section, we describe interpolation based on an autoregressive (AR)model of the signal process.
The term “autoregressive model” is analternative terminology for the linear predictive models considered inChapter 7. In this section, the terms “linear predictive model” and“autoregressive model” are used interchangeably. The AR interpolationalgorithm is a two-stage process: in the first stage, the AR modelcoefficients are estimated from the incomplete signal, and in the secondstage the estimates of the model coefficients are used to interpolate themissing samples. For high-quality interpolation, the estimation algorithmshould utilise all the correlation structures of the signal process, includingperiodic or pitch period structures. In Section 10.3.4, the AR interpolationmethod is extended to include pitch–period correlations.317Model-Based Interpolation10.3.3 Interpolation Based on a Short-Term Prediction ModelAn autoregressive (AR), or linear predictive, signal x(m) is described asPx ( m ) = ∑ a k x ( m − k ) +e ( m )(10.53)k =1where x(m) is the AR signal, ak are the model coefficients and e(m) is a zeromean excitation signal.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
