WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«В. С. Лемпицкий, А. А. Хропов АЛГОРИТМИЧЕСКИЕ ОСНОВЫ РАСТРОВОЙ МАШИННОЙ ГРАФИКИ Учебное пособие Допущено учебно-методическим советом по прикладной математике и информатике УМО по ...»

Основы информатики и математики

Д. В. Иванов, А. С. Карпов, Е. П. Кузьмин,

В. С. Лемпицкий, А. А. Хропов

АЛГОРИТМИЧЕСКИЕ ОСНОВЫ

РАСТРОВОЙ МАШИННОЙ ГРАФИКИ

Учебное пособие

Допущено учебно-методическим советом по прикладной

математике и информатике УМО по классическому университетскому образованию в качестве учебного пособия для студентов

высших учебных заведений, обучающихся по специальности и

направлению «Прикладная математика и информатика» и по направлению «Информационные технологии»

Интернет-Университет БИНОМ .

Информационных Технологий Лаборатория знаний www.intuit.ru www.lbz.ru Москва Оглавление Предисловие 8 Об авторах 10 Об иллюстрациях 12 О записи алгоритмов 13 Глава 1. Основные понятия. Представление цвета в машинной графике 14

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

1.2. Представление цвета в машинной графике...... 17 Глава 2. Современные аппаратные средства растровой графики 42

2.1. Основные понятия.................... 42

2.2. Устройства ввода..................... 44

2.3. Устройства вывода.................... 48

2.4. Архитектура графической подсистемы ПК...... 56 Глава 3. Алгоритмы растеризации отрезков, окружностей и эллипсов 66

3.1. Введение в растеризацию кривых........... 66

3.2. Изображение отрезка с целочисленными координатами концов.................. 67

3.3. Изображение отрезка с нецелочисленными координатами концов.................. 73

3.4. Изображение окружностей............... 75

3.5. Изображение эллипсов.................. 82 6 Оглавление Глава 4. Параметрические кривые и их растеризация 84

4.1. Интерполяция сплайнами................ 84

4.2. Аппроксимация...................... 86

4.3. Заключение........................ 101 Глава 5. Отсечение отрезков и многоугольников 102

5.1. Введение.......................... 102

5.2. Отсечение отрезков................... 103

5.3. Отсечение многоугольников.............. 113 Глава

–  –  –

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

растровый и векторный1 .

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

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





Аналогичные концепции есть и в трехмерной графике, но это выходит за рамки предмета данной книги .

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

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

Растр (англ. raster) – отображение вида f : X Y 2R C, где X Z, Y Z, 2R обозначает множество всех подмножеств R2, C – множество значений атрибутов (как правило, цвет) .

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

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

• A(i, j) R2 — область пикселя,

• C(i, j) C — атрибут пикселя (как правило, цвет). Чаще всего мы будем пользоваться следующими двумя видами атрибутов:

– 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;

• Aij := (i, i + 1) (j, j + 1) – квадрат. Пример такой модели растра см. на рис. 1.2. На реальных графических устройствах физически пиксели могут быть прямоугольниками, что иногда порождает дополнительные трудности .

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

–  –  –

(0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,2) (1,2) (2,2) (3,2) (4,2)

–  –  –

В реальности, как правило, X и Y — ограниченные наборы неотрицательных целых чисел; такой растр называется прямоугольным .

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

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

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

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

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

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

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

1.2. Представление цвета в машинной графике Понятие цвета возникает при описании восприятия глазами человека электромагнитных волн в определенном диапазоне частот (длина волны от 400 нм (фиолетовый) до 700 нм (красный) (см .

рис. 1.3)). Таким образом, самым общим описанием светового потока может служить его спектральная функция I(). Свет назыОсновные понятия. Представление цвета в машинной графике вается монохроматическим (не путать с монохромными дисплеями, рассматриваемыми в следующей главе), если его спектр состоит из одного значения ; математически I () = c · ( )), где c

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

