Наводнение
Flood fill , также называемый начальным заполнением , представляет собой алгоритм заливки , который определяет и изменяет область, подключенную к данному узлу в многомерном массиве с некоторым совпадающим атрибутом. Он используется в инструменте заливки «ведро» программ рисования для заполнения связанных областей одинакового цвета другим цветом, а также в таких играх, как Go и Minesweeper, для определения того, какие части очищены. Вариант, называемый заливкой границ, использует те же алгоритмы, но определяется как область, соединенная с данным узлом и не имеющая определенного атрибута. [1]
Обратите внимание, что заливка заливкой не подходит для рисования заполненных многоугольников, так как в более острых углах будут пропущены некоторые пиксели. [2] Вместо этого см. Правило чет-нечет и Правило ненулевого значения .
Параметры алгоритма
[ редактировать ]
Традиционный алгоритм заливки принимает три параметра: начальный узел, целевой цвет и замещающий цвет. Алгоритм ищет все узлы в массиве, которые соединены с начальным узлом путем целевого цвета, и заменяет их цветом замены. Для заливки границ вместо целевого цвета будет указан цвет границы.
Чтобы обобщить алгоритм обычным способом, в следующих описаниях вместо этого будут доступны две процедуры. [3] Один позвонил Inside который возвращает true для незаполненных точек, которые по своему цвету находятся внутри заполненной области, и называется Set который заполняет пиксель/узел. Любой узел, имеющий Set призванный, его больше не должно быть Inside.
В зависимости от того, считаем ли мы узлы, соприкасающиеся по углам, соединенными или нет, у нас есть два варианта: восьмисторонний и четырехсторонний соответственно.
Рекурсивная реализация на основе стека (четырехходовая)
[ редактировать ]Самая ранняя известная реализация неявно основанной на стеке рекурсивной четырехсторонней заливки выглядит следующим образом: [4] [5] [6] [7]
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.
Дальнейшие потенциальные оптимизации
[ редактировать ]- Проверьте и установите цвет пикселя каждого узла перед добавлением его в стек/очередь, уменьшив размер стека/очереди.
- Используйте цикл для направлений восток/запад, ставя в очередь пиксели выше/ниже по мере продвижения (что делает его похожим на алгоритмы заполнения диапазона, показанные ниже).
- Чередуйте две или более копии кода с дополнительными стеками/очередями, чтобы предоставить процессорам с нарушением порядка больше возможностей для распараллеливания.
- Используйте несколько потоков (в идеале с немного разным порядком посещения, чтобы они не оставались в одной и той же области). [6]
Преимущества
[ редактировать ]- Очень простой алгоритм - легко сделать без ошибок. [6]
Недостатки
[ редактировать ]- Использует много памяти, особенно при использовании стека. [6]
- Тестирует наиболее заполненные пиксели в общей сложности четыре раза.
- Не подходит для заполнения узором, так как для изменения требуются результаты теста пикселей.
- Шаблон доступа не поддерживает кэширование для варианта с очередями.
- Невозможно легко оптимизировать многопиксельные слова или битовые плоскости. [2]
Заполнение пролета
[ редактировать ]
Можно оптимизировать ситуацию, работая в первую очередь с промежутками, строками с константами. y. Первый опубликованный полный пример работает по следующему основному принципу. [1]
- Начиная с исходной точки, заполняйте слева и справа. Следите за самой левой заполненной точкой
lxи крайняя правая заполненная точкаrx. Это определяет диапазон. - Сканировать из
lxкrxвыше и ниже исходной точки в поисках новых исходных точек, с которыми можно продолжить.
В целях оптимизации алгоритм сканирования не требует перезапуска с каждой исходной точки, а только с тех, которые находятся в начале следующего интервала. Использование стека сначала исследует глубину интервалов, а очередь сначала исследует ширину.
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 span_added = false
for x in lx .. rx:
if not Inside(x, y):
span_added = false
else if not span_added:
Add (x, y) to s
span_added = true
Со временем были реализованы следующие оптимизации:
- Когда новое сканирование будет полностью находиться в пределах родительского диапазона, оно, безусловно, найдет только заполненные пиксели, и поэтому не потребуется постановка в очередь. [1] [6] [3]
- Кроме того, когда новое сканирование перекрывает исходный пролет, необходимо сканировать только свесы (U-образные и W-образные повороты). [3]
- Можно заполнять при сканировании семян. [6]
Окончательный вариант заполнителя интервалов с комбинированным сканированием и заполнением был опубликован в 1990 году. В форме псевдокода: [8]
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
if x1 > x:
Add (x, x1 - 1, y + dy, dy) to s
if x1 - 1 > x2:
Add (x2 + 1, x1 - 1, y - dy, -dy) to s
x1 = x1 + 1
while x1 < x2 and not Inside(x1, y):
x1 = x1 + 1
x = x1
Преимущества
[ редактировать ]- В 2–8 раз быстрее, чем пиксельно-рекурсивный алгоритм.
- Шаблон доступа удобен для кэша и битовой плоскости. [6]
- Можно рисовать горизонтальную линию, а не задавать отдельные пиксели. [6]
Недостатки
[ редактировать ]- По-прежнему посещает уже заполненные пиксели. (Для популярного алгоритма — 3 сканирования большинства пикселей. Для последнего — дополнительное сканирование только тех пикселей, где в заполненной области есть дыры.) [3]
- Не подходит для заполнения узором, так как для изменения требуются результаты теста пикселей.
Добавление поддержки заполнения узором
[ редактировать ]Два распространенных способа заставить алгоритмы на основе интервалов и пикселей поддерживать заполнение шаблоном — либо использовать уникальный цвет в качестве простой заливки, а затем заменить его шаблоном, либо отслеживать (в двумерном логическом массиве или в виде областей), какие пиксели были посещены, используя его для обозначения того, что пиксели больше не подлежат заполнению. Затем Inside должен вернуть false для таких посещенных пикселей. [3]
Теоретико-графовое заполнение
[ редактировать ]Некоторые теоретики применили к этой проблеме явную теорию графов, рассматривая промежутки пикселей или их агрегаты как узлы и изучая их связность. Первый опубликованный алгоритм теории графов работал аналогично заполнению интервалов, описанному выше, но имел возможность определять, когда он будет дублировать заполнение интервалов. [9] К сожалению, в нем были ошибки, из-за которых некоторые заливки не выполнялись. [10] Позже был опубликован исправленный алгоритм, основанный на аналогичной основе теории графов; однако он изменяет изображение по ходу выполнения, чтобы временно заблокировать потенциальные петли, усложняя программный интерфейс. [10] Опубликованный позже алгоритм основывался на том, что граница отличается от всего остального на изображении, и поэтому не подходит для большинства применений; [11] [3] для бухгалтерского учета также требуется дополнительный бит на пиксель. [3]
Преимущества
[ редактировать ]- Подходит для прямого заполнения узором, поскольку никогда не проверяет заполненные пиксели повторно. [9] [10] [11]
- Двойная скорость по сравнению с исходным алгоритмом интервала для несложных заливок. [3]
- Шаблон доступа удобен для кэша и битовой плоскости. [6] [3]
Недостатки
[ редактировать ]- Регулярно интервал приходится сравнивать с любым другим «фронтом» в очереди, что значительно замедляет сложные заполнения. [3]
- Переключение между областями теории графов и пикселями усложняет понимание.
- Код довольно сложен, что увеличивает вероятность ошибок.
Заполнение на основе ходьбы (метод фиксированной памяти)
[ редактировать ]Существует метод, который практически не использует память для четырехсвязных областей, притворяясь художником, пытающимся закрасить область, не загоняя себя в угол. Это также метод решения лабиринтов . Четыре пикселя, образующие основную границу, проверяются, чтобы определить, какие действия следует предпринять. Художник мог оказаться в одном из нескольких состояний:
- Все четыре граничных пикселя заполнены.
- Три граничных пикселя заполнены.
- Два граничных пикселя заполнены.
- Один граничный пиксель заполнен.
- Нулевые граничные пиксели заполняются.
Если необходимо следовать по пути или границе, используется правило правой руки. Художник следует за регионом, кладя правую руку на стену (границу региона) и продвигаясь по краю региона, не убирая руки.
В случае №1 художник рисует (заполняет) пиксель, на котором стоит художник, и останавливает алгоритм.
В случае №2 существует путь, ведущий из зоны. Нарисуйте пиксель, на котором стоит художник, и двигайтесь в направлении открытого пути.
В случае №3 два граничных пикселя определяют путь, который, если мы нарисуем текущий пиксель, может помешать нам когда-либо вернуться на другую сторону пути. Нам нужна «метка», чтобы определить, где мы находимся и в каком направлении движемся, чтобы увидеть, вернемся ли мы когда-нибудь точно к тому же пикселю. Если мы уже создали такую «метку», то сохраняем нашу предыдущую метку и переходим к следующему пикселю по правилу правой руки.
Метка используется для первой встреченной границы в 2 пикселя, чтобы запомнить, где начался проход и в каком направлении двигался художник. Если знак встречается снова и художник движется в том же направлении, то художник знает, что можно безопасно закрасить квадрат с знаком и продолжить движение в том же направлении. Это связано с тем, что (по какому-то неизвестному пути) пиксели на другой стороне метки могут быть достигнуты и окрашены в будущем. Знак удаляется для использования в будущем.
Если художник встречает отметку, но движется в другом направлении, значит, произошла своего рода петля, из-за которой художник возвращается к отметке. Эту петлю необходимо устранить. Отметка берется, и затем художник движется в направлении, указанном ранее отметкой, используя правило левой руки для границы (аналогично правилу правой руки, но с использованием левой руки художника). Это продолжается до тех пор, пока не будет найдено пересечение (с тремя или более открытыми граничными пикселями). Продолжая использовать правило левой руки, художник теперь ищет простой проход (созданный двумя граничными пикселями). После обнаружения этого двухпиксельного граничного пути этот пиксель закрашивается. Это разрывает цикл и позволяет алгоритму продолжить работу.
В случае №4 нам нужно проверить противоположные 8-связные углы, чтобы увидеть, заполнены они или нет. Если один или оба заполнены, это создает пересечение многих путей и не может быть заполнено. Если оба пусты, то текущий пиксель можно закрасить, а художник может двигаться по правилу правой руки.
Алгоритм меняет время на память. Для простых форм это очень эффективно. Однако если форма сложна и содержит множество элементов, алгоритм тратит много времени на отслеживание краев области, пытаясь убедиться, что все их можно закрасить.
Алгоритм ходьбы был опубликован в 1994 году. [12]
Псевдокод
[ редактировать ]Это реализация псевдокода оптимального алгоритма заливки фиксированной памяти, написанная на структурированном английском языке:
- Переменные
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 включает в себя инструмент заполнения корзины, который дает результат, аналогичный обычным операциям с растровыми изображениями, и действительно использует его: холст визуализируется, операция заливки выполняется в выбранной области, а затем результат отслеживается обратно до пути. Он использует концепцию граничного условия .
См. также
[ редактировать ]- Поиск в ширину
- Поиск в глубину
- Обход графа
- Маркировка подключенных компонентов
- Алгоритм Дейкстры
- Водораздел (обработка изображений)
Внешние ссылки
[ редактировать ]- Примеры реализации рекурсивной и нерекурсивной, классической и растровой заливки , автор Лоде Вандевенн.
- Пример реализации Java с использованием нерекурсивного Q.
Ссылки
[ редактировать ]- ^ Jump up to: а б с Смит, Элви Рэй (1979). Тоновая заливка . SIGGRAPH '79: Материалы 6-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 276–283. дои : 10.1145/800249.807456 .
- ^ Jump up to: а б Экланд, Брайан Д; Весте, Нил Х (1981). Алгоритм флага края — метод заливки для дисплеев растрового сканирования . Транзакции IEEE на компьютерах (том: C-30, выпуск: 1). стр. 41–48. дои : 10.1109/TC.1981.6312155 .
- ^ Jump up to: а б с д и ж г час я дж Фишкин, Кеннет П.; Барский, Брайан А. (1985). Анализ и алгоритм распространения заполнения . Компьютерные изображения: современные исследования графического интерфейса '85. стр. 56–76. дои : 10.1007/978-4-431-68033-8_6 .
- ^ Ньюман, Уильям М; Спроролл, Роберт Флетчер (1979). Принципы интерактивной компьютерной графики (2-е изд.). МакГроу-Хилл. п. 253. ИСБН 978-0-07-046338-7 .
- ^ Павлидис, Тео (1982). Алгоритмы обработки графики и изображений Спрингер-Верлаг. п. 181. ИСБН 978-3-642-93210-6 .
- ^ Jump up to: а б с д и ж г час я Левой, Марк (1982). Алгоритмы затопления территории . SIGGRAPH 1981 Конспект курса двумерной компьютерной анимации.
- ^ Фоли, доктор медицинских наук; ван Дам, А; Файнер, СК; Хьюз, СК (1990). Компьютерная графика: принципы и практика (2-е изд.). Аддисон-Уэсли. стр. 979–982. ISBN 978-0-201-84840-3 .
- ^ Хекберт, Пол С. (1990). «IV.10: Алгоритм заполнения семян». В Гласснере, Эндрю С. (ред.). Графические драгоценности . Академическая пресса. стр. 275–277. ISBN 0122861663 .
- ^ Jump up to: а б Либерман, Генри (1978). Как раскрашивать в книжке-раскраске . SIGGRAPH '78: Материалы 5-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 111–116. дои : 10.1145/800248.807380 .
- ^ Jump up to: а б с Шани, Ури (1980). Заполнение областей в двоичных растровых изображениях: теоретико-графовый подход . SIGGRAPH '80: Материалы 7-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 321–327. дои : 10.1145/800250.807511 .
- ^ Jump up to: а б Павлидис, Тео (1981). Контурная заливка в растровой графике . SIGGRAPH '81: Материалы 8-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 29–36. дои : 10.1145/800224.806786 .
- ^ Генрих, Доминик (1994). Экономичное заполнение областей в растровой графике . Визуальный компьютер. стр. 205–215. дои : 10.1007/BF01901287 .