A Survey of Parallel Algorithms for Fractal Image Compression <s> ( )< <s> From the contents: Recent theoretical results on fast encoding and decoding methods, various schemes for encoding images using fractal methods, and theoretical models for the encoding/decoding process.- Working C code for a fractal encoding/decoding scheme capable of encoding images in a few seconds, decoding at arbitrary resolution, and achieving high compression rations.- Experimental results from various schemes showing their capability and forming the basis for a sophisticated implementation.- A list of previously unresearched projects containing both new ideas and inhancements to the schemes discussed in the book.- A comparison of the fractal schemes in the book with JPEG, commercial fractal software, and wavelet methods. <s> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> ( )< <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> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> ( )< <s> In this paper a hybrid fractal and discrete cosine transform (DCT) coder is developed. Drawing on the ability of DCT to remove inter-pixel redundancies and on the ability of fractal transforms to capitalize on long-range correlations within the image, the hybrid coder performs an operationally optimal, in the rate-distortion sense, bit allocation among coding parameters. An orthogonal basis framework is used within which an image segmentation and a hybrid block-based transform are selected jointly. The selection of coefficients in the DCT component of the overall block transform is made a part of the optimization procedure. A Lagrangian multiplier approach is used to optimize the hybrid transform parameters together with the segmentation. Differential encoding of the DC coefficient is employed, with the scanning path based on a 3rd-order Hilbert curve. Simulation results show a significant improvement in quality with respect to the JPEG standard, an approach based on optimization of DCT basis vectors, as well as, the purely fractal techniques. <s> BIB003 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> ( )< <s> Fractal image compression is a new technique in image compression field based on Affine contractive transforms. Fractal image compression methods belong to different categories according to the different theories they are based on. All of those are discussed in this paper. In the end a conclusion is made to summarize the characters of fractal image compression. <s> BIB004 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> ( )< <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
In order to describe this in a little more detail, consider an arbitrary grayscale image, T, of size I × I pixels. This image may be partitioned into blocks of pixels in two different ways: the range blocks and the domain blocks. The range blocks, R, are a set of non-overlapping image blocks of size , which are denoted as The number of range blocks is and the original image T is the union of : . ( The domain blocks are also sub-blocks of the original image T, and they must cover the whole image. Unlike the range blocks however, the domain blocks may be overlapping (and usually are). Furthermore, the domain blocks should be larger in size than the range blocks. One way in which the domain blocks may be obtained is by sliding a window of size , where , throughout the image to construct the domain pool (the set of domain blocks). To encode a range block R, each of the blocks in the domain pool is scaled to the size of the range block, and is then compared to R with respect to intensity offset and contrast parameters, as well as the eight isometric transformations (the identity, reflections about the mid-horizontal and the mid-vertical axes, reflections about each diagonal, and rotations through 90°,180°and 270°). The set of contracted domain blocks is denoted as , where N D is the number of domain blocks in the domain pool. Each domain block has to be scaled and the eight isometries must then be applied. The resulting pool, C say, of size 8 × N D , is called a codebook pool. It is the domain block which has the closest match with R from the codebook pool which is selected as the best matched block. Details of this match are provided below however, for simplicity, we restrict this introduction to the special case where The overall form that the contraction takes is where each of the component transformations, ω i , must be defined. In the case of grayscale images these transformations take the form where s i controls the contrast and o i controls the brightness of the transformation BIB001 . The specific choice of parameters for the affine transformation are determined by minimizing the following quantity: . (4) Here I denotes the identity matrix of dimension N, and s and o are the above contrast and offset parameters, respectively, which must be determined in advance (see below) to calculate the distance between D and R. The contrast factor should ensure the contractility of the transformation. The metric is the mean square error (MSE) metric. This metric expresses the distance between two images or two range blocks. Assuming two images or image blocks, S and S ′ , possess n pixels with intensities S 1 , S 2 , …, Sn and S ′ 1 , S ′ 2 , …, S ′n , the distance between the blocks can be expressed as (5): The objective when determining s and o is to minimize R MSE . This is true when the partial derivatives of R MSE with respect to s and o are zero. Then, after a little algebra BIB004  , s can be found to be given by  and o to be given by (7): , . Finally, by substituting (6) and (7) into (4), the distance R MSE can be computed as (8): . (8) The domain block which results in the smallest value of R MSE is then chosen as the best matched block, and the corresponding parameters for the transformations may be encoded and stored. Note that it is possible to estimate the computational complexity of the encoding algorithm. Given an I × I pixel image to encode, where N D is the number of domain blocks and N R is the number of range blocks, then the time required to compute the best mapping is given by: Here τ t is the time to perform a transformation, τ d is the time to find the distance between two blocks, and τ c is the time to compare two distances. Since N D and N R are both of the order of I 2 , the overall computing time is at least O(I 4 ). It is important to note that each mapping exploits self-similarities that are present in most images at different scales. Thus, images with random content are not likely to be compressed very well as only few similarities of different sizes are likely to exist. Of course most images are not random and so FIC approach tends to be very effective. Not surprisingly there exists a significant amount of work that has been undertaken to develop variants on the basic algorithm above in order to improve performance BIB001 BIB002 BIB005  . Generally, attempts to speed up the fractal encoding consist of modifying these aspects BIB002 : the composition of the domain pool, the type of search used in block matching, and the representation/quantization of the transform parameters. One of the most important techniques applied in conjunction with the basic algorithm described above, is the use of the quad-tree data structure BIB001 . The basic idea is that we begin with quite a small range pool and a small domain pool and seek to find a satisfactory match to each range block from the set of domain blocks. If the mean square error is less than a desired tolerance then the match is deemed to be satisfactory but if it is not then the range block is split into four new range blocks, based upon its four quadrants. This process is repeated recursively until a sufficient quality is obtained. The main advantage of the approach is that it minimizes the number of range blocks required by having them as large as possible within any given region of the image. As we will see below however, when a parallel implementation of the algorithm is required, it adds considerable complexity to the load balancing across the processors. Other research in fractal image compression concentrates on investigating different transformations and improving search algorithms for matching transformations, each with the aim of decreasing the compression time   . An additional technique that many fractal compression algorithms employ to decrease their execution time is to use a classification scheme, typically based upon simple statistics of the blocks. For example, a sub-image may be classified according to its average grey-value and the variance of its four quadrants. Firstly, the sub-image is divided into its four quadrants which are numbered. The pixel values in the quadrant i of block r are r 1 i , r 2 i ,..., for i = 1,2,3,4. Secondly, the sum of the grey values in a quadrant is computed for each quadrant. Finally, a variance is computed for each quadrant. Member of the domain pool are then classified by their average and variance values and only a subset of these classes are searched for a match with each block in the range pool. The aim is of course to improve the speed without significantly affecting the quality of the compressed image. Apart from these attempts focusing on the coding speed, some hybrid coders, such as waveletbased and DCT-based fractal encoders, have been developed BIB003  . Various FIC side applications are now also explored in other fields such as image database indexing  and even face recognition  .