Колбочки бывают трех видов (их часто обозначают S, M и L2 ), и их кривые относительной чувствительности представлены на рис. 1.3 .

Пики на кривых чувствительности отвечают красному, зеленому и синему цветам. При этом следует заметить, что восприимчивость к синему цвету значительно ниже, чем к двум другим. Также важным свойством восприятия света человеком является его линейность: при освещении двумя источниками света (со спектральными функциями I1 (), I2 ()) человек воспринимает их как один со спектральной функцией, равной сумме I() = I1 () + I2 (). Этот факт называется законом Грассмана. Благодаря ему можно строить сравнительно простую теорию цветовосприятия .

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

Цветовая модель RGB Из рассмотренной выше модели человеческого зрения вытекает, что достаточно обоснованной является цветовая модель RGB (от англ. Red, Green, Blue – красный, желтый, зеленый), в которой спектральная функция представляется как сумма кривых чувствительности для каждого типа колбочек с неотрицательными весовыми по длине волны – от англ. Small, Middle, Large – малая, средняя и длинная

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

–  –  –

Рис. 1.3. Относительная чувствительность колбочек .

Относительная чувствительность 0.8 0.6 0.4 0.2

–  –  –

Рис. 1.4. Относительное восприятие интенсивности света палочками .

коэффициентами (обычно их нормируют от 0 до 1), которые так и обозначаются — R, G и B. Эта модель характеризуется свойством аддитивности (мы складываем цвета для получения новых). К примеру, спектральные функции:

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

–  –  –

• черного цвета: 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) .

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

Эта модель является в настоящее время самой распространенной. В то же время ей присущ важный недостаток: не все цвета, видимые человеком, представимы в этой модели. В конце 1920-х годов В.Д. Райтом [53] и Дж. Гилдом [33] были проведены эксперименты, в которых наблюдателю предлагалось каждому монохроматическому цвету3 фиксированной яркости в видимом диапазоне сопоставить цвет, составленный из смеси основных цветов R, G и B с Естественно, образцы брались с определенным шагом по спектру, равным 2 нм .

1.2. Представление цвета в машинной графике некоторыми весами, регулируемыми наблюдателем. Оказалось, что для некоторых цветов необходимо было добавить отдельно яркости испытуемого света и одного из базисных цветов (был выбран R), с тем чтобы получить одинаковое восприятие. Это соответствует отрицательному весу R-компоненты (см. рис. 1.6). Такой эффект связан с тем, что волны из видимого диапазона воздействуют сразу на все типы колбочек и не всегда возможно ограничиться положительными коэффициентами (более подробно см. [24]) для представления некоторых цветов из видимого спектра. К счастью, доля воспроизводимых цветов значительно больше, чем доля не представимых в этой модели цветов. Модель, с помощью которой можно представить все цвета из спектра, ограничиваясь неотрицательными коэффициентами, представлена в следующем подразделе .

–  –  –

Рис. 1.6. Функции представления цвета для RGB .

