A posteriori quantization of progressive matching pursuit streams

This paper proposes a rate-distortion optimal a posteriori quantization scheme for matching pursuit (MP) coefficients. The a posteriori quantization applies to an MP expansion that has been generated offline and cannot benefit of any feedback loop to the encoder in order to compensate for the quantization noise. The redundancy of the MP dictionary provides an indicator of the relative importance of coefficients and atom indices and, subsequently, on the quantization error. It is used to define a universal upper bound on the decay of the coefficients, sorted in decreasing order of magnitude. A new quantization scheme is then derived, where this bound is used as an Oracle for the design of an optimal a posteriori quantizer. The latter turns the exponentially distributed coefficient entropy-constrained quantization problem into a simple uniform quantization problem. Using simulations with random dictionaries, we show that the proposed exponentially upper bounded quantization (EUQ) clearly outperforms classical schemes. Stepping on the ideal Oracle-based approach, a suboptimal adaptive scheme is then designed that approximates the EUQ but still outperforms competing quantization methods in terms of rate-distortion characteristics. Finally, the proposed quantization method is studied in the context of image coding. It performs similarly to state-of-the-art coding methods (and even better at low rates) while interestingly providing a progressive stream that is very easy to transcode and adapt to changing rate constraints.