Wavelets and Subband Coding
Martin Vetterli
Jelena Kovaˇcevi ́c
Preface
The aim of the book is to present this unified view of wavelets and subband coding. It will be done from a signal processing perspective, but with sufficient background material such that people without signal processing knowledge will find it useful as well.
1 Wavelets, Filter Banks and Multiresolution Signal Processing
The modulation by complex exponentials in the Fourier transform is replaced by a scaling operation, and the notion of scale replaces that of frequency. In computer vision, multiresolution techniques have been used for various prob- lems, ranging from motion estimation to object recognition
2 Fundamentals of Signal Decompositions
2.1 Notations
Euler's formula states that for any real number x
exp(j * x) = cos(x) + j * sin(x)
When x=pi, Euler's formula evaluates to
exp( j * pi ) + 1 = 0
This formula can be interpreted as saying that the function exp( j*φ ) is a unit complex number, i.e., it traces out the unit circle in the complex plane as φ ranges through the real numbers.
Often we deal with functions of a continuous variable, and a related sequence indexed by an integer (typically, the latter is a sampled version of the former).
We use parentheses around a continuous variable and brackets around a discrete one
x[n] = f(nT)
2.2 HilbertSpaces
2.4 Fourier Theory and Sampling
2.4.2 FourierTransform
The Fourier transform satisfies a number of properties,
2.4.3 Fourier Series
2.4.4 Dirac Function, Impulse Trains and Poisson Sum Formula
The Dirac function, which is a generalized function or distribution, is defined as a limit of rectangular functions. For example, if
The Fourier transform of δ(t − t0) is
Next, we introduce the train of Dirac functions spaced T > 0 apart,
It can be shown that
2.4.5 Sampling
2.6 Time-Frequency Representations
2.6.1 Frequency, Scale and Resolution
The analysis functions for the wavelet transform will be defined as
Thus, large a’s (a ≫ 1) correspond to long basis functions in time, and will identify long-term trends in the signal to be analyzed.
. 68
................ 76
2.6.2 UncertaintyPrinciple ...................... 79
2.6.3 Short-TimeFourierTransform ................. 81
2.6.4 WaveletTransform........................ 83
2.6.5 BlockTransforms......................... 83
2.6.6 Wigner-VilleDistribution .................... 84
2.A BoundedLinearOperatorsonHilbertSpaces . . . . . . . . . . . . . 85
2.B ParametrizationofUnitaryMatrices .................. 86
2.B.1 GivensRotations......................... 87
2.B.2 HouseholderBuildingBlocks .................. 88
2.C ConvergenceandRegularityofFunctions . . . . . . . . . . . . . . . 89
2.C.1 Convergence ........................... 89
2.C.2 Regularity............................. 90
Discrete-Time Bases and Filter Banks 97
3.1 SeriesExpansionsofDiscrete-TimeSignals . . . . . . . . . . . . . . 100
3.1.1 Discrete-TimeFourierSeries ..................101
3.1.2 Haar Expansion of Discrete-Time Signals . . . . . . . . . . . 104
3.1.3 SincExpansionofDiscrete-TimeSignals. . . . . . . . . . . . 109
3.1.4 Discussion.............................110
3.2 Two-ChannelFilterBanks........................112
3.2.1 AnalysisofFilterBanks.....................113
3.2.2 ResultsonFilterBanks .....................123
3.2.3 Analysis and Design of Orthogonal FIR Filter Banks . . . . . 128
3.2.4 LinearPhaseFIRFilterBanks .................139
3.2.5 FilterBankswithIIRFilters ..................145
3.3 Tree-StructuredFilterBanks ......................148
3.3.1 Octave-Band Filter Bank and Discrete-Time Wavelet Series
3.3.2 Discrete-Time Wavelet Series and Its Properties . . . . . .
3.3.3 Multiresolution Interpretation of Octave-Band Filter Banks
3.3.4 General Tree-Structured Filter Banks and Wavelet Packets
. 150 . 154 . 158 . 161
3.4 MultichannelFilterBanks........................163
3.4.1 BlockandLappedOrthogonalTransforms. . . . . . . . . . . 163
3.4.2 AnalysisofMultichannelFilterBanks . . . . . . . . . . . . . 167
3.4.3 ModulatedFilterBanks.....................173
3.5 PyramidsandOvercompleteExpansions . . . . . . . . . . . . . . . . 179
3.5.1 OversampledFilterBanks....................179
3.5.2 PyramidScheme.........................181
3.5.3 Overlap-Save/Add Convolution and Filter Bank Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
3.6 MultidimensionalFilterBanks .....................184
3.6.1 Analysis of Multidimensional Filter Banks . . . . . . . . . . . 185
3.6.2 Synthesis of Multidimensional Filter Banks . . . . . . . . . . 189
3.7 Transmultiplexers and Adaptive Filtering in Subbands . . . . . . . . 192
3.7.1 Synthesis of Signals and Transmultiplexers . . . . . . . . . . 192
3.7.2 AdaptiveFilteringinSubbands.................195
3.A LosslessSystems.............................196
3.A.1 Two-ChannelFactorizations...................197
3.A.2 MultichannelFactorizations...................198
3.B Sampling in Multiple Dimensions and Multirate Operations . . . . . 202
4 Series Expansions Using Wavelets and Modulated Bases 209
4.1 DefinitionoftheProblem ........................211
4.1.1 Series Expansions of Continuous-Time Signals . . . . . . . . . 211
4.1.2 Time and Frequency Resolution of Expansions . . . . . . . . 214
4.1.3 HaarExpansion .........................216
4.1.4 Discussion.............................221
4.2 MultiresolutionConceptandAnalysis .................222
4.2.1 Axiomatic Definition of Multiresolution Analysis . . . . . . . 223
4.2.2 ConstructionoftheWavelet...................226
4.2.3 ExamplesofMultiresolutionAnalyses . . . . . . . . . . . . . 228
4.3 Construction of Wavelets Using Fourier Techniques . . . . . . . . . . 232
4.3.1 Meyer’sWavelet .........................233
4.3.2 Wavelet Bases for Piecewise Polynomial Spaces . . . . . . . . 238
4.4 Wavelets Derived from Iterated Filter Banks and Regularity . . . . . 246
4.4.1 HaarandSincCasesRevisited .................247
4.4.2 IteratedFilterBanks.......................252
4.4.3 Regularity.............................257
4.4.4 Daubechies’ Family of Regular Filters and Wavelets . . . . . 267
4.5 WaveletSeriesandItsProperties....................270
4.5.1 DefinitionandProperties ....................271
4.5.2 PropertiesofBasisFunctions..................276
4.5.3 Computation of the Wavelet Series and Mallat’s Algorithm . 280
4.6 GeneralizationsinOneDimension ...................282
4.6.1 BiorthogonalWavelets......................282
4.6.2 Recursive Filter Banks and Wavelets with Exponential Decay 288
4.6.3 Multichannel Filter Banks and Wavelet Packets . . . . . . . . 289
4.7 MultidimensionalWavelets .......................293
5
4.7.1 Multiresolution Analysis and Two-Scale Equation . .
4.7.2 Construction of Wavelets Using Iterated Filter Banks
4.7.3 Generalization of Haar Basis to Multiple Dimensions .
4.7.4 DesignofMultidimensionalWavelets..............298
4.8 LocalCosineBases............................300
4.8.1 RectangularWindow.......................302
4.8.2 SmoothWindow .........................303
4.8.3 GeneralWindow .........................304
4.A ProofofTheorem4.5...........................304
Continuous Wavelet and Short-Time Fourier Transforms and Frames 311
5.1 ContinuousWaveletTransform .....................313
5.1.1 AnalysisandSynthesis......................313
5.1.2 Properties.............................316
5.1.3 MorletWavelet..........................324
5.2 ContinuousShort-TimeFourierTransform. . . . . . . . . . . . . . . 325
5.2.1 Properties.............................325
5.2.2 Examples .............................327
5.3 Frames of Wavelet and Short-Time Fourier Transforms . . . . . . . . 328
5.3.1 Discretization of Continuous-Time Wavelet and Short-Time Fourier Transforms . . . . . . . . . . . . . . . . . . . . . . . . 329
5.3.2 ReconstructioninFrames ....................332
5.3.3 FramesofWaveletsandSTFT .................337
5.3.4 Remarks..............................342
6 Algorithms and Complexity 347
6.1 ClassicResults ..............................348
6.1.1 FastConvolution.........................348
6.1.2 FastFourierTransformComputation. . . . . . . . . . . . . . 352
6.1.3 Complexity of Multirate Discrete-Time Signal Processing . . 355
6.2 ComplexityofDiscreteBasesComputation . . . . . . . . . . . . . . 360
6.2.1 Two-ChannelFilterBanks....................360
6.2.2 Filter Bank Trees and Discrete-Time Wavelet Transforms . . 363
6.2.3 ParallelandModulatedFilterBanks . . . . . . . . . . . . . . 366
6.2.4 MultidimensionalFilterBanks .................368
6.3 ComplexityofWaveletSeriesComputation . . . . . . . . . . . . . . 369
6.3.1 ExpansionintoWaveletBases..................369
6.3.2 IteratedFilters..........................370
6.4 ComplexityofOvercompleteExpansions . . . . . . . . . . . . . . . . 371
7 Signal Compression and Subband Coding 383
7.1 Compression Systems Based on Linear Transforms . . . . . . . . . . 385
7.1.1 LinearTransformations .....................386
7.1.2 Quantization ...........................390
7.1.3 EntropyCoding .........................403
7.1.4 Discussion.............................407
7.2 SpeechandAudioCompression.....................407
7.2.1 SpeechCompression .......................407
7.2.2 High-QualityAudioCompression................408
7.2.3 Examples .............................412
7.3 ImageCompression............................414
7.3.1 Transform and Lapped Transform Coding of Images . . . . . 415
7.3.2 PyramidCodingofImages ...................421
7.3.3 SubbandandWaveletCodingofImages . . . . . . . . . . . . 425
7.3.4 Advanced Methods in Subband and Wavelet Compression . . 438
7.4 VideoCompression............................446
7.4.1 KeyProblemsinVideoCompression . . . . . . . . . . . . . . 447
7.4.2 Motion-CompensatedVideoCoding . . . . . . . . . . . . . . 453
7.4.3 PyramidCodingofVideo ....................454
7.4.4 Subband Decompositions for Video Representation and Com- pression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
Example: MPEG Video Compression Standard . . . . . . . . 463
7.4.5 JointSource-ChannelCoding ......................464
7.5.1 DigitalBroadcast.........................465
7.5.2 PacketVideo ...........................467
StatisticalSignalProcessing.......................467
留言