Affiliations: Department of Computer Science and Information
Engineering, National United University, Miaoli, 360, Taiwan.
pytsai@nuu.edu.tw | Department of Computer Science and Information
Management, Providence University, Taichung, 433, Taiwan. ychu@pu.edu.tw | Department of Computer Science and Information
Engineering, National United University, Miaoli, 360, Taiwan.
showlien@nuu.edu.tw
Note: [] Address for correspondence: Department of Computer Science and
Information Management, Providence University, Taichung, 433, Taiwan
Abstract: The codebook design in the vector quantization scheme is important
because it affects the image quality of the encoded image. The Linde-Buzo-Gray
(LBG) codebook generation algorithm is well known and a popular choice among
codebook users. However, a heavy computational complexity is consumed for the
iteratively clustering process in the LBG algorithm. In this paper, the
similarity of codewords in consecutive rounds of the LBG algorithm is exploited
to reduce the computational complexity. By checking the stability of codewords,
the status of each codeword in the codebook can be determined. Only the
unstable codewords are refined to generate the new codebook. The proposed
method can be further improved by cooperating with the finite state technique.
Experimental results show that the computational complexity of the proposed
method is reduced to about 4% of the LBG algorithm while achieving a slightly
worse image quality.
Keywords: LBG, Codebook, Stable codeword, Finite state
