“Quantization Design For Structured Overcomplete Expansions”

by Baltasar Beferull-Lozano

December 2002

The study of quantized overcomplete expansions is relevant to several important applications such as oversampled A/D conversion, multiple description quantization, joint source-channel coding and content-based retrieval. The problem of quantization of overcomplete (redundant) expansions is not as well understood as that of quantization of more traditional critically sampled (non-redundant) expansions. As an example, in the latter case, one can minimize the overall distortion by minimizing the distortion independently in each of the expansion coefficients. This is not true for an overcomplete expansion.

Previous work to date on quantized overcomplete expansions has assumed only simple quantization schemes and has focused on finding improved reconstruction algorithms. In our work, we study different issues related to overcomplete expansions, focusing on designing efficient quantization techniques for this type of decompositions. More specifically, the following topics are studied:(i) We propose new quantization designs for overcomplete expansions in where our approach is to design jointly the overcomplete decomposition together with the quantization scheme so that the whole system is equivalent to a regular vector quantizer in with a periodic structure which can be characterized in terms of lattice intersections.(ii) We show how the periodicity property makes it possible to achieve good accuracy with low complexity, by analyzing linear reconstruction and providing also some other low complexity reconstruction schemes.(iii) Given an intersection lattice , we provide general methods to decompose it as the intersection of simpler lattices and also give concrete decompositions for most of the best known lattices giving rise to different periodic quantizers with different tesselations.(iv) We obtain an expression for the effective normalized second moment of a periodic quantizer, which characterizes its rate-distortion performance at high rates and analyze the complete structure of the tesselations generated by some of the derived lattice decompositions evaluating the corresponding values of .(v) We analyze angular oversampling in the presence of quantization for overcomplete 2D filter banks in which are steerable under rotation. We define and make use of angular "consistency" constraints in order to increase the accuracy in the representation with the number of orientations by using Lie theory, Projection on convex sets (POCS) and Linear programming principles.(vi) We define energy-based features which are steerable under rotation and apply them to the problem of Rotation Invariance in content-based image retrieval.