Abstract
In general, the codebook generation for vector quantization emphasizes two major topics: minimizing the distortion error to improve the quality of the reconstructed image and reducing the time cost to enhance the efficiency. LBG is one of the famous codebook generation techniques proposed in recent decades. LBG was widely utilized due to its simplicity. However, it only guarantees a local optimum. To be an alternative to LBG, the pair-wise nearest neighbor (PNN) algorithm was devised to obtain better results. By the fully searching operation, PNN needs a large amount of calculations. In this paper, a Two-Phase Codebook Generation (TPCG) technique based on the relative pixel magnitudes is presented. With the pre-process of image decomposition, TPCG applies a simple quantifier to divide low frequency blocks in linear time, and then employs a new proposed k-nearest neighbor graph construction approach with Double Linked Algorithm instead of PNN for high frequency blocks. The experiments reveal that TPCG has accuracy approximates to that of PNN while keeping a low time cost. © 2010 IEEE.