A Review of the Fractal Image Coding Literature
---
paper_title: Fractal Image Compression

paper_content:

The top-selling multimedia encyclopedia Encarta, published by Microsoft Corporation, includes on one CD-ROM seven thousand color photographs which may be viewed interactively on a computer screen. The images are diverse; they are of buildings, musical instruments, people’s faces, baseball bats, ferns, etc. What most users do not know is that all of these photographs are based on fractals and that they represent a (seemingly magical) practical success of mathematics. Research on fractal image compression evolved from the mathematical ferment on chaos and fractals in the years 1978–1985 and in particular on the resurgence of interest in Julia sets and dynamical systems. Here I describe briefly some of the underlying ideas. Following Hutchinson [7], see also [5], consider first a finite set of contraction mappings wi, each with contractivity factor s < 1, taking a compact metric space X into itself, i = 1,2, . . .N. Such a setup is called an iterated function system (IFS), [1]. Use this IFS to construct a mapping W from the space H of nonempty compact subsets of X into itself by defining, in the self-explanatory notation, W (B) = N ⋃
---
paper_title: Introductory Functional Analysis with Applications

paper_content:

Metric Spaces. Normed Spaces Banach Spaces. Inner Product Spaces Hilbert Spaces. Fundamental Theorems for Normed and Banach Spaces. Further Applications: Banach Fixed Point Theorem. Spectral Theory of Linear Operators in Normed Spaces. Compact Linear Operators on Normed Spaces and Their Spectrum. Spectral Theory of Bounded Self--Adjoint Linear Operators. Unbounded Linear Operators in Hilbert Space. Unbounded Linear Operators in Quantum Mechanics. Appendices. References. Index.
---
paper_title: Fractal Block Coding of Digital Video

paper_content:

A video coding method is proposed which is based upon fractal block coding. The method utilizes a novel three-dimensional partitioning of input frames for which a number of efficient block-matching search methods can be used, and permits spatio-temporal splitting of the input blocks to improve overall-encoding quality. After describing the basic fractal block coding algorithm, the details of the proposed three-dimensional algorithm are presented along with encoding and decoding results from two standard video test sequences, representative of video-conferencing data. These results indicate that average compression rates ranging from 40 to 77 can be obtained with subjective reconstruction quality of video-conferencing quality. The results also indicate that, in order to meet the compression rates required for very low bit rate coding, it is necessary to employ additional techniques such as entropy encoding of the fractal transformation coefficients. >
---
paper_title: Rate buffered fractal video

paper_content:

We report real time fractal coding of 176 by 144 luminance images on a 33 MHz i-486 computer. With a zero searching first order (bilinear) Bath fractal transform, square blocks of 64 pixels are coded in 250 /spl mu/sec and decoded in 200 /spl mu/sec. This permits coding of 40% of each frame in a 25 Hz video sequence, or full coding at 10 Hz. By transmitting only those blocks of greatest error, we can obtain any degree of data compression. Useful video sequences of talking heads have been achieved with rates as low as 40 kbits/sec. We describe the techniques used, give illustrations of the degradation, and show the evolution of the errors in the decoded sequence as various events occur. The overall compression at 40 kbits/sec is 99:1, with further error reductions possible. >
---
paper_title: Vector Space Formulation of Two-Dimensional Signal Processing Operations

paper_content:

Abstracts Signal processing operations on two-dimensional fields of data can be cast into a vector space formulation. This formulation often leads to a simplified analysis of two-dimensional processing systems and to the discovery of more efficient computational algorithms. This paper considers the general representation of two-dimensional fields as vectors and discusses common types of operators on these data vectors. Particular emphasis is given to various forms of the superposition operation. Computation of superposition operations using unitary transform techniques is analyzed.
---
paper_title: Fractal Image Compression: Theory and Application

paper_content:

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.
---
paper_title: Fractals Everywhere

paper_content:

Focusing on how fractal geometry can be used to model real objects in the physical world, this up-to-date edition featurestwo 16-page full-color inserts, problems and tools emphasizing fractal applications, and an answers section. A bonus CD of an IFS Generator provides an excellent software tool for designing iterated function systems codes and fractal images.
---
paper_title: An inner product space approach to image coding by contractive transformations

paper_content:

Consideration is given to modeling of arbitrary digital gray tone images as the fixed points of contractive transformations on the image space. The transformation is designed to exploit a form of image redundancy called piecewise self-similarity. Results from inner product space theory are used to optimize the transformation within a class of affine transformations. The resulting transformation is described by a small amount of information compared to the original image, and its piecewise self-similar fixed point, found by successively iterating the transformation from any initial image, is close to the original image. Results are improved compared to earlier results with this technique. >
---
paper_title: A hybrid fractal-DCT coding scheme for image compression

paper_content:

We introduce a new way to use fractal coding for image compression, based on the parallel use of a fractal encoder and a DCT encoder. The two encoders are given the complementary roles to capture the information of edge and smooth variation, and the information of detail respectively. We show the advantage of using this hybrid coding scheme over the use of a fractal encoder alone, or a DCT encoder alone. This coding scheme is also the occasion to demonstrate a new concept of coding by nonlinear feature separation based on regular and uniform algorithms, suitable for real-time VLSI implementation.
---
paper_title: JPEG: Still Image Data Compression Standard

paper_content:

Foreword. Acknowledgments. Trademarks. Introduction. Image Concepts and Vocabulary. Aspects of the Human Visual Systems. The Discrete Cosine Transform (DCT). Image Compression Systems. JPEG Modes of Operation. JPEG Syntax and Data Organization. Entropy Coding Concepts. JPEG Binary Arithmetic Coding. JPEG Coding Models. JPEG Huffman Entropy Coding. Arithmetic Coding Statistical. More on Arithmetic Coding. Probability Estimation. Compression Performance. JPEG Enhancements. JPEG Applications and Vendors. Overview of CCITT, ISO, and IEC. History of JPEG. Other Image Compression Standards. Possible Future JPEG Directions. Appendix A. Appendix B. References. Index.
---
paper_title: Fractal image coding based on a theory of iterated contractive image transformations

paper_content:

The notion of fractal image compression arises from the fact that the iteration of simple deterministic mathematical procedures can generate images with infinitely intricate geometries known as fracial images [2]. The purpose of research on fractalbased digital image coding is to solve the inverse problem of constraining this complexity to match the realworld complexity of realworld images. In this. paper we propose a fractal image coding technique based on a mathematical theory of iterated transformations [1 2 3 7] which encompasses deterministic fractal geometry. Initial results were reported in [7 8]. The main characteristics of this technique are that (i) it is fractal in the sense that it approximates an original image by a fractal image and (ii) it is a blockcoding technique which relies on the assumption that image redundancy can be efficiently exploited through blockwise selfiransformabiliiy. We therefore refer to it as fracial blockcoding. The codingdecoding system is based on the construction for each original image given to encode of a specific image transformation which when iterated on any initial image produces a sequence of images which converges to a fractal approximation of the original. We show how to design such coders and thoroughly describe the implementation of a system for monochrome still images. Extremely promising coding results were obtained.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Image coding based on a fractal theory of iterated contractive image transformations

paper_content:

The author proposes an independent and novel approach to image coding, based on a fractal theory of iterated transformations. The main characteristics of this approach are that (i) it relies on the assumption that image redundancy can be efficiently exploited through self-transformability on a block-wise basis, and (ii) it approximates an original image by a fractal image. The author refers to the approach as fractal block coding. The coding-decoding system is based on the construction, for an original image to encode, of a specific image transformation-a fractal code-which, when iterated on any initial image, produces a sequence of images that converges to a fractal approximation of the original. It is shown how to design such a system for the coding of monochrome digital images at rates in the range of 0.5-1.0 b/pixel. The fractal block coder has performance comparable to state-of-the-art vector quantizers.
---
paper_title: Faster Fractal Image Compression Using Quadtree Recomposition

paper_content:

In this paper, we present a fractal image compression algorithm employing a new quadtree recomposition (QR) approach. In this approach, quadtree subblocks of an image are iteratively recombined into larger blocks for fractal coding. For complex images, this approach exhibits superior runtime performance, when compared to a classical quadtree decomposition (QD) scheme, while maintaining high fidelity for reconstructed images. Quantitative results include an evaluation of attained compression ratios, runtime performance, and signal-to-noise ratios (SNR) for reconstructed images.
---
paper_title: Variance-based quadtrees in fractal image compression

paper_content:

In fractal image compression, quadtree image partitions are commonly used. The authors show that the error-based splitting criterion for nodes in the quadtree image partition can be replaced by a test based on block variances. This simplifies and speeds up the algorithm for fractal image compression without harming the rate-distortion performance of the encoder.
---
paper_title: Optimal hierarchical partitions for fractal image compression

paper_content:

In fractal image compression a partitioning of the image is required. In this paper we discuss the construction of rate-distortion optimal partitions. We begin with a fine scale partition which gives a fractal encoding with a high bit rate and a low distortion. The partition is hierarchical, thus, corresponds to a tree. We employ a pruning strategy based on the generalized BFOS algorithm. It extracts subtrees corresponding to partitions and fractal encodings which are optimal in the rate-distortion sense. First results are included for the case of fractal encodings based on rectangular (HV) partitions. We also provide a comparison with greedy partitions based on the traditional collage error criterion or just using block variance.
---
paper_title: Region-based fractal image compression with quadtree segmentation

paper_content:

Fractal image coding is a novel technique for still image compression. A low bit rate region-based fractal image compression algorithm is proposed and several techniques are included as follows. First, we improve the performance of quadtree segmentation by an adaptive threshold. Then, a merging scheme is employed to the resulting quadtree segmentation that combines several similar blocks into a small number of regions. We also provide a quadtree-based segmented chain code to efficiently record the contours of the regions. The experimental results show that the proposed scheme has the lowest bit rate among the existing schemes at the same level of image quality.
---
paper_title: Region-based fractal image compression using heuristic search

paper_content:

Presents work carried out on fractal (or attractor) image compression. The approach relies on the assumption that image redundancy can be efficiently exploited through self-transformability. The algorithms described utilize a novel region-based partition of the image that greatly increases the compression ratios achieved over traditional block-based partitionings. Due to the large search spaces involved, heuristic algorithms are used to construct these region-based transformations. Results for three different heuristic algorithms are given. The results show that the region-based system achieves almost double the compression ratio of the simple block-based system at a similar decompressed image quality. For the Lena image, compression ratios of 41:1 can be achieved at a PSNR of 26.56 dB. >
---
paper_title: A new fractal image coding scheme employing blocks of variable shapes

paper_content:

