Алгоритмические основы растровой графики

Алгоритмические основы растровой графики

2-е издание, исправленное

Иванов Д.В.
Хропов А.А.
Кузьмин Е.П.
Карпов А.С.
Лемпицкий В.С.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Алгоритмические основы растровой графики/ Д.В. Иванов, А.А. Хропов, Е.П. Кузьмин, А.С. Карпов,
В.С. Лемпицкий - М.: Национальный Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Иванов Д.В., Хропов А.А., Кузьмин Е.П., Карпов А.С., Лемпицкий В.С., 2007-2016

3

Предисловие

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

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

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

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

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

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

4

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

Изложенный в данной книге материал апробирован многолетней практикой его
преподавания в рамках специального курса лекций “Алгоритмические основы
машинной графики”, читаемого авторами на Механико-математическом факультете
МГУ для студентов I-V курса и аспирантов. Надеемся, что приведенные в этом
пособии идеи будут полезны широкому кругу специалистов, - как начинающих
изучение, так и активно практикующих в своей работе алгоритмы растровой
компьютерной графики.

О записи алгоритмов

Алгоритмы в книге записываются на псевдокоде с синтаксисом напоминающим
объектно-ориентированные языки семейства C (такие как C++, C#, Java ). Основные
управляющие конструкции:

{действие1 ; действие2 ; … действиеN} - составное действие: выполнять
последовательно действие1, затем действие2, … действиеN.

if(условие) действие - если условие выполнено, то выполнить действие
(возможно составное).

if(условие) действие1 else действие2 - если условие выполнено, то выполнить

действие1 (возможно составное), в противном случае выполнить действие2
(возможно составное).

while(условие) действие - Цикл: если условие выполнено, то выполнить действие
(возможно составное), затем снова вернуться к началу цикла.

do действие while(условие); - Цикл: выполнить действие (возможно составное),
затем, если условие выполнено, то вернуться к началу цикла.

for(действие1 ; условие; действие2 ) действие - Цикл: удобная форма записи,
эквивалентная действие1; while(условие) { действие; действие2 ; }.

foreach(элемент in множество) действие - Цикл: действие выполняется
последовательно для каждого элемента из множества. При этом в действии могут
производиться манипуляции с текущим элементом.

break - выйти из цикла.

continue - перейти на следующую итерацию цикла.

ИмяФункции(аргумент1 , аргумент2 , … аргументN) - вызов функции с именем

5

ИмяФункции и аргументами аргумент1, аргумент2, … аргументN.

Объект.ИмяМетода(аргумент1 , аргумент2 , … аргументN) - вызов метода с
именем ИмяМетода и аргументами аргумент1, аргумент2, … аргументN для

объекта.

return значение - выйти из функции, возвратив значение.

6

Основные понятия. Представление цвета в машинной графике

Пояснение о записях алгоритмов. Растровая и векторная графика. Понятие растра.
Представление цвета в машинной графике. Цветовая модель RGB. Цветовая система
CIE XYZ и диаграмма цветности CIE. Преобразования между CIE XYZ и RGB.
Цветовые модели: CIE L*u*v*, CIE L*a*b*, CMY, CMYK, HSV, HLS, Y**, YUV,
YPbPr, YCbCr и YIQ

1.1. Растровая и векторная графика. Понятие растра

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

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

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

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

Формально, введем следующие определения:

Растр (англ. raster) - отображение вида

где 
, 
,

 обозначает множество всех подмножеств 
,

C - множество значений атрибутов (как правило, цвет).

f(i, j) - элемент растра, называемый пикселем (англ. pixel (от picture element)), в
русскоязычной литературе иногда также переводится как пиксел);

7

f(i, j) = (A(i, j),C(i, j)), где

 - область пикселя,
 - атрибут пикселя (как правило, цвет). Чаще всего мы будем

пользоваться следующими двумя видами атрибутов:

C(i, j) = I(i, j) - интенсивность (или яркость) пикселя;

C(i, j) = {R(i, j),G(i, j),B(i, j)} - цветовые атрибуты в цветовой
модели RGB (см. раздел 1.2).

Также иногда будут употребляться матричные обозначения:

Mij = (Aij ,Cij)

Aij может определяться двояко, в зависимости от того, с какой моделью мы хотим
работать:

Aij := (i, j) - одна точка. Пример такой модели растра см. на рис. 1.1;

 - квадрат. Пример такой модели растра см. на рис. 1.2.

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

В реальности, как правило, X и Y - ограниченные наборы неотрицательных целых
чисел; такой растр называется прямоугольным. Для него применимо понятие
Аспектовое отношение (англ. aspect ratio) - отношение ширины к высоте растра

(|X|/|Y|). Чаще всего такое понятие употребляется в связи с физическими растрами
(дисплеями, ПЗС-матрицами фотоаппаратов и т.д.) и записывается в виде простой
дроби с “:”, например “4:3”.

Рис. 1.1.  Модель растра первого типа.

8

Рис. 1.2.  Модель растра второго типа.

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

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

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

Устройства отображения растровой графики рассматриваются в следующей лекции.

1.2. Представление цвета в машинной графике

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

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

 ; математически 
 ), где c - яркость. Понятно, что описание цвета

9

путем описания функции в большинстве случаев слишком громоздко, хотя иногда и
применяется. К тому же, оно является избыточным, если подробнее рассмотреть, как
глаз человека воспринимает свет. На сетчатке глаза находятся два типа рецепторов:
палочки и колбочки. Палочки реагируют на степень яркости (или интенсивность)
падающего света (см. рис. 1.4), а колбочки отвечают за различение цветов; при этом
колбочки резко теряют свою чувствительность в темноте (в отличие от палочек),
поэтому все объекты начинают казаться серыми. Колбочки бывают трех видов (их
часто обозначают S, M и L )2), и их кривые относительной чувствительности
представлены на рис. 1.3. Пики на кривых чувствительности отвечают красному,
зеленому и синему цветам. При этом следует заметить, что восприимчивость к синему
цвету значительно ниже, чем к двум другим. Также важным свойством восприятия
света человеком является его линейность: при освещении двумя источниками света (со
спектральными функциями 
, 
 ) человек воспринимает их как один со

спектральной функцией, равной сумме 
. Этот факт называется

законом Грассмана. Благодаря ему можно строить сравнительно простую теорию
цветовосприятия.

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

Цветовая модель RGB

Из рассмотренной выше модели человеческого зрения вытекает, что достаточно
обоснованной является цветовая модель RGB (от англ. Red, Green, Blue - красный,
зеленый, голубой), в которой спектральная функция представляется как сумма кривых
чувствительности для каждого типа колбочек с неотрицательными весовыми
коэффициентами (обычно их нормируют от 0 до 1 ), которые так и обозначаются - R, G
и B. Эта модель характеризуется свойством аддитивности (мы складываем цвета для
получения новых). К примеру, спектральные функции:

черного цвета: fblack = 0, (R,G,B) = (0,0,0) ;
фиолетового цвета fviolet = fred + fblue, (R,G,B) = (1,0,1) ;
белого цвета fwhite = fred + fgreen + fblue, (R,G,B) = (1,1,1).

10