Set partition coding (SPC) has shown tremendous success in image compression. Despite its popularity, the lack of error resilience remains a significant challenge to the transmission of images in error-prone environments. In this paper, we propose a novel data representation called the progressive significance map (prog-sig-map) for error-resilient SPC. It structures the significance map (sig-map) into two parts: a high-level summation sig-map and a low-level complementary sig-map (comp-sig-map). Such a structured representation of the sig-map allows us to improve its error-resilient property at the price of only a slight sacrifice in compression efficiency. For example, we have found that a fixed-length coding of the comp-sig-map in the prog-sig-map renders 64% of the coded bitstream insensitive to bit errors, compared with 40% with that of the conventional sig-map. Simulation results have shown that the prog-sig-map can achieve highly competitive rate-distortion performance for binary symmetric channels while maintaining low computational complexity. Moreover, we note that prog-sig-map is complementary to existing independent packetization and channel-coding-based error-resilient approaches and readily lends itself to other source coding applications such as distributed video coding.

Efficient image sequence coding exploits both spatial correlation and temporal correlation. SPIHT is a powerful algorithm in exploiting spatial correlations for still image coding. Based on SPIHT, we present a novel approach to exploit temporal correlations for image sequence coding, while maintaining single frame, random access decoding. The so-called Differential-SPIHT takes advantage of inter-frame correlations by reusing the significance testing data of a SPIHT coded frame. From simulation results of videos and volumetric medical images, Differential-SPIHT offers significant reductions in bitrate from conventional two-dimensional (2D) SPIHT for the same reconstruction PSNR, while retaining the desirables features of rate scalability and computational simplicity.

This work investigates a central problem in steganography, that is: How much data can safely be hidden without being detected? To answer this question, a formal definition of steganographic capacity is presented. Once this has been defined, a general formula for the capacity is developed. The formula is applicable to a very broad spectrum of channels due to the use of an information-spectrum approach. This approach allows for the analysis of arbitrary steganalyzers as well as nonstationary, nonergodic encoder and attack channels. After the general formula is presented, various simplifications are applied to gain insight into example hiding and detection methodologies. Finally, the context and applications of the work are summarized in a general discussion.

We discuss the use of lattice vector quantizers in conjunction with a quadtree-based sorting algorithm for the compression of multidimensional data sets, as encountered, for example, when dealing with hyperspectral imagery. An extension of the SPECK algorithm is presented that deals with vector samples and is used to encode a group of successive spectral bands extracted from the hyperspectral image original block. We evaluate the importance of codebook choice by showing that a choice of dictionary that better matches the characteristics of the source during the sorting pass has as big an influence in performance as the use of a transform in the spectral direction. Finally, we provide comparison against state-of-the-art encoders, both 2D and 3D ones, showing the proposed encoding method is very competitive, especially at small bit rates.

Enhanced versions of the LVQ-SPECK algorithm are presented that further exemplify the codec’s good performance when dealing with multidimensional data sets. The two different alternatives might, in fact, be considered stepwise improvements over the original codec. First, an extended-range option is implemented, so that the number of spectral bands being simultaneously encoded is now a multiple of (instead of equal to) the codeword dimension. That in itself provides the means for much better rate allocation among the different bands. Then, use of the discrete wavelet transform over the spectral dimension, generating a wavelet packet decomposition of the original dataset is considered, and a substantial increase in coding performance is obtained, provided by the energy compaction characteristics of the transform. We provide results for the two different options of four-dimensional codebooks investigated, namely the shell-1 and shell-2 of the D4lattice, further cementing the idea that the latter is much more adept for use in this setting than the former. Finally we present comparison with other state-of-the-art codecs employed to the same task and show how competitive our proposed extensions are.

This paper proposes a low-complexity wavelet-based method for progressive lossy-to-lossless compression of four dimensional (4-D) medical images. The subband block hierarchal partitioning (SBHP) algorithm is modified and extended to four dimensions, and applied to every code block independently. The resultant algorithm, 4D-SBHP, efficiently encodes 4D image data by the exploitation of the dependencies in all dimensions, while enabling progressive SNR and resolution decompression. The resolution scalable and lossy-to-lossless performances are empirically investigated. The experimental results show that our 4-D scheme achieves better compression performance on 4-D medical images when compared with 3-D volumetric compression schemes

An image coding algorithm, Progressive Resolution Coding (PROGRES), for a high-speed resolution scalable decoding is proposed. The algorithm is designed based on a prediction of the decaying dynamic ranges of wavelet subbands. Most interestingly, because of the syntactic relationship between two coders, the proposed method costs an amount of bits very similar to that used by uncoded (i.e., not entropy coded) SPIHT. The algorithm bypasses bit-plane coding and complicated list processing of SPIHT in order to obtain a considerable speed improvement, giving up quality scalability, but without compromising coding efficiency. Since each tree of coefficients is separately coded, where the root of the tree corresponds to the coefficient in LL subband, the algorithm is easily extensible to random access decoding. The algorithm is designed and implemented for both 2-D and 3-D wavelet subbands. Experiments show that the decoding speeds of the proposed coding model are four times and nine times faster than uncoded 2-D-SPIHT and 3-D-SPIHT, respectively, with almost the same decoded quality. The higher decoding speed gain in a larger image source validates the suitability of the proposed method to very large scale image encoding and decoding. In the Appendix, we explain the syntactic relationship of the proposed PROGRES method to uncoded SPIHT, and demonstrate that, in the lossless case, the bits sent to the codestream for each algorithm are identical, except that they are sent in different order.

In this paper we consider the problem of faded wireless image and video transmission schemes under energy transmission constraints. An example of such a constrained system experiencing Rayleigh fading is code division multiple access (CDMA) where power control is used. We imposed on the average energy transmitted per an image or image sequence. A computationally inexpensive analytic mean square error (MSB) distortion rate (D-R) estimator for progressive wavelet coders which generates an exact distortion rate (D-R) function for 2-D and 3-D SPIHT algorithm is utilized from our previous research. Using the D-R function, the expected mean square error(MSE) at the receiver is minimized by optimally assigning the energy and parity allocation per each transmission block among the packets. A gain of 1.09 dB relative to optimal equal error protection (EEP) is obtained by varying both energy and parity among the transmission blocks. The results can be used to to increase image and video quality in CDMA systems.

We propose a wavelet based coding algorithm supporting random ROI access for hyperspectral images. Hyperspectral image users often are interested in only partial regions of the image datacube. It will reduce the consumption of memory and computational resources if users can identify and reconstruct only the region-of-interest (ROI). Based on the characteristic of the 3D wavelet tree structure, the proposed algorithm groups the wavelet coefficients according to their relationship with ROIs. The new algorithm is also resolution scalable. We demonstrate that comparing to non-ROI retrievable coding algorithm, our algorithm provides higher quality ROI reconstruction even at a low bit budget.

In this paper, we present a two-stage near-lossless compression scheme. It belongs to the class of "lossy plus residual coding" and consists of a wavelet-based lossy layer followed by arithmetic coding of the quantized residual to guarantee a given L(infinity) error bound in the pixel domain. We focus on the selection of the optimum bit rate for the lossy layer to achieve the minimum total bit rate. Unlike other similar lossy plus lossless approaches using a wavelet-based lossy layer, the proposed method does not require iteration of decoding and inverse discrete wavelet transform in succession to locate the optimum bit rate. We propose a simple method to estimate the optimal bit rate, with a theoretical justification based on the critical rate argument from the rate-distortion theory and the independence of the residual error.

Summary form only given. A very fast, low complexity algorithm for resolution-scalable and random access decoding is presented. The algorithm avoids the multiple passes of bit-plane coding for speed improvement. The decrease in dynamic range of wavelet coefficient magnitudes is efficiently coded. The hierarchical dynamic range coding naturally enables resolution-scalable representation of a wavelet transformed image. The method predicts the dynamic range of energy in each subset based on the dynamic range of energy of a parent set. Speed improvement over SPIHT is up to two times in encoding, and up to four times in decoding. The loss of quality is very small. Our method outperforms the LTW in Oliver et al. (2003), by up to two times in encoding and up to seven times in decoding.

Here we propose scalable three-dimensional set partitioned embedded block (3D-SPECK) - an embedded, block-based, wavelet transform coding algorithm of low complexity for hyperspectral image compression. Scalable 3D-SPECK supports both SNR and resolution progressive coding. After wavelet transform, 3D-SPECK treats each subband as a coding block. To generate SNR scalable bitstream, the stream is organized so that the same indexed bit planes are put together across coding blocks and subbands, so that the higher bit planes precede the lower ones. To generate resolution scalable bitstreams, each subband is encoded separately to generate a sub-bitstream. Rate is allocated amongst the sub-bitstreams produced for each block. To decode the image sequence to a particular level at a given rate, we need to encode each subband at a higher rate so that the algorithm can truncate the sub-bitstream to the assigned rate. Resolution scalable 3D-SPECK is efficient for the application of an image server. Results show that scalable 3D-SPECK provides excellent performance on hyperspectral image compression.

