Fractal image coding: a review

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     

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.     

Fractal modeling and segmentation for the enhancement of microcalcifications in digital mammograms

The objective of this research is to model the mammographic parenchymal and ductal patterns and enhance the microcalcifications using a deterministic fractal approach. According to the theory of deterministic fractal geometry, images can be modeled by deterministic fractal objects which are attractors of sets of two-dimensional (2-D) affine transformations. The iterated functions systems and the collage theorem are the mathematical foundations of fractal image modeling. Here, a methodology based on fractal image modeling is developed to analyze and model breast background structures. The authors show that general mammographic parenchymal and ductal patterns can be well modeled by a set of parameters of affine transformations. Therefore, microcalcifications can be enhanced by taking the difference between the original image and the modeled image. The authors' results are compared with those of the partial wavelet reconstruction and morphological operation approaches. The results demonstrate that the fractal modeling method is an effective way to enhance microcalcifications. It may also be able to improve the detection and classification of microcalcifications in a computer-aided diagnosis system.     

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

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

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.     

A nonlinear model for fractal image coding

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.     

Data hiding approach for efficient image indexing

A data hiding approach to embed the indexing keys inside the JPEG compressed images for their retrieval, inspired from the spirit of digital watermarking, is proposed. At the stage of database population, the existing approach is to compress all images by standard JPEG in order to save their storage space, but this ignores the compression of their indexing keys under the notion that the size of each indexing key is negligible. When a large image database is established, however, this part of storage space becomes non-trivial. By hiding the indexing keys inside the JPEG compressed codes, significant advantages are gained in that the indexing keys can be compressed naturally by JPEG without any additional cost. Experiments on hiding an indexing key of 256 bytes illustrate that: no noticeable distortion is introduced in comparison with non-watermarked images; and their storage space is reduced into the region of 7-27% of their original size.     

基于嵌入式零树小波编码直方图图像检索

图像和视频应用的快速增长，使得根据图像和视频内容进行查询的技术变得越来越重要，人们提出了许多基于像素域或压缩域的图像检索技术，因为多媒体数据库通常具有相当大的数据量，所以基于像素域图像检索技术的计算复杂度相当大，因此，许多文献提出更快的基于压缩域的图像检索技术，本文提出一种改进的基于嵌入式零树小波编码直方图的图像检索技术，特征提取综合考虑图像的颜色，纹理，频率和空间信息，所有的特征可以在压缩过程中自动得到，图像检索的过程就是匹配待检索图像和来自数据库的侯选图像的索引，实验证明这种方法具有好的检索性能。     

分形图像压缩

欧氏几何学不能处理自然界中非常复杂的形状，这只能借助于分形几何学，分形图像压缩就是利用分形几何学的有关原理进行编码，达到图像压缩之目的。     

Parameter analysis of fractal image compression and its applications in image sharpening and smoothing

In recent years, numerous fractal image compression (FIC) schemes and their applications in image processing have been proposed. However, traditional FIC ignores the importance of affine parameters in the iterated function system (IFS) and affine parameters are kept invariant for a certain image in almost all of these schemes. By analyzing fractal compression technology in this paper, we show that the affine parameters in IFS can vary with different image quality measurements. A positive correlation exists between the image contrast of fractal decoded image and affine scalar multiplier. This strong correlation demonstrates that an image can be sharpened or smoothed using fractal compression technology.     

A fractals-inspired approach to binary image database indexing and retrieval

This paper applies ideas from fractal compression and optimization theory to attack the problem of efficient content-based image indexing and retrieval. Similarity of images is measured by block matching after optimal (geometric, photometric, etc.) transformation. Such block matching which, by definition, consists of localized optimization, is further governed by a global dynamic programming technique (Viterbi algorithm) that ensures continuity and coherence of the localized block matching results. Thus, the overall optimal transformation relating two images is determined by a combination of local block-transformation operations subject to a regularization constraint. Experimental results on some limited subsets of still binary images from the mpeg-7 database demonstrate the power and potential of the proposed approach.     

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.     

一种基于人眼对比度敏感视觉特性的图像自适应量化方法

为了提高图像的压缩比和压缩质量,结合人眼对比度敏感视觉特性和图像变换域频谱特征,该文提出一种自适应量化表的构建方法。并将该表代替JPEG中的量化表,且按照JPEG的编码算法对3幅不同的彩色图像进行了压缩仿真实验验证,同时与JPEG压缩作对比分析。实验结果表明：与JPEG压缩方法相比,在相同的压缩比下,采用自适应量化压缩后,3幅解压彩色图像的SSIM和PSNR值分别平均提高了1.67%和4.96%。表明该文提出的结合人眼视觉特性的自适应量化是一种较好的、有实用价值的量化方法。     

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.     

A Parallel ASIC Architecture for Efficient Fractal Image Coding

Fractal image coding is a compression technique with many promising features, but it has been primarily placed in the class of archival coding algorithms due to its computationally expensive encoding algorithm. Though fractal coding has been extensively optimized for speed, it is still not practical for real-time applications on most sequential machines. The problem with fractal coding lies in the large amount of pixel block comparisons that are required, which makes fractal coding better suited toward parallel systems. At the same time, VLSI area has become a much less important constraint in chip design due to better fabrication techniques and smaller micron technologies. This has lead to a recent trend for designing parallel subsystems and including multimedia ASIC circuitry on general purpose CPUs. In this paper, we will present a parallel ASIC array architecture for use in fractal encoding that performs a full domain quad-tree search in near real-time for standard sized gray scale images. The design is also scalable so that larger images can be encoded faster by adding chips to the array. In designing this architecture, we include novel optimizations at the algorithmic, architecture, and circuit levels.     

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

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

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.     

Compression of image block means for non-equal block partition schemes using Delaunay triangulation and prediction

An approach based on applying Delaunay triangulation to the compression of mean values of image blocks that have non-identical shape and size is proposed. It can be useful for image compression methods that require the use of image partition schemes with non-equal block sizes, such as fractal and DCT-based image coding. Some aspects of practical realisation of the proposed method are discussed. Evaluation of the performance of the proposed method is carried out and comparisons with some conventional methods are made, demonstrating the potential of the method.     

Quantitative characterization of electron micrograph image usingfractal feature

In this investigation, texture analysis was carried out on electron micrograph images. Fractal dimensions and spatial grey level co-occurrence matrices statistics were estimated on each homogeneous region of interest, The fractal model has the advantages that the fractal dimension correlates to the roughness of the surface and is stable over transformations of scale and linear transforms of intensity. It can be calculated using three different methods. The first method estimates fractal dimension based on the average intensity difference of pixel pairs. In the second method, fractal dimension is determined from the Fourier transformed domain. Finally, fractal dimension can be estimated using reticular cell counting approach. Moreover, automatic image segmentation was performed using fractal dimensions, spatial grey level co-occurrence matrices statistics, and grey level thresholding. Each image was segmented into a number of regions corresponding to distinctly different morphologies: heterochromatin, euchromatin, and background. Fractal dimensions and spatial grey level co-occurrence matrices statistics were found to be able to characterize and segment electron micrograph images     

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

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