The University of British Columbia

A clustering algorithm based on the pairwise nearest-neighbor algorithm developed by Equitz, is introduced for the design of entropy-constrained residual vector quantizers. The algorithm designs residual vector quantization codebooks by merging the pair of stage clusters that minimizes the increase in overall distortion subject to a given decrease in entropy. Image coding experiments show that the clustering design algorithm typically results in more than a 200:1 reduction in design time relative to the standard iterative entropy-constrained residual vector quantization algorithm while introducing only small additional distortion. Multipath searching over the sequence of merges is also investigated and shown experimentally to slightly improve rate-distortion performance, The proposed algorithm can be used alone or can be followed by the iterative algorithm to improve the reproduction quality at the same bit rate.