A degree-k zero tree model is presented, in order to quantify the coding power of zerotrees in wavelet-based image coding. Based on the model, the coding behaviors of modern zerotree based image coders are clearly explained. Also, we explain why the well-known SPIHT algorithm can code a wider range of zerotrees than EZW. Experimental results support our idea that higher degree zerotree coder will have more coding power.

A very fast, low complexity algorithm for resolution scalable and random access decoding is presented. The algorithm avoids the multiple passes of bit-plane coding for speed improvement. The decrease in dynamic ranges of wavelet coefficients magnitudes is efficiently coded. The hierarchical dynamic range coding naturally enables a resolution scalable representation of a wavelet transformed image.

In this paper, we elaborate on denoising schemes based on lossy compression. First, we provide an alternative interpretation of the so-called Occam filter and relate it with the complexity-regularized denoising schemes in the literature. Next, we discuss about the 'critical distortion' of a noisy source and argue that optimal denoising is achieved at the corresponding critical encoding rate rather than at the encoding rates suggested by other compression-based denoisers. Finally, we discuss the so-called 'indirect rate distortion problem'. We focus particularly on the high bit-rate encoding of noisy sources and show lossless compression of a denoised source is often very wasteful of bits, and suggest a simple way of determining an appropriate bit-rate for compressing a denoised source economically while retaining its initial denoised quality.

Many technical imaging applications, like coding "images" of digital elevation maps, require extracting regions of compressed images in which the pixel values are within a predefined range, and there is a need for coding methods that allow finding these regions efficiently, without having to decompress the whole image. A series of techniques to solve this problem is presented. First, it shows that many of the linear transforms commonly used for image compression can be used for that purpose by proving that the inclusion of nonlinear factors (like minimum or maximum pixel value in a block) does not render the transformation irreversible, and can be made to have very limited impact on the compression efficiency. For example, it shows how the "DC" coefficient of an 8/spl times/8 discrete cosine transform (DCT) can be replaced by the minimum or maximum in the 8/spl times/8 block. This result is valid for a large set of transforms, including the DCT, Walsh-Hadamard, and dyadic Haar transforms, and valid for any type of order-statistic filter output. Next, it shows the results also apply to the quantized transform coefficient cases as well as integer-to-integer transforms. The choices for coding the minimum and maximum values simultaneously, while providing quick access to pixel range and efficient compression were finally studied.

In this paper a novel and computationally inexpensive analytic mean square error (MSE) distortion rate (D-R) estimator for SPIHT which generates a nearly exact distortion rate (D-R) function for the 2D and 3D SPIHT algorithm is presented. The analytical formula is derived from the observations that for any bit-plane coder, the slope of the D-R curve is constant for each level of the bit plane. Furthermore the slope of D-R curve reduces by a factor proportional to the level of the bit plane. An application of the derived results is presented in the area of 2D SPIHT transmission employing a binary symmetric channel (BSC) and Reed Solomon (RS) forward error correction (FEC) codes. Utilizing our D-R estimate, we employ unequal error protection (UEP) and equal error protection (EEP) in order to minimize the end to end mean square error (MSE) distortion of the transform domain. UEP yields a significant performance gain relative to EEP only when the average number of parity bits for a group of packets is constrained. When both the source rate and channel code rate varied under a bit budget constraint, optimal UEP yields only a slight improvement over the optimal EEP. A major contribution of this paper is the simple and extremely accurate analytical D-R model which potentially improves upon pre-existing methodologies and applications that rely on an accurate and computationally inexpensive D-R estimate. Another important contribution is that the optimum EEP, which requires almost no header information and can easily be computed using our method, is only slightly worse than the optimum UEP.

A new coding scheme for lossy to lossless compression of volumetric data using a three-dimensional packet wavelet transform is presented. The need of a unitary transform via the integer lifting scheme and the performance comparison of different integer filter kernels is discussed. A state-of-the-art coder, set partitioning in hierarchical trees (SPIHT), is considered and modified in order to adapt its tree-structure to the 3D packet wavelet structure defined. The algorithm is extensively tested and shows very good performance, both for lossy and lossless coding.

An embedded, block-based, wavelet transform coding algorithm of low complexity is proposed. Three-dimensional set partitioned embedded block (3D-SPECK) efficiently encodes, hyperspectral volumetric image data by exploiting the dependencies in all dimensions. Integer wavelet transform is applied to enable lossy and lossless decompression from the same bit stream. We demonstrate that 3D-SPECK, a wavelet domain algorithm, like other time domain algorithms, can preserve spectral profiles well. Airborne visible infrared imaging spectrometer (AVIRIS) imagery is used to test the proposed algorithm. Results show that 3D-SPECK, in addition to being very flexible, retains all the desirable features of compared state-of-the-art algorithms and is highly competitive to 3D-SPIHT and better than JPEG2000 multi-component in compression efficiency.

In this paper, we investigate a two-stage near-lossless compression scheme. It is in the spirit of "lossy plus residual coding" and consists of a wavelet-based lossy layer followed by an arithmetic coding of the quantized residual to guarantee a given L/sup /spl infin// error bound in the pixel domain. Our focus is on the selection of the optimum bit rate for the lossy layer to achieve the minimum total bit rate. Unlike other similar lossy plus lossless approaches using a wavelet-based lossy layer, the proposed method does not require iteration of decoding and the IWT(Inverse Wavelet Transform) to locate the optimum bit rate. We propose a simple method to estimate the optimal bit rate and provide a theoretical justification for it. It is based on the 'critical rate' argument from the Rate-Distortion theory and 'whiteness' of the residual.

Technical imaging applications such as coding "images" of digital elevation maps, require extracting regions of compressed images with the pixel values within a pre-defined range, without having to decompress the whole image. Previously, we introduced a class of nonlinear transforms which are small modifications of linear transforms to facilitate a search for the regions with pixel values below (above) a given 'threshold', without incurring any penalty in coding efficiency. However, coding efficiency had to be somewhat compromised when searching for regions with a given pixel 'range', especially at high coding rates. In this paper, we propose an improved method of pixel 'range' coding to deal with the aforementioned problem. Results show significant improvements in coding efficiency.

In this paper we consider the problem of robust image coding and packetization for the purpose of communications over slow fading frequency selective channels and channels with a shaped spectrum like those of digital subscribe lines (DSL). Towards this end, a novel and analytically based joint source channel coding (JSCC) algorithm to assign unequal error protection is presented. Under a block budget constraint, the image bitstream is de-multiplexed into two classes with different error responses. The algorithm assigns unequal error protection (UEP) in a way to minimize the expected mean square error (MSE) at the receiver while minimizing the probability of catastrophic failure. In order to minimize the expected mean square error at the receiver, the algorithm assigns unequal protection to the value bit class (VBC) stream. In order to minimizes the probability of catastrophic error which is a characteristic of progressive image coders, the algorithm assigns more protection to the location bit class (LBC) stream than the VBC stream. Besides having the advantage of being analytical and also numerically solvable, the algorithm is based on a new formula developed to estimate the distortion rate (D-R) curve for the VBC portion of SPIHT. The major advantage of our technique is that the worst case instantaneous minimum peak signal to noise ratio (PSNR) does not differ greatly from the averge MSE while this is not the case for the optimal single stream (UEP) system. Although both average PSNR of our method and the optimal single stream UEP are about the same, our scheme does not suffer erratic behavior because we have made the probability of catastrophic error arbitarily small. The coded image is sent via orthogonal frequency division multiplexing (OFDM) which is a known and increasing popular modulation scheme to combat ISI (Inter Symbol Interference) and impulsive noise. Using dual adaptive energy OFDM, we use the minimum energy necessary to send each bit stream at a particular probability of bit error. An added benefit of OFDM over serial transmission schemes is that some degree of progressiveness of SPIHT is preserved by transmitting both the VBC and LBC streams in parallel.

Set Partitioned Embedded bloCK coder (SPECK) has been found to perform comparable to the best-known still grayscale image coders like EZW, SPIHT, JPEG2000 etc. In this paper, we first propose Color-SPECK (CSPECK), a natural extension of SPECK to handle color still images in the YUV 4:2:0 format. Extensions to other YUV formats are also possible. PSNR results indicate that CSPECK is among the best known color coders while the perceptual quality of reconstruction is superior than SPIHT and JPEG2000. We then propose a moving picture based coding system called Motion-SPECK with CSPECK as the core algorithm in an intra-based setting. Specifically, we demonstrate two modes of operation of Motion-SPECK, namely the constant-rate mode where every frame is coded at the same bit-rate and the constant-distortion mode, where we ensure the same quality for each frame. Results on well-known CIF sequences indicate that Motion-SPECK performs comparable to Motion-JPEG2000 while the visual quality of the sequence is in general superior. Both CSPECK and Motion-SPECK automatically inherit all the desirable features of SPECK such as embeddedness, low computational complexity, highly efficient performance, fast decoding and low dynamic memory requirements. The intended applications of Motion-SPECK would be high-end and emerging video applications such as High Quality Digital Video Recording System, Internet Video, Medical Imaging etc.

