Optimal Two-Description Scalar Quantizer Design
作者： Sorina Dumitrescu , Xiaolin Wu
DOI: 10.1007/S00453-004-1126-X
关键词: Quantization (signal processing) 、 Random variable 、 Mathematics 、 Signal compression 、 Discrete mathematics 、 Directed acyclic graph 、 Combinatorics 、 Directed graph 、 Shortest path problem 、 Regular polygon 、 Theory of computation
摘要: Multiple description quantization is a signal compression technique for robust networked multimedia communication. In this paper we consider the problem of optimally quantizing random variable into two descriptions, with each being produced by side quantizer convex codecells. The optimization objective to minimize expected distortion given probabilities receiving either and both descriptions. formulated as one shortest path in weighted directed acyclic graph constraints on number types edges. An $O(K_1K_2N^3)$ time algorithm designing optimal two-description presented, where $N$ cardinality source alphabet, $K_1$, $K_2$ are codewords quantizers, respectively. This complexity reduced $O(K_1K_2N^2)$ exploiting Monge property function. Furthermore, if $K_1 = K_2 K$ descriptions transmitted through channels same statistics, then design can be solved $O(KN^2)$ time.
springer.com
sci-hub.se 参考文章(10)
Alberto Apostolico, Zvi Galil, Pattern matching algorithms Oxford University Press. ,(1997)
M. Fleming, Q. Zhao, M. Effros, Network vector quantization IEEE Transactions on Information Theory. ,vol. 50, pp. 1584- 1604 ,(2004) , 10.1109/TIT.2004.831832
Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, Robert Wilber, Geometric applications of a matrix-searching algorithm Algorithmica. ,vol. 2, pp. 195- 208 ,(1987) , 10.1007/BF01840359
V.A. Vaishampayan, Design of multiple description scalar quantizers IEEE Transactions on Information Theory. ,vol. 39, pp. 821- 834 ,(1993) , 10.1109/18.256491
D. Rebollo-Monedero, Rui Zhang, B. Girod, Design of optimal quantizers for distributed source coding data compression conference. pp. 13- 22 ,(2003) , 10.1109/DCC.2003.1193992
Sorina Dumitrescu, Xiaolin Wu, Algorithms for optimal multi-resolution quantization Journal of Algorithms. ,vol. 50, pp. 1- 22 ,(2004) , 10.1016/S0196-6774(03)00099-3
Dan Muresan, Michelle Effros, Quantization as Histogram Segmentation: Optimal Scalar Quantizer Design in Network Systems IEEE Transactions on Information Theory. ,vol. 54, pp. 344- 366 ,(2008) , 10.1109/TIT.2007.911170
C. Tian, S.S. Hemami, Universal multiple description scalar quantization: analysis and design IEEE Transactions on Information Theory. ,vol. 50, pp. 2089- 2102 ,(2004) , 10.1109/TIT.2004.833344
X. Wu, K. Zhang, Quantizer monotonicities and globally optimal scalar quantizer design IEEE Transactions on Information Theory. ,vol. 39, pp. 1049- 1053 ,(1993) , 10.1109/18.256513
D. Muresan, M. Effros, Quantization as histogram segmentation: globally optimal scalar quantizer design in network systems data compression conference. pp. 302- 311 ,(2002) , 10.1109/DCC.2002.999968