我正在尝试将多张图片合并成一张大图,并寻找一种最优算法来确定它们的位置。这些图片不能旋转或调整大小,但它们在结果图像中的位置并不重要。
最优的打包是困难的,但根据您问题域的细节,可能有简化方法可用。以下是一些想法:
如果您可以将位图划分为相等大小的瓷砖,则打包就很容易。然后,按需从瓷砖重新组装位图。
将图像按大小从大到小排序,然后对于每个图像,使用贪心分配器选择适合该图像的第一个可用子矩形。
使用遗传算法。从几个随机选择的布局开始。根据它们的紧密程度对它们进行评分。混合来自得分最高的解决方案,并迭代直到达到可接受的分数。
我为这个问题创建了一个算法,实际上它是NP-Hard Bin packing问题的一种变体,但是箱子大小是无限大的。
你可以尝试找一些相关文章并尝试优化算法,但最终仍将是一种暴力尝试每种可能性并尝试最小化结果箱子尺寸的方法。
如果你不需要最佳解,而只需要一个解,你可以避免暴力枚举所有组合。我曾经创建过一个做到这点的程序。
描述:
Images: array of the input images
ResultMap: 2d array of Booleans
FinalImage: large image
ResultMap用于快速检查当前FinalImage上是否可以放置图像。您可以优化它以使用int32,并为每个像素使用一个位。这将减少内存并提高性能,因为您可以一次检查32位(使用掩码)。但是,这将变得更加困难,因为您必须考虑需要制作的图像边缘的掩码。
现在我将描述“算法”的真正循环。
对于数组中的每个图像,请尝试找到一个适合它的位置。您可以编写一个循环,该循环将查看ResultMap数组并查找false值,然后开始查看是否在放置图像的大小的两个方向上仍保持false。这不是最优的解决方案,但可以以相当优化的方式解决问题(特别是如果有一些较小的图像来填补最后的空隙)。