我有一个由二进制掩码定义的任意形状（灰色 = 形状，黑色 = 背景）。
我想找到一个仅包含灰色像素的最大可能矩形（这样的矩形以黄色显示）：
形状始终是“一体的”，但不一定是凸的（并非形状边界上的所有点对都可以通过穿过该形状的直线连接）。
有时存在许多这样的“最大矩形”，然后可以引入进一步的约束，例如：
我对算法的第一个想法如下：
但是，我认为这样的算法会很慢并且不会导致最优解。
有什么建议？
Matlab Fileexchange 上有一个与您的问题相关的代码：http: //www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle/content/html/Inscribed_Rectangle_demo.html
更新
我根据来自 Atul Ingle 的上述链接写了这篇关于计算最大内接矩形的教程文章。
该算法首先在二进制掩码上搜索最大的正方形。这是使用简单的动态规划算法完成的。每个新像素都使用已知的三个相邻像素进行更新：
squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1
示例二进制掩码和计算图如下所示：
在地图中取最大值显示最大的内接正方形：
矩形搜索算法再扫描掩码两次以查找两类矩形：
这两个类都以最大的正方形为界，因为在给定点上没有一个矩形的两个维度都大于内接正方形（尽管一个维度可以更大）。
必须为矩形尺寸选择一些度量标准，例如面积、周长或尺寸的加权总和。
这是矩形的结果图：
将迄今为止找到的最佳矩形的位置和大小存储在变量中很方便，而不是构建地图然后寻找最大值。
该算法的实际应用是裁剪非矩形图像。我在我的图像拼接库 SharpStitch中使用了这个算法：
