On optimal multi-resolution scalar quantization

Any scalar quantizer of 2^h bins, where h is a positive integer, can be structured by a balanced binary quantizer tree T of h levels. Any pruned subtree τ of T corresponds to an operational rate R(τ) and distortion D(τ) pair. Denote by S_n the set of all pruned subtrees of n leaf nodes, 1≤n≤2^h. We consider the problem of designing a 2^h-bin scalar quantizer that minimizes the weighted average distortion D~=Σ_n=1^2(h) D(τ)W(n), where W(n) is a weighting function in the size of pruned subtrees (or the resolution of the underlying quantizer). We present an O(hN³) algorithm to solve the underlying optimization problem (N is the number of points of the histogram that represents the source probability mass function), and call the resulting quantizer optimal multi-resolution scalar quantizer in the sense that it minimizes a global distortion measure averaged over all quantization resolutions of T. Interestingly, a similar quantizer design problem studied by Brunk et al. (1996) is a special case of our formulation, and can thus be solved exactly and efficiently using our algorithm. Furthermore, we present an algorithm to generate a sequence of 2^h nested pruned subtrees of T, from the root of T to the entire tree T itself, which minimizes an expected distortion over a range of operational rates. The resulting nested pruned subtree sequence generates an optimized embedded (rate-distortion scalable) code stream with maximum granularity of 2^h quantization stages, as opposed to existing successively refinable quantizers, such as the popular bit-plane coding scheme, which offer only h stages.