Sparse DP Quantization Algorithm

Yukihiro BANDOH  Seishi TAKAMURA  Atsushi SHIMIZU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.3   pp.553-565
Publication Date: 2019/03/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.553
Type of Manuscript: PAPER
Category: Image
quantization,  sparseness,  dynamic programming,  

Full Text: FreePDF

We formulate the design of an optimal quantizer as an optimization problem that finds the quantization indices that minimize quantization error. As a solution of the optimization problem, an approach based on dynamic programming, which is called DP quantization, is proposed. It is observed that quantized signals do not always contain all kinds of signal values which can be represented with given bit-depth. This property is called amplitude sparseness. Because quantization is the amplitude discretization of signal value, amplitude sparseness is closely related to quantizer design. Signal values with zero frequency do not impact quantization error, so there is the potential to reduce the complexity of the optimal quantizer by not computing signal values that have zero frequency. However, conventional methods for DP quantization were not designed to consider amplitude sparseness, and so fail to reduce complexity. The proposed algorithm offers a reduced complexity optimal quantizer that minimizes quantization error while addressing amplitude sparseness. Experimental results show that the proposed algorithm can achieve complexity reduction over conventional DP quantization by 82.9 to 84.2% on average.