AP_06_4.vp 1 Introduction Multiple description coding (MDC) is a source coding technique which can be used for transmitting data over lossy diversity networks. The MDC generates two or more diffe- rent descriptions, which are sent over different channels of the network. Each of these descriptions can be decoded independently. The reconstruction quality at the receiver in creases with the number of received descriptions. Decoding one description is usually called side decoding. Decoding more than one description is usually called central decoding. If all descriptions need the same bandwith and all side- decoder outputs are of the same quality, the descriptions are called balanced. For a scenario displayed in Fig. 1 the theo- retical limits for a gaussian source with zero mean and unit variance are derived in [3]. A popular approach for MDC uses the indices of an arbitrary quantizer for a mapping procedure called index assignment [8]. For this approach it is difficult to allocate re- dundancy for three or more descriptions in an optimal way, as mentioned in [6]. Partitioning based MDC avoids this problem, by using quantizers with different rates for generat- ing the side descriptions [1]. As an additional benefit such approaches may also generate standard conform descriptions [7]. For such multiple description schemes there are several ways for central decoding, which are compared in this paper. The paper is structured as follows: In section two, three dif- ferent ways for reconstruction at the central decoder are introduced. In section three, the test scenario is explained and experimental results are shown. In section four, the re- sults are summarized. 2 MDC based on domain partitioning In domain partitioning based MDC the MD encoders are scalar quantizers with different quantization intervals. This results in different quantization errors for each description, as shown in Fig. 2: y x qi i� � This simple approach can easily be generalized to N descriptions with N uniform scalar quantizers. The propor- tion between the different quantization intervals adjust the redundancy. High redundancy corresponds to nearly equal sized quantization intervals: � � i j � 1 Low redundancy corresponds to high differences between the quantization intervals: � � i j �1 These N quantizers generates N sets of indices that de- scribes the source data. Balanced descriptions are achieved by switching these indices by a scheme, known to encoder and decoder. 2.1 Highest rate reconstruction The simplest and most common way for central decoding uses only the description with the highest rate for each quan- tization index. Ignoring the lower rate descrip tions leads to easily predictable central distortion and low complexity. 28 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 4/2006 Central Decoding for Multiple Description Codes based on Domain Partitioning M. Spiertz, T. Rusert Multiple Description Codes (MDC) can be used to trade redundancy against packet loss resistance for transmitting data over lossy diversity networks. In this work we focus on MD transform coding based on domain partitioning. Compared to Vaishampayan’s quantizer based MDC, domain based MD coding is a simple approach for generating different descriptions, by using different quantizers for each description. Commonly, only the highest rate quantizer is used for reconstruction. In this paper we investigate the benefit of using the lower rate quantizers to enhance the reconstruction quality at decoder side. The comparison is done on artificial source data and on image data. Keywords: multiple description coding, domain based, scalar quantization, reconstruction, central decoder. Fig. 1: A multiple description scenario with two senders and three receivers Fig. 2: Domain based MDC, qi � quantization error correspond- ing to a quantization interval �i 2.2 Reconstruction by linear superposition It is possible to reduce the quantization error of the central decoder by using more descriptions than only the highest rate description. For this we introduce N weight- ing factors �i, and construct the central reconstruction by weighted superposition of the received side reconstructions. With 1 1 1 1 1 � � � � � � � � �� �i i N N i i N a (1) the central decoder can be written as: y y y x qi i i N i i i N � � � � � � �� � 1 1 To maximize the reconstruction quality, we minimize the following term: E y x E qi i i N {( ) }� � � � � � � � � � � �� � � � ��� �2 1 2 � (E{.} �� statistical expectation) As a first approximation, we assume that qi and qj are uncorrelated for i � j. As a matter of fact this is not true, espe- cially for � �i j k k� �, � . In section 3 we will show that even with this raw assumption an enhancement for central decod- ing is possible for high redundancy. � � � �E y x E qi i i N {( ) } {( ) }2 2 1 � Condition (1) reduces the dimension of this problem by one: E y x E q E qi i i N i i N N{( ) } { } {� � � � � � � � � � � � � � � �2 2 1 1 1 1 2 1� � 2 }. Minimization of quantization error by zero setting the derivation for each �i : � �� � � E y x E q E qi i N i i i N{( ) } { } { } !� � � � � � � � � � � � 2 2 2 1 1 0 1 � . (2) The solution of these N � 1 equations minimizes the quan- tization error. As an example for two dimensions, (1) and (2) leads to: �1 2 2 1 2 2 2� � E q E q E q { } { } { } �2 1 2 1 2 2 2� � E q E q E q { } { } { } 2.3 Intersection reconstruction A more deterministic way of using the lower rate descrip- tions to enhance the quality of the central decoder output is shown in [4] for DPCM systems. Each received quantization index belongs to one quantization interval with one lower limit Li, and one upper limit Ui. For each quantizer, the fol- lowing applies: x L Ui i�( , ) . (3) By applying more than one quantizer intervals, formula (3) becomes: x L U ii i� �(max( ), min( )), . By reducing the width of the reconstruction interval the distortion at the decoder decreases and y approximates the source sample more accurate. This decoding approach results in no quality improvement if all limits of the higher rate quantizer are also limits of the lower rate quantizer. This may happen in the case of � �i j k k� �, � , depending on the width of the quantizer deadzone. In all other cases every received quantizer index may reduce the width of the recon- struction interval for the central decoder. 3 Experimental results For low complexity, all simulations are limited to two de- scriptions and three decoders, as shown in Fig. 1. First a gaussian source with zero mean and unit-variance is used as source data for comparison of the three decoders. The two encoders are uniform scalar quantizer with different quantization intervals �i. For balanced descriptions, the two sets of quantization indices are mixed by a codec wide known scheme, e.g. the scheme used in [6]. The rate is approximated by the entropy of the indices. Cause of the high rate of 2 bpss we assume uniformly distribution of the quantization error. Results are shown in Fig. 5 and Fig. 6, along with the theo- retical limit for multiple description coding of a gaussian source as derived in [3]. Fig. 5 shows that in the case of � �2 1 2 1� � � �k n k n, , � the linear superposition method gets worse than the highest rate method. In these cases the assumption of no cross-correlation between quantization er- © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 29 Acta Polytechnica Vol. 46 No. 4/2006 Fig. 3: Source sample x with two corresponding quantization in- tervals �1, �2, quantization interval �3 results from highest rate decoding, reconstruction values y1, y2 and y3 are chosen for an uniformly distributed source Fig. 4: Source sample x with two corresponding quantization in- tervals �1, �2; quantization interval �3 results from inter- section decoding; reconstruction values y1, y2 and y3 are chosen for an uniformly distributed source rors of different descriptions does not apply. For these cases, Fig. 6 shows the same quality for highest rate and inter- section reconstruction. This is because the limits of the lower rate quantization intervals are also limits of the higher rate quantization intervals when using uniform scalar quantizer without a wider deadzone. Second, the wavelet coefficients of some commonly used test images are used as sourcedata for the MDC. Generating the two descriptions is done similar as by the gaussian source. Entropycoding is performed by the SPIHT algorithm [5]. For visualization and comparison of the efficiency of MDCs redundancy rate distortion Plots (RRD-Plots), introduced by [9], are used. The experimental results for image Lena 512×512 are shown in Figs. 7 and 8. With other test images, comparable results are achieved. As by the gaussian source Fig. 7 shows that the linear su- perposition method improves the highest rate reconstruction only for high redundancy. For a redundancy of 0.6 or less the assumption of uncorrelated quantization errors qi seems wrong. In Fig. 8, no such drawback can be seen. The intersec- tion reconstruction improves every domain based MDC, and may be even more effective for more than two descriptions, because every different quantizer results in additionally limits of quantization intervals, which can be interpreted at the cen- tral decoder. 4 Conclusions In this paper it is shown how to utilize the lower rate quantizers for reducing the distortion at the central decoder in a domain based partitioning MDC. The linear superposi- tion and the intersection method are described for N possible descriptions, so they can be used in domain based partition ing MDC systems with arbitrary number of descriptions. For the first approach, called linear superposition, less complex- ity is traded for the possibility of drawbacks. For lower redun- dancy, the assumption of negligible cross correlation between the quantization errors of the different channels may not apply. 30 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 4/2006 Fig. 5: Highest rate decoder (solid line) vs. linear superposition decoder (dotted line), gaussian source with unit-variance and zero mean, rate: 2bpss Fig. 6: Highest rate decoder (solid line) vs. intersection decoder (dotted line), gaussian source with unit-variance and zero mean, rate: 2bpss Fig. 7: Lena 512×512, highest rate decoder (solid line) vs. linear superposition decoder (dotted line), PSNR for central de- coder: 30dB Fig. 8: Lena 512×512, highest rate decoder (solid line) vs. inter- section decoder (dotted line), PSNR for central decoder: 30dB The second, more complex approach is at least as good as the highest rate reconstruction, and by proper choosing of quantization intervals, a significant reduction of the distor- tion at the central decoder is possible. Although the intersection method is better than the linear superposition method, there may be applications where the quantization intervals may not be known at the decoder, for example [2]. For such applications the linear superposition may be an improvement for an environment with need of high redundancy. Further investigations may interpret the cross correlation of the linear superposition method or study the benefits of these central decoders for more than two channels. 5 Acknowledgments The research described in the paper was supervised by Prof. J. R. Ohm, IENT, RWTH Aachen University. The author wish to thank the team of the IENT, RWTH Aachen University for assistance and help. References [1] Bajic, I. V., Woods, J. W.: Domain-based Multiple De- scription Coding of Images and Video. IEEE Transac- tions on Image Processing, Vol. 12 October 2003, No. 10, p. 1211–1225. [2] Malvar, H. S., Hallapuro, A., Karczewicz, M., Kerof- sky L.: Low-complexity Transform and Quantization in H. 264/AVC. IEEE Trans. on Circuits and Systems for Video Technology, Vol. 13, July 2003, No. 7, p. 598–603. [3] Ozarow, L.: On a Source-Coding Problem with Two Channels and Three Receivers. The Bell Systems Technical Journal, Vol. 59, December 1980, No. 10. [4] Regunathan, L., Rose, K.: Efficient Prediction in Multi- ple Description Video Coding. In: Proc. IEEE Int. Conf. Image Processing, Vol. 1 (2000), p. 1020–1023. [5] Said, A., Pearlman, W. A.: A New Fast and Efficient Im- age Codec Based on Set Partitioning in Hierachical Trees. IEEE Trans. on Circuits and Systems for Video Tech- nology, 6 June 1996. [6] Tillo, T., Baccaglini, E., Olmo, G.: A Xexible Multi-Rate Allocation Scheme for Balanced Multiple Description Coding Application. In: IEEE International Workshop on Multimedia Signal Processing,, 2005 p. 081–084. [7] Tillo, T., Olmo, G.: A Novel Multiple Description Cod- ing Scheme Compatible with the JPEG 2000 Decoder. IEEE Signal Processing Letters, Vol. 11, November 2004, p. 908–911. [8] Vaishampayan, V. A.: Design of Multiple Description Scalar Quantizers. IEEE Trans. on Information Theory, Vol. 39, May 1993, No. 3, p. 821–834. [9] Wang, Y., Orchard, M. T., Vaishampayan, V. A., Reib- man, A. R.: Multiple Description Coding Using Pairwise Correlating Transforms. IEEE Transactions on Image Pro- cessing, Vol. 10, March 2001, p. 351–366. Martin Spiertz spiertz@ient.rwth-aachen.de Dipl.-Ing. Thomas Rusert rusert@ient.rwth-aachen.de Institute of Communications Engineering RWTH Aachen University 52056 Aachen, Germany © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 31 Acta Polytechnica Vol. 46 No. 4/2006