The high coding efficiency enabled by the H.264 standard comes with substantially greater algorithmic complexity as compared to that of existing standards. This additional complexity complicates very much the implementation and optimization tasks. However, efficient implementations on different platforms exist that achieve real-time constraints in several video applications. One such good example is UB Video's implementation of an H.264 Baseline encoder on the Texas Instruments' TMS320DM642 (DM642) Digital Signal Processor, which can achieve good speed-quality trade-offs in video conferencing applications. In this work, we analyze and optimize UB Video's implementation of its H. 264 Baseline encoder on the DM642. As a result, we have been able to improve memory transfer efficiency and reduce execution time, reducing the total number of encoder cycles by 18% without any loss in video quality.

The increasing availability of object-based video content requires new technologies for automatically extracting and matching of the low level features of arbitrarily shaped video. This paper proposes methods for shape retrieval of arbitrarily shaped video objects. Our methods take into account not only the still shape features but also the shape deformations that may occur in an object's lifespan. We compute the shape similarity of video objects by comparing the similarity of their representative temporal instances. We also describe motion of a video object via describing the deformations in an object's shape. Experimental results show that our proposed methods offer very good retrieval performance and match closely with the human ranking.

Three dimensional reconstruction of a rigid object from monocular video sequences is addressed. Initially object pose is estimated in each image by locating similar (unknown) textures assuming flat depth maps for all input images. Shape-from-silhouette Szeliski (1993) is then applied to make a 3-D model (volume), which is used for a new round of pose estimation, this time by a model-based method giving better estimates. Before repeating this process by building a new volume, pose estimates are adjusted to reduce error by maximizing a quality measure for shape-from-silhouette volume reconstruction. The volume feedback is terminated when pose estimates do not change much as compared to those produced by previous iteration. The final output is a pose index (the last set of pose estimates) and a volume. Good performance of the system is shown by several experiments. No model is assumed for the object. Feature points are neither detected nor tracked: no problematic feature matching or correspondence. The high-level pose index generated for input images can be used for content-based retrieval. Our method can be also applied to 3-D object tracking in video.

We study and analyze the computational complexity of a software-based H.264/AVC (advanced video codec) baseline profile decoder. Our analysis is based on determining the number of basic computational operations required by a decoder to perform the key decoding subfunctions. The frequency of use of each of the required decoding subfunctions is empirically derived using bitstreams generated from two different encoders for a variety of content, resolutions and bit rates. Using the measured frequencies, estimates of the decoder time complexity for various hardware platforms can be determined. A detailed example is provided to assist in deriving time complexity estimates. We compare the resulting estimates to numbers measured for an optimized decoder on the Pentium 3 hardware platform. We then use those numbers to evaluate the dependence of the time complexity of each of the major decoder subfunctions on encoder characteristics, content, resolution and bit rate. Finally, we compare an H.264/AVC-compliant baseline decoder to a decoder that is compliant with the H.263 standard, which is currently dominant in interactive video applications. Both "C" only decoder implementations were compared on a Pentium 3 hardware platform. Our results indicate that an H.264/AVC baseline decoder is approximately 2.5 times more time complex than an H.263 baseline decoder.

A unified approach to the coder control of video coding standards such as MPEG-2, H.263, MPEG-4, and the draft video coding standard H.264/AVC (advanced video coding) is presented. The performance of the various standards is compared by means of PSNR and subjective testing results. The results indicate that H.264/AVC compliant encoders typically achieve essentially the same reproduction quality as encoders that are compliant with the previous standards while typically requiring 60% or less of the bit rate.

A unified approach to the coder control of video coding standards such as MPEG-2, H.263, MPEG-4, and the draft video coding standard JVT/H.26L/AVC is presented. Using this unified framework, the performance of the various standards is compared by means of PSNR and subjective testing results. The results indicate that JVT/H.26L/AVC compliant encoding can typically achieve essentially the same objective PSNR reproduction quality as encoders that are compliant with previous standards while requiring as little as 60% or less of the bit rate of the next best standard, particularly for higher-latency applications and particularly for more difficult source material. Subjective testing shows that the bit savings produced by this draft standard are even larger than the PSNR results indicate.

The two-dimensional (2-D) discrete cosine transform (DCT) and the subsequent quantization of the transform coefficients are two computationally demanding steps of any DCT-based video encoder. In this paper, we propose an efficient joint implementation of these two steps, where the precision in computing the DCT can be exchanged for a reduction in the computational complexity. First, the quantization is embedded in the DCT, thus eliminating the need to explicitly quantize the transform coefficients. A multiplierless integer implementation of the quantized DCT (QDCT) is then proposed that performs shift and add operations instead of full multiplications. A sequence of multiplierless QDCT algorithms is obtained with increasing precision and number of computations. Finally, further savings in computations are obtained by terminating the DCT computations whenever intermediate results indicate that the transform and quantization steps will likely result in a block of zero values. The proposed algorithms are applied to, and results are presented for, high-quality MPEG-2 and low bit rate H.263 video encoding.

The generalized S transform (GST), a family of reversible integer-to-integer transforms inspired by the S transform, is proposed. This family of transforms is then studied in some detail. For example, the relationship between the GST and lifting scheme is discussed, and the effects of choosing different GST parameters are examined. Some examples of specific transforms in the GST family are also given.

The increasing availability of object-based video content requires new technologies for automatically extracting and matching of the low level features of arbitrarily shaped video. in this paper, we propose methods for the efficient retrieval of video object shapes. Our methods take into account not only the still shape features but also the shape deformations that may occur in the lifespan of video objects. We define a new shape similarity measure that is based on the shape similarity of the representative temporal instances of video objects. We also propose shape deformation features that are based on the variances of the still shape features. The proposed visual features can be derived directly from the MPEG-4 compressed domain or computed from the shape masks of the video objects in the spatial domain. Our experiments show that our proposed methods offer very good retrieval results.

We address the problem of robust video transmission over unreliable networks. Our approach employs the principle of multiple-descriptions, through pre- and post-processing of the video data, without modification to the source or channel codecs. We employ oversampling to add redundancy to the original video data followed by a decomposition of the oversampled video frames into "equal" sub-images which can be coded and transmitted over separate channels. Simulations using two descriptions show that this approach maintains excellent reconstructed video quality when only one description is received.

Motion features play an important role in video retrieval. We propose three new motion features that describe the local motion of arbitrarily shaped video objects. The proposed descriptors are based on the angular and circular area variances of the video object, the variances of the angular radial transform coefficients of the object's area, and the variances of the Fourier coefficients of the object's boundary. These descriptors can be derived directly from the MPEG-4 compressed domain or can be computed using the binary shape masks of the video objects in the spatial domain. Our experiments show that the ranking obtained by querying with our proposed features closely matches the human ranking.

