arrays - 在二进制矩阵中找到不(必要)与图像边界对齐的最大矩形

Question

我正在使用 this solution在二进制矩阵中找到与图像边界对齐的矩形。假设现在我想找到一个不与图像边框对齐的矩形，并且我不知道它的方向；找到它的最快方法是什么？

为了示例，让我们寻找一个仅包含 1 的矩形。例如:

1 1 1 1 0 0 0 0 0 1 0 0 1 1 1
0 1 1 1 1 1 0 0 0 1 0 0 1 1 0
0 0 0 1 1 1 1 1 0 1 0 0 1 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 1 0

然后是我描述的解决方案中描述的算法above只会找到大小为 6 (3x2) 的矩形。我想找一个倾斜的更大的矩形；我们可以清楚地看到至少大小为 10 或更大的矩形...

我正在使用 C/C++，但任何语言或伪代码的算法描述都会对我有很大帮助。

更多细节:

• 图片中可以有多个矩形:我只需要最大的一个
• 矩形不是图像中的漂亮矩形(我稍微修改了上面的示例)
• 我处理大图像 (1280x1024)，所以我正在寻找最快的解决方案(蛮力 O(n³) 算法会非常慢)
• (可选)如果解决方案可以并行化，那就更好了(然后我可以使用 GPU、SIMD 等进一步提升它)

Answer 1

对于这个问题，我只有部分答案，对于我提出的建议，我只有一些关于复杂性或速度的想法。

蛮力

我看到的第一个想法是利用您的问题是离散的这一事实来实现围绕图像中心的旋转和重复您已使用的算法以找到轴对齐的解决方案。

这有一个缺点，即检查大量候选轮换。但是，这项检查可以并行进行，因为它们彼此独立。这可能仍然很慢，尽管实现它(应该不会太难)并且一旦并行化就会为问题速度提供更明确的答案。

请注意，您的工作空间是一个离散矩阵，只有一个有限旋转数浏览。

其他方法

我看到的第二种解决方案是:

1. 缩减基础矩阵以便分离连接的组件 [1](对应于您感兴趣的值集)。
2. 对于这些较小的矩阵中的每一个——请注意它们可能会重叠，具体取决于分布——找到最小方向边界框 您感兴趣的值(value)集。
3. 对于其中的每一个，旋转您的矩阵，以便最小方向的边界框现在与轴对齐。
4. 启动算法，您已经找到最大轴对齐矩形，该矩形仅包含您的值集中的值。
5. 此算法找到的解决方案将是从所有连通分量中获得的最大矩形。

第二个解决方案可能会给你一个解决方案的近似值，但我相信它可能值得尝试。

供引用

我找到的最大/最大空矩形问题的唯一解决方案是轴对齐的。我已经看到许多与此问题在 2D 连续空间上的定向版本相对应的未解决问题。

编辑:

[1]因为我们要的是分离连通分量，所以如果有一定程度的重叠，你应该像下面的例子那样做:

0 1 0 0
0 1 0 1
0 0 0 1

应该分为:

0 0 0 0
0 0 0 1
0 0 0 1

和

0 1 0 0
0 1 0 0
0 0 0 0

请注意，我保留了矩阵的原始尺寸。我这样做是因为我从你的帖子中猜测它有一定的重要性，并且不会找到一个远离边界扩展的矩形作为解决方案(即我们不能仅仅假设边界之外有零值)。

编辑#2:

是否保留矩阵维度的选择是有争议的，因为它不会直接影响算法。

但是，值得注意的是，如果对应于连通分量的矩阵在非零值上不重叠，您可以选择“就地”存储这些矩阵。

您还需要考虑这样一个事实，如果您希望将矩形的坐标作为输出返回，为每个连接的组件创建一个具有不同维度的矩阵，这将迫使您将新创建的矩阵的坐标存储在原来的一个(其实一个点，比如左上角的那个就够了)。