Устранение ступенчатого эффекта

В растровых системах при невысокой разрешающей способности (меньше 300 dpi)

существует проблема ступенчатого эффекта (aliasing) — при большом шаге сетки растра пикселы линий образуют как бы ступени лестницы.

Рассмотрим  это  на  примере  отрезка  прямой  линии.  Вообще  говоря,  растровое изображение объекта определяется алгоритмом закрашивания пикселов, соответствующих

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

На рис. 3.11 показано растровое изображение толстой прямой линии, на которую для

сравнения наложен идеальный контур исходной линии.

Рис. 3.11. Растровое изображение отрезка линии

Устранение ступенчатого эффекта называется на английском языке antialiasing. Для того чтобы растровое изображение линии выглядело более ровным, можно цвет угловых пикселов "ступенек лестницы" заменить определенным оттенком, промежуточным между цветом объекта и цветом фона. Будем вычислять цвет пропорционально части площади ячейки растра, покрываемой идеальным контуром объекта. Если площадь всей ячейки обозначить как S, а часть площади, покрываемой контуром, — Sx, то искомый цвет равняется

На рис. 3.12 показано сглаженное растровое изображение, построенное указанным выше методом.

Рис. 3.12. Сглаживание

Методы визуализации сглаженных растровых изображений можно разделить на две группы. Первую группу составляют алгоритмы растеризации для отдельных примитивов

— линий,  фигур  с  заполнением.  В  ходе  вывода  последовательности  примитивов  для

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

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

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

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

выхватывает пикселы (рис. 3.13).

Для определения цвета текущего пиксела вычисляется некоторая функция,

учитывающая значение цветов пикселов этого окна. Базовую операцию такого фильтра можно представить так:

где Ρ — значение цвета текущего пиксела, F — новое значение цвета пиксела, К — нормирующий коэффициент, Μ — двумерный массив коэффициентов, который определяет свойства фильтра (обычно этот массив называют "маской").

Рис. 3.13. Окно локального цифрового фильтра

Размеры  окна  фильтра:   —  по  горизонтали и  (imax  –  imin  +1)  —  по вертикали.

При имеем фильтр с окном 3x3, частоиспользуемый на практике.

Для обработки всего растра необходимо выполнить указанные выше вычисления для

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

На  рис.  3.14  представлены  результаты  работы  двух  вариантов  нерекурсивного сглаживающего фильтра, использующего окно (маску) 3х3.

Рис. 3.14. Два сглаживающих фильтра

Значение нормирующего коэффициента здесь выбрано равным сумме элементов маски. Этим обеспечивается сохранение масштаба яркости преобразованного растра. Отметим, что маска — это не матрица, а массив коэффициентов, располагающихся соответственно пикселам окна. Средний фильтр можно задать и маской 2x2 — отбросить нулевые коэффициенты.

При  сглаживании  цветных  изображений  можно  использовать  модель  RGB  и

производить фильтрацию по каждому компоненту.

С помощью локальной цифровой фильтрации можно выполнять довольно

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

Дизеринг

Хорошо, если растровое устройство отображения может прямо воссоздавать тысячи

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

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

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

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

Если  графическое  устройство  не  способно  воссоздавать  достаточное  количество

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

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

Рассмотрим методы дизеринга. Простейшим вариантом дизеринга можно считать

создание оттенка цвета парами соседних пикселов.

Если  рассмотреть  ячейки  из  двух пикселов  (рис.  3.15),  то  ячейка  номер  1  дает

оттенок цвета С:

где С1 и С2 — цвета, которые графическое устройство непосредственно способно воссоздать для любого пиксела. Числовые значения С, Сj и С2 можно рассчитать в полутоновых градациях или в модели RGB — в отдельности для любого компонента.

Рис. 3.15. Ячейки