In critical applications of image compression that are sensitive to information loss, lossless compression techniques are usually employed. The compression ratios obtained from lossless techniques are low. Hence we need different schemes that give quantitative guarantees about the type and amount of distortion incurred, viz. near-lossless compression methods. In this paper, we explore hybrid techniques for near-lossless image compression based on error bound per pixel and apply them to Digital Terrain Elevation Data (DTED). We develop multi-stage quantization methods and other hybrid schemes using SPIHT as an embedded lossy coder. The methods developed are scalable with a control on maximum allowable deviation per pixel in the reconstruction. We compare the results obtained by these methods with JPEG-LS, the standard for lossless and near-lossless compression. Results show that these methods usually perform better than JPEG-LS in terms of compression performance and have additional features useful for progressive transmission.

We investigate and compare the performance of several three-dimensional (3D) embedded wavelet algorithms on lossless 3D image compression. The algorithms are Asymmetric Tree Three-Dimensional Set Partitioning In Hierarchical Trees (AT-3DSPIHT), Three-Dimensional Set Partitioned Embedded bloCK (3D-SPECK), Three-Dimensional Context-Based Embedded Zerotrees of Wavelet coefficients (3D-CB-EZW), and JPEG2000 Part II for multi-component images. Two kinds of images are investigated in our study -- 8-bit CT and MR medical images and 16-bit AVIRIS hyperspectral images. First, the performances by using different size of coding units are compared. It shows that increasing the size of coding unit improves the performance somewhat. Second, the performances by using different integer wavelet transforms are compared for AT-3DSPIHT, 3D-SPECK and 3D-CB-EZW. None of the considered filters always performs the best for all data sets and algorithms. At last, we compare the different lossless compression algorithms by applying integer wavelet transform on the entire image volumes. For 8-bit medical image volumes, AT-3DSPIHT performs the best almost all the time, achieving average of 12% decreases in file size compared with JPEG2000 multi-component, the second performer. For 16-bit hyperspectral images, AT-3DSPIHT always performs the best, yielding average 5.8% and 8.9% decreases in file size compared with 3D-SPECK and JPEG2000 multi-component, respectively. Two 2D compression algorithms, JPEG2000 and UNIX zip, are also included for reference, and all 3D algorithms perform much better than 2D algorithms.

In this letter, a novel and computationally inexpensive analytic mean square error (mse) distortion rate (D-R) estimator for SPIHT which generates a nearly exact D-R function for the two- and three-dimensional SPIHT algorithm is presented. Utilizing our D-R estimate, we employ unequal error protection and equal error protection in order to minimize the end to end MSE distortion of the transform domain. A major contribution of this letter is the simple and extremely accurate analytical D-R model which potentially improves upon pre-existing methodologies and applications that rely on an accurate and computationally inexpensive D-R estimate.

We propose an embedded, block-based, image wavelet transform coding algorithm of low complexity. It uses a recursive set-partitioning procedure to sort subsets of wavelet coefficients by maximum magnitude with respect to thresholds that are integer powers of two. It exploits two fundamental characteristics of an image transform-the well-defined hierarchical structure, and energy clustering in frequency and in space. The two partition strategies allow for versatile and efficient coding of several image transform structures, including dyadic, blocks inside subbands, wavelet packets, and discrete cosine transform (DCT). We describe the use of this coding algorithm in several implementations, including reversible (lossless) coding and its adaptation for color images, and show extensive comparisons with other state-of-the-art coders, such as set partitioning in hierarchical trees (SPIHT) and JPEG2000. We conclude that this algorithm, in addition to being very flexible, retains all the desirable features of these algorithms and is highly competitive to them in compression efficiency.

The error resilient and error concealment 3-D SPIHT (ERC-SPIHT) are introduced, which are encoded with an asymmetric tree structure. Next, error resilient video transmission is presented using the ERC-SPHITC algorithm with rate-compatible punctured convolutional (RCPC) code and Reed-Solomon code.

Summary form only given. Hyperspectral images were generated through the collection of hundreds of narrow and contiguously spaced spectral bands of data producing a highly correlated long sequence of images. An investigation and comparison was made on the performance of several three-dimensional embedded wavelet algorithms for compression of hyperspectral images. These algorithms include 3D-SPIHT, AT-3DSPIHT, 3D-SPECK (three-dimensional set partitioned embedded block), and JPEG2000. 3D-SPIHT is the three-dimensional extension of the state-of-the-art SPIHT (set partitioning in hierarchical trees) image compression algorithm. AT-SPIHT uses the same coding algorithms as 3D-SPIHT, but utilizes a more efficient, asymmetric tree structure. 3D-SPECK is a version of two-dimensional SPECK modified to encode 3D subband blocks. For an image sequence, 3D-DWT was applied to obtain a wavelet coefficient prism. This prism is partitioned into small code blocks with different sizes, and each subband is treated as a code block. A block splitting algorithm is used on the individual code blocks to test their significance. Compression performance was conducted on the mentioned algorithms using several AVIRIS (Airborne Visible Infrared Imaging Spectrometer) image sequences. The rate distortion performances were compared by means of the peak signal-to noise ratio (PSNR). The visual effect is considered a primary concern of hyperspectral imagery so an analysis of every algorithm's visual effect is in order. Through experimentation, AT-3DSPIHT provided high quality reconstructed images even at very low bit rate such as 0.4 bpp. A comparison was also conducted on JPEG200 and other algorithms concerning JPEG2000's multi-component images. The results have shown that AT-3DSPIHT, 3D-SPIHT and 3D-SPECK outperform JPEG2000 by the approximate range of 1 to 2.5 dB PSNR, depending on the image sequence.

In this paper, we investigate region-based embedded wavelet compression methods and introduce region-based extensions of the set partitioning in hierarchical trees (SPIHT) and the set partitioning embedded block (SPECK) coding algorithms applied to the breast region of digital mammograms. We have compared these region-based extensions, called OB-SPIHT and OB-SPECK, against the original SPIHT and the new standard JPEG 2000 on five digital mammograms compressed at rates ranging from 0.1 to 1.0 bits per pixel (bpp). Distortion was evaluated for all images and compression rates by the peak signal-to-noise ratio (PSNR). A comparison applying SPIHT and JPEG 2000 to the same set of images with the background pixels fixed to zero was also carried out. For digital mammography, region-based compression methods represent an improvement in compression efficiency from full-image methods, also providing the possibility of encoding multiple regions of interest.

Hyperspectral images are generated by collecting hundreds of narrow and contiguously spaced spectral bands of data producing a highly correlated long sequence of images. Some application specific data compression techniques may be applied advantageously before we process, store or transmit hyperspectral images. This paper applies asymmetric tree 3DSPIHT (AT-3DSPIHT) for hyperspectral image compression; it also investigates and compares the performance of the AT-3DSPIHT, 3DSPIHT and 3DSPECK on hyperspectral image compression. Results show that the AT-3DSPIHT outperforms the other two by the approximate range of 0.2 to 0.9 dB PSNR. It guarantees over 4 dB PSNR improvement at all rates or rate savings at least a factor of 2.5 over 2D coding of separate spectral bands without axial transformation.

Spatial resolution and contrast sensitivity requirements for some types of medical image techniques, including mammography, delay the implementation of new digital technologies, namely, computer-aided diagnosis, picture archiving and communications systems, or teleradiology. In order to reduce transmission time and storage cost, an efficient data-compression scheme to reduce digital data without significant degradation of medical image quality is needed. In this study, we have applied two region-based compression methods to digital mammograms. In both methods, after segmenting the breast region, a region-based discrete wavelet transform is applied, followed by an object-based extension of the set partitioning in hierarchical trees (OB-SPIHT) coding algorithm in one method, and an object-based extension of the set partitioned embedded block (OB-SPECK) coding algorithm in the other. We have compared these specific implementations against the original SPIHT and the new standard JPEG 2000, both using reversible and irreversible filters, on five digital mammograms compressed at rates ranging from 0.1 to 1.0 bit per pixel (bbp). Distortion was evaluated for all images and compression rates by the peak signal-to-noise ratio. For all images, OB-SPIHT and OB-SPECK performed substantially better than the traditional SPIHT and JPEG 2000, and a slight difference in performance was found between them. A comparison applying SPIHT and the standard JPEG 2000 to the same set of images with the background pixels fixed to zero was also carried out, obtaining similar implementation as region-based methods. For digital mammography, region-based compression methods represent an improvement in compression efficiency from full-image methods, also providing the possibility of encoding multiple regions of interest independently.

We investigate and prove the relationships among several commonly used and new performance metrics for embedded image bit streams transmitted over noisy channels. The average of the first error-free run length (FEFRL) is proposed as a simpler performance metric. On binary symmetric channels (BSC), the average FEFRL is obtained in closed form, which greatly simplifies performance optimization. Simulation results justify the merit of the proposed technique.

