java - 如何在 PGM 图像上使用 KMeans 实现 vector 量化

Question

要求做， 在 PGM 文件上使用 KMeans 进行 vector 量化(或图像压缩)
图像是 PMG 文件，其中 b = block 大小，k = 次数，t = 迭代，-g = 初始质心

图像是这样的 126 131 128 126 129 130 127 128 130 123 132 128 131 124 131 129 。 。 129

算法1 K-means算法 要求:输入数据X = {x1; x2;... xN}，簇数 K，其中 K <= N，初始 质心的猜测 Y = {y1; y2;..yK}，最大迭代次数T。

for t = 1; 2; .... T do
for i = 1; 2; .... N do
Find the centroid from the current set Y that is closest to xi.
Assign xi to its closest centroid.
end for
for j = 1; 2; .... K do
Update yj as the average of the vectors that are assigned to yj .
end for
end for

经过K-means之后，我们将原始数据简化为K个原型(prototype) vector Y的列表，如下
对于 X 中的每个 vector ，它最接近的原型(prototype) vector 的索引，即
X = {x1; x2; .. xN} -> Y = {y1; y2; .. yK},L = {l1; l2; ....lN}；
其中每个 li 都是 1 到 K 之间的整数，指示 xi 属于哪个原型(prototype) vector
最接近。仅存储或传输Y和L，而不是X。例如，使用 b = 4
K = 256，对于 420x300 像素的图像(未压缩 123 KB)，我们需要存储
X = 256 x {16 字节} + Y = 7875{字节} ~ 12 KB:
y 的存储         L 的存储

为了从压缩数据重建图像，对于每个 b x b block ，我们简单地 用最接近 block 的去光栅化原型(prototype) vector 填充它(回想一下 每个 block 对应一个 vector xi，它有一个索引值Li

我要问的是我完全不知道将更新 yj 指定为 vector 的平均值是什么意思以及如何重建图像，任何人都可以向我解释一下。 是的，这是作业，但我真的迷路了，如果有人能指出我正确的方向。

Answer 1

因此，最初您只需随机猜测质心 (y) 应该是什么。假设您需要 3 个簇，最初您猜测质心 Y = {126, 128, 130}。每次迭代将每个点放入具有最近质心的簇中后，再次计算 Y。因此，如果您的质心 y1(本例中最初为 126)得到 X 的 {126, 126, 127}，则新的 Y1 就是这 3 个点的平均值 (126.33)。 y2 和 y3 也类似。