这个问题可以表述为“在一个非凸多边形中找到最大的内接矩形”。
可以在
此链接中找到一个近似的解决方案。
这个问题也可以表述为:“对于每个角度,在一个矩阵中找到只包含零的最大矩形”,在这个SO
问题中探讨过。
我的解决方案基于
这个答案。它只能找到轴对齐的矩形,所以你可以很容易地通过给定的角度旋转图像,并对每个角度应用此解决方案。
我的解决方案是C++,但你可以很容易地将其移植到Python,因为我主要使用OpenCV函数,或者根据旋转调整上述提到的解决方案。
#include <opencv2\opencv.hpp>
#include <iostream>
using namespace cv;
using namespace std;
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)
{
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)));
Rect bestRect;
int bestAngle = 0;
for (int angle = 0; angle < 90; angle += 1)
{
cout << angle << endl;
Mat R = getRotationMatrix2D(Point(maxdim,maxdim), angle, 1);
Mat1b rotated;
warpAffine(work, rotated, R, work.size());
vector<Point> pts;
findNonZero(rotated, pts);
Rect box = boundingRect(pts);
Mat1b crop = rotated(box).clone();
crop = ~crop;
Rect r = findMinRect(crop);
if (r.area() > bestRect.area())
{
bestRect = r + box.tl();
bestAngle = angle;
}
}
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);
for (int i = 0; i < rotatedRectPoints.size(); ++i)
{
rotatedRectPoints[i] += bbox.tl() - Point(maxdim - bbox.width / 2, maxdim - bbox.height / 2);
}
RotatedRect rrect = minAreaRect(rotatedRectPoints);
return rrect;
}
int main()
{
Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE);
RotatedRect r = largestRectInNonConvexPoly(img);
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;
}
结果图片为:
![enter image description here](https://istack.dev59.com/jBIUJ.webp)
注意
我想指出这段代码并不是最优化的,所以它可能会有更好的表现。对于一个近似解,请参见这里和那里报告的论文。
这个答案给了我正确的方向。