Внедрение Flood Fill

Question

Это моя реализация C# основанного на стеке алгоритма заливки (который я основал на определении из Википедии). Раньше, когда я писал код, я только хотел, чтобы это работало. И это сделал. Затем я хотел узнать количество пикселей, которые были на самом деле заполнены. Поэтому в своем коде я изменил тип возвращаемого значения на int и вернул переменную "ctr". Но затем оказалось, что ctr примерно в два раза превышает фактическое количество залитых пикселей (я сделал отдельную функцию с единственной целью - подсчитать эти пиксели - просто чтобы знать наверняка).

Может кто-нибудь просветить, как и почему переменная "ctr" увеличивается в два раза, как это должно быть?

* КлассPixel служит только контейнером для значений x, y и цвета пикселей из растрового изображения.

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor)
{
    Bitmap result = new Bitmap(image.Width, image.Height);
    Stack<Pixel> pixels = new Stack<Pixel>();
    Color oldColor = image.GetPixel(x, y);
    int ctr = 0;

    pixels.Push(new Pixel(x, y, oldColor));

    while (pixels.Count > 0)
    {
        Pixel popped = pixels.Pop();

        if (popped.color == oldColor)
        {
            ctr++;
            result.SetPixel(popped.x, popped.y, newColor);

            pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y));
            pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y));
            pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1));
            pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1));
        }
    }

    return result;
}

Answer 1

Вы проверяете цвет пикселя здесь:

if (popped.color == oldColor)

Но popped.color может быть (и, по-видимому, в 50% случаев) устаревшим. Поскольку вы не проверяете дубликаты, когда вставляете пиксель в стек, у вас будут дубликаты. После удаления этих дубликатов атрибут цвета был бы сохранен давно.

Может быть, это проясняется с рисунком:

В качестве примера я взял растровое изображение с 9 пикселями. На первой панели у вас есть нумерация пикселей, а справа - ваш стек.

Вы начинаете с пикселя № 5. и помещаете пиксели 2, 4, 6 и 8 в стек. Затем вы снимаете пиксель 2 и нажимаете 1 и 3. На следующем шаге вы нажимаете 1 и нажимаете 2 и 4 (снова!). Тогда вы можете взять 2 и понять, что он уже приобрел новый цвет, когда он был нажат. (Немного поздно, но лучше поздно, чем никогда) однако: пиксель нет. 4 там дважды и вспомнил старый цвет дважды. Итак, вы берете пиксель № 4 и раскрашиваете его.

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

Хотя у меня может быть неправильный порядок в стеке, точка остается в силе.

Решение вашей проблемы: быстро и грязно (потому что оно все равно неэффективно)

if (image.GetPixel(popped.x, popped.y) == oldColor)

он считает пиксели, только если текущий цвет неправильный, а не запомненный цвет.

Рекомендуется: проверьте свои пиксели, нуждаются ли они в раскраске, прежде чем положить их в стек.

Answer 2

Если все, что делает Pixel, это удерживать цвет, переданный его конструктору, он не будет обновлять цвет после заполнения пикселя, поэтому может увеличивать ctr более одного раза на пиксель.

Если вы измените Pixel так, чтобы он указывал на изображение в его конструкторе, вы могли бы перечитать цвет (т.е. сделать цвет доступным свойством, которое считывает текущий цвет), или отслеживать уже заполненные координаты и не выдвигать их в секунду. время.

[Редактировать]

Если это не было очевидно из принятого ответа, GetPixel возвращает Color - тип значения. Думайте об этом как о int, который кодирует значение RGB пикселя в то время.

Если вы хотите быстро выполнить заливку, посмотрите пример Graphics.FloodFill.

Если ваша цель - изучение, я бы рекомендовал скопировать данные вашего изображения в массив для обработки и обратно - большинство классических алгоритмов изображений не очень увлекательны с использованием GetPixel().