In the fractal coding schemes proposed so far based on iterated function systems, an image is represented by a self-affine set of square blocks. We propose a scheme of fractal image coding with blocks of variable shapes. In this scheme, the range blocks are determined by the so-called splitting-and-merging method. Also, we define two kinds of range blocks, shade blocks and non-shade blocks, according to the variance of the brightness level inside blocks. By this method, range blocks both of various size and of various shapes are extracted from an input image. The larger range blocks result in the a greater reduction of the total number of blocks and, hence, the amount of encoded bits. Because of the specified order used in merging of primitive blocks, only a few more bits are added for each range block to encode its shape. The results of computer simulation with a test gray-scale image show that compared with the conventional scheme using square range blocks, the proposed coding scheme reduces about 0.2 bits/pel to achieve almost the same reproduced quality.
---
paper_title: Partitioning Complexity Issue for Iterated Functions Systems based Image Coding

paper_content:

Keywords: LTS1 Reference LTS-CONF-1994-012 Record created on 2006-06-14, modified on 2016-08-08
---
paper_title: Fractal image compression based on Delaunay triangulation and vector quantization

paper_content:

Presents a new scheme for fractal image compression based on adaptive Delaunay triangulation. Such a partition is computed on an initial set of points obtained with a split and merge algorithm in a grey level dependent way. The triangulation is thus fully flexible and returns a limited number of blocks allowing good compression ratios. Moreover, a second original approach is the integration of a classification step based on a modified version of the Lloyd algorithm (vector quantization) in order to reduce the encoding complexity. The vector quantization algorithm is implemented on pixel histograms directly generated from the triangulation. The aim is to reduce the number of comparisons between the two sets of blocks involved in fractal image compression by keeping only the best representative triangles in the domain blocks set. Quality coding results are achieved at rates between 0.25-0.5 b/pixel depending on the nature of the original image and on the number of triangles retained.
---
paper_title: A mixed triangular and quadrilateral partition for fractal image coding

paper_content:

This paper presents a new partitioning scheme for fractal image coding, based on triangles and quadrilaterals. The aim is to have the advantage of the triangles over the square and rectangular blocks, in terms of adaptivity to the image (reduction of the block effect), and to reduce the blocks number by grouping neighboring triangles into quadrilaterals. Quadrilaterals permit a reduction of the number of local contractive affine transformations composing the fractal transform, and thus to increase the compression ratio, while preserving the visual quality of the decoded image.
---
paper_title: Adaptive Delaunay triangulation for attractor image coding

paper_content:

The principle of attractor image coding presented in this paper is based on the theory of IFS (iterated function systems). The algorithm exploits piece-wise similarities between block of different sizes. To improve the algorithms based on regular and square blocks, we propose an adaptive Delaunay triangulation of the image support. The originality of the method is to map the triangles on specific parts of the image in order to have lots of similarities between them.
---
paper_title: Attractor image coding using lapped partitioned iterated function systems

paper_content:

The usual attractor coding technique is to partition a given image into a number of non-overlapping range blocks. Each block of the partition is expressed as the contractive transformation of another part of the image. However, the non-overlapping partitioning induces blocking artifacts which is highly disturbing to the human visual system. In this work, a novel coding scheme using iterated function systems with lapped range blocks (LPIFS) is proposed. Each range block laps with its adjacent blocks through a weighing window which has diminishing magnitudes towards its borders. In order to avoid blurring of image details, the transformation parameters are computed such that the aliasing error is compensated. The contractivity of the proposed transformation is also proved. Experiments show a very significant improvement of the visual quality of the decoded images with nearly no loss in image details.
---
paper_title: Overlapped adaptive partitioning for image coding based on the theory of iterated functions systems

paper_content:

Memoryless blockwise partitioning induces blockiness artifacts highly disturbing to the human visual system. This paper presents a new partitioning with overlapped blocks in the context of image coding based on iterated transformations systems. Each block of the partition is extended by n pixels. As usual each cell is expressed as the contractive transformation of another part of the image. During the decoding, values of pixels corresponding to overlapped regions are computed as the weighted sum of the different contributions leading to that pixel. This overlapped partitioning is embedded in a quadtree segmentation of the image support. In order to avoid blurring effects in small blocks while maintaining efficiency in bigger ones, the overlapping width n is a function of the block size. Simulations show a very significant improvement of the visual quality of decoded images with no increase of the bitrate request. >
---
paper_title: Orthonormal Fractal Image Encoding Using Overlapping Blocks

paper_content:

This paper presents a novel approach to partitioned fractal image encoding. In this we seek to address a number of problems with earlier fractal encodings. These are: the artefacts associated with the block based approaches at high compression ratios; accuracy limitations imposed by the constraint that only one domain block is used to construct each range block; convergence problems which have required that constraints be imposed on the scaling coefficients to ensure that the mapping functions are contractive. These problems are addressed with a technique based on an orthonormal basis expansion using overlapping blocks, where the basis is partly fixed and partly derived from the image in such a way as to take advantage of local interscale self similarity. A fractal image codec based on this technique, which we call the Lapped Orthogonal Fractal Transform (LOFT), is described and tested, and the results are compared to those of other codecs.
---
paper_title: Partitioning Complexity Issue for Iterated Functions Systems based Image Coding

paper_content:

Keywords: LTS1 Reference LTS-CONF-1994-012 Record created on 2006-06-14, modified on 2016-08-08
---
paper_title: Region-based fractal image compression with quadtree segmentation

paper_content:

Fractal image coding is a novel technique for still image compression. A low bit rate region-based fractal image compression algorithm is proposed and several techniques are included as follows. First, we improve the performance of quadtree segmentation by an adaptive threshold. Then, a merging scheme is employed to the resulting quadtree segmentation that combines several similar blocks into a small number of regions. We also provide a quadtree-based segmented chain code to efficiently record the contours of the regions. The experimental results show that the proposed scheme has the lowest bit rate among the existing schemes at the same level of image quality.
---
paper_title: Region-based fractal image compression using heuristic search

paper_content:

Presents work carried out on fractal (or attractor) image compression. The approach relies on the assumption that image redundancy can be efficiently exploited through self-transformability. The algorithms described utilize a novel region-based partition of the image that greatly increases the compression ratios achieved over traditional block-based partitionings. Due to the large search spaces involved, heuristic algorithms are used to construct these region-based transformations. Results for three different heuristic algorithms are given. The results show that the region-based system achieves almost double the compression ratio of the simple block-based system at a similar decompressed image quality. For the Lena image, compression ratios of 41:1 can be achieved at a PSNR of 26.56 dB. >
---
paper_title: Comparison of fractal methods with discrete cosine transform (DCT) and wavelets

paper_content:

The paper contains a brief description of fractal image compression methods with sample compression results. We also present comparative results between two fractal schemes, discrete cosine transform and a wavelet method. We show that, with the PSNR as a measure of image quality, some fractal schemes perform best over the range of compressions of most interest.
---
paper_title: Image coding based on a fractal theory of iterated contractive image transformations

paper_content:

The author proposes an independent and novel approach to image coding, based on a fractal theory of iterated transformations. The main characteristics of this approach are that (i) it relies on the assumption that image redundancy can be efficiently exploited through self-transformability on a block-wise basis, and (ii) it approximates an original image by a fractal image. The author refers to the approach as fractal block coding. The coding-decoding system is based on the construction, for an original image to encode, of a specific image transformation-a fractal code-which, when iterated on any initial image, produces a sequence of images that converges to a fractal approximation of the original. It is shown how to design such a system for the coding of monochrome digital images at rates in the range of 0.5-1.0 b/pixel. The fractal block coder has performance comparable to state-of-the-art vector quantizers.
---
paper_title: A mixed triangular and quadrilateral partition for fractal image coding

paper_content:

This paper presents a new partitioning scheme for fractal image coding, based on triangles and quadrilaterals. The aim is to have the advantage of the triangles over the square and rectangular blocks, in terms of adaptivity to the image (reduction of the block effect), and to reduce the blocks number by grouping neighboring triangles into quadrilaterals. Quadrilaterals permit a reduction of the number of local contractive affine transformations composing the fractal transform, and thus to increase the compression ratio, while preserving the visual quality of the decoded image.
---
paper_title: Fractal Image Compression Using Iterated Transforms

paper_content:

This article presents background, theory, and specific implementation notes for an image compression scheme based on fractal transforms. Results from various implementations are presented and compared to standard image compression techniques.
---
paper_title: RATE/DISTORTION PERFORMANCE OF FRACTAL TRANSFORMS FOR IMAGE COMPRESSION

paper_content:

We study the fidelity/compression performance of fractal image coding, and evaluate the merits or otherwise of a number of complexity options. We can first of all choose a quantization scheme for the transmission of coefficients which limits the code alphabet, according to permissible degradations. This alphabet can then be entropy coded to eliminate redundancy so that the compression efficiency of a range of implementation options can be studied and related to objective and subjective measures of degradation. We find rotations and reflections of little value. A limited degree of searching may be of benefit within image regions of high edge value, but in general more is gained by using a higher order fractal function than by searching.
---
paper_title: A nonlinear model for fractal image coding

paper_content:

After a very promising start, progress in fractal image coding has been relatively slow recently. Most improvements have been concentrating on better adaptive coding algorithms and on search strategies to reduce the encoding time. Very little has been-done to challenge the linear model of the fractal transformations used so far in practical applications. In this paper, we explain why effective nonlinear transformations are not easy to find and propose a model based on conformal mappings in the geometric domain that are a natural extension of the affine model. Our compression results show improvements over the linear model and support the hope that a deeper understanding of the notion of self-similarity would further advance fractal image coding.
---
paper_title: Fast block matching method for image data compression based on fractal models

paper_content:

This paper presents a fast block matching technique for image data compression based on fractal models. In fractal coding, domain blocks in an image are searched and the one most similar to a range block is selected as the best matching domain block. We propose a fast search method to improve the encoding time and the data compression rate. In our method a positive aim at a domain block consists of the inner pixels of the range block and the outer only one or two pixels of the range block. The method has been tested on real image data with good results.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Advances in block based fractal coding of still pictures

paper_content:

Fractal coding is a new technique for compressing images, which exploits similarities in different parts of the picture. For example, with a picture of a fern one can see easily where these similarities lie, each fern leaf resembling a smaller fern. With a more general picture it is not as obvious where these similarities lie. That is because attention is dominated by the macroscopic detail in the picture. If the picture is examined at a microscopic level by blocking the picture into 4*4 pixel blocks, then the 4*4 blocks show remarkable similarities: blocks that are predominantly flat, blocks with an edge across them, and so forth. >
---
paper_title: A novel fractal block-coding technique for digital images

paper_content:

An approach to digital image coding, rooted in iterated transformation theory (ITT) and referred to as ITT-based coding, is proposed. It is a fractal block-coding method which relies on the assumption that image redundancy can be efficiently exploited through block self-transformability. The coding-decoding system is based on the construction, for any given original image to encode, of an image transformation of a special kind which (when iterated on any initial image) produces a sequence of images that converges to a fractal approximation of the original. The requirements on the transformation are that (i) it is contractive in the metric space of images endowed with the L/sub 2/ metric, (ii) it leaves the original image approximately invariant, and (iii) its complexity is smaller than that of the original image. The fully automated ITT-based system has comparable performance, in terms of signal-to-noise-ratio and bit rate, to state-or-the-art vector quantizers, with which it shares some features. >
---
paper_title: Vector Space Formulation of Two-Dimensional Signal Processing Operations

