3

これは、モーション検出の問題で使用されています。基本的に、画像に対してモーション検出アルゴリズムを実行し、ブロブのリストを取得します。各ブロブは、移動したオブジェクトに対応していることが望ましいです。ただし、1つの大きなブロブであるはずの小さなブロブが互いに接触している可能性があるため、これらのブロブをマージする必要があります。

このアルゴリズムを使用して、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のブロブがあるかもしれません。ブロブのマージを行うより速い方法があるかどうか知りたいのですが。ありがとう

4

1 に答える 1

4

私は次の行に沿って何かを提案します：

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ため、ループ反復の合計数は、出力四角形の数の 2 倍を超えることはありません。

のパフォーマンスを向上させるために、output.findIntersected長方形のセットを交差検索用に最適化されたデータ構造として表すことができます (単純なリストではありません)。たとえば、四角形の最大 X で並べ替えられたデータ構造を保持して、いくつかの四角形を選別し、最小 X で並べ替えられた四角形を挿入することができます。ただし、挿入/削除時間はパフォーマンスに悪影響を及ぼす可能性があります。

于 2010-01-09T22:17:37.573 に答える