Compressed video bitstreams require protection from channel errors in a wireless channel. The 3-D set partitioning in hierarchical trees (SPIHT) coder has proved its efficiency and its real-time capability in the compression of video. A forward-error-correcting (FEC) channel (RCPC) code combined with a single automatic-repeat request (ARQ) proved to be an effective means for protecting the bitstream. There were two problems with this scheme: (1) the noiseless reverse channel ARQ may not be feasible in practice and (2) in the absence of channel coding and ARQ, the decoded sequence was hopelessly corrupted even for relatively clean channels. We eliminate the need for ARQ by making the 3-D SPIHT bitstream more robust and resistant to channel errors. We first break the wavelet transform into a number of spatio-temporal tree blocks which can be encoded and decoded independently by the 3-D SPIHT algorithm. This procedure brings the added benefit of parallelization of the compression and decompression algorithms, and enables implementation of region-based coding. We demonstrate the packetization of the bitstream and the reorganization of these packets to achieve scalability in bit rate and/or resolution in addition to robustness. Then we encode each packet with a channel code. Not only does this protect the integrity of the packets in most cases, but it also allows detection of packet-decoding failures, so that only the cleanly recovered packets are reconstructed. In extensive comparative tests, the reconstructed video is shown to be superior to that of MPEG-2, with the margin of superiority growing substantially as the channel becomes noisier. Furthermore, the parallelization makes possible real-time implementation in hardware and software.

This paper proposes several low complexity algorithmic modifications to the SPIHT (set partitioning in hierarchical trees) image coding method of Said and Pearlman (1996). The modifications exploit universal traits common to the real world images. Approximately 1-2% compression gain (bit rate reduction for a given mean squared error) has been obtained for the images in our test suite by incorporating all of the proposed modifications into SPIHT.

We present a low-complexity entropy coder originally designed to work in the JPEG2000 image compression standard framework. The algorithm is meant for embedded and non-embedded coding of wavelet coefficients inside a subband, and is called subband-block hierarchical partitioning (SBHP). It was extensively tested following the standard experiment procedures, and it was shown to yield a significant reduction in the complexity of entropy coding, with small loss in compression performance. Furthermore, it is able to seamlessly support all JPEG2000 features. We present a description of the algorithm, an analysis of its complexity, and a summary of the results obtained after its integration into the verification model (VM).

This paper presents a low memory implementation of efficient lossy volumetric medical image compression using the set partitioning in hierarchical trees (SPIHT) algorithm. The coding units in this three-dimensional wavelet transform and compression method are short sequences of horizontal stripes cut from the sequence of slices in the volumetric image. As the compression degree increases, the boundaries between adjacent coding units became increasingly visible. Unlike video, where image frames are viewed under dynamic conditions, the volume image is examined under static conditions and must not exhibit such boundary artifacts. In order to eliminate them, we utilize overlapping and averaging both at the intra-slice and inter-slice boundaries between adjacent and successive stripe sequences. Our low memory implementation smooths out considerably the variation in mean squared error among different slices and suffers only an insignificant loss in performance from that of a full memory implementation.

A variant of the SPIHT image compression algorithm called no list SPIHT (NLS) is presented. NLS operates without linked lists and is suitable for a fast, simple hardware implementation. NLS has a fixed predetermined memory requirement about 50% larger than that needed for the image alone. Instead of lists, a state table with four bits per coefficient keeps track of the set partitions and what information has been encoded. NLS sparsely marks selected descendant nodes of insignificant trees in the state table in such a way that large groups of predictably insignificant pixels are easily identified and skipped during coding passes. The image data is stored in a one dimensional recursive zig-zag array for computational efficiency and algorithmic simplicity. The performance of the algorithm on standard test images is nearly the same as SPIHT.

This paper presents a low memory implementation of efficient lossy volumetric medical image compression using the Set Partitioningin Hierarchical Trees (SPIHT) algorithm. The coding units in this three-dimensionalwavelet transform and compression method are short sequences of horizontal stripes cut from the sequence of slices in the volumetric image. As the compression degree increases, the boundaries between adjacent coding units became increasingly visible. Unlike video, where image frames are viewed under dynamic conditions, the volume image is examined under static conditions and must not exhibit such boundary artifacts. In order to eliminate them, we utilize overlappingand averaging both at the intra-slice and inter-slice boundaries between adjacent and successive stripe sequences. Our low memory implementation smooths out considerably the variation in mean squared error among different slices and suffers only an insignificant loss in performance from that of a full memory implementation.

A semi-automatic algorithm to extract the semantic video object from image sequences is proposed. Different schemes are used to get the initial video object in the first frame and other frames of a sequence. In the first frame, two polygons are input by the user to specify the area in which the object boundary is located. Then the video object is extracted automatically based on only the first frame. In the following frames, the image frame is segmented into intensity homogeneous regions. The moving regions are detected by a morphological filter, non-moving regions are selected by the object model obtained from the previous frame. These regions form the initial video object. In each frame, after the initial object is available, the edges which belong to the video object of interest are selected by a local object contour model. Finally, an active contour model (snake) is applied to extract the final object contour.

This paper describes a low-memory cache efficient hybrid block coder (HBC) for images in which an image subband decomposition is partitioned into a combination of spatial blocks and subband blocks, which are independently coded. Spatial blocks contain hierarchical trees spanning subband levels, and are each encoded using the SPIHT algorithm. Subband blocks contain a block of coefficients from within a single subband, and are each encoded by the SPECK algorithm. The decomposition may have the dyadic or a wavelet packet structure. Rate is allocated amongst the sub-bitstreams produced for each block and they are packetized. The partitioning structure supports resolution embedding. The final bitstream may be progressive in fidelity or in resolution.

We propose a low bit-rate embedded video coding scheme that utilizes a 3-D extension of the set partitioning in hierarchical trees (SPIHT) algorithm which has proved so successful in still image coding. Three-dimensional spatio-temporal orientation trees coupled with powerful SPIHT sorting and refinement renders 3-D SPIHT video coder so efficient that it provides comparable performance to H.263 objectively and subjectively when operated at the bit rates of 30 to 60 kbits/s with minimal system complexity. Extension to color-embedded video coding is accomplished without explicit bit allocation, and can be used for any color plane representation. In addition to being rate scalable, the proposed video coder allows multiresolutional scalability in encoding and decoding in both time and space from one bit stream. This added functionality along with many desirable attributes, such as full embeddedness for progressive transmission, precise rate control for constant bit-rate traffic, and low complexity for possible software-only video applications, makes the proposed video coder an attractive candidate for multimedia applications.

Summary form only given. One of the most popular encoders in the literature is the LZ78, which was proposed by Ziv and Lempel (1978). We establish a recursive way to find the longest m-tuple match. We prove the following theorem that shows how to obtain a longest (m+1)-tuple match from the longest m-tuple match. It shows that a (m+1)-tuple match is the concatenation of the first (m-1) words of the m-tuple match with the next longest double match. Therefore, the longest (m+1)-tuple match can be found using the m-tuple match and a procedure to compute the longest double match. Our theorem is as follows. Let A be a source alphabet, let A* be the set of all finite strings of A, and D/spl sub/A*, such that if x/spl isin/D then all prefixes of x belong to D. Let u denote a one-sided infinite sequence. If b/sub 1//sup m/ is the longest m-tuple match in u, with respect to D, then there is a longest (m+1)-tuple match b/spl circ//sub 1//sup m+1/, such that b/spl circ//sub i/=b/sub i/,/spl forall/i/spl isin/{1,...m-1}. We implemented the fast mmLZ and the results show a improvement in compression of around 5% over the LZW, in the Canterbury Corpus (Arnold and Bell, 1997) with little extra computational cost.

Constrained storage vector quantization, (CSVQ), introduced by Chan and Gersho (1990, 1991) allows for the stagewise design of balanced tree-structured residual vector quantization codebooks with low encoding and storage complexities. On the other hand, it has been established by Makhoul et al. (1985), Riskin et al. (1991), and by Mahesh et al. (see IEEE Trans. Inform. Theory, vol.41, p.917-30, 1995) that variable-length tree-structured vector quantizer (VLTSVQ) yields better coding performance than a balanced tree-structured vector quantizer and may even outperform a full-search vector quantizer due to the nonuniform distribution of rate among the subsets of its input space. The variable-length constrained storage tree-structured vector quantization (VLCS-TSVQ) algorithm presented in this paper utilizes the codebook sharing by multiple vector sources concept as in CSVQ to greedily grow an unbalanced tree structured residual vector quantizer with constrained storage. It is demonstrated by simulations on test sets from various synthetic one dimensional (1-D) sources and real-world images that the performance of VLCS-TSVQ, whose codebook storage complexity varies linearly with rate, can come very close to the performance of greedy growth VLTSVQ of Riskin et al. and Mahesh et al. The dramatically reduced size of the overall codebook allows the transmission of the code vector probabilities as side information for source adaptive entropy coding.

We address multiresolutional encoding and decoding within the embedded zerotree wavelet (EZW) framework for both images and video. By varying a resolution parameter, one can obtain decoded images at different resolutions from one single encoded bitstream, which is already rate scalable for EZW coders. Similarly one can decode video sequences at different rates and different spatial and temporal resolutions from one bitstream. Furthermore, a layered bitstream can be generated with multiresolutional encoding, from which the higher resolution layers can be used to increase the spatial/temporal resolution of the images/video obtained from the low resolution layer. In other words, we have achieved full scalability in rate and partial scalability in space and time. This added spatial/temporal scalability is significant for emerging multimedia applications such as fast decoding, image/video database browsing, telemedicine, multipoint video conferencing, and distance learning.

