Efficient Vector Quantization Codebook Generation Based on Histogram Thresholding Algorithm

In general, algorithms of vector quantization codebook generation focus on solving two kinds of problem: 1. to determine the quantization regions and the codewords that minimize the distortion error. 2. to reduce the computational complexity of codewords search for building the codebook. The codebook generation problem can be formulated as a classification problem of dividing N_p training vectors into N_c clusters. For large N_p and N_c, a traditional search algorithm such as the LBG method can hardly find the global optimal classification and needs a great deal of calculation. Threshold selection problem can be formulated as one to find the number of clusters and a partition vector from a given data set. The basic idea of thresholding is to select an optimal threshold value for separating objects regions in an image from the background based on their graylevel distribution. In this paper, a novel VQ codebook generation method based on the histogram thresholding is proposed. The squared Euclidean distance computational complexity can be reduced to O(N_p log₂ N_c) for a VQ codebook. The experimental results and the comparisions show that this method can not only reduces the squared Euclidean distance computational complexity but also finds better codeword to improve the quality of the VQ codebook.