A Partial Codevector Updating Scheme Based on Rate-distortion Optimisation for Adaptive Vector Quantisation

Abstract

In this paper, we propose a new adaptive vector quantisation (AVQ) algorithm based on the ratedistortion optimisation. This algorithm uses a new partial codevector updating (PCU) scheme which achieves rate distortion performance superior to that of the conventional AVQ algorithms using the full codevector updating (FCU) scheme. The PCU AVQ only updates the codevector’s components with quantisation errors higher than an optimal threshold instead of replacing the whole codevector. Basically, the proposed PCU-AVQ is a more generalized AVQ algorithm of the conventional FCU-AVQ. Additionally, the mathematical relation between the Lagrangian multiplier and the approximate optimal threshold is devised to reduce the rate-distortion cost computation. In addition, a fast PCU-AVQ algorithm is also proposed to reduce the encoding complexity. Both theoretical analysis and experimental results show that the proposed AVQ algorithm indeed improves the rate-distortion performance without computational complexity penalty. The PCU-AVQ can be combined with transform coding and entropy coding for higher compression ratio, and it can be widely implemented in specific AVQ algorithms for image, video and speech coding.

Keywords:

• Adaptive Vector Quantisation
• Partial Codevector Update
• Rate-distortion Optimisation
• Image and Video Coding