A Clustering Algorithm for Entropy-Constrained Vector Quantizer Design with Applications in Coding Image Pyramids

Abstract

A clustering algorithm for the design of efficient vector quantizers to be followed by entropy coding is proposed. The algorithm, called entropy-constrained pairwise nearest neighbor (ECPNN), designs codebooks by merging the pair of Voronoi regions which gives the least increase in distortion for a given decrease in entropy. The algorithm is an entropy-constrained version of the pairwise nearest neighbor (PNN) clustering algorithm of Equitz and can be used as an alternative to the entropy constrained vector quantizer design (ECVQ) proposed by Chou, Lookabaugh, and Gray. By a natural extension of the ECPNN algorithm we develop another algorithm that designs alphabet and entropy-constrained vector quantizers and call it alphabet and entropy-constrained pairwise nearest neighbor (AECPNN) design. The AECPNN algorithm can be used as alternative to the alphabet-and entropy-constrained vector quantizer design (AECVQ) proposed by Rao and Pearlman, that is directly based on the ECVQ design algorithm. Through simulations on synthetic sources, we show that ECPNN and ECVQ have indistinguishable mean-square-error versus rate performance and that the ECPNN and AECPNN algorithms obtain as close performance by the same measure as the ECVQ and AECVQ algorithms. The advantages over ECVQ are that the ECPNN approach enables much faster codebook design and uses smaller codebooks. A single pass through the ECPNN (or AECPNN) design algorithm, which progresses from larger to successively smaller rates, allows the storage of any desired number of intermediate codebooks. In the context of multirate subband (or transform) coders, this feature is especially desirable, since the ECPNN design algorithm must be run for each subband and storage of codebooks of different rates are required for each subband (or transformed coefficients). Coding image pyramids using ECPNN and AECPNN codebooks at rates from 1/3 to 1.0 bit/pixel, achieves performance, judged both visually and using peak-to-peak SNR criterion, which is competitive with that of the best methods currently known. © 1995 IEEE