1.

Introduction

24-bit color images have become commonplace since the turn of the millennium.^1,2 These images typically contain hundreds of thousands of distinct colors, which complicate their display, storage, transmission, processing, and analysis. Color quantization (cq) is a common image processing operation that reduces the number of distinct colors in a given image. Figure 1 shows the pencils image (Ref. 3, cc0 license, $768\times 512\text{pixels}$) and its quantized versions with 4, 16, 64, and 256 colors obtained using the median-cut algorithm.⁴ It can be seen that the reproduction is reasonably accurate with only 64 colors and is nearly indistinguishable from its original with 256 colors.

Fig. 1

Pencils and its various quantized versions: (a) original (117,157 colors), (b) 4 colors, (c) 16 colors, (d) 64 colors, and (e) 256 colors.

cq is composed of two phases: color palette design and pixel mapping. In the former phase, a small set of colors, called the color palette, representing the input colors is selected, whereas, in the latter phase, each pixel in the input image is assigned to one of the palette colors. The purpose of cq is to reduce the number of distinct colors in a given image to a significantly smaller number with minimal distortion. Since natural images often contain a wide range of colors, faithful reproduction of such images with a small color palette is a challenging problem. In fact, cq can be characterized as a large-scale combinatorial optimization problem.⁵

There are several ways to classify cq algorithms. Image-independent algorithms design a universal color palette without regard to any particular input image, whereas image-dependent ones design a custom color palette based on the distribution of the colors in a given input image. Unsurprisingly, a vast majority of cq algorithms are image-dependent. Another classification scheme is based on the nature of the underlying clustering algorithm.⁶ Hierarchical algorithms recursively find nested clusters in a top-down (or divisive) or bottom-up (or agglomerative) fashion. In contrast, partitional algorithms find all the clusters simultaneously as a partition of the data without imposing a hierarchical structure on the data.⁷ Early cq algorithms were mostly hierarchical, whereas modern cq algorithms tend to be partitional.⁸ Yet another classification scheme is based on whether or not the palette size is allowed to change during the cq process. Static algorithms assume that the palette size is a constant to be specified by the user in advance, whereas dynamic algorithms compute the palette size automatically at run-time. A vast majority of cq algorithms proposed to date are image-dependent and static. Therefore, in this paper, we focus primarily on such algorithms. (The extraction of relevant colors (i.e., colors that stand out to an observer⁹) from a color image, which is an important task in specific application domains such as fine arts^9,10 and medicine,^11,12 is outside the scope of this study.)

Many popular partitional algorithms are based on the local optimization of an objective function, which is typically nonsmooth and nonconvex with numerous local optima. Hence, such algorithms are often highly dependent on initialization¹³ and can easily get stuck in a poor local optimum. By contrast, metaheuristic-based algorithms are formulated based on global optimization and, thus, are less sensitive to initialization.

cq was a necessity in the past due to the limitations of the display hardware, many of which could not handle the number of colors that can be present in a typical 24-bit image. Over the past decades, 24-bit display hardware have become ubiquitous. However, cq is still used in many visual computing applications as a preprocessing step. Modern applications of cq include non-photorealistic rendering, image matting, image dehazing, image compression, color-to-grayscale conversion, image watermarking/steganography, image segmentation, content-based image retrieval, color analysis, saliency detection, and skin detection. For specific references, see Ref. 8.

Despite the over four decades of research on cq, there is currently no benchmark dataset on which cq algorithms can be developed, tested, and compared.⁸ Many cq studies employ a subset of the usc-sipi image database (Available at Ref. 14) or the Kodak lossless true color image suite (Available at Ref. 15). The usc-sipi dataset contains 14 scanned images of relatively poor quality (in modern standards). Furthermore, the copyright status of many of these images is unknown. The Kodak dataset contains 24 relatively high-quality images in the public domain. However, the dataset is neither sufficiently diverse nor sufficiently large to permit comprehensive evaluation of cq algorithms. (For example, in the usc-sipi dataset, three ($\approx 21\%$) images (4.1.01, 4.1.03, and 4.1.04) are portrait photos, two images (4.1.04 and 4.1.02) show the same person, and two images (4.1.07 and 4.1.08) depict identical objects. On the other hand, one-third of the Kodak images portray water bodies. In addition, the dataset contains pairs of images featuring identical objects [i.e., kodim02 depicts a subregion of kodim01, whereas kodim06 and kodim11 depict the same boat captured in two separate yet similar scenes.]) To address these problems, we curated a large, diverse, and high-quality dataset of 24-bit color images called cq100 and released it under a permissive license.

