algorithm - 如何生成一个与现有边界框至少按给定比例重叠的边界框？

Question

给定一个边界框 bbox1 , 我想随机生成一个新的边界框 bbox2 , 与 bbox1 重叠至少 0.5。

重叠率定义为 bbox1 之间的交集面积和 bbox2 , 除以两者的并集面积。

我能想到的天真的方法是随机生成边界框，直到找到满足条件的边界框。但显然，这会浪费一些时间来生成和评估不满意的候选人。

如果边界框由左上角和宽高编码bbox1 = (x1, y1, w1, h1) ，下面的伪代码显示了我如何生成新的边界框。

do
    x2 = random(x1 - w1, x1 + w1/2)
    y2 = random(y1 - h1, y1 + h1/2)
    w2 = random(0, 2 * w1)
    h2 = random(0, 2 * w1 * h1 / w2)
    bbox2 = (x2, y2, w2, h2)
while bboxOverlapRatio(bbox1, bbox2) < 0.5

有更好的解决方案吗？例如，我能否进一步缩小随机范围？

Answer 1

进一步缩小随机范围的一种方法是只生成新的边界框 bbox2中心在里面 bbox1 .

如果bbox2的中心在bbox1之外那么不可能有至少 0.5 的重叠(请注意，这本身就是一个单独的、有趣的数学问题)。

这个附加约束可以表示为x1 < x2 + w2/2 < x1 + w1 (与垂直轴的关系类似)，可用于缩小 w2 的范围和 h2 :

do
    x2 = random(x1 - w1, x1 + w1/2)
    y2 = random(y1 - h1, y1 + h1/2)
    w2 = random(max(0, 2 * (x1 - x2)), min(2 * w1, 2 * (x1 + w1 - x2)))
    h2 = random(max(0, 2 * (y1 - y2)), min(2 * w1 * h1 / w2, 2 * (y1 + h1 - y2)))
    bbox2 = (x2, y2, w2, h2)
while bboxOverlapRatio(bbox1, bbox2) < 0.5