在 2D 斑点上最适合矩形

Question

我有一个二进制斑点（见图），我想在其上放置一个已知宽度和高度的矩形。

如何找到最佳拟合矩形，即最大前景像素在内部且最大背景像素在外部的矩形？

（这是我对最适合的初步定义，我愿意接受其他建议）

我正在寻找已知尺寸的矩形，但如果有任意尺寸的解决方案，那就太好了。

斑点示例：

我想找到这些矩形：

到目前为止我的想法包括

• 从最小外接矩形开始；但这与这些斑点不太匹配
• 最大封闭矩形；同样的问题，而且我没有相应的算法
• 使用霍夫变换找到矩形边；数据太嘈杂了。

我意识到对于符合我的标准的同一个斑点可能有多个矩形，理想情况下我想要一些可以找到所有候选者的算法（认为因为这可能更难，我很高兴有一种方法只找到一个候选者） :

我主要使用 opencv 和 cvBlobLib 来处理我的数据，但我对任何通用解决方案持开放态度。

Answer 1

我看过一篇基于进化方法的类似主题的论文（RGB 平面上的圆覆盖）。

• 目标函数被明确定义（有多少个正方形？有多大？它们可以重叠吗？您可能想要惩罚小或重叠的正方形）。
• 您可以首先运行k 均值 算法来预处理数据，即找到正方形的潜在中心点。

我记得，对 SGA、CGA 和 eCGA 进行了比较（CGA 从初始的、基于 k 均值的覆盖开始），SGA 优于其他算法。它们是按每个图像运行的。大约有 30 个个体和 20 个世代，运行时间大约为几分钟。

对于 SGA，交叉运算符将一次选取两个父代，并将来自两个父代的最接近/最相似的圆配对。然后，对于每一对，它会在中间的某个位置绘制一个子圆，其半径也在两个圆的半径之间。（尽管我建议不要精确地取父母的值之间的值，但允许在范围之外有+/- 15％的值。这将防止总体过早收敛）。

对于矩形，您必须稍微修改方法；每个矩形可以是一个元组(x, y, width, height,rotation)，其中x和y是中心的坐标。