Study Of Vector Quantization Fast Codeword Search Algorithms

Vector Quantization (VQ) is an effective technique in lossy compression. It replaces the input vector with the index of the most matched codeword and then transmits and stores the index. While decoding, it only needs simple lookup. For its high-ratio compression and easy decoding, VQ has already been applied in static image coding, speech coding and speech recognition. Three key techniques are included in VQ, namely codebook design, codeword search and codeword index assignment, of which the former two are the most important. The codeword search is the research focus of this paper.First, in the research of fast codeword search algorithms based on inequation criteria, an improved algorithm is proposed to reduce the additional calculation and storage space caused by the sum and variance of subvectors in equal-average equal-variance algorithms. In the proposed algorithm, two subvector elimination criteria are integrated into one criterion to achieve simplicity, especially the variance of subvectors is avoided so that both offline and online calculation are reduced and codeword search becomes more efficient. Second, in the research of fast codeword search algorithms based on adaptive search range and search sequence, an improved algorithm is proposed to offset the inefficiency and redundance of the characteristic values in the original algorithms. The single characteristic value proposed is to more effectively define and express each vector, so a great deal of offline calculation and storage space are saved while ensuring the coding quality. Particularly, online calculation is also reduced in order to accelerate codeword search.Third, in the research of a fast codeword search algorithm for split-dimension vector quantization based on the sequence of characteristic values, an algorithm is proposed as a reference to the three codeword search categories, namely fast codeword search algorithms based on inequation criteria, based on adaptive search range and search sequence and based on transform domain. An improved PSO method is firstly adopted to design split-dimension vector codebook in Local Cosine Transform (LCT) transform domain. After that, the characteristic values are ranked and then efficient elimination criteria are used so as to accelerate the codeword search significantly.