A Posteriori Quantization of Progressive Matching Pursuit Streams
This paper proposes a rate-distortion optimal a posteriori quantization scheme for Matching Pursuit coefficients. The a posteriori quantization applies to a Matching Pursuit expansion that has been generated off-line, and cannot benefit of any feedback loop to the encoder in order to compensate for the quantization noise. The redundancy of the Matching Pursuit 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 sub-optimal 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, very easy to transcode and adapt to changing rate constraints.