We present an effective framework for increasing the error-resilience of low bit-rate video communications over an error-prone packet-switched network. Our framework is based on the principle of layered coding with transport prioritization. We introduce a rate-distortion optimized mode-selection algorithm for our prioritized layered framework. This algorithm is based on a joint source/channel-coding approach and trades off source coding efficiency for increased bitstream error-resilience to optimize the video coding mode selection within and across layers. The algorithm considers the channel conditions, as well as the error recovery and concealment capabilities, of the channel codec and source decoder, respectively. Important framework parameters including the packetization scheme, decoder error concealment method, and channel codec error-protection strength are considered. The effects of mismatch between the parameters employed by the encoder and the actual channel conditions are considered. Results are presented for a wide range of packet loss rates in order to illustrate the benefits of the proposed framework.

We propose a method for high-order image subsampling using feedforward artificial neural networks (FANNs). In our method, the high-order subsampling process is decomposed into a sequence of first-order subsampling stages. The first stage employs a tridiagonally symmetrical FANN, which is obtained by applying the design algorithm introduced by Dumitras and Kossentini (see IEEE Trans. Signal Processing, vol.48, p.1446-55, 2000). The second stage employs a small fully connected FANN. The algorithm used to train both FANNs employs information about local edges (extracted using pattern matching) to perform effective subsampling of both high detail and smooth image areas. We show that our multistage first-order subsampling method achieves excellent speed-performance tradeoffs, and it consistently outperforms traditional lowpass filtering and subsampling methods both subjectively and objectively.

The rapidly expanding field of multimedia communications has fueled significant research and development work in the area of real-time video encoding. Dedicated hardware solutions have reached maturity and cost-efficient hardware encoders are being developed by several manufacturers. However, software solutions based on a general purpose processor or a programmable digital signal processor (DSP) have significant merits. Toward this objective, we have developed a flexible framework for video encoding that yields very good computation-performance tradeoffs. The proposed framework consists of a set of optimized core components: motion estimation (ME), the discrete cosine transform (DCT), quantization, and mode selection. Each of the components can be configured to achieve a desired computation-performance tradeoff. The components can be assembled to obtain encoders with varying degrees of computational complexity. Computation control has been implemented within the proposed framework to allow the resulting algorithms to adapt to the available computational resources. The proposed framework was applied to MPEG-2 and H.263 encoding using Intel's Pentium/MMX desktop processor. Excellent speed-performance tradeoffs were obtained.

Summarization of video content is necessary in order to reduce the large amount of data involved in video retrieval. In a frame-based digital video retrieval framework, this is achieved by representing the content of a video sequence using key frames. Similarly, in an object-based framework, such as the one suggested by the MPEG-4 standard, video object planes can be used for summarization of video object content. We propose a method for key video object plane selection using the shape information in the MPEG-4 compressed domain. Two popular shape distance measures, the Hamming and Hausdorff distance measures, are employed to measure the similarities between the approximated shapes of the video objects. The corresponding algorithms, with different implementation complexity and computation tradeoffs, select key video object planes that represent efficiently the salient content of the video objects.

In this paper, we propose a flexible framework for DCT-based video encoding that yields very good computation performance tradeoffs. Each of the encoding components features a set of parameters that can be used to control its computational complexity and performance. A sequence of optimum parameter sets have been designed to obtain encoders with varying degrees of computational complexity. A computation control mechanism is proposed within the encoding framework to allow the encoding algorithm to adapt to the available computational resources. This will allow the encoder to run in real time on machines with different computing power levels, while also achieving the best possible reproduction quality. The proposed framework was applied to MPEG-2 and H.263 encoding. Our experimental results show that excellent speed-performance tradeoffs as well as accurate computation control can be obtained using the proposed method.

We propose an error concealment method for shape information in the MPEG-4 coded video sequences. A maximum a posteriori estimator, which employs an adaptive Markov random field, is used to restore the missing shape information. The proposed concealment method successfully reconstructs the missing shape data, with good computation-performance tradeoffs.

A software-based implementation of the image codec specified in the emerging JPEG-2000 standard is discussed. The run-time complexity and coding performance of this implementation are also analyzed.

We propose a method for high-order image subsampling using feedforward artificial neural networks (FANNs). Our method employs a tridiagonally symmetrical FANN, which is obtained by applying the design algorithm proposed by Dumitraa and Kossentini (see IEEE Transactions on Signal Processing, vol.48, no.5, p.1446-55, 2000), and a small, fully connected FANN. We show that our subsampling method provides excellent speed-performance tradeoffs as compared to those of the method based exclusively on fully connected FANNs.

We propose an algorithm to partition MPEG-4 video objects into temporal segments with uniform activity levels. These segments can be used for efficient summarization of video objects and/or retrieval of video objects by their motion. The proposed algorithm is based on the shape and texture coding modes of inter coded video object planes. Because the employed filtering techniques are simple and full decoding of the MPEG-4 bitstream is not required, the algorithm is computationally efficient.

We present a rate-distortion optimal joint source/channel coding framework for efficient and robust low bit rate video communications in packet networks. The proposed algorithm combines layered coding with transport prioritization in a novel operational rate-distortion optimization framework that trades off source coding performance for channel coding protection. The system is demonstrated to achieve significant improvement in reconstructed video quality for a range of packet loss rates.

We propose an efficient, similarity-based error concealment method for block-based coded images. In a hierarchical matching procedure, the image is first searched at a lower resolution to find the best match of a layer of pixels around a missing block. Then, the search is performed on the full resolution image. A fast search algorithm which follows a diamond-shaped search area is employed in both resolutions. The missing block is replaced with the block connected to the layer that yields the best match. Moreover, the proposed matching criterion takes into account the geometrical structure extracted from the surrounding pixels of a lost block. The fast search matching method needs significantly less number of computations required by a full search matching method and achieves almost the same reconstruction quality.

We introduce a mixed fixed-length coding (FLC) and variable-length coding (VLC) technique to improve the error resilience of the upcoming JPEG2000 image coding standard. Our proposed method operates on quantized subband coefficients, and produces a bit-stream with both FLC and VLC codewords. Higher error resilience is achieved by eliminating the error propagation within FLC sections, which in general comprise the majority of the coded bit-stream. A highly efficient coding technique has been developed to generate fixed-length codewords for groups of quantization indices, and significantly reduce the amount of information to be entropy coded. However, the noiseless compression performance is not compromised. Every effect has been made to minimize the impact of our modifications to the baseline coding structure and the bit-stream syntax defined in the standard, so the proposed technique can be easily integrated into any JPEG2000 compliant system.

