Fast nearest neighbor search of entropy-constrained vector quantization.

Entropy-constrained vector quantization (ECVQ) offers substantially improved image quality over vector quantization (VQ) at the cost of additional encoding complexity. We extend results in the literature for fast nearest neighbor search of VQ to ECVQ. We use a new, easily computed distance that successfully eliminates most codewords from consideration.

Progressive transmission of images using MAP detection over channels with memory.

We propose a new maximum a posteriori (MAP) detector, without the need for explicit channel coding, to lessen the impact of communication channel errors on compressed image sources. The MAP detector exploits the spatial correlation in the compressed bitstream as well as the temporal memory in the channel to correct channel errors. We first present a technique for computing the residual redundancy inherent in a compressed grayscale image (compressed using VQ). The performance of the proposed MAP detector is compared to that of a memoryless MAP detector. We also investigate the dependence of the performance on memory characteristics of the Gilbert-Elliott channel as well as average channel error rate. Finally, we study the robustness of the proposed MAP detector's performance to estimation errors.

Optimal bit allocation and best-basis selection for wavelet packets and TSVQ.

To use wavelet packets for lossy data compression, the following issues must be addressed: quantization of the wavelet subbands, allocation of bits to each subband, and best-basis selection. We present an algorithm for wavelet packets that systematically identifies all bit allocations/best-basis selections on the lower convex hull of the rate-distortion curve. We demonstrate the algorithm on tree-structured vector quantizers used to code image subbands from the wavelet packet decomposition.

Embedded multilevel error diffusion.

We present an algorithm for image browsing systems that embeds the output of binary Floyd-Steinberg (1975) error diffusion, or a low bit-depth gray-scale or color error diffused image into higher bit-depth gray-scale or color error diffused images. The benefits of this algorithm are that a low bit-depth halftoned image can be directly obtained from a higher bit-depth halftone for printing or progressive transmission simply by masking one or more bits off of the higher bit-depth image. The embedding can be done in any bits of the output, although the most significant or the least significant bits are most convenient. Due to constraints on the palette introduced by embedding, the image quality for the higher bit-depth halftone may be reduced. To preserve the image quality, we present algorithms for color palette organization, or binary index assignment, to be used as a preprocessing step to the embedding algorithm.

Codebook organization to enhance maximum a posteriori detection of progressive transmission of vector quantized images over noisy channels.

We describe a new way to organize a full-search vector quantization codebook so that images encoded with it can be sent progressively and have resilience to channel noise. The codebook organization guarantees that the most significant bits (MSBs) of the codeword index are most important to the overall image quality and are highly correlated. Simulations show that the effective channel error rates of the MSBs can be substantially lowered by implementing a maximum a posteriori (MAP) detector similar to one suggested by Phamdo and Farvardin (see IEEE Trans. Inform. Theory, vol.40, no.1, p.156-193, 1994). The performance of the scheme is close to that of pseudo-gray coding at lower bit error rates and outperforms it at higher error rates. No extra bits are used for channel error correction.

A predictive classified vector quantizer and its subjective quality evaluation for X-ray CT images.

The authors have developed a new classified vector quantizer (CVQ) using decomposition and prediction which does not need to store or transmit any side information. To obtain better quality in the compressed images, human visual perception characteristics are applied to the classification and bit allocation. This CVQ has been subjectively evaluated for a sequence of X-ray CT images and compared to a DCT coding method. Nine X-ray CT head images from three patients are compressed at 10:1 and 15:1 compression ratios and are evaluated by 13 radiologists. The evaluation data are analyzed statistically with analysis of variance and Tukey's multiple comparison. Even though there are large variations in judging image quality among readers, the proposed algorithm has shown significantly better quality than the DCT at a statistical, significance level of 0.05. Only an interframe CVQ can reproduce the quality of the originals at 10:1 compression at the same significance level. While the CVQ can reproduce compressed images that are not statistically different from the originals in quality, the effect on diagnostic accuracy remains to be investigated.

Evaluation of a combined two- and three-dimensional compression method using human visual characteristics to yield high-quality 10:1 compression of cranial computed tomography scans.

RATIONALE AND OBJECTIVES: The compression of cranial computed tomography scans was improved by using independent intra- and interframe compression techniques. METHODS: For intraframe compression, an image was decomposed into four subimages, one subimage was chosen as a reference subimage, and three of the subimages were predicted from the reference subimage. The prediction error was encoded with a classified vector quantizer (CVQ) based on human visual perception characteristics. Interframe redundancy is exploited by a displacement estimated interslice (DEI) algorithm that encodes the differences between reference subimages from adjacent slices. This combined DEI/CVQ method was subjectively evaluated by 13 radiologists under a blinded protocol, and was compared to the CVQ method alone, the DEI method alone, the original images, and to a standard intraframe discrete cosine transform (DCT) compression method. RESULTS: Only the combined DEI/CVQ method at 10:1 compression was not scored significantly different from the original images. At 15:1 compression, the DEI/CVQ method was scored significantly better than the 10:1 DCT and any other 15:1 compression methods. CONCLUSIONS: Compressed image quality is enhanced by exploiting inter- and intraframe redundancy, and by modeling some characteristics of human visual perception. The DEI/CVQ method is well-suited for progressive transmission, and thus, holds potential in teleradiology as well as picture archiving and communications systems.

