1. 简介

减色算法（ColorQuantization）是一种应用在色彩空间中用于减少图像离散色彩值的一类算法，旨在通过减少图像的离散色彩值从而减少了每个色彩值的表示比特数。一方面达到压缩图像的效果，另一方面使得一些以固定有限比特数表示像素的显示设备也能显示每个像素更多表示比特的图像。

2. 中位切割算法

中位切割算法（Median Cut）是最知名、应用最广泛的减色算法，常见的图像处理软件如 Photoshop、GIMP 等都使用了这个算法或其变种。

2.1 原理

假设有一张 RGB 图像，想要降低图像中色彩数目到 256256 色。中位切割算法流程如下：

  1. 将图片的所有像素放到同一个区域（RGB 三维空间中）
  2. 对所有区域进行以下操作：
    1. 计算此区域内所有像素的 RGB 三元素最大值与最小值的差
    2. 选出相差最大的那个颜色（R 或 G 或 B）
    3. 根据那个颜色去排序此区域内所有像素
    4. 分割前一半和后一半的像素到两个不同区域（即「中位切割」）
  3. 重复第二步直到产生了 256256 个区域
  4. 将每个区域的像素值平均起来，就得到 256256 色

2.2 实现

假设有一张 RGB 图像，其每个像素的每个分量（R、G、B）均用 88 比特表示，要想将其色彩数目由 256×256×256256 \times 256 \times 256 降低到 256256，简单伪代码部分实现如下：

  1. 统计每对 <R,G,B> 像素值的像素数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Global FREQUENCIES [0..255][0..255][0..255]
Global IMAGE [1..IMAGEHEIGHT][1..IMAGEWIDTH]

Procedure GatherFrequencies
    Begin
    For II = 1 To IMAGEHEIGHT Do
        Begin
        For JJ = 1 To IMAGEWIDTH Do
            Begin
            RED = IMAGE[II][JJ].RED
            GREEN = IMAGE[II][JJ].GREEN
            BLUE = IMAGE[II][JJ].BLUE
            FREQUENCIES[RED][GREEN][BLUE] = FREQUENCIES[RED][GREEN][BLUE] + 1
            End
        End
    End
  1. 分割一个区域。假设极差最大的色彩分量为 B，该区域 R、G、B 分量的范围分别为 [Rl,Rr]、[Gl,Gr]、[Bl,Br]：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Global FREQUENCIES [0..255][0..255][0..255]
Function DivideBlueInHalf
    Begin
    COUNT = 0
    For BLUECUT = Bl to Br Do
        Begin
        For II = Rl to Rr Do
            Begin
            For JJ = Gl to Gr Do
                Begin
                COUNT = COUNT + FREQUENCIES[II][JJ][BLUECUT]
                End
            End
        If COUNT > IMAGEHEIGHT * IMAGEWIDTH / 2 Then
            Return BLUECUT
        End
    Return Br
    End

附录