algorithm - 最适合 2D Blob 上的矩形

Question

我有一个二进制 blob(见图)，我想在它上面放置一个已知宽度和高度的矩形。

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

(这是我对best-fit的初步定义，我对其他建议持开放态度)

我正在寻找已知大小的矩形，但如果有任意大小的解决方案，那也很好。

示例 Blob :

我想找到这些矩形:

到目前为止我的想法包括在内

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

我意识到同一个 blob 可能有多个矩形符合我的标准，理想情况下我想要一些可以找到所有候选者的算法(认为因为这可能更难，我很乐意找到一种方法来只一名候选人):

我主要使用 opencv 和 cvBlobLib 来处理我的数据，但我愿意接受任何通用解决方案。

Answer 1

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

• 明确定义了目标函数(有多少个方 block ？有多大？它们可以重叠吗？你可能想惩罚小或重叠的方 block )。
• 您可以先运行 k-means预处理数据的算法，即找到正方形的潜在中心点。

我记得，对 SGA、CGA 和 eCGA 进行了比较(CGA 从初始的、基于 k-means 的覆盖开始)，其中 SGA 优于其他算法。它们是在每个图像的基础上运行的。大约有 30 个人和 20 代人的运行时间大约为几分钟。

至于 SGA，交叉运算符将同时接受两个 parent ，并将 parent 双方的最接近/最相似的圆圈配对。然后，对于每一对，它会在中间某处绘制一个子圆，其半径也在两个圆之间。 (虽然我建议不要完全取 parent 之间的值，但允许 +/- 15% 超出范围。这将防止人口过早收敛)。

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