Introduces a novel approach for rigid object pose estimation. The system rotates a reference frame of the object of interest until it reaches a view at which the rotated reference view and the unknown-pose view seem to be "similar". A number of pose similarity measures were tested for different types of objects undergoing various amounts of rotation from the reference pose. We demonstrate that the sum of the texture difference and the mask difference can be used as an effective pose similarity measure, which is capable of a unique determination of the correct pose. A number of optimization methods (e.g. genetic algorithms) were used as feedback from pose comparison to reference frame rotation. The results of comparing these methods in a number of experiments is reported in this paper as well.

We describe an effective method for increasing error resilience of video transmission over bit error prone networks. Rate-distortion optimized mode selection and synchronization marker insertion algorithms are introduced. The resulting video communication system takes into account the channel condition and the error concealment method used by the decoder, to optimize video coding mode selection and placement of synchronization markers in the compressed bit stream. The effects of mismatch between the parameters used by the encoder and the parameters associated with the actual channel condition and the decoder error concealment method are evaluated. Results for the binary symmetric channel and wideband code division multiple access mobile network models are presented in order to illustrate the advantages of the proposed method.

In this paper, we propose a two-stage error-concealment method for block-based compressed video which was transmitted in an error-prone environment. In the first stage, we obtain initial estimates of the missing blocks. If the motion vectors associated with the missing blocks are available, motion compensation is used to provide good estimates. Otherwise, a novel algorithm which preserves image continuity is used to estimate the blocks. In the second stage, a maximum a posteriori (MAP) estimator, which employs an adaptive Markov random field (MRF) as the image a priori model is used to improve the video reconstruction quality. The adaptive model enables the estimation to incorporate information embedded not only in the immediate neighborhood pixels but also in a wider neighborhood into the reconstruction procedure without increasing the order of the MRF model. The proposed concealment method achieves very good computation-performance tradeoffs, as demonstrated via experimental results.

This paper presents efficient coding and mapping algorithms that lead to a significant speed improvement in low bit rate H.263/H263+ video encoding while maintaining high video-reproduction quality. First, by exploiting the statistical properties of low resolution and slowly varying video sequences, we reduce significantly the computation times of the most computationally intensive components of video coding, particularly the discrete cosine transform, the inverse discrete cosine transform, quantization, and motion estimation. We also map some of the single instruction multiple data (SIMD)-oriented functions onto Intel's MMX architecture. The developed algorithms are implemented using our public-domain H.263/H.263+ encoder/decoder software. Using the above algorithms, our H.263/H.263+ baseline video-encoder implementation can encode more than 15 fps in QCIF resolution on a Pentium MMX 200-MHz computer.

In the context of image coding, a number of reversible integer-to-integer wavelet transforms are compared on the basis of their lossy compression performance, lossless compression performance, and computational complexity. Of the transforms considered, several were found to perform particularly well, with the best choice for a given application depending on the relative importance of the preceding criteria. Reversible integer-to-integer versions of numerous transforms are also compared to their conventional (i.e., nonreversible real-to-real) counterparts for lossy compression. At low bit rates, reversible integer-to-integer and conventional versions of transforms were found to often yield results of comparable quality. Factors affecting the compression performance of reversible integer-to-integer wavelet transforms are also presented, supported by both experimental data and theoretical arguments.

We introduce a fast and high performance image subsampling method using feedforward artificial neural networks (FANNs). Our method employs a pattern matching technique to extract local edge information within the image, in order to select the FANN desired output values during the supervised training stage. Subjective and objective evaluations of experimental results using still images and video frames show that our method, while less computationally intensive, outperforms the standard lowpass filtering and subsampling method.

In this paper, a two-stage method for the reconstruction of missing data in the transmission of baseline JPEG coded images in error prone environments is proposed. In the first stage, we estimate the values of the missing DC coefficients. As effects of errors in estimating the missing DC values will appear as a number of stripes across the image, a technique for removing such stripes is also developed. In the second stage, the data of missing blocks is reconstructed by exploiting the correlation between adjacent blocks. Simulation results intricate that our reconstruction method performs very well. The two key contributions of our method are that it does not assume nondifferential encoding of the DC coefficients, and that it performs well in the reconstruction of diagonal edges.

Object-based video representation, such as the one suggested by the MPEG-4 standard, offers a framework that is better suited for object-based video indexing and retrieval. In such a framework, the concept of a "key frame" is replaced by that of a "key video object plane". In this paper, we propose a method for key video object plane selection using the shape information in the MPEG-4 compressed domain. The shape of the video object (VO) is approximated using the shape coding modes of I, P, and B video object planes (VOPs) without decoding the shape information in the MPEG-4 bit stream. Two popular shape distance measures, the Hamming and Hausdorff distance measures, are modified to measure the similarities between the approximated shapes of the video objects. Although they feature different computational and implementation complexity tradeoffs, the corresponding algorithms achieve essentially the same performance levels in selecting key video object planes that represent efficiently the salient content of the video objects.

We propose a new method for error concealment of shape information in MPEG-4 video bit streams that are transmitted over error prone channels. The proposed method employs a MAP estimator with a Markov random field (MRF) as the image a priori model. The MRF is designed for binary shape information and its parameters are adapted based on the information of neighboring blocks. Our experimental results show that the proposed concealment method restores missing shape blocks with high accuracy. Compared to the median filtering method, our method restores 20% more missing shape data, with a much greater subjective improvement. The proposed algorithm requires a relatively small number of integer multiplications and additions and simple logic operations, making it suitable for real-time implementations.

[Summary form only given]. There has been a growing interest in reversible integer-to-integer wavelet transforms for image coding applications. In this paper, a number of such transforms are compared on the basis of their objective and subjective lossy compression performance, lossless compression performance, and computational complexity. Of the transforms considered, several were found to perform particularly well, with the best choice for a given application depending on the relative importance of lossless compression performance, lossy compression performance, and computational complexity. Reversible integer-to-integer versions of numerous transforms are also compared to their conventional (i.e., nonreversible real-valued) counterparts for lossy compression. In many cases, the reversible integer-to-integer and conventional versions of a transform were found to yield results with comparable image quality.

