基于矩形交集的更快合并方法

Question

这是一个与运动检测相关的问题。

基本上，我在图像上执行运动检测算法，并获得一系列blob，其中每个blob希望对应于已移动的物体。然而，我们必须合并这些blob，因为可能有许多小blob相互接触，应该成为一个大blob。

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

        //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。

谢谢

- Jean Azzopardi

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中删除或添加并从input中删除，因此循环迭代的总数不超过输出矩形数量的两倍。

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

- Victor Nicollet

---

谢谢您的回答，我遇到的唯一问题是如何表示您提到的数据结构。 - Jean Azzopardi

谢谢您的评论，但最终我们没有走得那么远，因为速度已经足够快了。 - Jean Azzopardi