扫描图像以查找矩形

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

这不是问题的起点。

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

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

我的逻辑是这样的：

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

这是一个说明该过程的图像。 （白色虚线矩形和黄色箭头不是图像的一部分，我只是为了插图而添加它们。）如您所见，一旦发现红色矩形，我会一直扫描它的右边，左下角。 递归。

所以这是该方法的代码：

 List difList=new List(); 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); } 

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

例如一个有问题的案例：

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

以类似的方式，我可以划分区域，使底部区域从scanArea的开始scanArea到结束，这将是这样的： 但是现在我们在foundRect矩形的右侧和左侧扫描重叠矩形时会出现问题，例如，在这种情况下：

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

如果事情不够清楚，那就告诉我，我会尽可能地解释它！ 谢谢！

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

Answer 1

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

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

 unfinished: {10,13,1} 

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

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

在我们扫描第3到第5行之后，我们得到了这个列表：

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

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

在第6行，在通过前两个未完成的矩形后，我们在位置10处发现了意外的黑色像素; 我们现在可以从未完成的列表中删除第三个矩形，并将其添加到完整矩形的数组中{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行找到了一个新的矩形：

 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} 

如果我们继续到最后，结果是：

 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完成。

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

单击[此处]以查看rextester.com上的简单C ++版本（抱歉，我不会说C＃）。

（Rextester目前似乎被黑了，所以我删除了链接并在此处粘贴了C ++代码。）

 #include  #include  #include  struct rectangle {int left, right, top, bottom;}; std::vector locate(std::vector> &image) { std::vector finished; std::list unfinished; std::list::iterator current; int height = image.size(), width = image.front().size(); bool new_found = false; // in C++17 use std::optionalnew_rect and check new_rect.has_value() for (int y = 0; y < height; ++y) { current = unfinished.begin(); // iterate over unfinished rectangles left-to-right for (int x = 0; x < width; ++x) { if (image[y][x] == 1) { // red pixel (1 in mock-up data) if (current != unfinished.end() && x == current->left) { x = current->right; // skip through unfinished rectangle ++current; } else if (!new_found) { // top left corner of new rectangle found new_found = true; current = unfinished.insert(current, rectangle()); current->left = x; } } else { // black pixel (0 in mock-up data) if (new_found) { // top right corner of new rectangle found new_found = false; current->right = x - 1; current->top = y; ++current; } else if (current != unfinished.end() && x == current->left) { current->bottom = y - 1; // bottom of unfinished rectangle found finished.push_back(std::move(*current)); current = unfinished.erase(current); } } } // if there is still a new_rect at this point, it borders the right edge } // if there are unfinished rectangles at this point, they border the bottom edge return std::move(finished); } int main() { std::vector> image { // mock-up for image data {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,0}, {0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,0}, {0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,0}, {0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,0}, {0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0}, {0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0}, {0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0}, {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,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0}, {0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0}, {0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0}, {0,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} }; std::vector rectangles = locate(image); std::cout << "left,right,top,bottom:\n"; for (rectangle r : rectangles) { std::cout << (int) r.left << "," << (int) r.right << "," << (int) r.top << "," << (int) r.bottom << "\n"; } return 0; } 

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

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

Answer 2

最简单的方法使用简单的算法，如：

 function find(Image): Collection of Rects core_rect = FindRects(Image) split(core_rect) -> 4 rectangles (left-top, left-bottom, right-top, right-bottom) return Merge of (find(leftTop), find(leftBottom), ...) function findAll(Image): Collection of Rects rects <- find(Image) sort rectangles by X, Y merge rectangles sort rectangles by Y, X merge rectangles return merged set 

两个矩形的合并应该相当简单 - 它们应该具有共享边界。 但是只有在图像包含矩形和仅矩形的情况下，给定方法才有效。 在更复杂的几何图形的情况下，使用逐行扫描算法进行区域检测和下一阶段形状类型识别可能更好。

Answer 3

根据您的要求：

• 保持函数Locate(Rectangle scanArea)不变。
• 使用递归算法扫描左/下/右（图）。

我将在递归函数中引入一个类型为Side的额外参数。

 internal enum Side : byte { Left, Bottom, Right } 

假设我们使用Bottom作为“切割”方向，我们可以通过创建一个包装器来提高效率（重新组装切割的矩形），该包装器存储bottomArea找到的矩形的额外信息。

 internal class RectangleInfo { public RectangleInfo(Rectangle rect, bool leftOverlap, bool rightOverlap) { Rectangle = rect; LeftOverlap = leftOverlap; RightOverlap = rightOverlap; } public Rectangle Rectangle { get; set; } public bool LeftOverlap { get; set; } public bool RightOverlap { get; set; } } 

