Image and Video Compression

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: DC–AC 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