Summary form only given. We present our work on rate-distortion (RD) optimized spatial scalability for MC-DCT based video coding. Extending our work on RD optimized coding from the single layered to the multi-layered framework, we incorporate the additional inter-layer coding dependencies present in a multilayered framework into the set of permissible coding parameters. We employ the Lagrangian rate-distortion functional as it provides an elegant framework for determining the optimal choice of motion vectors, coding modes, and quantized coefficient levels by weighting a distortion term against a resulting rate term. We obtain a simple relationship between the Lagrangian parameter /spl lambda/, that controls rate-distortion tradeoffs, and the reference and enhancement layer quantization parameters QP, to allow the RD optimized framework to work easily in conjunction with rate control techniques that control the average bit rate by adjusting the quantization parameters. We then incorporate these relationships into our coder and generate two-layer bit streams with both the non-RD optimized coder and the RD optimized coder. We also generate RD optimized single-layer bit streams with the same resolution as the second layer of the two-layer bit streams. For the two-layer bit streams, we obtain a 0.6 to 1.4 dB improvement in PSNR by using RD optimization in both the base and enhancement layers. Compared to the single-layer bit stream, RD optimization in both the base and enhancement layers causes the decrease in PSNR to be reduced from 1.1 to 1.7 dB, to 0.3 to 0.5 dB.

Summary form only given. This paper presents a motion estimation technique for the coding of video sequences that is based on long-term temporal prediction. The motion vector of a moving object is tracked from one frame to another using a projection method. The traced motion vector is used as a starting point for the motion estimation search algorithm. The motion estimation algorithm used is based on an optimum fast block matching algorithm. Combinations of both spatial and temporal prediction are also used to obtain a more accurate estimate of the motion vector of the current macroblock. An inaccurately predicted motion vector can have a significant negative impact on the motion estimation algorithm. It can force the search algorithm to be trapped in a local minimum, or to spend unnecessary computations to find the optimum motion vector. The accuracy of the predicted motion vector is estimated using a reliability measure that allows the motion search algorithm to decide whether to use temporal motion vector predictor, spatial motion vector predictor, or both. As a reliability measure we used the mean squared error between the traced motion vectors in the current frame and in the previous frame. The reliability measure increases if the motion vector belongs to a moving object with constant speed. If the reliability measure is smaller than a certain threshold, then we abandon the temporal prediction and use spatial prediction. If both prediction methods fail, we abandon the fast motion search and perform full-search motion estimation in the low-resolution images. The experimental results show that long-term prediction reduces the number of computations performed by the motion search algorithm by up to 20%, while obtaining essentially the same quality.

Summary form only given. The Joint Bi-Level Expert Group (JBIG), an international study group affiliated with the ISO/IEC and ITU-T, has recently completed a committee draft of the JBIG2 standard for lossy and lossless bi-level image compression. We study design considerations for a purely lossless encoder. First, we outline the JBIG2 bitstream, focusing on the options and parameters available to an encoder. Then, we present numerous lossless encoder design strategies, including lossy to lossless coding approaches. For each strategy, we determine the compression performance, and the execution times for both encoding and decoding. The strategy that achieved the highest compression performance in our experiment used a double dictionary approach, with a residue cleanup. In this strategy, small and unique symbols were coded as a generic region residue. Only repeated symbols or those used as a basis for soft matches were added to a dictionary, with the remaining symbols embedded as refinements in the symbol region segment. The second dictionary was encoded as a refinement-aggregate dictionary, where dictionary symbols were encoded as refinements of symbols from the first dictionary, or previous entries in the second dictionary. With all other bitstream parameters optimized, this strategy can easily achieve an additional 30% compression over simpler symbol dictionary approaches. Next, we continue the experiment with an evaluation of each of the bitstream options and configuration parameters, and their impact on complexity and compression. We also demonstrate the consequences of choosing incorrect parameters. We conclude with a summary of our compression results, and general recommendations for encoder designers.

A typical MPEG-2 video encoder requires that DCT and quantization be performed in most cases. In this paper we show how to combine these two steps, reducing substantially the number of computations. The new nonlinear transform is called the quantized discrete cosine transform, or QDCT. We also introduce a new method to trade-off the computational complexity and the precision of the QDCT. Although the QDCT is independent of the input data, better trade-offs can be obtained by making it data dependent, which is appropriate in multimedia applications such as MPEG-2 video coding. The results presented in this paper can also be extended to other linear transforms and/or other coding methods.

Loss of coded data during its transmission can affect a decoded video sequence to a large extent, making concealment of errors caused by data loss a serious issue. Previous work in spatial error concealment exploiting MRF models used a single pixel wide region around the erroneous area to achieve a reconstruction based on an optimality measure. This practically restricts the amount of available information that is used in a concealment procedure to a small region around the missing area. Incorporating more pixels usually means a higher order model and this is expensive as the complexity grows exponentially with the order of the MRF model. Using previously proposed approaches, the damaged area is reconstructed fairly well in very low frequency portions of the image. However, the reconstruction process yields blurry results with a significant loss of details in high frequency, or edge portions of the image. In our proposed approach, a MRF is used as the image a priori model. More available information is incorporated in the reconstruction procedure not by increasing the order of the model but instead by adaptively adjusting the model parameters. Adaptation is done based on the image characteristics determined in a large region around the damaged area. Thus, the reconstruction procedure can make use of information embedded in not only immediate neighborhood pixels but also in a wider neighborhood without a dramatic increase in computational complexity. The proposed method outperforms the previous methods in the reconstruction of missing edges.

In the context of image coding, a number of reversible integer-to-integer wavelet transforms are compared on the basis of their lossy compression performance, lossless compression performance, and computational complexity. Of the transforms considered, several were found to perform particularly well, with the best choice for a given application depending on the relative importance of the preceding criteria. Reversible integer-to-integer versions of numerous transforms are also compared to their conventional counterparts for lossy compression. At low bit rates, reversible integer-to-integer and conventional versions of transforms were found to often yield reconstructed images with comparable quality, both subjectively and objectively.

In this paper, we describe an effective method for increasing error resilience of video transmission over bit error prone networks. Rate-distortion optimized mode selection and synchronization marker insertion algorithms are introduced. The resulting video communication system takes into account the channel condition and the error concealment method used by the decoder, to optimize video coding mode selection and placement of synchronization markers in the compressed bit stream. Results for the binary symmetric channel and wideband code division multiple access mobile network models are presented in order to illustrate the advantages of the proposed method.

It is well-known that flexibility and error resilience are significantly improved by employing a scalable bit stream. The major drawback of multi-layered representations within a motion compensated (MC) discrete cosine transform (DCT) based framework is the increase in bit rate as compared to a single-layered representation having the same frequency, spatial and temporal resolution as in the highest layer of the multi-layered representation. Using rate-distortion (RD) optimization techniques, we can improve the compression efficiency of MC-DCT based SNR and spatially scalable video coding framework. We first show how RD optimization techniques can be applied independently for each layer. We then extend the framework to consider coding decisions jointly across layers.

