代码之家 › 专栏 › 技术社区 › Slashy

扫描图像以查找矩形

computer-vision image-processing algorithm c#

Slashy · 技术社区 · 7 年前

矩形可以有任何大小,但只有红色。

这是不问题从哪里开始。

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

Rectangle Locate(Rectangle scanArea); //扫描给定扫描区域中的矩形。如果未找到rectage,则返回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);
}

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

一个有问题的案例,例如:

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

以类似的方式,我可以划分区域,使底部区域从 扫描面积 最后是这样的: 但现在我们在扫描屏幕左右两侧重叠的矩形时会遇到问题 foundRect 矩形,例如,在这种情况下:

我只需要得到一个矩形。我希望结合我的代码逻辑得到任何帮助或建议,因为它工作得很好,但我认为递归方法只需要一个或两个附加条件。我不知道该做什么,我真的很感激任何帮助。

如果有什么不够清楚,就告诉我,我会尽可能地解释!

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

10 回复 | 直到 7 年前

m69 ''snarky and unwelcoming'' 6 年前

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

我们开始从上到下、从左到右扫描。在第1行中,我们在位置10处发现一个红色像素;我们继续扫描,直到找到下一个黑色像素(或到达行尾);现在我们可以将其存储在未完成的矩形列表中,如{left,right,top}:

unfinished: {10,13,1}

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

扫描第3行到第5行后,我们得到以下列表:

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

请注意,我们在遍历列表时插入了新找到的矩形(例如使用链表),以便它们从左到右排列。这样,在扫描图像时,我们每次只需要看一个未完成的矩形。

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}

如果此时还有任何未完成的矩形,它们将包围图像的底边,并且可以在底部=高度-1的情况下完成。

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

(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和顶部[x1]=y,并在存储完整的矩形时将其重置为零。

这种方法可以找到小到1像素的矩形。如果有最小尺寸,可以使用更大的步长扫描图像;最小尺寸为10x10,只需扫描大约1%的像素。

zubrabubra 7 年前

使用以下简单算法的最简单方法:

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

两个矩形的合并应该相当简单——它们应该有共享的边界。但给定的方法只适用于图像包含矩形且仅包含矩形的情况。对于更复杂的几何图形,最好使用逐行扫描算法进行区域检测,并在下一阶段进行形状类型识别。

Funk 7 年前

根据您的需求:

离开函数 Locate(Rectangle scanArea) 未触及。
使用递归算法扫描左/下/右(图)。

Id引入额外的类型参数 Side 到递归函数。

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

假设我们使用 Bottom 作为切割方向,我们可以通过创建一个包装器来提高效率(重新组装切割矩形),该包装器存储在 bottomArea s

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

List<Rectangle> leftList = new List<Rectangle>();
List<RectangleInfo> bottomList = new List<RectangleInfo>();
List<Rectangle> rightList = new List<Rectangle>();

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 => r.X + r.Width == rectInfo.Rectangle.X
                                   && r.Y == 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 => r.X == rectInfo.Rectangle.X + rectInfo.Rectangle.Width
                                    && r.Y == 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();
}

查找相邻矩形

可能存在多个具有相同形状的矩形 X 中的值 rightList (或 X + Width 中的值 leftList

根据元素的数量,在以下情况下,您也可以使用字典(用于更快的查找) 左列表 和 . 使用顶部交点作为关键点,然后检查 Height 在合并之前。

Michael Hudson 7 年前

遵循不更改Locate()函数而只是扩展现有逻辑的标准,我们需要在扫描后加入任何矩形。试试这个:

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

最后,启动扫描的主要功能

List<Tuple<Rectangle, Bool>> difList = new List<Tuple<Rectangle, Bool>();

// 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.

Hayyan 7 年前

我将用以下方法解决它:

我将从第一个像素开始读取图像。
注册位置 (x,y) 每个红色像素的。[放置 1 (x,y) 在具有相同图像大小的结果矩阵中]
成本为 O(nxm) 哪里 n 是行数和 m 是图像的列数。
矩形是连接的 1s 其中,每个x的总和(y)相同。这是一个必要的检查,以确保仅在存在斑点/圆(下图中的绿色段)的情况下捕捉矩形。。等

以下是结果矩阵的照片:

Yves Daoust 7 年前

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

有多种方法可以解决这个问题。一种是对图像行进行游程编码,并查找行与行之间的重叠。

另一种方法是扫描图像,并在每次遇到红色像素时执行整体填充(擦除整个矩形)。

另一种方法是扫描图像并在遇到红色像素时执行轮廓跟踪(标记每个轮廓像素,以便对斑点进行更多处理)。

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

DotNet Developer 7 年前

看看 this post flood fill algorithm 检测矩形。

tevemadar 7 年前

根据澄清意见,您现有的方法是一个完美的起点,我认为它应该使用一个辅助位图来操作,其中包含不应检查的像素(根本不检查,或者再次检查)。

假设大部分图像不是红色:

将辅助位图清除为0
设置x=y=0,扫描起始位置
从x、y方向扫描图像,按存储顺序进行操作以提高效率,找到图像上第一个红色像素,其中辅助位图为0
即矩形的角,使用现有方法(开始水平和垂直扫描等)查找其尺寸
记录矩形(x、y、w、h)
用1-s填充辅助位图中的矩形(x、y、w、h)
x+=w+1,从2开始继续(意味着它将检查新的x位置是否仍在图像尺寸内,并在必要时从0、y+1开始尝试,还可以识别扫描是否刚刚完成)

如果大部分图像被红色矩形覆盖,我会交换检入3(首先检查辅助位图,然后查看像素是否为红色),并扩展填充步骤(6),在左、右和底部方向各有一个像素(已经检查了顶部的像素)

就我个人而言,我更相信按内存顺序读取相邻像素的缓存效率,而不是跳转(由于分区的思想),但仍然要访问大多数像素,最后还要加入大量潜在的片段矩形。

shanif 7 年前

很抱歉,我没有阅读你的解决方案,因为我不确定你是想要一个好的解决方案,还是用这个解决方案来解决问题。

以红色通道为例(因为您说过只想检测红色矩形)
findContours公司
对于每个轮廓 3.2通过将轮廓的总面积与边界框的总面积进行比较,检查轮廓是否为矩形。

解决方案将根据输入图像的不同而变化。我希望我能帮助你。如果没有,请告诉我你需要什么样的帮助。

Peter 7 年前

你在图像上做每像素的线扫描。

如果像素up为黑色,像素left为黑色,但像素本身为红色向右走,直到它再次变黑(即右上方y2+1) 转到底部,找到黑色,即x2+1,这样就可以导出右,底部(x2,y2)

将x1、y1、x2、y2存储在列表结构或类中将刚找到的矩形涂成黑色,然后继续进行线扫描