A partial codevector updating scheme based on rate-distortion optimisation for adaptive vector quantisation

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