paper_content:

Abstracts Signal processing operations on two-dimensional fields of data can be cast into a vector space formulation. This formulation often leads to a simplified analysis of two-dimensional processing systems and to the discovery of more efficient computational algorithms. This paper considers the general representation of two-dimensional fields as vectors and discusses common types of operators on these data vectors. Particular emphasis is given to various forms of the superposition operation. Computation of superposition operations using unitary transform techniques is analyzed.
---
paper_title: A new image coding technique unifying fractal and transform coding

paper_content:

We present a new image coding scheme based on an unification of fractal and transform coding. We introduce a generalization of the luminance transformation generally used by fractal coding schemes. By extending the luminance transformation to the frequency domain fractal and transform coding become subsets of the proposed transformation. Our new coding scheme FTC (fractal based transform coding) combines the advantages of both techniques. Compared to JPEG a coding gain of 1.5-2.5 dB (PSNR) is obtained. The encoding time is reduced compared to conventional fractal coding schemes and a better convergence at the decoder is attained. At equal error rates the subjective quality of images coded with the new scheme is superior compared to transform coded images. >
---
paper_title: Class of fractal transforms

paper_content:

A general approach to the fractal coding of images is presented, in which image blocks are represented by least squares approximations by fractal functions. Previously known fractal transforms are subsets of this method, which is called the Bath fractal transform (BFT). By searching the image, a hybrid of known methods is achieved, and they are evaluated in the polynomial case with a standard test image.
---
paper_title: Fractal approximation of image blocks

paper_content:

A method for block coding of images based on a least squares fractal approximation by a self-affine system (SAS) is presented. The computational cost of the approximation is linear in the number of pixels in the image. The approximation to a rectangularly tiled block involves evaluating various low-order moments over the block, and solving a system of four linear equations for each tile. The method is applied to a standard test image and the effects of various optimizations are shown. A quantitative comparison with the adaptive discrete cosine transform at 8:1 compression is made. The fidelity of the fractal method shows promise and its greater speed and simplicity compared to other fractal transforms suggest immediate applications such as interactive browsing of remote image archives or image representation in multimedia systems. >
---
paper_title: Fractal block coding of images

paper_content:

An original method is presented for the efficient fractal approximation of rectangular grey-scale image blocks. Its application to the block coding of images is applied to standard test images, and compared to ADCT coding. Fractal coding by this method is relatively efficient and holds promise for applications in which low computational cost is a priority. >
---
paper_title: Fractal image compression without searching

paper_content:

We study the fidelity/compression performance of fast fractal image coding. The Bath fractal transform (BFT) is a generalization of earlier methods with a range of implementation options for the order of approximation and degree of searching. All fractal transforms are fast to decode, and the zero searching variants are nearly as fast to code. We examine BFTs of zero order (flat), first order (bilinear) and second order (biquadratic). The degradation introduced by Lloyd-Max (1982) quantization of the fractal coefficients is evaluated. Further compression is achieved by exploiting correlation in one of the fractal coefficients through differential coding. The other coefficients are quantized directly, and Huffman coding of each gives a compressed image. Possibilities for further compression are discussed. >
---
paper_title: Optimum parameters for hybrid fractal image coding

paper_content:

Evaluates the fidelity/compression performance of fractal transforms over a range of parameters, using an rms error metric. The authors consider order of approximation, different (fixed) block sizes and various degrees of image searching. They find that higher orders of the Bath fractal transform (BFT) are a better means of gaining accuracy at a given bit rate than searching of the image. The best rate/distortion performance is obtained with a lightly quantized higher order BFT, whose optimum block size increases with compression.
---
paper_title: Hybrid image compression with implicit fractal terms

paper_content:

The performance of any block based image coder can be improved by applying fractal terms to selected blocks. Two novel methods are used to achieve this. Firstly the coder determines whether a local fractal term will improve each image block by examining its rate-distortion contribution, so that only beneficial fractal terms are used. Secondly, the decoder deduces the offset parameters for the local fractal transform from the basis functions alone, by inferring the dominant edge position, so that no offset information is required. To illustrate the method, we use a quadtree decomposed image with a truncated DCT basis. Using a standard test image, the proportion of the picture area enhanced by fractals decreases from 16.1% at 0.6 bpp to 8.1% at a high compression ratio of 80:1 (0.1 bpp). The fractal terms contribute less than 5% of the compressed code in all cases. The PSNR is improved slightly, and edge detail is visually enhanced.
---
paper_title: A hybrid fractal-DCT coding scheme for image compression

paper_content:

We introduce a new way to use fractal coding for image compression, based on the parallel use of a fractal encoder and a DCT encoder. The two encoders are given the complementary roles to capture the information of edge and smooth variation, and the information of detail respectively. We show the advantage of using this hybrid coding scheme over the use of a fractal encoder alone, or a DCT encoder alone. This coding scheme is also the occasion to demonstrate a new concept of coding by nonlinear feature separation based on regular and uniform algorithms, suitable for real-time VLSI implementation.
---
paper_title: Fractal image coding using rate-distortion optimized matching pursuit

paper_content:

Matching pursuit is a general and flexible method for solving an optimization problem that is of interest in signal analysis, coding, control theory and statistics. In this paper, principles of rate-distortion optimal coding are used in combination with matching pursuit algorithm to obtain an enhanced fractal image coding method. The advantages of using such a method over traditional fractal image coders are described and compression results are presented.
---
paper_title: Vector quantization and signal compression

paper_content:

1 Introduction.- 1.1 Signals, Coding, and Compression.- 1.2 Optimality.- 1.3 How to Use this Book.- 1.4 Related Reading.- I Basic Tools.- 2 Random Processes and Linear Systems.- 2.1 Introduction.- 2.2 Probability.- 2.3 Random Variables and Vectors.- 2.4 Random Processes.- 2.5 Expectation.- 2.6 Linear Systems.- 2.7 Stationary and Ergodic Properties.- 2.8 Useful Processes.- 2.9 Problems.- 3 Sampling.- 3.1 Introduction.- 3.2 Periodic Sampling.- 3.3 Noise in Sampling.- 3.4 Practical Sampling Schemes.- 3.5 Sampling Jitter.- 3.6 Multidimensional Sampling.- 3.7 Problems.- 4 Linear Prediction.- 4.1 Introduction.- 4.2 Elementary Estimation Theory.- 4.3 Finite-Memory Linear Prediction.- 4.4 Forward and Backward Prediction.- 4.5 The Levinson-Durbin Algorithm.- 4.6 Linear Predictor Design from Empirical Data.- 4.7 Minimum Delay Property.- 4.8 Predictability and Determinism.- 4.9 Infinite Memory Linear Prediction.- 4.10 Simulation of Random Processes.- 4.11 Problems.- II Scalar Coding.- 5 Scalar Quantization I.- 5.1 Introduction.- 5.2 Structure of a Quantizer.- 5.3 Measuring Quantizer Performance.- 5.4 The Uniform Quantizer.- 5.5 Nonuniform Quantization and Companding.- 5.6 High Resolution: General Case.- 5.7 Problems.- 6 Scalar Quantization II.- 6.1 Introduction.- 6.2 Conditions for Optimality.- 6.3 High Resolution Optimal Companding.- 6.4 Quantizer Design Algorithms.- 6.5 Implementation.- 6.6 Problems.- 7 Predictive Quantization.- 7.1 Introduction.- 7.2 Difference Quantization.- 7.3 Closed-Loop Predictive Quantization.- 7.4 Delta Modulation.- 7.5 Problems.- 8 Bit Allocation and Transform Coding.- 8.1 Introduction.- 8.2 The Problem of Bit Allocation.- 8.3 Optimal Bit Allocation Results.- 8.4 Integer Constrained Allocation Techniques.- 8.5 Transform Coding.- 8.6 Karhunen-Loeve Transform.- 8.7 Performance Gain of Transform Coding.- 8.8 Other Transforms.- 8.9 Sub-band Coding.- 8.10 Problems.- 9 Entropy Coding.- 9.1 Introduction.- 9.2 Variable-Length Scalar Noiseless Coding.- 9.3 Prefix Codes.- 9.4 Huffman Coding.- 9.5 Vector Entropy Coding.- 9.6 Arithmetic Coding.- 9.7 Universal and Adaptive Entropy Coding.- 9.8 Ziv-Lempel Coding.- 9.9 Quantization and Entropy Coding.- 9.10 Problems.- III Vector Coding.- 10 Vector Quantization I.- 10.1 Introduction.- 10.2 Structural Properties and Characterization.- 10.3 Measuring Vector Quantizer Performance.- 10.4 Nearest Neighbor Quantizers.- 10.5 Lattice Vector Quantizers.- 10.6 High Resolution Distortion Approximations.- 10.7 Problems.- 11 Vector Quantization II.- 11.1 Introduction.- 11.2 Optimality Conditions for VQ.- 11.3 Vector Quantizer Design.- 11.4 Design Examples.- 11.5 Problems.- 12 Constrained Vector Quantization.- 12.1 Introduction.- 12.2 Complexity and Storage Limitations.- 12.3 Structurally Constrained VQ.- 12.4 Tree-Structured VQ.- 12.5 Classified VQ.- 12.6 Transform VQ.- 12.7 Product Code Techniques.- 12.8 Partitioned VQ.- 12.9 Mean-Removed VQ.- 12.10 Shape-Gain VQ.- 12.11 Multistage VQ.- 12.12 Constrained Storage VQ.- 12.13 Hierarchical and Multiresolution VQ.- 12.14 Nonlinear Interpolative VQ.- 12.15 Lattice Codebook VQ.- 12.16 Fast Nearest Neighbor Encoding.- 12.17 Problems.- 13 Predictive Vector Quantization.- 13.1 Introduction.- 13.2 Predictive Vector Quantization.- 13.3 Vector Linear Prediction.- 13.4 Predictor Design from Empirical Data.- 13.5 Nonlinear Vector Prediction.- 13.6 Design Examples.- 13.7 Problems.- 14 Finite-State Vector Quantization.- 14.1 Recursive Vector Quantizers.- 14.2 Finite-State Vector Quantizers.- 14.3 Labeled-States and Labeled-Transitions.- 14.4 Encoder/Decoder Design.- 14.5 Next-State Function Design.- 14.6 Design Examples.- 14.7 Problems.- 15 Tree and Trellis Encoding.- 15.1 Delayed Decision Encoder.- 15.2 Tree and Trellis Coding.- 15.3 Decoder Design.- 15.4 Predictive Trellis Encoders.- 15.5 Other Design Techniques.- 15.6 Problems.- 16 Adaptive Vector Quantization.- 16.1 Introduction.- 16.2 Mean Adaptation.- 16.3 Gain-Adaptive Vector Quantization.- 16.4 Switched Codebook Adaptation.- 16.5 Adaptive Bit Allocation.- 16.6 Address VQ.- 16.7 Progressive Code Vector Updating.- 16.8 Adaptive Codebook Generation.- 16.9 Vector Excitation Coding.- 16.10 Problems.- 17 Variable Rate Vector Quantization.- 17.1 Variable Rate Coding.- 17.2 Variable Dimension VQ.- 17.3 Alternative Approaches to Variable Rate VQ.- 17.4 Pruned Tree-Structured VQ.- 17.5 The Generalized BFOS Algorithm.- 17.6 Pruned Tree-Structured VQ.- 17.7 Entropy Coded VQ.- 17.8 Greedy Tree Growing.- 17.9 Design Examples.- 17.10 Bit Allocation Revisited.- 17.11 Design Algorithms.- 17.12 Problems.
---
paper_title: Fractal image coding: a review

