Заливка - Flood fill

Рекурсивная заливка в 4 направлениях

Заливка заливкой , также называемая начальным заполнением , представляет собой алгоритм, который определяет и изменяет область, связанную с данным узлом в многомерном массиве с некоторым совпадающим атрибутом. Он используется в инструменте заливки «ведро» программ рисования для заливки связанных областей одинакового цвета другим цветом, а также в таких играх, как Go и Minesweeper, для определения того, какие части очищены. Вариант, называемый заливкой границ, использует те же алгоритмы, но определяется как область, связанная с данным узлом, не имеющая определенного атрибута.

Обратите внимание, что заливка заливкой не подходит для рисования многоугольников с заливкой, так как она пропускает некоторые пиксели в более острых углах. Вместо этого см. Правило « Четно- нечетное» и « Ненулевое правило» .

Параметры алгоритма

Рекурсивная заливка по 8 направлениям

Традиционный алгоритм заливки принимает три параметра: начальный узел, целевой цвет и замещающий цвет. Алгоритм ищет все узлы в массиве, которые связаны с начальным узлом путем целевого цвета, и меняет их на цвет замены. Для заливки границ вместо целевого цвета будет предоставлен цвет границы.

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

В зависимости от того, рассматриваем ли мы узлы, соприкасающиеся в углах соединенными или нет, у нас есть два варианта: восьмисторонний и четырехсторонний соответственно.

Рекурсивная реализация на основе стека (четырехсторонняя)

Самая ранняя из известных рекурсивных четырехсторонних рекурсивных реализаций , неявно основанных на стеке, выглядит следующим образом: 

Flood-fill (node):
 1. If node is not Inside return.
 2. Set the node
 3. Perform Flood-fill one step to the south of node.
 4. Perform Flood-fill one step to the north of node
 5. Perform Flood-fill one step to the west of node
 6. Perform Flood-fill one step to the east of node
 7. Return.

Хотя его легко понять, реализация описанного выше алгоритма непрактична в языках и средах, где пространство стека сильно ограничено (например, микроконтроллеры ).

Перенос рекурсии в структуру данных

Четырехстороннее заливное заполнение с использованием очереди на хранение
Четырехстороннее заливное заполнение с использованием штабеля для хранения

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

Flood-fill (node):
  1. Set Q to the empty queue or stack.
  2. Add node to the end of Q.
  3. While Q is not empty:
  4.   Set n equal to the first element of Q.
  5.   Remove first element from Q.
  6.   If n is Inside:
         Set the n
         Add the node to the west of n to the end of Q.
         Add the node to the east of n to the end of Q.
         Add the node to the north of n to the end of Q.
         Add the node to the south of n to the end of Q.
  7. Continue looping until Q is exhausted.
  8. Return.

Дальнейшие возможные оптимизации

  • Проверьте и установите цвет пикселя каждого узла перед добавлением его в стек / очередь, уменьшив размер стека / очереди.
  • Используйте петлю для направлений восток / запад, выстраивая пиксели вверх / вниз по мере продвижения. (Делая его похожим на алгоритмы заполнения промежутка, описанные ниже.)
  • Чередование двух или более копий кода с дополнительными стеками / очередями, чтобы предоставить процессорам OoO больше возможностей для распараллеливания
  • Используйте несколько потоков (в идеале с немного разными порядками посещений, чтобы они не оставались в одной и той же области)

Преимущества

  • Очень простой алгоритм - легко избавиться от ошибок.

Недостатки

  • Использует много памяти, особенно при использовании стека.
  • Тестирует наиболее заполненные пиксели в общей сложности четыре раза.
  • Не подходит для заливки узором, так как требует изменения результатов тестирования пикселей.
  • Шаблон доступа не поддерживает кеширование для варианта с очередями.
  • Невозможно легко оптимизировать для многопиксельных слов или битовых плоскостей.

Заполнение пролета

Заливка строки развертки

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

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty stack or queue
  add (x, y) to s
  while s is not empty:
    Remove an (x, y) from s
    let lx = x
    while Inside(lx - 1, y):
      Set(lx - 1, y)
      lx = lx - 1
    while Inside(x, y):
      Set(x, y)
      x = x + 1
    scan(lx, x - 1, y + 1, s)
    scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):
  let added = false
  for x in lx .. rx:
    if not Inside(x, y):
      added = false
    else if not added:
      Add (x, y) to s
      added = true

Со временем были реализованы следующие оптимизации:

  • Когда новое сканирование будет полностью в пределах диапазона дедушки и дедушки, оно определенно найдет только заполненные пиксели, и поэтому не будет нуждаться в очереди.
  • Кроме того, когда новое сканирование перекрывает пролет дедушки и дедушки, необходимо сканировать только свесы (развороты и W-повороты).
  • Возможно заполнение при сканировании семян

