dividing the irregular shape into decreasing rectangles

Question

I have to dividing the irregular shape into decreasing rectangles, one the largest and then decreasing rectangles. I just wondering if such problem is known in the coding world? How to do it?

The drawing is showing what I would like to achieve:

Answer 1

First rectangle can be found with this piece of code taken from here

Rect findMinRect(const Mat1b& src)
{
    Mat1f W(src.rows, src.cols, float(0));
    Mat1f H(src.rows, src.cols, float(0));

    Rect maxRect(0, 0, 0, 0);
    float maxArea = 0.f;

    for (int r = 0; r < src.rows; ++r)
    {
        for (int c = 0; c < src.cols; ++c)
        {
            if (src(r, c) == 0)
            {
                H(r, c) = 1.f + ((r > 0) ? H(r - 1, c) : 0);
                W(r, c) = 1.f + ((c > 0) ? W(r, c - 1) : 0);
            }

            float minw = W(r, c);
            for (int h = 0; h < H(r, c); ++h)
            {
                minw = min(minw, W(r - h, c));
                float area = (h + 1) * minw;
                if (area > maxArea)
                {
                    maxArea = area;
                    maxRect = Rect(Point(c - minw + 1, r - h), Point(c + 1, r + 1));
                }
            }
        }
    }

    return maxRect;
}

Usage is simple

Mat src, src_gray, src_bin;
cv::cvtColor(src, src_gray, COLOR_BGR2GRAY);
src_bin = (src_gray > 1) * 255;
Rect box = findMinRect(~src_bin);
rectangle(src, box, Scalar(0, 0, 255), 2);
cv::imshow("with_rectangle", src);
cv::waitKey();

But it's only first iteration. In next iteration we have to deal with at least 3 original image pieces, then with 9 pieces, and so on. I thing so... I will be grateful for any further suggestions.

Answer 2

I took Paul Gray's answer and wrote an iterative process that consumes the source to find all the areas from largest to smallest in pure c++, the filled portions of the matrix do not need to be a contiguous shape.

This is the rect class that I used, I found out after that there is already a RECT class in windef.h but whatever I had already made my own at that point.

class rect
{
public:
    uint32_t rowStart;
    uint32_t colStart;
    uint32_t height;
    uint32_t width;

    rect(uint32_t _rowStart, uint32_t _colStart, uint32_t _height, uint32_t _width);
    rect();
};

this is the algorithm Paul Gray posted in their answer redone without using openCV

bool findMinRect(std::vector<std::vector<bool>> *src, rect *retItem)
{
    bool contFlg = false;
    uint32_t srcRows = src->size();
    uint32_t srcCols = (*src)[0].size();

    std::vector<std::vector<float>> W;
    W.resize(srcRows);

    for (int row = 0; row < srcRows; row++) 
    {
        for (int col = 0; col < srcCols; col++)
        {
            W[row].push_back(0.f);
        }
    }

    std::vector<std::vector<float>> H;
    H.resize(srcRows);

    for (int row = 0; row < srcRows; row++) 
    {
        for (int col = 0; col < srcCols; col++)
        {
            H[row].push_back(0.f);
        }
    }

    rect maxRect(0, 0, 0, 0);
    float maxArea = 0.f;

    for (int r = 0; r < srcRows; ++r)
    {
        for (int c = 0; c < srcCols; ++c)
        {
            if ((*src)[r][c] == true)
            {
                H[r][c] = 1.f + ((r > 0) ? H[r-1][c] : 0);
                W[r][c] = 1.f + ((c > 0) ? W[r][c-1] : 0);
            }

            float minw = W[r][c];
            for (int h = 0; h < H[r][c]; ++h)
            {
                minw = min(minw, W[r - h][c]);
                float area = (h + 1) * minw;
                if (area > maxArea)
                {
                    maxArea = area;
                    maxRect = rect(r - h, c - minw + 1, (r + 1 - (r - h)), (c + 1 - (c - minw + 1)));
                    contFlg = true;
                }
            }
        }
    }

    *retItem = maxRect;
    return contFlg;
}

The shapeChk method below is a sanity check for the source matrix to make sure is rectangular, if not it identifies where the issue is.

int shapeChk(std::vector<std::vector<bool>> *src)
{
    uint32_t srcRows = src->size();

    if (srcRows == 0)
    {
        return -1;
    }

    uint32_t srcCols = (*src)[0].size();

    if (srcCols == 0)
    {
        return -2;
    }

    for (int row = 0; row < srcRows; row++)
    {
        if ((*src)[row].size() != srcCols)
        {
            return (-4 - (row + 1));
        }
    }
    return 0;
}

The following method removes the area found from the source matrix in order to rerun the findMinRect method.

void clearclump(std::vector<std::vector<bool>> *src, rect *area)
{
    for (int r = (area->rowStart); r < (area->rowStart + area->height); r++)
    {
        for (int c = (area->colStart); c < (area->colStart + area->width); c++)
        {
            (*src)[r][c] = false;
        }
    }
}

And here is the main method that puts it all together.

int areaClump(std::vector<std::vector<bool>> *src, std::vector<rect> *areas)
{
    rect retItem(1, 0, 0, 0);
    int err = shapeChk(src);
    if (err != 0)
    {
        return err;
    }

    while (findMinRect(src, &retItem))
    {
        areas->push_back(retItem);
        clearclump(src, &retItem);
    }
    return 0;
}

When you run areaClump the source matrix will be entirely consumed and will have all flase entries, while the areas vector contains all the found areas. Not sure if this works for your purposes or if it's even the best way to handle it, but it worked for me so I thought I'd share the results, may be it'll help someone.