A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data. The basic properties of the algorithm are discussed and demonstrated by examples. Quite general distortion measures and long blocklengths are allowed, as exemplified by the design of parameter vector quantizers of ten-dimensional vectors arising in Linear Predictive Coded (LPC) speech compression with a complicated distortion measure arising in LPC analysis that does not depend only on the error vector. <s> BIB001 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> A review of vector quantization techniques used for encoding digital images is presented. First, the concept of vector quantization is introduced, then its application to digital images is explained. Spatial, predictive, transform, hybrid, binary, and subband vector quantizers are reviewed. The emphasis is on the usefulness of the vector quantization when it is combined with conventional image coding techniques, or when it is used in different domains. > <s> BIB002 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> 1 Introduction.- 1.1 Signals, Coding, and Compression.- 1.2 Optimality.- 1.3 How to Use this Book.- 1.4 Related Reading.- I Basic Tools.- 2 Random Processes and Linear Systems.- 2.1 Introduction.- 2.2 Probability.- 2.3 Random Variables and Vectors.- 2.4 Random Processes.- 2.5 Expectation.- 2.6 Linear Systems.- 2.7 Stationary and Ergodic Properties.- 2.8 Useful Processes.- 2.9 Problems.- 3 Sampling.- 3.1 Introduction.- 3.2 Periodic Sampling.- 3.3 Noise in Sampling.- 3.4 Practical Sampling Schemes.- 3.5 Sampling Jitter.- 3.6 Multidimensional Sampling.- 3.7 Problems.- 4 Linear Prediction.- 4.1 Introduction.- 4.2 Elementary Estimation Theory.- 4.3 Finite-Memory Linear Prediction.- 4.4 Forward and Backward Prediction.- 4.5 The Levinson-Durbin Algorithm.- 4.6 Linear Predictor Design from Empirical Data.- 4.7 Minimum Delay Property.- 4.8 Predictability and Determinism.- 4.9 Infinite Memory Linear Prediction.- 4.10 Simulation of Random Processes.- 4.11 Problems.- II Scalar Coding.- 5 Scalar Quantization I.- 5.1 Introduction.- 5.2 Structure of a Quantizer.- 5.3 Measuring Quantizer Performance.- 5.4 The Uniform Quantizer.- 5.5 Nonuniform Quantization and Companding.- 5.6 High Resolution: General Case.- 5.7 Problems.- 6 Scalar Quantization II.- 6.1 Introduction.- 6.2 Conditions for Optimality.- 6.3 High Resolution Optimal Companding.- 6.4 Quantizer Design Algorithms.- 6.5 Implementation.- 6.6 Problems.- 7 Predictive Quantization.- 7.1 Introduction.- 7.2 Difference Quantization.- 7.3 Closed-Loop Predictive Quantization.- 7.4 Delta Modulation.- 7.5 Problems.- 8 Bit Allocation and Transform Coding.- 8.1 Introduction.- 8.2 The Problem of Bit Allocation.- 8.3 Optimal Bit Allocation Results.- 8.4 Integer Constrained Allocation Techniques.- 8.5 Transform Coding.- 8.6 Karhunen-Loeve Transform.- 8.7 Performance Gain of Transform Coding.- 8.8 Other Transforms.- 8.9 Sub-band Coding.- 8.10 Problems.- 9 Entropy Coding.- 9.1 Introduction.- 9.2 Variable-Length Scalar Noiseless Coding.- 9.3 Prefix Codes.- 9.4 Huffman Coding.- 9.5 Vector Entropy Coding.- 9.6 Arithmetic Coding.- 9.7 Universal and Adaptive Entropy Coding.- 9.8 Ziv-Lempel Coding.- 9.9 Quantization and Entropy Coding.- 9.10 Problems.- III Vector Coding.- 10 Vector Quantization I.- 10.1 Introduction.- 10.2 Structural Properties and Characterization.- 10.3 Measuring Vector Quantizer Performance.- 10.4 Nearest Neighbor Quantizers.- 10.5 Lattice Vector Quantizers.- 10.6 High Resolution Distortion Approximations.- 10.7 Problems.- 11 Vector Quantization II.- 11.1 Introduction.- 11.2 Optimality Conditions for VQ.- 11.3 Vector Quantizer Design.- 11.4 Design Examples.- 11.5 Problems.- 12 Constrained Vector Quantization.- 12.1 Introduction.- 12.2 Complexity and Storage Limitations.- 12.3 Structurally Constrained VQ.- 12.4 Tree-Structured VQ.- 12.5 Classified VQ.- 12.6 Transform VQ.- 12.7 Product Code Techniques.- 12.8 Partitioned VQ.- 12.9 Mean-Removed VQ.- 12.10 Shape-Gain VQ.- 12.11 Multistage VQ.- 12.12 Constrained Storage VQ.- 12.13 Hierarchical and Multiresolution VQ.- 12.14 Nonlinear Interpolative VQ.- 12.15 Lattice Codebook VQ.- 12.16 Fast Nearest Neighbor Encoding.- 12.17 Problems.- 13 Predictive Vector Quantization.- 13.1 Introduction.- 13.2 Predictive Vector Quantization.- 13.3 Vector Linear Prediction.- 13.4 Predictor Design from Empirical Data.- 13.5 Nonlinear Vector Prediction.- 13.6 Design Examples.- 13.7 Problems.- 14 Finite-State Vector Quantization.- 14.1 Recursive Vector Quantizers.- 14.2 Finite-State Vector Quantizers.- 14.3 Labeled-States and Labeled-Transitions.- 14.4 Encoder/Decoder Design.- 14.5 Next-State Function Design.- 14.6 Design Examples.- 14.7 Problems.- 15 Tree and Trellis Encoding.- 15.1 Delayed Decision Encoder.- 15.2 Tree and Trellis Coding.- 15.3 Decoder Design.- 15.4 Predictive Trellis Encoders.- 15.5 Other Design Techniques.- 15.6 Problems.- 16 Adaptive Vector Quantization.- 16.1 Introduction.- 16.2 Mean Adaptation.- 16.3 Gain-Adaptive Vector Quantization.- 16.4 Switched Codebook Adaptation.- 16.5 Adaptive Bit Allocation.- 16.6 Address VQ.- 16.7 Progressive Code Vector Updating.- 16.8 Adaptive Codebook Generation.- 16.9 Vector Excitation Coding.- 16.10 Problems.- 17 Variable Rate Vector Quantization.- 17.1 Variable Rate Coding.- 17.2 Variable Dimension VQ.- 17.3 Alternative Approaches to Variable Rate VQ.- 17.4 Pruned Tree-Structured VQ.- 17.5 The Generalized BFOS Algorithm.- 17.6 Pruned Tree-Structured VQ.- 17.7 Entropy Coded VQ.- 17.8 Greedy Tree Growing.- 17.9 Design Examples.- 17.10 Bit Allocation Revisited.- 17.11 Design Algorithms.- 17.12 Problems. <s> BIB003 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> Preface 1 Introduction 1.1 Compression Techniques 1.1.1 Lossless Compression 1.1.2 Lossy Compression 1.1.3 Measures of Performance 1.2 Modeling and Coding 1.3 Organization of This Book 1.4 Summary 1.5 Projects and Problems 2 Mathematical Preliminaries 2.1 Overview 2.2 A Brief Introduction to Information Theory 2.3 Models 2.3.1 Physical Models 2.3.2 Probability Models 2.3.3. Markov Models 2.3.4 Summary 2.5 Projects and Problems 3 Huffman Coding 3.1 Overview 3.2 "Good" Codes 3.3. The Huffman Coding Algorithm 3.3.1 Minimum Variance Huffman Codes 3.3.2 Length of Huffman Codes 3.3.3 Extended Huffman Codes 3.4 Nonbinary Huffman Codes 3.5 Adaptive Huffman Coding 3.5.1 Update Procedure 3.5.2 Encoding Procedure 3.5.3 Decoding Procedure 3.6 Applications of Huffman Coding 3.6.1 Lossless Image Compression 3.6.2 Text Compression 3.6.3 Audio Compression 3.7 Summary 3.8 Projects and Problems 4 Arithmetic Coding 4.1 Overview 4.2 Introduction 4.3 Coding a Sequence 4.3.1 Generating a Tag 4.3.2 Deciphering the Tag 4.4 Generating a Binary Code 4.4.1 Uniqueness and Efficiency of the Arithmetic Code 4.4.2 Algorithm Implementation 4.4.3 Integer Implementation 4.5 Comparison of Huffman and Arithmetic Coding 4.6 Applications 4.6.1 Bi-Level Image Compression-The JBIG Standard 4.6.2 Image Compression 4.7 Summary 4.8 Projects and Problems 5 Dictionary Techniques 5.1 Overview 5.2 Introduction 5.3 Static Dictionary 5.3.1 Diagram Coding 5.4 Adaptive Dictionary 5.4.1 The LZ77 Approach 5.4.2 The LZ78 Approach 5.5 Applications 5.5.1 File Compression-UNIX COMPRESS 5.5.2 Image Compression-the Graphics Interchange Format (GIF) 5.5.3 Compression over Modems-V.42 bis 5.6 Summary 5.7 Projects and Problems 6 Lossless Image Compression 6.1 Overview 6.2 Introduction 6.3 Facsimile Encoding 6.3.1 Run-Length Coding 6.3.2 CCITT Group 3 and 4-Recommendations T.4 and T.6 6.3.3 Comparison of MH, MR, MMR, and JBIG 6.4 Progressive Image Transmission 6.5 Other Image Compression Approaches 6.5.1 Linear Prediction Models 6.5.2 Context Models 6.5.3 Multiresolution Models 6.5.4 Modeling Prediction Errors 6.6 Summary 6.7 Projects and Problems 7 Mathematical Preliminaries 7.1 Overview 7.2 Introduction 7.3 Distortion Criteria 7.3.1 The Human Visual System 7.3.2 Auditory Perception 7.4 Information Theory Revisted 7.4.1 Conditional Entropy 7.4.2 Average Mutual Information 7.4.3 Differential Entropy 7.5 Rate Distortion Theory 7.6 Models 7.6.1 Probability Models 7.6.2 Linear System Models 7.6.3 Physical Models 7.7 Summary 7.8 Projects and Problems 8 Scalar Quantization 8.1 Overview 8.2 Introduction 8.3 The Quantization Problem 8.4 Uniform Quantizer 8.5 Adaptive Quantization 8.5.1 Forward Adaptive Quantization 8.5.2 Backward Adaptive Quantization 8.6 Nonuniform Quantization 8.6.1 pdf-Optimized Quantization 8.6.2 Companded Quantization 8.7 Entropy-Coded Quantization 8.7.1 Entropy Coding of Lloyd-Max Quantizer Outputs 8.7.2 Entropy-Constrained Quantization 8.7.3 High-Rate Optimum Quantization 8.8 Summary 8.9 Projects and Problems 9 Vector Quantization 9.1 Overview 9.2 Introduction 9.3 Advantages of Vector Quantization over Scalar Quantization 9.4 The Linde-Buzo-Gray Algorithm 9.4.1 Initializing the LBG Algorithm 9.4.2 The Empty Cell Problem 9.4.3 Use of LBG for Image Compression 9.5 Tree-Structured Vector Quantizers 9.5.1 Design of Tree-Structured Vector Quantizers 9.6 Structured Vector Quantizers 9.6.1 Pyramid Vector Quantization 9.6.2 Polar and Spherical Vector Quantizers 9.6.3 Lattice Vector Quantizers 9.7 Variations on the Theme 9.7.1 Gain-Shape Vector Quantization 9.7.2 Mean-Removed Vector Quantization 9.7.3 Classified Vector Quantization 9.7.4 Multistage Vector Quantization 9.7.5 Adaptive Vector Quantization 9.8 Summary 9.9 Projects and Problems 10 Differential Encoding 10.1 Overview 10.2 Introduction 10.3 The Basic Algorithm 10.4 Prediction in DPCM 10.5 Adaptive DPCM (ADPCM) 10.5.1 Adaptive Quantization in DPCM 10.5.2 Adaptive Prediction in DPCM 10.6 Delta Modulation 10.6.1 Constant Factor Adaptive Delta Modulation (CFDM) 10.6.2 Continuously Variable Slope Delta Modulation 10.7 Speech Coding 10.7.1 G.726 10.8 Summary 10.9 Projects and Problems 11 Subband Coding 11.1 Overview 11.2 Introduction 11.3 The Frequency Domain and Filtering 11.3.1 Filters 11.4 The Basic Subband Coding Algorithm 11.4.1 Bit Allocation 11.5 Application to Speech Coding-G.722 11.6 Application to Audio Coding-MPEG Audio 11.7 Application to Image Compression 11.7.1 Decomposing an Image 11.7.2 Coding the Subbands 11.8 Wavelets 11.8.1 Families of Wavelets 11.8.2 Wavelets and Image Compression 11.9 Summary 11.10 Projects and Problems 12 Transform Coding 12.1 Overview 12.2 Introduction 12.3 The Transform 12.4 Transforms of Interest 12.4.1 Karhunen-Loeve Transform 12.4.2 Discrete Cosine Transform 12.4.3 Discrete Sine Transform 12.4.4 Discrete Walsh-Hadamard Transform 12.5 Quantization and Coding of Transform Coefficients 12.6 Application to Image Compression-JPEG 12.6.1 The Transform 12.6.2 Quantization 12.6.3 Coding 12.7 Application to Audio Compression 12.8 Summary 12.9 Projects and Problems 13 Analysis/Synthesis Schemes 13.1 Overview 13.2 Introduction 13.3 Speech Compression 13.3.1 The Channel Vocoder 13.3.2 The Linear Predictive Coder (Gov.Std.LPC-10) 13.3.3 Code Excited Linear Prediction (CELP) 13.3.4 Sinusoidal Coders 13.4 Image Compression 13.4.1 Fractal Compression 13.5 Summary 13.6 Projects and Problems 14 Video Compression 14.1 Overview 14.2 Introduction 14.3 Motion Compensation 14.4 Video Signal Representation 14.5 Algorithms for Videoconferencing and Videophones 14.5.1 ITU_T Recommendation H.261 14.5.2 Model-Based Coding 14.6 Asymmetric Applications 14.6.1 The MPEG Video Standard 14.7 Packet Video 14.7.1 ATM Networks 14.7.2 Compression Issues in ATM Networks 14.7.3 Compression Algorithms for Packet Video 14.8 Summary 14.9 Projects and Problems A Probability and Random Processes A.1 Probability A.2 Random Variables A.3 Distribution Functions A.4 Expectation A.5 Types of Distribution A.6 Stochastic Process A.7 Projects and Problems B A Brief Review of Matrix Concepts B.1 A Matrix B.2 Matrix Operations C Codes for Facsimile Encoding D The Root Lattices Bibliography Index <s> BIB004 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> A real-time, low-power video encoder design for pyramid vector quantization (PVQ) has been presented. The quantizer is estimated to dissipate only 2.1 mW for real-time video compression of images of 256 × 256 pixels at 30 frames per second in standard 0.8-micronCMOS technology with a 1.5 V supply. Applying this quantizer to subband decomposed images, the quantizer performs better than JPEG on average. We achieve this high level of power efficiency with image quality exceeding that of variable rate codes through algorithmic and architectural reformulation. The PVQ encoder is well-suited for wireless, portable communication applications. <s> BIB005 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> In this paper, a novel algorithm for low-power image coding and decoding is presented and the various inherent trade-offs are described and investigated in detail. The algorithm reduces the memory requirements of vector quantization, i.e., the size of memory required for the codebook and the number of memory accesses by using small codebooks. This significantly reduces the memory-related power consumption, which is an important part of the total power budget. To compensate for the loss of quality introduced by the small codebook size, simple transformations are applied on the codewords during coding. Thus, small codebooks are extended through computations and the main coding task becomes computation-based rather than memory-based. Each image block is encoded by a codeword index and a set of transformation parameters. The algorithm leads to power savings of a factor of 10 in coding and of a factor of 3 in decoding, at least in comparison to classical full-search vector quantization. In terms of SNR, the image quality is better than or comparable to that corresponding to full-search vector quantization, depending on the size of the codebook that is used. The main disadvantage of the proposed algorithm is the decrease of the compression ratio in comparison to vector quantization. The trade-off between image quality and power consumption is dominant in this algorithm and is mainly determined by the size of the codebook. <s> BIB006 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> Pyramid vector quantization (PVQ) uses the lattice points of a pyramidal shape in multidimensional space as the quantizer codebook. It is a fixed-rate quantization technique that can be used for the compression of Laplacian-like sources arising from transform and subband image coding, where its performance approaches the optimal entropy-coded scalar quantizer without the necessity of variable length codes. In this paper, we investigate the use of PVQ for compressed image transmission over noisy channels, where the fixed-rate quantization reduces the susceptibility to bit-error corruption. We propose a new method of deriving the indices of the lattice points of the multidimensional pyramid and describe how these techniques can also improve the channel noise immunity of general symmetric lattice quantizers. Our new indexing scheme improves channel robustness by up to 3 dB over previous indexing methods, and can be performed with similar computational cost. The final fixed-rate coding algorithm surpasses the performance of typical Joint Photographic Experts Group (JPEG) implementations and exhibits much greater error resilience. <s> BIB007 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> Vector quantization image encoding requires a huge amount of computation and thus of power consumption. In this paper a novel method is proposed for the reduction of the power consumption of vector quantization image processing by truncating the least significant bits of the image pixels and the codewords elements during the nearest neighbor computation. Experimental results prove that at least 3 pixels/elements bits can be truncated without affecting the picture quality. This results in an average 65% reduction of bus power consumption and in an average 62% reduction of the power consumed in major data path blocks. <s> BIB008 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> This paper evaluates and compares JPEG 2000 and Successive Approximation Multi-stage Vector Quantization (SAMVQ) compression algorithms for hyperspectral imagery. PSNR was used to measure the statistical performance of the two compression algorithms. The SAMVQ outperforms JPEG 2000 by 17 dB of PSNR at the same compression ratios. The preservation of both spatial and spectral features was evaluated qualitatively and quantitatively. The SAMVQ outperforms JPEG 2000 in both spatial and spectral features preservation. <s> BIB009 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Vector Quantization Compression. <s> An efficient hybrid image vector quantization (VQ) technique based on a classification in the DCT domain is presented in this letter. This algorithm combines two kinds of VQ, predictive VQ (PVQ) and discrete cosine transform domain VQ (DCTVQ), and adopts a simple classifier which employs only three DCT coefficients in the 8 × 8 block. For each image block, the classifier switches to the PVQ coder if the block is relatively complex, and otherwise switches to the DCTVQ coder. Experimental results show that the proposed algorithm can achieve higher PSNR values than ordinary VQ, PVQ, JPEG, and JPEG2000 at the same bit-rate. <s> BIB010
Vector quantization (VQ) is a conventional method for performing data compression BIB003  . VQ can be viewed as a mapping of a large set of vectors into a small subset of code vectors called the codebook. Formally, a vector quantizer Q is a mapping from a k-dimensional Euclidean space R k into a finite subset C of R k , called codebook. Thus, Q : R k → C. We highlight that the most important step is the codebook construction. The well-known algorithm used to design the codebook is LBG BIB001 . The encoder assigns to each input vector x from R k an index which corresponds to a vector in C, that in turn is mapped to a codeword c in the set C by a decoder. If a distortion measure d(x, c) which represents the cost associated with reproducing vectors x by c is defined, then the best mapping Q is the one which minimizes d(x, c). In image compression, basic vector quantization consists in dividing the input image into blocks of size l × m pixels, where each block is considered as a k-dimensional vector represented by a data vector x in the set R k . Each vector is, then, compared with the entries of an appropriate codebook C, and the index i of the codebook entry c i (most similar to the source data vector) is sent to a destination. At the destination, the index accesses to the corresponding entry from an identical codebook and permits to reconstruct approximately the original image ( Figure 10 ). For more detail, the reader is referred to BIB004 BIB003 BIB002 . In this kind of compression (and in fractal compression presented in Section 5.2), one should note the absence of transformation block, such as DCT or DWT, and entropy encoding block, which may reduce the computation complexity. The remaining task is to compare between the gain, in terms of power dissipation, of VQ (without transformation block), and a usual framework encoding scheme incorporating transformation block (such as DCT or DWT) and entropy encoding block. The advantage of image VQ over other types of quantizers is the simplicity of its decoder, since it only consists of table lookups. However, the basic disadvantage of VQ is its complexity, which increases with the increase of vector dimensionality. This complexity may decrease the coding speed and increase the power dissipation of the decoder especially in power-constrained applications such as VSN. Another disadvantage of image VQ is related to the design of a universal codebook for a large database of images, which requires an important memory and huge number of memory accesses. Several image coding schemes with vector quantization have been proposed in the imaging literature. However, no VQ scheme has been proposed in VSN context. We find appealing to supply this section by some attractive works which may help for the conception and design of a new VQ-based compression method dedicated to VSN. Particularly, we roughly present works which provide a VQ-based scheme exceeding the state of the art compression standards such as JPEG and JPEG2000 in terms of energy efficiency. The authors in BIB008 have considered a method for the reduction of the power consumption of vector quantization image processing, by truncating the least significant bits of the image pixels and the codeword elements during the nearest neighbor computation. In the same way, in BIB006 , an algorithm for low-power image coding and decoding is presented. The suggested algorithm reduces the memory requirements of vector quantization; that is, the size of memory required for the codebook and the number of memory accesses by using small codebooks, which reduces the power consumption. The authors in BIB005 suggest a low-power pyramid vector quantization, which on average outperforms JPEG sometimes in excess of 2 dB. Another work showing that the possibility of designing an efficient image VQ encoder that exceeds the performance of JPEG is that one suggested in BIB007 . The authors in BIB007 use the pyramidal VQ, a variant of VQ, combined with some indexing techniques which require roughly the same encoding and decoding hardware complexity. This scheme outperforms JPEG implementations. The paper BIB009 evaluates and compares JPEG2000 with a new variant of VQ called successive approximation multistage vector quantization (SAMVQ) compression algorithms for hyperspectral imagery. It is observed in BIB009 that the SAMVQ outperforms JPEG2000 by 17 dB of PSNR at the same compression ratios. Unfortunately, since SAMVQ was patented by CSA, its main idea and its degree of complexity are not clearly presented. The work in BIB010 combines two kinds of VQ, predictive VQ (PVQ) and discrete cosine transform domain VQ (DCTVQ), to yield an efficient hybrid image compression scheme. Moreover, this scheme uses a simple classifier which employs only three DCT coefficients within each block of 8 × 8 pixels. For each image block, the classifier switches to the DCTVQ coder if the block is not complex, and to the PVQ coder if the block is relatively complex. The suggested algorithm can achieve higher PSNR values than VQ, PVQ, JPEG, and JPEG2000 at the same bit rate. This scheme may be a good candidate for power-aware applications such as VSN. Data compression using VQ could be an acceptable compression technique for VSN, due to their reasonably compression ratio and relatively simple structure. Since VQbased compression scheme could be implemented without any transformation (i.e., DCT or DWT), which dissipates the highest percentage of energy within a compression scheme, it is interesting to think about the design of VQ schemes dedicated to VSN. The encoder within such scheme has to be light compared to DCT-based encoder or DWT-based encoder. Low-power image VQ encoders are encouraged in VSN application. To the best of our knowledge, the application of VQ compression method in VSN has not yet been investigated.