仅使用重叠方块重新创建图像
Nar*_*rks 5 algorithm math graphics
我正在尝试拍摄源图像,并使用重叠的单色方块在透明画布上重新创建它.目标是尽可能少地使用正方形.
换句话说,我正在拍摄一张空白的透明图像,并绘制各种颜色的正方形,直到我重新创建源图像,目标是尽可能少地使用正方形.
例如:
这是源图像.它有两种颜色:红色和绿色.我想只使用可能重叠的正方形来重新创建源图像.
理想的解决方案是一个大的红色正方形,然后在顶部绘制两个绿色正方形 - 这就是我希望我的算法找到的任何源图像 - 每个正方形的位置,大小,颜色和顺序.
我打算处理的目标图像是这样的:
(8倍放大)
它有1411个非透明像素(最坏情况),并且使用不使用重叠方块的蛮力解决方案,我使用1246个方块重新创建了图像.
我目前的解决方案是一种蛮力方法,其方式如下:
- 创建源图像中使用的所有颜色的列表.每个项目都是"图层".图层具有颜色,2D阵列表示像素.顺序很重要,但我不知道层需要的顺序,因此最初是任意的.
- 对于列表中的每个图层,初始化2D数组.每个元素对应于源图像中的像素.与图层所选颜色颜色相同的像素标记为"1".位于当前图层上方的图层中的像素标记为"不关心".所有其他像素都标记为"0".
- 使用一些算法处理每个图层,使用最小数量的正方形到达标记为"1"的每个像素,而不触摸任何标记为"0"的像素.
- 重新排列图层的顺序并返回到步骤2.对每个可能的图层组合执行此操作,然后检查哪个排序使用的总平方数最少.
有人在答复中可能有更好的解释; 但是对每个排列进行暴力测试是不可行的,因为我的目标图像有31种颜色(导致31种排列).
至于为什么我这样做？我正试图在游戏中创建一个图像(Starbound),我只能使用正方形.懒惰的解决方案是为每个像素使用一个正方形,但这只是太多的正方形.
小智 1
只是对可能的解决方案的建议。我没试过。
这是一种贪婪的方法。
对于每个像素，计算包含它的最大均匀正方形。
然后选择所有正方形中最大的一个并将其覆盖的所有像素标记为“覆盖”。
然后在所有未标记的像素中，选择最大的覆盖方块，依此类推，直到没有未标记的像素剩余。
领带并不重要，只需取任何最大的正方形并标记其像素即可。
更新：重叠提供了减少方块数量的机会。
考虑形状填充顺序的所有可能排列。首先在底层绘制的形状可以被其他一些形状（部分）隐藏。从顶层开始处理形状。当您处理形状以将每个像素与包含该形状的最大均匀正方形相关联时，请将所有覆盖的像素视为无关像素。
在给定的示例中，首先填充绿色方块；那么在填充红色方块时，绿色像素可以被认为是红色的，也可以不是红色的，这取决于方便性。
如果您无法尝试所有排列，请随机尝试。遗传算法或模拟退火等启发式方法可能会有所帮助。这里没有什么简单的事情。