A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Wavelet-Based Compression Schemes for VSN. <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> BIB001 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Wavelet-Based Compression Schemes for VSN. <s> This paper addresses the problem of low memory wavelet image compression. While wavelet or subband coding of images has been shown to be superior to more traditional transform coding techniques, little attention has been paid until recently to the important issue of whether both the wavelet transforms and the subsequent coding can be implemented in low memory without significant loss in performance. We present a complete system to perform low memory wavelet image coding. Our approach is "line-based" in that the images are read line by line and only the minimum required number of lines is kept in memory. There are two main contributions of our work. First, we introduce a line-based approach for the implementation of the wavelet transform, which yields the same results as a "normal" implementation, but where, unlike prior work, we address memory issues arising from the need to synchronize encoder and decoder. Second, we propose a novel context-based encoder which requires no global information and stores only a local set of wavelet coefficients. This low memory coder achieves performance comparable to state of the art coders at a fraction of their memory utilization. <s> BIB002 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Wavelet-Based Compression Schemes for VSN. <s> The strict constrains of wireless sensor networks (WSN) on individual sensor node’s resource brings great challenges to the information processing, especially in image capture sensor network. A Simple Wavelet Compression (SWC) processing of image coding is proposed to maximize compression and minimize energy cost in WSN. For low activity in WSN, we employ a Low-complexity Change Detection Algorithm (LCDA) to mark active blocks and we only encode these active regions to save energy. In particular, a position estimation and compensation method is presented to exploit the inherent correlations that exist between sensor readings based on distributed lifting scheme. The impact of this scheme on image signal quality is presented in the final. The simulation results showed that these approaches achieved significant energy savings without sacrificing the quality of the image reconstruction <s> BIB003 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Wavelet-Based Compression Schemes for VSN. <s> Due to resource constraints, digital image transmissions are a significant challenge for image sensor based Wireless Sensor Networks (WSN). In this paper, we propose a novel robust and energy-efficient scheme, called Image Component Transmission (ICT) in WSN by providing various levels of reliability during image transmissions. Different components in the embedded wavelet image bit stream are considered and essential components of the compressed image such as the information for the positions of significant wavelet coefficients are transmitted with higher quality assurance. Relatively less important components such as the information for the values of pixels are transmitted with lower overhead. Simulation results show the proposed scheme achieves higher energy efficiency in WSN, with image transmission quality enhanced considerably by up to 6dB in terms of the Peak Signal to Noise Ratio (PSNR). <s> BIB004 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Wavelet-Based Compression Schemes for VSN. <s> We propose a self-adaptive image transmission scheme driven by energy efficiency considerations in order to be suitable for wireless sensor networks. It is based on wavelet image transformand semireliable transmission to achieve energy conservation. Wavelet image transform provides data decomposition in multiple levels of resolution, so the image can be divided into packets with different priorities. Semireliable transmission enables priority-based packet discarding by intermediate nodes according to their battery's state-of-charge. Such an image transmission approach provides a graceful tradeoff between the reconstructed images quality and the sensor nodes' lifetime. An analytical study in terms of dissipated energy is performed to compare the self-adaptive image transmission scheme to a fully reliable scheme. Since image processing is computationally intensive and operates on a large data set, the cost of the wavelet image transform is considered in the energy consumption analysis. Results show up to 80% reduction in the energy consumption achieved by our proposal compared to a nonenergy-aware one, with the guarantee for the image quality to be lower-bounded. <s> BIB005 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Wavelet-Based Compression Schemes for VSN. <s> Existing image wavelet transform techniques exceed the computational and memory resources of low-complexity wireless sensor nodes. In order to enable multimedia wireless sensors to use image wavelet transforms techniques to pre-process collected image sensor data, we introduce the fractional wavelet filter. The fractional wavelet filter computes the wavelet transform of a 256x256 grayscale image using only 16-bit fixed-point arithmetic on a micro-controller with less than 1.5kbyte of RAM. We comprehensively evaluate the resource requirements (RAM, computational complexity, computing time) as well as image quality of the fractional wavelet filter. We find that the fractional wavelet transform computed with fixed-point arithmetic gives typically negligible degradations in image quality. We also find that combining the fractional wavelet filter with a customized wavelet-based image coding system achieves image compression competitive to the JPEG2000 standard. <s> BIB006
Herein, we consider another category of compression schemes, where authors do not use or modify an existing scheme, but rather they develop their own DWT-based method which fits their circumstances. Several research works have dealt with low-memory DWT schemes. Our goal is not to survey all DWT implementations suggested in the literature, but rather we review algorithms applicable to VSN. The line-based version of the image wavelet transform proposed in BIB002  employs a buffer system where we store only a subset of the wavelets coefficients. That is, a considerable reduction in memory is observed, compared to the traditional transform approach. The authors in BIB006 introduce the fractional wavelet filter as a computation scheme to calculate fractional values of each wavelet subband. This allows the image wavelet transform to be implemented with very low RAM requirements. More precisely, the authors show that their schemes permit to a camera sensor having less than 2 kByte RAM to perform a multilevel 9/7 image wavelet transform. The picture dimension can be 256 × 256 using fixed-point arithmetic and 128 × 128 using floating-point arithmetic. Compared to BIB002  , the line-based method cannot run on a sensor with very small memory. The fractional wavelet filter method reduces the memory requirements compared to the linebased approach. The authors do not show the impact of their scheme on energy consumption. Based on the fact that an image is generally constituted by a set of components (or regions) with unequal importance, the authors in BIB004 explore this idea to build a semireliable scheme for VSN called image component transmission (ICT). ICT scheme can be performed in two phases. In the first phase, the identification of the important components within the target image is performed after DWT process. After that, in the second phase, unequally important levels of transmissions are applied to different components in the compressed image. Important parts within an image, such as the information for the positions of significant wavelet coefficients, are transmitted reliably. While relatively less important components (such as the information for the values of pixels) are transmitted with lower importance, leading to energy efficiency. In fact, the suggested methodology transmission is generic and independent of specific wavelet image compression algorithms. In BIB005 , the authors propose an adaptive energy-aware protocol for image transmission over VSN. It is based on wavelet image decomposition using the Le Gall 5-tap/3-tap wavelet filter and semireliable transmission using prioritybased mechanism. The compression is achieved through the combination of the Le Gall 5-tap/3-tap wavelet filter with Lempel-Ziv-Welch (LZW) technique BIB001 . The target image is firstly decomposed using wavelet filter, which provides multiple levels of resolution of the input image having different priorities. After that, the semireliable policies are applied to the wavelet coefficients by intermediate nodes. Based on their remaining energies, intermediate nodes decide whether they drop or forward packets. As explained in BIB005 , packet priority is defined either based on the wavelet resolution level of the image or based on the wavelet coefficients magnitude. This transmission scheme offers a trade-off in consumed energy versus reconstructed image quality, and it shows the advantage of the magnitude-based prioritization method over the resolution level method. However, this mechanism sacrifices a certain amount of image quality to prolong the VSN's lifetime. The authors in BIB003 consider the slow activity scenario in clustered VSN. For that reason they suggest an adaptive and distributed wavelet compression algorithm. The key features of the proposed scheme are described as follows. This algorithm exploits the spatial inherent correlations between sensor readings using a position estimation and compensation method. For that purpose, a compression method based on 5/3 wavelet filter is used (the authors also mention the possibility to use EZW or SPIHT as a compression tool). They also propose a change detection algorithm to mark active blocks within a target image, and they only encode these blocks, which permits to reduce computation complexity without sacrificing the quality of the image reconstruction. After the survey of the main transform-based schemes, we review in Section 5 another category of compression schemes, which is non-transform-based such as vector quantization and fractals.