A wavelet-based analysis of fractal image compression

Why does fractal image compression work? What is the implicit image model underlying fractal block coding? How can we characterize the types of images for which fractal block coders will work well? These are the central issues we address. We introduce a new wavelet-based framework for analyzing block-based fractal compression schemes. Within this framework we are able to draw upon insights from the well-established transform coder paradigm in order to address the issue of why fractal block coders work. We show that fractal block coders of the form introduced by Jacquin (1992) are Haar wavelet subtree quantization schemes. We examine a generalization of the schemes to smooth wavelets with additional vanishing moments. The performance of our generalized coder is comparable to the best results in the literature for a Jacquin-style coding scheme. Our wavelet framework gives new insight into the convergence properties of fractal block coders, and it leads us to develop an unconditionally convergent scheme with a fast decoding algorithm. Our experiments with this new algorithm indicate that fractal coders derive much of their effectiveness from their ability to efficiently represent wavelet zero trees. Finally, our framework reveals some of the fundamental limitations of current fractal compression schemes.     

Region-based fractal image compression

A fractal coder partitions an image into blocks that are coded via self-references to other parts of the image itself. We present a fractal coder that derives highly image-adaptive partitions and corresponding fractal codes in a time-efficient manner using a region-merging approach. The proposed merging strategy leads to improved rate-distortion performance compared to previously reported pure fractal coders, and it is faster than other state-of-the-art fractal coding methods.     

分形在视频图像压缩中的应用

阐述了分形图像压缩的理论基础,了分形在视频图像空中的应用。分形图像压缩编码方法能够实现很高的压缩比,具有很高的实用价值。     

Combining fractal image compression and vector quantization

In fractal image compression, the code is an efficient binary representation of a contractive mapping whose unique fixed point approximates the original image. The mapping is typically composed of affine transformations, each approximating a block of the image by another block (called domain block) selected from the same image. The search for a suitable domain block is time-consuming. Moreover, the rate distortion performance of most fractal image coders is not satisfactory. We show how a few fixed vectors designed from a set of training images by a clustering algorithm accelerates the search for the domain blocks and improves both the rate-distortion performance and the decoding speed of a pure fractal coder, when they are used as a supplementary vector quantization codebook. We implemented two quadtree-based schemes: a fast top-down heuristic technique and one optimized with a Lagrange multiplier method. For the 8 bits per pixel (bpp) luminance part of the 512kappa512 Lena image, our best scheme achieved a peak-signal-to-noise ratio of 32.50 dB at 0.25 bpp.     

一种改进的分形图像压缩算法

为了缩短分形编码时间,通过对图像定义域块和值域块的统计特性分析,提出了改进的分形压缩算法。设计最优匹配定义域块自适应搜索方法,缩短搜索范围;用值域块均值代替灰度偏移量,减少计算量。实验证明,运用这种改进的分形图像压缩算法进行图像压缩,在保持较高的解压图像质量的情况下,大幅缩短图像压缩编码时间。     

Decoding algorithm for fractal image compression

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     

Region-based fractal image compression using heuristic search

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.     

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.     

分形图象压缩编码的回顾与展望

介绍了分析图象压缩编码的历史和现状，以及几种方法的分形压缩技术，总结了近年来在分形图象压缩编码方法所取得的重要进展，并提出了一种新的序列图象分形编码的思路。     

Fast fractal image compression using the Hadamard transform

A new algorithm for fractal image compression is developed to speed up the encoder. This new method converts image blocks into frequency-like domains using the Hadamard transform, in which the computations of the best matched are performed. At each search entry, the best mean square error computations of the eight dihedral symmetries are reformulated into the form of inner products. By a precise derivation, all redundant computations are completely avoided. With this improved technique, the complexity of the encoder is substantially reduced. A simulation shows that, with the same PSNR and compression ratio, the new method requires less computation time than the baseline method     

Technique for fractal image compression using genetic algorithm

A new method for fractal image compression is proposed using genetic algorithm (GA) with an elitist model. The self transformation property of images is assumed and exploited in the fractal image compression technique. The technique described utilizes the GA, which greatly decreases the search space for finding the self similarities in the given image. This article presents theory, implementation, and an analytical study of the proposed method along with a simple classification scheme. A comparison with other fractal-based image compression methods is also reported.     

Hybrid image compression method based on fractal geometry

A hybrid method for image compression based on the fractal geometry concept is presented. By combining the scanline subtraction and prediction mechanism with the yardstick-based compression method, higher compression rate can be achieved with good image quality. Furthermore, the performance of the algorithm is improved through error compensation.<>     