Thoracic CT images: effect of lossy image compression on diagnostic accuracy.

PURPOSE: To evaluate the effects of lossy image (noninvertible) compression on diagnostic accuracy of thoracic computed tomographic images. MATERIALS AND METHODS: Sixty images from patients with mediastinal adenopathy and pulmonary nodules were compressed to six different levels with tree-structured vector quantization. Three radiologists then used the original and compressed images for diagnosis. Unlike many previous receiver operating characteristic-based studies that used confidence rankings and binary detection tasks, this study examined the sensitivity and predictive value positive scores from nonbinary detection tasks. RESULTS: At the 5% significance level, there was no statistically significant difference in diagnostic accuracy of image assessment at compression rates of up to 9:1. CONCLUSION: The techniques presented for evaluation of image quality do not depend on the specific compression algorithm and provide a useful approach to evaluation of the benefits of any lossy image processing technique.

Index assignment for progressive transmission of full-search vector quantization.

The authors study codeword index assignment to allow for progressive image transmission of fixed rate full-search vector quantization (VQ). They develop three new methods of assigning indices to a vector quantization codebook and formulate these assignments as labels of nodes of a full-search progressive transmission tree. The tree is used to design intermediate codewords for the decoder so that full-search VQ has a successive approximation character. The binary representation for the path through the tree represents the progressive transmission code. The methods of designing the tree that they apply are the generalized Lloyd algorithm, minimum cost perfect matching from optimization theory, and a method of principal component partitioning. Their empirical results show that the final method gives intermediate signal-to-noise ratios (SNRs) that are close to those obtained with tree-structured vector quantization, yet they have higher final SNRs.

Error-diffused image compression using a binary-to-gray-scale decoder and predictive pruned tree-structured vector quantization.

The authors consider data compression of binary error diffused images. The original contribution is using nonlinear filters to decode error-diffused images to compress them in the gray-scale domain; this gives better image quality than directly compressing the binary images. Their method is of low computational complexity and can work with any halftoning algorithm.

Statistical distributions of DCT coefficients and their application to an interframe compression algorithm for 3-D medical images.

Displacement estimated interframe (DEI) coding, a coding scheme for 3-D medical image data sets such as X-ray computed tomography (CT) or magnetic resonance (MR) images, is presented. To take advantage of the correlation between contiguous slices, a displacement-compensated difference image based on the previous image is encoded. The best fitting distribution functions for the discrete cosine transform (DCT) coefficients obtained from displacement compensated difference images are determined and used in allocating bits and optimizing quantizers for the coefficients. The DEI scheme is compared with 2-D block discrete cosine transform (DCT) as well as a full-frame DCT using the bit allocation technique of S. Lo and H.K. Huang (1985). For X-ray CT head images, the present bit allocation and quantizer design, using an appropriate distribution model, resulted in a 13-dB improvement in the SNR compared to the full-frame DCT using the bit allocation technique. For an image set with 5-mm slice thickness, the DEI method gave about 5% improvement in the compression ratio on average and less blockiness at the same distortion. The performance gain increases to about 10% when the slice thickness decreases to 3 mm.

Tree-structured vector quantization of CT chest scans: image quality and diagnostic accuracy.

The authors apply a lossy compression algorithm to medical images, and quantify the quality of the images by the diagnostic performance of radiologists, as well as by traditional signal-to-noise ratios and subjective ratings. The authors' study is unlike previous studies of the effects of lossy compression in that they consider nonbinary detection tasks, simulate actual diagnostic practice instead of using paired tests or confidence rankings, use statistical methods that are more appropriate for nonbinary clinical data than are the popular receiver operating characteristic curves, and use low-complexity predictive tree-structured vector quantization for compression rather than DCT-based transform codes combined with entropy coding. The authors' diagnostic tasks are the identification of nodules (tumors) in the lungs and lymphadenopathy in the mediastinum from computerized tomography (CT) chest scans. Radiologists read both uncompressed and lossy compressed versions of images. For the image modality, compression algorithm, and diagnostic tasks the authors consider, the original 12 bit per pixel (bpp) CT image can be compressed to between 1 bpp and 2 bpp with no significant changes in diagnostic accuracy. The techniques presented here for evaluating image quality do not depend on the specific compression algorithm and are useful new methods for evaluating the benefits of any lossy image processing technique.

Variable rate vector quantization for medical image compression.

Three techniques for variable-rate vector quantizer design are applied to medical images. The first two are extensions of an algorithm for optimal pruning in tree-structured classification and regression due to Breiman et al. The code design algorithms find subtrees of a given tree-structured vector quantizer (TSVQ), each one optimal in that it has the lowest average distortion of all subtrees of the TSVQ with the same or lesser average rate. Since the resulting subtrees have variable depth, natural variable-rate coders result. The third technique is a joint optimization of a vector quantizer and a noiseless variable-rate code. This technique is relatively complex but it has the potential to yield the highest performance of all three techniques.