In this paper, we propose two fast codebook generation algo-book. Some alternative methods are also available [14]. rithms by making use of the information in the iterative process. The pairwise Nearest Neighbor (PNN) algorithm is a new Comparing to the conventional full search method (the LBG alternative [14] to the LBG algorithm for generating codealgorithm), the Fast Codebook Generation Algorithm (FCGA) books. The PNN algorithm is faster than the LBG method; reduces the CPU time by a factor of 2.49 to 6.16 for real images. however, worse distortion is usually obtained [15].
Compared to FCGA the Maximum Set Algorithm (MSA),
Haung and Harris developed a DSBS method to reduce which is designed for the large codebook, gives the worse perforcodebook generation time [15]. For real images, this mance in general for our simulations. However, the Maximum method reduced the CPU time by a factor of about 1.5
Set Algorithm (MSA) still gives a better performance than that and gave the same distortion as that produced by the LBG of the LBG algorithm and reduces the CPU time by a factor of 1.63 to 2.67. Both methods presented in this paper outperalgorithm. The DSBS algorithm uses the same splitting form the DSBS method developed by Huang and Harris. Comprocess used by the LBG algorithm to double the number pared to the LBG algorithm, the DSBS method reduced the of codewords, except that the new codewords are genercodebook generation time by a factor of 1.5-2. It is noted that ated differently. For each cluster of training vectors, the both FCGA and MSA give the same codebook as that produced codewords generated by the DSBS algorithm are on the by the LBG algorithm. Finally, some experimental results for principal axis of the scatter matrix of the cluster [15]. The several training sets with different types and sizes are listed. distortion caused by using the DSBS algorithm is about