AN ALGORITHM AND DESIGN TECHNIQUE FOR DESIGNING A VQ CODEBOOK TO MEET A MAXIMUM DISTORTION DESIGN CRITERION

摘要

Vector Quantization (VQ) codebooks are important in pattern classification and recognition, and the k-means algorithm is widely used for codebook generation. The Lloyd's and similar algorithms attempt to address the issue of codebook initialization in the k-means algorithm. However, they produce a codebook with only a locally minimized average codebook-distortion. Also, there is no guarantee on the maximum VQ-distortion even with respect to vectors used in the codebook's generation. This paper discusses an algorithm and design technique developed by the author to design any codebook of unspecified size to meet a maximum VQ-distortion design criterion. The criterion being that the maximum VQ-distortion is less than any design-specified maximum at least with respect to vectors used in the generation of the codebook. This would ensure that worst case VQ-distortion can be made as arbitrarily small as desired by design. This paper also provides test results that verify the above claim.