Optimal Design of a Two-Stage Wyner-Ziv Scalar Quantizer With Forwardly/Reversely Degraded Side Information

This paper addresses the optimal design of a two-stage Wyner-Ziv scalar quantizer with forwardly or reversely degraded side information (SI) for finite-alphabet sources and SI. We assume that the binning is performed optimally and address the design of the quantizer partitions. The optimization problem is formulated as the minimization of a weighted sum of distortions and rates. The proposed solution is globally optimal when the cells in each partition are contiguous. The solution algorithm is based on solving the single-source or the all-pairs minimum-weight path (MWP) problem in certain weighted directed acyclic graphs. When the conventional dynamic programming technique is used to solve the underlying MWP problems, the time complexity achieved is O(N
³
), where N is the size of the source alphabet. A so-called partial Monge property is additionally introduced, and a faster solution algorithm exploiting this property is proposed. Experimental results assess the practical performance of the proposed scheme.