This paper discusses with efficient side-information context description for context-based adaptive entropy coders. The design of context-based adaptive entropy coders is nontrivial due to the balance that must be struck between the benefits associated with using a large number of conditioning classes, or contexts, and the penalties resulting from data dilution. Recently an iterative algorithm is proposed, that begins with a large number of conditioning classes and then uses a clustering procedure to group them into a desired size. This method performs very well in contrast to the more usual approach of defining contexts in an ad-hoc manner. In this paper, two techniques were efficiently describing the context book one is coarse context quantization, and another one is classification map. The side information is decreased by 90%-95% when the classification map strategy is applied. It can be further compressed if the coarse context quantization method is used. It is believed that these techniques have great potential for improving the performance of data compression algorithms.

Region of interest coding is an important feature in JPEG2000 and it is accomplished by pre-emphasizing the wavelet coefficients participating in the reconstruction of the ROI. In the general scaling-based method, a number of extra bits appear in the right side of the least significant bit of the ROI samples after the shifting process. These bits need be coded at the time of bit-plane coding, but they are discarded by the decoder. The usual procedure is for the encoder to set these "don't care" bits to zero. In this paper, we propose a method that exploits the state of the JPEG2000 entropy coder to set the values of these bits in a more intelligent way. The method can be implemented with only a small increase in coder complexity and improvements of up to 6% in the number of bits required to represent a code-block has been observed. The bit-stream remains JPEG2000 compliant.

A pilot-assisted turbo coding system is proposed in which pilot bits are periodically inserted into the bit stream to be encoded by turbo encoder. In our rate 1/2 example, both the systematic bit for the pilot and a corresponding parity are punctured to keep the code rate unchanged On the decoding side, two schemes are proposed to improve the performance; the first uses the pilots to detect possible errors and scales the extrinsic information accordingly, while the second modifies the path metric. These two ideas can be combined to further improve the performance. The application of this scheme to soft output Viterbi algorithm (SOVA) is studied. In comparison with the standard SOVA decoder, our simulation results show that the use of pilot symbols to detect errors and scale the extrinsic information can result in a coding gain of 0.38 dB at an SNR of 2.5 dB. By itself, the modified metric contributes to an improvement of 0.12 dB at this same SNR, while a combination of the above two schemes achieves a 0.45 dB improvement.

This work derives a family of dilation matrices for the body-centered cubic (BCC) lattice, which is optimal in the sense of spectral sphere packing. While satisfying the necessary conditions for dilation, these matrices are all cube roots of an integer scalar matrix. This property offers theoretical advantages for construction of wavelet functions in addition to the practical advantages when iterating through a perfect reconstruction filter bank based on BCC downsampling. Lastly, we factor the BCC matrix into two matrices that allow us to cascade two two-channel perfect reconstruction filter banks in order to construct a four-channel perfect reconstruction filter bank based on BCC downsampling.

We propose an optimal joint source-channel maximum a posteriori probability decoder for variable-length encoded sources transmitted over a wireless channel, modeled as an additive-Markov channel. The state space introduced by the authors in a previous paper is used to take care of the unique challenges posed by variable-length codes. Simulations demonstrate, that this decoder performs substantially better than the standard Huffman decoder for a simple test source and is robust to inaccuracies in channel statistics estimates. The proposed algorithm also compares favorably to a standard forward error correction-based system.

Context-based adaptive entropy coding is an essential feature of modern image compression algorithms; however, the design of these coders is non-trivial due to the balance that must be struck between the benefits associated with using a large number of conditioning classes, or contexts, and the penalties resulting from data dilution. The problem is especially severe when coding small sub-images where the amount of data available is small. In this paper, we propose an iterative algorithm that begins with a large number of conditioning classes and then uses a clustering procedure to reduce this number to a desired value. This method is in contrast to the more usual approach of defining contexts in an ad-hoc manner. Experiments are conducted on synthetic data sources having varying amounts of memory, as well as on the sub-images resulting from a wavelet decomposition of an image. The results show that our approach to context selection is effective and that the algorithm automatically learns the structure of the data. This technique could be applied to improve the performance of both image and video coders.

