Vector Quantization Using Evolutionary Algorithm

As an efficient loss compression technique, vector quantization is known forits simple decoding, and has been widely applied to image and speech compression.The fundamental problem of vector quantization is designing codebook and searchingfor codeword. Designing codebook which determines compressive performance is vitalto vector quantization. The traditional algorithms for designing codebook such as LBGalgorithm and tree-structure approach depends on the initial codebook or aggregatedclass seeds, in addition, the self-adaptive ability of codebook is very weak, therefore, itis hard to approach the global optimal solution. As a global optimization searchingalgorithm, featuring colony diversity, simple universality, strong robustness, being fitfor parallel processing, and wide usage, genetic algorithm can acquire accumulateautomatically knowledge related to searching space during the searching process, andcontrol self-adaptively the searching process to approach the global optimal solution,which make up the deficiency of the traditional approach of vector quantization. Antcolony optimization (ACO for short) was first proposed by Dorigo, it adopts randomselection and pheromone renew as the real ant's forage to solve the CombinatorialOptimization problems. Now ACO was successfully applied in TSP, JSP, and theresearch in codebook design has been started recently, it is worth to keep on.According to the different coding design on chromosome in the genetic lgorithm,we put forward the codebook design of genetic vector quantization based on training listand vector quantization based on codebook, furthermore, its validity is proved. Thenintroduces the theory and model of ACO and the application of ACO in image vectorquantization. As for the main defect of ACO, such as slow convergence speed and fallin local optimization, this paper mends the ACO algorithm which used in image vectorquantization: this paper adopts a new pheromoneu pdate model-Train Vectors, whichbelong to diferent clustering centers, have different pheromone increment, and usessimulated annealing strategy to adjust the training vectors which has the maximumdistance bewteen the traning vector and its representative, experiment shows that themodified method has improved the codebook quality 0.16dB; Combine GeneticAlgorithm and ACO algorithm, a genetic ACO algorithm is proposed, genetic operatorsis integrated into ACO's every iterative, the codebooks which generated from ACO areoptimized by Genetic Operator, experiment shows that the PSNR of Codebook, which generate from Genetic ACO, is 29.82, there is 0.23dB increase than the Codebookgenerated only by ACO.Through the work of this paper, we can see the search ability of ACO, thecombination of genetic and ACO contains the advantages of genetic and ACO.Improves codebook's performance greatly.