A fractal vector quantizer for image coding

We investigate the relation between VQ (vector quantization) and fractal image coding techniques, and propose a novel algorithm for still image coding, based on fractal vector quantization (FVQ). In FVQ, the source image is approximated coarsely by fixed basis blocks, and the codebook is self-trained from the coarsely approximated image, rather than from an outside training set or the source image itself. Therefore, FVQ is capable of eliminating the redundancy in the codebook without any side information, in addition to exploiting the self-similarity in real images effectively. The computer simulation results demonstrate that the proposed algorithm provides better peak signal-to-noise ratio (PSNR) performance than most other fractal-based coders.     

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.     

Fractal curves to improve the reversible data embedding for VQ-indexes based on locally adaptive coding

The VQ reversible data embedding technology allows an original VQ coding to be completely restored after the extraction of embedded data. In this paper, we propose a new reversible scheme based on locally adaptive coding for VQ-compressed images. The fractal Hilbert curve is applied to replace the traditional trace of processing the VQ index table. The VQ index table is pre-processed to create a fractal Hilbert curve. Following the curve to process the VQ index table can get better compression rates in the data embedding procedure. Besides, compared to Chang et al.’s scheme, which compressed the inputted VQ index value only when the to-be-embedded bit b is 0, our method performs compressing operations in both cases that the to-be-embedded bits b are 0 and 1. The experimental results show that the proposed method has the best compression rate and the highest embedding capacity compared with other reversible VQ embedding methods.     

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

Fractal coding of video sequence using circular prediction mappingand noncontractive interframe mapping

We propose a novel algorithm for fractal video sequence coding, based on the circular prediction mapping and the noncontractive interframe mapping. The proposed algorithm can effectively exploit the temporal correlation in real image sequences, since each range block is approximated by the domain block in the adjacent frame, which is of the same size as the range block. The computer simulation results demonstrate that the proposed algorithm provides very promising performance at low bit rate, ranging from 40-250 kbyte/s.     

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.     

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.     

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.     

Iteration-free fractal image coding based on efficient domain pooldesign

The domain pool design is one of the dominant issues which affect the coding performance of fractal image compression. In this paper, we employ the LBG algorithm and propose a block averaging method to design the efficient domain pools based on a proposed iteration-free fractal image codec. The redundancies between the generated domain blocks are reduced by the proposed methods. Therefore, we can obtain the domain pools that are more efficient than those in the conventional fractal coding schemes and thus the coding performance is improved. On the other hand, the iteration process in the conventional fractal coding scheme not only requires a large size of memory and a high computation complexity but also prolongs the decoding process. The proposed iteration-free fractal codec can overcome the problems above. In computer simulation, both the LBG-based and block-averaging methods for the domain pool design in the proposed iteration free scheme achieve excellent performances. For example, based on the proposed block-averaging method, the decoded Lena image has at least a 0.5 dB higher PSNR (under the same bit rate) and an eight-time faster decoding speed than the conventional fractal coding schemes that require iterations.     

Regularised restoration of vector quantisation compressed images

The authors study the application of image restoration technology in improving the coding performance of a vector quantisation (VQ) image compression codec. Restoration of VQ-compressed images is rarely addressed in the literature, and direct applications of existing restoration techniques are generally inadequate to deal with this problem. A restoration algorithm is proposed, specific to VQ-compressed images, that makes good use of the codebook to derive useful a priori information for restoration. The proposed restoration algorithm is shown to be capable of improving the quality of a VQ-compressed image to a much greater extent, compared with other existing restoration approaches. As no extra information, other than the codebook, is required to carry out the restoration with the proposed algorithm, no transmission overhead is necessary and hence, it can be fully compatible with any VQ codec when used to improve coding performance     

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.     

基于图像块整体稀疏性与流形投影的压缩成像

如何利用自然图像本身固有的先验知识来提高重构图像质量是压缩成像系统的一个关键问题.本文在压缩成像系统中融合图像块整体稀疏性与流形特性,提出了一种高质量压缩成像算法.在该算法中,图像块由字典稀疏表示,同时还可由一组与图像块位于同一低维流形上的近邻点线性逼近,从而使稀疏重建信号分布在原始信号所处的流形附近.另外本文充分利用了图像中任意位置处图像块的稀疏性先验知识,使得压缩成像算法在低采样率下能重构出质量较高的图像.     

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

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

