Заливка

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Рекурсивна заливка у восьми напрямах

Заливка (від англ. flood fill чи англ. seed fill) — це алгоритм, що визначає область, «поєднану» з певним елементом у багатомірному масиві (як правило, це двовимірний масив точок растрового зображення). Алгоритм застосовується у програмах для редагування графіки для визначення області, яку треба заповнити певним кольором.

Заливка зображень — часто потрібна на практиці функція, суть якої — заповнити деяку область зображення, обмежену контуром, що заданий певним кольором.

Алгоритм[ред. | ред. код]

Рекурсивна заливка у чотирьох напрямах

Алгоритм має три параметри на вхід: стартовий елемент (вузол), замінюваний колір і колір заливки. Відшукуються всі елементи масиву, що зв'язані з початковим шляхом змінюємого кольору, і перефарбовуються у колір заливки. Варіантів реалізації достатньо багато, але всі вони так чи інакше використовують чергу або стек. Ось псевдокод простого рекурсивного алгоритму, в якому зв'язність у двовимірному масиві визначається у 4 напрямах: 

 Заливка (вузол, замінюваний колір, колір заливки):
 1. Якщо замінюваний колір дорівнює кольору заливки, то повернутись.
 2. Якщо колір вузла  не дорівнює  замінюваному кольору, то повернутись.
 3. Встановити колір вузла у колір заливки.
 4. Виконати Заливку (крок на захід від вузла, замінюваний колір, колір заливки).
    Виконати Заливку (крок на схід від вузла, замінюваний колір, колір заливки).
    Виконати Заливку (крок на північ від вузла, замінюваний колір, колір заливки).
    Виконати Заливку (крок на південь від вузла, замінюваний колір, колір заливки).
 5. Повернутися.

Хоча цей алгоритм і простий для розуміння, але він практично не застосовується у випадках обмеженості рекурсії (наприклад, у аплетах Java)

Інші способи реалізації[ред. | ред. код]

Наступний псевдокод показує реалізацію, засновану на застосуванні черги в явному вигляді. Це схоже на рекурсивне рішення, за винятком того, що замість рекурсивних викликів, він штовхає вузли в стек: 

 Заливка (вузол, замінюваний колір, колір заливки):
 1. Якщо замінюваний колір дорівнює кольору заливки, то повернутись.
 2. Присвоїти  Q  порожню чергу.
 3. Додати вузол у кінець Q.
 4. До тих пір, поки  Q  не порожній:
 5.    Присвоїти  n  перший елемент  Q 
 6.    Видалити перший елемент  Q .
 7.    Якщо колір  n  дорівнює  замінюваному кольору :
 8.       Встановити колір n до кольору заливки і відмітити "n" як елемент,що обробляється.
 9.       Додати західний вузол до кінця  Q , якщо західний елемент ще не був оброблений.
10.       Додати східний вузол до кінця  Q , якщо східний  елемент ще не був оброблений.
11.       Додати північний вузол до кінця  Q , якщо північний елемент ще не був оброблений.
12.       Додати південний вузол до кінця  Q , якщо південний елемент ще не був оброблений.
13.Повернутися.

Для того, щоб використовувати прапор "оброблено", усі пікселі доведеться ініціалізувати як необроблені перед запитом цього алгоритму. Найбільш практичні методики оптимізують використання стека або черги, вводячи цикл за «західним» і «східним» напрямками: 

 Заливка (вузол, замінюваний колір, колір заливки):
 1. Присвоїти  Q  порожню чергу.
 2. Якщо колір  вузла не дорівнює замінюваному кольору, повернутись.
 3. Додати  вузол  у  Q .
 4. Для кожного елемента від  N  до  Q :
 5.   Присвоїти  w  і  e  дорівнюють  N .
 6.   Переміщайте  w  на захід, поки колір вузла на захід від  w  більше не відповідає  замінюваному кольору .
 7.   Переміщайте  е  на схід, поки колір вузла на схід від  е  більше не відповідає  замінюваному кольору .
 8.   Для кожного вузла  n  між  w  і  e :
 9.    Встановіть колір  n  як  колір заливки         
