Abstract: We apply the vector quantization algorithm proposed byEquitz to the problem of efficiently selecting colorsfor a limited image palette. The algorithm performs thequantization by merging pairwise nearest neighbor (PNN)clusters. Computational efficiency is achieved by usingk- dimensional trees to perform fast PNN searches. Inorder to reduce the number of initial image colors, wefirst pass the image through a variable-size cubicalquantizer. The centroids of colors that fall in eachcell are then used as sample vectors for the mergingalgorithm. Tremendous computational savings is achievedfrom this initial step with very little loss in visualquality. To account for the high sensitivity of thehuman visual system to quantization errors in smoothlyvarying regions of an image, we incorporate activitymeasures both at the initial quantization step and atthe merging step so that quantization is fine in smoothregions and coarse in active regions. The resultingimages are of high visual quality. The computationtimes are substantially smaller than that of theiterative Lloyd-Max algorithm and are comparable to abinary splitting algorithm recently proposed by Boumanand Orchard.!
展开▼
