An efficient Lloyd-Max quantizer for Matching Pursuit decompositions

Several applications are using the matching pursuit algorithm for signal and video compression. The matching pursuit approximates signals iteratively using linear combinations of pre-defined atoms of a dictionary. In compression applications matching pursuits coefficients, which multiply the atoms in the linear combination, need to be quantized. The Lloyd-Max quantizer is known to be the best quantizer for a given source. However, to design a Lloyd-Max quantizer the statistics of the source need to be known. The statistics of matching pursuit coefficients are difficult to model. In this paper, starting from the observation that the statistics of the angles between the residues and the atoms present little variation along matching pursuit iterations, we propose to use these statistics to model the ones of matching pursuit coefficients. This permits the design of Lloyd-Max quantizers for matching pursuit coefficients. The Lloyd-Max quantize is compared to a state-of-the-art off-loop matching pursuit quantization scheme. Results show that the proposed scheme has good rate-distortion performance, specially at low rates.