Interpolation (779809), страница 6
Текст из файла (страница 6)
Thisis partly due to the numerical problems associated with the inversion of alarge matrix, involved in the time-domain interpolation of a large number ofsamples, Equation (10.58).Spectral–time representation provides a useful form for the interpolation ofa large gap of missing samples. For example, through discrete Fouriertransformation (DFT) and spectral–time representation of a signal, theproblem of interpolation of a gap of N samples in the time domain can beconverted into the problem of interpolation of a gap of one sample, alongthe time, in each of N discrete frequency bins, as explained next.Spectral–Time Representation with STFTA relatively simple and practical method for spectral–time representation ofa signal is the short-time Fourier transform (STFT) method.
To construct a327Model-Based InterpolationBlock lengthMissingsamplesMissingFequencybinsFrequency-TimeSamplesBlockoverlapFigure 10.14 Illustration of segmentation of a signal (with a missing gap) forspectral-time representation.Time (Blocks)Figure 10.15 Spectral-time representation of a signal with a missing gap.two-dimensional STFT from a one-dimensional function of time x(m), theinput signal is segmented into overlapping blocks of N samples, asillustrated in Figure 10.14.
Each block is windowed, prior to discreteFourier transformation, to reduce the spectral leakage due to the effects ofdiscontinuities at the edges of the block. The frequency spectrum of the mthsignal block is given by the discrete Fourier transform asN −1X (k , m) = ∑ w(i ) x(m( N − D) + i )e−j2πikN, k= 0, ..., N–1 (10.71)i =0where X(k,m) is a spectral–time representation with time index m andfrequency index k, N is the number of samples in each block, and D is theblock overlap.
In STFT, it is assumed that the signal frequency compositionis time-invariant within the duration of each block, but it may vary across328Interpolationg(·)x(m)=g(x(m–1), ..., x(m–P))z–1...z –1z –1Figure 10.16 Configuration of a digital oscillator.the blocks. In general, the kth spectral component of a signal has a timevarying character, i.e. it is “born”, evolves for some time, disappears, andthen reappears with a different intensity and a different characteristics.Figure 10.15 illustrates a spectralthtime signal with a missing block ofsamples.
The aim of interpolation is to fill in the signal gap such that, at thebeginning and at the end of the gap, the continuity of both the magnitudeand the phase of each frequency component of the signal is maintained. Formost time-varying signals (such as speech), a low-order polynomialinterpolator of the magnitude and the phase of the DFT components of thesignal, making use of the few adjacent blocks on either side of the gap,would produce satisfactory results.10.3.7 Interpolation Using Adaptive Code BooksIn the LSAR interpolation method, described in Section 10.3.2, the signalsare modelled as the output of an AR model excited by a random input.Given enough samples, the AR coefficients can be estimated withreasonable accuracy.
However, the instantaneous values of the randomexcitation during the periods when the signal is missing cannot berecovered. This leads to a consistent underestimation of the amplitude andthe energy of the interpolated samples. One solution to this problem is touse a zero-input signal model. Zero-input models are feedback oscillatorsystems that produce an output signal without requiring an input.The general form of the equation describing a digital nonlinearoscillator can be expressed asx(m)= g f (x(m − 1), x(m − 2), , x(m − P) )(10.72)The mapping function gf(·) may be a parametric or a non-parametricmapping.
The model in Equation (10.72) can be considered as a nonlinearModel-Based Interpolation329predictor, and the subscript f denotes forward prediction based on the pastsamples.A parametric model of a nonlinear oscillator can be formulated using aVolterra filter model. However, in this section, we consider a nonparametric method for its ease of formulation and stable characteristics.Kubin and Kleijin (1994) have described a non-parametric oscillator basedon a codebook model of the signal process.In this method, each entry in the code book has P+1 samples where the(P+1)th sample is intended as an output. Given P input samples x=[x(m–1),..., x(m–P)], the codebook output is the (P+1)th sample of the vector in thecodebook whose first P samples have a minimum distance from the inputsignal x. For a signal record of length N samples, a codebook of size N–Pvectors can be constructed by dividing the signal into overlapping segmentsof P+1 samples with the successive segments having an overlap of Psamples.
Similarly a backward oscillator can be expressed asxb (m)= g b (x(m + 1), x(m + 2),, x(m + P) )(10.73)As in the case of a forward oscillator, the backward oscillator can bedesigned using a non-parametric method based on an adaptive codebook ofthe signal process. In this case each entry in the code book has P+1 sampleswhere the first sample is intended as an output sample. Given P inputsamples x=[x(m), ..., x(m+P–1)] the codebook output is the first sample ofthe code book vector whose next P samples have a minimum distance fromthe input signal x.For interpolation of M missing samples, the ouputs of the forward andbackward nonlinear oscillators may be combined asM −1− m m xˆ ( k + m )xˆ ( k + m ) = b xˆ f ( k + m ) + M −1 M −1 (10.74).where it is assumed that the missing samples start at k.10.3.8 Interpolation Through Signal SubstitutionAudio signals often have a time-varying but quasi-periodic repetitivestructure.
Therefore most acoustic events in a signal record reoccur withsome variations. This observation forms the basis for interpolation through330Interpolationpattern matching, where a missing segment of a signal is substituted by thebest match from a signal record. Consider a relatively long signal record ofN samples, with a gap of M missing samples at its centre. A section of thesignal with the gap in the middle can be used to search for the best-matchsegment in the record. The missing samples are then substituted by thecorresponding section of the best-match signal. This interpolation method isparticularly useful when the length of the missing signal segment is large.For a given class of signals, we may be able to construct a library ofpatterns for use in waveform substitution, Bogner (1989).10.4 SummaryInterpolators, in their various forms, are used in most signal processingapplications.
The obvious example is the estimation of a sequence ofmissing samples. However, the use of an interpolator covers a much widerrange of applications, from low-bit-rate speech coding to patternrecognition and decision making systems. We started this chapter with astudy of the ideal interpolation of a band-limited signal, and its applicationsin digital-to-analog conversion and in multirate signal processing.
In thischapter, various interpolation methods were categorised and studied in twodifferent sections: one on polynomial interpolation, which is the moretraditional numerical computing approach, and the other on statisticalinterpolation, which is the digital signal processing approach.The general form of the polynomial interpolator was formulated and itsspecial forms, Lagrange, Newton, Hermite and cubic spline interpolatorswere considered.
The polynomial methods are not equipped to makeoptimal use of the predictive and statistical structures of the signal, and areimpractical for interpolation of a relatively large number of samples. Anumber of useful statistical interpolators were studied. These includemaximum a posteriori interpolation, least square error AR interpolation,frequency-time interpolation, and an adaptive code book interpolator.Model-based interpolation method based on an autoregressive model issatisfactory for most audio applications so long as the length of the missingsamples is not to large. For interpolation of a relatively large number ofsamples the time–frequency interpolation method and the adaptive codebook method are more suitable.Bibliography331BibliographyBOGNER R.E.
and LI T. (1989) Pattern Search Prediction of Speech. Proc.IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP89, pp. 180–183, Glasgow.COHEN L. (1989) Time-Frequency Distributions-A review. Proc. IEEE,77(7), pp. 941–81.CROCHIERE R.E. and RABINER L.R. (1981) Interpolation and Decimation ofDigital Signals-A Tutorial review.
Proc. IEEE, 69, pp. 300–331,March.GODSILL S.J. (1993) The Restoration of Degraded Audio Signals. Ph.D.Thesis, Cambridge University.GODSILL S.J. and Rayner P.J.W. (1993) Frequency domain interpolation ofsampled signals. IEEE Int. Conf., Speech and Signal Processing,ICASSP-93, Minneapolis.JANSSEN A.J., VELDHUIS R. and VRIES L.B (1984) Adaptive Interpolation ofDiscrete-Time Signals That Can Be Modelled as AutoregressiveProcesses.
IEEE Trans. Acoustics, Speech and Signal Processing,ASSP-34, 2, pp. 317–330 June.KAY S.M. ( 1983) Some Results in Linear Interpolation Theory. IEEETrans. Acoustics Speech and Signal Processing, ASSP-31, pp. 746–749, June.KAY S.M. (1988) Modern Spectral Estimation: Theory and Application.Prentice- Hall, Englewood Cliffs, NJ.KOLMOGROV A.N. (1939) Sur l’ Interpolation et Extrapolation des SuitesStationaires, Comptes Rendus de l’Academie des Sciences.
208, pp.2043–2045.KUBIN G. and KLEIJIN W.B. (1994) Time-Scale Modification of SpeechBased On A Nonlinear Oscillator Model. Proc. IEEE Int. Conf., Speechand Signal Processing, ICASSP-94, pp. I453–I456, Adelaide.LOCHART G.B. and GOODMAN D.J. (1986) Reconstruction of MissingSpeech Packets by Waveform Substitution. Signal Processing 3:Theories and Applications, pp. 357-360.MARKS R.J. (1983) Restoring Lost Samples From An Over-Sampled BandLimited Signal. IEEE Trans. Acoustics, Speech and Signal Processing,ASSP-31, 2. pp. 752–755, June.MARKS R.J. (1991) Introduction to Shannon Sampling and InterpolationTheory.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
