扫描图像以查找矩形 [英] Scanning images for finding rectangles

问题描述

我正在尝试扫描一个恒定大小的图像，并在其中找到绘制的矩形。
矩形可以是任何尺寸，但只有红色。

I'm trying to scan a constant size image and locate the drawn rectangles in it. The rectangles can come in any size, but only red colored.

这是问题开始的不。

我将使用已编写的函数，稍后我会将其用作伪代码调用。

I'm gonna use an already written function, and I will use it as pseudo code calls later on my code logic.

Rectangle Locate（Rectangle scanArea）; //扫描给定扫描区域中的矩形。
如果找不到rectagle，则返回null。

我的逻辑是这样的：

使用 Locate（）函数查找第一个初始红色矩形，并将完整图像大小作为参数。
现在，划分其余区域，并递归扫描。
这个算法逻辑的要点是你永远不会检查已经检查过的区域，并且你不必使用任何条件，因为总是 scanArea 参数是你以前没有扫过的新区域（这要归功于分割技术）。
除法过程如下：当前找到的矩形的右侧区域，底部区域和左侧区域。

Find a first initial red rectangle using the Locate() function with the full image size as an argument. Now, divide the rest areas, and keep scanning recursively. The main point in this algorithm's logic is that you never check a checked already area, and you don't have to use any condition because always the scanArea parameter is a new area which you haven't scanned before (and that's thanks to the division technique). The division process is done like this: right area of the current found rectangle, the bottom area, and the left area.

这是一个图像，说明了处理。

（白色虚线矩形和黄色箭头不是图像的一部分，我仅为插图添加了它们。）
如您所见，一旦找到一个红色矩形，我会一直扫描它的右边，左下角。递归。

Here's an image which illustrates that process. (The white dotted rectangles and the yellow arrows are not part of the image, I've added them only for the illustration.) As you seen, once a red rectangle found, I keep scanning the right of it, bottom and left. Recursively.

所以这里是该方法的代码：

So here's the code for that method:

List<Rectangle> difList=new List<Rectangle>();

