发现最大的矩形不是（必要的）与二元矩阵图像边界上对齐 [英] find largest rectangle not (necessary) aligned with image boundary in binary matrix

问题描述

我使用的<一个href="http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix">this解决方案找到矩形与图像边界二元矩阵排列。假设现在我想找到不与图像边界对齐的矩形，我不知道它的方向;这将是找到它的最快方法是什么？

I am using this solution to find rectangles aligned with the image border in a binary matrix. Suppose now I want to find a rectangle that is not aligned with the image border, and I don't know its orientation; what would be the fastest way to find it?

有关着想的例子，让我们来看看为只含1的矩形。例如：

For the sake of the example, let's look for a rectangle containing only 1's. For example:

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

然后，在该溶液中所述的算法予描述<一href="http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix">above只会发现大小6（3×2）的矩形。我想找到的是倾斜较大的矩形;我们可以清楚地看到至少有大小10个或更多...

Then the algorithm described in the solution I described above would only find a rectangle of size 6 (3x2). I would like to find a bigger rectangle that is tilted; we can clearly see a rectanble of at least size 10 or more...

我在C / C ++的工作，但一个算法描述的任何语言​​或伪code将帮助我很多东西。

I am working in C/C++ but an algorithm description in any language or pseudo-code would help me a lot.

更多的细节：

• 可存在图像中一个以上的矩形：我所需要的最大的唯一
• 矩形不是图像在一个美丽的矩形（我适应我的例子上面一点点）
• 在我工作的大图像（1280×1024），所以我在寻找最快的解决方法（蛮力O（n³）算法会很慢）
• （可选），如果该解决方案可以parallellized，这是一个加号（然后我就可以提高它更多使用GPU，SIMD，...）

推荐答案

我只是有这个问题要问我的建议了部分答案，只有在复杂性或速度的一些想法。

I only have a partial answer for this question, and only a few thoughts on complexity or speed for what I propose.

蛮力

这是我看到的第一个想法是使用的事实，你的问题是离散实施的的围绕图像的中心旋转的和的重复你已经为了寻找轴线对准解决方案中使用的算法的

The first idea that I see is to use the fact that your problem is discrete to implement a rotation around the center of the image and repeat the algorithm you already use in order to find the axis aligned solution.

这具有的缺点的的检查一大堆候选旋转的。然而，这种检查的的可以并行完成，因为他们是indepedant彼此的。这可能仍然很慢，但实现它（不要太用力），并会提供一个更明确的答案，一旦并行化问题的速度。

This has the downside of checking a whole lot of candidate rotations. However, this check can be done in parallel since they are indepedant of one another. This is still probably very slow, although implementing it (shouldn't be too hard) and would provide a more definite answer to the question speed once parallelized.

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

Note that your work-space being a discrete matrix, there is only a finite number of rotation to browse through.

其他方法

我看到的第二个解决方案是：

The second solution I see is:

1. 要砍掉你的基地矩阵，从而 分离连接组件[1] 的（对应的值设置你感兴趣）。
2. 对于那些规模较小的矩阵每个人 - 的注意，他们可能会根据分布重叠的 - 找到的的最小的方向包围盒的的值设置你感兴趣的问题。
3. 仍然为每一个那些， 旋转你的矩阵，从而最小方向包围盒现在是轴对齐的
4. 启动算法，你已经找到的的最大轴对准的距离值集仅包含值矩形。
5. 在该算法找到的解决办法是的的所有连接的组件所获得的最大的矩形的

1. To cut down your base matrix so as to separate the connected components [1] (corresponding to the value set you're interested in).
2. For each one of those smaller matrices -- note that they may be overlapping depending on the distribution -- find the minimum oriented bounding box for the value set you're interested in.
3. Still for each one of those, rotate your matrix so that the minimum oriented bounding box is now axis-aligned.
4. Launch the algorithm you already have to find the maximum axis-aligned rectangle containing only values from your value set.
5. The solution found by this algorithm would be the largest rectangle obtained from all the connected components.

这第二个解决方案将可能给你soluiton的近似值，但我相信它可能被证明是值得尝试的。

This second solution would probably give you an approximation of the soluiton, but I believe it might prove to be worth trying.

仅供参考

这是我发现的最大/最大空矩形的问题的唯一解决方案是轴对齐。我已经看到了对应于这个问题的二维连续空间的导向版本许多悬而未决的问题。

The only solutions that I have found for the problem of the maximum/largest empty rectangle are axis-aligned. I have seen many unanswered questions corresponding to the oriented version of this problem on 2D continuous space.

编辑：

[1] 因为我们要的是分开连接的组件，如果有一定程度的重叠，你应该做如下面的例子：

[1] Since what we want is to separate the connected component, if there is a degree of overlap, you should do as in the following example:

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

请注意，我不停的矩阵的原始尺寸。我这样做，因为我从您的文章，猜测它有一定的重要性，一个矩形的边界扩大渐行渐远不会找到一个解决方案（例如，我们不能只是假设有境外零值）。

Note that I kept the original dimensions of the matrix. I did that because I'm guessing from your post it has some importance and that a rectangle expanding further away from the boundaries would not be found as a solution (i.e. that we can't just assume there are zero values beyond the border).

编辑＃2：

与否保持矩阵的维数的选择是有争议的，因为它不会直接影响该算法

The choice of whether or not to keep the matrix dimensions is debatable since it will not directly influence the algorithm.

然而，值得注意的是，如果对应于连接的组件的矩阵不上的非零值重叠，可以选择存储就地那些矩阵

However, it is worth noting that if the matrices corresponding to connected components do not overlap on non-zero values, you may choose to store those matrices "in-place".

您还需要考虑的是，如果你希望返回作为输出的矩形的坐标，创建具有不同尺寸的矩阵为每个连接的组件，这将迫使你要保存新创建的矩阵中的坐标原来的（实际上，一个点，说，例如在左上方的，应该是足够了）。

You also need to consider the fact that if you wish to return as output the coordinates of the rectangle, creating a matrix with different dimensions for each connected component, this will force you to store the coordinates of your newly created matrix in the original one (actually, one point, say for instance the up-left one, should be enough).

这篇关于发现最大的矩形不是（必要的）与二元矩阵图像边界上对齐的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！