一、效果

① 原图；② K-Means 选取 128 个质心点进行量化；③ R G B 分别选择 4 值、8 值、4 值进行等距量化。

二、流程

原图像如下。定义 H, W 为图像的高和宽。

img = io.imread('pic2.png')
print(img.shape, np.min(img), np.max(img))
H, W, C = img.shape

plt.figure(figsize=(10, 6))
plt.figure(1)
plt.imshow(img)
plt.axis('off')
plt.title('original')
plt.show()

1. 等距量化方法

因为 $128 = 4 \times 8 \times 4$，这里先尝试以「红色 4 级别、绿色 8 级别、蓝色 4 级别」对每个通道分别做量化，最终可量化成 128 个颜色：

img0 = np.empty(shape=[H, W, 3])
for i in range(H):
    for j in range(W):
        img0[i][j] = np.array([
            img[i][j][0] // (256 / 4) / 4,
            img[i][j][1] // (256 / 8) / 8,
            img[i][j][2] // (256 / 4) / 4
        ])

plt.figure(figsize=(10, 6))
plt.figure(1)
plt.imshow(img0)
plt.axis('off')
plt.title('128 = 4 × 8 × 4 levels')

可以看到颜色数目局限、边缘明显。这个方法是用来与 K-Means 方法的效果做比较的。

2. 聚类问题的目标

现在有 $N$ 个三维空间中的点 $\boldsymbol p_i$ （ $i\in [1, N] \cap \N$ ）。求将这些点分为 $K$ 个集合 $A_j$ （$j \in [1, K] \cap \N$）（设第 $i$ 个点所属集合下标为 $a_i$ ），每个集合都有一个簇心点 $\boldsymbol c_j$ ，设法最小化所有点到其所属集合簇心点的距离平方和（总体误差）：

$$ E = \sum_{i=1}^{N} (\boldsymbol p_i - \boldsymbol c_{a_i})^2 $$

换句话说，就是找到将 $N$ 个点划分为 $K$ 份、并且让各份内都尽可能紧密的最佳方案。

3. K 均值聚类算法原理

此方法通过逐渐迭代簇心点，以求得簇心点的局部最优解。

**初始值：**随机选择 $K$ 个点作为初始簇心点 $\boldsymbol c_j$ 。