Research On Vector Quantization Codebook Design Algorithms Based On Natural Computation

As an effective lossy data compression technology, Vector Quantization (VQ) is the new development of the Shannon’s information theory in the application of the information source coding. The outstanding advantages of VQ are its high compression ratio and the simple coding and decoding methods, which have made it one of the most important technologies in data compression. VQ has gained numerous applications in image compression, pattern recognition, speech coding, video coding, etc. Therefore, the study on VQ is of great theoretical significance and practical value.The theoretical foundation of VQ is Shannon’s rate-distortion theory, and the fundamental principle is that VQ finds the nearest codeword for each input data and transmits the corresponding index to the decoder. Thus at the decoder, merely a simple table look-up operation is required. There are three key techniques in VQ:codebook design, codeword search and codeword index assignment. The codebook design is the most important among those techniques and has great influence on the performance of VQ. This paper puts emphasis on the codebook design technique and presents several natural computation based vector quantization codebook design algorithms.This paper is organized as follows:First of all, this paper proposes an unsupervised two-step learning vector quantization algorithm based on the ideal of the supervised learning vector quantization algorithm. Unlike the supervised learning algorithm, unsupervised learning algorithm cannot use the labels of training data to update the neural network. The proposed algorithm appends a correcting learning step to the simple unsupervised learning vector quantization. In the correcting learning step, a proposed function is used to determine whether there are wrongly clustered data or not and a correcting learning strategy is present to adjust the neural network for the wrongly clustered data.Secondly, to improve the deficient of genetic algorithm such as the poor local search ability and premature convergence, this paper introduces the simulated annealing algorithm into genetic algorithm and presents a partition-based genetic simulated annealing algorithm for vector quantization. The algorithm proposes novel effective crossover operator, mutation operator and simulated annealing method for the partition-based coding.Finally, an immunodominance based clonal selection algorithm for vector quantization is present in this paper to design optimal codebook. Novel effective immunodominance operator is proposed which can obtain prior knowledge adaptively and dynamically from the antibody population and then import the prior knowledge into antibody population. This operator can effectively improve the deficient of clonal selection algorithm such as easily plunging into the local optimum.This paper was supported by the National Natural Science Foundation (No.60803098), the National Research Foundation for the Doctoral Program of Higher Education of China (No.20070701022), the Provincial Natural Science Foundation of Shaanxi of China (2010JM8030) and the Fundamental Research Funds for the Central Universities (K50511020014).