C # - Нахождение границ изображения (не размер) - PullRequest
Новая
       22

C # - Нахождение границ изображения (не размер)

1 голос
/ 11 августа 2010

Я разрабатываю приложение для равномерного разделения сетки изображений и центрирования изображений (исходя из их сходства).До сих пор мне удавалось исправить сетку изображений с небольшими размерами, но всякий раз, когда я пытаюсь увеличить размер «спрайта» (например, 100x100), я получаю ошибку переполнения стека.

Да, я использую рекурсию, но всякий раз, когда проверяется пиксель, я устанавливаю логическое значение, чтобы деактивировать его, копировать в список и проверять остальные (во всех направлениях), пока список не заполнится.с изображением из сетки.Я не уверен, что это лучший способ, так как для каждого вызова я вызываю один и тот же метод 7 раз (предположим, что есть 7 смежных пикселей, которые еще не проверены) ... до тех пор, пока не останется пикселей для проверки, иЯ могу перейти к следующему изображению в сетке.

Я попытался отследить, где произошла ошибка, это было после проверки более или менее 1600 пикселей и добавления их в список.MyPixel - это класс, который содержит 4 переменные: x (int), y (int), color (Color) и флажок (bool) 

    public void processSprite(int i, int j)
    {
        //OOO
        //OXO
        //OOO
        pixeltemp.Add(new MyPixel(imap.pixels[i, j].x, imap.pixels[i, j].y, imap.pixels[i, j].color));
        imap.pixels[i, j].read = true;
        //OOO
        //OOX
        //OOO
        try
        {
            if (!imap.pixels[i + 1, j].read)
            {
                if (imap.pixels[i + 1, j].color.A == 0) //Found a Border
                {
                    imap.pixels[i + 1, j].read = true;
                }
                else
                {
                    processSprite(i + 1, j);
                }
            }
        }
        //... (code goes on)
    }
  • pixeltemp - это временный список пикселей, который содержитизображение (List<MyPixel>)
  • imap содержит все изображение (List<MyPixel>)

Полагаю, это не проблема памяти, поскольку мое приложение занимает всего 16 МБ.

Мой вопрос: почему у меня эта ошибка «переполнение стека», если это не бесконечная рекурсия?Есть ли более простой способ сделать это?Я думаю, что мой код выглядит некрасиво, я просто понятия не имею, как его улучшить.

Заранее спасибо!

1 Ответ

1 голос
/ 11 августа 2010

Переполнения стека вызваны не бесконечной рекурсией, а большей рекурсией (или, скорее, стеком вызовов), чем может обработать процесс.В вашем случае каждый рекурсивный вызов processSprite будет выполнять одинаковое количество рекурсивных вызовов processSprite.Таким образом, в наихудшем сценарии с 1600 пикселями без нахождения границы дерево вызовов будет выглядеть следующим образом: 

  processSprite(0, j)
    processSprite(1, j)
      processSprite(2, j)
        ...
          processSprite(1599, j) <-- That's 1600 call frames,
                                     enough for an overflow.

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

Редактировать:

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

IEnumerable<Rectangle> FindImageTiles(Bitmap compositeImage)
{
    var result = new List<Rectangle>();

    // Scan for a non-empty region that hasn't already been "captured"
    for (var x = 0; x < compositeImage.Width; x++)
    {
        for (var y = 0; y < compositeImage.Height; y++)
        {
            // Only process the pixel if we don't have a rectangle that
            // already contains this and if it's not empty
            if (!result.Any(r => r.Contains(x, y)) 
                && compositeImage.GetPixel(x, y).A != 0)
            {
                // Now that we've found a point, create a rectangle
                // surrounding that point, then expand outward until
                // we have a bounding rectangle that doesn't intersect
                // with the tile
                var rect = new Rectangle(x - 1, y - 1, 2, 2);
                bool foundBounds = false;
                while (!foundBounds)
                {
                    var xRange = Enumerable.Range(rect.Left, rect.Right)
                        .Where(px => px >= 0 && px < compositeImage.Width);
                    var yRange = Enumerable.Range(rect.Top, rect.Bottom)
                        .Where(py => py >= 0 && py < compositeImage.Height);

                    // Adjust the top
                    if (rect.Top >= 0 
                        && xRange
                            .Select(bx => compositeImage.GetPixel(bx, rect.Top))
                            .Any(p => p.A != 0))
                    {
                        rect.Y--;
                        rect.Height++;
                    }
                    else if (rect.Bottom < compositeImage.Height
                        && xRange
                            .Select(bx => compositeImage.GetPixel(bx, rect.Bottom))
                            .Any(p => p.A != 0))
                    {
                        rect.Height++;
                    }
                    else if (rect.Left >= 0
                        && yRange
                            .Select(by => compositeImage.GetPixel(rect.Left, by))
                            .Any(p => p.A != 0))
                    {
                        rect.X--;
                        rect.Width++;
                    }
                    else if (rect.Right < compositeImage.Width
                        && yRange
                            .Select(by => compositeImage.GetPixel(rect.Right, by))
                            .Any(p => p.A != 0))
                    {
                        rect.Width++;
                    }
                    else
                    {
                        foundBounds = true;
                    }
                }
                result.Add(rect);
            }
        }
    }

    return result;
}
...