How to adapt or resize a rectangle inside an object without including (or with a few numbers) of background pixels?

Question

After I applied thresholding and finding the contours of the object, I used the following code to get the straight rectangle around the object (or the rotated rectangle inputting its instruction):

img = cv2.imread('image.png')
imgray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
ret,thresh = cv2.threshold(imgray,127,255,cv2.THRESH_BINARY)
# find contours 
contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
cnt = contours[0]
# straight rectangle
x,y,w,h = cv2.boundingRect(cnt)
img= cv2.rectangle(img,(x,y),(x+w,y+h),(0,255,0),2)

see the image

Then I have calculated the number of object and background pixels inside the straight rectangle using the following code:

# rectangle area (total number of object and background pixels inside the rectangle)
area_rect = w*h
# white or object pixels (inside the rectangle)
obj = cv2.countNonZero(imgray)
# background pixels (inside the rectangle)
bac = area_rect - obj

Now I want to adapt the rectangle of the object as a function of the relationship between the background pixel and those of the object, ie to have a rectangle occupying the larger part of the object without or with less background pixel, for example:

How do I create this?

Answer 1

This problem can be stated as the find the largest rectangle inscribed in a non-convex polygon.

An approximate solution can be found at this link.

This problem can be formulated also as: for each angle, find the largest rectangle containing only zeros in a matrix, explored in this SO question.

My solution is based on this answer. This will find only axis aligned rectangles, so you can easily rotate the image by a given angle and apply this solution for every angle. My solution is C++, but you can easily port it to Python, since I'm using mostly OpenCV function, or adjust the solution in the above mentioned answer accounting for rotation.

Here we are:

#include <opencv2\opencv.hpp>
#include <iostream>
using namespace cv;
using namespace std;


// https://stackoverflow.com/a/30418912/5008845
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;
}


RotatedRect largestRectInNonConvexPoly(const Mat1b& src)
{
    // Create a matrix big enough to not lose points during rotation
    vector<Point> ptz;
    findNonZero(src, ptz);
    Rect bbox = boundingRect(ptz); 
    int maxdim = max(bbox.width, bbox.height);
    Mat1b work(2*maxdim, 2*maxdim, uchar(0));
    src(bbox).copyTo(work(Rect(maxdim - bbox.width/2, maxdim - bbox.height / 2, bbox.width, bbox.height)));

    // Store best data
    Rect bestRect;
    int bestAngle = 0;

    // For each angle
    for (int angle = 0; angle < 90; angle += 1)
    {
        cout << angle << endl;

        // Rotate the image
        Mat R = getRotationMatrix2D(Point(maxdim,maxdim), angle, 1);
        Mat1b rotated;
        warpAffine(work, rotated, R, work.size());

        // Keep the crop with the polygon
        vector<Point> pts;
        findNonZero(rotated, pts);
        Rect box = boundingRect(pts);
        Mat1b crop = rotated(box).clone();

        // Invert colors
        crop = ~crop; 

        // Solve the problem: "Find largest rectangle containing only zeros in an binary matrix"
        // https://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-n%C3%97n-binary-matrix
        Rect r = findMinRect(crop);

        // If best, save result
        if (r.area() > bestRect.area())
        {
            bestRect = r + box.tl();    // Correct the crop displacement
            bestAngle = angle;
        }
    }

    // Apply the inverse rotation
    Mat Rinv = getRotationMatrix2D(Point(maxdim, maxdim), -bestAngle, 1);
    vector<Point> rectPoints{bestRect.tl(), Point(bestRect.x + bestRect.width, bestRect.y), bestRect.br(), Point(bestRect.x, bestRect.y + bestRect.height)};
    vector<Point> rotatedRectPoints;
    transform(rectPoints, rotatedRectPoints, Rinv);

    // Apply the reverse translations
    for (int i = 0; i < rotatedRectPoints.size(); ++i)
    {
        rotatedRectPoints[i] += bbox.tl() - Point(maxdim - bbox.width / 2, maxdim - bbox.height / 2);
    }

    // Get the rotated rect
    RotatedRect rrect = minAreaRect(rotatedRectPoints);

    return rrect;
}



int main()
{
    Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE);

    // Compute largest rect inside polygon
    RotatedRect r = largestRectInNonConvexPoly(img);

    // Show
    Mat3b res;
    cvtColor(img, res, COLOR_GRAY2BGR);

    Point2f points[4];
    r.points(points);

    for (int i = 0; i < 4; ++i)
    {
        line(res, points[i], points[(i + 1) % 4], Scalar(0, 0, 255), 2);
    }

    imshow("Result", res);
    waitKey();

    return 0;
}

The result image is:

NOTE

I'd like to point out that this code is not optimized, so it can probably perform better. For an approximized solution, see here, and the papers reported there.

This answer to a related question put me in the right direction.

Answer 2

There's now a python library calculating the maximum drawable rectangle inside a polygon.

Library: maxrect

---

Install through pip:

pip install git+https://${GITHUB_TOKEN}@github.com/planetlabs/maxrect.git

Usage:

from maxrect import get_intersection, get_maximal_rectangle, rect2poly

# For a given convex polygon
coordinates1 = [ [x0, y0], [x1, y1], ... [xn, yn] ]
coordinates2 = [ [x0, y0], [x1, y1], ... [xn, yn] ]

# find the intersection of the polygons
_, coordinates = get_intersection([coordinates1, coordinates2])

# get the maximally inscribed rectangle
ll, ur = get_maximal_rectangle(coordinates)

# casting the rectangle to a GeoJSON-friendly closed polygon
rect2poly(ll, ur)

Source: https://pypi.org/project/maxrect/

Answer 3

here is a python code I wrote with rotation included. I tried to speed it up, but I guess it can be improved.

Answer 4

For future googlers,

Since your provided sample solution allows background pixels to be within the rectangle, I suppose you wish to find the the smallest rectangle that covers perhaps 80% of the white pixels.

This can be done using a similar method of finding the error ellipse given a set of data (in this case, the data is all the white pixels, and the error ellipse needs to be modified to be a rectangle)

The following links would hence be helpful

How to get the best fit bounding box from covariance matrix and mean position?

http://www.visiondummy.com/2014/04/draw-error-ellipse-representing-covariance-matrix/