A FAST SEARCH METHOD FOR VECTOR QUANTIZATION USING 2-PIXEL-MERGING SUM PYRAMID IN RECURSIVE WAY

摘要

Vector quantization (VQ) is a classical but still very promising signal compression method. In the framework of VQ, fast search method is a key issue because it is the time bottleneck in VQ encoding process. To speed up VQ, some fast search methods that are based on a 4-pixel-merging (4-PM) mean pyramid data structure have already been proposed in previous works. However, during the search process, the methods in these previous works discard the obtained value of Euclidean distance at an intermediate level completely if a rejection test fails at this level. This discarded value is a waste to the computation and becomes the overhead, which will certainly degrade the overall search efficiency of VQ encoding. To solve the overhead problem of computation, this paper proposes a 2-pixel-merging sum pyramid data structure and a recursive way for computing Euclidean distances level by level, which can reuse the obtained value of Euclidean distance at any level thoroughly to compute the next rejection test condition at a successive level. Mathematically, the proposed method can overcome the overhead problem of computation completely and reduce the computational burden that is needed in a conventional non-recursive way to about half at each level. Experimental results confirmed the proposed method outperforms the previous works obviously.