Speed-up fractal image compression with a fuzzy classifier

This paper presents a fractal image compression scheme incorporated with a fuzzy classifier that is optimized by a genetic algorithm. The fractal image compression scheme requires to find matching range blocks to domain blocks from all the possible division of an image into subblocks. With suitable classification of the subblocks by a fuzzy classifier we can reduce the search time for this matching process so as to speedup the encoding process in the scheme. Implementation results show that by introducing three image classes and using fuzzy classifier optimized by a genetic algorithm the encoding process can be speedup by about 40% of an unclassified encoding system.     

子块均点特征分形快速图像压缩编码

分形图像压缩根据图像特有的自相似性,利用压缩仿射变换消除图像数据冗余度,进而实现图像压缩,实现较高的压缩比。然而,分形图像压缩编码具有计算复杂度高、运行时间过长的致命缺点,对于图像信息量巨大的当今社会来说不具有实用性。为解决基本分形压缩编码耗时过长的问题,提出了子块均点特征分形压缩编码算法,利用该算法将基本分形压缩编码的全搜索转为局部搜索,限定搜索范围,减少定义域块的搜索,在客观质量稍作牺牲的基础上加快了编码速度。将所提算法分别与五点和特征算法、1-范数特征算法、欧式比特征算法以及双交叉算法进行比较,仿真结果表明,在时间稍逊的情况下,所提算法在客观质量（Peak Signal-to-Noise Ratio,PSNR）上更优。     

Fast fractal image compression based on one-norm of normalised block

An accelerating algorithm based on one-norm of the normalised block is proposed for fractal image coding. It can catch the best-matched block to a range block with a reduced search. Simulations show that it yields the same or superior quality as the baseline algorithm, while its runtime is shortened about 19 times.     

Statistical feature extraction based technique for fast fractal image compression

Fractal image compression is an innovative way of image representation by using relationships among the sub-section of image itself. It utilizes the existence of self-symmetry and uses affine contractive transforms. This technique has manifold advantages like, very high compression ratio, high decompression speed, high bit-rate and resolution independence, but high computation time expenses of suitable domain search in coding phase is the major bottleneck of the technique. This paper presents a fast fractal compression scheme based on feature extraction and innovative way of image comparison. In proposed development the complexity of suitable domain search is reduced by transforming the problem from image domain to vector domain. Simulation results confirms that suggested variant leads to a faster system as compared to existing state-of art Fractal Image Compression techniques.     

Genetic algorithm based on discrete wavelet transformation for fractal image compression

In this paper, a genetic algorithm (GA) based on discrete wavelet transformation (DWT) is proposed to overcome the drawback of the time-consuming for the fractal encoder. First, for each range block, two wavelet coefficients are used to find the fittest Dihedral block of the domain block. The similar match is done only with the fittest block to save seven eighths redundant MSE computations. Second, embedding the DWT into the GA, a GA based on DWT is built to fast evolutionary speed further and maintain good retrieved quality. Experiments show that, under the same number of MSE computations, the PSNR of the proposed GA method is reduced 0.29 to 0.47 dB in comparison with the SGA method. Moreover, at the encoding time, the proposed GA method is 100 times faster than the full search method, while the penalty of retrieved image quality is relatively acceptable.     

Adaptive vector-valued martingales: applications to image compression

Given a finite collection of functions defined on a common probability space, the paper describes an algorithm that constructs a vector-valued approximating martingale sequence. The orthonomal basis functions used to construct the martingale approximation are optimally selected, in each greedy step, from a large dictionary. The resulting approximations are characterized as generalized H-systems and provide scalar- and vector-valued orthonormal systems that can be employed to perform lossy compression for the given set of input functions. The filtration associated to the martingale allows for a multi-resolution analysis/synthesis algorithm to compute the approximating conditional expectation via a Fourier expansion. Convergence of the algorithm as well as several computational properties are established. Numerical examples are also provided for collection of images and video frames in order to study the approximating power of the constructed sequences.     

T-matrix and its applications in image processing

A T-matrix used for image scrambling is proposed and its periodicity is proved. The T-matrix has a simple conformation and a period twice as long as the Arnold matrix. It can be applied to image encryption and pre-processing in image processing such as image watermarking algorithms. Two examples of applications are given.     

Error-free computation of Daubechies wavelets for image compression applications

A novel encoding scheme for Daubechies wavelets is proposed. The technique eliminates the requirements to approximate the transformation matrix elements; rather, by using algebraic integers, it is possible to obtain exact representations for them. As a result, error-free calculations up to the final reconstruction step can be achieved, which provides considerable improvement in image reconstruction accuracy.