python - 最佳放置裁剪区域以捕获图像中的特征( Blob )的算法

Question

我有一个大图像，其中包含背景上感兴趣的“ Blob ”。我有所有 Blob 的位置(质心、边界框、区域)。我想在图像中裁剪出有限数量的固定大小的区域，以便捕捉大部分 Blob 。以下示例针对同一图像中的 1、2 或 3 个裁剪区域。

此示例表明裁剪 1 个区域(红色)相对容易:只需选择具有尽可能多 Blob 的区域即可。这可以通过尝试所有方法或可能通过使用核密度估计器或类似方法计算 Blob 密度来解决。

但裁剪 2 个区域(蓝色虚线)不仅仅是在上面第一个选择之后裁剪下一个最佳裁剪区域。这是一个新问题，我需要找到 2 种裁剪的最佳组合。尝试 2 种裁剪的所有组合(蛮力)可能会变得计算成本太高(我有很多图像要处理，而且它们很大)。

同样，裁剪 3 个区域(绿色)是一个新问题，而且是一个更不适合暴力破解的问题。在该特定示例中，3 个区域中的 2 个与蓝色情况相同，并添加了一个新区域，但这不是一般情况(我只是想展示一个稍微复杂的场景)。

我不知道解决 n-crops 案例的算法。我想知道这个问题是否有理论上/众所周知的解决方案。

另外:

• 问题的几何形状与上述示例大致相同(图像高度上最多裁剪两次，宽度上裁剪多次)；以防万一
• 裁剪不应相交
• Blob 应尽可能居中(即 https://dl.dropboxusercontent.com/u/1047321/SO_crop/cutout_one_blob.png)
• 裁剪应保持在原始图像边界内(参见上述任一示例)
• 应该考虑 Blob 的面积(我对大 Blob 比小 Blob 更感兴趣)；但这可能可以通过将权重与每个 blob 相关联来计算每个裁剪布局的分数来引入任何算法。
• 可以省略一些 Blob 。实际上，我可能会计算一个成本复杂性参数，例如添加裁剪的新 blob 数量，并设置一个阈值，低于该阈值我将停止添加裁剪。

提前感谢您的指点。

PS:编码语言在这里并不重要，因为算法的核心(根据 Blob 的位置/大小找到裁剪的最佳位置)只需要小数组(每个图像的位置/大小约为 100 个 Blob )进行计算。我可能会使用 Python 或 R。

Answer 1

如果 Blob 相对较小，如图所示，您可以使用 Blob 中心 x,y 对运行 k-Means 聚类。python scikit-learn 包非常成熟，应该运行良好:http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html (KMeans分类器的函数fit_predict)

k 是一个输入，表示您想要的簇数。该算法会将 blob(样本)拆分为 k 个簇(集)。然后，您可以计算每个集合的 x、y 帧(min-x、max-x、min-y、max-y)，还可以包括 blob 的各个大小，或者如果它们相当小，则只取它们的最大值。

然后您可以根据它们的 #blobs/frame-area 比率对簇进行排序，然后将它们相加，例如直到足够多的 Blob 被覆盖(完成) - 或者你的总面积变得太大(在这种情况下用更大的 k 重新运行)。