Abstract: We apply the vector quantization algorithm proposed by Equitz to the problem of efficiently selecting colors for a limited image palette. The algorithm performs the quantization by merging pairwise nearest neighbor (PNN) clusters. Computational efficiency is achieved by using k- dimensional trees to perform fast PNN searches. In order to reduce the number of initial image colors, we first pass the image through a variable-size cubical quantizer. The centroids of colors that fall in each cell are then used as sample vectors for the merging algorithm. Tremendous computational savings is achieved from this initial step with very little loss in visual quality. To account for the high sensitivity of the human visual system to quantization errors in smoothly varying regions of an image, we incorporate activity measures both at the initial quantization step and at the merging step so that quantization is fine in smooth regions and coarse in active regions. The resulting images are of high visual quality. The computation times are substantially smaller than that of the iterative Lloyd-Max algorithm and are comparable to a binary splitting algorithm recently proposed by Bouman and Orchard.!
展开▼
