Color Quantization Using the Fast K-Means Algorithm
Hideo Kasuga
Graduate School of Engineering, Shinshu University, Nagano, Japan 380-8553
Hiroaki Yamamoto and Masayuki Okamoto
Faculty of Engineering, Shinshu University, Nagano, Japan 380-8553
SUMMARY
Many color images use 24 bits for color information.
However, this number of colors is not always necessary. In
this paper, an algorithm that quantizes a full-color image
from about 17 million to 256 colors is proposed. The
quantized colors are calculated so that the sum of squared
quantization errors is minimized. To quantize the color
image, the fast K-means algorithm is proposed. This algo-
rithm classifies K clusters into groups. These groups are
used to decrease the number of calculations and the execu-
tion time. The fast K-means algorithm is effective when K
is large. The results show that for K = 256 the execution
time is less than a quarter of that for the K-means algorithm.
© 2000 Scripta Technica, Syst Comp Jpn, 31(8): 3340,
2000
Key words: Color quantization; clustering; K-
means algorithm; fast K-means algorithm.
1. Introduction
The color quantization problem was often examined
at a time when display performance was limited. Appropri-
ate quantization is necessary to show a full-color image on
a display that uses a look-up table. In this paper, we describe
an algorithm that quantizes a 24-bit color image to an 8-bit
per color image. There exist major color quantization algo-
rithms, such as the popularity algorithm, the median cut
algorithm (MCA) [1], and Watanabes algorithm [2]. The
popularity algorithm chooses the colors with the highest
frequency from a histogram. A disadvantage of the popu-
larity algorithm is that inappropriate colors are often chosen
when an image has many colors used equally. The MCA is
an algorithm that repeatedly divides the RGB color space
into smaller rectangular boxes and then chooses the quan-
tized color to be the average color in each box. To divide
the color space, we use the width of the data distribution as
a base, and then divide the space at the median point. The
MCA is faster than the popularity algorithm, but the quan-
tization error is larger because the method of division is not
optimum. Watanabes algorithm is an improved version of
the MCA. The division of the color space is similar to the
MCA, but the dividing line is based on the standard devia-
tion of the colors, and the space is divided at the average
point. This algorithm is faster than the popularity algorithm
and the quantization error is smaller. These algorithms are
excellent in execution time, but there is room for improve-
ment in quantization quality. There is a method using dith-
ering to represent a color image with a limited number of
colors [3]. However, it is difficult to understand the original
information from the dithered image. In this paper, we
propose an algorithm whose quantization quality is better
than previous algorithms. The quantization quality of an
algorithm is measured using PSNR in this paper.
© 2000 Scripta Technica
Systems and Computers in Japan, Vol. 31, No. 8, 2000
Translated from Denshi Joho Tsushin Gakkai Ronbunshi, Vol. J82-D-II, No. 7, July 1999, pp. 11201128
33