Fit a rectangle within mask

I have a binary mask which always forms a rectangular-ish object like this:


What I need to do is find the rectangle that fits within this area, like the pink one here:


I tried using cv::findNonZero() and cv::boundingRect() like this:

cv::Mat points;
cv::findNonZero(output_mask, points);
cv::Rect r = cv::boundingRect(points);
cv::rectangle(output, r, cv::Scalar(0, 0, 255));

but of course that gives me a rectangle that includes the outside of what I want vs the inside rectangle:


I feel like I’m missing something obvious. :slight_smile:

I saw something like that on stack overflow just recently.

this problem might be an optimization problem, i.e. no single best solution, or the problem space is non-convex.

Here is what I did to solve this. Note that the code I was working on only runs once, so it didn’t need to be very efficient.

Start by inverting the mask, so the outside is white and the inside portion is black:

cv::Mat inverted_mask;
cv::bitwise_not(output_mask, inverted_mask);

Get the “outside” rectangle:

cv::Mat points;
cv::findNonZero(inverted_mask, points);
const cv::Rect outside_rect = cv::boundingRect(points);

Then I decrease this rectangle until all pixels are black (zero):

int step = 50;
auto inside_rect = outside_rect;
while (true)
    const auto count = cv::countNonZero(inverted_mask(inside_rect));
    if (count == 0)
        // we found a rectangle we can use!

    inside_rect.x            += step;
    inside_rect.y            += step;
    inside_rect.width        -= (step * 2);
    inside_rect.height       -= (step * 2);

Now at this point we have a usable “inside” rectangle. So one at a time, I increase and decrease the left, right, top, and bottom borders until I have the largest rectangle possible, checking each change with a call to cv::countNonZero() to decide if I’ve gone too far.