ENTROPY-CONSTRAINED TREE-STRUCTURED VECTOR QUANTIZER DESIGN

Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the Generalized Breiman-Friedman-Olshen-Sto ne (GBFOS) algorithm are effective, but suffer from several shortcomin gs. We identify and clarify issues of suboptimality including greedy g rowing, the suboptimal encoding rule, and the need for time sharing be tween quantizers to achieve arbitrary rates, We then present the leaf- optimal tree design (LOTD) method which, with a modest increase in des ign complexity, alters and reoptimizes tree structures obtained from c onventional procedures. There are two main advantages over existing me thods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show t hat performance improvement is theoretically guaranteed. Simulation re sults for image coding demonstrate that close to 1 dB reduction of dis tortion for a given rate can be achieved by this technique relative to the GBFOS method.