Complexity Reduction of Multi-Level DP Quantization Through Inter-Level Redundancy Elimination

• Main Authors: Bandoh, Yukihiro, Takamura, Seishi, Shimizu, Atsushi
• Format: Conference Proceeding
• Language: English
• Subjects: bit-depth scalability; Complexity theory; Dynamic programming; Heuristic algorithms; Histograms; Indexes; multi-layered structure; Optimization; quantization; Quantization (signal)
• ISSN: 2381-8549
• DOI: 10.1109/ICIP.2019.8803433

Designing an optimum quantizer can be treated as the optimization problem of finding the quantization indices that minimize the quantization error. One solution to the optimization problem, DP quantization, is based on dynamic programming. Some applications, such as bit-depth scalable codec and tone mapping, require the construction of multiple quantizers with different quantization levels, for example, from 12bit/channel to 10bit/channel and 8bit/channel. Unfortunately, conventional DP quantization optimizes the quantizer for just one quantization level. That is, it is unable to simultaneously optimize multiple quantizers. Therefore, when DP quantization is used to design multiple quantizers, there are many redundant computations in the optimization process. This paper proposes an extended DP quantization with a complexity reduction algorithm for the optimal design of multiple quantizers. Experiments show that the proposed algorithm reduces complexity by 20.3%, on average, compared to conventional DP quantization.