We extend the work of Sherwood and Zeger (IEEE Signal Processing Letters, vol.4, p.189-91, 1997) to progressive video coding for noisy channels. By utilizing a three dimensional (3D) extension of the set partitioning in hierarchical trees (SPIHT) algorithm, we cascade the resulting 3D SPIHT video coder with the rate-compatible punctured convolutional (RCPC) channel coder for transmission of video over a binary symmetric channel (BSC). Progressive coding is achieved by increasing the target rate of the 3D embedded SPIHT video coder as the channel condition improves. The performance of our proposed coding system is acceptable at a low transmission rate and bad channel conditions. Its low complexity makes it suitable for emerging applications such as video over wireless channels.

This paper proposes an efficient, low complexity audio coder based on the SPIHT (set partitioning in hierarchical trees) coding algorithm , which has achieved notable success in still image coding. A wavelet packet transform is used to decompose the audio signal into 29 frequency subbands corresponding roughly to the critical subbands of the human auditory system. A psychoacoustic model, which, for simplicity, is based on MPEG model I, is used to calculate the signal to mask ratio, and then calculate the bit rate allocation among subbands. We distinguish the subbands into two groups: the low frequency group which contains the first 17 subbands corresponding to 0-3.4 kHz, and the high frequency group which contains the remaining high frequency subbands. The SPIHT algorithm is used to encode and decode the low frequency group and a reverse sorting process plus arithmetic coding algorithm is used to encode and decode the high frequency group. The experiment shows that this coder yields nearly transparent quality at bit rates 55-66 kbits/sec, and degrades only gradually at lower rates. The low complexity of this coding system shows its potential for interactive applications with levels of quality from good to perceptually transparent.

We examine progressive lossy to lossless compression of medical volumetric data using three-dimensional (3D) integer wavelet packet transforms and set partitioning in hierarchical trees (SPIHT). To achieve good lossy coding performance, we describe a 3D integer wavelet packet transform that allows implicit bit shifting of wavelet coefficients to approximate a 3D unitary transformation. We also address context modeling for efficient entropy coding within the SPIHT framework. Both lossy and lossless coding performance are better than those previously reported.

The SPIHT (set partitioning in hierarchical trees) algorithm by Said and Pearlman (see IEEE Trans. on Circuits and Systems for Video Technology, no.6, p.243-250, 1996) is known to have produced some of the best results in still image coding. It is a fully embedded wavelet coding algorithm with precise rate control and low complexity. We present an application of the SPIHT algorithm to video sequences, using three-dimensional (3D) wavelet decompositions and 3D spatio-temporal dependence trees. A full 3D-SPIHT encoder/decoder is implemented in software and is compared against MPEG-2 in parallel simulations. Although there is no motion estimation or compensation in the 3D SPIHT, it performs measurably and visually better than MPEG-2, which employs complicated motion estimation and compensation.

The paper treats the subject of wavelet (pyramid) decomposition and reconstruction for the purposes of image and signal compression. A new, fast and promising technique given an arbitrary low-pass filter enables us to find a corresponding high-pass filter. The decomposition and reconstruction are executed fast by employing the short recursive filters either before the reconstruction or after the decomposition. This technique was used for finding the filters producing the best results for the given support size. Three such filters are considered. The simulation results are presented in the tables and plots. They show that our 7 tap filter is better for compression than the well known 9/7 filter.

Embedded zerotree wavelet (EZW) coding, introduced by Shapiro (see IEEE Trans. Signal Processing, vol.41, no.12, p.3445, 1993), is a very effective and computationally simple technique for image compression. We offer an alternative explanation of the principles of its operation, so that the reasons for its excellent performance can be better understood. These principles are partial ordering by magnitude with a set partitioning sorting algorithm, ordered bit plane transmission, and exploitation of self-similarity across different scales of an image wavelet transform. Moreover, we present a new and different implementation based on set partitioning in hierarchical trees (SPIHT), which provides even better performance than our previously reported extension of EZW that surpassed the performance of the original EZW. The image coding results, calculated from actual file sizes and images reconstructed by the decoding algorithm, are either comparable to or surpass previous results obtained through much more sophisticated and computationally complex methods. In addition, the new coding and decoding procedures are extremely fast, and they can be made even faster, with only small loss in performance, by omitting entropy coding of the bit stream by the arithmetic code.

We propose a new image multiresolution transform that is suited for both lossless (reversible) and lossy compression. The new transformation is similar to the subband decomposition, but can be computed with only integer addition and bit-shift operations. During its calculation, the number of bits required to represent the transformed image is kept small through careful scaling and truncations. Numerical results show that the entropy obtained with the new transform is smaller than that obtained with predictive coding of similar complexity. In addition, we propose entropy-coding methods that exploit the multiresolution structure, and can efficiently compress the transformed image for progressive transmission (up to exact recovery). The lossless compression ratios are among the best in the literature, and simultaneously the rate versus distortion performance is comparable to those of the most efficient lossy compression methods.

A novel approach for coding textured images is presented. The texture field is assumed to be a realization of a regular homogeneous random field, which can have a mixed spectral distribution. On the basis of a two-dimensional (2-D) Wold-like decomposition, the field is represented as a sum of a purely indeterministic, harmonic, and countable number of evanescent fields. We present an algorithm for estimating and coding the texture model parameters, and show that the suggested algorithm yields high-quality reconstructions at low bit rates. The model and the resulting coding algorithm are seen to be applicable to a wide variety of texture types found in natural images.

Linear prediction schemes make a prediction x/spl circ//sub i/ of a data sample x/sub i/ using p previous samples. It has been shown by Woods and O'Neil (1986) as well as Pearlman (1991) that as the order of prediction p/spl rarr//spl infin/, there is no gain to be obtained by coding subband samples. This paper deals with the less well understood theory of finite-order prediction and optimal coding from subbands which are generated by ideal (brickwall) filtering of a stationary Gaussian source. We first prove that pth-order prediction from subbands is superior to pth-order prediction in the fullband, when p is finite. This fact adduces that optimal vector p-tuple coding in the subbands is shown to offer quantifiable gains over optimal fullband p-tuple coding, again when p is finite. The properties of subband spectra are analyzed using the spectral flatness measure. These results are used to prove that subband DPCM provides a coding gain over fullband DPCM, for finite orders of prediction. In addition, the proofs provide means of quantifying the subband advantages in linear prediction, optimal coding, and DPCM coding in the form of gain formulas. Subband decomposition of a source is shown to result in a whitening of the composite subband spectrum. This implies that, for any stationary source, a pth-order prediction error filter (PEF) can be found that is better than the pth-order PEF obtained by solving the Yule-Walker equations resulting from the fullband data. We demonstrate the existence of such a "super-optimal" PEF and provide algorithmic approaches to obtaining this PEF. The equivalence of linear prediction and AR spectral estimation is then exploited to show theoretically, and with simulations, that AR spectral estimation from subbands offers a gain over fullband AR spectral estimation.

The optimal joint decoder utilizing NLIVQ (nonlinear interpolative vector quantization) introduced by Gersho [1990] results in vector quantizers which have reduced encoding complexity at the expense of coding performance loss due to the inferiority of their space-filling property. We show a method of improving a high resolution NLIVQ codebook by partitioning its cells in such a way that the resulting lower resolution codebook consists of cells with better space-filling properties. The resolution reduction method is also extended to the case where the quantizer indices are entropy-constrained. From the simulations it is seen that the unconstrained and constrained entropy versions of the proposed vector quantizer have comparable performance to vector quantizers designed by LEG and ECVQ algorithms.

We propose an elegant yet efficient adaptive subband coding scheme in which the rate allocation and structures of the quantizers are jointly optimized based on the time-varying rate-distortion characteristics of the input signals. By employing the tree-structured vector quantizers and the generalized BFOS pruning algorithm, the operations of the rate allocation and quantization are elegantly combined, whereby the adaptation is both convenient and optimal. The results on video coding have shown that the adaptive scheme can achieve substantial performance improvement over the non-adaptive scheme.

A clustering algorithm for the design of efficient vector quantizers to be followed by entropy coding is proposed. The algorithm, called entropy-constrained pairwise nearest neighbor (ECPNN), designs codebooks by merging the pair of Voronoi regions which gives the least increase in distortion for a given decrease in entropy. The algorithm can be used as an alternative to the entropy-constrained vector quantizer design (ECVQ) proposed by Chou, Lookabaugh, and Gray (1989). By a natural extension of the ECPNN algorithm the authors develop another algorithm that designs alphabet and entropy-constrained vector quantizers and call it alphabet- and entropy-constrained pairwise nearest neighbor (AECPNN) design. Through simulations on synthetic sources, it is shown that ECPNN and ECVQ have indistinguishable mean-square-error versus rate performance and that the ECPNN and AECPNN algorithms obtain as close performance by the same measure as the ECVQ and AECVQ (Rao and Pearlman, 1993) algorithms. The advantages over ECVQ are that the ECPNN approach enables much faster codebook design and uses smaller codebooks. A single pass through the ECPNN (or AECPNN) design algorithm, which progresses from larger to successively smaller rates, allows the storage of any desired number of intermediate codebooks. In the context of multirate subband (or transform) coders, this feature is especially desirable. The performance of coding image pyramids using ECPNN and AECPNN codebooks at rates from 1/3 to 1.0 bit/pixel is discussed.>

