pngs综述，尺寸优化

Question

我有大约1000个相同大小的PNG图像(瓷砖)(32 Pxx32px)。它们看起来都不一样，但有些非常相似(它们使用相同的颜色)。我必须用PNG图片(区块)来总结它们，每块大约有50块。块大小是动态的，但不应该太小。

我的目标是最小化结果块的大小.

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

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

我假设当颜色超过1,2,4,8,16,32等等时，文件大小就会“跳跃”。因此，这些可能是值得注意的门槛。

I现在将勾勒出一种不产生最优解的算法，

定义

介绍一组瓷砖的距离。一组瓷砖A到一块瓷砖B的距离是B中不同颜色的数量，而不是A组中不同颜色的数量。

颜色( G )是一组瓷砖G中不同颜色的总数。

算法

1)取第一块瓷砖，放入Group1中。

2)循环所有剩余的瓷砖，并将最小组距的瓷砖T放入Group1，如果颜色(Group1)+ d_T较小，等于某个阈值，例如16。重复这一步骤，直到找不到这样的瓷砖。

3)选择下一个剩余的瓷砖，并重复这个步骤。

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

不幸的是，这并不一定会产生最好的结果(可能有一个更大的组可能具有相同的阈值)。

这个算法可以改变为返回最优解，还是应该选择不同的方法？

是否有任何因素影响巴布亚新几内亚的规模，而我并没有考虑这些因素？

Answer 1

这可以分为两个问题：

1. 选择要放在一起的图像(以获得最小的调色板)
2. 选择它们的顺序(利用PNG过滤器)

调色板

处理直方图。您可以张贴颜色(截断最小有效位)，以获得更小的直方图和更大的重叠之间的不同图像直方图。

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

这种不同将通过添加到组的总直方图中的新直方图条目的数目来度量(例如，如果组已经使用了蓝色和粉红色，那么蓝色图像成本为0，blue+red成本为1，yellow+green成本为2)。

您还可以使用给定的颜色(sqrt(num_pixels)适用于平干)以及组直方图中距离最近的可用颜色的距离来衡量不同像素的数量。

不仅仅是原始颜色的数量，还包括这些颜色选择的好坏。均方误差较低的调色板几乎总是能提供更好的压缩(每比特的视觉信息量)，因为颜色不会在图像中不那么重要的区域上“花费”很差。

过滤器

对于第一次近似，您可以根据图像的平滑性对其进行排序。过滤器是有用的梯度，通常没有帮助在嘈杂的地区。

然后，当它改进启发性过滤时，您可以通过随机交换图像来施加更多的暴力，即：

1. 挑选两幅图像
2. 计算这些图像行中32行像素的启发式
3. 如果这能提高分数，就继续交换，如果没有，就回溯
4. 让它在一夜之间运行

专注于#1，因为过滤器没有最佳调色板那么大的节省。