A clustering algorithm for entropy-constrained vector quantizer design with applications in coding image pyramids

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems for video technology 1995-04, Vol.5 (2), p.83-95
Main Authors: de Garrido, D.P., Pearlman, W.A., Finamore, W.A.
Format: Article
Language:English
Subjects:
Acoustic materials
Algorithm design and analysis
Applied sciences
Clustering algorithms
Decoding
Entropy coding
Exact sciences and technology
Image coding
Image processing
Information, signal and communications theory
Merging
Nearest neighbor searches
Signal processing
Signal processing algorithms
Telecommunications and information theory
Visual communication
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 can be used as an alternative to the entropy-constrained vector quantizer design (ECVQ) proposed by Chou, Lookabaugh, and Gray (1989). By a natural extension of the ECPNN algorithm the authors develop another algorithm that designs alphabet and entropy-constrained vector quantizers and call it alphabet- and entropy-constrained pairwise nearest neighbor (AECPNN) design. Through simulations on synthetic sources, it is shown 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 (Rao and Pearlman, 1993) 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. The performance of coding image pyramids using ECPNN and AECPNN codebooks at rates from 1/3 to 1.0 bit/pixel is discussed.< >
ISSN:1051-8215
1558-2205
DOI:10.1109/76.388057