Более быстрый способ выполнения слияния прямоугольников на основе их пересечения - PullRequest
Новая
       26

Более быстрый способ выполнения слияния прямоугольников на основе их пересечения

3 голосов
/ 10 января 2010

это используется при обнаружении движения. По сути, я выполняю алгоритм обнаружения движения на изображении и получаю список больших двоичных объектов, каждый из которых, мы надеемся, соответствует перемещенному объекту. Однако мы должны объединить эти сгустки, так как может быть много маленьких, соприкасающихся друг с другом, которые должны быть одним большим сгустком.

Я объединяю капли, используя этот алгоритм. 

        //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 капель в целом. Я хотел бы знать, есть ли более быстрый способ слияния BLOB-объектов. Спасибо

1 Ответ

4 голосов
/ 10 января 2010

Я бы предложил что-то вроде: 

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-деревья или адаптивные двоичные деревья, также могут работать, но время вставки / удаления может отрицательно повлиять на производительность.

...