基于邻近像素的低复杂度预测矢量量化 图像压缩编码算法

针对传统低复杂度预测矢量量化图像编码算法预测准确性的不足,通过分析像素距离对相关性的影响,提出了数种改进的基于邻近像素的预测方案,并提出了一种具有边缘走向自适应性的预测方案.仿真实验表明,采用这些预测方案的预测矢量量化算法能够在保持低计算复杂度的同时,显著提高矢量预测准确度,改善图像编码性能.     

Vector quantization using tree-structured self-organizing featuremaps

In this paper, we propose a binary-tree structure neural network model suitable for structured clustering. During and after training, the centroids of the clusters in this model always form a binary tree in the input pattern space. This model is used to design tree search vector quantization codebooks for image coding. Simulation results show that the acquired codebook not only produces better-quality images but also achieves a higher compression ratio than conventional tree search vector quantization. When source coding is applied after VQ, the new model performs better than the generalized Lloyd algorithm in terms of distortion, bits per pixel, and encoding complexity for low-detail and medium-detail images     

Progressive Image Transmission Using LOT with Two-Channel Conjugate VQ

A progressive image transmission (PIT) scheme based on the classified two-channel conjugate VQ (TCCVQ) technique in the lapped orthogonal transform (LOT) domain is proposed. Conventional block transform coding of images using DCT produces in general undesirable block-artifacts at low bit rates. In this paper, image blocks are transformed using the LOT and classified into four classes based on their structural properties and further subdivided adaptively into subvectors depending on the LOT coefficient statistics to improve the reconstructed image quality by adaptive bit allocation. The subvectors are quantized using the two-channel conjugate VQ technique which has less computational complexity and less storage memory, and is more robust against channel errors. The vector quantized subvectors are transmitted and decoded in stages so that an image is progressively reconstructed, i.e., initially a crude version followed by quality build up in successive stages as the occasion demands in interactive visual communications. Coding tests using computer simulations show that the LOT/TCCVQ-based PIT of images is an effective coding scheme. The results are also compared with those obtained using conventional classified VQ in both the DCT and LOT domains.     

A novel gray image representation using overlapping rectangular NAM and extended shading approach

In this paper, inspired by the idea of overlapping rectangular region coding of binary images, we extend the SDS design, which is based on overlapping representation from binary images to gray images based on the non-symmetry and anti-packing model (NAM). A novel gray image representation is proposed by using the overlapping rectangular NAM (RNAM) and the extended Gouraud shading approach, which is called ORNAM representation. Also, we present an ORNAM representation algorithm of gray images. The encoding and the decoding of the proposed algorithm can be performed in O(n log n) time and O(n) time, respectively, where n denotes the number of pixels in a gray image. The wrong decoding problem of the hybrid matrix R for the overlapping RNAM representation of gray images is solved by using the horizontal, vertical, and isolated matrices, i.e., H, V and I, respectively, which are used to identify the vertex types. Also, we put forward four criteria of anti-packing homogeneous blocks. In addition, by redefining a codeword set for the three vertices symbols, we also propose a new coordinate data compression procedure for coding the coordinates of all non-zone elements in the three matrices H, V and I. By taking some idiomatic standard gray images in the field of image processing as typical test objects, and by comparing our proposed ORNAM representation with the conventional S-Tree Coding (STC) representation, the experimental results in this paper show that the former has higher compression ratio and less number of homogeneous blocks than the latter whereas maintaining a satisfactory image quality, and therefore it is a better method to represent gray images.     

Blocking effect reduction of compressed images using classification-based constrained optimization

In this paper we propose an adaptive image restoration algorithm using block-based edge-classification for reducing block artifacts in compressed images. In order to efficiently reduce block artifacts, edge direction of each block is classified by using model-fitting criterion, and the constrained least-squares (CLS) filter with corresponding direction is used for restoring the block. The proposed restoration filter is derived based on the observation that the quantization operation in a series of coding processes is a nonlinear and many-to-one mapping operator. Then we propose an approximated version of a constrained optimization technique as a restoration process for removing the nonlinear and space-varying degradation operator. For real-time implementation, the proposed restoration filter can be realized in the form of a truncated FIR filter, which is suitable for postprocessing reconstructed images in digital TV, video conferencing systems, etc.