paper_content:

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. >
---
paper_title: Fractal Image Compression Using Iterated Transforms

paper_content:

This article presents background, theory, and specific implementation notes for an image compression scheme based on fractal transforms. Results from various implementations are presented and compared to standard image compression techniques.
---
paper_title: Fractal Image Compression

paper_content:

The top-selling multimedia encyclopedia Encarta, published by Microsoft Corporation, includes on one CD-ROM seven thousand color photographs which may be viewed interactively on a computer screen. The images are diverse; they are of buildings, musical instruments, people’s faces, baseball bats, ferns, etc. What most users do not know is that all of these photographs are based on fractals and that they represent a (seemingly magical) practical success of mathematics. Research on fractal image compression evolved from the mathematical ferment on chaos and fractals in the years 1978–1985 and in particular on the resurgence of interest in Julia sets and dynamical systems. Here I describe briefly some of the underlying ideas. Following Hutchinson [7], see also [5], consider first a finite set of contraction mappings wi, each with contractivity factor s < 1, taking a compact metric space X into itself, i = 1,2, . . .N. Such a setup is called an iterated function system (IFS), [1]. Use this IFS to construct a mapping W from the space H of nonempty compact subsets of X into itself by defining, in the self-explanatory notation, W (B) = N ⋃
---
paper_title: Region-based fractal image compression using heuristic search

paper_content:

Presents work carried out on fractal (or attractor) image compression. The approach relies on the assumption that image redundancy can be efficiently exploited through self-transformability. The algorithms described utilize a novel region-based partition of the image that greatly increases the compression ratios achieved over traditional block-based partitionings. Due to the large search spaces involved, heuristic algorithms are used to construct these region-based transformations. Results for three different heuristic algorithms are given. The results show that the region-based system achieves almost double the compression ratio of the simple block-based system at a similar decompressed image quality. For the Lena image, compression ratios of 41:1 can be achieved at a PSNR of 26.56 dB. >
---
paper_title: Fractal image coding based on a theory of iterated contractive image transformations

paper_content:

The notion of fractal image compression arises from the fact that the iteration of simple deterministic mathematical procedures can generate images with infinitely intricate geometries known as fracial images [2]. The purpose of research on fractalbased digital image coding is to solve the inverse problem of constraining this complexity to match the realworld complexity of realworld images. In this. paper we propose a fractal image coding technique based on a mathematical theory of iterated transformations [1 2 3 7] which encompasses deterministic fractal geometry. Initial results were reported in [7 8]. The main characteristics of this technique are that (i) it is fractal in the sense that it approximates an original image by a fractal image and (ii) it is a blockcoding technique which relies on the assumption that image redundancy can be efficiently exploited through blockwise selfiransformabiliiy. We therefore refer to it as fracial blockcoding. The codingdecoding system is based on the construction for each original image given to encode of a specific image transformation which when iterated on any initial image produces a sequence of images which converges to a fractal approximation of the original. We show how to design such coders and thoroughly describe the implementation of a system for monochrome still images. Extremely promising coding results were obtained.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Class of fractal transforms

paper_content:

A general approach to the fractal coding of images is presented, in which image blocks are represented by least squares approximations by fractal functions. Previously known fractal transforms are subsets of this method, which is called the Bath fractal transform (BFT). By searching the image, a hybrid of known methods is achieved, and they are evaluated in the polynomial case with a standard test image.
---
paper_title: Fractal approximation of image blocks

paper_content:

A method for block coding of images based on a least squares fractal approximation by a self-affine system (SAS) is presented. The computational cost of the approximation is linear in the number of pixels in the image. The approximation to a rectangularly tiled block involves evaluating various low-order moments over the block, and solving a system of four linear equations for each tile. The method is applied to a standard test image and the effects of various optimizations are shown. A quantitative comparison with the adaptive discrete cosine transform at 8:1 compression is made. The fidelity of the fractal method shows promise and its greater speed and simplicity compared to other fractal transforms suggest immediate applications such as interactive browsing of remote image archives or image representation in multimedia systems. >
---
paper_title: Fractal block coding of images

paper_content:

An original method is presented for the efficient fractal approximation of rectangular grey-scale image blocks. Its application to the block coding of images is applied to standard test images, and compared to ADCT coding. Fractal coding by this method is relatively efficient and holds promise for applications in which low computational cost is a priority. >
---
paper_title: Advances in block based fractal coding of still pictures

paper_content:

Fractal coding is a new technique for compressing images, which exploits similarities in different parts of the picture. For example, with a picture of a fern one can see easily where these similarities lie, each fern leaf resembling a smaller fern. With a more general picture it is not as obvious where these similarities lie. That is because attention is dominated by the macroscopic detail in the picture. If the picture is examined at a microscopic level by blocking the picture into 4*4 pixel blocks, then the 4*4 blocks show remarkable similarities: blocks that are predominantly flat, blocks with an edge across them, and so forth. >
---
paper_title: Optimum parameters for hybrid fractal image coding

paper_content:

Evaluates the fidelity/compression performance of fractal transforms over a range of parameters, using an rms error metric. The authors consider order of approximation, different (fixed) block sizes and various degrees of image searching. They find that higher orders of the Bath fractal transform (BFT) are a better means of gaining accuracy at a given bit rate than searching of the image. The best rate/distortion performance is obtained with a lightly quantized higher order BFT, whose optimum block size increases with compression.
---
paper_title: Fast hierarchical codebook search for fractal coding of still images

paper_content:

This paper presents a method for fast encoding of still images based on iterated function systems (IFSs). The major disadvantage of this coding approach, usually referred to as fractal coding, is the high computational effort of the encoding process compared to e.g. the JPEG algorithm. This is mainly due to the costly 'full search' of the transform parameters within a fractal codebook. We therefore propose an hierarchical encoding scheme which is based upon a two level codebook search and a structural classification of its entries. By this way only a small subset of the codebook has to be considered, which increases encoding speed significantly. Refining the initial codebook and applying a second search even increases the reconstruction quality compared to the full search but with a fraction of its computational effort.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Hybrid image compression with implicit fractal terms

paper_content:

The performance of any block based image coder can be improved by applying fractal terms to selected blocks. Two novel methods are used to achieve this. Firstly the coder determines whether a local fractal term will improve each image block by examining its rate-distortion contribution, so that only beneficial fractal terms are used. Secondly, the decoder deduces the offset parameters for the local fractal transform from the basis functions alone, by inferring the dominant edge position, so that no offset information is required. To illustrate the method, we use a quadtree decomposed image with a truncated DCT basis. Using a standard test image, the proportion of the picture area enhanced by fractals decreases from 16.1% at 0.6 bpp to 8.1% at a high compression ratio of 80:1 (0.1 bpp). The fractal terms contribute less than 5% of the compressed code in all cases. The PSNR is improved slightly, and edge detail is visually enhanced.
---
paper_title: Fractal image coding: a review

paper_content:

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. >
---
paper_title: Fractal coding of medical images

paper_content:

In this paper, we investigate the application of fractal concept to the coding of medical images, taking into account the self-similarity at different scales. The approach proposed by Jacquin is very flexible, enabling us to optimize different steps of the associated algorithm. We remark that the choice of the distance used to measure the self-similarity between the range block Ri and the estimated range block Ri is essential to the algorithm. In fact, the choice of the metric determines the optimal parameters of the affine transformation. In our study, we propose two metrics, L2 and L(infinity ) and compare their performances. We also develop a simple fast decoding scheme, necessary for a clinical use. This paper addresses the adaptation of the fractal compression algorithm to medical image modalities. We present the results obtained with two image data bases (numerized mammograms and x-ray angiograms). A comparison with JPEG results shows the improvement with our technique, particularly for low bit rates.© (1996) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Still image coding based on vector quantization and fractal approximation.

paper_content:

In this paper, we propose a coding algorithm for still images using vector quantization (VQ) and fractal approximation, in which low-frequency components of an input image are approximated by VQ, and its residual is coded by fractal mapping. The conventional fractal coding algorithms indirectly used the gray patterns of an original image with contraction mapping, whereas the proposed fractal coding method employs an approximated and then decimated image as a domain pool and uses its gray patterns. Thus, the proposed algorithm utilizes fractal approximation without the constraint of contraction mapping. For approximation of an original image, we employ the discrete cosine transform (DCT) rather than conventional polynomial-based transforms. In addition, for variable blocksize segmentation, we use the fractal dimension of a block that represents the roughness of the gray surface of a region. Computer simulations with several test images show that the proposed method shows better performance than the conventional fractal coding methods for encoding still pictures.
---
paper_title: VQ-enhanced fractal image compression

paper_content:

A novel hybrid scheme combining fractal image compression with mean-removed shape-gain vector quantization is presented. The scheme uses a small set of VQ codebook blocks as a block classifier for the domain blocks and as an alternative means of coding when able to provide a satisfying distortion. Our scheme is shown to improve the performance of conventional fractal coding in all its aspects. The rate-distortion curve is ameliorated, and both the encoding and the decoding are faster.
---
paper_title: Fractal color image compression using vector distortion measure

paper_content:

A fractal monochrome image compression technique proposed by Jacquin is investigated for 24-bit true color image by encoding the RGB components' images independently. To exploit the spectral redundancy in RGB components, the root mean square error distortion measure in grayscale space is extended to 3-dimensional color space for fractal-based color image coding. Experimental results show that a 1.5 compression ratio improvement can be obtained using the vector distortion measure in fractal coding with fixed image partition as compared to separate fractal coding in RGB images. In addition, adaptive fractal color image coding based on quadtree partition is also proposed which can obtain a good trade-off between compression ratio and image fidelity.
---
paper_title: A new improved collage theorem with applications to multiresolution fractal image coding

paper_content:

The paper presents an improved collage theorem, valid for a class of signal mappings called affine blockwise average (ABA) mappings. The ABA structure is exploited to form a bound depending on norms of collage error signals at several resolutions. Compared to previously published collage theorems, the new theorem provides a much tighter bound on the maximum distance between the original signal (real world image) and the decoder attractor, given the distance between the original and the "collage" optimized by the encoder. This is achieved without contractivity constraints on the ABA mapping parameters. Finally, an encoding method in which one attempts to minimize the upper bound directly is suggested. >
---
paper_title: On the Convergence of Fractal Transforms