The remainder of this paper is organized as follows. Section 2 gives a detailed description of our dataset. Section 3 demonstrates the use of our dataset in comparing cq algorithms. Finally, Sec. 4 concludes the paper and suggests future research directions.

2.

Description of the Dataset

Our objective was to collect a large, diverse, and high-quality dataset of images and release it under a permissive license. We started by collecting over 100 images from three public sources:

During the image collection process, we paid particular attention to the diversity of content and license compatibility issues. Once we obtained a tentative dataset with 100+ images, we eliminated the images with outlying aspect ratios using the following iterative process. We first computed the mean ($m$) and standard deviation ($s$) of the aspect ratios (Ordinarily, the aspect ratio of an $H\times W$ image is given by $W/H$. However, to treat portrait and landscape images uniformly, we computed the aspect ratio as $\max (W/H,H/W)$.) of the current set of images and then eliminated those with outlying aspect ratios, that is, aspect ratios outside the range $[m-2s,m+2s]$. We added a few more images to the set (from the aforementioned public sources) and then repeated the above outlier removal process until we were left with 100 images. The characteristics of this dataset were:

The images in our initial dataset had dimensions ranging from $768\times 512$ to $6498\times 8123$. To facilitate comparisons, it is desirable to have all images contain the same number of pixels. A simple way to achieve this goal is to resize all images to the same dimensions (and thus the same aspect ratio). To this end, we performed a grid search between the minimum ($l=1.25$) and maximum ($u=1.64$) aspect ratios in the dataset with a step size of $(u-l)/1000$. The optimal aspect ratio minimizing the average relative deviation (Given an image, let $a$ and $\tilde{a}$ be its aspect ratios before and after resizing, respectively. The relative deviation in the aspect ratio caused by the resizing operation is then $\epsilon =|\tilde{a}-a|/a$.) turned out to be 1.49973, which is very close to the standard 3:2 aspect ratio commonly used in 35-mm film photography and digital single-lens reflex camera (dslr) photography. Accordingly, we resized [We used the resize operator (with the default Lanczos resampling filter) of the convert program of ImageMagick 7.1.0-33 (available at Ref. 17)] all portrait and landscape images in our initial dataset respectively to $512\times 768$ and $768\times 512$ to achieve our target aspect ratio of 1.5. These resizing operations caused an average of only 5.35% relative distortion in the aspect ratio, which is negligible. Other than resizing, file renaming and file format conversion were the only modifications made to the original images. Most of the files originally had meaningless or long and overly descriptive names, some reaching 120 characters. Therefore, we renamed each file concisely to accurately reflect its contents. This renaming operation reduced the mean filename length from about 40 to about 12. As for file formats, 95 of the images were originally stored in the jpg format and 5 in the png format. We converted all images to the uncompressed binary ppm format. ppm is popular in visual computing because it is uncompressed, and ppm files are easy to read and write, owing to their extremely simple structure. As mentioned earlier, each image in cq100 has one of four types of licenses (For an overview of these licenses, visit Ref. 18.) (listed in decreasing permissiveness):

Since these licenses are mutually compatible, we released cq100 under the least permissive of them, namely the cc by-sa 4.0 license. Nevertheless, this license allows anyone to share and modify our dataset with the restrictions noted above. The metadata associated with each image include the following 16 attributes: original image filename, modified image filename, image category, source url, license, license url, author, author url, modifications made to the original image, additional notes about the original image, original image width, original image height, original image number of colors, modified image width, modified image height, and modified image number of colors.

To demonstrate the diversity of cq100, we show thumbnails for images 1 through 25, 26 through 50, 51 through 75, and 76 through 100 in Figs. 2Fig. 3Fig. 4–5, respectively. The numeric id around each thumbnail indicates the alphabetical order of the filename of the corresponding image, e.g., 1: adirondack_chairs; 2: astro_bodies,…, 99: wool_carder_bee; and 100: yasaka_pagoda. A more detailed view of a subset of cq100 is given in Fig. 6, which displays a sample image from each category. Note that for each image featured in Figs. 2Fig. 3Fig. 4Fig. 5–6, the original license is given in the respective caption.

Fig. 2

Thumbnails for images 1 through 25 (3, 5, 10, 18, and 21 are in the public domain; 6, 15, 16, and 23 are licensed under cc0; the others are licensed under cc by-sa).

Fig. 3

Thumbnails for images 26 through 50 (35, 39, 44, and 48 are in the public domain; 26, 28, 29, 36, 37, 41, 42, 47, and 49 are licensed under cc0; 34, 45, and 50 are licensed under cc by; and the others are licensed under cc by-sa)

Fig. 4

Thumbnails for images 51 through 75 (51, 60, 73, and 74 are in the public domain; 63, 64, and 66 are licensed under cc0; 67 is licensed under cc by; and the others are licensed under cc by-sa).

