Data Compression (eBook)

The Complete Reference

David Salomon (Autor)

eBook Download: PDF

2006 | 3. Auflage
919 Seiten
Springer New York (Verlag)
978-0-387-21832-8 (ISBN)

Infos

"Data compression is one of the most important fields and tools in modern computing. From archiving data, to CD ROMs, and from coding theory to image analysis, many facets of modern computing rely upon data compression. Data Compression provides a comprehensive reference for the many different types and methods of compression. Included are a detailed and helpful taxonomy, analysis of most common methods, and discussions on the use and comparative benefits of methods and description of ""how to"" use them. The presentation is organized into the main branches of the field of data compression: run length encoding, statistical methods, dictionary-based methods, image compression, audio compression, and video compression.

Detailed descriptions and explanations of the most well-known and frequently used compression methods are covered in a self-contained fashion, with an accessible style and technical level for specialists and nonspecialists. Topics and features: coverage of video compression, including MPEG-1 and H.261; thorough coverage of wavelets methods, including CWT, DWT, EZW and the new Lifting Scheme technique; complete audio compression; QM coder used in JPEG and JBIG, including new JPEG 200 standard; image transformations and detailed coverage of discrete cosine transform and Haar transform; coverage of EIDAC method for compressing simple images; prefix image compression; ACB and FHM curve compression; geometric compression and edgebreaker technique. Data Compression provides an invaluable reference and guide for all computer scientists, computer engineers, electrical engineers, signal/image processing engineers and other scientists needing a comprehensive compilation for a broad range of compression methods." -- Dieser Text bezieht sich auf eine andere Ausgabe 

---

Data compression is one of the most important fields and tools in modern computing. From archiving data, to CD ROMs, and from coding theory to image analysis, many facets of modern computing rely upon data compression. Data Compression provides a comprehensive reference for the many different types and methods of compression. Included are a detailed and helpful taxonomy, analysis of most common methods, and discussions on the use and comparative benefits of methods and description of "e;how to"e; use them. The presentation is organized into the main branches of the field of data compression: run length encoding, statistical methods, dictionary-based methods, image compression, audio compression, and video compression. Detailed descriptions and explanations of the most well-known and frequently used compression methods are covered in a self-contained fashion, with an accessible style and technical level for specialists and nonspecialists. Topics and features: coverage of video compression, including MPEG-1 and H.261; thorough coverage of wavelets methods, including CWT, DWT, EZW and the new Lifting Scheme technique; complete audio compression; QM coder used in JPEG and JBIG, including new JPEG 200 standard; image transformations and detailed coverage of discrete cosine transform and Haar transform; coverage of EIDAC method for compressing simple images; prefix image compression; ACB and FHM curve compression; geometric compression and edgebreaker technique.Data Compression provides an invaluable reference and guide for all computer scientists, computer engineers, electrical engineers, signal/image processing engineers and other scientists needing a comprehensive compilation for a broad range of compression methods.

Inhalt

