Color quantization using an accelerated Jancey k-means clustering algorithm

Color quantization (CQ) is a fixed-rate vector quantization developed for color images to reduce their number of distinct colors while keeping the resulting distortion to a minimum. Various clustering algorithms have been adapted to the CQ problem over the past 40 years. Among these, hierarchical algorithms are generally more efficient (i.e., faster), whereas partitional ones are more effective (in minimizing distortion). Among the partitional algorithms, the effectiveness and efficiency of the Lloyd (or batch) k-means algorithm have been shown by multiple recent studies. We investigate an alternative, lesser-known k-means algorithm proposed by Jancey, which differs from Lloyd k-means (LKM) in the way it updates the cluster centers at the end of each iteration. To obtain a competitive color quantizer, we develop a weighted variant of Jancey k-means (JKM) and then accelerate the weighted algorithm using the triangle inequality. Through extensive experiments on 100 color images, we demonstrate that, with the proposed modifications, JKM outperforms LKM significantly in terms of efficiency without sacrificing effectiveness. In addition, the proposed JKM-based color quantizer is as straightforward to implement as the popular LKM color quantizer. (c) 2024 SPIE and IS&T