Fig. 5

Thumbnails for images 76 through 100 (79 is in the public domain; 76, 78, 82, 86, 88, 91, 92, 97, and 98 are licensed under cc0; 84, 89, and 96 are licensed under cc by; and the others are licensed under cc by-sa).

Fig. 6

Sample images from cq100: (a) red-eyed tree frog (animals), (b) fruits (food), (c) color checker (miscellaneous), (d) nylon cords (objects), (e) schoolgirls (people), (f) cosmic vista (places), (g) daisy bouquet (plants), and (h) sports bicycles (vehicles). Images (a), (e), and (f) are in the public domain; the others are licensed under cc0.

Figures 7 and 8 show box plots of the distribution of respectively the number of distinct colors and colorfulness¹⁹ per image for cq100, Kodak, and usc-sipi datasets. It can be seen that cq100 has a greater color diversity compared to the other two datasets.

Fig. 7

Box plot of the distribution of the number of distinct colors per image for cq100, Kodak, and usc-sipi datasets.

Fig. 8

Box plot of the distribution of the colorfulness per image for cq100, Kodak, and usc-sipi datasets

3.

Demonstration of the Dataset

In this section, we demonstrate the use of our cq100 dataset on a cq task. First, we describe the experimental setup and present a brief qualitative assessment. Then, we conduct a more detailed quantitative assessment and discuss its implications.

3.1.

Experimental Setup and Qualitative Assessment

We compare the following 21 cq algorithms (listed in chronological order) with respect to their effectiveness [An effective cq algorithm is one that produces minimal distortion, as quantified by a chosen image fidelity metric (see Sec. 3.2).]:

• • Median-cut algorithm⁴ (divisive hierarchical) (mc)

• • Popularity algorithm⁴ (partitional) (pop)

• • Octree algorithm²⁰ (agglomerative hierarchical) (oct)

• • Wan et al.’s marginal variance minimization algorithm²¹ (divisive hierarchical) (wan)

• • Orchard and Bouman’s binary splitting algorithm²² (divisive hierarchical) (bs)

• • Wu’s variance minimization algorithm²³ (divisive hierarchical) (wu)

• • Dekker’s self-organizing map algorithm²⁴ (partitional) (som)

• • Split-and-merge algorithm²⁵ (agglomerative hierarchical) (sam)

• • Batch $k$-means algorithm initialized using vcl²⁶ (partitional) (wsm)

• • Fuzzy $c$-means algorithm initialized using wu²⁷ (partitional) (wfcm)

• • Adaptive distributing units algorithm²⁸ (partitional) (adu)

• • Variance-cut algorithm with Lloyd iterations²⁹ (divisive hierarchical) (vcl)

• • Ant-tree algorithm³⁰ (metaheuristic) (atcq)

• • Firefly algorithm combined with atcq³¹ (metaheuristic) (ffatcq)

• • Artificial bee colony combined with atcq³² (metaheuristic) (abcatcq)

• • Shuffled-frog leaping algorithm³³ (metaheuristic) (sfla)

• • wu combined with atcq³⁴ (metaheuristic) (wuatcq)

• • Particle swarm optimization combined with atcq³⁵ (metaheuristic) (psoatcq)

• • bs combined with itatcq³⁶ (metaheuristic) (bsitatcq)

• • Iterative atcq³⁷ (metaheuristic) (itatcq)

• • Iterative online $k$-means algorithm³⁸ (partitional) (iokm)

These algorithms represent the cq work published between 1980 and 2022. (For a modern survey of cq, see Ref. 8.) However, it should be noted that our objective is not to perform an exhaustive comparison of the cq algorithms published over the past 40 years but to demonstrate the use of the presented dataset in comparing several popular cq algorithms.

We execute each algorithm with the default parameter values suggested by its authors (see Table 1) and quantize each image in our dataset to 4, 16, 64, and 256 colors separately. The cases of 4 and 256 colors represent the two extremes. It can be argued that a typical natural image can hardly be quantized to fewer than 4 colors, and most images can be reproduced relatively accurately with no more than 256 colors.

Table 1

Parameter setting for each cq algorithm.

Algorithm	Parameter setting
mc/pop/wan/wu	Number of bits: 5
oct	Maximum depth: 6
som	Sampling factor: 1
sam	Initial number of clusters: $20\times$ number of colors
wsm	Decimation factor: 2
	Maximum number of iterations: 100
	Convergence threshold: 0.001
wfcm	Decimation factor: 2
	Maximum number of iterations: 100
	Convergence threshold: 0.001
	Weighting exponent: 2
