A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Scheme: Compressive Sensing <s> This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f. <s> BIB001 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Scheme: Compressive Sensing <s> Suppose x is an unknown vector in Ropfm (a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements n can be dramatically smaller than the size m. Thus, certain natural classes of images with m pixels need only n=O(m1/4log5/2(m)) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual m pixel samples. More specifically, suppose x has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor)-so the coefficients belong to an lscrp ball for 0<ples1. The N most important coefficients in that expansion allow reconstruction with lscr2 error O(N1/2-1p/). It is possible to design n=O(Nlog(m)) nonadaptive measurements allowing reconstruction with accuracy comparable to that attainable with direct knowledge of the N most important coefficients. Moreover, a good approximation to those N important coefficients is extracted from the n measurements by solving a linear program-Basis Pursuit in signal processing. The nonadaptive measurements have the character of "random" linear combinations of basis/frame elements. Our results use the notions of optimal recovery, of n-widths, and information-based complexity. We estimate the Gel'fand n-widths of lscrp balls in high-dimensional Euclidean space in the case 0<ples1, and give a criterion identifying near- optimal subspaces for Gel'fand n-widths. We show that "most" subspaces are near-optimal, and show that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces <s> BIB002 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Scheme: Compressive Sensing <s> Compressive Sensing is an emerging field based on the revelation that a small group of nonadaptive linear projections of a compressible signal contains enough information for reconstruction and processing. In this paper, we propose algorithms and hardware to support a new theory of Compressive Imaging. Our approach is based on a new digital image/video camera that directly acquires random projections of the light field without first collecting the pixels/voxels. Our camera architecture employs a digital micromirror array to perform optical calculations of linear projections of an image onto pseudorandom binary patterns. Its hallmarks include the ability to obtain an image with a single detection element while measuring the image/video fewer times than the number of pixels/voxels; this can significantly reduce the computation required for video acquisition/encoding. Since our system relies on a single photon detector, it can also be adapted to image at wavelengths that are currently impossible with conventional CCD and CMOS imagers. We are currently testing a prototype design for the camera and include experimental results. <s> BIB003 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Scheme: Compressive Sensing <s> With the advent of a single-pixel camera, compressive imaging applications have gained wide interests. However, the design of efficient measurement basis in such a system remains as a challenging problem. In this paper, we propose a highly sparse and fast sampling operator based on the scrambled block Hadamard ensemble. Despite its simplicity, the proposed measurement operator offers universality and requires a near-optimal number of samples for perfect reconstruction. Moreover, it can be easily implemented in the optical domain thanks to its integer-valued elements. Several numerical experiments show that its imaging performance is comparable to that of the dense, floating-coefficient scrambled Fourier ensemble at much lower implementation cost. <s> BIB004 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Scheme: Compressive Sensing <s> In this paper, we propose and demonstrate a novel wireless camera network system, called CITRIC. The core component of this system is a new hardware platform that integrates a camera, a frequency-scalable (up to 624 MHz) CPU, 16MB FLASH, and 64MB RAM onto a single device. The device then connects with a standard sensor network mote to form a camera mote. The design enables in-network processing of images to reduce communication requirements, which has traditionally been high in existing camera networks with centralized processing. We also propose a back-end client/server architecture to provide a user interface to the system and support further centralized processing for higher-level applications. Our camera mote enables a wider variety of distributed pattern recognition applications than traditional platforms because it provides more computing power and tighter integration of physical components while still consuming relatively little power. Furthermore, the mote easily integrates with existing low-bandwidth sensor networks because it can communicate over the IEEE 802.15.4 protocol with other sensor network platforms. We demonstrate our system on three applications: image compression, target tracking, and camera localization. <s> BIB005 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Other Scheme: Compressive Sensing <s> Compressive sensing is a revolutionary idea proposed recently to achieve much lower sampling rate for sparse signals. For large wireless sensor networks, the events are relatively sparse compared with the number of sources. Because of deployment cost, the number of sensors is limited, and due to energy constraint, not all the sensors are turned on all the time. In this paper, the first contribution is to formulate the problem for sparse event detection in wireless sensor networks as a compressive sensing problem. The number of (wake-up) sensors can be greatly reduced to the similar level of the number of sparse events, which is much smaller than the total number of sources. Second, we suppose the event has the binary nature, and employ the Bayesian detection using this prior information. Finally, we analyze the performance of the compressive sensing algorithms under the Gaussian noise. From the simulation results, we show that the sampling rate can reduce to 25% without sacrificing performance. With further decreasing the sampling rate, the performance is gradually reduced until 10% of sampling rate. Our proposed detection algorithm has much better performance than the l 1 -magic algorithm proposed in the literature. <s> BIB006
Compressed Sensing (CS), also called compressive sampling, is a new paradigm that combines both signal acquisition and compression. Originally, CS is based on the work of Candès et al. BIB001 and Donoho BIB002 . This section is by no means an exhaustive overview of the literature on the CS or an in depth mathematical description of the CS theory, but rather it presents basic definition related to CS and some works related to the integration of CS within a VSN. Issues, such as formulating the problem of sparse event detection in sensor networks as a CS problem BIB006 , or the look for a suitable transformation that makes the signal sparse, are not considered. We refer our reader to BIB001 BIB002 for the theoretical concepts behind CS paradigm. Any real-valued, finite length, and compressible signal x ∈ R N can be represented in terms of basis matrix ψ i N i=1 , which is assumed to be orthogonal, where s is the N × 1 column vector of weighting coefficients The signal x is called K-sparse if K coefficients of s i coefficients of (1) are nonzero, and (N − K) are zero. The case of interest is when K N. In many applications, signals have only a few large coefficients. One of the most applications of sparse representation is in image compression, where a an image with dense (nonzero) pixel values can be encoded and compressed using a small fraction of the coefficients after a transformation, such as DCT or DWT. In fact, CS has been motivated by a striking observation: if the source signal s is K-sparse, s can be recovered from a small set of observations y ∈ R M under a linear projection on x, where Θ = φψ, and the measurements matrix φ ∈ R M×N is typically full rank with M < N. There exist infinitely many solutions of s that give rise to y in (2). The CS theory states that, for most full rank matrices φ that are incoherent to ψ, if s is K-sparse, it is the unique solution of a regularized 0 -minimization ( 0 -min) program BIB001 min s 0 subject to y = φψs. Unfortunately, solving (3) is both numerically unstable and NP-complete, requiring an exhaustive enumeration of all (N K) possible locations of the nonzero coefficients. Surprisingly, optimization based on the 1 norm, min s 1 subject to y = φψs, can exactly recover K-sparse signals and closely approximate compressible signals with high probability using only M ≥ cK log(N/K) iid Gaussian measurements BIB003 . The CS paradigm combines acquisition and compression in one step, which is totally different than conventional compression paradigms mentioned in this paper. This allows the reduction in power computation, which is very required in limited power applications such as VSN. The theory of CS seeks to recover a sparse signal from a small set of linear and nonadaptive measurements. The tremendous advantage of CS is to exhibit recovery methods that are computationally feasible, numerically stable, and robust against noise and packet loss over communication channels. Despite the aforementioned CS benefits, there still exists a huge gap between theory and imaging applications. In particular, it is unknown how to construct an efficient sensing operator and reduce the number of random measurements needed at the acquisition stage, particularly when the measurement is performed in spatial domain. The authors in  study the performance of CS for VSN images in terms of complexity and quality of reconstruction. In order to assess the performance of CS, the authors implement the block diagram shown in Figure 14 , where x is the input image of N × N pixels, and M is the number of measurements. The projection is performed onto a measurement matrix whose elements are generated by gathering 256 samples of the Fourier coefficients of the input image X along each of r radial lines in the frequency plane as explained in  . The authors show that it is possible to operate at very low data rates with reduced complexity and still achieving good image quality at the reception. Based on CS, an image representation scheme for VSN is proposed in  . The target image is firstly divided into two components through a wavelet transform: dense and sparse components. The former is encoded using JPEG or JPEG2000, while the latter is encoded using CS. In order to improve the rate distortion performance, the authors suggest leveraging the strong correlation between dense and sparse components using a piecewise autoregressive model. Given the measurements and the prediction of the sparse component as initial guess, they use projection onto convex set algorithm to reconstruct the sparse component. In general, the proposed work reduces the number of random measurements needed for CS reconstruction and the decoding computational complexity, compared to some CS methods. In BIB003 , the authors suggest algorithms and hardware implementation to support CS. In fact, they use a camera architecture, called single-pixel camera (which is detailed in  ), which employs a digital micromirror device to carry out optical calculations of linear projections of an image onto pseudorandom binary patterns. Its main characteristic is the ability to acquire an image with a single detection element. This can significantly reduce the computation and the power required for video acquisition and compression. In BIB004 , the authors propose a sparse and fast sampling operator based on the block Hadamard transform. Despite its simplicity, the proposed measurement operator requires a near optimal number of samples for perfect reconstruction. From the practical standpoint, the block Hadamard transform is easily implemented in the optical domain (e.g., using the singlepixel camera  ) and offers fast computation as well as small memory requirement. The suggested algorithm seems very efficient to be applied in power-constrained applications such as VSN. The unique work adopting CS paradigm in the context of VSN is that one developed in BIB005 , where both CS and JPEG are used for compression purpose. No details about the CS scheme are furnished in BIB005 .