Split and merge codebook design algorithms for image compression

This paper introduces two new codebook design algorithms for image data compression applications. The proposed algorithms design codebooks by splitting and merging the prototypes of the training vectors, which play the role of code-vectors in the encoding/decoding process. The split-1 (S1) algorithm begins with a codebook containing a single prototype and designs a codebook of the desired size by splitting one prototype at each iteration. The split-1-merge-2 (S1M2) algorithm begins with a codebook of the desired size and improves its quality in an iterative fashion by splitting one prototype and merging two prototypes at each iteration. The proposed algorithms are used to design codebooks for image data compression based on vector quantization. The experimental results indicate that the proposed algorithms are strong competitors to the popular Linde-Buzo-Gray algorithm in terms of their computational requirements and the quality of the designed codebooks. (C) 2000 SPIE and IS&T. [S1017-9909(00)00204-X].