任意多边形中最大的内接矩形
largest inscribed rectangle in arbitrary polygon
我使用 OpenCV 拼接已有一段时间了。现在我想做拼接的最后一步：裁剪图像。这导致在一般多边形中找到最大的内接轴平行矩形。
我已经用谷歌搜索并找到了一些答案 (How do I crop to largest interior bounding box in OpenCV?)。尽管程序 运行 很慢，但输出图像的质量还是不错的（裁剪图像需要 15 秒，而将 36 张 1600x1200 图片拼接成 1 张全景图只需要 47 秒），因为使用的算法时间复杂度很差（对于每个点在轮廓中，它扫描相同 row/column) 中的所有点。
有什么方法可以改善吗？谢谢
P/S: 我也找到了这本书:
Finding the Largest Area Axis-Parallel Rectangle in a Polygon
Karen Daniels y Victor Milenkovicz Dan Rothx Harvard University,
Division of Applied Sciences,
Center for Research in Computing Technology,
Cambridge, MA 02138.
June 1995
但我不知道如何将理论应用到代码中 :v
您可能不想实现该算法；这将花费相当长的时间，而且我怀疑尽管有大 O 限制，您仍会对性能感到失望。
听起来好像您正在处理栅格，因此您可以在二进制矩阵中使用 linear-time algorithm for finding the largest rectangle of zeros。
也许看看这个 largest interior rectancle implementation. It uses the algorithm described in this paper。示例图像是
目前我正在 opencv stitching tool
中实现裁剪功能
我使用 OpenCV 拼接已有一段时间了。现在我想做拼接的最后一步：裁剪图像。这导致在一般多边形中找到最大的内接轴平行矩形。
我已经用谷歌搜索并找到了一些答案 (How do I crop to largest interior bounding box in OpenCV?)。尽管程序 运行 很慢，但输出图像的质量还是不错的（裁剪图像需要 15 秒，而将 36 张 1600x1200 图片拼接成 1 张全景图只需要 47 秒），因为使用的算法时间复杂度很差（对于每个点在轮廓中，它扫描相同 row/column) 中的所有点。
有什么方法可以改善吗？谢谢
P/S: 我也找到了这本书:
Finding the Largest Area Axis-Parallel Rectangle in a Polygon
Karen Daniels y Victor Milenkovicz Dan Rothx Harvard University,
Division of Applied Sciences,
Center for Research in Computing Technology,
Cambridge, MA 02138.
June 1995
但我不知道如何将理论应用到代码中 :v
您可能不想实现该算法；这将花费相当长的时间，而且我怀疑尽管有大 O 限制，您仍会对性能感到失望。
听起来好像您正在处理栅格，因此您可以在二进制矩阵中使用 linear-time algorithm for finding the largest rectangle of zeros。
也许看看这个 largest interior rectancle implementation. It uses the algorithm described in this paper。示例图像是
目前我正在 opencv stitching tool
中实现裁剪功能