Preface to the Third Edition 7
Preface to the Second Edition 11
Preface to the First Edition 15
Contents 17
Introduction 21
1 Basic Techniques 35
1.1 Intuitive Compression 35
1.1.1 Braille 35
1.1.2 Irreversible Text Compression 36
1.1.3 Ad Hoc Text Compression 37
1.2 Run-Length Encoding 40
1.3 RLE Text Compression 41
1.3.1 Relative Encoding 44
1.4 RLE Image Compression 45
1.4.1 Lossy Image Compression 49
1.4.2 Conditional Image RLE 50
1.4.3 The BinHex 4.0 Format 53
1.4.4 BMP Image Files 54
1.5 Move-to-Front Coding 55
1.6 Scalar Quantization 59
2 Statistical Methods 63
2.1 Information Theory Concepts 64
2.1.1 Algorithmic Information Content 68
2.2 Variable-Size Codes 70
2.3 Pre.x Codes 71
2.3.1 The Unary Code 71
2.3.2 Other Pre.x Codes 73
2.4 The Golomb Code 77
2.5 The Kraft-MacMillan Inequality 85
2.6 The Counting Argument 86
2.7 Shannon-Fano Coding 86
2.8 Hu.man Coding 88
2.8.1 Hu.man Decoding 93
2.8.2 Average Code Size 94
2.8.3 Number of Codes 95
2.8.4 Ternary Hu.man Codes 97
2.8.5 Height Of A Hu.man Tree 97
2.8.6 Canonical Hu.man Codes 99
2.9 Adaptive Hu.man Coding 104
2.9.1 Uncompressed Codes 105
2.9.2 Modifying the Tree 105
2.9.3 Counter Over.ow 106
2.9.4 Code Over.ow 108
2.9.5 A Variant 109
2.9.6 Vitter’s Method 110
2.10 MNP5 110
2.10.1 Updating the Table 112
2.11 MNP7 115
2.12 Reliability 116
2.13 Facsimile Compression 119
2.13.1 One-Dimensional Coding 119
2.13.2 Two-Dimensional Coding 123
2.14 Arithmetic Coding 126
2.14.1 Implementation Details 135
2.14.2 Under.ow 138
2.14.3 Final Remarks 138
2.15 Adaptive Arithmetic Coding 140
2.16 The QM Coder 144
2.17 Text Compression 153
2.18 PPM 154
2.18.1 PPM Principles 158
2.18.2 Examples 161
2.18.3 Exclusion 162
2.18.4 Four PPM Variants 163
2.18.5 Implementation Details 164
2.18.6 PPM* 169
2.18.7 PPMZ 171
2.18.8 Fast PPM 174
2.19 Context-Tree Weighting 176
2.19.1 CTW for Text Compression 183
3 Dictionary Methods 185
3.1 String Compression 187
3.2 Simple Dictionary Compression 188
3.3 LZ77 (Sliding Window) 189
3.3.1 A Circular Queue 192
3.4 LZSS 193
3.4.1 De.ciencies 195
3.5 Repetition Times 196
3.6 QIC-122 198
3.7 LZX 200
3.8 File Di.erencing: VCDIFF 203
3.9 LZ78 205
3.10 LZFG 208
3.11 LZRW1 211
3.12 LZRW4 214
3.13 LZW 215
3.13.1 LZW Decoding 216
3.13.2 LZW Dictionary Structure 219
3.13.3 LZW in Practice 224
3.13.4 Di.erencing 225
3.13.5 LZW Variants 225
3.14 LZMW 226
3.15 LZAP 228
3.16 LZY 229
3.17 LZP 231
3.17.1 Example 233
3.17.2 Practical Considerations 235
3.17.3 LZP1 and LZP2 236
3.17.4 LZP3 and LZP4 237
3.18 Repetition Finder 238
3.19 UNIX Compression 241
3.20 GIF Images 242
3.21 The V.42bis Protocol 243
3.22 Various LZ Applications 243
3.23 De.ate: Zip and Gzip 244
3.23.1 The Details 247
3.23.2 Format of Mode-3 Blocks 249
3.23.3 The Hash Table 254
3.23.4 Conclusions 255
3.24 PNG 256
3.25 XML Compression: XMill 260
3.26 EXE Compressors 262
3.27 CRC 263
3.28 Summary 266
3.29 Data Compression Patents 266
3.30 A Uni.cation 268
4 Image Compression 271
4.1 Introduction 273
4.2 Approaches to Image Compression 279
4.2.1 Gray Codes 282
4.2.2 Error Metrics 290
4.3 Intuitive Methods 293
4.3.1 Subsampling 293
4.3.2 Quantization 294
4.4 Image Transforms 294
4.5 Orthogonal Transforms 299
4.5.1 Two-Dimensional Transforms 302
4.5.2 Walsh-Hadamard Transform 303
4.5.3 Haar Transform 304
4.5.4 Karhunen-Lo` eve Transform 307
4.6 The Discrete Cosine Transform 309
4.6.1 Introduction 310
4.6.2 The DCT as a Basis 315
4.6.3 The DCT as a Rotation 325
4.6.4 The Four DCT Types 329
4.6.5 Practical DCT 330
4.6.6 The LLM Method 333
4.6.7 Hardware Implementation of the DCT 335
4.6.8 QR Matrix Decomposition 336
4.6.9 Vector Spaces 338
4.6.10 Rotations in Three Dimensions 341
4.6.11 Discrete Sine Transform 342
4.7 Test Images 345
4.8 JPEG 349
4.8.1 Luminance 351
4.8.2 DCT 354
4.8.3 Quantization 355
4.8.4 Coding 357
4.8.5 Lossless Mode 362
4.8.6 The Compressed File 362
4.8.7 JFIF 363
4.9 JPEG-LS 366
4.9.1 The Encoder 367
4.10 Progressive Image Compression 372
4.10.1 Growth Geometry Coding 377
4.11 JBIG 380
4.11.1 Progressive Compression 382
4.12 JBIG2 389
4.12.1 Generic Region Decoding 393
4.12.2 Symbol Region Decoding 396
4.12.3 Halftone Region Decoding 396
4.12.4 The Overall Decoding Process 398
4.13 Simple Images: EIDAC 400
4.14 Vector Quantization 402
4.15 Adaptive Vector Quantization 410
4.16 Block Matching 415
4.16.1 Implementation Details 418
4.17 Block Truncation Coding 419
4.18 Context-Based Methods 425
4.19 FELICS 428
4.20 Progressive FELICS 431
4.20.1 Subexponential Code 431
4.21 MLP 435
4.21.1 Pixel Sequencing 436
4.21.2 Prediction 436
4.21.3 Error Modeling 437
4.22 Adaptive Golomb 443
4.23 PPPM 444
4.24 CALIC 446
4.24.1 Three Passes 446
4.24.2 Context Quantization 448
4.25 Di.erential Lossless Compression 449
4.26 DPCM 451
4.27 Context-Tree Weighting 456
4.28 Block Decomposition 457
4.29 Binary Tree Predictive Coding 461
4.30 Quadtrees 468
4.30.1 Bintrees 471
4.30.2 Composite and Di.erence Values 472
4.30.3 Progressive Bintree Compression 476
4.30.4 Compression of 479
Tree 479
Structures 479
4.30.5 Pre.x Compression 483
4.31 Quadrisection 485
4.32 Space-Filling Curves 493
4.33 Hilbert Scan and VQ 494
4.34 Finite Automata Methods 497
4.34.1 Weighted Finite Automata 497
4.34.2 Generalized Finite Automata 511
4.35 Iterated Function Systems 514
4.35.1 A.ne Transformations 515
4.35.2 A 517
Rotation 517
4.35.3 Translations 517
4.35.4 IFS De.nition 519
4.35.5 IFS Principles 520
4.35.6 IFS Decoding 525
4.35.7 IFS Encoding 526
4.35.8 IFS for Grayscale Images 527
4.36 Cell Encoding 531
5 Wavelet Methods 533
5.1 Fourier Transform 533
5.2 The Frequency Domain 534
5.3 The Uncertainty Principle 538
5.4 Fourier Image Compression 541
5.5 The CWT and Its Inverse 544
5.6 The Haar Transform 550
5.6.1 Applying the Haar Transform 553
5.6.2 Properties of the Haar Transform 560
5.6.3 A Matrix Approach 564
5.7 Filter Banks 569
5.7.1 Deriving the Filter Coe.cients 576
5.8 The DWT 579
5.9 Multiresolution Decomposition 592
5.10 Various Image Decompositions 593
5.11 The Lifting Scheme 600
5.11.1 The Linear Wavelet Transform 603
5.11.2 Interpolating Subdivision 606
5.11.3 Scaling Functions 609
5.12 The IWT 611
5.13 The Laplacian Pyramid 613
5.14 SPIHT 617
5.14.1 Set Partitioning Sorting Algorithm 621
5.14.2 Spatial Orientation Trees 622
5.14.3 SPIHT Coding 623
5.14.4 Example 626
5.14.5 QTCQ 627
5.15 CREW 629
5.16 EZW 629
5.16.1 Example 632
5.17 DjVu 633
5.18 WSQ, Fingerprint Compression 636
5.19 JPEG 2000 642
6 Video Compression 657
6.1 Analog Video 657
6.1.1 The CRT 658
6.2 Composite and Components Video 663
6.3 Digital Video 665
6.3.1 High-De.nition Television 666
6.4 Video Compression 669
6.4.1 Suboptimal Search Methods 674
6.5 MPEG 681
6.5.1 MPEG-1 Main Components 682
6.5.2 MPEG-1 Video Syntax 692
6.5.3 Motion Compensation 699
6.5.4 Pel Reconstruction 701
6.6 MPEG-4 703
6.7 H.261 708
6.7.1 H.261 Compressed Stream 709
7 Audio Compression 711
7.1 Sound 712
7.2 Digital Audio 715
7.3 The Human Auditory System 718
7.3.1 Conventional Methods 722
7.3.2 Lossy Sound Compression 722
7.4 724
-Law and A-Law Companding 724
7.5 ADPCM Audio Compression 730
7.6 MLP Audio 732
7.7 Speech Compression 737
7.7.1 Properties of Speech 737
7.7.2 Waveform Codecs 740
7.7.3 Source Codecs 740
7.7.4 Hybrid Codecs 744
7.8 Shorten 745
7.9 MPEG-1 Audio Layers 749
7.9.1 Frequency Domain Coding 752
7.9.2 Format of Compressed Data 756
7.9.3 Encoding: Layers I and II 761
7.9.4 Encoding: Layer II 764
7.9.5 Psychoacoustic Models 765
7.9.6 Encoding: Layer III 768
8 Other Methods 775
8.1 The Burrows-Wheeler Method 776
8.1.1 Compressing L 779
8.1.2 Implementation Hints 780
8.2 Symbol Ranking 781
8.3 ACB 785
8.3.1 The Encoder 787
8.3.2 The Decoder 787
8.3.3 A Variation 789
8.3.4 Context Files 791
8.4 Sort-Based Context Similarity 792
8.5 Sparse Strings 797
8.5.1 OR-ing Bits 798
8.5.2 Variable-Size Codes 800
8.5.3 Variable-Size Codes for Base 2 802
8.5.4 Fibonacci-Based Variable-Size Codes 803
8.5.5 Pre.x Compression 804
8.6Word-Based Text Compression 809
8.6.1 Word-Based Adaptive Hu.man Coding 810
8.6.2 Word-Based LZW 811
8.6.3 Word-Based Order-1 Prediction 812
8.7 Textual Image Compression 813
8.8 Dynamic Markov Coding 819
8.8.1 The DMC Algorithm 821
8.8.2 DMC Start and Stop 826
8.9 FHM Curve Compression 828
8.10 Sequitur 831
8.11 Triangle Mesh Compression: Edgebreaker 836
8.12 SCSU: Unicode Compression 847
8.12.1 BOCU-1: Unicode Compression 852
Bibliography 855
Glossary 874
Joining the Data Compression Community 897
Index 899
Colophon 919
More eBooks at www.ciando.com 0

Textauszug

4 Image Compression (p. 251- 252)

The first part of this chapter discusses the basic features and types of digital images and the main approaches to image compression. This is followed by a description of about 30 different compression methods. The author would like to start with the following observations:

1. Why were these particular methods included in the book, while others were ignored? The simple answer is: Because of the documentation available to the author. Image compression methods that are well documented were included. Methods that are kept secret, or whose documentation was not clear to the author, were left out.

2. The treatment of the various methods is uneven. This, again, reflects the documentation available to the author. Some methods have been documented by their developers in great detail, and this is reflected in this chapter. Where no detailed documentation was available for a compression algorithm, only its basic principles are outlined here.

3. There is no attempt to compare the various methods described here. This is because most image compression methods have been designed for a particular type of image, and also because of the practical difficulties of getting all the software and adapting it to run on the same platform.

4. The compression methods described in this chapter are not arranged in any particular order. After much thought and many trials, the author gave up any hope of sorting the compression methods in any reasonable way. Readers looking for any particular method can use the table of contents and the detailed index to easily locate it.

A digital image is a rectangular array of dots, or picture elements, arranged in m rows and n columns. The expression m×n is called the resolution of the image, and the dots are called pixels (except in the cases of fax images and video compression, where they are referred to as pels). The term "resolution" is sometimes also used to indicate the number of pixels per unit length of the image. Thus, dpi stands for dots per inch. For the purpose of image compression it is useful to distinguish the following types of images:

1. A bi-level (or monochromatic) image. This is an image where the pixels can have one of two values, normally referred to as black and white. Each pixel in such an image is represented by one bit, so this is the simplest type of image.

2. A grayscale image. A pixel in such an image can have one of the n values 0 through n . 1, indicating one of 2n shades of gray (or shades of some other color). The value of n is normally compatible with a byte size, i.e., it is 4, 8, 12, 16, 24, or some other convenient multiple of 4 or of 8. The set of the most-significant bits of all the pixels is the most-significant bitplane. Thus, a grayscale image has n bitplanes.


3. A continuous-tone image. This type of image can have many similar colors (or grayscales). When adjacent pixels differ by just one unit, it is hard or even impossible for the eye to distinguish their colors. As a result, such an image may contain areas with colors that seem to vary continuously as the eye moves along the area. A pixel in such an image is represented by either a single large number (in the case of many grayscales) or by three components (in the case of a color image). A continuous-tone image is normally a natural image (natural as opposed to artificial), and is obtained by taking a photograph with a digital camera, or by scanning a photograph or a painting. Figures 4.57 through 4.60 are typical examples of continuous-tone images.

Produkt-Details

• Erscheint lt. Verlag: 9.5.2006
• Sprache: englisch
• Themenwelt: Informatik ► Datenbanken ► Data Warehouse / Data Mining
• ISBN-10: 0-387-21832-7 / 0387218327
• ISBN-13: 978-0-387-21832-8 / 9780387218328