Chair: Avideh Zakhor, University of California-Berkeley (USA)
Jaroslaw Domaszewicz, Texas A & M University (USA)
Vinay A. Vaishampayan, Texas A & M University (USA)
A part of a fractal code is an assignment of a domain block to every range block. The assignment is used to construct the dependence graph of a fractal code. The vertices of the graph represent the range blocks. Two vertices $x$ and $y$ are connected by a directed edge from $y$ to $x$ if the range block $y$ is overlapped, fully or partially, by the domain block assigned to the range block $x$. An algorithm to analyze the structure of the dependence graph is presented. The exposed structure of the graph can be used for three different purposes. The first one is convergence analysis: the affine transformations linking domain and range blocks can be classified into those that affect convergence and those that do not. The second one is decoding time reduction: certain range blocks can be reconstructed in a non-iterative way. The third one is improving upon collage coding: the affine transformations for some range blocks can be optimized based on the domain blocks extracted from the reconstructed rather than the original image.
Bernd Hurtgen, RWTH - Aachen (GERMANY)
This paper reports on investigations concerning the performance of fractal transforms. Emerging from the structural constraints of fractal coding schemes, lower bounds for the reconstruction error are given without regarding quantization noise. This implies finding an at least locally optimal transformation matrix. A full search approach is by definition optimal but also intractable for practical implementations. In order to simplify the calculation of some appropriate encoding parameter, the collage theorem and other fast but also suboptimal approaches are applied. For a memoryless Gaussian source and some real world images the optimal encoding parameters in view of the structural constraints are determined together with the minimal reachable distortion. This allows to quantify the performance of the suboptimal encoding procedures.
Hui Zhang, Southeast University (PEOPLES REPUBLIC OF CHINA)
Xiqi Gao, Southeast University (PEOPLES REPUBLIC OF CHINA)
Zhenya He, Southeast University (PEOPLES REPUBLIC OF CHINA)
A Modified Fractal Transform (MFT) is presented in this paper. In the function part of MFT, the conventional greyscale function of an image block is replaced by the greyscal function of an error image block which mean is removed. This fractal transform is used to approximate an image which we want to encode. The simulation results show that with MFT the image decoding process is very fast, typically only 1 to 3 iterations are required to reconstruct the image while the quality of reconstructed image remains high.
S. J. Woolley, University of Bath (U.K.)
D. M. Monro, University of Bath (U.K.)
We evaluate the fidelity/compression performance of fractal transforms over a range of parameters, using an rms error metric. We consider order of approximation, different (fixed) block sizes and various degrees of image searching. We 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/disortion performance is obtained with a lightly quantized higher order BFT, whose optimum block size increases with compression.
Lance M. Kaplan, University of Southern California (USA)
C.-C. Jay Kuo, University of Southern California (USA)
In this work, we propose a method called incremental Fourier synthesis to generate images based upon the 2-D extended self-similar (ESS) model. This algorithm creates the stationary increments of ESS processes by Fourier synthesis. Then, the increments are added up to generate the nonstationary 2-D ESS process. Because the new method can take advantage of the FFT, its computational complexity is only O(N^2 \log_2(N)), and its memory requirement is O(N^2) for an image of size N X N.
Syed A. Rizvi, State University of New York at Buffalo (USA)
Nasser M. Nasrabadi, State University of New York at Buffalo (USA)
The performance of an ordinary Vector Quantizer (VQ) can be improved by incorporating memory in the VQ scheme. A VQ scheme with finite memory known as Finite State Vector Quantization has been shown to give better performance than the ordinary VQ. The major problems with the FSVQ are the lack of accurate prediction of the current state, the state codebook design, and the amount of memory required to store all the state codebooks. This paper presents a new FSVQ scheme called Finite-State Residual Vector Quantization (FSRVQ) in which a neural network based state prediction is used. Furthermore, a novel tree-structured competitive neural network is used to jointly design the next-state and the state codebooks for the proposed FSRVQ. Simulation results show that the new scheme gives better performance with significant reduction in the memory requirement when compared to the conventional FSVQ schemes.
Young Tae Kim, Kwangwoon University (KOREA)
Hyung Hwa Ko, Kwangwoon University (KOREA)
In this paper, we propose a finite state vector quantization(FSVQ) with dynamic states according to the edges for image coding. A state is dynamically selected by considering the edge orientation of 4 neighboring blocks of a coding block. The state is decided as a part of the state blocks according to the edge characteristic. A state codebook is generated by reordering the super codebook using weighted nearest neighbor rule. This algorithm, different from CVQ, is devised to preserve edges at low bit rates without sending overhead bits for class information. In comparison with side match vector quantization (SMVQ) which is an example of FSVQ in the spatial domain, memory requiring for the storage of state codebook is further reduced because state space is reduced. Simulation result show 31.62dB in PSNR (Peak Sigal to Noise Ratio) at the 0.432 bit/pixel with fixed length code.
J. Skowronski, CNRS-ESE (FRANCE)
I. Dologlou, CNRS-ESE (FRANCE)
This paper describes the Permutative Vector Quantization (PVQ) scheme as a special case of a more general structurally constrained Vector Quantization concept. This concept makes it possible to increase the vector dimensions beyond the technical bounds of conventional VQ and to exploit, by means of this, the inter-pixel correlations in large image blocks. Furthermore, a codebook design algorithm adapted to Pemutative VQ is proposed and it is shown experimentally that the coding performance of conventional VQ can be improved using the present scheme.
Dongmei Wang, AT&T Bell Laboratories (USA)
John Hartung, AT&T Bell Laboratories (USA)
Codebook Adaptation Algorithm for a Scene Adaptive Video Coder In this paper, we propose a codebook adaptation algorithm for very low bit rate, real-time video coding. Although adaptive codebook design has been studied in the past, its implementation at very low coding rates suitable for the MPEG4 standard remains significantly challenging. Our coder uses a standard motion compensated predictor with DCT quantization. It is unique in that it uses a hybrid scalar/vector quantizer to code predictor residuals. Bits are dynamically allocated to minimize distortion in the current frame, and scalar quantized blocks are used to adapt the VQ codebook. A codebook adaptation algorithm is described which uses an "equidistortion principle" and a competitive learning algorithm to continuously adapt the codewords. This training algorithm results in an increased use of the more efficient vector quantizer and improved video quality.
Alexandru Bogdan, Columbia University (USA)
We extend the Iterated Transformation Theory $(ITT)$ fractal image coding algorithm proposed by A. Jacquin [1] to generate a pyramid image representation. An $ITT-coded$ image is modeled as the solution of a second kind functional equation. This representation is iterated to form an $ITT-chain$ of functional equations which can serve as the framework for a multiscale signal decomposition. This formalism can be extended to accommodate hybrid $ITT$ representations and, in the limit, $ITT-coded$ signals as a solution of a homogeneous functional equation. Existence of the $ITT-chain$ signal representation is shown to be connected to the eigen-structure of the linear operators of the associated functional equations. At each level of the $ITT-chain$ representation, the signal is decomposed into two parts which are not orthogonal. We use this decomposition to build an $ITT-pyramid$ representation for gray-tone images as well as for RGB color images.