In general, growth algorithms for optimal tree-structured vector quantizers do not exist. In this paper we show that if the source satisfies certain conditions; namely, that of diminishing marginal returns; optimal growth algorithms do exist. We present such an algorithm and compare its performance with that of other tree growth algorithms. Even for sources that do not meet the necessary conditions for the growth algorithm to be optimal, such as for speech with unknown statistics, it is seen by simulation that the algorithm outperforms other known growth algorithms, For sources that do not satisfy the required conditions, the algorithm presented here can also be used to grow the initial tree for the pruning process. The performance of such pruned trees is superior to that of trees pruned from full trees of the same rate.>

Most existing quadrature mirror filters (QMFs) closely match the derived closed-form expression for an efficient class of QMFs. We use the closed-form expressions to derive the relationship between information-theoretic loss and the frequency selectivity of the QMF, by calculating first-order entropy as well as rate-distortion theoretic performance of a two band QMF system. We find that practical QMFs do not suffer a significant information-theoretic loss with first-order autoregressive Gaussian sources. With second-order autoregressive sources we find that practical QMFs suffer a notable information-theoretic loss when the bandwidth of the source is extremely narrow, but incur a small loss when the bandwidth is wider. We suggest that our results broadly apply to higher order autoregressive sources as well.

The performance of optimum vector quantizers subject to a conditional entropy constraint is studied. This new class of vector quantizers was originally suggested by Chou and Lookabaugh (1990). A locally optimal design of this kind of vector quantizer can be accomplished through a generalization of the well-known entropy-constrained vector quantizer (ECVQ) algorithm. This generalization of the ECVQ algorithm to a conditional entropy-constrained is called CECVQ, i.e., conditional ECVQ. Furthermore, we have extended the high-rate quantization theory to this new class of quantizers to obtain a new high-rate performance bound. The new performance bound is compared and shown to be consistent with bounds derived through conditional rate-distortion theory. A new algorithm for designing entropy-constrained vector quantizers was introduced by Garrido, Pearlman, and Finamore (see IEEE Trans. Circuits Syst. Video Technol., vol.5, no.2, p.83-95, 1995), and is named entropy-constrained pairwise nearest neighbor (ECPNN). The algorithm is basically an entropy-constrained version of the pairwise nearest neighbor (ECPNN) clustering algorithm of Equitz (1989). By a natural extension of the ECPNN algorithm we develop another algorithm, called CECPNN, that designs conditional entropy-constrained vector quantizers. Through simulation results on synthetic sources, we show that CECPNN and CECVQ have very close distortion-rate performance.>

We study the performance of conditional entropy-constrained vector quantizers when used to quantize subbands of the displaced frame differences derived from video sequences. Chou and Lookabaugh (1990) originally suggested a locally optimal design of this new kind of vector quantizer which can be accomplished through a generalization of the well known entropy-constrained vector quantizer (ECVQ) algorithm. This generalization of the ECVQ algorithm to a conditional entropy-constrained is called CECVQ, i.e., conditional ECVQ. The non-memoryless quantization performed by the conditional entropy-constrained VQ is based on the current vector to be encoded and the previous encoded vector. A new algorithm for conditional entropy-constrained vector quantizer design is derived and it is based on the pairwise nearest neighbour technique presented by Equitz (1989).>

A novel approach for coding textured images is presented. The texture field is assumed to be a realization of a regular homogeneous random field, which can have a mixed spectral distribution. On the basis of a 2D Wold-like decomposition, the field is represented as a sum of purely indeterministic, harmonic, and a countable number of evanescent fields. We present an algorithm for estimating and coding the texture model parameters, and show that the suggested algorithm yields high quality reconstructions at low bit rates. The model and the resulting coding algorithm are seen to be applicable to a wide variety of texture types found in natural images.

The paper presents two different approaches to image sequence coding which exploit the spatial frequency statistics as well as the spatial and temporal correlation present in the video signal. The first approach is the pyramidal decomposition of the Motion Compensated Frame Difference (MCFD) signal in the frequency domain and the subsequent coding by unbalanced Tree Structured Vector Quantizers (TSVQ) designed to match the statistics of the frequency bands. The type of TSVQ used in this study possess the advantage of low computational complexity with coding performance comparable to full-search vector quantization. The second approach is similar except that the order of motion estimation/compensation and pyramidal decomposition are interchanged.

A simple yet effective image sequence coding technique based on the zero-tree method is studied. The frames of the image sequence are decomposed hierarchically into 5 levels and motion compensation is performed on each subband separately. The displaced frame difference (DFD) is then encoded using the zero-tree method. Simulations done on the first 60 frames of the Miss America sequence using backward motion compensation with pel recursive motion estimation technique have yielded an average PSNR of 40.52 dB at a rate of 0.3 bpp and 43.68 dB at 1.0 bpp. This technique has the advantage that it works well with most images as no training set is required. There is precise control of the coding rate and the transmission is progressive.

In this paper a new image transformation suited for reversible (lossless) image compression is presented. It uses a simple pyramid multiresolution scheme which is enhanced via predictive coding. The new transformation is similar to the subband decomposition, but it uses only integer operations. The number of bits required to represent the transformed image is kept small through careful scaling and truncations. The lossless coding compression rates are smaller than those obtained with predictive coding of equivalent complexity. It is also shown that the new transform can be effectively used, with the same coding algorithm, for both lossless and lossy compression. When used for lossy compression, its rate-distortion function is comparable to other efficient lossy compression methods.

Alphabet-constrained rate-distortion theory is extended to coding of sources with memory. Two different cases are considered: when only the size of the codebook is constrained and when the codevector values are also held fixed. For both cases, nth-order constrained-alphabet rate-distortion functions are defined and a convergent algorithm for their evaluation is presented. Specific simulations using AR(1) sources show that performance near the rate-distortion bound is possible using a reproduction alphabet consisting of a small number of codevectors. It is also shown that the additional constraint of holding the codevector values fixed does not degrade performance of the coder in relation to the size-only constrained case. This observation motivates the development of a fixed-codebook vector quantizer, called the alphabet- and entropy-constrained vector quantizer, the performance of which is comparable to the entropy-constrained vector quantizer. A number of examples using an AR(1) and a speech source are presented to corroborate the theory.>

Reduction of exposure in a pulsed cardiac X-ray fluoroscopy system may be accomplished by interrupting exposure during slower phases of the cardiac cycle and filling in the missing frames by interpolation to restore the full frame rate. The authors present a novel interpolation method whereby the collected frames are decomposed into a multiresolution hierarchy and a pixel-recursive algorithm is employed from the lowest to highest resolution in the hierarchy to obtain estimates of the pixel displacements. The intensity changes between corresponding pixels are then interpolated to fill in the missing frames. The authors show a computer simulation of the method, where only 11 of the original 29 frames produce a natural, nearly artifact-free rendition of the sequence.>

A new algorithm for multirate vector quantization is used for coding image pyramids. The algorithm, called alphabet and entropy-constrained pairwise-nearest-neighbor (AECPNN), designs codebooks choosing subcodebooks from a large generic codebook. The algorithm is the natural extension of the ECPNN design technique with constrained alphabet. Results of coded image pyramids obtained using the present algorithm are comparable to results for the ECPNN design technique.>

A new algorithm for nonorthogonal decomposition is proposed and applied to Gabor decomposition of image. The algorithm is iterative and its advantages are discussed. Also a modified version of the algorithm is considered which increases the rate of convergence. Image simulations show that this method gives much lower reconstruction error that the method using biorthogonal functions, at a cost of a greater amount of computer time.>

A tree code, asymptotically optimal for stationary Gaussian sources and squared error distortion, is applied suboptimally to encode the discrete cosine transform (DCT) of image subblocks. The variance spectrum of each block DCT is estimated and specified uniquely by a set of one-dimensional autoregressive parameters. The average pel rate for each block is allowed to vary to meet the specification of the same average distortion per block. Since the variance spectrum and rate are different for every block. so is the code tree. Comparative coding simulations with a 256*256 and 512*512 image show that DCT tree coding with postcoding is clearly superior to DCT quantization and that a variable block rate assignment gains about 3 dB over a fixed block rate assignment.>

The authors consider the encoding of image subbands with a tree code that is asymptotically optimal for Gaussian sources and the mean squared error (MSE) distortion measure. They first prove that optimal encoding of ideally filtered subbands of a Gaussian image source achieves the rate distortion bound for the MSE distortion measure. The optimal rate and distortion allocation among the subbands is a by-product of this proof. A bound is derived which shows that subband coding is closer than full-band coding to the rate distortion bound for a finite length sequence. The tree codes are then applied to encode the image subbands, both nonadaptively and adaptively. Since the tree codes are stochastic and the search of the code tree is selective, a relatively few reproduction symbols may have an associated squared error a hundred times larger than the target for the subband. Correcting these symbols through a postcoding procedure improves the signal-to-noise ratio and visual quality significantly, with a marginal increase in total rate.