This paper proposes an optimal maximum a posteriori probability decoder for variable-length encoded sources over binary symmetric channels (BSC) that uses a novel state-space to deal with the problem of variable-length source codes in the decoder. This sequential, finite-delay, joint source-channel decoder delivers substantial improvements over the conventional decoder and also over a system that uses a standard forward error correcting code operating at the same over all bit rates. This decoder is also robust to inaccuracies in the estimation of channel statistics.

This paper describes the compression of grayscale medical ultrasound images using a recent compression technique, i.e., space-frequency segmentation (SFS). This method finds the rate-distortion optimal representation of an image from a large set of possible space-frequency partitions and quantizer combinations and is especially effective when the images to code are statistically inhomogeneous, which is the case for medical ultrasound images. We implemented a compression application based on this method and tested the algorithm on representative ultrasound images. The result is an effective technique that performs better than a leading wavelet-transform coding algorithm, i.e., set partitioning in hierarchical trees (SPIHT), using standard objective distortion measures. To determine the subjective qualitative performance, an expert viewer study was run by presenting ultrasound radiologists with images compressed using both SFS and SPIHT. The results confirmed the objective performance rankings. Finally, the performance sensitivity of the space-frequency codec is shown with respect to several parameters, and the characteristic space-frequency partitions found for ultrasound images are discussed.

Joint space-frequency segmentation is a relatively new image compression technique that finds the rate-distortion optimal representation of an image from a large set of possible space-frequency partitions and quantizer combinations. As such, the method is especially effective when the images to code are statistically inhomogeneous, which is certainly the case in the ultrasound modality. Unfortunately, however, the original paper on space-frequency segmentation neglected to use an actual entropy coder, but instead relied upon the zeroth-order entropy to guide the algorithm. In this work, we fill this gap by comparing actual entropy-coding strategies and their effect on both the resulting segmentations as well as the rate-distortion performance. We then apply the resulting "complete" algorithm to representative ultrasound images. The result is an effective technique that performs significantly better than SPIHT using both objective and subjective measures.

This paper proposes an optimal joint source-channel, maximum a posteriori, decoder for entropy coded Markov sources transmitted over noisy channels. We introduce the concept of incomplete and complete states to deal with the problem of variable length source codes in the decoder. The proposed decoder is sequential, thereby making the expected delay finite. When compared to the traditional decoder, the proposed decoder shows a maximum improvement, of about 4 dB in a modified signal to noise ratio and an improvement of 21.95% in percentage of bits that are received in an out of synchronization condition, for a simple test source.

Summary form only given. Entropy codes (e.g. Huffman codes) are often used to improve the rate-distortion performance of codecs for most sources. However, transmitting entropy coded sources over noisy channels can cause the encoder and decoder to lose synchronization, because the codes tend to be of variable length. Designing optimal decoders to deal with this problem is nontrivial since it is no longer optimal to process the data in fixed-length blocks, as is done with fixed-length codes. This paper deals with the design of an optimal decoder (MAPD), in the maximum a posteriori (MAP) sense, for an entropy coded memoryless source transmitted over a binary symmetric channel (BSC) with channel cross over probability /spl epsiv/. The MAP problem is cast in a dynamic programming framework and a Viterbi like implementation of the decoder is presented. At each stage the MAPD performs two operations: the metric-update and the merger-check operations. A stream of 40,000 samples of a zero mean, unit variance, Gaussian source, quantized with uniform, N-level quantizers was Huffman encoded and the resulting bit stream was transmitted over a BSC. Experiments were performed for values of N ranging from 128 to 1024 and for four different random error patterns, obtained using a random number generator. The results demonstrate that the MAPD performs better than the HD on an average, whenever /spl epsiv/ is comparable to the source probabilities. A maximum reduction of 2.94% in the bits that are out of synchronization, was achieved for the 1024 level quantizer.

This paper examines the problem of compressing multispectral images using the wavelet transform and stack-run entropy coding. Our goal is to explore various ways of coding the wavelet coefficients in order to see which techniques can best exploit the correlation between the multispectral bands to produce an efficient coding algorithm. The results of our study indicate that applying the KLT to each subband followed by lattice VQ on Z/sup n/ and subsequent independent entropy coding of each of the lattice dimensions is an effective and fairly simple coding technique. We also demonstrate the importance of proper bit-allocation or, equivalently, the correct choice of the lattice scale parameter for each subband.