This paper presents a motion estimation technique for the coding of moving video sequences that is based on spatial and temporal prediction. The motion vector of a moving object is tracked using spatial and temporal prediction and used as a starting point for the motion estimation search algorithm. The predicted motion vector is selected from several candidate motion vectors according to the block matching criterion. Experimental results show that spatio-temporal prediction reduces the number of computations performed by the motion search algorithm by 30% for MPEG-2 encoding and by 40% for H.263 encoding.

In this paper, we present a spatio-temporal segmentation method for content-based video retrieval. Our method is effective in the presence of partial occlusion or when new areas become exposed. In addition, periodic spatial segmentation is not performed. Rather, it is invoked as needed depending on whether or not new regions have been detected. A discussion of how this method can be used for content-based retrieval is also provided. Finally, experimental results that demonstrate the performance of the proposed spatio-temporal segmentation method are presented.

The emerging JBIG2 standard allows compliant encoders to achieve very high compression rates on bi-level images, especially when images are properly segmented into regions of line-art, halftones and text. We propose a fast method that is very effective at separating text from non-text regions, even when the regions are nonrectangular or have skew. Our method can also detect regions of reverse-coloured text. In most cases, our method increases the compression performance of the encoder. More importantly, our method can improve encoding speeds considerably, often by an order of magnitude.

The JBIG2 standard supports lossless and lossy coding models for text, halftone, and generic regions in bi-level images. For the JBIG2 lossy halftone compression mode, halftones are descreened before encoding. Previous JBIG2 descreening implementations produce high-quality images for clustered dot halftones at high compression rates but significantly degrade the image quality for stochastic halftones, even at much lower rates. In this paper, we develop (1) a flexible, computationally efficient, JBIG2-compliant method for compressing stochastic halftones that reduces noise, artifacts, and blurring; (2) quality measures for linear and nonlinear distortion in compressed halftones; and (3) rate-distortion tradeoffs for the encoder parameters.

We present a new wavelet/subband framework that allows the efficient and effective quantization/coding of subband coefficients in both noiseless and noisy channel environments. Two different models, one based on a zero-tree structure and another based on a quadtree and context-based modeling structure, are introduced for coding the locations of significant subband coefficients. Then, several multistage residual lattice vector quantizers are proposed for the quantization of such coefficients. The proposed framework features relatively simple modeling and quantization/coding structures that produce a bit stream containing two distinct bit sequences, which can then be protected differently according to their importance and channel noise sensitivity levels. The resulting wavelet/subband image coding algorithms provide good tradeoffs between compression performance and resilience to channel errors, In fact, experimental results indicate that for both noiseless and noisy channels, the resulting coders outperform most of the source-channel coders reported in the literature. More importantly, our coders are substantially more robust than all previously reported source-channel coders with respect to varying channel error conditions. This is a desired feature in low-bandwidth wireless applications.

We present a semi-fixed-length motion vector coding method for H.263-based low bit rate video compression. The method exploits structural constraints within the motion field. The motion vectors are encoded using semi-fixed-length codes, yielding essentially the same levels of rate-distortion performance and subjective quality achieved by H.263's Huffman-based variable length codes in a noiseless environment. However, such codes provide substantially higher error resilience in a noisy environment.

We present an efficient computation constrained block-based motion vector estimation algorithm for low bit rate video coding that yields good tradeoffs between motion estimation distortion and number of computations. A reliable predictor determines the search origin, localizing the search process. An efficient search pattern exploits structural constraints within the motion field. A flexible cost measure used to terminate the search allows simultaneous control of the motion estimation distortion and the computational cost. Experimental results demonstrate the viability of the proposed algorithm in low bit rate video coding applications. The resulting low bit rate video encoder yields essentially the same levels of rate-distortion performance and subjective quality achieved by the UBC H.263+ video coding reference software. However, the proposed motion estimation algorithm provides substantially higher encoding speed as well as graceful computational degradation capabilities.

Among the many different modes of operations allowed in the current JPEG standard, the sequential and progressive modes are the most widely used. While the sequential JPEG mode yields essentially the same level of compression performance for most encoder implementations, the performance of progressive JPEG depends highly upon the designed encoder structure. This is due to the flexibility the standard leaves open in designing progressive JPEG encoders. In this work, a rate-distortion (RD) optimized JPEG compliant progressive encoder is presented that produces a sequence of scans, ordered in terms of decreasing importance. Our encoder outperforms an optimized sequential JPEG encoder in terms of compression efficiency, substantially at low and high bit rates. Moreover, unlike existing JPEG compliant encoders, our encoder can achieve precise rate/distortion control. Substantially better compression performance and precise rate control, provided by our progressive JPEG compliant encoding algorithm, are two highly desired features currently sought for the emerging JPEG-2000 standard.

This paper introduces a subband video coding algorithm for operation over a continuum of rates from very low to very high. The key elements of the system are statistical rate-distortion-constrained motion estimation and compensation, multistage residual quantization, high order statistical modeling, and arithmetic coding. The method is unique in that it provides an improved mechanism for dynamic spatial and temporal coding. Motion vectors are determined in a nontraditional way, using a rate-distortion cost criterion. This results in a smoother and more consistent motion field, relative to that produced by conventional block matching algorithms. Control over the system computational complexity and performance may be exercised easily.

The emerging ITU-T H.263+ low bit-rate video coding standard is version 2 of the draft international standard ITU-T H.263. In this paper, we discuss this emerging video coding standard and present compression performance results based on our public domain implementation of H.263+.

In this paper, we present a video chrominance subsampling method using feedforward artificial neural networks (FANNs). Experimental results show that our method outperforms spatial subsampling obtained via low pass filtering and decimation both objectively and subjectively. Other advantages of our algorithm are computational efficiency and low memory requirements. Moreover, no pre- or post-processing is required by our method.

Among the different modes of operations allowed in the current JPEG standard, the sequential and progressive modes are the most widely used. While the sequential JPEG mode yields essentially the same level of compression performance for most encoder implementations, the performance of progressive JPEG depends highly upon the designed encoder structure. This is due to the flexibility the standard leaves open in designing progressive JPEG encoders. In this paper, a rate-distortion optimized JPEG compliant progressive encoder is presented that produces a sequence of bit scans, ordered in terms of decreasing importance. Our encoder outperforms a baseline sequential JPEG encoder in terms of compression, significantly at medium bit rates, and substantially at low and high bit rates. Moreover, unlike baseline JPEG encoders, ours can achieve precise rate/distortion control. Good rate-distortion performance at low bit rates and precise rate control, provided by our JPEG compliant progressive encoder, are two highly desired features currently sought for JPEG-2000.