为了加快查找速度，您还可以将leftArea s和rightArea s中的切割矩形划分为单独的列表。 这会将您的示例代码转换为：

 List difList = new List(); List leftList = new List(); List bottomList = new List(); List rightList = new List(); private void AccumulateDifferences(Rectangle scanArea, Side direction) { Rectangle foundRect = Locate(scanArea); if (foundRect == null) return; // stop the recursion. switch (direction) { case Side.Left: if (foundRect.X + foundRect.Width == scanArea.X + scanArea.Width) leftList.Add(foundRect); else difList.Add(foundRect); break; case Side.Bottom: bottomList.Add(new RectangleInfo(foundRect, foundRect.X == scanArea.X, foundRect.X + foundRect.Width == scanArea.X + scanArea.Width)); break; case Side.Right: if (foundRect.X == scanArea.X) rightList.Add(foundRect); else difList.Add(foundRect); break; } Rectangle leftArea = new Rectangle(scanArea.X, foundRect.Y, (foundRect.X - scanArea.X), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define left 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 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. AccumulateDifferences(leftArea, Side.Left); AccumulateDifferences(bottomArea, Side.Bottom); AccumulateDifferences(rightArea, Side.Right); } private void ProcessDifferences() { foreach (RectangleInfo rectInfo in bottomList) { if (rectInfo.LeftOverlap) { Rectangle leftPart = leftList.Find(r => rX + r.Width == rectInfo.Rectangle.X && rY == rectInfo.Rectangle.Y && r.Height == rectInfo.Rectangle.Height ); if (leftPart != null) { rectInfo.Rectangle.X = leftPart.X; leftList.Remove(leftPart); } } if (rectInfo.RightOverlap) { Rectangle rightPart = rightList.Find(r => rX == rectInfo.Rectangle.X + rectInfo.Rectangle.Width && rY == rectInfo.Rectangle.Y && r.Height == rectInfo.Rectangle.Height ); if (rightPart != null) { rectInfo.Rectangle.X += rightPart.Width; rightList.Remove(rightPart); } } difList.Add(rectInfo.Rectangle); } difList.AddRange(leftList); difList.AddRange(rightList); } private void LocateDifferences(Rectangle scanArea) { AccumulateDifferences(scanArea, Side.Left); ProcessDifferences(); leftList.Clear(); bottomList.Clear(); rightList.Clear(); } 

寻找相邻的矩形

有可能多个矩形在rightList存在相同的X值（或rightList X + Width值），因此我们需要在找到可能的匹配时validation交集。

在leftList和rightList情况下，根据元素的数量，您还可以使用字典（以便更快地查找）。 使用顶部交叉点作为键，然后在合并之前检查Height 。

Answer 4

遵循不更改Locate（）函数但只扩展现有逻辑的标准，我们需要在扫描后加入任何rects。 试试这个：

首先稍微修改LocateDifferences（）函数以跟踪可能需要连接的矩形。

 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. if (foundRect.X == scanArea.X || foundRect.Y == scanArea.Y || (foundRect.X + foundRect.Width == scanArea.X + scanArea.Width) || (foundRect.Y + foundRect.Height == scanArea.Y + scanArea.Height)) { // edge may extend scanArea difList.Add(Tuple.Create(foundRect, false)); } else { difList.Add(Tuple.Create(foundRect, true)); } LocateDifferences(rightArea); LocateDifferences(bottomArea); LocateDifferences(leftArea); } 

我还添加了这两种方法：

 // JoinRects: will return a rectangle composed of r1 and r2. private Rectangle JoinRects(Rectangle r1, Rectangle r2) { return new Rectangle(Math.Min(r1.X, r2.X), Math.Min(r1.Y, r2.Y), Math.Max(r1.Y + r1.Width, r2.Y + r2.Width), Math.Max(r1.X + r1.Height, r2.X + r2.Height)); } // ShouldJoinRects: determines if the rectangles are connected and the height or width matches. private bool ShouldJoinRects(Rectangle r1, Rectangle r2) { if ((r1.X + r1.Width + 1 == r2.X && r1.Y == r2.Y && r1.Height == r2.Height) || (r1.X - 1 == r2.x + r2.Width && r1.Y == r2.Y && r1.Height == r2.Height) || (r1.Y + r1.Height + 1 == r2.Y && r1.X == r2.X && r1.Width == r2.Width) || (r1.Y - 1 == r2.Y + r2.Height && r1.X == r2.X && r1.Width == r2.Width)) { return true; } else { return false; } } 

最后你的主要function开始扫描

 List> difList = new List(); // HERE: fill our list by calling LocateDifferences LocateDifferences(); var allGood = difList.Where(t => t.Item2 == true).ToList(); var checkThese = difList.Where(t => t.Item2 == false).ToArray(); for (int i = 0; i < checkThese.Length - 1; i++) { // check that its not an empty Rectangle if (checkThese[i].IsEmpty == false) { for (int j = i; j < checkThese.Length; j++) { // check that its not an empty Rectangle if (checkThese[j].IsEmpty == false) { if (ShouldJoinRects(checkThese[i], checkThese[j]) { checkThese[i] = JoinRects(checkThese[i], checkThese[j]); checkThese[j] = new Rectangle(0,0,0,0); j = i // restart the inner loop in case we are dealing with a rect that crosses 3 scan areas } } } allGood.Add(checkThese[i]); } } //Now 'allGood' contains all the rects joined where needed. 

Answer 5

我会用以下方式解决它：

1. 我将从第一个像素开始读取图像。
2. 记录每个红色像素的位置(x,y) 。 [将1 (x,y)放在具有相同图像大小的结果矩阵中]
3. cost是O(nxm) ，其中n是行数， m是图像的列数。
4. 矩形是连接的1s的集合，其中sum（y）对于每个x是相同的。 这是一个必要的检查，以确保只有在有斑点/圆圈（下图中的绿色部分）时才捕获矩形。等等。

下面是结果矩阵的照片：

Answer 6

没有必要重新发明轮子。 这是一个连接组件标签问题。

https://en.wikipedia.org/wiki/Connected-component_labeling

有各种方法可以解决它。 一种是通过对图像行进行行程编码并找到行与行之间的重叠。

另一种方法是每次遇到红色像素时扫描图像并执行泛光填充（擦除整个矩形）。

另一种方法是扫描图像并在遇到红色像素时执行轮廓跟踪（并标记每个轮廓像素，以便更多地处理blob）。

所有这些方法都适用于任意形状，您可以根据矩形的特定形状进行调整。

Answer 7

看看这篇文章 。 那里解决了类似的问题。 我建议使用泛洪填充算法来检测矩形。

Answer 8

根据澄清评论，你现有的方法是一个完美的起点，我认为它应该使用一个辅助位图来操作，其中包含不应该检查哪些像素（根本没有）。

假设大部分图像不是红色的：

1. 清除辅助位图为0
2. 设置x = y = 0，扫描的起始位置
3. 扫描图像从x，y，按存储顺序进行以提高效率，找到辅助位图为0的图像上的第一个红色像素
4. 这是矩形的一角，使用现有方法找到它的尺寸（开始水平扫描和垂直扫描等）
5. 记录矩形（x，y，w，h）
6. 用1-s填充辅助位图中的矩形（x，y，w，h）
7. x + = w + 1，从2继续（暗示它将检查新的x位置是否仍然在图像尺寸内并且从0开始尝试，如果需要则从y + 1开始，并且还识别是否刚刚完成扫描）

如果大部分图像都被红色矩形覆盖，我会交换3中的检查（首先检查辅助位图，然后查看像素是否为红色），并向右，向左延伸一个像素填充步骤（6）和底部方向（已经检查过顶部的像素）

就个人而言，我更多地相信在内存顺序中读取相邻像素的缓存效率，而不是跳跃（由于分区的想法），但仍然访问大多数像素加上必须在最后加入潜在的大量片段矩形。

Answer 9

我很抱歉，但我没有阅读您的解决方案，因为我不确定您是否需要一个好的解决方案或解决该解决方案的问题。

使用现有构建块的简单解决方案（如OpenCV，我不知道是否有c＃的端口）是：

1. 采取红色通道（因为你说你只想检测红色矩形）
2. findContours
3. 对于每个轮廓3.1，取其边界框3.2通过比较其总面积与边界框的总面积来检查轮廓是否为矩形。

解决方案将根据输入图像的多样性而改变。 我希望我帮助你。 如果没有，请指导我你想要什么样的帮助。

Answer 10

您可以在图像上对每个像素进行线扫描。

如果像素向上是黑色而像素左边是黑色但是像素本身是红色那么你就离开了上角（x1，y1）。 向右移动直到它的黑色（这是右上方y2 + 1）转到底部找到黑色那是x2 + 1所以你可以得到右边，底部（x2，y2）

将x1，y1，x2，y2存储在列表结构或类中，将刚刚找到的矩形绘制为黑色，并连续扫描