Устранение ступенчатости (антиэлайзинг)

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

Рис. 9.9. Распределение весов при увеличении разрешения в 4 раза

Рис. 9.10. Распределение весов при увеличении разрешения в 16 раз

Для предотвращения сильных искажений в этом случае можно, во- первых, повышать разрешение растра, что позволяет отображать всё более мелкие детали объектов. Но у этого подхода есть свои чисто физические ограничения. Второй подход заключается в том, что растр рассчитывается с более высоким разрешением, а изображается с более низким - путем усреднения атрибутов пикселей первого более детального растра с определенными весами. Если веса одинаковы, то мы получаем равномерное усреднение, как показано на рис. 9.9. Лучших результатов можно достигнуть, если использовать разные веса у пикселей первого растра. На рис. 9.10 показано распределение весов при детализации пикселя экранного растра.

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

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

Рис. 9.11. Отсекаемая отрезком площадь пикселя

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

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

(9.9)

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

Рассмотрим в качестве свертываемой функции и ядра следующие функции:

Рис. 9.12. Блок-схема модифицированного алгоритма Брезенхема

Тогда, в силу того, что подынтегральное выражение обращается в ноль при и при , получаем

Учитывая вид функции , получаем, что свертка будет отлична от нуля только на интервале . Значения свертки в некоторых точках приведены в таблице 9.1.

Таблица 9.1. Значения свертки в узлах
		1/2		3/2
		1/8	1/2	3/8

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

Рис. 9.13. Фигуры, соответствующие значениям свертки из таблицы 9.1

На рис. 9.13 приведен вид пересечения для всех пяти случаев из таблицы 9.1. Если сравнить эти результаты с рис. 9.11, то видно, что значения свертки при дают площадь той части пикселя, что находится внутри многоугольника (если считать ), а при - сумму площадей двух пересекаемых пикселей.

В заключение проиллюстрируем результат применения алгоритма устранения ступенчатости на примере изображения, полученного с помощью программы Corel Draw. Эта программа представляет собой развитый графический редактор, позволяющий строить объекты векторной графики. На рис. 9.14 показано изображение простых графических примитивов, предварительно переведенное в растровую форму, на котором при большом увеличении заметно сглаживание с применением оттенков серого цвета.

увеличить изображение
Рис. 9.14. Сглаженные изображения