Особенность методов, использующих затравочное заполнение состоит в том, что нам известен (или мы задаем) хотя бы один пиксел внутри области заполнения. Область может быть либо внутренне (Рис.1) либо гранично-определенной (Рис.2). Для гранично-определенных областей ни один пиксел внутри не может иметь выделенное значение.
Рассмотрению подвергнутся алгоритмы, позволяющие выполнить заполнение для гранично определенных областей(для внутренне заполненных — процесс аналогичен). Вспоминая определение связности (4 или 8), становится понятным, что способ заполнения 4-х связной области с помощью 8 -ми связных переходов будет неверен . Поэтому для задания гранично-определенных областей будем применять 4-связный вариант. Однако возможна модификация алгоритмов, если применить задание диагональных направлений соседних пикселов. Простой алгоритм заполнения с затравкой.
Алгоритм предусматривает работу со стеком прямого действия (стеком с дисциплиной обслуживания FILO), т.е.
first input last output (по принципу патронов в магазине). Принцип работы алгоритма следующий:
Поместить затравочный пиксел в стек
Пока стек не пуст
Извлечь пиксел из стека
Присвоить пикселу требуемое значение
Для каждого из соседних к текущему 4-х связных пикселов проверить: является ли он граничным пикселом или не присвоено ли уже пикселу требуемое значение. Проигнорировать пиксел в любом из этих двух случаев. В противном случае поместить пиксел в стек.
На псевдокоде это можно представить таким образом:
Затравка (х, у) выдает затравочный пиксел
Push — процедура, которая помещает пиксел в стек
Pop — процедура, которая извлекает пиксел из стека
Пиксел (х, у) = Затравка (х, у)
инициализируем стек
Push Пиксел (х, у)
while (стек не пуст)
извлекаем пиксел из стека
Pop Пиксел (х, у)
if Пиксел (х, у) < > Нов_значение then
Пиксел (х, у) = Нов_значение
end if
проверим, надо ли помещать соседние пикселы в стек
if (Пиксел (х + 1, у) < > Нов_значение and
Пиксел (х + 1, у) < > Гран_значение) then
Push Пиксел (х + 1, у)
if (Пиксел (х, у + 1) < > Нов_значение and
Пиксел (х, у + 1) < > гран_значение) then
Push Пиксел (х, у + 1)
if (Пиксел (х — 1, у) < > Нов_значение and
Пиксел (х — 1, у) < > Гран_значение) then
Push Пиксел (х — 1, у)
if (Пиксел (х, у — 1) < > Нов_значение and
Пиксел (х, у — 1) < > гран_значение) then
Push Пиксел (х, у — 1)
end if
end while
Простой алгоритм с затравкой не всегда применим, ввиду большого размера стека. Да и информация, содержащаяся в последнем может повторяться или быть лишней. Поэтому ставится цель — минимизация стека. Достигнуть этого можно применив построчный алгоритм заполнения с одним затравочным пикселом (для любого интервала на одной сканирующей строке) к гранично-определенным областям. Допускается использование выпуклых фрагментов или имеющих дыры.
· Непрерывный интревал — группа примыкающих друг к другу пикселов.
Схема и описание алгоритма на псевдокоде приведены в Лабораторной работе № 9.
