In this paper, new upper and lower bounds are first presented for the rate loss of multiple description source codes (MDSCs). For a two-description MDSC (2DSC), the rate loss of descriptioniwith distortionDiis defined asLi=Ri-R(Di),i∈ {1,2}, whereRiis the rate of theith description andR(D) is the rate-distortion function for the given source; the joint rate loss associated with decoding the two descriptions together to achieve central distortionD0is measured asL0=R1+R2-R(D0). Consider an arbitrary memoryless source with variance σ2and let the distortion measure be the mean squared error distortion measure. It is shown that for any optimal 2DSC, (a)0 ≤L0≤ 0.8802 and 0 ≤L1,L2≤ 0.3802 ifD0≤D1+D2-σ2; (b) 0 ≤L1,L2≤ 0.4401 ifD0≥ (1/D1+1/D2-1/σ2)-1; (c) 0 ≤L1,L2≤ 0.3802 andR(max{D1,D2})-1 ≤L0≤R(max{D1,D2})+0.3802 for all otherD0. A tighter bound on the distance between the El Gamal-Cover inner bound and the achievable region is also presented. Inspired by these new bounds, a low-complexity composite 2DSC design first developed by Lastras-Montaño and Castelli is extended and the resulting code is shown to be near-optimal for all memoryless sources and all distortions. These results are also extended to MDSCs with an arbitrary number of packets. Finally, Gaussian sources are analyzed in detail to verify these bounds and examine their tightness.

In this paper, we study the rate loss and achievable region of the multiterminal source code (MTSC), which is the code designed for a system comprising two independent encoders and joint decoder: encoders 1 and 2 describe sources X and Y using rates R1and R2, respectively, and the joint decoder reconstructs X with distortion D1and reconstructs Y with distortion D2. The rate loss of an MTSC is defined as L1= R1$RX|Y(D1), L2= R2- RX|Y(D2), and L0= R1+ R2- RXY(D1, D2), where RXY(D1, D2) is the joint rate-distortion function of (X,Y), and RX|Y(D1) and RY|X(D2) are two conditional rate-distortion functions. We first show that for general real-valued memoryless sources and mean squared error distortion measure, the rate loss has an intrinsic connection with K1= RXY(D1, D2) $RY(D2) - RX|Y(D1) and K2= RXY(D1, D2) - RX(D1) - RY|X(D2). We then study two common types of sources, jointly Gaussian sources and remote sources, in more details and bound K1and K2from above by small universal constants, which leads to small universal upper bounds on the rate loss and therefore good approximations of the achievable region

In this paper, we present upper bounds on the rate loss of the multiresolution source code in the Wyner-Ziv setting (WZ-MRSC). We define two types of rate loss, the side-information rate loss and the multiresolution rate loss, to measure the nonsuccessive refinability. The former compares the rates achievable by a given WZ-MRSC to the corresponding minimal rates achievable by single-resolution Wyner-Ziv codes, and the latter refers to the difference between the rates achievable by a given WZ-MRSC and the minimal achievable rates by any WZ-MRSC at the same resolution. We bound these two types of rate loss from above and show that the side-information rate loss and corresponding successive refinability largely depend on the side information, while there exist small universal constant upper bounds on the multiresolution rate loss that are generally independent of the side information

In this paper, we first present new upper and lower bounds for the rate loss of multiple description source codes (MDSCs). For a two-description MDSC (2DSC), the rate loss of description i with distortion Diis Li= Ri$R(Di), i isin {1, 2}, where Riis the rate of the ith description; the joint rate loss associated with decoding the two descriptions together to achieve central distortion D0is L0= R1+ R2- R(D0). We show that given any memoryless source with variance sigma2and mean squared error distortion measure, for any optimal 2DSC, (a) 0 les L0les 0.8802 if D0les D1+ D2- sigma2; (b) 0 les L1, L2les 0.4401 if D0ges (1/D1+ 1/D2- 1/sigma2)-1; (c) 0 les L1, L2les 0.3802 and R(max{D1, D2}) - 1 les L0les R(max{D1, D2}) + 0.3802 otherwise. We also present a tighter bound on the distance between the El Gamal-Cover inner bound and the achievable region. In addition, these new bounds, which are easy to compute, inspire new designs of low-complexity near-optimal 2DSC. In essence, we demonstrate that any optimal 2DSC can be nearly separated into a multi-resolution source code and a traditional single-resolution code, and the resulting rate penalty for each description is less than 0.6901 bit/sample for general sources and less than 0.5 bit/sample for successively refinable sources

