MINIMAX PARTIAL DISTORTION COMPETITIVE LEARNING FOR OPTIMAL CODEBOOK DESIGN

The design of the optimal codebook for a given codebook size and input source is a challenging puzzle that remains to be solved. The key pro blem in optimal codebook design is how to construct a set of codevecto rs efficiently to minimize the average distortion. A minimax criterion of minimizing the maximum partial distortion is introduced in this pa per. Based on the partial distortion theorem, it is shown that minimiz ing the maximum partial distortion and minimizing the average distorti on mill asymptotically have the same optimal solution corresponding to equal and minimal partial distortion. Motivated by the result, me inc orporate the alternative minimax criterion into the on-line learning m echanism, and develop a new algorithm called minimax partial distortio n competitive learning (MMPDCL) for optimal codebook design. A computa tion acceleration scheme for the MMPDCL algorithm is implemented using the partial distance search technique, thus significantly increasing its computational efficiency. Extensive experiments have demonstrated that compared with some well-known codebook design algorithms, the MMP DCT, algorithm consistently produces the best codebooks with the small est average distortions. As the codebook size increases, the performan ce gain becomes more significant using the MMPDCL algorithm. The robus tness and computational efficiency of this new algorithm further highl ight its advantages.