将非矩形图像分割成相同大小的块

Question

5

我正在寻找一种算法，用于将非矩形图像（即透明图像）分块为16x16像素大小的块。这些块可以重叠，但目标是获得最少的块数。

示例:

原始图像:

目标图像:

摘要：

谢谢您的帮助！

- Benjamin Schulte

这看起来像是“装箱问题”。 - Spektre

1

通过这个问题，您可以找到这篇论文，它将您的问题确定为直角多边形p中心问题。（似乎在学术界已经被充分研究，但很难找到现成的算法。） - M Oehm

@MOehm：这些链接可能很有用，但这似乎不是矩形p中心问题，根据那篇论文，该问题涉及确定最小可能的d，以便使用给定数量的d * d正方形覆盖给定点集。在这里，d是固定的，而p是未知的。 - j_random_hacker

看起来我可能漏掉了什么，但是是否还有其他的约束需要最小化/最大化呢？从列出的条件来看，答案似乎是1；覆盖所有像素的最小块。我猜测还有第二个约束，即块中透明像素的总数应该被最小化或者类似的东西。这样对吗？ - Dave Durbin

@j_random_hacker：是的，你说得对。当我看到帖子中的图片时，我立刻想到地图是如何在地图集中分成页面的，所以意大利的图像对我来说非常恰当。一旦建立了联系，就很难打破它。 - M Oehm

@DaveDurbin：块的大小是固定的并且已经给定。在这个例子中，它是16像素。 - M Oehm

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Answer 1

这是集合覆盖问题的一个特殊情况。你可以尝试使用整数规划求解器，但可能存在太多可能的块。整数规划适用于列生成/分支定价，但这是一种高级技术，需要一些实验才能正确使用。

我认为你可以使用贪心算法，重复选择覆盖尽可能多像素的块，包括一个边界像素。