扫描图像以查找矩形

Question

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

这不是问题的起点.

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

Rectangle Locate(Rectangle scanArea); //扫描给定扫描区域中的矩形.如果未找到rectagle,则返回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,例如,在这种情况下:

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

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

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

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 <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之间找到矩形的顶部时,将不完整的矩形存储为宽度[x1] = x2-x1和top [x1] = y,并在存储完整矩形时将它们重置为零.

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