An algorithm given by R.P. Rao (see Proc. IEEE Inter. Telecomm. Symp., Sept. 1990) for multirate vector quantization is used for coding image pyramids. The algorithm, called alphabet- and entropy-constrained vector quantization (AECVQ), operates by optimally choosing sub-codebooks from a large generic codebook. In terms of performance and complexity, AECVQ equals the best single-rate VQ. Excellent results at 1 b/p and below, judged both visually and using a peak-to-peak SNR criterion, have been obtained by coding image pyramids using the AECVQ algorithm. these results demonstrate significant improvements over existing schemes. Although an AECVQ based image coding scheme is considerably complex, it can be implemented in real time using current VLSI technology.>

An information-theoretic analysis of multiresolution pyramid structures is presented. The analysis is carried out using the concept of spectral entropy which, for Gaussian sources, is linearly related to the differential entropy. The spectral entropy is used to define the spectral roughness measure that, in turn, is an indicator of the amount of memory in a source. The more the memory in a source, the greater is the value of its spectral roughness measure. The spectral roughness measure also plays an important role in lower bounding the rate-distortion function. The main result is that the spectral roughness measure of a pyramid structure is less than that of the original fullband process. This means that substantial reduction in bits can be obtained by merely representing a source as a pyramid. Simulations using one-dimensional and two-dimensional sources verifying these claims are presented.>

A clustering algorithm for the design of efficient vector quantizers to be followed by entropy coding is proposed. The algorithm generates a sequence of quantizers whith rates close to theoretical rate- distortion bound. A fast version of this algorithm can be used as an alternative to the entropy-constrained vector quantizer technique proposed by Chou, Lookabaugh and Gray.

There exists a transform trellis code that is optimal for stationary Gaussian sources and the squared- error distortion measure at all rates. In this paper, we train an asymptotically optimal version of such a code to obtain one which is matched better to the statistics of real world data. The training algorithm uses the M-algorithm to search the trellis codebook and the LBG-algorithm to update the trellis codebook. To adapt the codebook for the varying input data, we use two gain-adaptive methods. The gain-adaptive sheme 1, which normalizes input block data by its gain factor, is applied to images at rate 0.5 bits/pixel. When each block is encoded at the same rate, the nonstationarity among the block variances leads to a variation in the resulting distortion from one block to another. To alleviate the non-uniformity among the encoded image, we design four clusters from the block power, in which each cluster has its own trellis codebook and different rates. The rate of each cluster is assigned through requiring a constant distortion per-letter. This gain-adaptive scheme 2 produces good visual and measurable quality at low rates.

A transform trellis coding scheme is used to encode images at rates below 1 b/pel, resulting in high SNR values and very good subjective performance. A discrete cosine transform (DCT) is used to decorrelate the data samples, and a trellis encoder is used to encode the transformed coefficients. To overcome image nonstationarity, a clustering algorithm is used to segment the transformed image into distinct regions and a separate trellis diagram is then constructed for each cluster. To further improve the image quality, particularly to reduce the blocking effect, a scalar quantizer is used to quantize large-magnitude coefficients of the error image in the transform domain. The performance of the proposed scheme is found to be better than that of other recently reported schemes.>

An adaptive block discrete-cosine transform (DCT) coding scheme is implemented with the same average distortion designated for each block. This constant distortion designation not only has perceptual advantages, but also allows the rate to vary, adjusting to the changing spectral characteristics among the blocks. The successful execution of this scheme requires a different spectral estimate for each block. To keep overhead and computation within limits, a novel technique is introduced by which a two-dimensional block spectrum is characterized by a one-dimensional autoregressive model. Simulations with images of natural scenes and medical radiology provide reconstructions with nearly uniform block distortion and very high visual and measurable quality at low rates.>

An image coding system is proposed in which hexagonally sampled images are decomposed into subbands that are selective in both frequency and orientation. Nine high-frequency bands each of one octave and 60 degrees of angular orientation are built on a pyramidal structure along with one low-frequency band. Bits are then allocated optimally to the subbands under a mean-squared-error distortion measure. Optimal quantizers are designed for each subband for entropy coding under a Laplacian distribution assumption. An adaptive version of the coding scheme is also implemented, and the results are compared at rates of 0.5 and 1.0 bits per pixel.>

A scheme for fast vector quantization is proposed. Instead of searching the whole code book directly, the proposed algorithm restricts the search to a very small subset of the code book. Given any input vector, the search process is divided into two steps: (1) define a subset that contains the nearest code vector and (2) find the optimal code vector from the subset. The main task of this algorithm is to define a minimum-size subset that is certain to contain the nearest code vector. A method that takes advantage of the relations of two kinds of Dirichlet partition, one of a lattice quantizer and the other of an ordinary vector quantizer, is given. Simulations using Gaussian and Laplacian sources show that the computational complexity can be substantially reduced with little loss (less than 0.1 dB) in performance.>

It is proved that optimal coding of image subbands achieves the ultimate rate-distortion performance for Gaussian sources with squared-error distortion. Optimal performance is achieved only asymptotically with infinite-size source sequences. The approach of the rate-distortion function of finite-size sequences to its limit is investigated and a bound is derived that shows a potentially closer approach for coding subbands that for the full band. A suboptimal realization of an optimal tree coding method is used to encode both the full-band image and its subbands at 1.0 bit per pixel. The subband tree-coded image is more than 2 dB better in SNR and its overall performance is nearly comparable to that of the best schemes known to date.>

A block discrete-cosine transform coding scheme is implemented with a different rate assignment to each block for the purpose of maintaining a constant distortion per block. A spectral estimate is calculated for every block. Overhead rate and computation for adaptation are kept to a reasonable level through characterization of the block's estimated spectrum by a one-dimensional autoregressive model. Simulations with natural and multimodality medical images provide reconstructions with nearly uniform block distortion and very high visual and measurable quality at low rates.>

Recently, Mazor and Pearlman[1] proved a source coding theorem for transform trellis codes. In this paper we apply their results to code speech using backward adaptation. Two spectral estimation techniques, called the moving average (MA) and autocorrelation (AR) techniques, are presented for estimating the spectrum from past and current blocks of speech for the purpose of constructing the trellis code for the next block of speech. Simulations are performed using both methods. The performance for the MA method is about 11 dB for a code of rate 1 bit/sample. For the AR method, the performance is about 12.5 dB for the same code rate. Tests are also performed on the effect of the trellis parameters on coding performance.

For a class of stationary Gaussian sources and the squared-error distortion measure, an asymptotically optimal tree coding scheme is derived using tree codes with finite branch length. The distribution of the reproduction process is derived in an explicit form, and using the random coding argument and results from the theory of branching processes with stationary ergodic environmental processes, the source coding theorem is proved. The theorem is applicable to all Gaussian sources with a power spectrum that satisfies the Lip 1 condition with no restriction on the coding rate.

A transform tree code, theoretically optimal for stationary Gaussian sources and the squared-error distortion measure at all rates, is adaptively applied in a blockwise fashion to the encoding of images. The rate of the basic tree code is 0.5 bits/pel and the overhead rate ranges from .24 to .36 bits/pel. A smoothing and block quantization is used for effective reduction of the rate for transmitting a set of eigenvalue estimates, which comprise the main contribution to the overhead. In encoding simulations the adaptation with smoothing and quantization gave better performance with a block size of 16 at lower search intensity and with more uniformity and less blocking effect. At a block size of 32, where the reconstruction quality is higher, the same adaptation technique yielded nearly the same results as the non-adaptive one at the same overall rate, but with a savings of search and computational complexity.

This paper presents a rate-distortion derived transform trellis coding (TTC) scheme with applications to Gaussian AR sources and speech data. The optimal encoder consists of a Karhunen-Loeve transform (KLT) on the source output, followed by a search on a trellis structured random code, where the decoder is a time-variant nonlinear filter. The scheme is implementable and applicable to stationary Gaussian sources with a bounded and continuous power spectrum and the squared error distortion measure. The code construction is based on the power or eigenvalue spectrum of the source with no restriction on the coding rate. The TTC scheme is first applied to encode a Gaussian AR source often used to model speech. Simulations were conducted at several rates, using an optimal KLT and the suboptimal discrete cosine transform (DCT). Results demonstrate that the DCT performs as well as the KLT, and both yield average distortions very close to the distortion-rate function. For speech data, an adaptive version of the DCT TTC scheme is applied to encode two speech sentences at several coding rates. The adaptation is controlled by an estimate of the short-term eigenvalue spectrum which is transmitted as side information to the receiver. The proposed scheme is a very efficient speech waveform coder that provides reconstructed speech with very high signal-to-noise ratio values and very good perceptual quality at low bit rates.

