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 $\tau$ of $T$ corresponds to an operational rate $R(\tau)$ and distortion $D(\tau)$ pair. Denote by $S_{n}$ the set of all pruned subtrees of n leaf nodes, $1\leq n\leq 2^{h}$. We consider the problem of designing a $2^{h}$-bin scalar quantizer that minimizes the weighted average distortion $\overline{D}=\sum_{n=1}^{2^{h}}\sum_{\tau\in S_{n}}D(\tau)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^{3})$ 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 $\mathrm{OV}$ er all quartization resolutions of $T$. In terestingly a similar quantizer design problem studied by Brunk et al. [1] is a special case of our formulation, and can th us 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 en tire 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.