В 1990 году был опубликован окончательный вариант заполнения пролета с комбинированным сканированием и заполнением, который работает следующим образом (хотя эта версия исправляет некоторые ошибки в оригинале): 

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty queue or stack
  Add (x, x, y, 1) to s
  Add (x, x, y - 1, -1) to s
  while s is not empty:
    Remove an (x1, x2, y, dy) from s
    let x = x1
    if Inside(x, y):
      while Inside(x - 1, y):
        Set(x - 1, y)
        x = x - 1
    if x < x1:
      Add (x, x1-1, y-dy, -dy) to s
    while x1 < x2:
      while Inside(x1, y):
        Set(x1, y)
        x1 = x1 + 1
      Add (x, x1 - 1, y+dy, dy) to s
      if x1 - 1 > x2:
        Add (x2 + 1, x1 - 1, y-dy, -dy)
      while x1 < x2 and not Inside(x1, y):
        x1 = x1 + 1
      x = x1

Преимущества

  • В 2-8 раз быстрее, чем пиксельно-рекурсивный алгоритм.
  • Шаблон доступа удобен для кеширования и битовой плоскости.
  • Можно рисовать горизонтальную линию, а не устанавливать отдельные пиксели.

Недостатки

  • По-прежнему посещает пиксели, которые уже заполнены. (Для популярного алгоритма требуется 3 сканирования большинства пикселей. В последнем случае выполняется дополнительное сканирование только тех пикселей, где есть дыры в залитой области.)
  • Не подходит для заливки узором, так как требует изменения результатов тестирования пикселей.

Добавление поддержки заливки узором

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

Теоретико-графическое заполнение

Некоторые теоретики применили явную теорию графов к проблеме, рассматривая промежутки пикселей или их совокупности как узлы и изучая их связность. Первый опубликованный алгоритм теории графов работал аналогично заполнению промежутков, описанному выше, но имел способ определять, когда он дублирует заполнение промежутков. К сожалению, в нем были ошибки, из-за которых некоторые заливки не выполнялись. Скорректированный алгоритм был позже опубликован на аналогичной основе в теории графов; однако он изменяет изображение по мере продвижения, чтобы временно блокировать потенциальные петли, усложняя программный интерфейс. Опубликованный позже алгоритм зависел от того, что граница отлична от всего остального на изображении, и поэтому не подходит для большинства применений; для бухгалтерского учета также требуется дополнительный бит на пиксель.

Преимущества

  • Подходит для заливки узором напрямую, так как никогда не тестирует повторно заполненные пиксели.
  • Удвоение скорости исходного алгоритма диапазона для несложных заливок.
  • Шаблон доступа удобен для кеширования и битовой плоскости.

Недостатки

  • Регулярно интервал нужно сравнивать со всеми остальными «фронтами» в очереди, что значительно замедляет сложные заполнения.
  • Переключение между теоретической графической и пиксельной областями усложняет понимание.
  • Код довольно сложный, что увеличивает вероятность ошибок.

Заполнение на основе ходьбы (метод с фиксированной памятью)

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

  1. Все четыре граничных пикселя заполнены.
  2. Залиты три граничных пикселя.
  3. Два граничных пикселя заполнены.
  4. Заливается один граничный пиксель.
  5. Нулевые граничные пиксели заполнены.

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

В случае № 1 художник закрашивает (заполняет) пиксель, на котором он стоит, и останавливает алгоритм.

Для случая № 2 существует путь, ведущий из области. Нарисуйте пиксель, на котором стоит художник, и двигайтесь в направлении открытого пути.

В случае № 3 два граничных пикселя определяют путь, который, если мы закрасим текущий пиксель, может помешать нам когда-либо вернуться на другую сторону пути. Нам нужна «метка», чтобы определить, где мы находимся и в каком направлении движемся, чтобы увидеть, вернемся ли мы когда-нибудь к точно такому же пикселю. Если мы уже создали такую ​​«метку», то мы сохраняем нашу предыдущую метку и переходим к следующему пикселю, следуя правилу правой руки.

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

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

В случае № 4 нам нужно проверить противоположные 8-соединенные углы, чтобы увидеть, заполнены они или нет. Если один из них или оба заполнены, это создает перекресток с множеством путей и не может быть заполнен. Если оба пустые, то текущий пиксель можно нарисовать, и художник может двигаться, следуя правилу правой руки.

Алгоритм торгует временем на память. Для простых форм это очень эффективно. Однако, если фигура сложна с множеством функций, алгоритм тратит много времени на отслеживание краев области, пытаясь убедиться, что все можно раскрасить.

Этот алгоритм был впервые коммерчески доступен в 1981 году в системе обработки изображений Vicom производства Vicom Systems, Inc. Алгоритм ходьбы был опубликован в 1994 году. Классический алгоритм рекурсивного заполнения заливкой был также доступен в системе Vicom.

Псевдокод

Это реализация псевдокода оптимального алгоритма заливки с фиксированной памятью, написанная на структурированном английском языке:

Переменные
  • cur,, markи mark2каждый из них содержит координаты пикселей или нулевое значение
    • ПРИМЕЧАНИЕ: если markустановлено значение null, не стирайте предыдущее значение координаты. Сохраните эти координаты, чтобы их можно было вспомнить в случае необходимости.
  • cur-dir,, mark-dirи mark2-dirкаждый из них удерживает направление (влево, вправо, вверх или вниз)
  • backtrackи findloopкаждый содержит логические значения
  • count целое число
