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

Author(s) : Zhibin Pan (Tohoku University, Japan) Koji Kotani (Tohoku University, Japan) Tadahiro Ohmi (Tohoku University, Japan)

Abstract : 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 [5], [6]. 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.

Menu