(PDF) Multiple description vector quantizer design based on redundant representation of central code

2016 24th European Signal Processing Conference (EUSIPCO) Multiple Description Vector Quantizer Design Based on Redundant Representation of Central Code Akinori Ito Graduate School of Engineering Tohoku University Sendai, Miyagi 980-8579 Japan Email:

Abstract—A design method of a multiple description vector receiver side, if the two descriptions are received, they are quantizer (VQ) is proposed. VQ is widely used for data com- decoded at the central decoder and a high-quality signal is pression, transmission and other processing. Here, we assume obtained. When only a part of the descriptions is received, the transmission channels with data erasure such as a packet-based network. Multiple description coding is a coding method used received description is decoded by the side decoder, and the to achieve “graceful degradation” when transmitting signals decoded signal is degraded, but it is better than nothing. through lossy channels. The proposed method is inspired by Many MDC methods have been proposed so far. Time series the vector quantizer design of Poggi et al., which combines data such as speech signal can be divided using pairs of two VQ design based on the self-organizing map (SOM) and the contiguous samples [8]–[11]. As a more general method, the multiple description scalar quantizer (MDSQ). The method also uses the SOM-based VQ; the difference is that the proposed MD scalar quantizer (MDSQ) [12] splits one scalar value into method combines a bit-error-tolerant VQ designed by SOM and two descriptions. As the MDSQ does not need any assumption a novel scheme for cell arrangement of SOM based on Redundant about the distribution of the value to be split, it can be used Representation of Central Code (RRCC). The method is not only for any data. easy to design for any bit rate but is also more robust against When we want to encode a vector, a vector quantizer (VQ) data erasure compared with the conventional VQ. is used because of its optimality compared with the scalar quantizer. Several methods to combine VQ and MDC have I. I NTRODUCTION been proposed such as lattice MDVQ [13] or SOM-based For digital communication, packet-based networks such as MDVQ [14]. The proposed method is an improvement of the the Internet are often used. In a network based on the Internet SOM-based MDVQ, which has the problem that it is difficult Protocol (IP) [1], sent data packets are eventually lost because to design the index assignment matrix (IAM). The design of bit errors introduced in the transmission channel or conges- of IAM greatly affects the performance of the quantizer, but tion. To recover the lost packet, methods of retransmitting the there is no fixed methodology that enables the quantizer to be packets are often used such as transmission control protocol designed automatically. (TCP) [2]. However, sometimes packet retransmission is not This paper proposes a new design method of MDVQ. The appropriate or is even impossible for real-time or multicast ap- key point of the method is to assign redundant bit sequences plication. In this case, various error correction coding methods to the code vectors of the quantizer, which enables the erased are commonly used such as Reed-Solomon code [3], Turbo code to be estimated when one of the descriptions is lost on code [4], LDPC code [5], etc. These error correction codes the channel. completely recover the original data when the loss rate is under II. C ONVENTIONAL MDSQ AND MDVQ a certain threshold. However, if more losses than the threshold are introduced, almost all of thje data in the packets are lost. A. MDSQ When the data to be protected are multimedia signals MDSQ is a method to split a scalar value into two descrip- such as image, video or audio signals, complete bit-by-bit tions, while the total rate of the descriptions is less than twice recovery is not always necessary. Packet loss concealment the rate of the original value. Figure 1 shows an example of [6], [7] is based on the assumption that the quality of the an index assignment matrix (IAM) when splitting a three-bit recovered signal can be degraded from the original signal value into two two-bit codes. For example, if we want to send if the degradation is sufficiently small. Multiple description the original value of 3, we send “10” and “01” to channel coding (MDC) is a channel coding scheme used in such a A and channel B, respectively. When both of the descriptions situation, where slight degradation is permitted for a digital are received, the original code can be recovered at the receiver communication channel with erasure. side using the same IAM. When the description of channel A MDC is a channel coding method that splits the original is lost, we receive only “01” from channel B. In this case, signal into two or more bitstreams. The MD encoder encodes we know that the original value should be either 2 or 3. If the the input signal into two (or more) descriptions, and the prior probability distribution of the original value is known, the descriptions are sent to the destination independently. At the most probable value among the possibilities (2 or 3) is chosen. 978-0-9928-6265-7/16/$31.00 ©2016 IEEE 106 2016 24th European Signal Processing Conference (EUSIPCO) Side channel A 00 01 10 11 00 0 1 01 2 3 Side channel 10 4 5 B 11 6 7 Fig. 1. An example of IAM of the MDSQ If the distribution is uniform, the value is chosen randomly. Fig. 2. Arrangement of SOM cells rk according to the IAM Although the IAM determines the bit rate, robustness against erasure and distortion, the design methodology of IAM is not Poggi’s method uses the property of SOM, and arranges rk completely established [12]. according to the IAM used for an MDSQ. Figure 2 shows B. Lattice-based MDVQ by Vaishampayan examples of the arrangement of cells. As shown, the cells are The multiple description vector quantizer (MDVQ) is an arranged in the same way as the values in the IAM shown MDC for VQ that encodes one vector into two or more in Fig. 1. When the code vectors are trained using this cell vectors. The lattice-based MDVQ proposed by Vaishampayan arrangement, we can expect that the cells that are near in the [13] quantizes the input vector into a point of the regularly cell space also have code vectors that are near in the vector arranged lattice. Among the lattice points, coarse lattice points space. At the same time, we can assign two codes to a cell in (sub-lattice) are defined. Using the lattice-MDVQ, any point exactly the same way as that in MDSQ. The decoding method of the lattice can be associated with two sub-lattice points is also the same as those of MDSQ; the only difference is that uniquely, and the sub-lattice points are located relatively near the MDVQ outputs the code vector assigned to the cell instead to the original lattice point. Thus we send two numbers of the of outputting the cell number. sub-lattice points instead of sending the number of the lattice The problems of this method are almost the same as those point. If the two sub-lattice points are received, we can recover of MDSQ. It is difficult to design the cell arrangement (which the original lattice point. When only one sub-lattice point is corresponds to an IAM), especially when the bit length of the received, that sub-lattice point is used as the received data. code is large. Another problem is that there is no theoretical This method can be used for any multidimensional vectors, background on how to choose the cell among the possible cells but the lattice cannot be designed from the distribution of the when one description is lost. data to be coded. Another difficulty with this method is that, III. P ROPOSED M ETHOD while theoretically possible, it is not easy to design a sub- A. Overview lattice for any lattice. The proposed MDVQ is basically similar to the MDVQ C. SOM-based MDVQ by Poggi et al. by Poggi et al., where SOM is used to design code vectors Poggi et al. proposed an MDVQ using the self-organizing and cells are arranged according to the descriptions sent to map (SOM) [14]. Poggi’s method consists of two components; two channels. The difference is that a bit pattern is assigned one is to design the cell arrangement using a similar strategy in addition to the cell number to a cell, which determines as MDSQ, and the other is to train the code vectors using the cell arrangement and multiple descriptions simultaneously. SOM. This bit pattern is called “Redundant Representation of Central SOM [15] is a kind of neural network that simulates the Code (RRCC).” An overview of the proposed method is as topographic map in the central nervous system. From an follows. Here, we only consider a two-channel case, but it is engineering point of view, SOM is regarded as a clustering not difficult to extend the proposed method to the case of three algorithm where some kind of order is introduced among the or more channels. code vectors. 1) Each cell has an RRCC in addition to the cell number (k In SOM, we use “cells” instead of “codes” of the ordinary of rk ). When the length of a description sent to one of VQ. The k-th cell has a coordinate in the cell space rk and a two channels is B bits, the length of the RRCC becomes weight vector (which is the same as a code vector) mk in the 2B bits. same space as the input vector. When training data x1 , . . . , xN 2) Arrange the cells rk at the vertices of a 2B-dimensional are given, SOM determines the arrangement of the weight hypercube so that the distance between two cells is vectors so that the quantization error becomes smaller and related to the Hamming distance between two RRCCs the correlation between ||rj − rk || and ||mj − mk || becomes of the cells. larger. The arrangement of rk is usually given at the beginning 3) Train code vectors using SOM. of training and does not change during training. Using SOM, 4) In the encoding phase, when a vector is given, choose the we can design VQ so that code vectors xi and xj are near nearest code vector, and determine the two descriptions when ri and rj are near. based on the corresponding RRCC. 107 2016 24th European Signal Processing Conference (EUSIPCO) 000 001 011 010 110 111 101 100 000 000000 000001 000010 000100 B=2 B=3 14 001 001000 001001 001011 001101 B=4 011 011001 011011 011010 011111 010 010000 010011 010010 010110 12 110 110010 110110 110111 110100 111 111011 111110 111111 111101 10 101 101001 101111 101101 101100 SNR(dB) 100 100000 100110 100101 100100 8 Fig. 3. An example of RRCCs for three-bit side decoders 6 5) In the decoding phase, when the two descriptions are 4 received at the receiver side, the RRCC is recovered by concatenating the two descriptions and the corre- 0 5 10 15 20 sponding code vector is output. When one description Erasure rate (%) is lost, the RRCC is estimated by repeating the received description twice, and the corresponding code vector is Fig. 4. SNR of the proposed vector quantizer output. The details of the method are explained below. example, assume that B = 2 and the original RRCC is 0100. B. Designing RRCCs Here, the first half 01 and the second half 00 are sent to the receiver using different channels. When we only receive the First, the method of designing RRCCs is described. Let the first description 01, we estimate the RRCC to be 0101. bit length of a description sent to one channel be B. Here, the 1 2 1 Consider an RRCC BR = BR .BR where BR = b1 . . . bB , description is an integer 0 ≤ c < 2B . Let b(x, B) be a B-bit 2 BR = bB+1 . . . b2B . From the definition of RRCC, it is assured representation of integer x, and b1 .b2 be the concatenation of 1 2 that DH (BR , BR ) ≤ 1. Thus, when we estimate RRCC as two bit sequences. Then the set of RRCC R is determined as 0 1 1 BR = BR .BR , follows. 0 1 2 1 1 1) b(c, B).b(c, B) ∈ R for 0 ≤ c < 2B DH (BR , BR ) = DH (BR .BR , BR .BR ) (1) 2) b(c, B).b(c0 , b) ∈ R when DH (b(c, B), b(c0 , B)) = 1 for 2 1 = DH (BR , BR ) ≤ 1 0 ≤ c, c0 < 2B 0 2 2 Here, DH (b, b0 ) is the Hamming distance between two equal- and the same result holds for BR = BR .BR . We trained length bit patterns. The property of RRCC assures that the the code vectors so that code vectors associated with similar Hamming distance between the first half and the second half RRCCs are located at nearby positions, so we expect the code of an RRCC is at most one. Figure 3 shows an example of vector recovered from the estimated RRCC to be similar to RRCCs for B = 3, where the row and column are the codes the original one. sent to the two channels. The bit patterns in the table represent The advantage of the proposed method is that we can design RRCCs. Here, we can transmit one of 64 codes (5 bits) by the quantizer automatically; we do not need to design the IAM, sending 3 + 3 = 6 bits using both channels. and we can design the quantizer for any bit length of the code. A drawback of the method is that the number of code vectors C. Training code vectors using SOM is fixed when we determine the bit length of the description. After designing RRCCs, code vectors are trained using The number of code vectors (and the number of RRCCs) is SOM. The key point is to arrange a cell at the coordinate (B + 1)2B , which means that RRCCs become sparse when B determined from the corresponding RRCC. When an RRCC is is large. a 2B-bit pattern b1 . . . b2B , the coordinate of the corresponding IV. E XPERIMENT cell is rk = (b1 , . . . , b2B ). We can arrange the code vectors so that two cells with similar RRCCs also have similar code Simulation experiments were conducted to compare the vectors. This kind of VQ, which has tolerance against bit errors proposed method with conventional vector quantizers. The introduced in the transmission channel, is called “channel- input vectors had two-dimensions, where each dimension optimized VQ” [16], [17]. A channel-optimized VQ using obeys N (0, 1) independently. 1000 training samples and 1000 SOM was proposed by de Bodt et al. [18], and our method of test samples were used. The batch SOM algorithm was used training the code vectors is a variant of de Bodt’s method. for training the SOM, and the number of iteration was 30. When testing, discriptions were randomly lost according to the D. Decoding erasure rate. When one description was lost, we estimated the When we receive two descriptions at the receiver side, RRCC using the above-mentioned method. If two descriptions we can recover the original RRCC by concatenating the were lost, we just used a fixed code vector. We conducted the two descriptions. When one of the two descriptions is lost, same experiment 10 times with different random seeds, and RRCC is estimated by repeating the received description. For the results were averaged. 108 2016 24th European Signal Processing Conference (EUSIPCO) method has a higher SNR than the conventional method. When the number of code vectors was 8 in the conventional method, degradation upon increasing the erasure rate was small, but the 15 Proposed B=2 Proposed B=3 K−means 4bit total SNR was low; when the number was 12, SNR under no K−means 6bit erasure was almost the same as that of the proposed method, but SNR fell rapidly when the erasure rate increased. 10 V. C ONCLUSION SNR(dB) In this paper, a new MDVQ design methodology was proposed. The proposed method was inspired by the SOM- 5 based MDVQ, but we do not need to design the IAM. A new concept, RRCC, was introduced in the training process. A channel-optimized VQ based on SOM was used to train 0 the code vectors. Simulation experiments revealed that the 0 5 10 15 20 proposed method was more robust than the conventional VQ Erasure rate (%) and MDVQ. Fig. 5. SNR of the proposed vector quantizer and k-means vector quantizer R EFERENCES [1] E. J. Postel, “Internet protocol,” RFC791, 1981. [2] ——, “Transmission control protocol,” RFC793, 1981. [3] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” J. Soc. for Industrial and Applied Mathematics, vol. 8, no. 2, pp. 300– 304, 1960. 9 Proposed (B=2) Poggi (n=8) [4] C. Berrou and A. Glavieux, “Near optimum error correcting coding and Poggi (n=12) decoding: turbo-codes,” IEEE Trans. Communication, vol. 44, no. 10, 8 pp. 1261–1271, 1996. [5] M. C. Davey and D. J. C. MacKay, “Low density parity check codes 7 over gf (q),” in Proc. Information Theory Workshop, 1998, pp. 70–71. [6] C. Perkins, O. Hodson, and V. Hardman, “A survey of packet loss SNR(dB) 6 recovery techniques for streaming audio,” IEEE Network, vol. 12, no. 5, pp. 40–48, 1998. 5 [7] B. Wah, X. Su, and D. Lin, “A survey of error-concealment schemes for real-time audio and video transmissions over the Internet,” in Proc. 4 Int. Symp. on Multimedia Software Engineering, 2000, pp. 17–24. [8] W. Jiang and A. Ortega, “Multiple description speech coding for robust 3 communication over lossy packet networks,” in IEEE Int. Conf. on Multimedia and Expo, 2000, pp. 444–447. 2 [9] V. K. Goyal and J. Kovačević, “Generalized multiple description coding 0 5 10 15 20 with correlating transform,” IEEE Trans. Inf. Theory, vol. 47, no. 6, pp. 2199–2224, 2001. Erasure rate(%) [10] A. Ito and S. Makino, “Multiple description coding of an audio stream Fig. 6. SNR of the proposed vector quantizer and Poggi’s vector quantizer by optimum recovery transforms,” Journal of Digital Information Man- agement, vol. 6, pp. 189–195, 2008. [11] ——, “Designing side information of multiple description coding,” Journal of Information Hiding and Multimedia Signal Processing, vol. 1, Figure 4 shows the result of the proposed method for no. 1, pp. 10–19, 2010. different values of B. The x-axis is the erasure rate. In all [12] V. A. Vaishampayan, “Design of multiple description scalar quantizers,” IEEE Trans. Inform. Theory, vol. 39, pp. 821–834, 1993. cases, the degradation of SNR at an erasure rate of 10 % was [13] V. A. Vaishampayan and N. Sloane, “Multiple-description vector quan- around 5 dB. tization with lattice codebooks: design and analysis,” IEEE Trans. Inf. Figure 5 compares the results of the proposed method and Theory, vol. 47, no. 5, pp. 1718–1734, 2001. [14] G. Poggi, D. Cozzolino, and L. Verdoliva, “Self-organizing maps for the the k-means method, the most popular method for designing design of multiple description vector quantizers,” Neurocomputing, vol. an ordinary VQ. In this experiment, the total rate was set to be 122, pp. 298–309, 2013. the same. We can see that, when no errors were introduced, the [15] T. Kohonen, “The self-organized map,” Proc. IEEE, vol. 78, no. 9, pp. 1464–1480, 1990. k-means method outperformed the proposed method. However, [16] N. Farvardin, “A study of vector quantization for noisy channels,” IEEE for an erasure rate of 1 %, the proposed method showed higher Trans. Information Theory, vol. 36, no. 4, pp. 799–809, 1990. SNR. [17] X. Yu, H. Wang, and E.-H. Yang, “Design and analysis of optimal noisy channel quantization with random index assignment,” IEEE Trans. Next, we compared the proposed method with the SOM- Information Theory, vol. 56, no. 11, pp. 5796–5804, 2010. based MDVQ proposed by Poggi et al. [14]. In this exper- [18] E. de Bodt, M. Cottrell, P. Letremy, and M. Verleysen, “On the use of iment, B was set to 2. We used the two cell arrangements self-organizing maps to accelerate vector quantization,” Neurocomput- ing, pp. 187–203, 2004. shown in Fig. 2, where the numbers of code vectors were 8 and 12. The number of code vectors of the proposed method was 12. Figure 6 shows the result, revealing that the proposed 109