基於它們的交集執行矩形合併的更快方法

Question

這被用於運動檢測問題。 基本上，我在圖像上執行運動檢測算法，並獲取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; 
        } 
       } 
      } 
     } 

這是我如何合併斑點：

/// <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斑點。我想知道是否有更快的方法來進行斑點合併。 感謝

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樹或自適應二叉樹）也可以工作，但插入/移除時間可能會對性能產生不利影響。