A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source. <s> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> The author reviews recent multichannel models developed in psychophysiology, computer vision, and image processing. In psychophysiology, multichannel models have been particularly successful in explaining some low-level processing in the visual cortex. The expansion of a function into several frequency channels provides a representation which is intermediate between a spatial and a Fourier representation. The author describes the mathematical properties of such decompositions and introduces the wavelet transform. He reviews the classical multiresolution pyramidal transforms developed in computer vision and shows how they relate to the decomposition of an image into a wavelet orthonormal basis. He discusses the properties of the zero crossings of multifrequency channels. Zero-crossing representations are particularly well adapted for pattern recognition in computer vision. > <s> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> For the past few years, a joint ISO/CCITT committee known as JPEG (Joint Photographic Experts Group) has been working to establish the first international compression standard for continuous-tone still images, both grayscale and color. JPEG’s proposed standard aims to be generic, to support a wide variety of applications for continuous-tone images. To meet the differing needs of many applications, the JPEG standard includes two basic compression methods, each with various modes of operation. A DCT-based method is specified for “lossy’’ compression, and a predictive method for “lossless’’ compression. JPEG features a simple lossy technique known as the Baseline method, a subset of the other DCT-based modes of operation. The Baseline method has been by far the most widely implemented JPEG method to date, and is sufficient in its own right for a large number of applications. This article provides an overview of the JPEG standard, and focuses in detail on the Baseline method. <s> BIB003 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> An approach to image coding based on a fractal theory of iterated contractive transformations defined piecewise is described. The main characteristics of this approach are that it relies on the assumption that image redundancy can be efficiently captured and exploited through piecewise self-transformability on a block-wise basis, and it approximates an original image by a fractal image, obtained from a finite number of iterations of an image transformation called a fractal code. This approach is referred to as fractal block coding. The general coding-decoding system is based on the construction, for an image to be encoded, of a fractal code-a contractive image transformation for which the original image is an approximate fixed point-which, when applied iteratively on any initial image of the decoder, produces a sequence of images which converges to a fractal approximation of the original. The design of a system for the encoding of monochrome digital images at rates below 1 b/pixel is described. Ideas and extensions from the work of other researchers are presented. > <s> BIB004 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> The redundancy of the multiresolution representation has been clearly demonstrated in the case of fractal images, but it has not been fully recognized and exploited for general images. Fractal block coders have exploited the self-similarity among blocks in images. We devise an image coder in which the causal similarity among blocks of different subbands in a multiresolution decomposition of the image is exploited. In a pyramid subband decomposition, the image is decomposed into a set of subbands that are localized in scale, orientation, and space. The proposed coding scheme consists of predicting blocks in one subimage from blocks in lower resolution subbands with the same orientation. Although our prediction maps are of the same kind of those used in fractal block coders, which are based on an iterative mapping scheme, our coding technique does not impose any contractivity constraint on the block maps. This makes the decoding procedure very simple and allows a direct evaluation of the mean squared error (MSE) between the original and the reconstructed image at coding time. More importantly, we show that the subband pyramid acts as an automatic block classifier, thus making the block search simpler and the block matching more effective. These advantages are confirmed by the experimental results, which show that the performance of our scheme is superior for both visual quality and MSE to that obtainable with standard fractal block coders and also to that of other popular image coders such as JPEG. > <s> BIB005 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> The hexagonal grid has long been known to be superior to the more traditional rectangular grid system in many aspects in image processing and machine vision related fields. However, systematic developments of the mathematical backgrounds for the hexagonal grid are conspicuously lacking. The purpose of this paper is to study geometric transformations on the hexagonal grid. Formulations of the transformation matrices are carried out in a symmetrical hexagonal coordinate frame. A trio of new trigonometric functions are defined in this paper to facilitate the rotation transformations. A fast algorithm for rounding an arbitrary point to the nearest hexagonal grid point is also presented. > <s> BIB006 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <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> BIB007 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <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> BIB008 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> A fractal coder partitions an image into blocks that are coded via self-references to other parts of the image itself. We present a fractal coder that derives highly image-adaptive partitions and corresponding fractal codes in a time-efficient manner using a region-merging approach. The proposed merging strategy leads to improved rate-distortion performance compared to previously reported pure fractal coders, and it is faster than other state-of-the-art fractal coding methods. <s> BIB009 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> Fractal image compression has received much attention from the research community because of some desirable properties like resolution independence, fast decoding, and very competitive rate-distortion curves. Despite the advances made, the long computing times in the encoding phase still remain the main drawback of this technique. So far, several methods have been proposed in order to speed-up fractal image coding. We address the problem of choosing the best speed-up techniques for fractal image coding, comparing some of the most effective classification and feature vector methods--namely Fisher, Hurtgen, and Saupe--and a new feature vector coding scheme based on the block's mass center. Furthermore, we introduce two new coding schemes combining Saupe with Fisher, and Saupe with mass center coding scheme. Experimental results demonstrate both the superiority of feature vector techniques on classification and the effectiveness of combining Saupe and the mass center coding scheme, an approach that exhibits the best time-distortion curves. <s> BIB010 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> Fractal image encoding is a computationally intensive method of compression due to its need to find the best match between image subblocks by repeatedly searching a large virtual codebook constructed from the image under compression. One of the most innovative and promising approaches to speed up the encoding is to convert the range-domain block matching problem to a nearest neighbor search problem. This paper presents an improved formulation of approximate nearest neighbor search based on orthogonal projection and pre-quantization of the fractal transform parameters. Furthermore, an optimal adaptive scheme is derived for the approximate search parameter to further enhance the performance of the new algorithm. Experimental results showed that our new technique is able to improve both the fidelity and compression ratio, while significantly reduce memory requirement and encoding time. <s> BIB011 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> This paper presents a new adaptive search approach to reduce the computational complexity of fractal encoding. A simple but very efficient adaptive necessary condition is introduced to exclude a large number of unqualified domain blocks so as to speed-up fractal image compression. Furthermore, we analyzed an unconventional affine parameter that has better properties than the conventional luminance offset. Specifically, we formulated an optimal bit allocation scheme for the simultaneous quantizations of the usual scaling and the aforementioned unconventional affine parameter. Experiments on standard images showed that our adaptive search method yields superior performance over conventional fractal encoding. <s> BIB012 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> Region-based functionality offered by the MPEG-4 video compression standard is also appealing for still images, for example to permit object-based queries of a still-image database. A popular method for still-image compression is fractal coding. However, traditional fractal image coding uses rectangular range and domain blocks. Although new schemes have been proposed that merge small blocks into irregular shapes, the merging process does not, in general, produce semantically-meaningful regions. We propose a new approach to fractal image coding that permits region-based functionalities; images are coded region by region according to a previously-computed segmentation map. We use rectangular range and domain blocks, but divide boundary blocks into segments belonging to different regions. Since this prevents the use of standard dissimilarity measure, we propose a new measure adapted to segment shape. We propose two approaches: one in the spatial and one in the transform domain. While providing additional functionality, the proposed methods perform similarly to other tested methods in terms of PSNR but often result in images that are subjectively better. Due to the limited domain-block codebook size, the new methods are faster than other fractal coding methods tested. The results are very encouraging and show the potential of this approach for various internet and still-image database applications. <s> BIB013 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> Image quality assessment is an important issue addressed in various image processing applications such as image/video compression and image reconstruction. The peak signal-to-noise ratio (PSNR) with the L/sup 2/-metric is commonly used in objective image quality assessment. However, the measure does not agree very well with the human visual perception in many cases. A fuzzy image metric (FIM) is defined based on Sugeno's (1977) fuzzy integral. This new objective image metric, which is to some extent a proper evaluation from the viewpoint of the judgment procedure, is closely approximates the subjective mean opinion score (MOS) with a correlation coefficient of about 0.94, as compared to 0.82 obtained using the PSNR. Compared to the L/sup 2/-metric, we demonstrate that a better performance can be achieved in fractal coding by using the proposed FIM. <s> BIB014 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> INTRODUCTION <s> In this paper, a fast fractal encoding algorithm using simple classification scheme is proposed. During the encoding process, the range blocks and domain blocks are classified first. Then, each range block is limited to search in the corresponding domain class to find the best match. Since the searching space is reduced, the encoding speed is improved. Three classes of image blocks are defined, which are smooth class, diagonal/sub-diagonal edge class and horizontal/vertical edge class. The classification operation is performed using only the lowest horizontal and vertical DCT coefficients of the given block. Thus the classification scheme is simple and computationally efficient. Moreover, since the classification mechanism is designed according to the edge properties and the intrinsic idea of fractal coding, the quality of the decoded image can be preserved. The thresholds for the classifier are also adaptively determined from the range pool so as to reduce the overhead and to guarantee a stable speedup ratio of 3. Simulation results show that the stable speedup ratio of the proposed algorithm can be achieved and is independent of images while the quality of the decoded image is almost the same as that of the full search method. <s> BIB015
Data compression is a ubiquitous feature of modern society, occurring in many forms and in many settings. The variety of compression techniques is also very diverse, ranging from lossless compression of quantitative data  BIB001 through to lossy compression of diffuse data such as audio, image and movie files     . The advantage of lossy compression is that excellent compression ratios may be obtained by ignoring aspects of the data that are unimportant. For example, if the human eye is incapable of distinguishing between two images then it is reasonable to assume that any differences between them are not significant. It follows therefore that, by their nature, lossy compression algorithms tend to be designed with a particular application in mind; image data being a particularly common example. By far the most popular lossy compression algorithm for photographic types of image is the JPEG algorithm BIB003 . This is widely used in many areas of image storage and processing, from digital cameras through to photographic archives and libraries. For most purposes the JPEG algorithm is a highly satisfactory commercial product which is fast and efficient, allowing a choice between moderate compression ratio with small loss of quality, through to large compression ratio with a more noticeable loss of quality. Other image compression techniques are available BIB002 BIB004 . One such approach is based on Fractal Image Compression (FIC) BIB004 BIB009 BIB013 BIB008 BIB010 BIB012 BIB014 BIB011 BIB005 BIB015  BIB006 . This technique seeks to exploit affine redundancy that is present in typical images in order to achieve high compression ratios, generally maintaining good image quality with resolution independence. The main drawback of FIC however is that there is a very high computational cost associated with the encoding phase BIB007 . This is no doubt the main reason that the approach has remained less popular than faster alternatives such as JPEG. Nevertheless, there are a number of reasons why FIC should not be ignored. Whilst the encoding is expensive, the decoding is fast and straightforward, and allows smooth images to be recovered at all levels of resolution. Furthermore, the compression ratios achieved are often very high BIB008 and so if data density or data transmission rates are of more importance than real-time compression then FIC may be advantageous. Finally, as computer hardware continues to increase in its speed and decrease in its cost, resources that once seemed prohibitive, for encoding large quantities of data, would become widely accessible. In the light of the above discussion it seems timely therefore to revisit the FIC approach and consider its application in the context of modern computer architectures. Today's commodity processors are cheap and the combination of fast networking and switching, and portable parallel message passing libraries such as MPI  , mean that parallel computational environments are easily achievable in terms of both cost and the level of expertise required to maintain and program them. As demonstrated below, the fractal image compression algorithm itself is highly amenable to parallel implementation and so in this paper we are motivated to return to the FIC approach with a view to considering the main issues associated with its application on parallel architectures. This can ensure that the compression phase need not be the bottleneck that it once was, and the positive features of fractal compression will become available without this major drawback. The purpose of this short paper is therefore to provide a brief survey of stateof-the-art parallel fractal image compression methods, and to draw conclusion on how and what these techniques may offer in the future. The rest of the paper consists of an introduction to the iterated function theory that lies at the heart of FIC algorithms, followed by a brief description of the key aspects of FIC methods. This section sets the background for the main contribution of this paper-a survey of parallel fractal image compression. The paper then concludes with a discussion of what has been found and how it may be of importance in looking to the future.