1

我有大约 1000 个相同大小（32 像素 x 32 像素）的 PNG 图像（图块）。它们看起来都不同，但有些非常相似（它们使用相同的颜色）。我必须将它们总结为 PNG 图像（块），每个图像大约有 50 个图块。块大小是动态的，但不应太小。

我的目标是最小化生成的块的大小。

维基百科告诉我，PNG 文件的大小取决于每个像素的颜色深度。

我的想法是对瓷砖进行分组，使每个组的颜色最少。还需要存储颜色索引，因此将每个图块保存为块不是最佳解决方案。进行蛮力运行需要很长时间，所以我希望有一个分组算法的好草图。

我假设当颜色数量超过 1、2、4、8、16、32 等时，文件大小会“跳跃”。所以这些可能是需要注意的门槛。

我现在将绘制一个不会产生最优解的算法

定义

引入组瓷砖距离。一组图块 A 到图块 B 的距离是 B 中不同颜色的数量，但不是组 A。

颜色（G）是一组瓷砖 G 中不同颜色的总数。

算法

1) 选择第一块瓷砖并将其放入 Group1。

2) 循环遍历所有剩余的瓦片并将具有最小组瓦片距离 d_T 的瓦片 T 放入 Group1，如果 Colors(Group1) + d_T 小于某个阈值，例如 16。重复此步骤直到找不到这样的瓦片.

3）选择下一个剩余的瓷砖并重复该过程。

如果组太多或太少，请调整阈值。

不幸的是，这不一定会产生最佳结果（可能有更大的组可能具有相同的阈值）。

可以更改此算法以返回最佳解决方案还是我应该选择不同的方法？

是否有任何因素会影响我没有考虑的 PNG 大小？

4

1 回答 1

1

这可以分为两个问题：

  1. 选择要放在一起的图像（以获得最小的调色板）

  2. 选择它们所在的顺序（利用 PNG 过滤器）

调色板

使用直方图。您可以对颜色进行分色（截断最低有效位）以获得更小的直方图和不同图像的直方图之间更大的重叠。

然后对它们进行分组，例如对最不相似的直方图进行成对分组或使用 K 均值聚类。

差异性将通过添加到组的总直方图中的新直方图条目的数量来衡量（例如，如果组已经使用蓝色和粉红色，则蓝色图像成本为 0，蓝色+红色成本为 1，黄色+绿色成本为 2）。

您还可以使用给定的颜色（sqrt(num_pixels)适用于pngquant）以及与组直方图中最近的可用颜色的距离，通过像素数来衡量差异。

不仅仅是颜色的原始数量，还有这些颜色的选择程度。具有较低均方误差的调色板几乎总是会提供更好的压缩（每比特的视觉信息量），因为颜色不会在图像的不太重要的区域上“花费”得很差。

过滤器

对于第一个近似值，您可以按图像的平滑度对图像进行排序。过滤器对渐变很有用，通常在嘈杂的区域没有帮助。

然后，当它改进过滤启发式时，您可以通过随机交换图像来进行更多暴力操作，即：

  1. 选择两张图片
  2. 计算这些图像行中 32 行像素的启发式方法
  3. 如果这样可以提高分数，请继续交换，如果没有，则回溯
  4. 让它通宵运行

专注于＃1，因为过滤器不会像最佳调色板那样节省大量成本。

于 2012-03-24T21:34:22.853 回答