private void LocateDifferences(Rectangle scanArea)
{
    Rectangle foundRect = Locate(scanArea);
    if (foundRect == null)
        return; // stop the recursion.

    Rectangle rightArea = new Rectangle(foundRect.X + foundRect.Width, foundRect.Y, (scanArea.X + scanArea.Width) - (foundRect.X + foundRect.Width), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define right area.
    Rectangle bottomArea = new Rectangle(foundRect.X, foundRect.Y + foundRect.Height, foundRect.Width, (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define bottom area.
    Rectangle leftArea = new Rectangle(scanArea.X, foundRect.Y, (foundRect.X - scanArea.X), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define left area.

    difList.Add(rectFound);

    LocateDifferences(rightArea);
    LocateDifferences(bottomArea);
    LocateDifferences(leftArea);
}

到目前为止一切正常，它找到了每个红色矩形。
但有时，矩形保存为少数矩形。对于我来说显而易见的原因：
重叠矩形情况。

So far everything works alright, it does find every red rectangle. But sometimes, the rectangles saved as few rectangles. For a reason that obvious for me: overlapping rectangles case.

一个有问题的案例，例如：

A problematic case for example:

现在，在这种情况下，程序按计划找到第一个红色区域，但是，因为右边区域仅启动在完整的第二个区域的中间，它不会从第二个红色矩形的开头扫描！

Now, in this case, the program finds the first red region as planned, but then, since the right area starts only in the middle of the full second region, it does not scan from the beginning of the second red rectangle!

以类似的方式，我可以将区域划分为底部区域从 scanArea 的开头延伸到最后，如下所示：

但是现在我们在 foundRect r的右侧和左侧扫描重叠矩形时会遇到问题ectangle，例如，在这种情况下：

In a similar way, I can divide the areas so the bottom area stretches from the start of scanArea to the end, which would be like this: But now we would have a problem when scanning overlapping rectangles on the right and on the left of the foundRect rectangle, for example, in this kind of case:

我需要将每个矩形放在一个只有一块。
我想得到任何与我的代码逻辑相结合的帮助或建议 - 因为它工作得很好，但我认为在递归方法中只需要一两个额外的条件。我不知道该怎么办，我真的很感激任何帮助。

I need to get each rectangle in one piece only. I would like to get any help or suggestion combined with my code logic - because it works great but just needs a little one or two additional conditions in the recursion method I think. I'm not sure what to do and I would really appreciate any help.

如果事情不够清楚，请告诉我，我会解释它最好的我可以！
谢谢！

If something isn't clear enough, just tell and I'll explain it as best as I can! Thanks!

当然，这不是我面临的真正问题，它只是一个小小的示范，可以帮助我解决实际问题我正在研究（这是一个实时的互联网项目）。

Of course, this is not the real problem I'm facing against, it is just a little demonstration which could help me solve the real problem that I'm working on (which is a real-time internet project).

推荐答案

一种可以找到多个矩形的算法扫描图像一次不必复杂。与您现在正在做的主要区别在于，当您找到矩形的顶角时，您不应立即找到宽度和高度并存储矩形，而是暂时将其保留在未完成的矩形列表中，直到你遇到了它的底角。然后，可以使用此列表有效地检查每个红色像素是否是新矩形的一部分，或者您已经找到的那个。考虑这个例子：

An algorithm which can find multiple rectangles by scanning an image once doesn't have to be complicated. The main difference with what you're doing now is that when you find the top corner of a rectangle, you shouldn't immediately find the width and height and store the rectangle, but instead keep it in a list of unfinished rectangles temporarily, until you come across its bottom corner. This list can then be used to efficiently check whether each red pixel is part of a new rectangle, or one you've already found. Consider this example:

我们开始扫描顶部从底部到左到右。在第1行中，我们在第10位找到一个红色像素;我们继续扫描，直到找到下一个黑色像素（或到达行尾）;现在我们可以将它存储在未完成的矩形列表中{left，right，top}：

We start scanning top-to-bottom and left-to-right. In line 1, we find a red pixel at position 10; we continue scanning until we find the next black pixel (or reach the end of the line); now we can store it in a list of unfinished rectangles as {left,right,top}:

unfinished: {10,13,1}  

扫描下一行时，我们遍历未完成的矩形列表，所以我们知道何时期待一个矩形。当我们到达位置10时，我们找到了预期的红色像素，我们可以跳到位置14并迭代超过未完成的矩形。当我们到达位置16时，我们找到一个意外的红色像素，并继续到位置19的第一个黑色像素，然后将第二个矩形添加到未完成的列表：

When scanning the next line, we iterate over the list of unfinished rectangles, so we know when to expect a rectangle. When we reach position 10, we find a red pixel as expected, and we can skip to position 14 and iterate past the unfinished rectangle. When we reach position 16 we find an unexpected red pixel, and continue to the first black pixel at position 19, and then add this second rectangle to the unfinished list:

unfinished: {10,13,1},{16,18,2}  

在我们扫描第3到第5行后，我们得到这个清单：

After we've scanned lines 3 to 5, we get this list:

unfinished: {1,4,3},{6,7,3},{10,13,1},{16,18,2},{21,214}  

请注意，当我们在列表上进行迭代（使用例如链表）时，我们插入新找到的矩形，以便它们按从左到右的顺序排列。这样，我们只需要在扫描图像时一次查看一个未完成的矩形。

Note that we insert newly found rectangles while we're iterating over the list (using e.g. a linked list), so that they are in order from left to right. That way, we only ever have to look at one unfinished rectangle at a time while we're scanning the image.

在第6行，在通过前两个未完成的矩形后，我们在位置10处发现了一个意外的黑色像素;我们现在可以从未完成的列表中删除第三个矩形，并将其添加到完整矩形的数组中{left，right，top，bottom}：

On line 6, after passing the first two unfinished rectangles, we find an unexpected black pixel at position 10; we can now remove the third rectangle from the unfinished list, and add it to an array of complete rectangles as {left,right,top,bottom}:

unfinished: {1,4,3},{6,7,3},{16,18,2},{21,21,4}  
finished: {10,13,1,5}  

当我们到达第9行的末尾时，我们已经完成了所有的矩形在第5行之后未完成，但我们在第7行找到了一个新的矩形：

When we reach the end of line 9, we've completed all the rectangles that were unfinished after line 5, but we've found a new rectangle on line 7:

unfinished: {12,16,7}  
finished: {10,13,1,5},{16,18,2,5},{1,4,3,6},{6,7,3,8},{21,21,4,8}  

如果我们继续结束，结果是：

If we continue to the end, the result is:

unfinished:  
finished: {10,13,1,5},{16,18,2,5},{1,4,3,6},{6,7,3,8},{21,21,4,8},  
          {12,16,7,10},{3,10,10,13},{13,17,13,14},{19,22,11,14}  

如果此时还有任何未完成的矩形，则它们会与图像的下边缘交界，并且可以使用bottom = height-1完成。

If there are any unfinished rectangles left at this point, they border the bottom edge of the image, and can be completed with bottom=height-1.

请注意，跳过未完成的矩形意味着您只需要扫描黑色像素以及红色矩形的顶部和左侧边缘;在这个例子中，我们跳过了384个像素中的78个。

Note that skipping through unfinished rectangles means you only have to scan the black pixels and the top and left edge of the red rectangles; in the example we skipped over 78 of the 384 pixels.

点击此处，查看简单的C ++版本在rextester.com上采取行动（对不起，我不会说C＃）。

Click here to see a simple C++ version in action on rextester.com (sorry, I don't speak C#).

如果你发现C＃的链表实现不够快，你可以使用两个长度图像宽度的数组，当你发现在第y行的位置x1和x2之间的矩形顶部，将不完整的矩形存储为宽度[x1] = x2-x1和top [x1] = y，并在存储完整的矩形时将它们重置为零。

If you find that C#'s linked list implementation is not fast enough, you could use two arrays of length image width, and when you find the top of a rectangle between positions x1 and x2 on line y, store the incomplete rectangle as width[x1]=x2-x1 and top[x1]=y, and reset them to zero when you store the complete rectangle.

此方法可以找到小至1像素的矩形。如果存在最小尺寸，则可以使用更大的步骤扫描图像;最小尺寸为10x10，你只需要扫描大约1％的像素。

这篇关于扫描图像以查找矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！