v
Contents
Preface ......................................................................................................................xi
Authors ...................................................................................................................xv
1. Introduction to Image Compression ...........................................................1
1.1 Need for Coding ....................................................................................1
1.2 Measurement of Quality ...................................................................... 1
1.3 Lossless Compression ...........................................................................2
1.4 Lossy Compression ............................................................................... 2
Bibliography ......................................................................................................4
2. Lossless Image Compression .......................................................................5
2.1 Introduction ...........................................................................................5
2.2 Source Encoders and Decoders ...........................................................6
2.3 Coding Redundancy .............................................................................7
2.4 Interpixel Redundancy .........................................................................8
2.5 Psychovisual Redundancy ...................................................................8
2.6 Image Compression Models ................................................................ 9
2.7 Channel Encoder and Decoder Realization .................................... 11
2.8 Information Theory ............................................................................ 11
2.8.1 Information .............................................................................11
2.9 Classication ........................................................................................12
2.9.1 Compression Ratio .................................................................12
2.9.2 Contents of a Picture .............................................................12
2.9.2.1 Shannon-Fano Coding ...........................................13
2.9.2.2 Huffman Coding .................................................... 14
2.9.2.3 Lempel-Ziv 77 ........................................................17
2.9.2.4 Arithmetic Coding ................................................. 19
2.9.2.5 Run-Length Coding ...............................................19
Bibliography ....................................................................................................21
3. Image Transforms .........................................................................................23
3.1 Introduction .........................................................................................23
3.2 Fundamentals of Image Transforms ................................................25
3.2.1 Orthogonal Functions ...........................................................25
3.2.2 Unitary Matrix .......................................................................26
3.2.3 Unitary Transform ................................................................. 26
3.2.4 One-Dimensional Signals .....................................................27
3.2.5 Two-Dimensional Signals .....................................................27
3.3 Two-Dimensional Image Transforms with a Fixed Basis .............29
vi Contents
3.4 Two-Dimensional Fourier Transforms.............................................30
3.4.1 Separability ............................................................................. 31
3.4.2 Translation ..............................................................................33
3.4.3 Periodicity and Conjugate Properties ................................. 34
3.4.4 Rotation ...................................................................................35
3.4.5 Distributive and Scaling .......................................................36
3.4.6 Average .................................................................................... 36
3.4.7 Convolution and Correlation ...............................................36
3.4.8 Correlation ..............................................................................37
3.5 Two-Dimensional Discrete Cosine Transforms ..............................37
3.5.1 Comparison of Discrete Cosine Transforms and
Discrete Fourier Transforms ................................................39
3.5.2 Application: DCAC Coefcients Based on Multiple
Watermarking Technique .....................................................40
3.5.2.1 Deciding the Step Size ........................................... 41
3.5.2.2 Watermark Embedding .........................................43
3.5.2.3 Watermark Decoding.............................................44
3.5.2.4 Experimentation and Results ...............................44
3.5.2.5 Conclusion and Discussion ...................................46
3.6 The Walsh-Hadamard Transform ....................................................49
3.7 Optimal Transforms ........................................................................... 51
3.8 The Karhunen-Loeve Transform: Two-Dimensional Image
Transform with a Data-Dependent Basis.........................................53
3.8.1 Properties of the Karhunen-Loeve Transform ...................53
3.8.1.1 De-Correlation ........................................................ 53
3.8.1.2 Minimizing the Mean Square Error with a
Limited Basis ...........................................................54
3.8.1.3 Minimizing the Transmission Rate at a
Given Noise ............................................................. 55
3.9 Summary ..............................................................................................56
Bibliography ....................................................................................................57
4. Wavelet-Based Image Compression ..........................................................61
4.1 Introduction ......................................................................................... 61
4.2 The Short-Time Fourier Transform ................................................... 61
4.3 Wavelets ................................................................................................62
4.4 The Continuous Wavelet Transform ................................................63
4.5 Inverse Continuous Wavelet Transform ..........................................65
4.6 The Discrete Wavelet Transform ......................................................65
4.6.1 Wavelet Transform—Multiresolution Analysis ................66
4.6.1.1 Scaling Function ..................................................... 66
4.6.1.2 Wavelet Function ....................................................67
4.6.2 Properties of the Digital Filter .............................................68
4.6.3 Two-Dimensional Wavelet ....................................................69
viiContents
4.7 Wavelet Families .................................................................................71
4.8 Choice of Wavelet Function ............................................................... 71
4.9 Discrete Wavelet Transform–Based Image Compression .............73
4.10 JPEG 2000 Image Compression Standard ........................................75
Questions ........................................................................................................78
Bibliography ....................................................................................................79
5. Image Compression Using Vector Quantization ...................................81
5.1 Introduction ......................................................................................... 81
5.2 Theory of Vector Quantization .........................................................82
5.2.1 Advantages of Vector Quantization .................................... 84
5.2.2 Disadvantages of Vector Quantization ............................... 84
5.3 Design of Vector Quantizers .............................................................85
5.3.1 The Linde-Buzo-Gray Algorithm ........................................ 85
5.3.2 Other Methods of Designing VQ.........................................87
5.4 Tree-Structured Vector Quantizer ....................................................88
5.5 Mean-Removed Vector Quantizer .................................................... 89
5.6 Gain-Shape Vector Quantization ...................................................... 90
5.7 Classied Vector Quantizer ...............................................................91
5.8 Multistage Vector Quantizer .............................................................92
5.9 Adaptive Vector Quantizer ................................................................93
5.10 Hierarchical Vector Quantizer .......................................................... 93
5.11 Predictive Vector Quantizer .............................................................. 94
5.12 Transform Vector Quantizer .............................................................95
5.13 Binary Vector Quantizer .................................................................... 97
5.14 Variable-Rate Vector Quantization ................................................... 98
5.15 Articial Neural Network Approaches to Vector Quantizer
Design ................................................................................................... 98
5.15.1 Introduction to Articial Neural Networks.......................99
5.15.2 Competitive Learning Algorithm .....................................100
5.15.3 Kohonen’s Self-Organizing Feature Maps .......................100
5.16 Concluding Remarks ........................................................................ 102
5.17 MATLAB Programs .......................................................................... 102
References .....................................................................................................108
Bibliography .................................................................................................. 109
6. Digital Video Compression ...................................................................... 111
6.1 Introduction ....................................................................................... 111
6.2 Digital Video Data............................................................................. 112
6.3 Video Compression Techniques ...................................................... 113
6.4 Perceptual Redundancies ................................................................ 113
6.4.1 Temporal Perception ............................................................ 113
6.4.2 Spatial Perception ................................................................ 114
viii Contents
6.5 Exploiting Spatial Redundancies (Intraframe Coding
Technique) .......................................................................................... 114
6.5.1 Predictive Coding ................................................................ 114
6.5.2 Transform Coding ............................................................... 115
6.6 Exploiting Temporal Redundancies (Interframe Coding
Technique) .......................................................................................... 115
6.6.1 Interframe Predictive Coding ............................................ 116
6.6.2 Motion-Compensated Prediction ...................................... 117
6.7 Exploiting Statistical Redundancies ............................................... 118
6.8 Hybrid Video Coding ....................................................................... 118
6.9 Block Matching Motion Estimation ................................................ 119
6.9.1 Block Distortion Measure ................................................... 121
6.9.2 Block Size ..............................................................................122
6.9.3 Search Range ........................................................................123
6.10 Motion Search Algorithms ..............................................................123
6.11 Exhaustive Search ............................................................................. 124
6.12 Two-Dimensional Logarithmic Search Algorithm ...................... 124
6.13 Three-Step Search Algorithm .........................................................125
6.14 Cross-Search Algorithm ...................................................................125
6.15 One-at-a-Time Search Algorithm ....................................................126
6.16 Performance Comparison of Motion Search Algorithms ........... 127
6.17 Video Coding Standards ..................................................................129
6.17.1 H.261 and H.263 ...................................................................130
6.17.2 MPEG-1 Video Coding Standard ....................................... 131
6.17.3 MPEG-2 Video Coding Standard ...................................... 131
6.17.4 MPEG-4 ................................................................................. 131
6.17.5 MPEG-7..................................................................................132
6.17.6 H.264/MPEG-4 Part 10/AVC .............................................. 132
6.17.7 Scalable Video Coding ........................................................ 132
6.17.8 Next-Generation Video Compression—HEVC ................133
References .....................................................................................................134
7. Image Quality Assessment ....................................................................... 137
7.1 Introduction ....................................................................................... 137
7.2 Subjective Image Quality Analysis ................................................138
7.3 Objective Image Quality Assessment ............................................ 139
7.4 Full-Reference Image Quality Assessment ................................... 140
7.4.1 Peak Signal-to-Noise Ratio, Mean Square Error, and
Maximum Difference .......................................................... 140
7.4.2 Why Mean Square Error Is Not Always Correct ............. 141
7.4.3 Spectral Activity Measure and Spatial Frequency
Measure ................................................................................. 142
7.4.4 Normalized Cross-Correlation Measure .......................... 143
7.4.5 Structural Content and Image Fidelity ............................. 143
7.4.6 Mean Structural Similarity Index ..................................... 144

Get Image and Video Compression now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.