Алгоритм
ПРИМЕЧАНИЕ. Все направления (вперед, назад, влево, вправо) относительно cur-dir 
set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false

while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
    if count is not 4 then
        do
            turn right
        while front-pixel is inside
        do
            turn left
        while front-pixel is not inside
    end if
    switch count
        case 1
            if backtrack is true then
                set findloop to true
            else if findloop is true then
                if mark is null then
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both inside then
                clear mark
                set cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is not inside then
                if front-left-pixel is inside then
                    clear mark
                    set cur
                    jump to PAINT
                end if
            else if mark is not set then
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set then
                    if cur is at mark then
                        if cur-dir is the same as mark-dir then
                            clear mark
                            turn around
                            set cur
                            jump to PAINT
                        else
                            set backtrack to true
                            set findloop to false
                            set cur-dir to mark-dir
                        end if
                    else if findloop is true then
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark then
                        set cur to mark2
                        set cur-dir to mark2-dir
                        clear mark and mark2
                        set backtrack to false
                        turn around
                        set cur
                        jump to PAINT
                    else if cur at mark2 then
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end if
                end if
            end if
        end case
        case 3
            clear mark
            set cur
            jump to PAINT
        end case
        case 4
            set cur
            done
        end case
    end switch
end MAIN LOOP

Преимущества

  • Постоянное использование памяти.

Недостатки

  • Шаблон доступа не поддерживает кеширование или битовую плоскость.
  • Может потратить много времени на обход петель, прежде чем закрыть их.

Векторные реализации

Версия 0.46 Inkscape включает инструмент заливки ведра, выдающий результат, аналогичный обычным операциям с растровыми изображениями, и действительно использующий его: визуализируется холст, выполняется операция заливки заливки в выбранной области, а затем результат прослеживается до пути. Он использует понятие граничного условия .

Смотрите также

внешние ссылки

использованная литература

  1. ^ a b c Смит, Элви Рэй (1979). Оттеночная заливка . SIGGRAPH '79: Материалы 6-й ежегодной конференции по компьютерной графике и интерактивным методам. С. 276–283. DOI : 10.1145 / 800249.807456 .
  2. ^ a b Экленд, Брайан Д.; Вест, Нил Х (1981). Алгоритм краевого флага - отображается метод заливки для растрового сканирования . Транзакции IEEE на компьютерах (том: C-30, выпуск: 1). С. 41–48. DOI : 10.1109 / TC.1981.6312155 .
  3. ^ Б с д е е г ч я J Фишкин, Кеннет Р; Барский, Брайан А (1985). Анализ и алгоритм распространения заполнения . Компьютерные изображения: современные труды по графическому интерфейсу '85. С. 56–76. DOI : 10.1007 / 978-4-431-68033-8_6 .
  4. ^ Ньюман, Уильям М; Спроул, Роберт Флетчер (1979). Принципы интерактивной компьютерной графики (2-е изд.). Макгроу-Хилл. п. 253. ISBN. 978-0-07-046338-7.
  5. ^ Pavlidis, Тео (1982). Алгоритмы обработки графики и изображений . Springer-Verlag. п. 181. ISBN. 978-3-642-93210-6.
  6. ^ a b c d e f g h я Левой, Марк (1982). Алгоритмы затопления территорий . SIGGRAPH 1981 Двумерная компьютерная анимация примечания к курсу.
  7. ^ Фоли, JD; ван Дам, А; Файнер, СК; Хьюз, СК (1990). Компьютерная графика: принципы и практика (2-е изд.). Аддисон-Уэсли. С. 979–982. ISBN 978-0-201-84840-3.
  8. ^ Хекберт, Пол S (1990). «IV.10: Алгоритм заполнения семян». В Гласснер, Эндрю С. (ред.). Самоцветы графики . Академическая пресса. С. 275–277. ISBN 0122861663.
  9. ^ a b Либерман, Генри (1978). Как раскрашивать в книжке-раскраске . SIGGRAPH '78: Материалы 5-й ежегодной конференции по компьютерной графике и интерактивным методам. С. 111–116. DOI : 10.1145 / 800248.807380 .
  10. ^ a b c Шани, Ури (1980). Заполнение областей в двоичных растровых изображениях: теоретико-графический подход . SIGGRAPH '80: Материалы 7-й ежегодной конференции по компьютерной графике и интерактивным методам. С. 321–327. DOI : 10.1145 / 800250.807511 .
  11. ^ a b Павлидис, Тео (1981). Контурная заливка в растровой графике . SIGGRAPH '81: Материалы 8-й ежегодной конференции по компьютерной графике и интерактивным методам. С. 29–36. DOI : 10.1145 / 800224.806786 .
  12. ^ Генрих, Доминик (1994). Компактное заполнение областей в растровой графике . Визуальный компьютер. С. 205–215. DOI : 10.1007 / BF01901287 .