The performance of several decorrelating transforms is evaluated in the JPEG-2000 baseline system. The transforms considered are based on uniform parallel 2-channel and 8-channel filter banks and discrete cosine transform (DCT) building blocks. Through the analysis of lossy compression results, a system employing a combination of 8- channel and 2-channel filter banks is found to perform best overall. Also, the performance of several reversible transforms is evaluated in the same coding framework. Based on lossy and lossless compression results, a reversible version of the Cohen-Daubechies-Feauveau (2,2) wavelet transform was found to be most effective.

An algorithm for high-quality coding of 48 kHz sampled audio signals is presented. The algorithm employs a perceptual transform and a variable-depth multistage quantizer. The resulting audio reproduction quality is better than that of the Motion Pictures Expert Group (MPEG) layer I coder and roughly equivalent to that of the MPEG layer II coder.

We discuss the ITU-T H.263+ (or H.263 Version 2) low-bit-rate video coding standard. We first describe, briefly, the H.263 standard including its optional modes. We then address the 12 new negotiable modes of H.263+. Next, we present experimental results for these modes, based on our public-domain implementation (http:ilspmg.ece.ubc.ca). Tradeoffs among compression performance, complexity, and memory requirements for the H.263+ optional modes are discussed. Finally, results for mode combinations are presented.

The Joint Bi-Level Image Experts Group (JBIG), an international study group affiliated with ISO/IEC and ITU-T, is in the process of drafting a new standard for lossy and lossless compression of bilevel images. The new standard, informally referred to as JBIG2, will support model-based coding for text and halftones to permit compression ratios up to three times those of existing standards for lossless compression. JBIG2 will also permit lossy preprocessing without specifying how it is to be done, In this case, compression ratios up to eight times those of existing standards may be obtained with imperceptible loss of quality. It is expected that JBIG2 will become an international standard by 2000.

Version 2 of ITU Recommendation H.263, better known as H.263+, includes a number of new mechanisms to improve coding efficiency and support various types of networks more efficiently. This paper provides an overview of the error resilience optional modes of H.263+ and describes the use of such modes in various multimedia network scenarios.

A clustering algorithm based on the pairwise nearest-neighbor (PNN) algorithm developed by Equitz (1989), is introduced for the design of entropy-constrained residual vector quantizers. The algorithm designs residual vector quantization codebooks by merging the pair of stage clusters that minimizes the increase in overall distortion subject to a given decrease in entropy. Image coding experiments show that the clustering design algorithm typically results in more than a 200:1 reduction in design time relative to the standard iterative entropy-constrained residual vector quantization algorithm while introducing only small additional distortion. Multipath searching over the sequence of merges is also investigated and shown experimentally to slightly improve rate-distortion performance. The proposed algorithm can be used alone or can he followed by the iterative algorithm to improve the reproduction quality at the same bit rate.

Prediction and search techniques are introduced for efficient rate-distortion optimized motion estimation in a very low bit rate video coding framework. For prediction, three types of predictors are considered: mean, weighted mean, and median. Prediction allows us to constrain the motion vector search to a small diamond-shaped area whose center is the predicted motion vector. The size of the search area is further constrained by employing a probabilistic model. We evaluate two models, both of which permit the contraction or the expansion of the search area as a function of the local statistics of the motion flow. The proposed techniques are analyzed in the context of a very low bit rate DCT-based video coding framework, where a rate-distortion criterion is used for motion estimation as well as for 8/spl times/8 block coding mode selection. A particular resulting very low bit rate video coder is shown experimentally to outperform the H.263 TMN5 simulation model in terms of encoding speed and compression performance, simultaneously.

The MPEG-2 bitstream syntax offers a great variety of coding mode options for encoding a macroblock. We present an MPEG-2 compliant interlaced video encoder that employs an efficient macroblock coding mode selection method. The macroblock coding mode is selected based on a rate-distortion criterion. However, a computational analysis as well as predictive and statistical modeling techniques are introduced that lead to substantially better computation-performance trade-offs. The proposed MPEG-2 video encoder is shown experimentally to be better than the MPEG-2 TM5 encoder in both compression performance and computation requirements, simultaneously.

We present a generalized embedded zerotree wavelet image coding algorithm that achieves relatively good tradeoffs between compression performance and channel error resilience and robustness. The proposed algorithm features a relatively simple coding structure, yet it also provides a high level of flexibility. The fundamental approach is to explicitly classify the encoder's output bit sequence into subsequences, which are then protected differently according to their importance and robustness. Our combined source/channel coding algorithm can outperform most existing channel resilient coding algorithms for specific target bit error rates. However, its main advantage is that it provides an efficient solution to the common channel mismatching problem by producing a bit stream that is very robust with respect to varying channel error conditions.

Predictive rate-distortion (RD) optimized motion estimation techniques are studied and developed for very low bit-rate video coding. Four types of predictors are studied: mean, weighted mean, median, and statistical mean. The weighted mean is obtained using conventional linear prediction techniques. The statistical mean is obtained using a finite-state machine modeling method based on dynamic vector quantization. By employing prediction, the motion vector search can then be constrained to a small area. The effective search area is reduced further by varying its size based on the local statistics of the motion field, through using a Lagrangian as the search matching measure and imposing probabilistic models during the search process. The proposed motion estimation techniques are analyzed within a simple DCT-based video coding framework, where an RD criterion is used for alternating among three coding modes for each 8/spl times/8 block: motion only, motion-compensated prediction and DCT, and intra-DCT. Experimental results indicate that our techniques yield very good computation-performance tradeoffs. When such techniques are applied to an RD optimized H.263 framework at very low bit rates, the resulting H.263 compliant video coder is shown to outperform the H.263 TMN5 coder in terms of compression performance and computations simultaneously.

We introduce a computation-constrained predictive motion estimation algorithm for fast Motion Picture Expert Group-2 (MPEG-2) encoding. Motion estimation is restricted to a relatively small search area whose center is a two-dimensional (2D) median predicted motion vector. The number of computations is further reduced by incorporating explicitly a computational constraint during the estimation process. Experimental results show that the median prediction as well as the dynamic nature of the implementation lead to a dramatic increase in motion estimation speed for only a small loss in compression performance. A unique feature of our algorithm is that the reconstruction quality of the resulting MPEG-2 coder is proportional to the computer's processing power, providing much needed flexibility in many MPEG-2 software applications.

