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 回答