A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by granularity <s> The recent application of fractal techniques is a significant development in image compression. These fractal methods provide very high compression ratios for natural scenes. Fractal methods have the advantage of being resolution independent. However, their encoding complexity is O(n/sup 4/) for an n/spl times/n pixel image. This prohibits their real-time application. We propose a massively parallel implementation on a pyramid machine that yields a considerable speedup. This implementation reduces the fractal encoding complexity to O(n/sup 2/). Our parallel method has much better performance than other existing methods. > <s> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by granularity <s> In this paper, we present a parallel fractal image compression using the programmable graphics hardware. The main problem of fractal compression is the very high computing time needed to encode images. Our implementation exploits SIMD architecture and inherent parallelism of recently graphic boards to speed-up baseline approach of fractal encoding. The results we present are achieved on cheap and widely available graphics boards. <s> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by granularity <s> Data compression has become an important issue in relation to storage and transmission. This issue is especially true for databases consisting of a large number of detailed computer images. Many methods have been proposed in recent years for achieving high compression ratios for compressed image storage. A very promising compression technique, in terms of compression ratios, is fractal image compression. Fractal image compression exploits natural affine redundancy present in typical images to achieve a high compression ratio in a lossy compression format. Fractal based compression algorithms, however, have high computational demands. To obtain faster compression, a sequential fractal image compression algorithm may be translated into a parallel algorithm. This translation takes advantage of the inherently parallel nature, from a data domain viewpoint, of the fractal transform process. > <s> BIB003 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by granularity <s> ABSTRACT Fractal image compression is computationally expensive. Therefore speedup techniques are required to achieve time demands comparable to other compression techniques. In this paper we combine sequential and parallel techniques suitable for MIMD architectures which moves this compression scheme closer to real-time processing.The algorithms introduced are especially designed for memory-critical environments. Keywords: Fractal Image Compression, Parallel Algorithms, MIMD Architectures 1 INTRODUCTION Fractal image compression4'14 has generated much interest in the image compression community as com-petitor5 with well established compression techniques (e.g. DCT-JPEG22) and new emerging technologies (e.g.wavelets2"). One of the main drawbacks of conventional fractal image coding is the high encoding complexity(whereas decoding complexity is much lower) compared to e.g. transform coding. On the other hand fractal coding offers promising performance in terms of image quality.For these reasons speedup techniques are necessary in order to accelerate the execution speed. Two differentapproaches can be distinguished: <s> BIB004 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by granularity <s> This paper proposes a parallel architecture for quadtree-based fractal image coding. This architecture is capable of performing the fractal image coding based on quadtree partitioning without the external memory for the fixed domain pool. Since a large domain block consists of small domain blocks, the calculations of distortion for all kinds of domain blocks are performed by the summation of the distortions for the maximum-depth domain pool which is extracted from the smallest range blocks of the neighbor processors. Fast comparison module is proposed for this architecture. This module can compute the distortions between range blocks and their eight isometric transformations by one full rotation around the center. <s> BIB005
A very simple view of parallel algorithms typically classes them as being either "fine grained" or "coarse grained". Interestingly however, for parallel fractal image compression, a range of algorithms have been developed over the time that have far more that just two different levels of granularity. At one extreme BIB001 proposes using n 2 processors for an n × n pixel image, with each processor working with a single pixel of the image. This is extremely fine-grained parallelism, where computations such the sums appearing in equations  or (7) are computed in parallel. On the other end of scale, the image can be partitioned amongst the available processors for each processor to then simultaneously apply the sequential fractal compression algorithm on its own sub-image without any communication  . This embarrassingly parallel algorithm is extremely coarse grained but suffers from the drawback that the quality of the compressed image will be inferior to that obtained using the sequential algorithm. This is because each processor is only working with a subset of the complete domain pool and so will not generally get as good a match with its range blocks as will be obtained using the sequential algorithm. For the remaining part of this review we will only consider parallel algorithms which are able to reproduce the compressed images that are obtained using accepted sequential algorithms. Intermediate levels of granularity may be found in the work of other authors. For example, BIB002   present descriptions of some relatively fine-grained algorithms. These involve individual processing units being responsible for calculations on small sets of pixels. For example "pixel processors" store 4 × 4 pixel maps in  . Coarser grained algorithms tend to partition the range pool amongst the processors and then require each processor to find a suitable match to its own subset of the range pool from all of the available domains, e.g. BIB003 BIB004   . In some cases the entire domain pool is directly available to each processor and in others it must be partitioned and communicated: this issue is discussed in more detail in section 3.2 below. A slightly less coarse grained algorithm is presented in BIB005 which assumes that the number of available processors is equal to the number of range blocks and that the domain blocks are passed through the system in a pipeline, or systolic architecture.