Image coding based on a fractal theory of iterated contractiveimage transformations

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.     

Progressive decoding method for fractal image compression

Fractal image compression is an efficient technique for compactly coding images, in which an image is encoded by a contractive transformation whose fixed point is close to the original image, and then is decoded by using an iteration procedure stemmed from the well known Banach fixed-point theorem. A new fixed-point iteration theorem with a control parameter is presented, which provides a novel iteration procedure that progressively approaches the fixed point of a contractive transformation and particularly reverts back to the conventional iteration procedure when the control parameter is set as one. Based on the new iteration procedure, a progressive decoding algorithm is proposed for fractal image compression, which does not need any specific fractal encoder and is useful for low bandwidth transmission. The experimental results demonstrate that the progressive fractal decoding is capable of controlling the decoding iteration procedure by varying the control parameter values and displaying progressively how the original image is obtained from a black image or another image at each step of the increasing iterations.     

A review of the fractal image coding literature

Fractal image compression is a technique based on the representation of an image by a contractive transform, on the space of images, for which the fixed point is close to the original image. This broad principle encompasses a very wide variety of coding schemes, many of which have been explored in the rapidly growing body of published research. While certain theoretical aspects of this representation are well established, relatively little attention has been given to the construction of a coherent underlying image model that would justify its use. Most purely fractal-based schemes are not competitive with the current state of the art, but hybrid schemes incorporating fractal compression and alternative techniques have achieved considerably greater success. This review represents a survey of the most significant advances, both practical and theoretical, since the publication of Jacquin's (1990) original fractal coding scheme.     

Distortion Minimization with Fast Local Search for Fractal Image Compression

Optimal fractal image coding is an NP-hard combinatorial optimization problem, which consists of finding in a finite set of contractive affine mappings one whose unique fixed point is closest to the original image. Current fractal image schemes are based on a greedy suboptimal algorithm known as collage coding. In a previous paper, Hamzaoui, Hartenstein, and Saupe proposed a local search algorithm that iteratively improves an initial solution found by collage coding. For a standard fractal scheme based on quadtree image partitions, peak-signal-to-noise ratio (PSNR) gains are up to 0.8 dB. However, the algorithm is time-consuming because it involves many iteration steps, each of which requires the computation of the fixed point of an affine mapping. In this paper, we provide techniques that drastically reduce the complexity of the algorithm. Moreover, we show that the algorithm is also successful with a state-of-the-art fractal scheme based on highly adaptive image partitions.     

引入非线性变换的分形图像压缩编码

提出了一种基于非线性变换的分形图像压缩编码方法。证明了引入的非线性变换满足压缩迭代映射理论。模拟实验的结果表明 ,与传统的分形图像压缩编码方法相比 ,压缩比和峰值信噪比均有所改善。     

Isometry-Based Shape-Adaptive Fractal Coding for Images

Fractal image coding is an effective method to eliminate the image redundancy through piecewise self-transformability. The fractal code consists of a set of contractive affine transforms. To improve the performance when a range block experiences large error, we usually partition the range block into square or nonsquare subrange blocks for two- or multilevel fractal coding. In this paper, we find an inherent property of fractal coding that can be used to decide the edge orientation of a range block. Then this property is used for shape-adaptive fractal coding (SAFC). In SAFC, the top-level range block is partitioned into square or nonsquare (rectangle or triangle) subrange blocks for multilevel fractal encoding. Here, the maximum size of the range block can be the same as that of the whole image size while the minimum size is 4×4. In SAFC, no additional computations are required to obtain the edge orientation of a range block. Instead, we propose an edge-orientation detector, where the edge orientation of a range block is obtained during the fractal encoding process. According to our simulation results, SAFC can reduce the bit rate requirement of the conventional fractal coding scheme.     

Fractal coding of subbands with an oriented partition

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.     

Still image coding based on vector quantization and fractalapproximation

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.     

Image coding by block prediction of multiresolution subimages

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.     

基于亚取样分形插值预测的混合图像编码方法

提出了一种基于亚取样分形插值预测的混合图像编码方法。将原始图像在水平方向和垂直方向皆作１／２抽取得到一幅“亚抽图像”，对亚抽图像进行分形编码得到亚抽图像的分形码，采用分形插值方法由亚抽图像的分形码解码得到原始图像的分形预测图像，然后对预测误差图像进行基于ＤＣＴ的自适应补偿编码。实验表明，这种方法的编码速度有了很大提高，而且恢复图像的质量具有较高的保真度。     

Combined Kohonen neural networks and discrete cosine transform method for iterated transformation theory

Iterated transformation theory (ITT) coding, also known as fractal coding, in its original form, allows fast decoding but suffers from long encoding times. During the encoding step, a large number of block best-matching searches have to be performed which leads to a computationally expensive process. Because of that, most of the research efforts carried on this field are focused on speeding up the encoding algorithm. Many different methods and algorithms have been proposed, from simple classifying methods to multi-dimensional nearest key search. We present in this paper a new method that significantly reduces the computational load of ITT-based image coding. Both domain and range blocks of the image are transformed into the frequency domain (which has proven to be more appropriate for ITT coding). Domain blocks are then used to train a two-dimensional Kohonen neural network (KNN) forming a codebook similar to vector quantization coding. The property of KNN (and self-organizing feature maps in general) which maintains the input space (transformed domain blocks) topology allows to perform a neighboring search to find the piecewise transformation between domain and range blocks.     

