Fast encoding method for vector quantization based on a new mixed pyramid data structure [image coding applications]

VQ is a famous signal compression method. The encoding speed of VQ is a key problem for its practical application. In principle, the high dimension of a vector makes it very expensive computationally to find the best-matched template in a codebook for an input vector by Euclidean distance. As a result, many fast search methods have been developed in previous works based on statistical features (i.e. mean, variance or L/sub 2/ norm) or multi-resolution representation (i.e. various pyramid data structures) of a vector to deal with this computational complexity problem. Therefore, how to use them optimally in terms of a small memory requirement and a little computational overhead becomes very important. This paper proposes to combine both the 2-PM sum pyramid and (n/spl times/n)-PM variance pyramid of a vector to construct a new mixed pyramid data structure, which only requires (k+1) memories for a k-dimensional vector. Experimental results confirmed that the encoding efficiency by using this mixed pyramid outperforms the previous works significantly.

1. INTRODUCTION

In a vector quantization (VQ) [1] framework, its encoding process is implemented block by block sequentially. The distortion between an n×n input block and a codeword can be measured by squared Euclidean distance for simplicity as

$$d^{2}(I,C_{i})=\sum\limits_{j=1}^{k}(I_{j}-C_{i,j})^{2} \qquad i=1,2,\cdots,N_{c} \eqno{\hbox{(1)}}$$ where I is the current image block, is the i^th codeword, j represents the j^th element of a vector, k (=n×n) is the vector dimension and is the codebook size. Due to a high dimension k, it is very expensive to compute .