A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> Let \{(X_{k}, Y_{k}) \}^{ \infty}_{k=1} be a sequence of independent drawings of a pair of dependent random variables X, Y . Let us say that X takes values in the finite set \cal X . It is desired to encode the sequence \{X_{k}\} in blocks of length n into a binary stream of rate R , which can in turn be decoded as a sequence \{ \hat{X}_{k} \} , where \hat{X}_{k} \in \hat{ \cal X} , the reproduction alphabet. The average distortion level is (1/n) \sum^{n}_{k=1} E[D(X_{k},\hat{X}_{k})] , where D(x,\hat{x}) \geq 0, x \in {\cal X}, \hat{x} \in \hat{ \cal X} , is a preassigned distortion measure. The special assumption made here is that the decoder has access to the side information \{Y_{k}\} . In this paper we determine the quantity R \ast (d) , defined as the infimum ofrates R such that (with \varepsilon > 0 arbitrarily small and with suitably large n )communication is possible in the above setting at an average distortion level (as defined above) not exceeding d + \varepsilon . The main result is that R \ast (d) = \inf [I(X;Z) - I(Y;Z)] , where the infimum is with respect to all auxiliary random variables Z (which take values in a finite set \cal Z ) that satisfy: i) Y,Z conditionally independent given X ; ii) there exists a function f: {\cal Y} \times {\cal Z} \rightarrow \hat{ \cal X} , such that E[D(X,f(Y,Z))] \leq d . Let R_{X | Y}(d) be the rate-distortion function which results when the encoder as well as the decoder has access to the side information \{ Y_{k} \} . In nearly all cases it is shown that when d > 0 then R \ast(d) > R_{X|Y} (d) , so that knowledge of the side information at the encoder permits transmission of the \{X_{k}\} at a given distortion level using a smaller transmission rate. This is in contrast to the situation treated by Slepian and Wolf [5] where, for arbitrarily accurate reproduction of \{X_{k}\} , i.e., d = \varepsilon for any \varepsilon >0 , knowledge of the side information at the encoder does not allow a reduction of the transmission rate. <s> BIB001 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> Wireless distributed microsensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. In this paper, we look at communication protocols, which can have significant impact on the overall energy dissipation of these networks. Based on our findings that the conventional protocols of direct transmission, minimum-transmission-energy, multi-hop routing, and static clustering may not be optimal for sensor networks, we propose LEACH (Low-Energy Adaptive Clustering Hierarchy), a clustering-based protocol that utilizes randomized rotation of local cluster based station (cluster-heads) to evenly distribute the energy load among the sensors in the network. LEACH uses localized coordination to enable scalability and robustness for dynamic networks, and incorporates data fusion into the routing protocol to reduce the amount of information that must be transmitted to the base station. Simulations show the LEACH can achieve as much as a factor of 8 reduction in energy dissipation compared with conventional outing protocols. In addition, LEACH is able to distribute energy dissipation evenly throughout the sensors, doubling the useful system lifetime for the networks we simulated. <s> BIB002 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> A distributed coding technique for images captured from sensors with overlapping fields of view in a sensor network is outlined. First, images from correlated views are roughly registered (relative to a sensor of primary interest) via a low-bandwidth data-sharing method involving image feature points and feature point correspondence. An area of overlap is then identified, and each sensor transmits a low-resolution version of the common image block to the receiver, amortizing the coding cost for that block among the set of sensors. Super-resolution techniques are finally employed at the receiver to reconstruct a high-resolution version of the common block. We discuss the registration and super-resolution techniques used and present examples of each step in the proposed coding process. A numerical analysis illustrating the potential coding benefit follows, and we conclude with a brief discussion of the key issues remaining to be resolved on the path to coder robustness. <s> BIB003 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> In recent years, sensor research has been undergoing a quiet revolution, promising to have a significant impact throughout society that could quite possibly dwarf previous milestones in the information revolution. Realizing the great promise of sensor networks requires more than a mere advance in individual technologies. It relies on many components working together in an efficient, unattended, comprehensible, and trustworthy manner. One of the enabling technologies in sensor networks is the distributed source coding (DSC), which refers to the compression of the multiple correlated sensor outputs that does not communicate with each other. DSC allows a many-to-one video coding paradigm that effectively swaps encoder-decoder complexity with respect to conventional video coding, thereby representing a fundamental concept shift in video processing. This article has presented an intensive discussion on two DSC techniques, namely Slepian-Wolf coding and Wyner-Ziv coding. The Slepian and Wolf coding have theoretically shown that separate encoding is as efficient as joint coding for lossless compression in channel coding. <s> BIB004 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> Efficient compression and transmission of images in a resource-constrained multihop wireless network is considered. Distributed image compression is proposed as a means to overcome the computation and/or energy limitation of individual nodes by sharing the processing of tasks. It has the additional benefit of extending the overall lifetime of the network by distributing the computational load among otherwise idle processors. Two design alternatives for energy efficient distributed image compression are proposed and investigated with respect to energy consumption and image quality. Simulation results show that the proposed scheme prolongs the system lifetime at a normalized total energy consumption comparable to the centralized image compression. <s> BIB005 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> A wireless sensor network with multimedia capabilities typically consists of data sensor nodes, which sense, for instance, sound or motion, and video sensor nodes, which capture video of events of interest. In this survey, we focus on the video encoding at the video sensors and the real-time transport of the encoded video to a base station. Real-time video streams have stringent requirements for end-to-end delay and loss during network transport. In this survey, we categorize the requirements of multimedia traffic at each layer of the network protocol stack and further classify the mechanisms that have been proposed for multimedia streaming in wireless sensor networks at each layer of the stack. Specifically, we consider the mechanisms operating at the application, transport, network, and MAC layers. We also review existing cross-layer approaches and propose a few possible cross-layer solutions to optimize the performance of a given wireless sensor network for multimedia streaming applications. <s> BIB006 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Distributed Source Coding Paradigm <s> Currently most energy-constrained wireless sensor networks are designed with the object of minimizing the communication power at the cost of more computation. To achieve high compression efficiency, the main image compression algorithms used in wireless sensor networks are the high-complexity, state-of-the-art image compression standards, such as JPEG2000. These algorithms require complex hardware and make the energy consumption for computation comparable to communication energy dissipation. To reduce the hardware cost and the energy consumption of the sensor network, a low-complexity and energy efficient image compression scheme is proposed. The compression algorithm in the proposed scheme greatly lowers the computational complexity and reduces the required memory, while it still achieves required PSNR. The proposed implementation scheme of the image compression algorithm overcomes the computation and energy limitation of individual nodes by sharing the processing of tasks. And, it applies transmission range adjustment to save communication energy dissipation. Performance of the proposed scheme is investigated with respect to image quality and energy consumption. Simulation results show that it greatly prolongs the lifetime of the network under a specific image quality requirement. <s> BIB007
To be self contained, we supply our paper by a short introduction on DSC paradigm and some related works. For more information on the subject, readers are advised to read BIB004 or BIB006 . DSC for VSN, refers to the compression of multiple statistically dependent sensor outputs that do not communicate with each other. Each sensor sends, independently, its compressed output to a base station for joint decoding. The well-known conventional one-to-many coding framework used in most codec's, such as MPEG, is reversed under DSC paradigm. In fact, within the one-to-many framework, the encoder usually behaves complex, compared to the relatively simple decoder complexity. On the other hand, the many-to-one coding paradigm, which is the intrinsic characteristic of DSC, moves the encoder complexity at the decoder side. Therefore, encoders can be designed simple, compared to the more complex decoders implemented at the sink. Under DSC paradigm applied in VSN, the complexity of the coder side is then shifted to the decoder at the sink, where enough power is available. Despite the inherent encoder simplicity characteristic of the DSC, their theoretical restrictions have not yet been closely achieved by practical applications. The theoretical aspects behind DSC schemes are outside the scope of this paper. We refer our reader to  for more details. The lossless Slepian-Wolf and lossy Wyner-Ziv coding schemes are an encouraging conceptual basis for DSC. In practice, lossy DSC is usually implemented using a quantizer followed by lossless DSC, while the decoder consists of the joint entropy decoder followed by a joint dequantizer BIB004 . A brief description of Wyner-Ziv theorem is supplied, since it represents a promising solution for VSN and achieves a comparable performance to that of MPEG. The Wyner-Ziv theorem extends the Slepian-Wolf work for lossy coding with a distortion measure. Theoretically, a Wyner-Ziv encoder can be seen as a coarse quantizer of the original signal, followed by a Slepian-Wolf encoder stage, which performs lossless encoding of source data assuming that the decoder has access to some side information which is not known to the encoder BIB001 . To reconstruct the received signal at the decoder with minimum distortion, joint source-channel coding is performed using side information (complete sensed data sent by one of the sources). Figure 13 shows a schematic diagram of the Wyner-Ziv encoder/decoder. For more information about this subject, the reader is referred to BIB004 . Recall that our interest in this section is to review the interesting DSC schemes of still images in VSN context, including distributed JPEG2000 and distributed coding of overlapped images taken by different cameras. We start by the work presented in  , where the authors use JPEG as a compression method to reduce the size of images without any special considerations to energy factor during compression stage. Rather, they consider a scenario where sensors, sharing the same field of view, can process and combine overlapping regions to reduce the energy spent on image transmission. For that reason, a distributed protocol was proposed and evaluated. The simulations show that the distributed protocol, when compared to sending images individually, can achieve some reductions in energy consumption. The authors in BIB003 present a method for distributed coding technique of images in VSN by exploring correlation between overlapped sensor field of views. To do that, overlapped images are first registered via a method involving the extraction of image feature points and feature points analysis. After that, the region of overlap is identified, and each sensor sends a low-resolution version of the overlapped area toward the receiver. At the reception, the base station uses the superresolution methods allowing the high-resolution version of the overlapped region. The work in BIB007 is inspired by the concept of parallel distributed computing theory. A distributed lapped biorthogonal transform-(LBT-) based image compression scheme is proposed for VSN. It uses LBT transform, which is very suitable for distributed implementation in the sensor network, compared to DCT or DWT. Moreover, to further reduce the computational complexity, Golomb and multiple quantization coders are used in image compression instead of Huffman or arithmetic coding. For routing purposes, the proposed scheme is designed based on the well-known LEACH protocol, which is designed for clusters sensor networks BIB002 . This scheme prolongs the lifetime of the network under a specific image quality requirement. Compared to DCT, LBT improves coding efficiency by solving the problem of blocking artifacts and taking into consideration interblock spatial correlation. Weighted against DWT, LBT may lower considerably the complexity of computation and reduce the required memory. In resource-constrained VSNs, the authors in BIB005 firstly notice the high energy consumption of JPEG2000. To make it light, they distribute the work load of wavelet transform to several groups of nodes along the path between the source and the destination using the concept of parallel distributed computing theory. That is, they propose two data exchange schemes with respect to image quality and energy consumption. In the first scheme, the target image is partitioned into a set of blocks along the rows to perform 1D wavelet. Similarly, the target image is divided into a set of blocks to perform 1D wavelet on columns. This data exchange scheme does not result in any image quality loss. In the next scheme, the image is partitioned into tiles, and each tile is sent to a node to do 2D wavelet transform independently. The authors in BIB005 show, by simulation, that the distributed scheme improves significantly the network lifetime compared to a centralized approach.