Scanning images for finding rectangles

Question

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.

This is not where the problem starts.

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); // scans for a rectangle in a given scan area. if no rectagle is found,returns null.

My logic was like this:

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!

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

Answer 1

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:

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}  

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}  

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.

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}  

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}  

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.

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.

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

(Rextester seems to be hacked at the moment, so I've removed the link and pasted the C++ code here.)

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

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.

This method will find rectangles as small as 1 pixel. If there is a minimum size, you can scan the image using greater steps; with a minimum size of 10x10 you'd only have to scan around 1% of the pixels.