Графические данные и цветовые модели

1. Графические данные и цветовые модели. Векторная и растровая графика В настоящее время доля графической информации, хранимой на локальных носителях и передаваемой по сетям связи, достаточно велика, соответственно весьма актуален вопрос о способах хранения и обработки этой информации. Графические данные исторически делятся на 2 класса: • Векторная графика • Растровая графика В векторной графике используется математическое описание точек, отрезков, геометрических фигур для построения графических объектов. Векторные данные представляют собой координаты точек, типы графических объектов, атрибуты (цвет, толщина, тип) линий. Например, чтобы задать на экране прямоугольник достаточно написать: Прямоугольник(x1,y1,x2,y2,1,red) Где x1,y1,x2,y2 – координаты 2-х углов прямоугольника, 1 – толщина линии, red – цвет линии. Другой пример: Векторные команды: Цвет черный Линия 3, 2, 3, 8 Линия 4, 4, 6, 2 Линия 4, 5, 7, 8 Позволят задать следующее изображение: Основное преимущество векторной графики состоит в том, что при изменении масштаба изображения оно не теряет своего качества. Отсюда следует и еще одно преимущество - при изменении размеров изображения не изменяется размер файла. Кроме того векторный файл имеет как правило существенно меньший объем чем растровый. Но далеко не каждое изображение можно разложить на простейшие графические объекты. Поэтому для представления, например, фотографий используется растровая графика, которой и будет посвящен в дальнейшем наш курс. Растровая графика представляет собой прямоугольную матрицу (bitmap), разделенную на маленькие квадратики — пикселы (pixel — picture element). Значение каждого пиксела – его цвет, а координаты, форма и размеры пикселей задаются при определении растра. Процедура разбиения изображения на пиксели называется растеризацией, или оцифровкой, изображения. Пример изображения, разбитого на пикселы: При масштабировании растрового изображения (изменении размеров изображения) качество растрового изображения значительно ухудшается. При уменьшении безвозвратно теряется часть информации (уменьшается количество точек). При увеличении проявляется «пикселизованность» - контуры становятся ступенчатыми (добавляются лишние точки с цветом соседней точки) В технике и компьютерной графике чаще всего используют прямоугольный растр, в котором пиксели составляют прямоугольную матрицу. Размер сетки растра, задаваемый в виде N1*N2, где N1 - число пикселей по горизонтали, N2 – число пикселей по вертикали называется разрешающей способностью (или графическим разрешением) экрана. Количество бит, используемых для кодирования цвета одной точки, называется глубиной цвета (битовой глубиной, цветовым разрешением). От глубины цвета зависит количество отображаемых цветов, которое может быть вычислено по формуле: M=2k, где M – количество отображаемых цветов, k – глубина цвета. Стандартные значения графического разрешения экрана : 640*480, 800*600, 1024*768, 1280*1024, 1600*1200 Наиболее распространенными значениями глубины цвета являются 4, 8, 16 или 24 бита на точку. Глубина цвета, к (бит) Количество отображаемых цветов, N 1 (монохромная) 21 = 2 4 24 = 16 8 28 = 256 16 (High Color) 216 = 65 536 24 (True Color) 224 = 16 777 216 Битовая карта монохромного изображения будет выглядеть так (0 трактуется как белый пиксель, 1 как черный): 00000000 00100100 00101000 00110000 00110000 00101000 00100100 00100010 Размер памяти, требуемой для хранения растра, зависит от разрешения и цветовой глубины. При выводе на монитор растр храниться в видеопамяти. Видеопамять – оперативная память, хранящая видеоинформацию во время ее воспроизведения в изображение на экране Вопрос: Сколько места в памяти будет занимать тот же рисунок размером 8х8 пикселей, если сохранить его в формате как А) 256-цветный рисунок; В) в режиме HighColor; С) в режиме True Color D) Монохромный Решение. Рисунок разбит на 8*8=64 пикселя. А) 256=28, т.е. код каждого пикселя передается 8 битами. I=64*1=64 байта В) HighColor: 1 пиксель передается 16 битами (2 байта). I=64*2=128 байтов С) TrueColor: цвет пикселя передается 24 битами (3 байта). I=64*3=192 байта D) Монохромный цвет пикселя передается 1 битом (1/8 байта). I=64/8=8 байт Цветовые модели В компьютерной технике чаще всего используются следующие цветовые модели: RGB (Red-Green-Blue, красный – зеленый – синий) CMYK (Cyan-Magenta-Yellow, голубой – пурпурный - желтый – черный) RGB RGB - метод синтеза на экране цветного изображения с использованием красного (R), зеленого (G) и синего (B) цветов. На градации каждого цвета в RGB отводится 8 бит, поэтому всего для представления RGB-цвета в полном диапазоне нужно 24 бита, которые представляют 16,777,216 цветов. Глаз человека воспринимает длины волн в диапазоне от 400 до 700 нм. Волны другой длины не вызывают у человека зрительных ощущений. Длину волны от 430 нм до 470 нм человеческий глаз воспринимает как синий цвет, в диапазоне от 500 до 540 нм, как зеленый цвет и в диапазоне от 620 до 700 нм, как красный цвет. Цветовое зрение человека обусловлено наличием трёх видов световосприимчивых рецепторов на сетчатке глаза(колбочек), с максимумами чувствительности соответствующими красному, зеленому и синему цветам . RGB цвета являются базовыми, все остальные тона воспринимаются как их смешение в определённой пропорции. Например, чтобы получить желтый цвет, совсем необязательно воспроизводить его истинную длину волны, достаточно создать такой спектр излучения, который возбуждает рецепторы глаза сходным образом. Это явление называется метамерией. Цветовая модель RGB используется в таких светящихся устройствах, как телевизионные кинескопы и компьютерные мониторы. Для создания всех цветов, встречающихся в природе, они смешивают три первичных цвета RGB. Смесь 100% всех трех цветов дает белый, а смесь 0% всех трех цветов дает черный, синего (B) и красного (R), мы получаем пурпурный (M magenta), при смешении зеленого (G) и красного (R) — желтый (Y yellow), при смешении зеленого (G) и синего (B) — циановый (цвет морской волны) (С cyan). При смешении всех трёх цветовых компонентов мы получаем белый цвет (W). Значения координат R, G и B можно считать принадлежащими отрезку [0,1], что представляет пространство RGB в виде куба 1×1×1. • Любая точка куба (r, g, b) определяет какой-то цвет; • Линия (0,0,0) – (1,1,1) описывает все градации серого от черного до белого; • На гранях куба расположены самые насыщенные цвета; • Чем ближе точка к главной диагонали, тем менее насыщен соответствующий цвет; • Если все три координаты точки (r, g, b) ненулевые, то цвет ненасыщенный, причем, наименьшее значение определяет долю серого оттенка, а разность значений – тон и долю насыщенного цветового оттенка. В компьютерах для представления каждой из координат традиционно используется один октет, значения которого обозначаются для удобства целыми числами от 0 до 255 включительно. Таким образом, при R=255; G=255; B=0 получаем желтый цвет. CMYK Цветовая модель, используемая в принтерах и в других периферийных устройствах. Комбинации чернил четырех цветов: голубого (C), пурпурного (M), желтого (Y) и черного (К) позволяют воспроизводить все цвета. Теоретически все цвета можно воспроизводить с помощью комбинаций голубого, пурпурного и желтого. Однако, на практике сочетание этих трех цветов не позволяет воспроизвести чистый черный цвет. Поэтому к ним отдельно добавляются черные чернила. Палитра В растровых файлах используется обычно один из двух методов хранения данных о пикселях. В полноцветных изображениях пиксель может принимать любое из более чем 16 миллионов значений, поэтому и цвет пикселя хранится обычно как 24-разрядное значение - по 8 битов на красную, зеленую и синюю компоненты цвета. Если изображение содержит 1 миллион пикселей, то размер файла будет равен 3 миллионам байтов плюс длина неграфических данных. Если же изображение ограничено 256 или менее цветами, то цветовая информация обычно кодируется с использованием палитры. Вместо того чтобы хранить значение цвета пикселя, информация о пикселе указывает на строку в палитре или таблице перекодировки, а она, в свою очередь, содержит цвет. С уменьшением количества битов, требуемых для представления цвета пикселя, уменьшается размер файла.       В качестве примера возьмем изображение из миллиона пикселей, содержащее 256 различных цветов. Кодирование цвета каждого пикселя 24-битным значением приводит к расточительной избыточности, потому что некоторые (а возможно и все) из 256-ти цветов повторяются неоднократно. Для хранения используемых цветов лучше выделить в файле 768 байтов под цветовую палитру: 256 полей по 24 бита, каждое поле содержит один из цветов, встречающихся в изображении. Тогда под значение цвета пикселя можно отвести 8 битов, то есть целое число в диапазоне от 0 до 255, указывающее номер цвета в палитре. Теперь для графической части файла достаточно 1.000.768 байтов, против прежних 3.000.000 байтов, которые требуются для хранения этого изображения без использования палитры. И даже с учетом дополнительных байтов из неграфической части файла, мы все-таки получаем уменьшение размера файла почти на две трети. В случае 16-цветного изображения для хранения под номер цвета отводится 4 бита, то есть в одном байте будет храниться информация о 2-х пикселях. Пример стандартной 16-цветной палитры № цвета Цвет R G B № цвета Цвет R G B Черный 8 Серый 85 85 85 1 Синий 170 9 Светло-синий 85 85 255 2 Зеленый 170 10 Светло-зеленый 85 255 255 3 Голубой 170 170 11 Светло-голубой 85 255 255 4 Красный 170 12 Светло-красный 255 85 85 5 Фиолетовый 170 170 13 Светло-фиолетовый 255 85 255 6 Коричневый 170 85 14 Желтый 255 255 85 7 Светло-серый 170 170 170 15 Ярко-белый 255 255 255 В данном случае, если цвет равен, например 14, то по номеру цвета с помощью палитры определяют R=255, G=255, B=65 и в результате получаем желтый цвет. Так как в каждом изображении используется свой набор цветов, палитра подбирается для конкретного изображения и помещается в графический файл. На практике палитра используется если количество цветов 4, 16 или 256. Вопросы для самоконтроля. • Достоинства и недостатки векторной графики • Достоинства и недостатки растровой графики • Какой объем памяти требуется доля хранения без сжатия TrueColor изображения 600х800 пикселей • Для чего и в каких случаях используется цветовая палитра • Почему для цветных принтеров не подходит цветовая модель RGB 2. Описание библиотеки для работы с графикой Wingraph.h Для облегчения работы с графикой в курсе ПГИ была разработана библиотека Wingraph.h для срекды программирования Borland C++ Builder. Данная библиотека позволяет легко выводить графические объекты с требуемым разрешением и глубиной цвета. Создание проекта и подключение библиотеки. Создание нового проекта после запуска С++ Builder 6: 1. File -> New -> Other -> Console Wizard 2. Установить переключатель Source Type (тип исходного кода) в положение «С++» 3. Отключить все остальные опции (рисунок 5.1) 4. Нажать ОК 5. Удалить нижеуказанные строки #include WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) { return 0; } 6. Вставить нижеуказанные строки #define MAXCOLORTC // MAXCOLOR16 - 16 цветов // MAXCOLOR256 - 256 цветов // MAXCOLORTC - 16м цветов True Color #include "wingraph.h" void main() { // ваш код } В модуле wingraph.h уже есть функция WinMain, которая используется для создания окна приложения. Функции рисования Данная библиотека позволяет выводить на экран следующие элементы графики: точки, прямые и ломаные линии, прямоугольники, многоугольники, окружности, эллипсы, дуги, сектора, а так же текстовые надписи. На рисунке показан пример окна с перечисленными выше элементами: Координаты точек, определяющих местоположение и размер графических элементов, задаются положительными целыми числами. Начало координат, т.е. точка (0,0), соответствует верхнему левому углу рабочей области окна. Ось абсцисс направлена вправо, ось ординат – вниз. Есть возможность рисовать за пределами окна. При расширении окна, например с помощью мыши, будут видны нарисованные там графические элементы. Перечислим кратко функции рисования: • void putpixel(const int& x,const int& y, const int& z, int color) Данная функция рисует на экране пиксель заданного цвета (параметр z) в точке с координатами (x,y). Если цвет не указан, то используется цвет, установленный ранее с помощью функции setcolor(int color). Для задания цвета в режиме True Color можно использовать макрос RGB(r,g,b). • void line(int x1, int y1, int x2, int y2, int color) Рисует прямую линию, соединяющую точки (x1,y1) и (x2,y2). • void linerel(int dx, int dy, int color) Рисует линию от текущей позиции до точки, находящейся на расстоянии (dx, dy) от нее. Текущая позиция смещается на (dx,dy). • void lineto(int x, int y, int color) Рисует линию от текущей позиции до точки с координатами (x,y). Текущая позиция перемещается в (x,y). • void drawpoly(int numpoints, int* polypoints, int color) Рисует многоугольник, имеющий numpoints точек, используя текущие тип линии и цвет. polypoints указывает на последовательность из (numpoints x 2) целых чисел. Каждая пара чисел является координатами вершины многоугольника. • void circle(int x, int y, int radius, int color) Рисует окружность с центром в (x,y) и радиусом radus. • void arc(int x, int y, int stangle, int endangle, int radius, int color) Рисует дугу окружности с центром в точке с координатами (x,y) и радиусом radius текущим цветом вывода. Дуга рисуется от угла stangle до угла endangle. • void ellipse(int x, int y, int xradius, int yradius, int color) Рисует эллипс с центром в точке с координатами (x,y), горизонтальной и вертикальной осями радиусом xradius и yradius соответственно, текущим цветом. • void bar(int left, int top, int right, int bottom) Рисует двухмерный заполненный прямоугольник. Прямоугольник заполняется, с использованием текущего цвета и шаблона заполнения. Left, top – координаты левого верхнего угла прямоугольника, а right и bottom – правого нижнего. • void bar3d(int left, int top, int right, int bottom, int depth, int topflag, int color) Аналогично bar рисует трехмерный прямоугольный столбец, затем закрашивает его, используя текущий шаблон и цвет заполнения. Глубина столбца в пикселах задается параметром depth. • void rectangle(int left, int top, int right, int bottom, int color) Рисует прямоугольник линией текущего вида, толщины и цвета. left, top – координаты левого верхнего угла прямоугольника; right, bottom – координаты правого нижнего угла прямоугольника. • void fillpoly(int numpoints, int* polypoints, int color) Рисует закрашенный многоугольник, имеющий numpoints точек, используя текущие тип линии и цвет. polypoints указывает на последовательность из (numpoints x 2) целых чисел. Каждая пара чисел является координатами вершины многоугольника. • void fillellipse(int x, int y, int xradius, int yradius, int color) Рисует эллипс с центром в точке (x,y) и горизонтальной и вертикальной осями xradius и yradius соответственно, и закрашивает его текущими цветом закраски, используя текущий шаблон. • void pieslice(int x, int y, int stangle, int endangle, int radius, int color) Рисует сектор круга с центром в точке с координатами (x,y) и радиусом radius, текущим цветом рисунка. Дуга рисуется от угла stangle до угла endangle. • void sector(int x, int y, int stangle, int endangle, int xradius, int yradius, int color) Рисует эллиптический сектор с центром в точке с координатами (x,y) и горизонтальными и вертикальными радиусами xradius и yradius соответственно. Дуга рисуется от угла stangle до угла endangle. • void outtext(char* textstring, int color) Отображает строку текста в окне, используя текущие установленные параметры выравнивания текста, а также текущие шрифт, направление и размер. Текст выводится в текущую позицию. • void outtextxy(int x, int y, char* textstring, int color) Отображает строку текста в окне экрана в заданной позиции (x,y), используя текущие установленные параметры выравнивания текста, а также текущие шрифт, направление и размер. Установка цвета Библиотека поддерживает 3 различных режима работы с цветом: 1. MAXCOLOR16 – поддержка 16 цветов; 2. MAXCOLOR256 – поддержка 256 цветов; 3. MAXCOLORTC – режим True Color, 16 миллионов цветов. Режим работы устанавливается с помощью директивы #define. Для режима MAXCOLORTC цвет задается числом типа int, в котором три младших байта кодируют интенсивность трех основных цветов – красного (r), зеленого (g) и синего (b). Для сведения всех трех составляющих цвета в одно целое число используется макрос RGB(r,g,b). Так черному цвету соответствует комбинация RGB(0,0,0), белому – RGB(255,255,255). Промежуточные значения соответствуют всем остальным цветам. Текущее значение цвета, которым рисуются все графические элементы, устанавливается с помощью функции setcolor (int color). По умолчанию установлен черный цвет рисования. В режимах MAXCOLOR16 и MAXCOLOR256 цвет устанавливается заданием соответствующего номера, где 0 – черный цвет, а белый – 15 или 255 соответственно. Так же в случае использования режима MAXCOLOR16 аргумент color может быть именем, указанном в перечислении COLORS. Например, выражения, представленные ниже, дают совершенно одинаковый эффект: 1. setcolor(2); 2. setcolor(GREEN); При рисовании объектов с помощью функции putpixel более быстрым вариантом является непосредственное указание цвета с помощью дополнительного параметра. Следующие фрагменты кода эквиваленты по своему действию, но второй вариант быстрее и удобнее в использовании: 1. setcolor(RGB(20,30,40)); putpixel(10,10); 2. putpixel(10,10, RGB(20,30,40)); Определение и изменение текущих параметров Помимо изменения цвета фигуры существует еще ряд функций, влияющих на внешний вид элементов и их расположение: • void setbgcolor(int color) – устанавливает текущий цвет фона фигуры, используя палитру; • int getcolor() – возвращает текущий цвет рисования; • int getbgcolor() – возвращает текущий цвет фона; • int getx() – возвращает текущую координату x; • int gety() – возвращает текущую координату y; • int getmaxx() – возвращает максимальное (относительно окна) значение координаты х для текущего режима; • int getmaxy() – возвращает максимальное (относительно окна) значение координаты y для текущего режима; • void clearpalette() – восстанавливает палитру в режиме MAXCOLOR16. • void setpalette(int colornum, int color) – устанавливает элементу colornum новый цвет . • void setfillstyle(const int& pattern, const int& color) – устанавливает текущие цвет и шаблон заполнения для закрашиваемых фигур; • void getfillsettings(struct fillsettingstype* fillinfo) – получает информацию о текущем шаблоне и цвете заполнения. • void setlinestyle(int num) – устанавливает стиль рисования линий для всех геометрических фигур: линий, окружностей, прямоугольников и т.д. Типы шаблонов линий: сплошная, штриховая, пунктирная, штрих пунктирная линия, невидимая. • void settextstyle(const int& font, const int& direction, const int& charsize) – Устанавливает шрифт текста, направление отображения текста и размер символов. Вызов settextstyle действует для любых текстов, выводимых с помощью outtext и outtextxy. • void moveto(const int& x, const int& y) – перемещает текущую позицию в точку с координатами (x,y). • void moverel(const int& dx, const int& dy) – перемещает текущую позицию на заданное расстояние. • void resize (const int& nX, const int& nY) – изменяет размер окна приложения. Пример программы, выводящей разноцветные диагональные линии. #define MAXCOLOR256 // MAXCOLOR16 // MAXCOLOR256 // MAXCOLORTC #include "wingraph.h" void main() { resize(640,480); int n = getmaxx(); for(int i=0; i<256; i++) { setpalette(i,RGB(random(256),random(256),random(256))); } for(int i=0;i<640;i+=10) for(int j=0;j<480;j+=10) line(i,j,i+10,j+10,random(256)); } Вопросы для самоконтроля. • Какие цветовые разрешения поддерживает библиотека Wingraph.h • Как определить текущие размеры графического окна • Какие функции библиотеки Wingraph.h потребуются для вывода на экран графического рапстрового файла 3. Методы сжатия используемые для графических форматов Так как графическая и видео информация, как правило высоко избыточна, большинство графических и видео форматов используют сжатие информации для уменьшения объема файлов с данной информацией. Сжатие позволяют уменьшить избыточность, присущую графическим данным, и тем самым уменьшить объем памяти, необходимый для их хранения. Мы будет разделять методы сжатия на: • Симметричные и ассиметричные. В симметричных затраты на сжатие и восстановление информации примерно одинаковы, в ассиметричных что одно существенно сложнее другого. • Адаптивные и неадаптивные. Адаптивное сжатие позволяет кодеру и декодеру настраиваться на статистику источника. • С потерями и без потерь. Сжатие без потерь – в том случае, если после декодирования информации получаем точную копию оригинала. Для сжатия графики используются следующие методы: • RLE – кодирование длин серий. Повторяющиеся значения пикселей заменяются счетчиком и значением пикселей группы. • Код Хаффмена • Арифметический код • LZ и LZW коды • JPEG сжатие • Фрактальное сжатие – реальное изображение кодируется математическими данными, описывающими фрактальные (похожие) свойства изображения. В 40х годах XX века К. Шеннон разработал математическую теорию, которая имеет дело с наиболее фундаментальными аспектами теории связи. Основной задачей в теории информации является кодирование сообщений. С практической точки зрения удобно разделить кодирование для источника и кодирование для канала Разбиение кодера и декодера на две части позволяет строить кодер и декодер для источника независимо от кодера и декодера для канала. Задачей кодера для источника является представление выхода источника с помощью последовательности двоичных символов, причем на этом шаге необходимо уменьшить избыточность источника до минимума, то есть закодировать последовательность букв источника минимально возможным количеством двоичных символов. Задача кодирования для канала состоит в том, чтобы надежно воспроизвести двоичную последовательность данных на выходе декодера для канала; на этом шаге – для защиты от помех в канале – наоборот, избыточность вносится в сообщение источника. В данной работе в дальнейшем будет рассматриваться только кодирование для источника. Первым эффективно сжимающим кодом для источника был код, созданный С. Морзе в 1837 году. Принцип его построения основан на том, что часто встречающимся буквам алфавита источника были поставлены в соответствие короткие кодовые слова, а редким — более длинные. За счет этого средняя длина кодового слова получается короче, чем при кодировании равномерным кодом. Затем, с развитием теории информации, появились код Хаффмена, для которого доказана его оптимальность, близкий к оптимальному код Шеннона и другие. Они, как и код Морзе, строятся для заранее известной статистики источника, поэтому получили название статических. Но так как эта статистика обычно заранее точно не известна, практическое применение этих кодов было ограничено. С практической точки зрения наиболее удобными универсальными кодами являются последовательные методы, не требующие предварительного просмотра сообщения источника, и позволяющие кодировать его “за один проход”. Дискретные источники информации Под дискретным понимается источник, который в каждую единицу времени порождает один символ xi из дискретного множества А={a1, a2, ..., ak}, называемого алфавитом источника, где k — размер алфавита. Источник, с точки зрения теории информации, считается заданным полностью, если известен не только алфавит источника, но и есть его модель, позволяющая вычислить вероятность любой последовательности символов в любой момент времени. Таким образом, источник задан, если определен его алфавит А = {a1, a2, ..., ak}, и для последовательности символов xi, xi+1, ..., xi+L, порождаемой источником, известны вероятности слов p(xi, xi+1, ..., xi+L) при любых i и L, определя­ющих позицию и длину последовательности символов источника. То есть, с точки зрения теории информации, отождествляются источники различной физической природы, описываемые одним и тем же распределением вероятностей. Простейший класс моделей источников составляют дискретные источники без памяти, или бернуллиевские. В этих источниках выходом является последовательность символов, каждый из которых выбирается из алфавита А={a1, a2, ..., ak} статистически независимо и случайно, в частности, знание предыдущих символов источника не влияет на вероятность последующих. При этом выбор производится в соответствии с заданным распределением вероятностей p(a1), p(a2), ..., p(ak). В случае Бернуллиевского источника для любой последовательности символов x1, x2, ..., xn из алфавита А выполняется равенство р(x1, x2 , ..., xn) = p(x1)  p(x2)  ...  p(xn) В том случае, если вероятность появления очередного символа источника xi зависит от одного предыдущего символа xi-1, источник называется марковским, или марковским 1го порядка. Для марковских источников: p(xi/xi-1, xi-2 , ..., x1) = p(xi/xi-1) Таким образом, в сообщениях марковского источника всю информацию о вероятности текущего символа дает один предыдущий символ, а остальные не влияют на его появление. Определение марковских источников можно распространить и на более общий случай, когда вероятность очередного символа источника определяется не одним, а s предыдущими символами. Такой источник называется марковским порядка, или связности s. В случае марковского источника связности s выполняется следующее равенство: p(xi/xi-1, xi-2 , ... , x1) = p(xi/xi-1, xi-2, ... , xi-s) В дальнейшем мы будем рассматривать эргодические стационарные источники. К эргодическим относятся источники, не имеющие устойчивых типов поведения (характеристики по многим реализациям совпадают с характеристиками по одной, достаточно длинной, реализации источника). Источник называется стационар­ным, если его распределение вероятностей не зависит от сдвига во времени. То есть, вероятность произвольной последовательности (x1, x2, ... xi) в момент времени t равна вероятности этой же последовательности через интервал времени j. pt(x1, x2, ... , xi) = pt+j(x1, x2, ... , xi) Условная информация и энтропия Предположим, что дискретный источник без памяти U имеет алфавит А из k букв a1, a2, ... , ak c вероятностями p(a1), p(a2), ..., , p(ak), p(a1) + p(a2) + ... + p(ak) = 1. Обозначим через p(ai/aj) вероятность того, что на выходе источника появится символ ai при условии что предыдущим символом был aj. p(ai/aj) = p(ai, aj)/p(aj) где p(ai, aj) — вероятность последовательного появления пары символов ai, aj. Таким образом, p(ai/aj) — условная вероятность символа ai. Для бернуллиевских источников p(ai/aj)= p(ai), так как появление aj ничего не говорит о вероятности появления ai. Определим взаимную информацию как информацию о символе ai, содержащуюся в появлении aj. Она равна: В тех случаях, когда взаимная информация между символами источника велика (источники с высокой корреляцией символов), можно достаточно точно предсказывать вероятность очередного символа по предыдущим. Собственную информацию, содержащуюся в символе источника aj, можно определить следующим образом: Она может быть интерпретирована как априорная неопределенность символа ai, либо как информация, требуемая для разрешения этой неопределенности. Основание логарифма определяет шкалу, в которой измеряется информация. Наиболее часто используется основание 2, в этом случае информация измеряется в битах. Основной характеристикой источника является его энтропия, характеризующая неопределенность символов источника. Безуслов­ная энтропия определяется как среднее значение собственной информации источника и задается равенством: Если перейти от символов источника к блокам символов длины L, то можно определить энтропию Lго порядка. Пусть X = {x1, x2, ... ,xL} — последовательность из L символов дискретного источника с алфавитом A. Тогда определим энтропию на блок символов источника как: где kL — количество всех последовательностей длины L в алфавите А. При L получаем предельную энтропию H. Энтропия играет очень важную роль в теории информации, определяя минимально возможную среднюю длину кодового слова. Так, для бернуллиевских источников средняя длина кодового слова не может быть меньше безусловной энтропии, для марковских источников связности n — меньше условной энтропии nго порядка, и для любого источника — меньше H. Кодирование дискретных источников информации Обозначим через x1, x2, ...,xL последовательность символов дискретного источника. Каждый символ выбирается из алфавита А={a1, a2, ... ,ak}, где k — размер алфавита. Задача кодирования источника заключается в отображении множества букв из алфавита А в множество символов из кодового алфавита размером D. При передаче и хранении информации в компьютерных системах используется двоичный кодовый алфавит, состоящий из 1 и 0, что обусловлено особенностями обработки и хранения данных в ЭВМ. В связи с этим, в дальнейшем мы будем рассматривать, только случай когда D=2. Коды разделяются на равномерные, или с фиксированной длиной кодового слова, и неравномерные, или с переменной длиной кодового слова. Под длиной кодового слова понимается количество символов кодового алфавита в нем. Для равномерных кодов все кодовые слова имеют одинаковую длину N. В этом случае для однозначного декодирования при отображении последовательности букв источника в кодовую последовательность минимально возможная длина кодового слова определяется как: N = log2k где символом x обозначается наибольшее целое число не меньшее x. Например, для кодирования латинского алфавита, состоящего из 26 букв, требуется по крайней мере N = log2 26 = 5 двоичных символов. Для неравномерного кода основной характеристикой является среднее количество символов, затрачиваемое на кодирование одной буквы источника (для равномерных кодов это количество постоянно для любой буквы источника). Обозначим через ni число символов в кодовом слове, соответствующем букве источника ai. Тогда среднее число символов на одну букву источника определится как: Для уменьшения средней длины кодового слова короткие кодовые слова должны приписываться высоковероятным буквам источника, а более длинные — низковероятным. Из всех кодов нас будут интересовать только однозначно декодируемые, то есть такие, для которых последовательности кодовых символов, соответствующие различным последователь­нос­тям букв источника, различны. К однозначно декодируемым относятся префиксные коды, в которых ни одно кодовое слово не является началом никакого другого. Удобное представление кодовых слов, удовлетворяющих свойству префикса, можно получить, используя кодовые деревья. Построим кодовое дерево для следующего случая: даны символы источника a1, a2, ... ,a6 и соответствующие вероятности: p(a1)=1/2, p(a2) = p(a3) = p(a4) = 1/8, p(a5) =p (a6) = 1/16. Более вероятным символам источника будем ставить в соответствие более короткие кодовые слова: y(a1) = 0, y(a2) = 100, y(a3) = 101, y(a4) = 110, y(a5) = 1110, y(a6) = 1111. Каждому из ребер, выходящему из узла кодового дерева, присваивается один символ двоичного кодового алфавита. Всем узлам дерева присваивается двоичное слово, описывающее путь к этому узлу от корня. Узлы, из которых не выходит ребер кодового дерева, называются концевыми узлами или “листьями”. Именно им и ставятся в соответствие кодовые слова в префиксных кодах. Для любого однозначно декодируемого кода выполняется неравенство Крафта: Причем, если это неравенство выполняется, то обязательно существует код, обладающий свойством префикса, с размером кодового алфавита D, длинами кодовых слов ni. Если это неравенство не выполняется, то однозначно декодируемого кода не существует. Связь между средней длиной кодового слова N любого однозначно декодируемого побуквенного кода и энтропией источника H определяется следующим неравенством: H  N И в то же время существует однозначно декодируемый код со средней длиной: N < H+1 При использовании блоковых кодов, когда кодируются не отдельные символы источника, а их последовательности длины L, можно получить код, средняя длина которого будет удовлетворять условию: HL  N = значению, хранящемуся в 6 младших битах X <данные> = находятся в следующем байте за X. ИНАЧЕ <повторитель> = 1 <данные> = X Поскольку для насыщения данного алгоритма требуется в среднем 25% неповторяющихся данных и, по меньшей мере, наличие смещения между повторяющимися данными, то размер получаемого файла, как правило, оказывается приемлемым. Формат заголовка PCX typedef struct TPCXHeaderStruct { unsigned char ID; //Постоянный флаг 10 = ZSoft .PCX unsigned char Version; // Информация о версии unsigned char Coding; //1 = PCX кодирование RLE unsigned char BitPerPixel; // Число бит на пиксел unsigned int XMin; // Размеры изображения unsigned int YMin; unsigned int XMax; unsigned int YMax; unsigned int HRes; // Горизонтальное разрешение создающего устройства unsigned int VRes; // Вертикальное разрешение создающего устройства unsigned char Palette[48]; // Набор цветовой палитры (для 16-цветного изображения) unsigned char Reserved; unsigned char Planes; // Число цветовых слоев unsigned int BytePerLine; // Число байт на строку в цветовом слое (для PCX-файлов всегда должно быть четным) unsigned int PaletteInfo; // Как интерпретировать палитру: 1 = цветная/черно-белая, 2 = градации серого unsigned int HScreenSize; unsigned int VScreenSize; unsigned char Filler[54]; // Заполняется нулями до конца заголовка } TPCXHeader; Смещение Обозначение Длина Описание / комментарий Manufacturer 1 Постоянный флаг 10 = ZSoft .PCX 1 Version 1 Информация о версии: 0 = Версия 2.5 2 = Версия 2.8 с информацией о палитре 3 = Версия 2.8 без информации о палитре 5 = Версия 3.0 2 Encoding 1 1 = PCX кодирование длинными сериями 3 Bits per pixel 1 в слое 4 Window 8 Размеры изображения (Xmin, Ymin) – (Xmax, Ymax) в пикселах включительно 12 Hres 2 Горизонтальное разрешение создающего устройства 14 Vres 2 Вертикальное разрешение создающего устройства 16 Colormap 48 Набор цветовой палитры (см. далее текст) 64 Reserved 1   65 NPlanes 1 Число цветовых слоев 66 Bytes per Line 2 Число байт на строку в цветовом слое (для PCX-файлов всегда должно быть четным) 68 Palette Info 2 Как интерпретировать палитру: 1 = цветная/черно-белая, 2 = градации серого 70 Filler 58 Заполняется нулями до конца заголовка Все переменные длины 2 являются целыми. Декодирование файлов в формате PCX Сначала определяется размер изображения, для этого вычисляют [XSIZE = Xmax - Xmin + 1] и [YSIZE = Ymax - Ymin + 1]. Затем вычисляют, сколько байтов требуется для сохранения одной несжатой строки развертки изображения: TotalBytes = NPlanes * BytesPerLine Т.к. всегда используется целое число байтов, возможно существование неиспользуемых данных в конце каждой строки развертки. TotalBytes показывает, сколько памяти должно быть доступно для декодирования каждой строки развертки, включая неиспользуемую информацию на правом конце каждой строки. Далее выполняется собственно декодирование, читается первый байт данных из файла. Если два старших бита этого байта равны 1, оставшиеся шесть битов показывают, сколько раз следует повторить следующий байт из файла. Если это не так, то этот байт сам является данными с повторителем равным 1. Далее продолжается декодирование до конца строки, ведя подсчет количества байтов, переданных в буфер вывода. В конце каждой строки развертки имеет место остановка алгоритма кодирования, но ее не существует при переходе от одного слоя к другому. Когда строка сформирована полностью, в конце каждого слоя внутри строки возможно наличие лишних данных. Для нахождения этого остатка используются значения XSIZE и YSIZE. Если данные являются многослойными, то BytesPerLine показывает, где заканчивается каждый слой внутри строки развертки. Продолжается декодирование оставшихся строк. В файле возможно наличие лишних строк с округлением на 8 или 16 строк. Описание информации о палитре Информация о 16-цветной палитре (EGA/VGA). Информация о палитре запоминается в одном из двух различных форматов. В стандартном формате RGB (IBM EGA, IBM VGA) данные запоминаются в 16 тройках. Каждая тройка состоит из 3 байтов со значениями красного (Red), зеленого (Green) и синего (Blue) цветов. Значения могут находиться в диапазоне 0-255 Информация о 256-цветной палитре VGA. 256-цветная палитра форматируется и интерпретируется точно так же, как 16-цветная. Палитра (число цветов * 3 байта длины) добавляется в конец PCX файла и ей предшествует байт с десятичным значением 12. Для доступа к 256-цветной палитре следует: 1. Прочитать в заголовке поле Version. Если оно равно 5, палитра должна быть. Или прочитать в заголовке поле Bits per pixel. Если оно равно 8, 256-цветная палитра должна быть. 2. Прочитать конец файла и отсчитать назад 769 байт. Найденное вами значение должно равняться 12, что указывает на присутствие 256-цветной палитры. Формат GIF GIF (Graphics Interchange Format — формат для обмена изображениями) Формат GIF способен хранить сжатые данные без потери качества в формате до 256 цветов. Независящий от аппаратного обеспечения формат GIF был разработан в 1987 году (GIF87a) фирмой CompuServe для передачи растровых изображений по сетям. В 1989-м формат был модифицирован (GIF89a), были добавлены поддержка прозрачности и анимации. GIF использует LZW-компрессию, что позволяет неплохо сжимать файлы, в которых много однородных заливок (логотипы, надписи, схемы). Изображение в формате GIF хранится построчно, поддерживается только формат с индексированой палитрой цветов. Стандарт разрабатывался для поддержки 256-цветовой. При этом каждый кадр содержит свою палитру. Один из цветов в палитре может быть объявлен «прозрачным». В этом случае в программах, которые поддерживают прозрачность GIF (например, большинство современных браузеров) сквозь пиксели, окрашеные «прозрачным» цветом будет виден фон GIF использует формат сжатия LZW. Таким образом, хорошо сжимаются изображения, строки которых имеют повторяющиеся участки. Например, изображения в которых много пикселей одного цвета по горизонтали. Алгоритм сжатия LZW относится к форматам сжатия без потерь. Это означает, что восстановленые из GIF данные будут в точности соответствовать упакованым. Следует отметить, что это верно только для 8-битных изображений с палитрой, для цветной фотографии потери будут обусловлены переводом её к 256 цветам. Метод сжатия LZW разработан в 1978 году израильтянами Лемпелом и Зивом и доработан позднее в США. Сжимает данные путём поиска одинаковых последовательностей (они называются фразы) во всем файле. Выявленные последовательности сохраняются в таблице, им присваиваются более короткие маркеры (ключи). Так, если в изображении имеются наборы из розового, оранжевого и зелёного пикселов, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например, 7) и затем сохраняет эти данные 50 раз в виде числа 7. Метод LZW, так же, как и RLE, лучше действует на участках однородных, свободных от шума цветов, он действует гораздо лучше, чем RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее. Формат GIF допускает чересстрочное хранение данных. При этом строки разбиваются на группы, и меняется порядок хранения строк в файле. При загрузке изображение проявляется постепенно, в несколько проходов. Благодаря этому, имея только часть файла, можно увидеть изображение целиком, но с меньшим разрешением. Порядок хранения строго определен, а именно, строки изображения с чередованием размещаются в четыре прохода: каждая 8-я строка, начиная с 0-й; каждая 8-я строка, начиная с 4-й; каждая 4-я строка, начиная с 2-й; каждая 2-я строка, начиная с 1-й. Таким образом, загрузив 1/8 данных, пользователь будет иметь представление о целом изображении. Таким образом, задолго до окончания загрузки файла пользователь может понять, что внутри и решить, стоит ли ждать полной загрузки изображения. Чересстрочная запись незначительно увеличивает размер файла, но это, как правило, оправдывается приобретаемым свойством. Формат GIF поддерживает анимационные изображения. Фрагменты представляют собой последовательности нескольких статичных кадров, а также информацию о том, сколько времени каждый кадр будет показан на экране. Анимация может быть закольцована, тогда после последнего кадра будет вновь показан первый и так далее. Формат JPEG JPEG (Joint Photographic Experts Group — объединённая группа экспертов в области фотографии) — является широкоиспользуемым методом сжатия фотоизображений. Формат файла, который содержит сжатые данные обычно также называют именем JPEG; наиболее распространённые расширения для таких файлов .jpeg, .jfif, .jpg, .JPG, или .JPE. Однако из них .jpg самое популярное расширение на всех платформах. JPEG метод сжатия, позволяющим сжимать данные полноцветных многоградационных изображений с глубиной от 6 до 24 бит/пиксел с достаточно высокой скоростью и эффективностью. Сегодня JPEG - эта схема сжатия изображений, которая позволяет достичь очень высоких коэффициентов сжатия. Правда, максимальное сжатие графической информации, как правило, связано с определенной потерей информации. То есть, для достижения высокой степени сжатия алгоритм так изменяет исходные данные, что получаемое после восстановления изображение будет отличаться от исходного (сжимаемого). Этот метод сжатия используется для работы с полноцветными изображениями высокого фотографического качества Этапы обработки изображения 1) Плавное преобразование цветового пространства: [R G B] -> [Y Cb Cr] (R,G,B - 8-битовые величины без знака) | Y | | 0.299 0.587 0.114 | | R | | 0 | | Cb | = | -0.1687 -0.3313 0.5 | * | G | + |128| | Cr | | 0.5 -0.4187 -0.0813 | | B | |128| Новая величина Y = 0.299*R + 0.587*G + 0.114*B названа яркостью. Величины Cb = - 0.1687*R - 0.3313*G + 0.5 *B + 128 и Cr = 0.5 *R - 0.4187*G - 0.0813*B + 128 названы цветовыми величинами и представляют 2 координаты в системе, которая измеряет оттенок и насыщение цвета. Эти 2 координаты кратко названы цветоразностью. Преобразование [Y,Cb,Cr] в [R,G,B] (обратно предыдущему преобразованию) RGB-цвет может быть вычислен непосредственно из YCbCr (8-битовые величины без знака) следующим образом: R = Y + 1.402 *(Cr-128) G = Y - 0.34414*(Cb-128) - 0.71414*(Cr-128) B = Y + 1.772 *(Cb-128) 2) Дискретизация JPEG Стандарт принимает во внимание то, что глаз более чувствителен к яркости цвета, чем к оттенку этого цвета. Так, для большинства JPG, яркость взята для каждого пикселя, тогда как цветоразность – как средняя величина для блока 2x2 пикселей. Y Y Y3 Y4 Cb=0,25*U cR=0,25*V =1..4 =1..4 3) Сдвиг Уровня Все 8-битовые величины без знака (Y,Cb,Cr) в изображении - "смещенные по уровню": они преобразовываются в 8-битовое знаковое представление вычитанием 128 из их величины. 4) 8x8 Дискретное Косинусоидальное Преобразование (DCT) Изображение делится на блоки 8x8 пикселей. Затем для каждого блока 8x8 применяется DCT-трансформация. Блоки 8x8 обрабатываются слева направо и сверху вниз. Примечание: Поскольку каждый пиксель в блоке 8x8 имеет 3 компонента (Y,Cb,Cr), DCT приложен отдельно в трех блоках 8x8: • Первый блок 8x8 является блоком, который содержит яркость пикселей в исходном блоке 8x8; • Второй блок 8x8 является блоком, который содержит величины Cb; • И, аналогично, третий блок 8x8 содержит величины Cr. Цель: от обработки исходных изображений переходим к пространству частот изменения яркости и оттенка. DCT-трансформация очень похожа на 2-мерное преобразование Фурье, которое получает из временного интервала (исходный блок 8x8) частотный интервал (новые коэффициенты 8x8=64, которые представляют амплитуды проанализированного частотного пространства) Математическое определение прямого DCT (FDCT) и обратного DCT (IDCT): FDCT: u,v = 0,1...7 c(u,v)=1/2, когда u=v=0; c(u,v)= 1 – в остальных случаях. IDCT: x,y = 0,1...7 5) Зигзагообразная перестановка 64 DCT коэффициентов Смысл – в том, что мы просматриваем коэффициенты 8x8 DCT в порядке повышения пространственных частот (Числа в блоке 8x8 указывают порядок, в котором мы просматриваем 2-мерную матрицу 8x8) 0, 1, 5, 6,14,15,27,28, 2, 4, 7,13,16,26,29,42, 3, 8,12,17,25,30,41,43, 9,11,18,24,31,40,44,53, 10,19,23,32,39,45,52,54, 20,22,33,38,46,51,55,60, 21,34,37,47,50,56,59,61, 35,36,48,49,57,58,62,63 Результат- отсортированный вектор с 64 коэффициентами (0..63). Первая величина на векторе (индекс 0) соответствует самой низкой частоте в изображении – она обозначается термином DC. С увеличением индекса на векторе, мы получаем величины соответствующие высшим частотам (величина с индексом 63 соответствует амплитуде самой высокой частоте в блоке 8x8). Остальная часть коэффициентов DCT обозначается AC. Вычисления при использовании метода DCT чрезвычайно сложны; фактически — это наиболее трудоемкий этап сжатия JPEG. Выполнив его, мы практически разделяем высокочастотную и низкочастотную информацию, из которых состоит изображение. После этого можно отбросить высокочастотные данные без потери низкочастотных. Сам по себе этап преобразования DCT не предусматривает потерь, за исключением ошибок округления. 6) Квантование На этом этапе, у нас есть отсортированный вектор с 64 величинами, соответствующими амплитудам 64 пространственных частот в блоке 8x8. Далее, каждая величина делится на число, определенное для вектора с 64 величинами - таблицу квантования, затем округляется до ближайшего целого. для (i = 0; i<=63; i++) вектор[i] = (округлить) (вектор[i] / таблица_квантования[i] + 0.5) Дискретное косинусное преобразование представляет собой преобразование информации без потерь и не осуществляет никакого сжатия. Напротив, дискретное косинусное преобразование подготавливает информацию для этапа сжатия с потерями или округления. Округление представляет собой процесс уменьшения количества битов, необходимых для хранения коэффициентов матрицы дискретного косинусного преобразования за счет потери точности. Стандарт JPEG реализует эту процедуру через матрицу округления. Для каждого элемента матрицы дискретного косинусного преобразования существует соответствующий элемент матрицы округления. Результирующая матрица получается делением каждого элемента матрицы дискретного косинусного преобразования на соответствующий элемент матрицы округления и последующим округлением результата до ближайшего целого числа. Как правило, значения элементов матрицы округления растут по направлению слева направо и сверху вниз. Выбор матрицы округления. От выбора матрицы округления зависит баланс между степенью сжатия изображения и его качеством после восстановления. Стандарт JPEG позволяет использовать любую матрицу округления, однако ISO разработала набор матриц округления. Пример матрицы округления: 3 5 7 9 11 13 15 17 5 7 11 13 15 17 19 21 7 11 13 15 17 19 21 23 9 11 13 15 17 19 21 23 11 13 15 17 19 21 23 25 13 15 17 19 21 23 25 27 15 17 19 21 23 25 27 29 17 19 21 23 25 27 29 31 Необходимо отметить, что при таких значениях матрицы округления коэффициент в матрице дискретного косинусного преобразования, расположенный в ячейке (7,7), должен принимать значение не меньше 16, чтобы после округления иметь значение, отличное от 0, и влиять на декодируемое изображение. Таким образом, операция округления является единственной фазой работы JPEG, где происходит потеря информации. Чем больше коэффициент квантования, тем больше данных теряется, поскольку реальное DCT-значение представляется все менее и менее точно. Каждая из 64 позиций выходного блока DCT имеет собственный коэффициент квантования. Причем термы большего порядка квантуются с большим коэффициентом, чем термы меньшего порядка. Кроме того, для данных яркости и цветности применяются отдельные таблицы квантования, позволяющие квантовать данные цветности с большими коэффициентами, чем данные яркости. Таким образом, JPEG использует различную чувствительность глаза к яркости и цветности изображения. На этом этапе большинство JPEG-компрессоров управляются с помощью установки качества. Компрессор использует встроенную таблицу, рассчитанную на среднее качество, и наращивает или уменьшает значение каждого элемента таблицы обратно пропорционально требуемому качеству. Применяемые таблицы квантования записываются в сжатый файл, чтобы декомпрессор знал, как восстановить коэффициенты DCT (приблизительно). Выбор соответствующей таблицы квантования является "высоким искусством". Большинство существующих компрессоров используют таблицу, разработанную Комитетом JPEG ISO. Возможно, со временем будут предложены таблицы, позволяющие осуществлять сжатие более эффективно и при сохранении качества изображения. На квантованном векторе, на высоких пространственных частотах, мы имеем как правило много последовательных нулей. 7) RLE кодирование нулей Теперь у нас есть квантованный вектор с длинной последовательностью нулей. Мы можем использовать это, кодируя последовательные нули. Здесь мы пропускаем кодировку первого коэффициента вектора (коэффициент DC), который закодирован по-другому. Рассмотрим исходный 64 вектор как 63 вектор (это - 64 вектор без первого коэффициента) Допустим, мы имеем 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, только 0,...,0 Здесь - как RLC JPEG сжатие сделано для этого примера: (0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); EOB EOB - короткая форма для Конца Блока, это - специальная кодированная величина (маркер). (0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); (0,0) 8) Конечный шаг - кодирование Хаффмана Конечный поток битов записывается в файле JPЕG на диск. Вопросы для самоконтроля. • Достоинства и недостатки формата BMP • Область применения формата GIF • Какие методы сжатия используются в формате JPEG Литература 1. Аммерал Л.Программирование графики на ТурбоСи.-М. :СолСистем. 2. Глушаков С.В., Кнабе Г.А.Компьютерная графика.-Харьков. :Фолио, 2002.500 с. 3. Роджерс Д., Адамс Дж.А.Математические основы машинной графики. Пер.с англ.-М.:Мир,2001.-604с.,ил. 4. http://www.compression.ru - все о методах сжатия. 5. Просис Д. Файлы растровой графики: взгляд внутрь. // PC Magazine. - 1996. - December с. 3 - 21. 6. Климов А.С. Форматы графических файлов. - С.-Петербург: ДиаСофт, - 480с. 7. Матвеев С. Форматы графических файлов. // Открытые системы. - 1997.- №4. - с.12-15. 8. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC . - Москва: Унитех, - 320с. 9. Мюррей Д.Д. , Райнер У. Ван. Энциклопедия форматов графических файлов. Пер. с англ. - Киев: BHV, - 535с.