An Efficient Algorithm for Optimal Tree Pruning with Application to VQ
Xiaolin Wu * Yonggang Fang t A vector space can be recursively partitioned into k convex regions with k 1 cutting halfphnes. Such a k-partition can be embedded into a binary tree of k leave$,. This tree data structure was independently developed by researcherr) in VQ [6], pattern classification [I], databases [3] and computer graphics [4]. It was given different names in different research communities: quantizer tree, classification tree, k-d tree, and binary spatial partitioning (BSP) tree. In this abstract, we will use the term BSP tree. Each leaf of the BSP tree corresponds to a resulting convex region of the k-partition, and each internal node of the tree and its two sons correslpond to a bipartition by a cutting halfplane. The BSP tree has a wide range of applications: source coding, pattern recognition, artificial intelligence, computer graphics, etc. However, for clarity and relevancy to the information theory symposium, we will study the problem in the framework of VQ. The results apply to other applications straightforwardly. A tree-structured vector quantizer (TSVQ) has two attractive advantages: low design complexity and low decoding complexity compared with its unstructured counterparts. However, these computational advantages are gained at the expense of codebook optimality. Namely, the k-partition embedded into the BSP tree is not, in general, a Voronoi diagram on the k centroids. Two avenues were opened to improve the performance of TSVQ: 1) adaptive partitioning strategy and 2) optimal tree pruning. When growing the spatial partitioning tree we can optimize the cutting halfplanes one at a time by principal analysis 191, or optimize several cutting halfplanes together by dynamic programming as proposed by Wu [lo], and/or elaborate on the order of tree growth using a look-ahead scheme as suggested by Riskin and Gray [7], and Wu and Zhang [9], rather than blind recursion. To further improve the performance of TSVQ, one can generate an initial BSP tree of larger size and then optimally prun it back to the required size. The first work on pruned TSVQ was due to Chou et al. [2], which was developed from an earlier work by Breiman et al. [l] on classification trees. The pruning of a BSP tree is an optimization problem of minimizing some objective function (say, quantization distortion) under certain constraints (e.g., the size or the expected height of the tree, the entropy of the leaves, etc.). The algorithm of [2] can find points on the convex hull of the objective function. However, given an arbitrary constraint value, this algorithm can only obtain the minimum through time sharing. Recently, ILin et al. [8] showed that optimally pruning an n-node initial tree to a I;-node tree to minimize the total quantization distortion can be effected in O(nk) time without time sharing. In this research we found that the expected execution time of Lin et al.’s algorithm can be reduced from O(n2) to O(n1ogn) if O ( n ) = O ( k ) (a common case in practice). We observed that the mechanic bottomup testing in the search for the optimal subtree as conducted by the algorithm of [SI was often unnecessary and wasteful. Decisions can be made at a much earlier stage as to which subtrees can never be part of the final optimal k-node tree and which top portion of the initial BSP tree must stay in the final optimal k-node tree. Consequently, the search domain, and hence the algorithm execution time is drastically reduced. Let E(*) be the quantization distortion of the quantizer cell corresponding to a BSP tree node o. Then for each internal node v,