Content-based image retrieval using block-constrained fractalcoding and nona-tree decomposition

Fractal coding has been proved useful for image compression. In fractal coding, an image is represented by a number of self-transformations (fractal code) by which an approximation of the original image can be reconstructed. The authors present a block-constrained fractal coding scheme and a nona-tree decomposition based matching strategy for content-based image retrieval. In the coding scheme, an image is partitioned into non-overlapped blocks with a size close to that of a query iconic image. The fractal code is generated for each block independently. In the similarity measure of the fractal code, an improved nona-tree decomposition scheme is adopted to avoid matching the fractal code globally in order to reduce computational complexity. The experimental results show that the authors' coding scheme and matching strategy are useful for image retrieval, and compare favourably with two other methods tested in terms of storage usage and computing time     

基于方差不变特性的快速分形图像编码方法

本文结合图像子块的自身统计特性，提出一种基于方差不变特性的快速分形编码方法。实验结果表明，该方法可使编码速度有较大提高，而解码图像质量无明显下降；且有相对确定的编码时间，有助于编码系统的硬件实现。     

基于小波分析的分形图像去噪压缩方法

近十几年来,分形(Fractal)在图像压缩技术中的应用已成为图像数据压缩领域中最为热点的问题之一。其压缩比在理论上可超过经典压缩方法的几个数量级。但实际上,原始图像经常被噪声污染。噪声的存在一方面使得图像编码的时间延长,另一方面降低了图像的信噪比,使图像质量明显下降。本文对小波变换、分形压缩编码的原理和特点进行了分析;结合小波变换和分形压缩编码,利用分形的自相似性,研究了基于小波域的分形图像去噪、压缩方法。该方法有效地减少了计算复杂度和编码时间并获得了良好的图像质量。实验结果表明,该方法在较大的压缩范围内,能够获得好的压缩结果,同时也表明采用这种方法的潜力之所在。     

结合判别函数的分形IFS图像检索

该文提出一种分形编码的图像比对搜索方法,即把迭代函数系可反映图像的拓扑特性,用于图像的储存和检索.而图像经过分形编码后,得到大量资料,需要一个有效的方法进行检索,文中根据Fisher判别函数来判定图像相似度.实验结果表明,图像比对搜索引擎能准确找出查询图像的相似图像外,还证实本方法对图像有一定的容错性能,能有效地提高图像比对搜索引擎在实际应用中的可适性。     

基于矢量量化的层次分形编码方法

文中提出了一种新的分形图像压缩方法,该方法将矢量量化的概念应用于分形块编码中,对图像的平缓区进行矢量量化的线性组合编码,对图像的丰富细节区用分形编码,并且在分形编码时,采取了层次处理。实验表明,与基本的分形块编码方法相比,本文提出的矢量量化层次分形编码方法在保证一定的重建图像质量下,使图像的压缩比有了明显的提高,并且大大提高了编码和解码速度。     

多波段遥感图像的快速分形编码

分形图像编码用动态迭代过程的参数来表示相应的静态图像数据,可以突破熵压缩编码的理论界限,因而得到广泛的关注.将分形图像编码应用于多波段遥感图像压缩中,根据多波段遥感图像的特点,对基于四叉树分割的快速分形编码方法进行改进,令各个波段图像共享同一四叉树分割方式,同时,利用多波段遥感图像的谱间相关性,缩小仿射变换的搜索匹配空间,以此来提高压缩比和编码速度,实验表明,本方法能显著提高基于四叉树分割的分形编码方法的性能,取得了令人满意的结果.     

基于自适应四叉树分形图像编码的数字水印技术

提出了一种基于自适应四叉树分形编码的数字水印技术。对原始图像进行四叉树分形编码后，通过给定子块在不同的寻找区域中搜索其最佳匹配父块来嵌入水印。实验结果表明，本方法在嵌入水印编码时间、图像质量和鲁棒性方面均比传统的方法有较大的改进。     

Hybrid fractal image coding with quadtree-based progressive structure

A progressive structure which takes the quadtree depth into consideration is proposed for fractal image coding. Simulation results show that its image quality at different received data rates is better than that without considering the quadtree level. Then, a hybrid fractal image coding scheme based on traditional and no-search fractal image coding with the proposed progressive structure is suggested. The image quality and compression ratio can be controlled by a threshold, which makes it downward compatible to the no-search fractal image coding. Experimental results justify that the progressive performance of the proposed scheme is better than that of traditional fractal image coding.     

基于分形的混合图象压缩方法

分形图象压缩方法是近年来迅速兴起的一种高倍率图象压缩方法，它依据分形原理，利用迭代函数系统（IFS）来抽取自然图象中的自相似性，达到压缩图象的目的；解码时利用拼帖定理来快速恢复图象。然而它最大的缺点是速度太慢。为此，本文将分形图象压缩同传统的块截取变换方法（BlockTruncatingCoding）结合，在压缩速度、压缩倍数和压缩失真方面有个折衷，达到较好的性能。