A new tree code is introduced for discrete-time stationary Gaussian sources with hounded, integrable power spectra and the squared-error distortion measure. The codewords in the tree are reconstructions of Karhunen-Loève transforms of the source words. The branching factor and the number of code letters per branch may vary with level in the tree. A theorem that guarantees the existence of an optimal code for any code rate using such a tree is proved. The proof uses the random coding argument in conjunction with a theorem on survival of a branching process with random environment. A suboptimal but computationally affordable realization of the theorem's coding technique was used for encoding simulations for six autoregressive sources at rates of1.0, 0.50, 0.25, and0.10bits per source symbol. The average distortion results were generally within1dB of the distortion-rate bound but varied widely depending on the source and rate. The results were compared with those for transform quantization simulations for the same sources and rates. The tree code always performed better but only by an average of0.44dB all sources and rates. Longer source blocks and more intensive search would certainly improve the performance of the tree codes, but at the expense of extra computation and storage.

We have utilized for image coding a transform tree coding technique that is theoretically optimal for Gaussian sources and the squared error criterion at all nonzero rates. In the interest of affordable computation, we used a suboptimal discrete cosine transform to encode image sub-blocks and a selective search through the code tree. Coding simulations of a woman's face image at rates of 1.0 and 0.25 bits/pel gave good to excellent results. The rate 1.0 results were superior to previous ones using another tree coding method. Until now there have been no reported results with searched codes for images using a rate under 1.0 bit/pel. Encoding a computer-generated image source indicated SNR performance about 2dB less than the optimal SNR of the rate-distortion bound.

We seek to evaluate the efficiency of hybrid transform/ DPCM interframe image coding relative to an optimal scheme that minimizes the mean-squared error in encoding a stationary Gaussian image sequence. The stationary assumption leads us to use the asymptotically optimal discrete Fourier transform (DFT) on the full frame of an image. We encode an actual image sequence with full-frame DFT/DPCM at several rates and compare it to previous interframe coding results with the same sequence. We also encode a single frame at these same rates using a full-frame DFT to demonstrate the inherent coding gains of interframe transform DPCM over intraframe coding. We then generate a pseudorandom image sequence with precise Gauss-Markov statistics and encode it by hybrid full-frame DFT/DPCM at various rates. We compare the signal-to-noise ratios (SNR's) of these reconstructions to the optimal ones calculated from the rate-distortion function. We conclude that in a medium rate range below 1 bit/pel/frame where reconstructions for hybrid transform/ DPCM may be unsatisfactory, there is enough margin for improvement to consider more sophisticated coding schemes.

Constraining the reproduction alphabet to be of small size in encoding continuous-amplitude memoryless sources has been shown to give very small degradation from the ideal performance of the rate-distortion bound. The optimum fixed-size reproduction alphabet and its individual letter probabilities are required in order to encode the source with performance approaching that of theory. These can be found through a somewhat lengthy, but convergent, algorithm. Given reasonably chosen fixed sets of reproduction letters and/or their probabilities, we define new rate-distortion functions which are coding bounds under these alphabet constraints. We calculate these functions for the Gaussian and Laplacian sources and the squared-error distortion measure and find that performance near the rate-distortion bound is achievable using a reproduction alphabet consisting of a small number of optimum quantizer levels.

For stationary discrete-time Gaussian sources and the squared-error distortion measure, a trellis source code is constructed. The encoder consists of a Karhunen-Loeve transform on the source output followed by a search on a trellis structured code, where the decoder is a time-variant nonlinear filter. The corresponding code theorem is proved using the random coding argument. The proof technique follows that of Viterbi and Omura, who proved the trellis coding theorem for memoryless sources. The resultant coding scheme is implementable and applicable at any nonzero rate to a stationary Gaussian source with a bounded and continuous power spectrum. Therefore. for stationary sources, it is more general than Berger's tree coding scheme, which is restricted to autoregressive Gaussian sources in a region of high rate (low distortion).

Recent research has shown that nearly optimum ratedistortion function performance can be obtained in encoding memoryless continuous-amplitude sources using a constrained-size reproduction alphabet. In this paper, we use a four-letter reproduction alphabet in encoding the Gaussian and Laplacian sources with the squared-error distortion measure. We introduce a sliding-block code generator/decoder and perform extensive coding simulations at a rate of one bit/source symbol. The average distortions in those simulations are much below the optimum quantization distortion and, with much smaller search intensity, are about the same or lower than distortions reported previously in comparable research. The slidingblock code results are also compared to those of parallel random coding simulations with the same reproduction alphabet and rate.

A non-adaptive scheme for encoding an image sequence is described that yields better results than any previous comparable interframe image coding method. The scheme uses a hybrid of two-dimensional transform coding for the spatial dimension and DPCM for the time dimension similar to some previous works [e.g., 1]. Unlike the previous efforts, which use discrete cosine transforms (DCT's) of image subblocks and suboptimal quantization, we utilize a full image DFT and an optimal quantization algorithm. The results with the standard sixteen frame sequence of Walter Cronkite are visually superior to previous transform coding efforts, especially at rates lower than 1 bit/pixel/ frame. The signal-to-noise ratios are higher than those of nonadaptive hybrid DCT/DPCM in [1] by 2.6 to 10.5 dB depending on rate.

A rate-distortion theory is introduced for the optimal encoding of stationary memoryless continuous-amplitude sources with a single-letter distortion measure and reproduction alphabets of a given finite size. The theory arises from a judicious approximation of the original continuous-input discrete-output problem by one with discrete input and output. A size-constrained output alphabet rate-distortion function is defined, its coding significance is established by coding theorems, and a convergent algorithm is presented for its evaluation. The theory is applied to Gaussian sources with squared-error distortion measure. Using the algorithm for the calculation of the new rate-distortion function in this case establishes the existence of codes which attain almost any desired rate between the rate-distortion bound and the optimum entropy-coded quantizer. Furthermore, one can closely approach the rate-distortion limit with a surprisingly small number of output levels. The calculation furnishes optimal output levels, output level probabilities, and other parameters necessary for a trellis coding simulation. The search algorithm represents the first use for asymmetric sources and distortion measures of a variation of a single stack algorithm proposed by Gallager. Carrying out the simulation at a rate of 1 bit per source symbol, codes are found with 4 and 64 output levels which attain distortions smaller than that of an optimum quantizer and close to the rate-distortion bound. Furthermore, these codes attain comparable or better performance with far less search effort than previous attempts with a continuous output alphabet.

We solve numerically the optimum fixed-level non-uniform and uniform quantization of a circularly symmetric complex (or bivariate) Gaussian random variable for the mean absolute squared error criterion. For a given number of total levels, we determine its factorization into the product of numbers of magnitude and phase levels that produces the minimum distortion. We tabulate the results for numbers of "useful" output levels up to 1024, giving their optimal factorizations, minimum distortion, and entropy. For uncoded quantizer outputs, we find that the optimal splitting of rate between magnitude and phase, averaging to 1.52 and 1.47 bits more in the phase angle than magnitude for optimum and uniform quantization, respectively, compares well with the optimal polar coding formula Of 1.376 bits of Pearlman and Gray [3]. We also compare the performance of polar to rectangular quantization by real and imaginary parts for both uncoded and coded output levels. We find that, for coded outputs, both polar quantizers are outperformed by the rectangular ones, whose distortion-rate curves nearly coincide with Pearlman and Gray's polar coding bound. For uncoded outputs, however, we determine that the polar quantizers surpass in performance their rectangular counterparts for all useful rates above 6.0 bits for both optimum and uniform quantization. Below this rate, the respective polar quantizers are either slightly inferior or comparable.

We have derived an efficient and general algorithm for optimal quantization and applied it to the important, but neglected Rayleigh random variable. The optimal quantization range and output levels for the distortion criterion of minimum mean squared error have been calculated and tabulated for numbers of output levels from 1 to 64. We also compute and report the corresponding distortions and output entropies. For the sake of comparison, we also calculate and tabulate level spacings, minimum errors, and entropies for the optimal uniform (equal step size) quantization of the Rayleigh density. Distortion-rate curves are presented for uncoded and entropy coded quantizer outputs and compared with the distortion-rate function. We judge that these results will be useful to workers in the fields of optical holography, image processing, and communications.

Distortion-rate theory is used to derive absolute performance bounds and encoding guidelines for direct fixed-rate minimum mean-square error data compression of the discrete Fourier transform (DFT) of a stationary real or circularly complex sequence. Both real-part-imaginary-part and magnitude-phase-angle encoding are treated. General source coding theorems are proved in order to justify using the optimal test channel transition probability distribution for allocating the information rate among the DFT coefficients and for calculating arbitrary performance measures on actual optimal codes. This technique has yielded a theoretical measure of the relative importance of phase angle over the magnitude in magnitude-phase-angle data compression. The result is that the phase angle must be encoded with 0.954 nats, or 1.37 bits, more rate than the magnitude for rates exceeding 3.0 nats per complex element. This result and the optimal error bounds are compared to empirical results for efficient quantization schemes.

The discrete Fourier transform (DFT) often is used instead of the optimum Karhunen-Lo\grave{e}ve transform (KLT) in encoding a stationary normal time series, because the recursive FFT is computationally efficient and yields "nearly" uncorrelated components. Substituting the DFT for the KLT and then treating its components as if they were uncorrelated reduces the ultimate performance attainable in fixed-rate source coding. We address the problem of this performance degradation by deriving a simple and easily applied upper bound on the increase in the distortion-rate function (DRF) for the mean-squared error criterion incurred by substitution of the DFT for the KLT.