Design of absolutely optimal quantizers for a wide class of distortion measures (1978)

In this paper designs of two types of quantizers are presented. The first type is designed to minimize a distortion measure under the constraint that the number of levels is fixed or the entropy of the output signal is bounded below a given value. The distortion measure is defined as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E[f(x,\eta)]</tex> , the expected value of an error weighting function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(x, \eta)</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> is the quantizer input and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\eta</tex> is the corresponding quantization error. This paper departs from the quautization work reported in the literature heretofore in allowing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</tex> to be a function of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> as well as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\eta</tex> . Algorithms to minimize such a distortion measure ander the constraints mentioned above are presented. They use a combination of dynamic programming and Fibonacci search. It is shown that if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(x,\eta)</tex> is semiconvex in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\eta</tex> for all fixed values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> , Fibonacci search can be used in one of the steps of the minimization algorithm. This reduces the number of multiplications by a factor of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M/(5 \log M)</tex> when the range of input values is divided into <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</tex> parts. Some examples are considered. The first deals with an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(x,\eta)</tex> which is zero if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\eta</tex> is below a certain threshold <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T(x)</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\eta_{2}-T_{2}(x)</tex> otherwise. It arises in coding video signals by differential pulse-code modulation (PCM). The second deals with the minimum mean-square quantization of a truncated Laplacian input density. The step sizes of the near-optimal uniform quantizers are obtained under varions entropy constraints. The third example shows that the optimal quantizer can be asymmetric, even when the probability density and the error weighting function are symmetric. The second type of quantizer is designed to minimize the number of levels or the output entropy, when the quantization error is constrained not to exceed a threshold function. Methods to design them are presented that involve, respectively, a geometric construction and a dynamic programming algorithm in which the domain of search is modified according to the constraint mentioned above.