A dichotomy color quantization algorithm for the HSI color space

Yu Xia, Huaiyu Zhuang, Yani Cui, Jiaxian Deng, Jia Ren, Haixia LongScientific 2023 · DOI

TL;DR

Researchers have developed a novel color quantization algorithm that operates in the HSI (Hue, Saturation, Intensity) color space rather than the traditional RGB space. By mapping the complex, piecewise Hue component to a single-valued monotonic function and applying a dichotomy-based search, the algorithm achieves significantly lower image distortion (MSE) than state-of-the-art RGB-based methods.

What Problem Does This Paper Address?

Color quantization (CQ) is the process of reducing the number of distinct colors in an image while trying to keep the result as visually similar to the original as possible. This is essential for displaying images on low-end hardware, speeding up transmission, and reducing storage requirements.

Most existing algorithms work in the RGB color space. However, RGB has a major flaw for image processing: its components (Red, Green, Blue) are highly interdependent. If you distort one, you often inadvertently distort the others. The HSI color space is generally superior for maintaining image quality during compression, but it’s rarely used for quantization because the Hue (H) component is mathematically "messy"—it is defined by a piecewise function that makes standard optimization difficult. This paper tackles the challenge of making HSI quantization both accurate and computationally efficient.

Methods

The authors propose a three-step solution:

  1. Monotonic Function Mapping: To handle the piecewise nature of Hue, they constructed a single-valued monotonic function, $f(H)$. This transformation maps the circular Hue values into a continuous range $[0, 9)$, effectively "unwrapping" the color wheel into a linear format that is much easier to quantize.
  2. Iterative Quantization: Using the Minimum Mean Square Error (MMSE) as a criterion, they developed an iterative algorithm to find the optimal quantization points along this new $f(H)$ curve.
  3. Dichotomy Optimization: The iterative approach is computationally expensive (requiring millions of searches). To fix this, they introduced a dichotomy quantization algorithm. By treating the search for quantization points as a root-finding problem on a monotonic curve, they used a binary-search-like method to find optimal points in a fraction of the time.

Datasets

The study utilized standard benchmark images from the USC-SIPI image database, commonly used in computer vision research:

  • Mandrill (Baboon): Known for its high-frequency texture and diverse color palette.
  • Plane, Lake, Peppers, and Lena: Standard images used to test various aspects of color reproduction and edge preservation. All test images were $512 \times 512$ pixels.

Key Insights and Ideas

  • The "Unwrapping" Strategy: The most significant "aha" moment is the realization that Hue doesn't have to be treated as a piecewise angular value. By mapping it to a monotonic function, the authors turned a non-linear optimization problem into a linear one.
  • Independence Matters: By quantizing in HSI space, the algorithm treats color (Hue), vibrancy (Saturation), and brightness (Intensity) as independent variables. This prevents the "color shifting" often seen in RGB quantization when one channel is compressed more than others.
  • Efficiency through Dichotomy: The jump from the iterative algorithm to the dichotomy algorithm is a classic example of algorithmic optimization. Moving from a linear search to a logarithmic-style search reduced the number of iterations for a typical quantization task from ~8.5 million to just ~4,200.

Key Results

The proposed method was compared against several high-performance RGB algorithms, including K-means variants (PSO+KM, ABC+KM) and Ant-Tree-based methods (ATCQ).

  • Massive MSE Reduction: In the Mandrill image test with 256 colors, the proposed HSI method achieved a Mean Square Error (MSE) of 0.69. In contrast, the best-performing RGB-based competitor (ABC+KM) had an MSE of 97.14. Lower MSE indicates much higher fidelity to the original image.
  • Visual Fidelity: Qualitative results show that even at very low color counts (e.g., 32 colors), the proposed method maintains the "feel" and shading of the original image better than uniform HSI quantization.
  • Computational Speedup: The dichotomy approach proved to be orders of magnitude faster than the basic iterative approach while maintaining the same precision.

Limitations and Future Work

While the dichotomy algorithm significantly reduces the number of iterations required to find quantization points, the authors note that the overall speed of quantifying the H component is still not quite "real-time" for all applications.

Future research will focus on further optimizing the speed of the H-component transformation to make the algorithm suitable for high-speed video processing or mobile applications where computational resources are strictly limited. Additionally, the paper primarily focuses on the Hue component; further refinement of how Saturation and Intensity are weighted relative to Hue could yield even better perceptual results.

Summary updated

Abstract

Color quantization is used to obtain an image with the same number of pixels as the original but represented using fewer colors. Most existing color quantization algorithms are based on the Red Green Blue (RGB) color space, and there are few color quantization algorithms for the Hue Saturation Intensity (HSI) color space with a simple uniform quantization algorithm. In this paper, we propose a dichotomy color quantization algorithm for the HSI color space. The proposed color quantization algorithm can display images with a smaller number of colors than other quantization methods of RGB color space. The proposed algorithm has three main steps as follows: first, a single-valued monotonic function of the Hue (H) component in the from RGB color space to HSI color space (RGB-HSI) color space conversion is constructed, which can avoid the partition calculation of the H component in the RGB-HSI color space; second, an iterative quantization algorithm based on the single-valued monotonic function is proposed; and third, a dichotomy quantization algorithm is proposed to improve the iterative quantization algorithm. Both visual and numerical evaluations reveal that the proposed method presents promising quantization results.
BibTeX
@inproceedings{xia2023dichotomy,
  author = {Yu Xia and Huaiyu Zhuang and Yani Cui and Jiaxian Deng and Jia Ren and Haixia Long},
  title = {{A dichotomy color quantization algorithm for the HSI color space}},
  booktitle = {Scientific},
  year = {2023},
  doi = {10.1038/s41598-023-34977-0},
}
Figure