A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Overview of Image Compression 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> Overview of Image Compression for VSN <s> Sensor networks are distributed event-based systems that differ from traditional communication networks in several ways: sensor networks have severe energy constraints, redundant low-rate data, and many-to-one flows. Data-centric mechanisms that perform in-network aggregation of data are needed in this setting for energy-efficient information flow. In this paper we model data-centric routing and compare its performance with traditional end-to-end routing schemes. We examine the impact of source-destination placement and communication network density on the energy costs and delay associated with data aggregation. We show that data-centric routing offers significant performance gains across a wide range of operational scenarios. We also examine the complexity of optimal data aggregation, showing that although it is an NP-hard problem in general, there exist useful polynomial-time special cases. <s> BIB002 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Overview of Image Compression for VSN <s> The impact of using different lossy compression algorithms on the matching accuracy of fingerprint and face ::: recognition systems is investigated. In particular, we relate rate-distortion performance as measured in PSNR ::: to the matching scores as obtained by the recognition systems. JPEG2000 and SPIHT are correctly predicted ::: by PSNR to be the most suited compression algorithms to be used in fingerprint and face recognition systems. ::: Fractal compression is identified to be least suited for the use in the investigated recognition systems, although ::: PSNR suggests JPEG to deliver worse recognition results in the case of face imagery. JPEG compression performs ::: surprisingly well at high bitrates in face recognition systems, given the low PSNR performance observed. <s> BIB003 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Overview of Image Compression for VSN <s> Energy-efficient image communication is one of the most important goals for a large class of current and future sensor network applications. This paper presents a quantitative comparison between the energy costs associated with 1) direct transmission of uncompressed images and 2) sensor platform-based JPEG compression followed by transmission of the compressed image data. JPEG compression computations are mapped onto various resource-constrained sensor platforms using a design environment that allows computation using the minimum integer and fractional bit-widths needed in view of other approximations inherent in the compression process and choice of image quality parameters. Detailed experimental results examining the tradeoffs in processor resources, processing/transmission time, bandwidth utilization, image quality, and overall energy consumption are presented. <s> BIB004
This section provides some background information to follow this paper. Recall that VSNs are spatially distributed networks consisting of small sensing devices equipped with low-power CMOS imaging sensors such as Cyclops. Ideally, VSNs are deployed in the region of interest to collect and transmit data in multi-hop way. VSNs are involved in many domains such as environmental monitoring, video surveillance, and object detection and tracking. VSNs differ from their predecessor's scalar data WSN mainly in the following. (i) Information volume and nature of VSN, which is in general pixel based, is quite different from simple scalar data manipulated by WSN, such as temperature. (ii) Lost information in VSNs is tolerated due to the redundancy nature of visual flows. Whereas in WSN, the loss of some packets may affect seriously the value of collected data (e.g., temperature value). (iii) VSN's camera has a restricted directional sensing field of view, which is not the case for scalar data sensors. (iv) VS neighbors monitoring the same small local region of interest have multiple and different views of this scene, compared to scalar data sensor where a unique value (e.g., temperature) is collected by neighbor's nodes (situated in the same region). (v) Important resources in memory, processing, and communication power are required for VS node to manipulate the huge amount of visual flows. (vi) Efficient compression algorithms, in terms of power dissipation, are mandatory to handle information flows, compared to scalar data sensor where the compression is not very required. Most significant studies in scalar data WSN have typically assumed the computational costs, including acquisition and compression, insignificant compared to the related communication costs (e.g., BIB002 ). This assumption may be suitable for scalar data sensors, where the computation cost of data compression, if performed, is negligible compared to the communication cost. In case of WSN handling images (or video), this assumption may not hold, since visual flows always necessitate compression. In this section, we show the relationship between the compression cost and the transmission cost in the context of VSN. Deciding to precede transmission by compression or not depends mainly on the specific compression algorithm, and possibly on the processor and the radio transceiver if we include the time factor. Usually, image transmission preceded by compression is the ideal choice to gain in time and energy. It is well known that some compression algorithms are more time and energy consuming than others. Those algorithms are, generally, used for storage purpose, or also used when no power or time restrictions are required. For instance, compression using Fractals or JPEG2000 is very time and energy consuming BIB003 , and their applications to VSN seem less efficient. However, when applied to traditional wired networks, JPEG2000 gives the highest compression ratio regardless of the consumed energy. Another example is described in BIB004 , where the authors have shown that compressing, using JPEG, and transmitting an image is more energy inefficient than transmitting the uncompressed image at higher quality level. In such a case, compression is not justified, since the transmission of the uncompressed image consumes less energy. Different image compression classifications are found in the literature. In general, they are categorized in terms of data loss, or whether they use a transform coding or predictive coding BIB001 . Our goal is not to survey all of them, but rather we review those ISC algorithms that their applications in VSN domain seem practical. In particular, basic algorithms for coding images are still considered. Based on the requirements of reconstruction, image compression schemes are commonly provided into two categories: lossless and lossy scheme. Lossless image compression algorithms refer to the perfect reconstruction of the original image from the compressed one. On the other hand, with lossy image compression scheme, merely an approximation of the original image is achieved. The main benefit of lossy image compression algorithm over lossless one is to gain in encoding/decoding time, compression ratio BIB001 , or also in case of power-constrained applications, in energy. That is, we believe that lossy schemes are highly encouraged in VSN, compared to lossless techniques. However, if lossy and lossless compression algorithms yield the same results in terms of power dissipation, lossless algorithms are encouraged. We regroup the ISC algorithms discussed in this paper into two categories: transform-based algorithms, such as discrete cosine transform-(DCT-) and discrete wavelet transform-(DWT-) based algorithms, and non transformbased algorithms, such as vector quantization or fractals; see Figure 2 . We note that the typical design of a transformbased algorithm is based on three stages: spatial decorrelation (also called source encoder), followed by quantizer, and entropy encoder. Other schemes (non-transform-based algorithms) such as vector quantization or fractals do not follow this design.