10.    Якщо колір вузла на північ від  n  є  замінюваним кольором , додати цей вузол у  Q .
11.    Якщо колір вузла на південь від  n  є  замінюваним кольором , додати цей вузол у  Q .
12. Продовжувати цикл доки  Q  не закінчиться.
13. Повернутись.

Якщо прописати в алгоритмі використання окремого масиву для зберігання форми області, це дозволить узагальнити його на випадок «нечіткого» заповнення, коли елементи можуть дещо відрізнятися від початково заданих. Використання цього додаткового масиву як альфа-каналу дозволяє створити плавний перехід на кордонах між залитою і не залитою областями.

Метод заливки для фіксованого об'єму пам'яті[ред. | ред. код]

Метод заливки, що реалізується в обмеженому об'ємі пам'яті (англ. Fixed memory method), або, як його ще називають, — «метод правої руки».

Опис методу[ред. | ред. код]

Є метод, що практично не використовує додаткової пам'яті для зв'язуючих по 4 напрямках[en] (див. Околиця фон Неймана) областей. Цим же методом можна шукати вихід з лабіринту. Уявіть собі маляра, який фарбує область так, щоб не опинитися затиснутим в кутку. Початкові кордони — це чотири пікселя, які маляр розглядає, щоб вибрати одну з можливих дій. Основні можливі стани:

  1. Всі 4 граничних пікселя пофарбовані.
  2. Три граничних пікселя пофарбовані.
  3. Два граничних пікселя пофарбовані.
  4. Один граничний піксель зафарбований.
  5. Жоден з граничних пікселів не зафарбований.

При продовженні кордону використовується метод правої руки. Маляр обходить область, тримаючи праву руку на «стіні» (кордоні області) і просувається, не відриваючи руки.

У випадку № 1 маляр фарбує піксель, на якому стояв, і закінчує (алгоритм завершений).

У випадку № 2 існує шлях з області назовні. Маляр фарбує піксель, на якому стояв, і рухається цим шляхом.

У випадку № 3 два граничних пікселя створюють смугу, яка, якщо ми пофарбуємо поточний піксель, може відрізати нас від усього, що знаходиться по її іншу сторону. Потрібно закріпити «стрілку», що вказує, де ми зараз і куди дивимося, щоб, якщо ми колись повернемося на цей піксель, ми могли її побачити. Якщо така стрілка вже намальована, ми її зберігаємо і рухаємося далі за правилом правої руки.

Стрілка на першому двохпіксельному кордоні фіксує, де маляр почав роботу і куди звідти пішов. Якщо маляр зустрічає ту ж мітку, рухаючись в тому ж напрямку, то він розуміє, що фарбувати цей квадрат, рухаючись у цьому напрямку, безпечно: пікселі на іншій стороні по якомусь поки не відомому шляху будуть доступні для фарбування в майбутньому. Мітка знімається, і її можна поставити десь ще.

Якщо ж маляр зустрічає стрілку, що вказує не туди, куди він йде, значить, він пройшов якимось шляхом, що повернув його до мітки. Цю петлю треба виключити. Мітка забирається, а маляр рухається у вказаному нею напрямі, керуючись правилом лівої руки. Так він йде, поки не потрапить на перетин (з не менш ніж трьома пікселями відкритого кордону). Не відриваючи лівої руки, маляр шукає простий прохід (що складається з двох граничних пікселів). Знайшовши його, він фарбує цей піксель, петля розривається, і можна продовжувати алгоритм.

У випадку № 4 ми повинні перевірити протилежні зв'язані по 8 напрямам кути — пофарбовані вони чи ні. Якщо хоча б один з цих двох кутів пофарбований, виходить перетин багатьох шляхів, які ми зафарбувати не зможемо. Якщо обидва порожні, можемо пофарбувати поточний піксель і слідувати далі за правилом правої руки.

Алгоритм дає виграш в пам'яті за рахунок програшу за часом. Для областей простої форми він дуже ефективний, але в більш складних випадках багато часу витрачається на те, щоб відстежити межі області і переконатися, що все можна зафарбувати.

