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

Question

After I applied the threshold value and found the contours of the object, I used the following code to get a straight rectangle around the object (or a rotated rectangle introducing 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 image

Then I 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 the object of the object, i.e. have a rectangle that occupies most of the object without or a smaller background pixel, for example

How do I create this?

Answer 1

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

An approximate solution can be found at this link .

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

My decision is based on this answer. This will only find rectangles with axis aligned, so you can easily rotate the image by a given angle and apply this solution for each angle. My solution is C ++, but you can easily port it to Python, since I mainly use the OpenCV function or tweak the solution in the above answer responsible for the 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(rh, 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" // /questions/89541/find-largest-rectangle-containing-only-zeros-in-an-nn-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; } 

Result Image:

Note

I would like to point out that this code is not optimized, so it can probably work better. For an approximate solution, see here and reports were published there.

This answer to the corresponding question set me in the right direction.

Answer 2

here is the python code that I wrote with rotation turned on. I tried to speed it up, but I think it can be improved.

Answer 3

For future googlers

Since your provided exemplary solution allows background pixels to be inside the rectangle, I assume you want to find the smallest rectangle that covers perhaps 80% of the white pixels.

This can be done using a similar method for finding the error ellipse specified by the data set (in this case, the data is all white pixels, and the error ellipse should be changed as a rectangle)

Therefore, the following links will be useful.

How to get the optimal bounding box from the covariance matrix and middle position?

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