A Survey of Parallel Algorithms for Fractal Image Compression <s> Modifications to the standard compression algorithms <s> Fractal image compression is a technique based on the representation of an image by a contractive transform, on the space of images, for which the fixed point is close to the original image. This broad principle encompasses a very wide variety of coding schemes, many of which have been explored in the rapidly growing body of published research. While certain theoretical aspects of this representation are well established, relatively little attention has been given to the construction of a coherent underlying image model that would justify its use. Most purely fractal-based schemes are not competitive with the current state of the art, but hybrid schemes incorporating fractal compression and alternative techniques have achieved considerably greater success. This review represents a survey of the most significant advances, both practical and theoretical, since the publication of Jacquin's (1990) original fractal coding scheme. <s> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Modifications to the standard compression algorithms <s> Since fractal image compression is computationally very expensive, speed-up techniques are required in addition to parallel processing in order to compress large images in reasonable time. In this paper we discuss parallel fractal image compression algorithms suited for MIMD architectures which employ block classification as speed-up method. <s> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Modifications to the standard compression algorithms <s> In this paper we present a fast fractal encoding method based on an intelligent search of a Standard Deviation (STD) value between range and domain blocks. First, we describe the basic fractal image compression theory and an improved bit allocation scheme for Jacquin's Iterated Function System (IFS) parameter. Experimental results show that using a Fixed Scale Parameter (FSP) can shorten encoding time without significantly affecting reconstructed image quality. Second, we present a search algorithm based on the STD introduced by Tong. We enhance Tong's STD search algorithm by introducing a domain Intelligent Classification Algorithm (ICA) based on STD-classified domain blocks. The domain block search pool is pruned by eliminating multiple domain blocks with similar STD values. We refer to this pruning as the De-Redundancy Method (DRM). The domain search process is adaptive with the range block STD value of interest controlling the size of the domain pool searched. We refer to this process as the Search Number Adaptive Control (SNAC). Finally, we present experimental results showing the efficiency of the proposed method, noting a significant improvement over Tong's original STD method without significant loss in the reconstructed image quality. <s> BIB003 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Modifications to the standard compression algorithms <s> In order to improve the efficiency and speed of match seeking in fractal compression, this paper presents an Average-Variance function which can make the optimal choice more efficiently. Based on it, we also present a fast optimal choice fractal image compression algorithm and an optimal method of constructing data tree which greatly improve the performances of the algorithm. Analysis and experimental results proved that it can improve PSNR over 1 dB and improve the coding speed over 30--40% than ordinary optimal choice algorithms such as algorithm based on center of gravity and algorithm based on variance. It can offer much higher optimal choice efficiency, higher reconstructive quality and rapid speed. It's a fast fractal encoding algorithm with high performances. <s> BIB004 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Modifications to the standard compression algorithms <s> Fractals can be an effective approach for several applications other than image coding and transmission: database indexing, texture mapping, and even pattern recognition problems such as writer authentication. However, fractal-based algorithms are strongly asymmetric because, in spite of the linearity of the decoding phase, the coding process is much more time consuming. Many different solutions have been proposed for this problem, but there is not yet a standard for fractal coding. This paper proposes a method to reduce the complexity of the image coding phase by classifying the blocks according to an approximation error measure. It is formally shown that postponing range\slash domain comparisons with respect to a preset block, it is possible to reduce drastically the amount of operations needed to encode each range. The proposed method has been compared with three other fractal coding methods, showing under which circumstances it performs better in terms of both bit rate and/or computing time. <s> BIB005 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Modifications to the standard compression algorithms <s> Fractal video compression is a relatively new video compression method. Its attraction is due to the high compression ratio and the simple decompression algorithm. But its computational complexity is high and as a result parallel algorithms on high performance machines become one way out. In this study we partition the matching search, which occupies the majority of the work in a fractal video compression process, into small tasks and implement them in two distributed computing environments, one using DCOM and the other using .NET Remoting technology, based on a local area network consists of loosely coupled PCs. Experimental results show that the parallel algorithm is able to achieve a high speedup in these distributed environments. <s> BIB006
So far we have only discussed the parallel implementation of "standard" fractal compression algorithms. Typically these require each range block to be compared against the image of all domain blocks in the domain pool. If a satisfactory match is not found an adaptive quad-tree data structure will also be used. There are however a number of techniques that have been developed in an attempt to improve the speed of the sequential fractal compression algorithms without significantly reducing the quality of the compressed image. These complexity reduction schemes do have an effect on the quality of the compressed image however they are designed with the aim of minimizing this effect. A number of such techniques are described in BIB001 . Current interest in this topic appears to be as active as ever, e.g. BIB003 BIB004 BIB005 . A number of authors have attempted to combine such complexity reduction schemes with their parallel algorithms, as discussed in BIB002 for example. Typically these schemes are based upon the use of classification techniques such as that outlined in section 2, where the elements of the range and domain pools are assigned to different classes and range elements of a given class are only compared against the images of domain blocks from the same class. For example, in BIB006 , this block classification approach is used to create 72 different classes based 10 upon the mean and variance values of the grey values in each block. Many other discrete feature methods exist however and can be incorporated within parallel algorithms, BIB002 .