The design of vector quantizers (VQ) involves the partitioning of a mu
ltidimensional space into a finite number of regions. It is desired bu
t generally difficult to find the partition that minimizes the expecte
d distortion subject to a cost constraint. Tree-structured vector quan
tization (TSVQ) reduces the complexity by imposing a hierarchical stru
cture on the partitioning. We study the design of optimal tree-structu
red vector quantizers that minimize the expected distortion subject to
cost functions related to storage cost, encoding rate, or quantizatio
n time. The optimal design problem is shown to be intractable in most
cases, and heuristic techniques have to be used. We analyze the perfor
mance of a general design heuristic based on successive partitioning,
and propose a recursively descend optimization criterion for the algor
ithm. Experimental results in image compression show the new criterion
performs favorably compared with existing ones.