Motion estimation in video is a very important tool for such applications as interpolation, motion compensation, and segmentation. However, in interlaced video, it is often desirable to perform interpolation prior to the motion estimation. In this correspondence, a novel technique is presented that, rather than minimizing the interpolation error in each of the frames used for motion estimation, seeks to make these errors equal. The new method is shown to perform deinterlacing better than several other approaches also based on Bayesian estimation.

Traditionally, Markov models have not been successfully used for compression of signal data other than binary image data. Due to the fact that exact substring matches in non-binary signal data are rare, using full resolution conditioning information generally tends to make Markov models learn slowly, yielding poor compression. However, as is shown in this paper, such models can be successfully applied to non-binary signal data compression by continually adjusting the resolution and order to minimize the code-length of the past samples in the hope that this choice will best compress the future samples as well, a technique inspired by Rissanen's minimum description length (MDL) principle. Performance of this method meets or exceeds current approaches.

Several methods exist for adaptation to non-stationary statistics in histogram modelling. Among the techniques that perform local adaptation by decaying histogram counts, we show that fixed decay rate schemes are sub-optimal. We use an order-0 model and an arithmetic coder to demonstrate that improved performance can be obtained by using a variable decay rate scheme that uses the derivative of the per-symbol codelength sequence to control the rate of decay.

It is known that the combination of uniform quantization and entropy coding performs optimally at asymptotically high rates. However, due to synchronization problems resulting from the use of variable length codes, this is true only in the absence of transmission errors. Thus, the performance over noisy channels can be improved by using either fixed length codes and Lloyd-Max quantization or by adding end-of-line symbols. Computer simulations are used to compare the above two schemes for a variety of error rates, line lengths and amounts of error protection. It is found that the "uniform" scheme gives the best SNR for a given rate in the case of memoryless Gaussian and Laplacian sources, provided that its parameters are chosen sensibly. It is expected that these results will generalize to other sources.>

This paper examines the potential uses of interband leakage in image coders based on subband decomposition. The approach taken is to use the lowpass subband to predict the signal behavior in the other bands. This information is then used to both inform the coder/decoder as to likely locations for significant energy in the highpass bands, and to form a difference signal that can be coded at a lower rate. These methods give significant gains for some image/filter combinations, but in general it seems that analysis filters producing low correlation should be used if possible.>

An efficient image source coding technique gives good compression performance at low computational complexity. This research introduces an efficient coding technique, based on pyramid coding, that involves transforming an image into an equivalent lower entropy form prior to lossless coding. The proposed method is also a multiresolution technique that facilitates progressive image transmission.

The application of simulated annealing to the design of a codebook for a vector quantizer (VQ) that is used to code images are studied. The traditional method for VQ codebook design is to use the generalized Lloyd algorithm (GLA), an iterative optimization procedure where an initial codebook is continually refined so that each iteration reduces the distortion involved in coding a given training set. However, this algorithm easily gets trapped in local minima of the distortion, resulting in a suboptimal codebook. Simulated annealing is a procedure that uses randomness in a search algorithm and tends to skirt relatively poor local minima in favor of better ones. The mean-squared-error (MSE) is used as the distortion measure during the design, and coded images are evaluated both subjectively and in terms of the peak-signal-to-noise ratio.>

Current algorithms for the efficient coding of images generally employ one of two techniques: Vector Quantization or Transform Coding. Both of these methods are based on block coding, and the traditional algorithms require the partitioning of the original image into a number of, usually square, regions of uniform size. This paper explores techniques where the size of these regions, or blocks, is varied according to the local detail of the image. By isolating regions of differing detail, using a quad-tree based segmentation algorithm to control the size of the blocks, the low detail areas can be encoded at substantially lower rates than is otherwise possible. Satisfactory quality coding results are achieved at rates between 0.35 and 0.4 bpp; the actual rate depends on the image being encoded.