Основные методы устранения ступенчатости

Построчный алгоритм заполнения с затравкой

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

Пока стек не пуст:

1) извлекаем пиксель (X,Y) из стека;

2) заполняем максимум возможного интервала, в котором находится пиксель вправо и влево до достижения граничных пикселов;

3) заполняем крайнюю левую L_x и крайнюю правую R_x абсциссы заполненного интервала;

4) в соседних строках над и под интервалом L_x и R_x находим незаполненные к настоящему моменту внутренние пиксели области, как мы уже заметили, объединенные в интервалы, а в каждом из этих интервалов находим крайние правые пиксели, каждый из этих пикселов вставляем в стек в качестве затравочных.

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

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

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

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

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

Модифицированный алгоритм Брезенхема с устранением ступенчатости для первого квадранта

Отрезок проводится из (X₁,Y₁) в (X₂,Y₂)

I - число доступных уравнений интенсивности

все переменные целого типа

инициализация переменных

X=Х₁; Y=Y₁; DX=X₂-X₁; DY=Y₂-Y₁;

m=(I*DY)/DX;

W=I–m;

e=I/2;

plot(X,Y,m/2);

while (X<X₂)

if e<W then

X=X+1;

e=e+m

else

X=X+1;

Y=Y+1;

e=e-W;

end{if};

plot(X,Y,e)

end{while}

end.