Перша комерційна реалізація цього алгоритму з'явилася в 1981 році на системі Vicom Image Processing, випущеної Vicom Systems, Inc. Також в цій системі був присутній і класичний рекурсивний алгоритм.

Алгоритм (англійською)[ред. | ред. код]

Це реалізація псевдокоду, який виконує алгоритм заливки, з фіксованим використанням пам'яті.

Змінні : 

    cur, mark, and mark2 each hold either pixel coordinates or a null value
         NOTE: when mark is set to null, do not erase its previous coordinate value.
               Keep those coordinates available to be recalled if necessary.
    cur-dir, mark-dir, and mark2-dir each hold a direction (left, right, up, or down)
    backtrack and findloop each hold boolean values
    count is an integer

(Примітка: усі напрямки (front, back, left, right) рахуються відносно поточного напрямку) 

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
	move forward
end while

jump to START

MAIN LOOP:
	move forward
	if right-pixel is empty
		if backtrack is true and findloop is false and either front-pixel or left-pixel is empty
			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
		do
			turn right
		while front-pixel is empty
		do
			turn left
		while front-pixel is filled
	end if
	switch count
		case 1
			if backtrack is true
				set findloop to true
			else if findloop is true
				if mark is null
					restore mark
				end if
			else if front-left-pixel and back-left-pixel are both empty
				clear mark
				fill cur
				jump to PAINT
			end if
		end case
		case 2
			if back-pixel is filled
				if front-left-pixel is not filled
					clear mark
					fill cur
					jump to PAINT
				end if
			else if mark is not set
				set mark to cur
				set mark-dir to cur-dir
				clear mark2
				set findloop and backtrack to false
			else
				if mark2 is not set
					if cur is at mark
						if cur-dir is the same as mark-dir
							clear mark
							turn around
							fill 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
						set mark2 to cur
						set mark2-dir to cur-dir
					end if
				else
					if cur is at mark
						set cur to mark2
						set cur-dir to mark2-dir
						clear mark and mark2
						set backtrack to false
						turn around
						fill cur
						jump to PAINT
					else if cur at mark2
						set mark to cur
						set cur-dir and mark-dir to mark2-dir
						clear mark2
					end
				end if
			end if
		end case
		case 3
			clear mark 			
			fill cur
			jump to PAINT
		end case
		case 4
			fill cur
			done
		end case
	end switch
end MAIN LOOP

Метод сканування рядків[ред. | ред. код]

Алгоритм можна прискорити, заливаючи відразу лініями. Замість вкладання в стек координат кожного з можливих майбутніх пікселів розглядаються сусідні рядки (ті, що вище і ті, що нижче), і в них визначаються суміжні сегменти, які при наступному проході можна залити; координати (початок чи кінець) втискуються в стек. У більшості випадків рядковий алгоритм на порядок швидше попіксельного алгоритму. Його перевага в тому, що кожен піксель перевіряється тільки один раз.

У векторній графіці[ред. | ред. код]

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

Поведінка при великих розмірах[ред. | ред. код]

Заливка у чотирьох напрямах, яка використовує чергу для зберігання
Заливка у чотирьох напрямах, яка використовує стек для зберігання

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

Алгоритм заливки у чотирьох напрямах використовує суміжну техніку і чергу як місце для зберігання пікселів та ромбовидно заповнюється.

Ефективність: для заливки одного пікселя перевіряються чотири (вісім, якщо рух іде у восьми напрямках)

Алгоритм заливки у чотирьох напрямах використовує суміжну техніку і стек як місце для зберігання пікселів з лінійною заливкою. Цей алгоритм може бути добре видно у старих 8-бітних іграх, що були створені за допомогою Graphic Adventure Creator[en].

Ефективність: для заливки одного пікселя перевіряються чотири (вісім, якщо рух іде у восьми напрямках)

Посилання[ред. | ред. код]


Алгоритми Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (серпень 2017)
Отримано з https://uk.wikipedia.org/w/index.php?title=Заливка&oldid=36243082