根据交集执行矩形合并的更快方法

Question

这被用于运动检测问题。 基本上，我对图像执行运动检测算法，并获取斑点列表，其中每个斑点希望对应于已移动的对象。然而，我们必须合并这些斑点，因为可能有许多小斑点相互接触，而这些小斑点应该是一个大斑点。

我使用这个算法将斑点合并在一起。

        //Expand all blobs by 1x1 to ensure that we can use intersection
        //blobs is a List<blob>
        foreach (Blob blob in blobs)
        {
            blob.BoundingBox.Inflate(1, 1);
        }

        bool needToRestartMerging = true;

        while (needToRestartMerging == true)
        {
            int count = blobs.Count;

            needToRestartMerging = false;
            for (int i = 0; i < count - 1; i++)
            {
                for (int j = i + 1; j < count; j++)
                {
                    //BoundingBox is a simple System.Drawing.Rectangle
                    if (blobs[i].BoundingBox.IntersectsWith(blobs[j].BoundingBox))
                    {
                        Blob newBlob = blobs[i].Merge(blobs[j]);
                        blobs.RemoveAt(i);
                        blobs.RemoveAt(j-1);
                        blobs.Add(newBlob);
                        needToRestartMerging = true;
                        count = blobs.Count;
                    }
                }
            }
        }

这就是我合并 blob 的方式：

    /// <summary>
    /// Given a Pixel Location, we resize the Blob so that it is included in the BoundingBox
    /// </summary>
    /// <param name="x">Pixel XCoordinate</param>
    /// <param name="y">Pixel YCoordinate</param>
    public void ResizeToPixelLocation(int x, int y)
    {           
        numPixels++;
        if (x >= _boundingBox.Right)
        {
            _boundingBox.Width = x - _boundingBox.X;
        }
        if (y >= _boundingBox.Bottom)
        {
            _boundingBox.Height = y - _boundingBox.Y;
        }
        if (x <= _boundingBox.Left)
        {
            int oldLeft = _boundingBox.Left;
            int xOffset = x - _boundingBox.Left;
            _boundingBox.Offset(xOffset, 0);
            _boundingBox.Width += (oldLeft - x);
        }
        if (y <= _boundingBox.Top)
        {
            int oldTop = _boundingBox.Top;
            int yOffset = y - _boundingBox.Top;
            _boundingBox.Offset(0, yOffset);
            _boundingBox.Height += (oldTop - y);

        }
    }

    /// <summary>
    /// Merge this blob with another blob
    /// </summary>
    /// <param name="blob2">The second blob</param>
    /// <returns></returns>
    public Blob Merge(Blob blob2)
    {
        Blob newBlob = new Blob(BoundingBox.X, BoundingBox.Y);
        newBlob.ThreadID = this.ThreadID;
        newBlob.numPixels = NumPixels + blob2.NumPixels;
        newBlob.BoundingBox = BoundingBox;
        newBlob.ResizeToPixelLocation(blob2.BoundingBox.X, blob2.BoundingBox.Y);
        newBlob.ResizeToPixelLocation(blob2.BoundingBox.Right, blob2.BoundingBox.Bottom);
        return newBlob;
    }

总共可能有大约 0-150 个 blob。我想知道是否有更快的方法来进行 blob 合并。 谢谢

Answer 1

我建议如下：

mergeConnected(input):
  output = new RectangleSet
  while input.length > 0 do
    nextRect = input.pop()
    intersected = output.findIntersected(nextRect)
    if intersected then
      output.remove(intersected)
      input.push(nextRect.merge(intersected))
    else
      output.insert(nextRect)
  done
  return output

每个循环迭代要么从 output 中删除，要么添加到 output 并从 input 中删除，因此总数循环迭代次数不大于输出矩形数量的两倍。

为了提高 output.findIntersected 的性能，您可以将矩形集表示为针对交集搜索而优化的数据结构（而不​​是普通列表）。例如，您可以保留按矩形的最大 X 排序的数据结构，以剔除其中的几个，然后插入按最小 X 排序的矩形。简单的经典解决方案（例如 kd 树或自适应二叉树）也可以工作，但插入/移除时间可能会对性能产生不利影响。