22 Основные понятия. Представление цвета в машинной графике Цветовая система CIE XYZ и диаграмма цветности CIE Международный стандарт представления цвета CIE XYZ был принят в 1931 году Международной комиссией по освещению (CIE `

– фр. Commission Internationale de l‘Eclairage), В нем определяются три базисные функции X (), Y (), Z (), зависящие от длины волны (см. рис. 1.7), линейные комбинации которых с неотрицательными коэффициентами (X, Y и Z) позволяют получить все видимые человеком цвета .

Z 1,5

–  –  –

где I() – спектральная функция распределения для представляемого цвета, а k – масштабный коэффициент, выбираемый исходя из

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

–  –  –

где Iбел () – спектральная функция распределения для выбранного эталона белого цвета. Функция Y () соответствует относительному восприятию интенсивности света палочками (рис. 1.4) .

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

Рассмотрим значения цветности (англ. chromacity values)

x, y, z, которые определяются из X,Y,Z следующим образом:

X Y Z x=, y=, z= (1.1) .

X +Y +Z X +Y +Z X +Y +Z Они вводятся для описания только цветовых свойств света, безотносительно его энергии, и зависят только от основной длины волны и насыщенности. Таким образом, если опять же поместить эти точки в трехмерное евклидово пространство, то они будут как раз лежать на плоскости X + Y + Z = 1 (она также показана на рис. 1.8). Проекция этой плоскости на Oxy называется диаграммой цветности CIE (см. рис. 1.9 и рис. III вклейки) .

Эта диаграмма весьма полезна и наглядна и широко используется. Цвета, расположенные на границе проекции, являются монохроматическими. При смешении базисных цветов можно получить все цвета, находящиеся в их выпуклой оболочке на диаграмме цветности. Этим как раз и объясняется, что с помощью трех базовых цветов R,G,B (да и любых других) мы не можем получить все видимые цвета .

Введем понятие точки белого (англ. white point). Это точка на диаграмме цветности, соответствующая измеренным координатам белого цвета. Она может варьироваться в зависимости от того, какой источник цвета принимается за белый. В исходной модели CIE XYZ весовые функции были специально подобраны так, чтобы дневному свету солнца соответствовала точка (x, y, z) = (1/3, 1/3, 1/3). Другие точки белого применяются для компенсации условий съемки, 24 Основные понятия. Представление цвета в машинной графике

–  –  –

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

Важной характеристикой как цветовых моделей, так и конкретных устройств, отображающих цветную информацию, является Цветовая гамма (англ. Color gamut) — подмножество цветов, воспроизводимое в условиях конкретной цветовой модели или для конкретного устройства цветового отображения .

Корректно отображать цветовую гамму как некоторое подмноПредставление цвета в машинной графике

–  –  –

Рис. 1.9. Диаграмма цветности CIE c приблизительными цветовыми гаммами для разных классов устройств .

жество в конусе видимых цветов (см. рис. 1.8). Можно также ограничиться проекцией на диаграмму цветности, но при этом не учитывается диапазон яркости. На рис. 1.9 и рис. III вклейки представлены некоторые типичные цветовые гаммы, которые позволяют судить о полноте охвата отображаемых цветов разными устройствами .

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

–  –  –

Все представимые в модели RGB цвета образуют параллелепипед в CIE XYZ (см. рис. 1.10), пересечение которого с плоскостью X + Y + Z = 1, спроецированное на диаграмму цветности и дает цветовую гамму данной модели .

Таким образом, в зависимости от координат (x, y, Y ) для базисных цветов в конкретном устройстве (фотоаппарате, мониторе, проекторе и т.п.) одним и тем же значениям (R, G, B) соответствуют разные цвета .

Цветовые пространства, в которых каждому набору цветовых компонент соответствует физически единственный цвет, называются [...]

1.2. Представление цвета в машинной графике else if( Hue 240 ) return N1 + (N2 - N1)*(240 - Hue) / 60;

else return N1;

} Цветовые модели Y** Существует несколько тесно связанных цветовых моделей, которые объединяет то, что в них используется явное разделение информации о яркости и цвете. Компонента Y соответствует одноименной компоненте в модели CIE XYZ и отвечает за яркость. Такие модели находят широкое применение в телевизионных стандартах, так как исторически необходима была совместимость с черно-белыми телевизорами, которые принимали только сигнал, соответствующий Y .

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

Цветовые модели YUV, YPbPr и YCbCr Расcмотрим цветовую модель YUV.

U и V отвечают за цветовую информацию и определяются через преобразование из RGB:

–  –  –

Модель YUV применяется в телевизионной системе PAL .

Цветовые модели YCbCr и YPbPr являются вариациями YUV с другими весами для U и V (им соответствуют Cb/Pb и Cr/Pr) .

40 Основные понятия. Представление цвета в машинной графике Рис. 1.15. RGB-куб в пространстве YUV, диаграмма UV при Y = 0,5 .

YPbPr применяется для описания аналоговых сигналов (преимущественно в телевидении), а YCbCr – для цифровых. Для их определения используются два коэффициента: Kb и Kr. Тогда преобразование из RGB в YPbPr описывается так:

–  –  –

Выбор Kb и Kr зависит от того, какая RGB-модель используется (это в свою очередь зависит от воспроизводящего оборудования) .

Обычно берется, как и выше, Kb = 0, 114; Kr = 0, 299. В последнее время также используют Kb = 0, 0722; Kr = 0, 2126, что лучше отражает характеристики современных устройств отображения .

Из приведенных выше формул следует что при R, G, B [0, 1] имеем следующие диапазоны Y [0; 1]; P b, P r [0, 5; 0, 5] .

Для цифрового представления эти формулы видоизменяют для получения только положительных дискретных коэффициентов в диапазонах Y [minY, maxY ], Cb, Cr [minC, maxC],

minY, maxY, minC, maxC N {0}:

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

–  –  –

В телевидении обычно берут minY = 16, maxY = 235, minC = 16, maxC = 240. В стандарте сжатия изображений

JPEG (см. раздел 14.4) используется полный 8-битный диапазон:

minY = 0, maxY = 255, minC = 0, maxC = 255 .

Цветовая модель YIQ Цветовая модель YIQ применялась в телевизионной системе NTSC (I – от англ. in-phase, Q – от англ. quadrature; происходят от особенностей систем декодирования). Она тесно связана с моделью YUV, так как переход от YUV к YIQ является поворотом в плоскости U V = IQ на 33 .

–  –  –

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

[...]





Похожие работы:

«Доклад по теме: Администрирование локальных сетей. Жгулев С.В. Королев 2003 Администрирование локальных сетей. 2 Оглавление . Администрирование локальных сетей Удаленное управление Управление питанием Установка Настройка Управление Полный контроль Обзор Remote Ad...»

«Рынок марганцевых сплавов – 2009 – сентябрь ООО Инфометгео / Александр Терешин Информационный обзор РЫНОК МАРГАНЦЕВЫХ СПЛАВОВ – 3кв. 2009 Москва 2009 © ООО Инфометгео / Александр Терешин / http://www.infogeo.ru/metalls, post@infogeo.ru 1 Рынок марганцевых сплавов – 2009 – се...»

«ДК 004.4 К 32.973.26-018.2 Rod Stephens Essencial Algorithms: F Practical Approach to Computer Algorithms © 2013 by John Wiley & Sons, Inc., Indianapolis, Indiana. All rights reserved. Authoris...»

«-1Futaba 14SG Программирование для самолетов Автор: Malcolm Holt Перевод: Владислав Ярополов -2СОДЕРЖАНИЕ ВВЕДЕНИЕ Использование сенсорного датчика и кнопок Структура меню Недостающие пункты меню Органы управления и переключатели Программирование на основе функций Изгиб крыла (Camber) ТАЙМЕРЫ Системный...»

«Правительство Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Санкт-Петербургский государственный университет" Кафедра Системного Программирования Атам...»

«ШВЕЙЦАРСКОЕ АГЕНТСТВО ПО МЕЖДУНАРОДНОМУ РАЗВИТИЮ И СОТРУДНИЧЕСТВУ (SDC) МЕЖГОСУДАРСТВЕННАЯ КООРДИНАЦИОННАЯ ВОДОХОЗЯЙСТВЕННАЯ КОМИССИЯ ЦЕНТРАЛЬНОЙ АЗИИ (МКВК) Международный институт Научно-инф...»

«Список слушателей ЦДО, успешно сдавших вступительные экзамены в 2015 году и представленных к зачислению в РАУ Направление "Туризм" Госзаказ 1. Амирханян Анжела Самвеловна 54303.02011 48,32 балла 2. Аристакесян Наре Жирайровна 543.03.02013 46,98 балла 3. Геворгян Софья К...»

«Satbayev University Список специальностей ИДО (контингент обучающихся на 1 декабря 2017 года) Ваша специальность Смежные специальности SU 5В071900 "Радиотехника, электроника и Авиационная и ракетнокосмичес...»







 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.