摘要: Abstract Optimal quantization, a fundamental problem in source coding and information theory, can be formulated as discrete optimization problem. In 1964 Bruce (“Optimum Quantization,” Sc.D. thesis, MIT, May 1964) devised dynamic programming algorithm for optimal quantization. For the mean-square error measure when amplitude density function of quantized signal is represented by histogram N points, Bruce's compute K-level quantizer O(KN2) time. This paper shows that same solved O(KN) The improvement made better understanding objective this particular non-linear use Aggarwal et al.'s matrix-searching technique.
elsevier.com
sci-hub.se 参考文章(7)
X. Wu, Optimal bi-level quantization and its application to multilevel quantization IEEE Transactions on Information Theory. ,vol. 37, pp. 160- 163 ,(1991) , 10.1109/18.61117
James E. Boyce, David P. Dobkin, Robert L. (Scot) Drysdale III, Leo J. Guibas, Finding extremal polygons SIAM Journal on Computing. ,vol. 14, pp. 134- 147 ,(1985) , 10.1137/0214011
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
X. Wu, J. Rokne, An O(KN lg N) algorithm for optimum K-level quantization on histograms of N points Proceedings of the seventeenth annual ACM conference on Computer science : Computing trends in the 1990's Computing trends in the 1990's - CSC '89. pp. 339- 343 ,(1989) , 10.1145/75427.75472
Xiaolin Wu, Fast approximations to discrete optimal quantization Information Processing Letters. ,vol. 31, pp. 175- 179 ,(1989) , 10.1016/0020-0190(89)90119-1
D. Sharma, Design of absolutely optimal quantizers for a wide class of distortion measures IEEE Transactions on Information Theory. ,vol. 24, pp. 693- 702 ,(1978) , 10.1109/TIT.1978.1055961
J. Max, Quantizing for minimum distortion IEEE Transactions on Information Theory. ,vol. 6, pp. 7- 12 ,(1960) , 10.1109/TIT.1960.1057548