Пример растра с использованием ячеек из двух пикселов приведен на рис. 3.16. Как видим, для создания промежуточного оттенка (С) ячейки образуют вертикальные линии, которые очень заметны. Для того чтобы человек воспринял это как сплошной оттенок, необходимо, чтобы угловой размер ячеек был меньше одной угловой минуты. Можно изменять положения таких ячеек в растре, располагая их, например, по диагонали. Это лучше, но не намного.

Рис. 3.16. Простейший дизеринг

Наиболее часто используют квадратные ячейки больших размеров. Приведем пример ячеек размером 2x2 (рис. 3.17). Такие ячейки дают 5 градаций, из них три комбинации (1, 2, 3) образуют новые оттенки.

Предоставим также примеры ячеек других размеров (рис. 3.18).

Рис. 3.17. Ячейки 2x2

Рис. 3.18. Ячейки 3x3 предоставляют 10                     Ячейки 5x5 дают 26 градаций градаций

Расчет цвета, который соответствует одной из комбинаций пикселов в ячейке, можно выполнить следующим образом. Если пикселы ячейки могут быть только двух цветов (С1 и С2), то необходимо подсчитать часть площади ячейки для пикселов каждого цвета. Цвет ячейки С можно оценить соотношением

где S— общая площадь ячейки; S1 и S2 — части площади, занятые пикселами цветов С1 и С2 соответственно, причем S1+ S2 = S. Проще всего, если пикселы квадратные, а их размер равняется шагу расположения пикселов. Примем площадь одного пиксела за единицу. В этом случае площадь, занятая пикселами в ячейке, равняется их количеству (рис. 3.19).

Рис. 3.19. Площадь определяется количеством пикселов

Для ячейки 5x5, изображенной на рисунке 3.18 (справа), рассчитаем цвет С для

некоторых цветов С1  и С2. Если C1  — белый цвет (R1  G1  B1  ) = (255, 255, 255), а С2 — черный (R2  G2 В2) = (0, 0, 0), тогда

то есть мы получили светло-серый цвет.

Еще пример. Если С1 — желтый (R1 G1 В1) = (255, 255, 0), а С2 — красный (R2 G2 В2)

= (255, 0, 0), то С= (255, 204, 0). Это оттенок оранжевого.

Итак, если в ячейке размерами n x n использованы два цвета, то с помощью этой ячейки можно получить n2 + 1 разных цветовых градаций. Две комбинации пикселов ячейки — если все пикселы ячейки имеют цвет С1 или С2 — дают цвет соответственно С1 или C2. Все другие комбинации дают оттенки, промежуточные между С1 и С2.

Можно  считать,  что ячейки  размером  пхп  образуют  растр  с  разрешающей

способностью в n раз меньшей, чем у начального растра, а глубина цвета возрастает пропорционально n2. Для характеристики изображений, которые создаются методом дизеринга, используют термин — линиатура растра. Линиатура вычисляется как количество линий (ячеек) на единицу длины — сантиметр, миллиметр, дюйм. В последнем случае единица измерения для линиатуры — lpi (по аналогии с dpi).

Как реализовать метод дизеринга в графической системе? Рассмотрим примеры преобразования растрового изображения размером pxq с определенной глубиной цвета в другой растр, предназначенный для отображения с помощью графического устройства, в котором используется ограниченное количество основных цветов. В таком случае надо выбрать размеры ячейки тхп, которые обеспечивают достаточное количество цветовых градаций. Потом любой пиксел растра превращается в пиксел растра отображения. Это можно осуществить двумя способами.

Первый способ. Любой пиксел заменяется ячейкой из mxn пикселов. Это самое точное преобразование по цветам, но размер растра увеличивается и составляет mpxnq пикселов.

Второй  способ.  Здесь  размеры  растра  не  изменяются.  Цвет  любого  пиксела

преобразованного растра вычисляется следующим образом.

• Определяем координаты пиксела (х, у) для преобразуемого растра.

• Находим цвет пиксела (х, у).

• По цвету пиксела находим номер (к) ячейки, наиболее адекватно представляющей

этот цвет.

