Une méthode plus rapide pour effectuer la fusion rectangle en fonction de leur intersection

Question

cela est utilisé dans un problème de détection de mouvement. Fondamentalement, j'effectue un algorithme de détection de mouvement sur une image, et obtient une liste de blobs, où chaque blob correspond, espérons-le, à un objet qui a bougé. Cependant, nous devons fusionner ces blobs car il pourrait y avoir beaucoup de petits qui se touchent qui devraient être un gros blob.

Je fusionne les blobs ensemble en utilisant cet algorithme.

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

Voilà comment je fusionner les 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; 
    } 

que je peux avoir sur 0-150 blobs en tout. J'aimerais savoir s'il existe un moyen plus rapide de fusionner un blob. Merci

Answer 1

je suggère quelque chose le long des lignes de:

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 

Chaque itération de la boucle soit supprime de output ou ajoute à output et supprime de input, de sorte que le nombre total d'itérations de la boucle est pas plus que deux fois le nombre de rectangles de sortie. Pour améliorer les performances de output.findIntersected, vous pouvez représenter votre ensemble de rectangles comme une structure de données optimisée pour la recherche d'intersections (par opposition à une liste simple). Par exemple, vous pouvez garder une structure de données triée par le maximum X de vos rectangles pour en éliminer plusieurs, puis insérer des rectangles triés par X minimum. Des solutions classiques simples, telles que des arbres kd ou des arbres binaires adaptatifs, pourraient aussi fonctionner, mais le temps d'insertion/retrait peut affecter les performances.