8.5. СРАВНЕНИЕ И КОМБИНАЦИИ АЛГОРИТМОВ

Если сравнивать алгоритмы заполнения, основанные на анализе значений пикселов, используя в качестве критерия длину реализующей их программы, то простейшим явно окажется алгоритм 8.4, следующим будет алгоритм заполнения по критерию четности, алгоритм 8.3, и последним — алгоритм 8.5. Вычислительные процедуры, используемые в алгоритмах 8.3 и 8.5, в некоторых

отношениях одинаковы. Оба алгоритма опираются на одни и те же структуру данных и основную вычислительную процедуру. Они обращаются к подпрограмме только при работе с пикселами контура, так что число таких обращений приблизительно равно числу горизонтальных интервалов контура (другими словами, числу вершин К-ГСС). Пикселы, находящиеся во внутренней части заполняемой области, имеют последовательную адресацию, причем для каждого из них проводится только одна простая проверка — выясняется принадлежит пиксел контуру или нет. Последовательную адресацию можно очень эффективно реализовать на большинстве ЭВМ с помощью индексных регистров. Рекурсивный алгоритм использует при обработке каждого пиксела внутренней части области до четырех обращений к подпрограмме. Эти обращения являются дорогостоящими, что связано с необходимостью сохранять содержимое регистров, а также информацию, требующуюся для возвращения в начальную точку. Последнюю операцию можно эффективно выполнять на ЭВМ, в которых стеки реализованы аппаратно. Таким образом, основные затраты, связанные с использованием рекурсивного алгоритма, определяются необходимостью сохранять содержимое ячеек памяти (в случае, если соответствующие регистры используются как вызывающей, так и вызываемой программами). При использовании языка высокого уровня эти затраты довольно велики, однако можно попробовать написать программу, реализующую этот алгоритм, на языке ассемблера, для которого указанные затраты являются умеренными (см. задачу 8.5).

Теперь сравним между собой два нерекурсивных алгоритма. Заполнение области по критерию связности обладает двумя основными преимуществами: при связном контуре гарантируется отсутствие «утечки» пикселов; время вычислений пропорционально площади заполняемой области, а не площади прямоугольника, описывающего заполняемый контур, как это имеет место при использовании алгоритмов заполнения по критерию четности. Основные недостатки заполнения области по критерию связности состоят в следующем: а) необходимость знать хотя бы одну точку, лежащую во внутренней части области — при решении некоторых прикладных задач отыскание такой точки может вызвать затруднения; б) если заполняемая область имеет связный контур, но ее внутренняя часть не является связной, то заполненной окажется лишь та часть области, в которой находится затравочный пиксел (алгоритм заполнения по критерию четности обеспечит заполнение всех частей области); в) обход внутренней части области не соответствует организации растра, что может приводить к чрезмерному росту объема обмена между главной ЭВМ и управляющим устройством графического дисплея. Этот недостаток приобретает значение в связи с соображениями, приведенными в подразд. 8.3.2. Если нет возможности запрограммировать соответствующим образом микропроцессор, то все горизонтальные сроки можно считывать последовательно, размещая в оперативной

памяти три строки одновременно и используя их для определения порядков вершин ГСС. При использовании контроля четности строка, просмотренная один раз, больше просмотру подвергаться не должна. В случае алгоритмов заполнения по критерию связности дела обстоят уже не так. (Именно поэтому при заполнении приходится использовать значение яркости, отличное от значения яркости контура.) Итак, реальные вычислительные затраты могут оказаться выше из-за значительного объема операций ввода-вывода.

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

Рис. 8.12. (см. скан) Последовательность заполнения отдельных зон внутренней части области

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

Такой алгоритм не пропустит при заполнении те внутренние части области, которые не соединены с частью, содержащей затравочный пиксел.

Имеет смысл отметить, что большая часть вычислений, предусматриваемых алгоритмом 8.5, приходится на окрестности вертикальных экстремумов контура, т. е. на те точки, число которых довольно незначительно. На рис. 8.12 приведен пример области,

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

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

После этого заполнение осуществляется на основе критерия связности. Каждое значение уровня серого тона соответствует некоторому пикселу, вытолкнутому из стека. Алгоритм легко приспособить для заполнения изображения таким образом, что цвет заполняемых пикселов выбирается в зависимости от их адресов (вместо заполнения пикселами одного цвета) Соответствующий пример приведен на рис. 8 13.