Sequential Scalar Quantization of Two Dimensional Vectors in Polar and Cartesian Coordinates

Abstract

This thesis addresses the design of quantizers for two-dimensional vectors, where the scalar components are quantized sequentially. Specifically, design algorithms for unrestricted polar quantizers (UPQ) and successively refinable UPQs (SRUPQ) for vectors in polar coordinates are proposed. Additionally, algorithms for the design of sequential scalar quantizers (SSQ) for vectors with correlated components in Cartesian coordinates are devised. Both the entropy-constrained (EC) and fixed-rate (FR) cases are investigated.

The proposed UPQ and SRUPQ design algorithms are developed for continuous bivariate sources with circularly symmetric densities. They are globally optimal for the class of UPQs/SRUPQs with magnitude thresholds confined to a finite set. The time complexity for the UPQ design is $O(K^2 + KP_{max})$ in the EC case, respectively $O(KN^2)$ in the FR case, where $K$ is the size of the set from which the magnitude thresholds are selected, $P_{max}$ is an upper bound for the number of phase levels corresponding to a magnitude bin, and $N$ is the total number of quantization bins. The time complexity of the SRUPQ design is $O(K^3P_{max})$ in the EC case, respectively $O(K^2N^{'2}P_{max})$ in the FR case, where $N'$ denotes the ratio between the number of bins of the fine UPQ and the coarse UPQ.

The SSQ design is considered for finite-alphabet correlated sources. The proposed algorithms are globally optimal for the class of SSQs with convex cells, i.e, where each quantizer cell is the intersection of the source alphabet with an interval of the real line. The time complexity for both EC and FR cases amounts to $O(K_1^2K_2^2)$, where $K_1$ and $K_2$ are the respective sizes of the two source alphabets. It is also proved that, by applying the proposed SSQ algorithms to finite, uniform discretizations of correlated sources with continuous joint probability density function, the performance approaches that of the optimal SSQs with convex cells for the original sources as the accuracy of the discretization increases.

The proposed algorithms generally rely on solving the minimum-weight path (MWP) problem in the EC case, respectively the length-constrained MWP problem or a related problem in the FR case, in a weighted directed acyclic graph (WDAG) specific to each problem. Additional computations are needed in order to evaluate the edge weights in this WDAG. In particular, in the EC-SRUPQ case, this additional work includes solving the MWP problem between multiple node pairs in some other WDAG. In the EC-SSQ (respectively, FR-SSQ) case, the additional computations consist of solving the MWP (respectively, length-constrained MWP) problem for a series of other WDAGs.