paper_content:

This paper reports on investigations concerning the convergence of fractal transforms for signal modelling. Convergence is essential for the functionality of fractal based coding schemes. The coding process is described as non-linear transformation in the finite-dimensional vector space. Using spectral theory, a necessary and sufficient condition for the contractivity is derived from the eigenvalues of a special linear operator. In the same way some constraints for the choice of the encoding parameters are deduced which are less strict than those imposed so far. The proposed contractivity measure can be calculated directly from the transformation parameters during the encoding process. For complex encoding schemes the calculation of the eigenvalues may be infeasible. For those cases a contractivity criterion derived from the norm of the operator is suggested. >
---
paper_title: Fractal Image Compression Using Iterated Transforms

paper_content:

This article presents background, theory, and specific implementation notes for an image compression scheme based on fractal transforms. Results from various implementations are presented and compared to standard image compression techniques.
---
paper_title: Fractal (self-VQ) encoding of video sequences

paper_content:

We present results of a scheme to encode video sequences of digital image data based on a quadtree still-image fractal method. The scheme encodes each frame using image pieces, or vectors, from its predecessor; hence it can be thought of as a VQ scheme in which the code book is derived from the previous image. We present results showing: near real-time (5 - 12 frames/sec) software-only decoding; resolution independence; high compression ratios (25 - 244:1); and low compression times (2.4 - 66 sec/frame) as compared with standard fixed image fractal schemes.© (1994) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: On the problem of convergence in fractal coding schemes

paper_content:

Most fractal coding schemes employ an iterative decoding algorithm in order to reconstruct the approximation of the original signal from the fractal code. A necessary condition for obtaining a unique solution is the convergence of the reconstruction process. This paper reports on investigations concerning a necessary and sufficient condition for convergence which is based upon the spectral radius of the transformation matrix. For a very general class of fractal transforms a simple calculation of the spectral radius can be performed in order to decide whether the reconstruction converges or not. This allows more freedom in the choice of the encoding parameters resulting in a better and faster reconstruction process. Also the proposed description leads to a more accurate theoretical foundation of fractal coding schemes. >
---
paper_title: On the Convergence of Fractal Transforms

paper_content:

This paper reports on investigations concerning the convergence of fractal transforms for signal modelling. Convergence is essential for the functionality of fractal based coding schemes. The coding process is described as non-linear transformation in the finite-dimensional vector space. Using spectral theory, a necessary and sufficient condition for the contractivity is derived from the eigenvalues of a special linear operator. In the same way some constraints for the choice of the encoding parameters are deduced which are less strict than those imposed so far. The proposed contractivity measure can be calculated directly from the transformation parameters during the encoding process. For complex encoding schemes the calculation of the eigenvalues may be infeasible. For those cases a contractivity criterion derived from the norm of the operator is suggested. >
---
paper_title: A system/graph theoretical analysis of attractor coders

paper_content:

This paper provides links between the young field of attractor coding and the well-established fields of systems theory and graph theory. Attractor decoders are modeled as linear systems whose stability is both necessary and sufficient for convergence of the decoder. This stability is dictated by the location of the eigenvalues of the sparse state transition matrix of the system. The relationship between these eigenvalues, spatial causality of the system, and the patterns of interdependency between signal elements (or image pixels) is investigated for several cases using concepts from graph and matrix theory.
---
paper_title: Statistical evaluation of fractal coding schemes

paper_content:

This paper reports on investigations concerning the convergence of the reconstruction process in fractal coding schemes from a statistical point of view. For a rather general family of "fractal operators" a necessary and sufficient condition for the convergence based on the spectral radius of the fractal operator is provided. Emerging from this condition the probability density function (PDF) of the magnitude of the eigenvalues is formulated which enables to determine a probabilistic measure for the convergence of the reconstruction process. Since the PDF considerably depends on the structure of the operators, various coding schemes can be analyzed with respect to their convergence properties in a statistical sense. The results presented indicate that certain types of operators are less suited for applications in the field of fractal coding compared to others.
---
paper_title: Rate buffered fractal video

paper_content:

We report real time fractal coding of 176 by 144 luminance images on a 33 MHz i-486 computer. With a zero searching first order (bilinear) Bath fractal transform, square blocks of 64 pixels are coded in 250 /spl mu/sec and decoded in 200 /spl mu/sec. This permits coding of 40% of each frame in a 25 Hz video sequence, or full coding at 10 Hz. By transmitting only those blocks of greatest error, we can obtain any degree of data compression. Useful video sequences of talking heads have been achieved with rates as low as 40 kbits/sec. We describe the techniques used, give illustrations of the degradation, and show the evolution of the errors in the decoded sequence as various events occur. The overall compression at 40 kbits/sec is 99:1, with further error reductions possible. >
---
paper_title: Optimal fractal coding is NP-hard

paper_content:

In fractal compression a signal is encoded by the parameters of a contractive transformation whose fixed point (attractor) is an approximation of the original data. Thus fractal coding can be viewed as the optimization problem of finding in a set of admissible contractive transformations the transformation whose attractor is closest to a given signal. The standard fractal coding scheme based on the collage theorem produces only a suboptimal solution. We demonstrate by a reduction from MAXCUT that the problem of determining the optimal fractal code is NP-hard. To our knowledge, this is the first analysis of the intrinsic complexity of fractal coding. Additionally, we show that standard fractal coding is not an approximating algorithm for this problem.
---
paper_title: Iterative collage coding for fractal compression

paper_content:

A fractal encoder processes the original source vector by selecting a contractive map whose unique fixed point (attractor) approximates the original. A description of the map is transmitted to the decoder. The decoder iterates the map to recover the attractor. The task of picking the map is called the inverse problem. The predominantly used, suboptimum, technique to solve the inverse problem is collage coding. In collage coding, only the first decoding iteration is optimized. We propose two new suboptimum algorithms for the inverse problem. In our approach, the encoder imitates the iterative operation of the decoder. At each step, however, a new map is used so as to keep the sequence of approximations close to the original. If the sequence converges, then the limit is an attractor, and it is a good candidate for the reconstructed vector. The description of the map corresponding to the attractor is sent to the decoder. >
---
paper_title: Accelerating fractal image compression by multi-dimensional nearest neighbor search

paper_content:

In fractal image compression the encoding step is computationally expensive. A large number of sequential searches through a list of domains (portions of the image) are carried out while trying to find the best match for another image portion. Our theory developed here shows that this basic procedure of fractal image compression is equivalent to multi-dimensional nearest neighbor search. This result is useful for accelerating the encoding procedure in fractal image compression. The traditional sequential search takes linear time whereas the nearest neighbor search can be organized to require only logarithmic time. The fast search has been integrated into an existing state-of-the-art classification method thereby accelerating the searches carried out in the individual domain classes. In this case we record acceleration factors from 1.3 up to 11.5 depending on image and domain pool size with negligible or minor degradation in both image quality and compression ratio. Furthermore, as compared to plain classification our method is demonstrated to be able to search through larger portions of the domain pool without increased the computation time.
---
paper_title: Geometrical Interpretation Of Ifs Based Image Coding

paper_content:

In most classical coding methods, a global optimization is carried out to ensure a given bit-rate or a given quality. In IFS based coding, some heuristic choices are made at each step of the algorithm: No method has, for instance, been proposed to optimize the domain blocks position, or the quantization of the transformations parameters. In this article we first analyze the limits of the existing algorithms, then define a new geometrical interpretation of the classical Jacquin-like method. Through the above analysis, we will answer some of these important questions.
---
paper_title: Lean domain pools for fractal image compression

paper_content:

In fractal image compression an image is partitioned into ranges for each of which a similar subimage, called domain, is selected from a pool of subimages. A typical choice for the domain pool may consist of all square subimages of a particular size. However, only a fraction of this large pool is actually used in the fractal code. This subset can be characterized in two related ways: (1) It contains domains with relatively large intensity variation. (2) The collection of used domains are localized in those image regions with a high degree of structure. Both observations lead us to improvements of fractal image compression. Firstly, we accelerate the encoding process by a priori discarding those domains from the pool which are unlikely to be chosen for the fractal code. This comes at the expense of a slight loss in compression ratio. In our empirical studies (using Fisher's adaptive quadtree method) we have found that a twofold acceleration leads to a drop of only 2 to 3% in the compression ratio while the image quality even improves by 0.1 to 0.2 dB. Secondly, the localization of the domains can be exploited for an improved encoding in effect raising the compression ratio back up without any penalty.© (1996) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Fast methods for fractal image encoding

paper_content:

Fractal image compression is a relatively new and very promising technique for still image compression. However, it is not widely applied due to its very time consuming encoding procedure. In this research, we focus on speeding up this procedure by introducing three schemes: dimensionality reduction, energy-based classification, and tree search. We have developed an algorithm that combines these three schemes together and achieves a speed-up factor of 175 at the expense of only 0.6 dB degradation in PSNR relative to the unmodified exhaustive search for a typical image encoded with 0.44 bpp.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Multi-resolution tree search for iterated transformation theory-based coding

paper_content:

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. >
---
paper_title: A pyramid algorithm for fast fractal image compression

paper_content:

We present a fast fractal image encoding algorithm which is based on a refinement of the fractal code from an initial coarse level of the pyramid. The pyramid search algorithm is quasi-optimal in terms of minimizing the mean square error. Assuming that the distribution of the matching error is described by an independent, identically distributed (i.i.d.) Laplacian random process, we derive the threshold sequence for the objective function in each pyramidal level. The computational efficiency depends on the depth of the pyramid and the search step size and could be improved up to two orders of magnitude compared with the full search of the original image.
---
paper_title: On the performance of fractal compression with clustering.

paper_content:

The paper investigates a technique to reduce the computational complexity of fractal image compression on gray-scale images. The technique uses a clustering process on image domain blocks with the clusters formed with the use of k-d trees and the fast pairwise nearest neighbor algorithm of Equitz (1984). Results indicate the method is effective for smaller domain block sizes and generally shows improvement in terms of picture peak signal-to-noise ratio (SNR) over the quadrant variance classification method.
---
paper_title: Codebook Clustering by Self-organizing Maps for Fractal Image Compression

paper_content:

A fast encoding scheme for fractal image compression is presented. The method uses a clustering algorithm based on Kohonen's self-organizing maps. Domain blocks are clustered, yielding a classification with a notion of distance which is not given in traditional classification schemes.
---
paper_title: Lossless acceleration of fractal image compression by fast convolution

paper_content:

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.
---
paper_title: Advances in block based fractal coding of still pictures

paper_content:

Fractal coding is a new technique for compressing images, which exploits similarities in different parts of the picture. For example, with a picture of a fern one can see easily where these similarities lie, each fern leaf resembling a smaller fern. With a more general picture it is not as obvious where these similarities lie. That is because attention is dominated by the macroscopic detail in the picture. If the picture is examined at a microscopic level by blocking the picture into 4*4 pixel blocks, then the 4*4 blocks show remarkable similarities: blocks that are predominantly flat, blocks with an edge across them, and so forth. >
---
paper_title: Fast methods for fractal image encoding

paper_content:

Fractal image compression is a relatively new and very promising technique for still image compression. However, it is not widely applied due to its very time consuming encoding procedure. In this research, we focus on speeding up this procedure by introducing three schemes: dimensionality reduction, energy-based classification, and tree search. We have developed an algorithm that combines these three schemes together and achieves a speed-up factor of 175 at the expense of only 0.6 dB degradation in PSNR relative to the unmodified exhaustive search for a typical image encoded with 0.44 bpp.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Finite-state fractal block coding of images

paper_content:

An image compression scheme based on the finite-state fractal block coding (FS-FBC) is proposed. Since the FS algorithm has been successfully employed by the vector quantization (VQ) techniques and there are many similarities between VQ and FBC scheme, we employ the FS algorithm on FBC technique to determine the fractal codes. The next-state functions for the domain pool size, contrast scaling factor, isometry, and mean are designed. In computer simulation, we first independently investigate the FS effect of each parameter and then combine all methods to test the overall effect. We obtain a reconstructed Lena image with 33.9 dB PSNR at 0.42 bit/pixel, while the result of original FBC scheme is 31.4 dB at 0.6 bit/pixel. The simulation results show that our FS methods can be successfully employed on the FBC technique to reduce the bit rate and the image quality is still preserved.
---
paper_title: Vq-Encoding Of Luminance Parameters In Fractal Coding Schemes

paper_content:

This paper is concerned with the efficient storage of the luminance parameters in a fractal code by means of vector quantization (VQ). For a given image block (range) the collage error as a function of the luminance parameters is a quadratic function with ellipsoid contour lines. We demonstrate how these functions should be used in an optimal codebook design algorithm leading to a non-standard VQ-scheme. In addition we present results and an evaluation of this approach. The analysis of the quadratic error functions also provides guidance for optimal scalar quantization.
---
paper_title: Fractal image compression without searching

paper_content:

We study the fidelity/compression performance of fast fractal image coding. The Bath fractal transform (BFT) is a generalization of earlier methods with a range of implementation options for the order of approximation and degree of searching. All fractal transforms are fast to decode, and the zero searching variants are nearly as fast to code. We examine BFTs of zero order (flat), first order (bilinear) and second order (biquadratic). The degradation introduced by Lloyd-Max (1982) quantization of the fractal coefficients is evaluated. Further compression is achieved by exploiting correlation in one of the fractal coefficients through differential coding. The other coefficients are quantized directly, and Huffman coding of each gives a compressed image. Possibilities for further compression are discussed. >
---
paper_title: An inner product space approach to image coding by contractive transformations

paper_content:

Consideration is given to modeling of arbitrary digital gray tone images as the fixed points of contractive transformations on the image space. The transformation is designed to exploit a form of image redundancy called piecewise self-similarity. Results from inner product space theory are used to optimize the transformation within a class of affine transformations. The resulting transformation is described by a small amount of information compared to the original image, and its piecewise self-similar fixed point, found by successively iterating the transformation from any initial image, is close to the original image. Results are improved compared to earlier results with this technique. >
---
paper_title: Rate/distortion in fractal compression: order of transform and block symmetries

paper_content:

The authors have evaluated two complexity options in fractal image coding, namely the order of the fractal approximation and the benefits of searching over block symmetries. This was done in terms of the the entropy and distortion for a range of quantizations of the fractal coefficients. The results question the current wisdom in this field. Most fractal block coding systems use a low order approximation, while the present results suggest that where the distortion and compression are similar, a higher order approximation gives a noticeably sharper image. Virtually all reported fractal coding algorithms search for the best block reflections and rotations, but the present authors demonstrate that extra bits required to code the symmetry options are not compensated for by the modest fidelity gained. >
---
paper_title: A hybrid fractal-DCT coding scheme for image compression

paper_content:

We introduce a new way to use fractal coding for image compression, based on the parallel use of a fractal encoder and a DCT encoder. The two encoders are given the complementary roles to capture the information of edge and smooth variation, and the information of detail respectively. We show the advantage of using this hybrid coding scheme over the use of a fractal encoder alone, or a DCT encoder alone. This coding scheme is also the occasion to demonstrate a new concept of coding by nonlinear feature separation based on regular and uniform algorithms, suitable for real-time VLSI implementation.
---
paper_title: A new image coding technique unifying fractal and transform coding

paper_content:

We present a new image coding scheme based on an unification of fractal and transform coding. We introduce a generalization of the luminance transformation generally used by fractal coding schemes. By extending the luminance transformation to the frequency domain fractal and transform coding become subsets of the proposed transformation. Our new coding scheme FTC (fractal based transform coding) combines the advantages of both techniques. Compared to JPEG a coding gain of 1.5-2.5 dB (PSNR) is obtained. The encoding time is reduced compared to conventional fractal coding schemes and a better convergence at the decoder is attained. At equal error rates the subjective quality of images coded with the new scheme is superior compared to transform coded images. >
---
paper_title: A Non Uniform Segmentation Optimal Hybrid Fractal/dct Image Compression Algorithm

paper_content:

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 in the image, the hybrid coder performs an 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. A Lagrangian multiplier approach is used to optimize the hybrid parameters and 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.
---
paper_title: Hybrid image compression with implicit fractal terms

paper_content:

The performance of any block based image coder can be improved by applying fractal terms to selected blocks. Two novel methods are used to achieve this. Firstly the coder determines whether a local fractal term will improve each image block by examining its rate-distortion contribution, so that only beneficial fractal terms are used. Secondly, the decoder deduces the offset parameters for the local fractal transform from the basis functions alone, by inferring the dominant edge position, so that no offset information is required. To illustrate the method, we use a quadtree decomposed image with a truncated DCT basis. Using a standard test image, the proportion of the picture area enhanced by fractals decreases from 16.1% at 0.6 bpp to 8.1% at a high compression ratio of 80:1 (0.1 bpp). The fractal terms contribute less than 5% of the compressed code in all cases. The PSNR is improved slightly, and edge detail is visually enhanced.
---
paper_title: Fractal image coding using rate-distortion optimized matching pursuit

paper_content:

Matching pursuit is a general and flexible method for solving an optimization problem that is of interest in signal analysis, coding, control theory and statistics. In this paper, principles of rate-distortion optimal coding are used in combination with matching pursuit algorithm to obtain an enhanced fractal image coding method. The advantages of using such a method over traditional fractal image coders are described and compression results are presented.
---
paper_title: Fractal decoding algorithm for fast convergence

paper_content:

A fractal coding is discussed that concentrates on relieving excessive computation burden and improving image quality in encoding. But the convergence speed of the decoder is important because, in many applications, the encoding is done once, while the decoding is to be repeated many times. Because the well-known fractal coding scheme is based on the iterated function system (IFS), we cannot avoid the iterated transformation though the scheme can be done noniteratively in a special case. Such a transformation encounters difficulty in parallel processing and hence a fast decoding algorithm is necessary. An algorithm to speedup the decoding process is described. The analysis and the simulation results of the proposed method show that our algorithm is much faster than the conventional method.
---
paper_title: Decoding algorithm for fractal image compression

paper_content:

A new iterative decoding method is proposed for fractal image compression. Convergence properties are provided. Experimental results show the superiority of the new method over the conventional decoding procedure.
---
paper_title: Rendering algorithms for deterministic fractals

paper_content:

Heavy computation requirements have inhibited the application of fractal technology, but new algorithms for coding and displaying iterated function system fractals are achieving real-time performance in software. We discuss the standard rendering algorithms and introduce a variation that performs a minimal number of arithmetic operations when constructing an approximate fractal. In addition, we describe novel extensions that let us render gray-scale and color fractal images. >
---
paper_title: Resolution enhancement of images using fractal coding

paper_content:

The code generated by fractal coding of a digital image provides a resolution-independent representation of the image as this code can be decoded to generate a digital image at any resolution. When the image is decoded at a size larger than the original encoded image, image details beyond the resolution of the original image are predicted by assuming local self-similarity in image at different scales. In this paper, we (1) present a formulation of how decoding may be done at a higher resolution, (2) evaluate the accuracy of the predicted details using a frequency analysis of fractally enlarged test images, and (3) propose a method for fractal resolution enhancement without the low-frequency loss of information due to fractal coding.© (1997) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Image compression using partitioned iterated function systems

paper_content:

The Partitioned Iterated Function Systems (PIFS) involves partitioning a image into non-overlapping range blocks and overlapping domain blocks. For each range block, a matching domain block is found by applying a contractive affine transformation. The set of transformations uniquely defines an estimation of the original image. In this paper, we investigate the quadtree partition technique of generating range blocks. In this technique, a range block is recursively partitioned into 4 equally sized sub-squares, when it is not covered well enough by a domain. But this method has a inherent penalty in which the existence of range blocks of different sizes requires the storage of the sizes and coordinates of the range blocks. We present a scheme that stores the required decoding information with very little overhead. One of the properties offractals is that detail exists at every scale. This has led us to investigate into the possibility of exploiting the scalability property of fractals to allow us to improve the compression time and ratio.
---
paper_title: Zooming Using Iterated Function Systems

paper_content:

Iterated Function Systems (I.F.S.) have been recently studied in the field of image coding. In addition to compression, I.F.S. possess some properties of fractals which can be used to sub/oversample an image. In this paper, we review how I.F.S. can be used for image zooming, directly from basic algorithms of still image compression. This study shows that results obtained in such a way do not produce better results than those obtained by using classical spatial interpolators such as the linear one. However, in this paper we also show that modified versions of the basic approach provide a better use of I.F.S.'s coding for zooming.
---
paper_title: Self-quantized wavelet subtrees: wavelet-based theory of fractal image compression

paper_content:

We describe a novel adaptive wavelet-based compression scheme for images which takes advantage of image redundancy across scales. As with standard wavelet transform coders, our compressed image representation consists of a set of quantized wavelet coefficients and quantized wavelet subtrees. Instead of having a fixed subtree codebook, however, we construct a codebook from the image being compressed. Subtrees are quantized to contracted isometries of coarser scale subtrees. This codebook drawn from the image is effective for quantizing locally smooth regions and locally straight edges. We prove that this self- quantization enables us to recover the fine scale wavelet coefficients of an image given its coarse scale coefficients. We show that this self-quantization algorithm is equivalent to a fractal image compression scheme when the wavelet basis is the Haar basis. The wavelet framework greatly simplifies the analysis of fractal compression schemes and places fractal compression in the context of existing wavelet subtree coding schemes. We obtain a simple convergence proof which strengthens existing fractal compression results, we describe a new reconstruction algorithm which requires O(N) operations for an N pixel image, and we derive an improved means of estimating the error incurred in decoding fractal compressed images. We show the effect of self-quantization for a test image.
---
paper_title: Merging Fractal Image Compression and Wavelet Transform Methods

paper_content:

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.
---
paper_title: Fractal representation of images via the discrete wavelet transform

paper_content:

Fractal representation of images is based on mappings between similar regions within an image (also known as IFS). Such a representation can be applied to image coding and to increase image resolution. One of the main drawbacks of conventional fractal representation is the fact that the mappings are between blocks. As a result, the reconstructed image may suffer from disturbing blockiness. In this work we present a method for mapping similar regions within an image in the wavelet domain. We first show how to use the Haar wavelet transform coefficients to find mappings which are identical to conventional blockwise mappings. The union of these mappings, between sets of wavelet coefficients, can be interpreted as a prediction of higher bands of a signal from its lower band. Changing the mother-wavelet to other than Haar, creates mappings which are between regions which smoothly decay towards their borders, thus reducing the blockiness, as well as improving the PSNR of the reconstructed image.
---
paper_title: Adaptive self-quantization of wavelet subtrees: a wavelet-based theory of fractal image compression

paper_content:

Fractal image compression was one of the earliest compression schemes to take advantage of image redundancy in scale. The theory of iterated function systems motivates a broad class of fractal schemes but does not give much guidance for implementation. Fractal compression schemes do not fit into the standard transform coder paradigm and have proven difficult to analyze. We introduce a wavelet-based framework for analyzing fractal block coders which simplifies these schemes considerably. Using this framework we find that fractal block coders are Haar wavelet subtree quantization schemes, and we thereby place fractal schemes in the context of conventional transform coders. We show that the central mechanism of fractal schemes is an extrapolation of fine-scale Haar wavelet coefficients from coarse-scale coefficients. We use this insight to derive a wavelet-based analog of fractal compression, the self-quantization of subtrees (SQS) scheme. We obtain a simple SQS decoder convergence proof and a fast SQS decoding algorithm which simplify and generalize existing fractal compression results. We describe an adaptive SQS compression scheme which outperforms the best fractal schemes in the literature by roughly 1 dB in PSNR across a broad range of compression ratios and which has performance comparable to some of the best conventional wavelet subtree quantization schemes.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Self-quantized wavelet subtrees: wavelet-based theory of fractal image compression

paper_content:

We describe a novel adaptive wavelet-based compression scheme for images which takes advantage of image redundancy across scales. As with standard wavelet transform coders, our compressed image representation consists of a set of quantized wavelet coefficients and quantized wavelet subtrees. Instead of having a fixed subtree codebook, however, we construct a codebook from the image being compressed. Subtrees are quantized to contracted isometries of coarser scale subtrees. This codebook drawn from the image is effective for quantizing locally smooth regions and locally straight edges. We prove that this self- quantization enables us to recover the fine scale wavelet coefficients of an image given its coarse scale coefficients. We show that this self-quantization algorithm is equivalent to a fractal image compression scheme when the wavelet basis is the Haar basis. The wavelet framework greatly simplifies the analysis of fractal compression schemes and places fractal compression in the context of existing wavelet subtree coding schemes. We obtain a simple convergence proof which strengthens existing fractal compression results, we describe a new reconstruction algorithm which requires O(N) operations for an N pixel image, and we derive an improved means of estimating the error incurred in decoding fractal compressed images. We show the effect of self-quantization for a test image.
---
paper_title: Adaptive self-quantization of wavelet subtrees: a wavelet-based theory of fractal image compression

paper_content:

Fractal image compression was one of the earliest compression schemes to take advantage of image redundancy in scale. The theory of iterated function systems motivates a broad class of fractal schemes but does not give much guidance for implementation. Fractal compression schemes do not fit into the standard transform coder paradigm and have proven difficult to analyze. We introduce a wavelet-based framework for analyzing fractal block coders which simplifies these schemes considerably. Using this framework we find that fractal block coders are Haar wavelet subtree quantization schemes, and we thereby place fractal schemes in the context of conventional transform coders. We show that the central mechanism of fractal schemes is an extrapolation of fine-scale Haar wavelet coefficients from coarse-scale coefficients. We use this insight to derive a wavelet-based analog of fractal compression, the self-quantization of subtrees (SQS) scheme. We obtain a simple SQS decoder convergence proof and a fast SQS decoding algorithm which simplify and generalize existing fractal compression results. We describe an adaptive SQS compression scheme which outperforms the best fractal schemes in the literature by roughly 1 dB in PSNR across a broad range of compression ratios and which has performance comparable to some of the best conventional wavelet subtree quantization schemes.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: New results for fractal/wavelet image compression

paper_content:

In this research, we perform a multiresolution analysis of the mappings used in fractal image compression. We derive the transform-domain structure of the mappings and demonstrate a close connection between fractal image compression and wavelet transform coding using the Haar basis. We show that under certain conditions, the mappings correspond to a hierarchy of affine mappings between the subbands of the transformed image. Our analysis provides new insights into the mechanism underlying fractal image compression, leads to a non-iterative transform-domain decoding algorithm, and suggests a transform-domain encoding method with extensions to wavelets other than the Haar transform. As a result, we also propose a novel transform-domain encoding scheme whereby the image is hierarchically encoded starting with a coarse approximation and detail is added through a casual sequence of affine mappings between the subbands. This new approach is not only theoretically elegant, but also useful for embedded representation, i.e. images can be decoded to an intermediate resolution.© (1996) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Self-quantized wavelet subtrees: wavelet-based theory of fractal image compression

paper_content:

We describe a novel adaptive wavelet-based compression scheme for images which takes advantage of image redundancy across scales. As with standard wavelet transform coders, our compressed image representation consists of a set of quantized wavelet coefficients and quantized wavelet subtrees. Instead of having a fixed subtree codebook, however, we construct a codebook from the image being compressed. Subtrees are quantized to contracted isometries of coarser scale subtrees. This codebook drawn from the image is effective for quantizing locally smooth regions and locally straight edges. We prove that this self- quantization enables us to recover the fine scale wavelet coefficients of an image given its coarse scale coefficients. We show that this self-quantization algorithm is equivalent to a fractal image compression scheme when the wavelet basis is the Haar basis. The wavelet framework greatly simplifies the analysis of fractal compression schemes and places fractal compression in the context of existing wavelet subtree coding schemes. We obtain a simple convergence proof which strengthens existing fractal compression results, we describe a new reconstruction algorithm which requires O(N) operations for an N pixel image, and we derive an improved means of estimating the error incurred in decoding fractal compressed images. We show the effect of self-quantization for a test image.
---
paper_title: Merging Fractal Image Compression and Wavelet Transform Methods

paper_content:

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.
---
paper_title: Fractal wavelet coding using a rate-distortion constraint

paper_content:

We propose a hybrid fractal wavelet coder (FWC) which adopts adaptive fractal prediction in the wavelet domain and wavelet coding in this research. This new compression scheme uses wavelet coding as the core component, and applies contractive mapping (or the so-called fractal prediction) whenever it offers additional rate savings. A model based rate-distortion (R-D) criterion of low complexity is used to evaluate the fractal prediction efficiency and search for the best domain-range match. The superior R-D performance of FWC is demonstrated with extensive experimental results.
---
paper_title: Class of fractal transforms

paper_content:

A general approach to the fractal coding of images is presented, in which image blocks are represented by least squares approximations by fractal functions. Previously known fractal transforms are subsets of this method, which is called the Bath fractal transform (BFT). By searching the image, a hybrid of known methods is achieved, and they are evaluated in the polynomial case with a standard test image.
---
paper_title: Image coding by block prediction of multiresolution subimages

paper_content:

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. >
---
paper_title: Fractal coding of subbands with an oriented partition

paper_content:

Abstract We propose a new image compression scheme based on fractal coding of the coefficients of a wavelet transform, in order to take into account the self-similarity observed in each subband. The original image is first decomposed into subbands containing information in different spatial directions and at different scales, using an orthogonal wavelet-generated filter bank. Subbands are encoded using local iterated function systems (LIFS), with range and domain blocks presenting horizontal or vertical directionalities. Their sizes are defined according to the correlation lengths and resolution of each subband. The edge degradation and the blocking effects encountered at low bit-rates using conventional LIFS algorithm are reduced with this approach. The computation complexity is also greatly decreased by a 12:1 factor in comparison to fractal coding of the full resolution image. The proposed method is applied to standard test images. The comparison with other fractal coding approaches and with JPEG shows an important increase in terms of PPSNR/bit-rate. Especially for images presenting a privileged directionality, the use of adaptive partitions results in about 3 dB improvement in PPSNR. We also discuss the distorsion versus rate improvement obtained on high-frequency subbands when fractal coding instead of pyramidal vector quantization is used. Our approach achieves a real gain in PPSNR for low bit-rates between 0.3 and 1.2 bpp.
---
paper_title: An image coding scheme using block prediction of the pyramid subband decomposition

paper_content:

In this work, we propose a hybrid vector quantization scheme for general images that aims at exploiting similarities among detail signals in a multiresolution decomposition of the image. In a multiresolution decomposition, the image is decomposed into a set of subbands which are localized in scale, orientation and space. Our coding scheme consists of dividing each subimage of the multiresolution decomposition into square range blocks. The range blocks are matched against domain blocks chosen in the lower resolution subimage with the same orientation, and coded through a description of the map transforming the domain block into the range block. The pool of of domain blocks acts as a codebook for the range block, as in vector quantization, with the difference that the codebook is built from blocks inside the multiresolution decomposition. If the prediction procedure is not satisfactory with respect to a target quality, the block is coded using a geometric vector quantizer for Laplacian random variables. >
---
paper_title: A hybrid fractal-DCT coding scheme for image compression

paper_content:

We introduce a new way to use fractal coding for image compression, based on the parallel use of a fractal encoder and a DCT encoder. The two encoders are given the complementary roles to capture the information of edge and smooth variation, and the information of detail respectively. We show the advantage of using this hybrid coding scheme over the use of a fractal encoder alone, or a DCT encoder alone. This coding scheme is also the occasion to demonstrate a new concept of coding by nonlinear feature separation based on regular and uniform algorithms, suitable for real-time VLSI implementation.
---
paper_title: JPEG: Still Image Data Compression Standard

paper_content:

Foreword. Acknowledgments. Trademarks. Introduction. Image Concepts and Vocabulary. Aspects of the Human Visual Systems. The Discrete Cosine Transform (DCT). Image Compression Systems. JPEG Modes of Operation. JPEG Syntax and Data Organization. Entropy Coding Concepts. JPEG Binary Arithmetic Coding. JPEG Coding Models. JPEG Huffman Entropy Coding. Arithmetic Coding Statistical. More on Arithmetic Coding. Probability Estimation. Compression Performance. JPEG Enhancements. JPEG Applications and Vendors. Overview of CCITT, ISO, and IEC. History of JPEG. Other Image Compression Standards. Possible Future JPEG Directions. Appendix A. Appendix B. References. Index.
---
paper_title: Fractal image coding as generalized predictive coding

paper_content:

We point out that a prevalent form of fractal image coding can be viewed as a kind of generalized predictive coding. Several key issues in predictive coding are the prediction gain, the design of codebooks for predictors and prediction residuals, shaping of reconstruction errors, and codec complexity. Fractal coding can yield higher prediction gains than conventional predictive coding by its use of noncausal predictors and long-term predictors. However, noncausal prediction necessitates iterative decoding and long-term predictors require search over a large area, both of which increase codec complexity. Design of predictors and prediction codebooks for fractal coding has relied much on heuristics. Drawing on known results about predictive coding, we outline several directions for codec design, among which are short-term prediction and transform coding or vector quantization of prediction residuals. Shaping of reconstruction errors by noise-feedback or analysis-by-synthesis coding may also be beneficial. >
---
paper_title: Adaptive self-quantization of wavelet subtrees: a wavelet-based theory of fractal image compression

paper_content:

Fractal image compression was one of the earliest compression schemes to take advantage of image redundancy in scale. The theory of iterated function systems motivates a broad class of fractal schemes but does not give much guidance for implementation. Fractal compression schemes do not fit into the standard transform coder paradigm and have proven difficult to analyze. We introduce a wavelet-based framework for analyzing fractal block coders which simplifies these schemes considerably. Using this framework we find that fractal block coders are Haar wavelet subtree quantization schemes, and we thereby place fractal schemes in the context of conventional transform coders. We show that the central mechanism of fractal schemes is an extrapolation of fine-scale Haar wavelet coefficients from coarse-scale coefficients. We use this insight to derive a wavelet-based analog of fractal compression, the self-quantization of subtrees (SQS) scheme. We obtain a simple SQS decoder convergence proof and a fast SQS decoding algorithm which simplify and generalize existing fractal compression results. We describe an adaptive SQS compression scheme which outperforms the best fractal schemes in the literature by roughly 1 dB in PSNR across a broad range of compression ratios and which has performance comparable to some of the best conventional wavelet subtree quantization schemes.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Fractal image coding based on a theory of iterated contractive image transformations

paper_content:

The notion of fractal image compression arises from the fact that the iteration of simple deterministic mathematical procedures can generate images with infinitely intricate geometries known as fracial images [2]. The purpose of research on fractalbased digital image coding is to solve the inverse problem of constraining this complexity to match the realworld complexity of realworld images. In this. paper we propose a fractal image coding technique based on a mathematical theory of iterated transformations [1 2 3 7] which encompasses deterministic fractal geometry. Initial results were reported in [7 8]. The main characteristics of this technique are that (i) it is fractal in the sense that it approximates an original image by a fractal image and (ii) it is a blockcoding technique which relies on the assumption that image redundancy can be efficiently exploited through blockwise selfiransformabiliiy. We therefore refer to it as fracial blockcoding. The codingdecoding system is based on the construction for each original image given to encode of a specific image transformation which when iterated on any initial image produces a sequence of images which converges to a fractal approximation of the original. We show how to design such coders and thoroughly describe the implementation of a system for monochrome still images. Extremely promising coding results were obtained.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Image coding by block prediction of multiresolution subimages

paper_content:

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. >
---
paper_title: Vq-Encoding Of Luminance Parameters In Fractal Coding Schemes

paper_content:

This paper is concerned with the efficient storage of the luminance parameters in a fractal code by means of vector quantization (VQ). For a given image block (range) the collage error as a function of the luminance parameters is a quadratic function with ellipsoid contour lines. We demonstrate how these functions should be used in an optimal codebook design algorithm leading to a non-standard VQ-scheme. In addition we present results and an evaluation of this approach. The analysis of the quadratic error functions also provides guidance for optimal scalar quantization.
---
paper_title: Image compression using partitioned iterated function systems

paper_content:

The Partitioned Iterated Function Systems (PIFS) involves partitioning a image into non-overlapping range blocks and overlapping domain blocks. For each range block, a matching domain block is found by applying a contractive affine transformation. The set of transformations uniquely defines an estimation of the original image. In this paper, we investigate the quadtree partition technique of generating range blocks. In this technique, a range block is recursively partitioned into 4 equally sized sub-squares, when it is not covered well enough by a domain. But this method has a inherent penalty in which the existence of range blocks of different sizes requires the storage of the sizes and coordinates of the range blocks. We present a scheme that stores the required decoding information with very little overhead. One of the properties offractals is that detail exists at every scale. This has led us to investigate into the possibility of exploiting the scalability property of fractals to allow us to improve the compression time and ratio.
---
paper_title: Fractal Coding Performance for First Order Gauss-Markov Models

paper_content:

Fixed block size fractal coding is evaluated for first-order Gauss–Markov models and the effects of varying tile correlation are presented. Performance for this class of statistical models is found to be significantly suboptimal.
---
paper_title: Fractal wavelet coding using a rate-distortion constraint

paper_content:

We propose a hybrid fractal wavelet coder (FWC) which adopts adaptive fractal prediction in the wavelet domain and wavelet coding in this research. This new compression scheme uses wavelet coding as the core component, and applies contractive mapping (or the so-called fractal prediction) whenever it offers additional rate savings. A model based rate-distortion (R-D) criterion of low complexity is used to evaluate the fractal prediction efficiency and search for the best domain-range match. The superior R-D performance of FWC is demonstrated with extensive experimental results.
---
paper_title: Fractal coding versus classified transform coding

paper_content:

Fractal coding and classified transform coding exhibit strong structural similarity, but they use different types of redundancy in image data: piecewise self-similarity in one case and local correlation in the other. Comparing performance of the two techniques leads to a quantitative, compression-oriented definition of piecewise self-similarity. The amount of piecewise self-similarity is evaluated for sample images. For a moderate number of domain blocks, classified transform coding consistently outperforms fractal coding, and the images are not found to be piecewise self-similar. As the number of domain blocks increases, the performance gap becomes negligible.
---
paper_title: An inner product space approach to image coding by contractive transformations

paper_content:

Consideration is given to modeling of arbitrary digital gray tone images as the fixed points of contractive transformations on the image space. The transformation is designed to exploit a form of image redundancy called piecewise self-similarity. Results from inner product space theory are used to optimize the transformation within a class of affine transformations. The resulting transformation is described by a small amount of information compared to the original image, and its piecewise self-similar fixed point, found by successively iterating the transformation from any initial image, is close to the original image. Results are improved compared to earlier results with this technique. >
---
paper_title: An image coding scheme using block prediction of the pyramid subband decomposition

paper_content:

In this work, we propose a hybrid vector quantization scheme for general images that aims at exploiting similarities among detail signals in a multiresolution decomposition of the image. In a multiresolution decomposition, the image is decomposed into a set of subbands which are localized in scale, orientation and space. Our coding scheme consists of dividing each subimage of the multiresolution decomposition into square range blocks. The range blocks are matched against domain blocks chosen in the lower resolution subimage with the same orientation, and coded through a description of the map transforming the domain block into the range block. The pool of of domain blocks acts as a codebook for the range block, as in vector quantization, with the difference that the codebook is built from blocks inside the multiresolution decomposition. If the prediction procedure is not satisfactory with respect to a target quality, the block is coded using a geometric vector quantizer for Laplacian random variables. >
---
paper_title: A class of multiresolution stochastic models generating self-affine images

paper_content:

Fractal image compression is based on the rather poorly motivated assumption that "natural" images exhibit significant affine self-similarity. The accuracy of this assumption is evaluated by a comparison between the statistics of natural images and those of a multiresolution stochastic model designed to generate images exhibiting affine self-similarity as assumed by fractal coding techniques. These comparisons suggest that self-affinity does not represent a particularly accurate characterization of image statistics.
---
paper_title: Fractals and image representation

paper_content:

For some years now, ‘fractals’ have provided spectacular displays (which have seemingly hypnotised both the popular technical press and the ‘media’) on computer workstations equipped with high-power graphics processors, and also provoked much controversy with regard to their potential for mimicking real-world imagery. In this paper the authors briefly describe the theoretical background of fractal representations and investigate in more detail the validity of such an approach for applications in natural scene portrayal and coding.
---
paper_title: Fractal image coding using rate-distortion optimized matching pursuit

paper_content:

Matching pursuit is a general and flexible method for solving an optimization problem that is of interest in signal analysis, coding, control theory and statistics. In this paper, principles of rate-distortion optimal coding are used in combination with matching pursuit algorithm to obtain an enhanced fractal image coding method. The advantages of using such a method over traditional fractal image coders are described and compression results are presented.
---
paper_title: Fractal image coding: a review

paper_content:

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. >
---

Title: A Review of the Fractal Image Coding Literature

Section 1: INTRODUCTION
Description 1: Provide an overview of the fundamental principles of fractal image coding and its historical context, including Banach's fixed point theorem and the development of Iterated Function Systems (IFS) and Partitioned IFS (PIFS).

Section 2: PARTITION SCHEMES
Description 2: Discuss various image partition schemes, such as fixed size square blocks, quadtree, horizontal-vertical, irregular regions, polygonal blocks, overlapped blocks, and comparisons among these methods.

Section 3: BLOCK TRANSFORMS
Description 3: Describe different types of block transforms, distinguishing between block support transforms and block intensity transforms, and their importance in the fractal coding process.

Section 4: DOMAIN POOL SELECTION
Description 4: Examine the different strategies for selecting the domain pool, including global and local domain pools, synthetic codebooks, hybrid codebooks, and a comparative analysis of their effectiveness.

Section 5: ENCODING
Description 5: Outline the encoding process, focusing on the collage theorem, convergence issues, and strategies to achieve suboptimal and optimal encoding.

Section 6: SEARCH STRATEGIES
Description 6: Review various search strategies designed to improve the efficiency of the domain search process, including invariant representation, domain pool reduction, classification, distance bounds, multiresolution search, clustering, efficient distance computation, and nearest neighbour search.

Section 7: TRANSFORM REPRESENTATION
Description 7: Discuss methods for representing and quantising the transform parameters, including the use of quantisation, rate-distortion optimisation techniques, and approaches to minimise distortion.

Section 8: DECODING
Description 8: Detail the decoding process and its variations, such as standard decoding, successive correction decoding, hierarchical decoding, pixel chaining, postprocessing, and resolution independence.

Section 9: WAVELET ANALYSIS
Description 9: Explore the connection between fractal coding and wavelet analysis, including mappings between wavelet subtrees, the use of general wavelet bases, and alternative schemes involving subband prediction techniques.

Section 10: PERFORMANCE COMPARISONS
Description 10: Compare the performance of various fractal coding algorithms and identify the key factors contributing to their effectiveness based on empirical studies.

Section 11: CONCLUSIONS
Description 11: Summarize the overall findings of the review, discuss the theoretical and practical implications of fractal image coding, and suggest directions for future research.