• По координатам (х, у) вычисляем координаты пиксела внутри ячейки:

• Находим цвет (С) пиксела ячейки с координатами (хk, уk ).

• Записываем в преобразованный растр пиксел (х, у) с цветом С.

Такой способ можно использовать не для любых вариантов расположения пикселов в ячейках. Конфигурации пикселов должны быть специально разработаны для таких преобразований. Одно из требований можно сформулировать так. Если ячейки разработаны на основе двух цветов, например, белого и черного, а градации изменяются пропорционально номеру ячейки, то необходимо, чтобы ячейка с номером (i) для более темной градации серого содержала бы все черные пикселы ячейки номер (i - 1).

Рассмотрим пример изображения, созданного на основе ячеек 5x5.

Для создания такого изображения специально была выбрана небольшая

разрешающая способность, чтобы подчеркнуть структуру изображения. Ячейки образуют достаточно заметный квадратный растр (рис. 3.20).

Рис. 3.20. Пример квадратного растра с ячейками 5x5

Для улучшения восприятия изображения можно использовать другое расположение ячеек, например, диагональное (рис 3.21).

3.21. Диагональное расположение ячеек 5x5

Диагональное расположение можно получить, если сдвигать четные строки ячеек. А для того чтобы получить диагональную структуру растра, подобную той, что используется для печати газет, можно использовать квадратное расположение ячеек другого типа (рис. 3.22).

3.22. Диагональные структуры: а - сдвиг строк ячеек, б - ячейки другого типа

Вы, наверно, уже заметили, что для всех приведенных выше примеров дизеринга

ячейки образуют точки переменного размера с постоянным шагом. Однако часто используется другой подход — переменная плотность расположения точек постоянного размера. Такой способ получил название частотной модуляции (ЧМ) (рис. 3.23).

3.23. ЧМ-ячейки 6x6

Положительная черта способа ЧМ — меньшая заметность структуры растра. Однако его использование усложнено в случае, когда размер пикселов больше, чем шаг. Начиная с определенной плотности, пикселы смыкаются. Кроме того, на дискретном растре невозможно обеспечить плавное изменение плотности (частоты), в особенности для ячеек небольшого размера. Рассмотрим пример ячеек 5x5, реализующих ЧМ-дизеринг (рис. 3.24).

3.24. Набор ЧМ-ячеек 5x5

Для изображений, созданных методом ЧМ-дизеринга, растрирование менее заметно (рис. 3.25).

Рис. 3.25. Диагональное расположение ЧМ-ячеек 5x5

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

Другой разновидностью дизеринга являются методы, в которых вообще не используются ячейки. Одним из популярнейших методов дизеринга в настоящее время является "'error diffusion" метод Флойда-Стейнберга. Он обеспечивает высокое качество изображений и часто используется в драйверах принтеров и графических редакторах (рис. 3.26).

Рис. 3.26. Дизеринг методом «error-diiffusion» Флойда-Стейнберга

Рассмотрим алгоритм Флойда-Стейнберга. При обработке первой строки растра для первого пиксела цвет (С) заменяется на ближайший из возможных (X). Например, пиксел серого цвета заменяется соответствующим черным или белым. Для этого пиксела вычисляется ошибка Ε = С-Х. Эта ошибка в пропорции (7/16, 5/16, 3/16, 1/16) распределяется по соседним пикселам (отсюда и название метода — "error diffusion "). При обработке следующего пиксела рассматривается уже сумма его собственного цвета плюс значение ошибки, которое дошло к этому пикселу. Как распространяется ошибка — это зависит от направления сканирования строки (рис. 3.27).

Рис. 3.27. Добавление частей ошибки к соседним символам     Напрвления сканирования

Для уменьшения вероятности образования регулярных узоров рекомендуется соседние строки сканировать в противоположных направлениях — "змейкой".

Этот метод был предложен для градаций серого, однако, он с успехом используется,

например, для преобразования 24-битных изображений в 256-цветные.