Fast Adaptive Algorithm for Time-Critical Color Quantization Application

摘要

Color quantization is the process of grouping n data points to k cluster. We proposed a new approach, based on Wu's color quantization. Our approach can significantly reduce the time consumption during the process compared with available methods but still maintain an acceptable quality of color distribution. As a rough rule of thumb, a quantized image with more than 30 dB of PSNR is often indistinguishable from the uncompressed original image. To achieve this requirement, we proposed to put the cutting plane through the centroid of the largest value representing variance box on the 3D-color histogram of color distribution. This plane is perpendicular to the axis, on which the sum of the squared Euclidean distances between the centroid of both sub-boxes and the centroid of the box is greatest. This guarantees that the total variances of sub-boxes are reduced automatically. To speed up the process, we exploited the dynamic programming as Wu [6] used in his approach. Unlike Wu's approach, we replaced the second order moment calculation with a value representing variance. Because variance is not actually used in calculation, a simpler indicator of data scatterness would speed up the process. From our whole process, we achieved approximately 40% less time consumption than Wu's quantizer.