This paper extends the concept of embedded wavelet still image coding to video coding. The starting point of our work is the SPIHT image codec introduced by Said and Pearlman in (1996). We choose this algorithm because of its simplicity and its high efficiency. Our goal is to streamline its performance in order to explore its potential in real time software-only video coding applications. At low rates, the computational bottleneck of the SPIHT algorithm is in the forward and inverse wavelet transforms. To circumvent this problem, we propose a template-based filtering approach which replaces all multiplies by indexing operations. Unlike other multiplierless filtering techniques, the distortion penalty paid for the reduction in complexity is negligible. Furthermore, the proposed technique can efficiently accommodate progressive reconstruction. Specifically, we show that bitwise progressive reconstruction, i.e., updating the output after receiving each new refinement bit, can be achieved with a complexity proportional to the number of nonzero bits transmitted. This approach is specially interesting for data transmission over low bandwidth channels.

Subband image coding is one of the most efficient image compression techniques known to date. Its advantages over standard techniques based on transform coding are particularly important at very low bit rates. The ability offered by a multiresolution decomposition approach to separately quantize the information contained in different frequency bands of an image, according to a criterion that accounts for the different sensitivity of the human visual system to each band, is crucial to the success of the technique. At low bit rates, the bands with lower energy content (usually the higher frequency bands) are very coarsely quantized, which accounts for most of the coding gain. Image quality is preserved by finely quantizing the higher energy content bands, commonly associated with the low frequency areas of the spectrum. We propose a fast and efficient method of achieving this goal. Our method is based on the combination of entropy coding with three types of scalar quantization: (i) scalar quantization, (ii) finite-state scalar quantization (FSSQ) and (iii) predictive FSSQ (PFSSQ). Scalar quantization is applied to bands with very low inter-pixel correlation, whereas FSSQ is used for bands with medium to high inter-pixel correlation. The common case that the lowest frequency band of an image exhibits linear inter-pixel correlation is exploited through PFHSQ, which uses a contextual model of the quantized prediction error to more accurately encode it. Uniform quantizers have been used throughout. The results of our experiments show that this system is specially well suited to very low bit rate image coding.

A new finite-state vector quantization (FSVQ) algorithm is developed based on state space optimization and the derailment prevention requirement. The proposed derailment-free FSVQ (DF-FSVQ) achieves good performance through (i) state space reduction, which allows a practical implementation of high-order FSVQ, and (ii) derailment free state transitions. Experimental results show that our approach outperforms other known FSVQ schemes in terms of performance, system complexity, and processing speed, especially at low bit rate image coding.

A new approach to the design of a finite-state vector quantizer (FSVQ) is proposed. FSVQ essentially exploits correlations between adjacent blocks for efficient coding. Previous FSVQ design schemes had ad-hoc features in defining states and resource allocation using equal number of bits for state codebooks regardless of their probabilities of occurrence in a given source. We propose a FSVQ design approach which improves the compression performance by merging states and using variable state-codebook sizes. Another undesirable feature of the FSVQ is a derailment problem which degrades the performance in many practical applications. We propose a structurally constrained state-codebook design approach that eliminates the derailment problem. The performance of the proposed algorithm outperforms previously known FSVQ methods. Further development of the algorithm utilizing mean-removed VQ is described which gives less block artifact even though PSNR is a little bit inferior.

The authors present a new pruned tree structured vector quantization (TSVQ) algorithm, called incremental tree growing (ITG), which incrementally grows and quantizes the context tree locally on a level by level basis, thus drastically reducing both the memory requirements and the computational complexity. After the incremental tree growing is completed, terminal branches are globally vector quantized again, which is possible due to significant reduction of the number of initial branches. Using a technique similar in spirit to the mean removed VQ (MRVQ) of Baker and Gray (1983), significant reduction in the number of probability tables is achieved. In one of their simulations, they reduced the number of probability tables from 262 K(=2/sup 18/) to 108 by using the ITG algorithm, and from 108 to 10 using the modified MRVQ at the conditional entropy increase of only 1.26%. In summary, the proposed ITG algorithm combined with a modified MRVQ provides an efficient framework for the design of context-trees with reduced memory and computational requirements.>

High order statistical modeling is a promising technique for data compression. Previously we introduced an algorithm for the design of efficient high order statistical models of digital images. The system consisted in mapping the context set to a tree-structured vector quantizer, the context-tree, and using vector quantization techniques to reduce the size of the tree and, thus, simplify the model. While the models obtained through this off-line design procedure are very efficient they can only be used to code images in the same class as those represented in the training set. In this paper, we show that high order models can be obtained adaptively by constructing the context-tree with a wider range of image classes and allowing the coder to adaptively collect the statistics as the input is processed. Since the structure of the model (context-tree) is kept fixed and only the conditional distributions are allowed to vary the overall scheme is semi-adaptive. The compression efficiency is better than the conventional DPCM+entropy scheme by 8% to 36% for the images used for the simulations.>