An O(KN lg N) algorithm for optimum K-level quantization on histograms of N points

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(KN lg N) algorithm for optimum K-level quantization on histograms of N points

Full text

Pdf (382 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 17th conference on ACM Annual Computer Science Conference table of contents

Louisville, Kentucky

Pages: 339 - 343

Year of Publication: 1989

ISBN:0-89791-299-3

Authors

X. Wu	Department of Mathematical Sciences, University of Lethbridge, Lethbridge, Canada T1K 3M4
J. Rokne	Department of Computer Science, University of Calgary, Calgary, Canada T2N 1N4

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 8, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/75427.75472 What is a DOI?

ABSTRACT

Optimum quantization is a fundamental problem in digital signal processing and information theory. In 1964 Bruce [1] devised a polynomial-time algorithm to solve this particular non-linear programming problem using the dynamic programming technique. For the mean-square error measure and when the amplitude density function of the quantized signal is represented by a histogram of N points, Bruce's algorithm can generate the optimum K-level quantizer in O(KN2) time. This paper proposes an efficient algorithm which can do the same job with the worst-case time complexity of O(KN lg N). This is due to the discovery of some useful properties of optimum meansquare quantizers and an innovative algorithm structure combining the two algorithmic techniques, dynamic programming and divide-and-conquer. This algorithm structure contributes a new effective methodology to the design of efficient algorithms. Finally the paper outlines a more sophisticated algorithm which can reduce both the time and space complexity of the O(KN lg N) algorithm derived in the paper.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. D. Bruce, "Optimum Quantization," So. D. thesis, M.I.T., May 14, 1964.
	2	J. Max, "Quantizing for minimum distortion," IRE Trans. Inform. Theory, vol. IT-6, pp. 7-12, :Jan. 1960.
	3	Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
	4	D. K. Sharma, "Design of absolutely optimal quantizers for a wide class of distortion measures," IEEE Trans. Inform. Theory vol. IT-24, pp. 693-702, Nov. 1978.
	5	X. Wu, Algorithmic approaches to optimal meansquare quantization, Ph.D dissertation, Dept. of Computer Science, Univ. of Calgary, 1988.