We present a new embedded zerotree wavelet image coding algorithm that is based on the algorithms developed by Shapiro (see IEEE Trans. Signal Processing, Spec. Issue Wavelets Signal Processing, vol.41, no.12, p.3445-62, 1993) and Said et al. (see IEEE Trans. Circuits Syst. Video Technol., vol.6, no.6, p.243-50, 1996). Our algorithm features a relatively simple coding structure and provides a better framework for balancing between high compression performance and robustness to channel errors. The fundamental approach is to explicitly classify the encoder's output bit sequence into subsequences, which are then protected differently according to their importance and robustness. Experimental results indicate that, for noisy channels, the proposed algorithm is slightly more resilient to channel errors than more complex and sophisticated source-channel coding algorithms. More important is that our algorithm is substantially more robust with respect to varying channel error conditions. This provides much needed reliability in low-bandwidth wireless applications.

Abstract only given. A significant amount of current research on vector quantization (VQ) implementations addresses increasing the speed of image encoding. This is typically accomplished by imposing structures, exploiting properties of the distance measure, or developing efficient and fast implementations. This research proposes a parallel implementation of a full-search VQ encoding algorithm using a low memory, fine grain SIMD pixel processor (SIMPil) being developed at Georgia Tech. This implementation fully exposes the available parallelism of the encoding process and exploits the processing and I/O capabilities of the processor, resulting in a system that can perform real-time image and video compression. The proposed implementation encodes a large region of the original image at once, replacing each constituent input block with its corresponding VQ codeword index. Preliminary simulation results indicate that the proposed implementation is capable of sustain real-time frame rates. In the simulation, 92058 clock cycles are required to encode a single 64/spl times/64 region. The image of Lena (256/spl times/256) requires 16 passes to be completely encoded, for a total of about 1472089 clock cycles. With a 50 MHz processor, a 256/spl times/256 image frame will be encoded in 29.4 ms, supporting a frame rate of >30 frames/sec. Three VQ implementations are compared on different hardware platforms. A prototype SIMPil implementation is being fabricated by MOSIS in 0.8 /spl mu/m CMOS.

Digital coding of high-fidelity audio signals has become a key technology in the development of cost-effective multimedia systems. Most audio coding algorithms rely on (i) removal of statistical redundancies in the signal and (ii) exploitation of masking properties of the human auditory system to hide distortions in the coded signal. Transform and subband coders provide a convenient framework for time-frequency domain signal analysis and coding based on these two principles. We present a subband coding algorithm for high-quality coding of 48 kHz sampled audio signals that is based on perceptual transformation, variable-depth multistage uniform quantization, and complexity-constrained higher-order entropy coding. The construction does not require any training and avoids completely the need to send side information.

We present an efficient motion estimation algorithm where motion vectors are selected based on a rate-distortion criterion. The algorithm minimizes the rate subject to a constraint on overall distortion by optimizing jointly the motion vector coder and the residual coder. As the joint optimization is generally very demanding, we propose methods where the rate-distortion performance of the residual coder is approximated by parametric functions. This results in a substantial reduction in computational complexity while sacrificing only a small loss in performance. Experimental results indicate that the proposed algorithm can improve the performance of H.261- and H.263-based video coders significantly while still generating H.261/H.263 decodable bit streams, respectively.

Distortion resulting from ringing and/or aliasing is the most objectionable subjective distortion normally appearing in low bit rate subband/wavelet coded images. This paper presents a method for significantly reducing both ringing and aliasing, while still achieving low bit rates and requiring low encoding/decoding complexity. The method employs a new signal dependent two-band filter bank system that employs short FIR filters, yet results in a relatively small loss of aliasing cancellation in its synthesis section. The signal dependent part of the filter bank is the statistical linear prediction used to decorrelate the subband signals. Experimental results indicate that this approach can achieve very good subjective quality at low bit rates.

We introduce a low-complexity, high-performance DCT-based video coding algorithm that is designed for very low bit rates. The algorithm employs a fast statistical and rate-distortion-optimized motion estimation method with integer-pel accuracy. The searching is constrained to a small diamond-shaped area whose center is the statistical mean, which is obtained using a finite-state machine modeling method based on dynamic state vector quantization. The same modeling method is also employed for coding the motion vectors. A simple rate-distortion criterion is used for alternating between three modes of operation for each 8/spl times/8 block: motion-only coding, motion-compensated predictive coding, and intra coding. Experimental results indicate that the proposed algorithm can outperform current H.263-based video coders significantly at very low bit rates. But, more important is that our algorithm's rate, distortion, and complexity can be easily controlled, a feature desired in many very low bit rate video communication applications due to power and mobility constraints.

This paper introduces an extension of entropy constrained residual vector quantization (VQ) where intervector dependencies are exploited. The method, which we call conditional entropy-constrained residual VQ, employs a high-order entropy conditioning strategy that captures local information in the neighboring vectors. When applied to coding images, the proposed method is shown to achieve better rate-distortion performance than that of entropy-constrained residual vector quantization with less computational complexity and lower memory requirements, moreover, it can be designed to support progressive transmission in a natural way. It is also shown to outperform some of the best predictive and finite-state VQ techniques reported in the literature. This is due partly to the joint optimization between the residual vector quantizer and a high order conditional entropy coder as well as the efficiency of the multistage residual VQ structure and the dynamic nature of the prediction.

The mainstream approach to subband coding has been to partition the input signal into subband signals and to code those signals separately with optimal or near-optimal quantizers and entropy coders. A more effective approach, however, is one where the subband coders are optimized jointly so that the average distortion introduced by the subband quantizers is minimized subject to a constraint on the output rate of the subband encoder. A subband coder with jointly optimized multistage residual quantizers and entropy coders is introduced and applied to image coding. The high performance of the coder is attributed to its ability to exploit statistical dependencies within and across the subbands. The efficiency of the multistage residual quantization structure and the effectiveness of the statistical modeling algorithm result in an attractive balance among the reproduction quality, rate, and complexity.

This paper introduces a new framework for video coding that facilitates operation over a wide range of transmission rates. The new method is a subband coding approach that employs motion compensation, and uses prediction-frame and intra-frame coding within the framework. It is unique in that it allows lossy coding of the motion vectors through its use of multistage residual vector quantization (RVQ). Furthermore, it selects the motion vector with the best rate-distortion tradeoff among a number of possible motion vector candidates, and provides a rate-distortion-based mechanism for alternating between intra-frame and inter-frame coding. The framework provides an easy way to control the system complexity and performance, and inherently supports multiresolution transmission.

This paper describes a very computationally efficient design algorithm for color image coding at low bit rates. The proposed algorithm is based on uniform tree-structured subband decomposition, multistage scalar quantization of the image subbands, and high order entropy coding. The main advantage of the algorithm is that no multiplications are required in both analysis/synthesis and encoding/decoding. This can lead to a simple hardware implementation of the subband coder, while maintaining a high level of performance.