In this paper, we first define and bound the rate loss of source codes for broadcast channels. Our broadcast channel model comprises one transmitter and two receivers; the transmitter is connected to each receiver by a private channel and to both receivers by a common channel. The transmitter sends a description of source (X, Y) through these channels, receiver 1 reconstructs X with distortion D1, and receiver 2 reconstructs Y with distortion D2. Suppose the rates of the common channel and private channels 1 and 2 are R0, R1, and R2, respectively. The work of Gray and Wyner gives a complete characterization of all achievable rate triples (R0,R1,R2) given any distortion pair (D1,D2). In this paper, we define the rate loss as the gap between the achievable region and the outer bound composed by the rate-distortion functions, i.e., R0+R1+R2 ≥ RX,Y (D1,D2), R0 + R1 ≥ RX(D1), and R0 + R2 ≥ RY (D2). We upper bound the rate loss for general sources by functions of distortions and upper bound the rate loss for Gaussian sources by constants, which implies that though the outer bound is generally not achievable, it may be quite close to the achievable region. This also bounds the gap between the achievable region and the inner bound proposed by Gray and Wyner and bounds the performance penalty associated with using separate decoders rather than joint decoders. We then construct such source codes using entropy-constrained dithered quantizers. The resulting implementation has low complexity and performance close to the theoretical optimum. In particular, the gap between its performance and the theoretical optimum can be bounded from above by constants for Gaussian sources.

The rate loss of a multiresolution source code (MRSC) describes the difference between the rate needed to achieve distortion D/sub i/ in resolution i and the rate-distortion function R(D/sub i/). This paper generalizes the rate loss definition to multiple description source codes (MDSCs) and bounds the MDSC rate loss for arbitrary memoryless sources. For a two-description MDSC (2DSC), the rate loss of description i with distortion D/sub i/ is defined as L/sub i/=R/sub i/-R(D/sub i/), i=1,2, where R/sub i/ is the rate of the ith description; the joint rate loss associated with decoding the two descriptions together to achieve central distortion D/sub 0/ is measured either as L/sub 0/=R/sub 1/+R/sub 2/-R(D/sub 0/) or as L/sub 12/=L/sub 1/+L/sub 2/. We show that for any memoryless source with variance /spl sigma//sup 2/, there exists a 2DSC for that source with L/sub 1//spl les/1/2 or L/sub 2//spl les/1/2 and a) L/sub 0//spl les/1 if D/sub 0//spl les/D/sub 1/+D/sub 2/-/spl sigma//sup 2/, b) L/sub 12//spl les/1 if 1/D/sub 0//spl les/1/D/sub 1/+1/D/sub 2/-1//spl sigma//sup 2/, c) L/sub 0//spl les/L/sub G0/+1.5 and L/sub 12//spl les/L/sub G12/+1 otherwise, where L/sub G0/ and L/sub G12/ are the joint rate losses of a Gaussian source with variance /spl sigma//sup 2/.

In this paper, we build multiresolution source codes using entropy constrained dithered scalar quantizers. We demonstrate that for n-dimensional random vectors, dithering followed by uniform scalar quantization and then by entropy coding achieves performance close to the n-dimensional optimum for a multiresolution source code. Based on this result, we propose a practical code design algorithm and compare its performance with that of the set partitioning in hierarchical trees (SPIHT) algorithm on natural images.

We examine the performance of the Karhunen-Loeve transform (KLT) for transform coding applications. The KLT has long been viewed as the best available block transform for a system that orthogonally transforms a vector source, scalar quantizes the components of the transformed vector using optimal bit allocation, and then inverse transforms the vector. This paper treats fixed-rate and variable-rate transform codes of non-Gaussian sources. The fixed-rate approach uses an optimal fixed-rate scalar quantizer to describe the transform coefficients; the variable-rate approach uses a uniform scalar quantizer followed by an optimal entropy code, and each quantized component is encoded separately. Earlier work shows that for the variable-rate case there exist sources on which the KLT is not unique and the optimal quantization and coding stage matched to a "worst" KLT yields performance as much as 1.5 dB worse than the optimal quantization and coding stage matched to a "best" KLT. In this paper, we strengthen that result to show that in both the fixed-rate and the variable-rate coding frameworks there exist sources for which the performance penalty for using a "worst" KLT can be made arbitrarily large. Further, we demonstrate in both frameworks that there exist sources for which even a best KLT gives suboptimal performance. Finally, we show that even for vector sources where the KLT yields independent coefficients, the KLT can be suboptimal for fixed-rate coding.

