A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> A hybrid method for image compression based on the fractal geometry concept is presented. By combining the scanline subtraction and prediction mechanism with the yardstickbased compression method, higher compression rate can be achieved with good image quality. Furthermore, the performance of the algorithm is improved through error compensation. <s> BIB001 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> Iterated transformation theory-based coding (ITTBC) suffers from very high computational complexity in the encoding phase. This is due to its exhaustive search. This paper proposes a multiresolution tree search ITTBC (MTS-ITTBC) to reduce the encoding complexity. MTS-ITTBC searches the ITT-code using a multiresolution search-tree. The computational load of MTS-ITTBC is O(NlogN), while that of full search ITTBC is O(N/sup 2/), where N is the number of range blocks or domain blocks in an image. Numerical examples show that the encoding time of MTS-ITTBC can be reduced to 14% of that of the full search ITTBC, while the loss in quality relative to the full search ITTBC is about 0.5 dB in p-pSNR, which is visually negligible. > <s> BIB002 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> D ince the conception of fractal image compression by Michael F. Barnsley around 1987, the research literature on this topic has exper ienced a rapid growth. Following is a brief description of the major advances in the field and the largest, comprehensive bibliography published on this topic to date. While JPEG is becoming the industry standard for image compression technology, there is ongoing research in alternative methods. Currently there are at least two exciting new developments: wavelet based methods and fractal image compression. This article is intended to provide the reader with an overview and a resource of the research on the latter. We attempt to put the work into historical perspective and to provide the most comprehensive and up-to-date list of references in the field, truly a considerable number as shown in the following table. <s> BIB003 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> Fractal image compression and wavelet transform methods can be combined into a single compression scheme by using an iterated function system to generate the wavelet coefficients. The main advantage of this approach is to significantly reduce the tiling artifacts: operating in wavelet space allows range blocks to overlap without introducing redundant coding. Our scheme also permits reconstruction in a finite number of iterations and lets us relax convergence criteria. Moreover, wavelet coefficients provide a natural and efficient way to classify domain blocks in order to shorten compression times. Conventional fractal compression can be seen as a particular case of our general algorithm if we choose the Haar wavelet decomposition. On the other hand, our algorithm gradually reduces to conventional wavelet compression techniques as more and more range blocks fail to be properly approximated by rescaled domain blocks. <s> BIB004 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> In fractal image compression the encoding step is computationally expensive. We present a new technique for reducing the computational complexity. It is lossless, i.e., it does not sacrifice any image quality for the sake of the speedup. It is based on a codebook coherence characteristic to fractal image compression and leads to a novel application of the fast Fourier transform-based convolution. The method provides a new conceptual view of fractal image compression. This paper focuses on the implementation issues and presents the first empirical experiments analyzing the performance benefits of the convolution approach to fractal image compression depending on image size, range size, and codebook size. The results show acceleration factors for large ranges up to 23 (larger factors possible), outperforming all other currently known lossless acceleration methods for such range sizes. <s> BIB005 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> Fractal image compression has many features that makes it a powerful compression scheme, but it has been mainly restricted to archival storage due to its time consuming encoding algorithm. In this paper, we take a known quad-tree fractal encoding algorithm and design an ASIC parallel image processing array that can encode reasonably sized gray-scale images in real-time. In designing this architecture, we include novel optimizations that result in speed improvements at the algorithmic, architectural, and circuit levels. <s> BIB006 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> Presented in this paper are experimental results for a parallel implementation of a fractal image compression algorithm. The fractal image compression process exhibits a natural parallelism and the specific parallel implementation is shown to be beneficial for the execution speed of the algorithm. Furthermore, computational speed has been enhanced through an algorithmic modification employing a quadtree recomposition approach in which quadtree subblocks are iteratively combined into larger ranges for fractal encoding. Furthermore, classification schemes which serve to reduce the O(n/sup 4/) algorithmic complexity are explored. <s> BIB007 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> In this paper, a fast encoding algorithm is developed for fractal image compression. At each search entry in the domain pool, the mean square error (MSE) calculations of the given range block and the eight dihedral symmetries of the domain block are obtained simultaneously in the frequency domain, in which the redundant computations are all eliminated in the new encoding algorithm. It is shown in software simulation that the encoding time is about six times faster than that of the baseline method with almost the same PSNR for the retrieved image. The fast algorithm is performed to deal with the eight dihedral symmetries at each search entry. Therefore, it can be applied to various enhanced algorithms which are equipped with quadtree, classification, and other mechanisms. <s> BIB008 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> Fast algorithms for reducing encoding complexity of fractal image coding have recently been an important research topic. Search of the best matched domain block is the most computation intensive part of the fractal encoding process. In this paper, a fast fractal approximation coding scheme implemented on a personal computer based on matching in range block's neighbours is presented. Experimental results show that the proposed algorithm is very simple in implementation, fast in encoding time and high in compression ratio while PSNR is almost the same as compared with Barnsley's fractal block coding . <s> BIB009 </s> A Survey of Image Compression Algorithms for Visual Sensor Networks <s> Fractal Compression. <s> This paper presents a short survey of the key research work that has been undertaken in the application of parallel algorithms for Fractal image compression. The interest in fractal image compression techniques stems from their ability to achieve high compression ratios whilst maintaining a very high quality in the reconstructed image. The main drawback of this compression method is the very high computational cost that is associated with the encoding phase. Consequently, there has been significant interest in exploiting parallel computing architectures in order to speed up this phase, whilst still maintaining the advantageous features of the approach. This paper presents a brief introduction to fractal image compression, including the iterated function system theory upon which it is based, and then a review on the different techniques that have been, and can be, applied in order to parallelize the compression algorithm. <s> BIB010
Fractal image compression is a lossy compression technique based on fractal theory, which basically states that an image can be described by a set of fractals. Therefore, a compressed image using fractals contains a set of parameters allowing the decoder side to yield approximately a mathematical representation of the input image. Like VQ, fractal image compression is significantly different from conventional compression techniques such as JPEG, as it is not based on frequency transformations such as DCT or DWT. To the best understanding of the reader, let us introduce quickly fractal concept. Fractals are an iterative reproduction of a basic pattern, or geometric form, according to some mathematical transformations, including rotation, scaling, and translation. As explained in  , let us imagine a copying machine which makes three reduced copies of the input image; see Figure 11 . Imagine now that we fed the output of this machine back as input, the result will be an iteration of the input image. If we repeat this process many times on several input images, we will obtain Figure 12 , where the process converges to the same final image Figure 12(c) . With fractal image compression, we exploit the selfsimilarity property between objects within natural images, which is expressed as similar repeating patterns, to reduce the image's file size. The well-known image coding scheme based on fractals is summarized in three steps as follows BIB009 . (1) Range block partition: partitioning the original image into nonoverlapped blocks R i of size s × s, called ranges. (2) Domain block selection: for each R i , search in the image to find a block D i of size 2s × 2s (double size of range block) that is very similar to R i . (3) Mapping: select the mapping functions, which map the domain to the range by an affine transformation Usually, an affine transformation is applied when a domain block is mapped to a range block. Such affine transformation includes isometries (e.g., rotation and reflection), gray level scaling, and shift operation. In general, an affine transformation is given by: Initial image First copy Second copy (c) Figure 12 : The first three copies generated by the photocopying machine of Figure 11  . Fractal encoding is used to convert an input image to fractal codes, while fractal decoding is just the reverse, where a set of fractal codes are converted to reconstruct the input image. The main noticeable advantages of fractal image compression can be summarized as follows: high achievable compression ratio; good quality of the reconstructed image; simple decoding process which is viewed as a simple interpretation of the fractal codes and their translation into bitmap image; fractal images are stored or sent as mathematical formulas instead of bitmaps, which minimize the sorting/sending cost; and the possibility of image scaling without distortion compared to JPEG. Nevertheless, fractal image compression presents a main drawback related to the encoding process which is extremely computationally intensive and time consuming. This is due to the hard tasks of finding all fractals during the partition step and the search for the best match of fractals. After the first fractal-based image coder introduced by Jaquin in 1990, several variations of fractal coders have been proposed. Most of them focus on the improvement of the encoding process, especially on two main parts, partition BIB002 BIB005 and mapping BIB001 . Furthermore, some attempts to improve fractal compression encoding have tried to join fractal with some transforms, such as DCT and DWT. In  , there is some early works trying to combine fractal with DCT and wavelets. In BIB008 , the authors suggest a fast encoding algorithm for fractal image compression using the DCT inner product. One of the papers BIB004 is trying to join wavelet transform with fractal encoding. The main goal behind joining fractal with certain transforms is to take advantage of identifying more self-similarities within the frequency domain, in order to eliminate more redundant data and speed up the encoding process, which might reduce the computational complexity. Unfortunately, despite these improvements, the encoding process is still yet complex, and its application to VSN shortens the lifetime of the network. To the best of our knowledge, no work has been suggested for the use of fractals within the compression chain of VSN. The main justification could be the high computational complexity of the encoding process. This complexity limits the usefulness of fractally compressed data to powerconstrained applications such VSN. An open research issue might be the adaptation and the integration of fractal compression within VSN codecs handling only natural images. This is due to the fact that fractal image compression has proven its efficiency especially on this kind of images and provides very high compression ratios BIB004 . Joining fractal with certain transform including DCT or DWT is another key issue permitting the reduction of the encoding process complexity. Another open research issue concerns the introduction of parallelism while using fractals in VSN. This technique allows circumventing the computational load of the encoding fractal compression within a VS node. Various parallel implementations of a fractal image compression are proposed in the literature  BIB006 BIB007 . A reader interested by this subject is invited to consult BIB003 BIB010 .