Faster way to perform rectangle merging based on their intersection

Question

Hi, this is being used in a motion detection problem. Basically, I perform a motion detection algorithm on an image, and get a list of blobs, where each blob hopefully corresponds to an object that has moved. However, we have to merge these blobs as there might be many small ones touching each other that should be one large blob.

I merge the blobs together using this algorithm.

        //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;
                    }
                }
            }
        }

This is how I merge the blobs:

    /// <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;
    }

I may have about 0-150 blobs in all. I'd like to know if there's a faster way to do a blob merging. Thanks

Answer 1

I would suggest something along the lines of:

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

Every loop iteration either removes from output or adds to output and removes from input, so the total number of loop iterations is no larger than twice the number of output rectangles.

To improve the performance of output.findIntersected, you can represent your set of rectangles as a data structure optimized for intersection searching (as opposed to a plain list). For instance, you can keep a data structure sorted by the maximum X of your rectangles to cull several of them, and then insert rectangles sorted by minimum X. Plain classic solutions, such as kd-trees or adaptive binary trees, could also work, but the insertion/removal time might adversely affect performance.