The performance of the KLT for transform coding applications was examined. The KLT has long been viewed as the best available block transform for transform coding. The fixed-rate and variable-rate transform codes were also presented. The fixed-rate approach uses an optimal fixed-rate scalar quantizer to describe the transform coefficients; the variable-rate approach uses a uniform scalar quantizer followed by an optimal entropy code. Earlier work shows that for the variable-rate case, there exist sources on which the KLT is not unique and the optimal transform code matched to a "worst" KLT yields performance as much as 1.5 dB worse than the optimal transform code matched to a "best" KLT. The results were strengthened to show that in both the fixed-rate and the variable-rate coding frameworks, there exist sources for which the performance penalty for using a "worst" KLT can be made arbitrarily large. Further demonstrations in both frameworks show that there exist sources for which even a best KLT gives suboptimal performance. Finally, the results show that even for vector sources where the KLT yields independent coefficients, the KLT can be suboptimal for fixed-rate coding.

Summary form only given. Assuming the squared error distortion measure, the performance achieved is bounded by using scalar entropy constrained dithered quantization (SECDQ) to build multi-resolution (MR), multiple access (MA) and broadcast system (BS) source codes. The resulting performances for arbitrary source distribution are discussed.

We present new bounds for the rate loss of multiresolution source codes (MRSCs). Considering an M-resolution code, the rate loss at the ith resolution with distortion D/sub i/ is defined as L/sub i/=R/sub i/-R(D/sub i/), where R/sub i/ is the rate achievable by the MRSC at stage i. This rate loss describes the performance degradation of the MRSC compared to the best single-resolution code with the same distortion. For two-resolution source codes, there are three scenarios of particular interest: (i) when both resolutions are equally important; (ii) when the rate loss at the first resolution is 0 (L/sub 1/=0); (iii) when the rate loss at the second resolution is 0 (L/sub 2/=0). The work of Lastras and Berger (see ibid., vol.47, p.918-26, Mar. 2001) gives constant upper bounds for the rate loss of an arbitrary memoryless source in scenarios (i) and (ii) and an asymptotic bound for scenario (iii) as D/sub 2/ approaches 0. We focus on the squared error distortion measure and (a) prove that for scenario (iii) L/sub 1/<1.1610 for all D/sub 2/<D/sub 1/; (b) tighten the Lastras-Berger bound for scenario (ii) from L/sub 2//spl les/1 to L/sub 2/<0.7250; (c) tighten the Lastras-Berger bound for scenario (i) from L/sub i//spl les/1/2 to L/sub i/<0.3802, i/spl isin/{1,2}; and (d) generalize the bounds for scenarios (ii) and (iii) to M-resolution codes with M/spl ges/2. We also present upper bounds for the rate losses of additive MRSCs (AMRSCs). An AMRSC is a special MRSC where each resolution describes an incremental reproduction and the kth-resolution reconstruction equals the sum of the first k incremental reproductions. We obtain two bounds on the rate loss of AMRSCs: one primarily good for low-rate coding and another which depends on the source entropy.

We examine the rate-distortion performance and computational complexity of linear transforms for lossy data compression. The goal is to better understand the performance/complexity tradeoffs associated with using the Karhunen-Loeve transform (KLT) and its fast approximations. Since the optimal transform for transform coding is unknown in general, we investigate the performance penalties associated with using the KLT by examining cases where the KLT fails, developing a new transform that corrects the KLT's failures in those examples, and then empirically testing the performance difference between this new transform and the KLT. Experiments demonstrate that while the worst KLT can yield transform coding performance at least 3 dB worse than that of alternative block transforms, the performance penalty associated with using the KLT on real data sets seems to be significantly smaller, giving at most 0.5 dB difference in our experiments. The KLT and its fast variations studied here range in complexity requirements from O(n(2)) to O(n log n) in coding vectors of dimension n. We empirically investigate the rate-distortion performance tradeoffs associated with traversing this range of options. For example, an algorithm with complexity O(n(3/2)) and memory O(n) gives 0.4 dB performance loss relative to the full KLT in our image compression experiments.

The weighted universal transform code (WUTC) is a two-stage transform code that replaces JPEG's single, non-optimal transform code with a jointly designed collection of transform codes to achieve good performance across a broader class of possible sources. Unfortunately, the performance gains of WUTC are achieved at the expense of significant increases in computational complexity and larger codes. We here present a faster, more space-efficient WUTC algorithm. The new algorithm uses separable coding instead of direct KLT. While separable coding gives performance comparable to that of WUTC, it uses only 1/8 of the floating-point multiplications and 1/32 of storage of direct KLT. Experimental results included in this work compare the performance of new separable WUTC with both the WUTC and other fast variations of that algorithm.