We propose a new framework for the compression of multi-view image sequences. We define three types of frames, and each type is coded with a different strategy. The first type of frame is independently coded and is called I-frame. The second is a B-frame and is coded using a bidirectional disparity estimator and a modified version of the subspace projection technique (SPT). The SPT algorithm compensates the photometric variations between the multi-view frames. The projection block size is chosen to be small so that coding of the residual image is not necessary. On the other hand, to decrease the overhead information both disparity vectors and projection coefficients are coded with a lossy scheme. Finally, the third type of frame is a P-frame and is coded by employing a unidirectional disparity estimator and DC level compensation.

An iterative design algorithm for the joint design of complexity- and entropy-constrained subband quantizers and associated entropy coders is proposed. Unlike conventional subband design algorithms, the proposed algorithm does not require the use of various bit allocation algorithms. Multistage residual quantizers are employed because they provide greater control of the complexity-performance tradeoffs, and also because they allow efficient and effective high-order statistical modeling. The resulting subband coder exploits statistical dependencies within subbands, across subbands, and across stages, mainly through complexity-constrained high-order entropy coding. Experimental results demonstrate that the complexity-rate-distortion performance of the new subband coder is exceptional.

A region-based stereo image coding algorithm is proposed and evaluated. Three types of regions are considered: occlusion, edge and smooth regions. The region in the right image that is occluded due to finite viewing area is estimated using a new approach. This region is independently coded. The non-occluded region is segmented into edge and smooth regions. Each region is composed of fixed size blocks. The disparity for each block in a non-occluded region is estimated using a block-based approach. The estimated disparity field is encoded employing a lossy residual uniform scalar quantizer and an adaptive arithmetic coder based on the segmentation information. The decoded vectors are used for the subspace projection technique, which is a combined disparity and illumination compensation algorithm. The proposed approach is shown to outperform standard block-based and independent coding algorithms.

A rate distortion constrained statistical motion estimation algorithm is presented that leads to improvements in subband video coding. The main advantages of the algorithm is that it requires a relatively small number of computations, produces a much smoother motion field, and employs a more effective measure of performance than the conventional mean absolute difference or mean squared error. The proposed algorithm circumvents problems in the motion compensation loop such as illumination variations, noise, and occlusions, by providing a mechanism for alternating between intraframe and residual coding. Experimental results demonstrate that the corresponding video coder outperforms the H.263 in terms of motion vector search complexity and overall bit rate at the same reproduction quality.

High order entropy coding is a powerful technique for exploiting high order statistical dependencies. However, the exponentially high complexity associated with such a method often discourages its use. In this paper, an entropy-constrained residual vector quantization method is proposed for lossless compression of images. The method consists of first quantizing the input image using a high order entropy-constrained residual vector quantizer and then coding the residual image using a first order entropy coder. The distortion measure used in the entropy-constrained optimization is essentially the first order entropy of the residual image. Experimental results show very competitive performance.

An entropy-constrained residual vector quantization design algorithm is used to design codebooks for image coding. Entropy-constrained residual vector quantization has several important advantages. It can outperform entropy-constrained vector quantization in terms of rate-distortion performance, memory, and computation requirements. It can also be used to design vector quantizers with relatively large vector sizes and high output rates. Experimental results indicate that good image reproduction quality can be achieved at relatively low bit rates. For example, a peak signal-to-noise ratio of 30.09 dB is obtained for the 512x512 LENA image at a bit rate of 0.145 b/p.

Necessary conditions for the optimality of variable-rate residual vector quantizers are derived, and an iterative descent algorithm based on a Lagrangian formulation is introduced for designing residual vector quantizers having minimum average distortion subject to an entropy constraint. Simulation results for entropy-constrained residual vector quantizers are presented for memoryless Gaussian, Laplacian, and uniform sources. A Gauss-Markov source is also considered. The rate-distortion performance is shown to be competitive with that of entropy-constrained vector quantization and entropy-constrained trellis-coded quantization.

The paper reports on some methods to improve the performance of residual vector quantization (RVQ) for low bit rate image coding. The problem addressed is the direct application of RVQ-based techniques to coding images at low bit rates. In the first part of the paper, RVQs are investigated where vectors are allowed to overlap. The RVQ structure allows this to be done in stages and without increasing the bit rate, resulting in a reduction in blocking effects. In the second part of the paper, entropy-constrained RVQ is considered where an additional constraint is placed on the RVQ codebook to improve the reproduction quality given fixed memory constraints.>

An extension of entropy-constrained residual vector quantization is presented where inter-vector dependencies are exploited. The method, which the authors call conditional entropy-constrained residual vector quantization, employs a high-order entropy conditioning strategy that captures local information in the neighboring vectors. The complexity of the proposed design algorithm is relatively low, due mainly to the efficiency of the multistage structure of the residual vector quantizer, but also to the effectiveness of the searching techniques used to locate the best conditioning spatial-stage region of support. Experimental results show that the new method outperforms standard entropy-constrained residual vector quantization while also requiring lower encoding complexity and memory requirements.>

The encoding procedure for multistage residual vector quantizers consists of searching a tree to find the codeword that best matches the input. Many techniques have been proposed for searching such trees, ranging from the slow and faithful to the fast and inaccurate. The present authors introduce a simple method, which they call dynamic M-search, that is both fast and effective for searching the residual vector quantization tree. The new method is applied to image coding, performance results are presented, and advantages are shown over conventional M-search.>

Entropy-constrained residual vector quantization (EC-RVQ) is a relatively new VQ method that was shown to be capable of excellent rate-distortion performance. The paper investigates the incorporation of adaptivity into the EC-RVQ framework for application to image coding. Experimental results show that the dynamic nature of the implementation leads to a noticeable improvement in coding quality as well as improved robustness.>

The approach is based on some advances in the area of variable rate residual vector quantization considered separately, and in conjunction with subband image decomposition. Comparisons illustrate the improvement in performance attributable to this approach relative to the JPEG coding standard.>

A new residual vector quantizer (RVQ) design algorithm is modified so that the multistage structure can be exploited to produce variable-rate RVQ (VR-RVQ) systems. VR-RVQ systems are shown to have very useful properties: (1) the codebook storage requirement and the search complexity are both reduced; (2) the VR-RVQ system is able to exploit the spatial variance of perceptually important information; and (3) the VR-RVQ codebook can operate over a wide range of rates, without having to store several codebooks. Experiments were performed using VR-RVQ systems with vectors of many sizes, and results show significant improvement over fixed-rate RVQ systems with the same block size.>