Fast encoding method for vector quantization based on a new mixed pyramid data structure

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 Lc 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 2-PM sum pyramid and (nxn)-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 obviously.