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

这不是问题开始的地方。

我将使用一个已经编写好的函数，稍后我将在我的代码逻辑中将其用作伪代码调用。

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

我的逻辑是这样的:

使用 Locate() 函数以完整图像大小作为参数找到第一个初始红色矩形。 现在，划分其余区域，并递归扫描。 该算法逻辑的要点是您永远不会检查已检查的区域，并且您不必使用任何条件，因为 scanArea 参数始终是您之前未扫描过的新区域(这要归功于除法技术)。 划分过程是这样的:当前找到的矩形的右边区域，底部区域，左边区域。

这是一张说明该过程的图片。 (白色虚线矩形和黄色箭头不是图像的一部分，我添加它们只是为了说明。) 如您所见，一旦找到红色矩形，我就会继续扫描它的右侧、底部和左侧。递归地。

下面是该方法的代码:

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);
}

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

例如一个有问题的案例:

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

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

我只需要将每个矩形拼成一 block 。 我想得到任何帮助或建议结合我的代码逻辑 - 因为它工作得很好但我认为在递归方法中只需要一两个额外的条件。我不确定该怎么做，非常感谢任何帮助。

如果有什么地方不够清楚，请告诉我，我会尽我所能解释! 谢谢!

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

最佳答案

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

我们开始从上到下和从左到右扫描。在第 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 <vector>
#include <list>
#include <iostream>

struct rectangle {int left, right, top, bottom;};

std::vector<rectangle> locate(std::vector<std::vector<int>> &image) {
    std::vector<rectangle> finished;
    std::list<rectangle> unfinished;
    std::list<rectangle>::iterator current;
    int height = image.size(), width = image.front().size();
    bool new_found = false;                  // in C++17 use std::optional<rectangle>new_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<std::vector<int>> 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<rectangle> 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之间的矩形顶部时，将不完整的矩形存储为 width[x1]=x2-x1 和 top[x1]=y，并在存储完整的矩形时将它们重置为零。

此方法将找到小至 1 像素的矩形。如果有最小尺寸，您可以使用更大的步长扫描图像；最小尺寸为 10x10，您只需扫描大约 1% 的像素。

关于c# - 扫描图像寻找矩形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46757121/