adu	Learning rate: 0.015
vcl	Decimation factor: 2
	Number of bits: 5
	Number of iterations: 10
atcq	$\alpha =0.25$, 0.3, 0.35, and 0.4 for 4, 16, 64, and 256 colors, respectively.
ffatcq	Number of fireflies: 5
	$\alpha =\{0.25,0.30,0.35,0.40,0.45\}$
	Number of iterations: 20
abcatcq	Number of food sources: 5
	$\alpha =\{0.25,0.30,0.35,0.40,0.45\}$
	Number of iterations: 20
sfla	Number of frogs: 8
	Number of memeplexes: 2
	Number of iterations: 20
psoatcq	Number of particles: 5
	$\alpha =\{0.25,0.30,0.35,0.40,0.45\}$
	Number of iterations: 20
bsitatcq	Number of iterations: 20
itatcq	$\alpha =0.35$
	Iterations: 20

Figures 9Fig. 10Fig. 11–12, respectively show the shopping bags, motorcycle, umbrellas, and common jezebel images quantized using three algorithms (in each figure, going from top to bottom, the subfigures are arranged in progressively decreasing quality). Given an input image, for each algorithm, we display the corresponding reduced-color output image and a grayscale error image that allows us to visualize the differences between the input and output. The error image is obtained by amplifying the pixelwise normalized Euclidean differences between the input and output by a factor of four and then negating them for better visualization (see below). Hence, the cleaner/lighter the error image, the better the reproduction of the input image.

Fig. 9

(a) Shopping bags (13,752 colors) and its various quantized versions (4 colors): (b) wfcm, (d) wuatcq, and (f) bsitatcq. Subfigures (c), (e), and (g) are the error images corresponding to subfigures (b), (d), and (f), respectively.

Fig. 10

(a) Motorcycle (212,020 colors) and its various quantized versions (16 colors): (b) psoatcq, (d) adu, and (f) bsitatcq. Subfigures (c), (e), and (g) are the error images corresponding to subfigures (b), (d), and (f), respectively.

Fig. 11

(a) Umbrellas (217,673 colors) and its various quantized versions (64 colors): (b) sfla, (d) abcatcq, and (f) wfcm. Subfigures (c), (e), and (g) are the error images corresponding to subfigures (b), (d), and (f), respectively.

Fig. 12

(a) Common jezebel (137,446 colors) and its various quantized versions (256 colors): (b) adu, (d) wsm, and (f) iokm. Subfigures (c), (e), and (g) are the error images corresponding to subfigures (b), (d), and (f), respectively.

Let $I_{\mathrm{RGB}}$ and ${\tilde{I}}_{RGB}$ respectively denote the $H\times W$ original input and quantized output images in the standard rgb (srgb) color space.³⁹ $I_{\mathrm{RGB}}(r,c)$ and ${\tilde{I}}_{\mathrm{RGB}}(r,c)$ are then three-dimensional vectors containing the rgb values of the pixel with (row, column) coordinate $(r,c)$ in $I_{\mathrm{RGB}}$ and ${\tilde{I}}_{\mathrm{RGB}}$, respectively ($r\in \{1,\dots ,H\}$ and $c\in \{1,\dots ,W\}$). The corresponding pixel in the 8-bit error image $E$ is then computed as

Eq. (1)

$$E(r,c)=255-\frac{4}{\sqrt{3}}{\Vert I_{\mathrm{RGB}}(r,c)-{\tilde{I}}_{\mathrm{RGB}}(r,c)\Vert }_2,$$

where ${\Vert ·\Vert }_2$ denotes the Euclidean (${\ell }_2$) norm. Note that the division by a $\sqrt{3}$ is necessary for the rgb -to-grayscale conversion, and pixels in $E$ with negative values are clipped to zero.

4.

Conclusions and Future Research Directions

In this paper, we presented cq100, a large, diverse, and high-quality dataset of 24-bit color images released under the cc by-sa 4.0 license. We also demonstrated how cq100 can be used to compare cq algorithms based on the popular mse metric (computed in the cielab color space). Future work includes a multivariate comparison of cq algorithms over cq100 based on several image fidelity metrics.

The use of cq100 is not restricted to cq. For example, it can also be used to develop, test, and compare filtering⁵⁹ or segmentation^60,61 algorithms. However, for some applications, the images in the dataset may need to be annotated by one or more human experts. For example, in a segmentation application, the annotation for a given image could include bounding boxes around objects of interest or a segmentation mask for the entire image. cq100 is significantly larger and more diverse than its two main competitors (i.e., usc-sipi and Kodak). Although the current size of the dataset appears to be adequate for its primary target application, which is an unsupervised learning task, it should be expanded if it is to be used for supervised learning tasks.