求多边形中最大的内接矩形

Question

我有一堆带有红色标记多边形的图像（255,0,0）：

我想提取边界框，但在多边形内部，如蓝色矩形所示：

OpenCV cv.boundingRect 给了我外部边界框，但如何提取内部边界框？

Answer 1

这个内接矩形问题比外矩形问题稍微复杂一些。一个相关的一般情况是多边形内的多边形 -多边形包含问题在 1983 年的这篇论文中进行了描述。该算法确定一个具有 n 个点的多边形是否可以拟合另一个具有 m 个点的多边形，其复杂度为 O(n^3 m^3(n+m)log(n+m)) 复杂度。

“几何凸集中最大内切矩形”的限制情况可以更快地完成。看看这篇 2019 年的论文（DeepAI Link），他们考虑了在紧凑且实体的凸集内找到最大体积的内接盒和轴对齐内接盒的问题。

这是另一个较旧的更容易理解的凸多边形算法，具有良好的可视化效果。

这是一个MATLAB 实现。但代码缺乏注释，有点难以理解。

这是一个python 实现，但有点过时了。

Answer 2

假设你有两个矩形

import numpy as np

rect1 = np.array([[[20,15],[210,30],[220,100],[20,100]]], np.int32)
rect2 = np.array([[[25, 180], [215, 215], [220, 285], [20, 295]]], np.int32)

您可以使用最大的内部矩形包计算最大的内接多边形。他们来了[x, y, width, height]。

import largestinteriorrectangle as lir

lir1 = lir.lir(rect1)  # array([20, 30, 191, 71])
lir2 = lir.lir(rect2)  # array([23, 215, 193, 71])

让我们绘制一下：

import cv2 as cv

img = np.zeros((380, 240, 3), dtype = "uint8")

cv.polylines(img, [rect1], True, (0,0,255), 3)
cv.polylines(img, [rect2], True, (0,0,255), 3)
    
cv.rectangle(img, lir.pt1(lir1), lir.pt2(lir1), (255,0,0), 3)
cv.rectangle(img, lir.pt1(lir2), lir.pt2(lir2), (255,0,0), 3)

cv.imshow('Shapes', img)
cv.waitKey(0)
cv.destroyAllWindows()

该包使用了本文的算法

请注意，该包使用numbas即时编译 (JIT)。因此，第一次导入largestinteriorrectangle需要一些时间，但之后速度非常快

在您的图像中，蓝色矩形不接触红色多边形。所以你需要添加1x 和 y 并减去2宽度和高度

Answer 3

这不是一个快速的解决方案，但该算法应该为您提供正确的最大内部矩形：

1. 将轮廓绘制为强度值为 1 的蒙版
2. 计算掩模的积分图像https://en.wikipedia.org/wiki/Summed-area_table
3. 对于掩码值 > 0 的每个像素：对于该像素右侧/底部的每个像素，通过从积分图像中读取 4 个值来测试整个矩形是否填充有白色像素。

积分图像使其比应有的效率更高，算法本身只是蛮力。

int main()
{
    //std::vector<cv::Point> contour = { cv::Point(100,100), cv::Point(200,160), cv::Point(220, 230), cv::Point(90,270) };
    std::vector<cv::Point> contour = { cv::Point(100,100), cv::Point(150,200), cv::Point(200,160), cv::Point(220, 230), cv::Point(90,270) };
    //std::vector<cv::Point> contour = { cv::Point(100,100), cv::Point(200,100), cv::Point(200, 300), cv::Point(100,300) };

    cv::Mat img = cv::Mat::zeros(512, 512, CV_8UC3);
    cv::Mat mask = cv::Mat::zeros(img.size(), CV_8UC1);

    std::vector<std::vector<cv::Point> > contours = { contour };
    cv::drawContours(mask, contours, 0, cv::Scalar::all(1), -1); // mask values to 1 to make area == sum of pixels
    cv::drawContours(img, contours, 0, cv::Scalar(0, 0, 255), 1);

    cv::Mat integral;
    mask = mask;
    cv::integral(mask, integral, CV_32S);

    cv::Rect best;

    //cv::Mat legal = mask.clone();
    for (int y = 0; y < mask.rows; ++y)
    {
        std::cout << y << std::endl;
        for (int x = 0; x < mask.cols; ++x)
        {
            if (mask.at<uchar>(y, x) == 0) continue;
            cv::Point i1 = cv::Point(x, y);
            int val1 = integral.at<int>(i1);
            for (int y2 = y + 1; y2 < integral.rows; ++y2)
                for (int x2 = x + 1; x2 < integral.cols; ++x2)
                {
                    
                    cv::Point i2 = cv::Point(x2, y);
                    cv::Point i3 = cv::Point(x, y2);
                    cv::Point i4 = cv::Point(x2, y2);
                    if (mask.at<uchar>(i4) == 0) continue;
                    int val2 = integral.at<int>(i2);
                    int val3 = integral.at<int>(i3);
                    int val4 = integral.at<int>(i4);

                    int area = val1 + val4 - val2 - val3;
                    if (area != (x2 - x) * (y2 - y))
                    {
                        //std::cout << i1 << " to " << i4 << " = w:" << (x2 - x) << " h:" << (y2 - y) << std::endl;
                        //std::cout << area << " vs. " << (x2 - x) * (y2 - y) << std::endl;
                        //legal.at<uchar>(y, x) = 0;
                        //std::cin.get();
                    }
                    else
                    {
                        if (area > best.area()) best = cv::Rect(i1, i4);
                    }
                }
        }
        
    }

    cv::rectangle(img, best, cv::Scalar(255, 0, 0), 1);

    cv::imshow("img", img);
    cv::imshow("mask", mask>0);
    cv::waitKey(0);
}