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

Лекции по курсу Представление графической информации Перцев И.В. Графические данные и цветовые модели. Векторная и растровая графика В настоящее время доля графической информации, хранимой на локальных носителях и передаваемой по сетям связи, достаточно велика, соответственно весьма актуален вопрос о способах хранения и обработки этой информации. Графические данные исторически делятся на 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 байт Структура и примеры графических растровых форматов Графический формат задает способ хранения графики в файле. Формат определяет объем памяти, требуемой для хранения изображения и скорость обработки графической информации. Для уменьшения объема данных используются различные методы сжатия информации. Растровые файлы различны типов, отличаясь деталями, как правило имеют схожую структуру: • Заголовок • Палитра • Растровые данные В свою очередь в заголовок включается обычно следующая информация: • Идентификатор графического формата • Версия графического формата • Описание растра – количество строк в растре, пикселей в строке, битовая глубина пикселей. • Тип используемого сжатия • Координаты изображения на устройстве вывода • Разрешение в точках на дюйм (DPI). Используется для указания разрешающей способности при вводе графической информации, например, со сканера, или выводе информации, например, на принтер. Зная разрешение, можно восстановить размер оригинала изображения. • Текстовое описание растра или комментарии. Палитра В растровых файлах используется обычно один из двух методов хранения данных о пикселях. В полноцветных изображениях пиксель может принимать любое из более чем 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. Формат BMP Формат BMP (от слова bitmap) был создан компанией Microsoft и широко используется в ОС Windows для растровой графики. Вам необходимо записать изображение в этом формате, например, если вы хотите использовать его в качестве фона вашего рабочего стола. Хотя в этом формате может применяться компрессия, большинство программ ее не используют. BMP-файлы с компрессией могут иметь расширение RLE. Без компрессии размер файла оказывается близок к максимальному. BMP-файл состоит из четырёх частей: 1. Заголовок файла (FILEHEADER) 2. Заголовок изображения (MAPINFO) 3. Палитра (может отсутствовать) 4. Само изображение Тип «WORD» должен иметь размер 16 бит, типы «DWORD» и «LONG» — 32 бита Рассмотрим заголовки для BMP версии 3 1. Файлы битовых образов нового формата начинаются со структуры размером 14 байт FileHeader { word    bfType;    //тип файла (для битового образа - BM) dword    bfSize;    //размер файла в dword word bfReserved1;    //не используется word bfReserved2;    //не используется dword bfOffbits;     //смещение данных битового образа от заголовка в байтах } 2. Непосредственно за ней располагается структура MapInfo, содержащая всю информацию о битовом образе. (40 байт для версии BMP 3) MapInfo { dword Size;         //число байт, занимаемых структурой MapInfo dword Width;        //ширина битового образа в пикселях dword Height;        //высота битового образа в пикселях word Planes;        //число битовых плоскостей word BitCount;    //число битов на пиксель dword Compression;    //тип сжатия dword SizeImage;    //размер картинки в байтах long XPelsPerMeter;//горизонтальное разрешение устройства, пиксель/м long YPelPerMeter; //вертикальное разрешение устройства, пиксель/м dword ClrUsed;    //число используемых цветов dword ClrImportant; //число "важных" цветов } Более подробно: Size - обычно используется для облегчения доступа к таблице цветов (палитре). Planes - определяет число битовых плоскостей; однако, поскольку цвет кодируется последовательными битами, это число всегда равно 1. BitCount - этим полем определяется число цветов, используемых битовым образом. В зависимости от способа кодирования, может принимать значения: 1 - битовый образ монохромный, и таблица цветов должна содержать два элемента. Каждый бит в массиве данных кодирует один пиксель. Если значение бита - 0, то пиксель становится первым цветом таблицы; если - 1, пиксель становится вторым цветом таблицы. 4 - битовый образ имеет максимум 16 цветов, и массив bmiColors (таблица цветов) имеет до 16 элементов. Цвет каждого пиксель определяется по таблице цветов при помощи четырехбитного индекса. Например, если первый байт данных имеет значение 3Ah, то при отображении битового образа цвет первого пикселя определяет элемент таблицы цветов с индексом 3, а цвет второго – с индексом 10(А). (в каждом байте информация о 2-х пикселях) 8 - битовый образ имеет максимум 256 цветов, и таблица цветов имеет до 256 элементов. Каждый байт массива данных определяет цвет одного пикселя. 16 - файл не содержит палитры. Каждые два байта изображения хранят интенсивность красной, зелёной и синей компоненты одного пикселя. При этом старший бит не используется, на каждую компоненту отведено 5 бит: 0RRRRRGGGGGBBBBB. 24 - битовый образ имеет максимум 2 в 24-й степени цветов. Таблица цветов пуста, а цвет пикселей определяется пакетами из трех байтов, описывающими цветовые интенсивности красного, зеленого и голубого цветов. biCompression - тип сжатия. Может принимать значения:     BI_RGB - сжатие отсутствует;     BI_RLE8 - сжатие для формата 8 бит на пиксел;     BI_RLE4 - сжатие для формата 4 бита на пиксел. XPelsPerMeter и YPelsPerMeter - могут использоваться для выбора из списка ресурсов пиктограммы, наиболее подходящей для данного устройства. ClrUsed - число цветов, используемых данными битовым образом. Если 0, то используются все цвета палитры (указанные в массиве bmiColors). ClrImportant - используется для управления алгоритмом отображения цветов. Так, если четыре различных приложения отображают на экране по одному битовому образу с 75 цветами каждый, то адаптер, выводящий 256 цветов одновременно, не сможет полностью аутентично отобразить на экране все 4 картинки. В этом случае используется механизм замены цветов - ищется битовый образ с наименьшим приоритетом и его "лишние" цвета заменяются наиболее подходящими. 3. Палитра. Хранится в виде следующего массива струткур: структура RGBquad {     byte    rgbRed;         //интенсивность красного     byte    rgbGreen;         //интенсивность зеленого     byte    rgbBlue;         //интенсивность голубого     byte    rgbReserved;    //не используется     } BmiColors[N] Где N – количество цветов в палитре. 4.После того, как все параметры битового образа определены, в файле идут сами строки битовой плоскости, причем первой строкой в формате BMP считается нижняя строка (т.е. начало координат находится в левом нижнем углу изображения). Cтроки выровнены по 32-битной границе - dword ! То есть для 256-цветного изображения при количестве пикселей в строке 253, в растре каждая строка будет занимать 256 байт – 253 байта хранят информацию о пикселях, и еще 3 добавляются для выравнивания (не выводятся на экран). Описание библиотеки для работы с графикой Wingraph.h Для облегчения работы с графикой в курсе ПГИ была разработана библиотека Wingraph.h для среды программирования Borland C++ Builder или Dev-cpp. Данная библиотека позволяет легко выводить графические объекты с требуемым разрешением и глубиной цвета. пример #define MAXCOLORTC // MAXCOLOR16 - 16 цветов // MAXCOLOR256 - 256 16 цветов // MAXCOLORTC - True Color #include "wingraph.h" int main() { resize(512,512); for(int i=0; i<512; i++) for(int j=0; j<512; j++) putpixel(i,j,RGB(i/2,j/2,255-j/2)); } Можно так же пользовоться библиотекой graphics.h или любой другой. #include "graphics.h" int main() { initwindow(256,256); for(int i=0; i<256; i++) for(int j=0; j<256; j++) putpixel(i,j,RGB(i,255-i,128)); getch(); } Библиотека graphics.h Для того, чтобы подключить модуль для работы с графикой в Windows 8/10, сделайте следуюшее: 1. Скачайте последнюю версию Dev-C++. 2. Скачайте архив, содержащий файлы graphics.h, winbgim.h (заголовочные файл) и libbgi.a (библиотека). Размер архива 28 Кб. Далее предполагается, %Dev-Cpp% — это папка, в которой установлена среда Dev-C++ (например, C:\Program Files (x86)\Dev-Cpp). 3. Скопируйте файл graphics.h в папку %Dev-Cpp%\MinGW64\x86_64-w64-mingw32\include. 4. Скопируйте файл libbgi.a в папку %Dev-Cpp%\MinGW64\x86_64-w64-mingw32\lib. 5. Запустите оболочку Dev-C++ и войдите в меню Сервис-Параметры компилятора. 6. Перейдите на вкладку Компилятор. Переключитесь на 32-битный компилятор (32-bit Release). Включите флажок Добавить эти команды к командной строке компоновщика и добавьте в окно под этим флажком строчку -lbgi -lgdi32 -luser32 как на рисунке: Пример обработки BMP файл. (Лб 1,2,4) #include "graphics.h" #include #include //#define COLOR(r,g,b) (r|(g<<8)|(b<<16)|(3<<24)) #pragma pack(1) struct head { char type[2]; long fsize; short rez1, rez2; long offbits; long head2size; long width; long height; short planes; short bitcount; long compression; long sizeimage; long x; long y; long clrused; long clrimp; } head_file; unsigned char pal[256][4]; main() { FILE* file, *file2; file = fopen("CAT256.BMP", "rb"); file2 = fopen("CAT256_BW.BMP", "wb"); fread(&head_file, sizeof(head_file), 1, file); fwrite(&head_file, sizeof(head_file), 1, file2); int width = head_file.width; int height = head_file.height; int width1=width; while (width1 % 4 != 0) width1++; int color; printf("%.2s %d %d %d",head_file.type, width, height, head_file.bitcount); fread(pal, sizeof(pal), 1, file); for(int i=0;i<256;i++) { // pal[i][0]/=1.5; pal[i][1]/=1.5; pal[i][2]/=1.5; //преобразование палитры } fwrite(pal, sizeof(pal), 1, file2); initwindow ( width, height,"Lab PGI"); byte col; for (int i = height-1; i >=0; i--) { for (int j = 0; j < width1; j++) { fread(&col, 1, 1, file); if (j < width) { // if(i%50==0||j%50==0) col=0; //преобразование растра color = RGB(pal[col][2],pal[col][1],pal[col][0]); putpixel(j,i, color); } fwrite(&col, 1, 1, file2); } } fclose(file); fclose(file2); getchar(); } Масштабирование (Лб 5) #include "graphics.h" #include #include //#define COLOR(r,g,b) (r|(g<<8)|(b<<16)|(3<<24)) #pragma pack(1) struct head { char type[2]; long fsize; short rez1, rez2; long offbits; long head2size; long width; long height; short planes; short bitcount; long compression; long sizeimage; long x; long y; long clrused; long clrimp; } head_file; unsigned char pal[256][4]; main() { FILE* file; file = fopen("CAT256.BMP", "rb"); fread(&head_file, sizeof(head_file), 1, file); int width = head_file.width; int height = head_file.height; int width1=width; while (width1 % 4 != 0) width1++; printf("%.2s %d %d %d",head_file.type, width, height, 1< #include #define COLOR(r,g,b) (r|(g<<8)|(b<<16)|(3<<24)) #pragma pack(1) struct head { char type[2]; long fsize; short rez1, rez2; long offbits; long head2size; long width; long height; short planes; short bitcount; long compression; long sizeimage; long x; long y; long clrused; long clrimp; } head_file; main() { FILE* file; file = fopen("fish.BMP", "rb"); fread(&head_file, sizeof(head_file), 1, file); int width = head_file.width; int height = head_file.height; int width1=width; while (width1 % 4 != 0) width1++; printf("%.2s %d %d %d\n",head_file.type, width, height, 1<=0; i--) { for (int j = 0; j < width1; j++) { fread(&col, 1, 3, file); /* if(i<100 &&j<100) { // логотип – белый квадрат col[0]= col[0]*k+255*(1-k); col[1]= col[1]*k+255*(1-k); col[2]= col[2]*k+255*(1-k); } */ //далее замена младших бит каждого пикселя на случайные for(int m=0;m<3; m++) col[m]=col[m]&m2 | rand()%(m1+1); if (j < width){ color = COLOR(col[2],col[1],col[0]); putpixel(j,i, color); } } } fclose(file); getchar(); } Описание формата PCX Файлы изображений, которые используются в продуктах семейства PC Paintbrush и FRIEZE, были разработаны фирмой Zsoft. Открывать или импортировать файлы PCX могут почти все графические приложения для персональных компьютеров. Цветовые возможности 1, 2, 4, 8 или 24- битовый цвет. Всегда применяется сжатие RLE. Файлы изображения PCX начинается с заголовка длиной 128 байт. Затем идут закодированные графические данные. При кодировании используется простой алгоритм, основанный на методе длинных серий. Если в файле хранится несколько цветовых слоев, каждая строка изображения запоминается по цветовым слоям Метод кодирования состоит в следующем: ДЛЯ каждого байта X, прочитанного из файла. ЕСЛИ оба старших бита X равны 1, то <повторитель> = значению, хранящемуся в 6 младших битах X <данные> = находятся в следующем байте за X. ИНАЧЕ <повторитель> = 1 <данные> = X Формат заголовка 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 Заполняется нулями до конца заголовка Декодирование файлов в формате 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-цветной палитры. #include "graphics.h" #include #include //#define COLOR(r,g,b) (r|(g<<8)|(b<<16)|(3<<24)) #pragma pack(1) typedef struct TPCXHeaderStruct { unsigned char ID; unsigned char Version; unsigned char Coding; unsigned char BitPerPixel; unsigned short XMin; unsigned short YMin; unsigned short XMax; unsigned short YMax; unsigned short HRes; unsigned short VRes; unsigned char Palette[48]; unsigned char Reserved; unsigned char Planes; unsigned short BytePerLine; unsigned short PaletteInfo; unsigned short HScreenSize; unsigned short VScreenSize; unsigned char Filler[54]; } TPCXHeader; main() { FILE *a; a = fopen("cat256.PCX", "rb"); unsigned char pal[256][3]; unsigned char id; fseek(a, -256 * 3 -1, SEEK_END); fread(&id,1,1,a); fread(pal, sizeof(pal), 1, a); // Ïàëèòðó ñ÷èòûâàåì fseek(a, 0, SEEK_SET); TPCXHeader header; fread(&header, sizeof(header), 1, a); int xSize = header.XMax - header.XMin + 1; int ySize = header.YMax - header.YMin + 1; printf("id=%d xsize=%d yzize=%d\n ",id,xSize,ySize); initwindow (xSize, ySize); int totalBytes = header.Planes * header.BytePerLine; int color; byte c, t; for (int b = 0; b < ySize; b++) { int j = 0; while (j < totalBytes) { fread(&c, 1, 1, a); // Èç ôàéëà ÷èòàåì îäèí áàéò t = c & 0xC0; if (t == 0xC0) { // страршие биты 11 t = c & 0x3F;//из младших 6 берем счетчик группы fread(&c, 1, 1, a); // Значение группы for (int d = 0; d < t; d++) { if (j < xSize) //putpixel(j, b, c); color = RGB(pal[c][0],pal[c][1],pal[c][2]); putpixel(j,b, color); j++; } } else { // одиночный пиксель if (j < xSize) // putpixel(j, b, c); color = RGB(pal[c][0],pal[c][1],pal[c][2]); putpixel(j,b, color); j++; } } } getchar(); fclose(a); } Преобразование цветов. Пример. #include "graphics.h" #include #include #define COLOR(r,g,b) (r|(g<<8)|(b<<16)|(3<<24)) #pragma pack(1) struct head { short bftype; long bfsize; short rez1, rez2; long bfoffbits; long bisize; long biwidth; long biheight; short biplanes; short bibitcount; long bicompression; long bisizeimage; long bix; long biy; long biclrused; long biclrimp; } head_file; unsigned char pal[256][4], pal1[16][4]; int num[16]={0}; long ver[256]={0}; long razn(unsigned char p1[4], unsigned char p2[4]) { return (long)(p1[0]-p2[0])*(p1[0]-p2[0])+ (long)(p1[2]-p2[2])*(p1[2]-p2[2])+ (long)(p1[1]-p2[1])*(p1[1]-p2[1]); } main(){ FILE* File; int k,i,j,max,min,r,n,l; File = fopen("CAT256.BMP", "rb"); fread(&head_file, sizeof(head_file), 1, File); fread(pal, sizeof(pal), 1, File); int Width = head_file.biwidth; int Height = head_file.biheight; int Width1=Width; while (Width1 % 4 != 0)Width1++; int color; unsigned char **rastr; rastr=(unsigned char **)malloc(Height*sizeof(char *)); for(int i=0; i0) { printf("%10d",ver[j]); max++; } } printf("\n"); getch(); for(i=0; i<16; i++) { for(max=n=j=0; j<256; j++) if(ver[j]>max) { for(k=0; k0) {max=ver[j]; n=j; } } num[i]=n; printf("%d\n",ver[n]); ver[n]=-ver[n]; } for(max=j=0; j<256; j++) { if(ver[j]>0) { printf("%10d",ver[j]); max++; } } printf("\n%d",max); for (int i=0;i<16;i++) { pal1[i][0]=pal[num[i]][0]; pal1[i][1]=pal[num[i]][1]; pal1[i][2]=pal[num[i]][2]; } for (int i = 0; i < Height; i++) { for (int j = 0; j < Width; j++) { col= rastr[i][j]; min=razn(pal[col],pal1[0]); for(k=1;k<16;k++) { r=razn(pal[col],pal1[k]); if(min>r) {min=r; l=k;} } color = RGB(pal1[l][2],pal1[l][1],pal1[l][0]); putpixel(j+Width,Height-i, color); } } fclose(File); getch(); getchar(); } Цветовые модели В компьютерной технике чаще всего используются следующие цветовые модели: 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) ненулевые, то цвет ненасыщенный, причем, наименьшее значение определяет долю серого оттенка, а разность значений – тон и долю насыщенного цветового оттенка. Таким образом, при R=255; G=255; B=0 получаем желтый цвет. CMYK Цветовая модель, используемая в принтерах и в других периферийных устройствах. Комбинации чернил четырех цветов: голубого (C), пурпурного (M), желтого (Y) и черного (К) позволяют воспроизводить все цвета. Теоретически все цвета можно воспроизводить с помощью комбинаций голубого, пурпурного и желтого. Однако, на практике сочетание этих трех цветов не позволяет воспроизвести чистый черный цвет. Поэтому к ним отдельно добавляются черные чернила. Вопросы для самоконтроля. • Достоинства и недостатки векторной графики • Достоинства и недостатки растровой графики • Какой объем памяти требуется доля хранения без сжатия TrueColor изображения 600х800 пикселей • Для чего и в каких случаях используется цветовая палитра Почему для цветных принтеров не подходит цветовая модель RGB Методы сжатия, используемые для графических форматов Так как графическая и видео информация, как правило высоко избыточна, большинство графических и видео форматов используют сжатие информации для уменьшения объема файлов с данной информацией. Сжатие позволяют уменьшить избыточность, присущую графическим данным, и тем самым уменьшить объем памяти, необходимый для их хранения. Мы будет разделять методы сжатия на: • Симметричные и ассиметричные. В симметричных методах затраты на сжатие и восстановление информации примерно одинаковы, в ассиметричных что одно существенно сложнее другого. • Адаптивные и неадаптивные. Адаптивное сжатие позволяет кодеру и декодеру настраиваться на статистику источника. • С потерями и без потерь. Сжатие без потерь – в том случае, если после декодирования информации получаем точную копию оригинала. Для сжатия графики используются следующие методы: • 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) = 1 Собственную информацию, содержащуюся в символе источника aj, можно определить следующим образом: Она может быть интерпретирована как априорная неопределенность символа ai, либо как информация, требуемая для разрешения этой неопределенности. Основание логарифма определяет шкалу, в которой измеряется информация. Наиболее часто используется основание 2, в этом случае информация измеряется в битах. Основной характеристикой источника является его энтропия, характеризующая неопределенность символов источника. Безуслов­ная энтропия определяется как среднее значение собственной информации источника и задается равенством: Энтропия достигает максимума, когда символы источника равновероятны, и минимума, когда вероятность одного из символов равна 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. Она равна: В тех случаях, когда взаимная информация между символами источника велика (источники с высокой корреляцией символов), можно достаточно точно предсказывать вероятность очередного символа по предыдущим. Если перейти от символов источника к блокам символов длины L, то можно определить энтропию Lго порядка. Пусть X = {x1, x2, ... ,xL} — последовательность из L символов дискретного источника с алфавитом A. Тогда определим энтропию на блок символов источника как: где kL — количество всех последовательностей длины L в алфавите А. При L получаем предельную энтропию H. Пример – пусть aj – 1 контрольный срок, ai – 2 контрольный срок. ai aj 1 2 1 кс 0,15 0,04 0,01 0,2 1 0,05 0,30 0,05 0,40 2 0,05 0,15 0,20 0,40 2 кс 0,25 0,49 0,26 1,00 Вероятность 0 за 2КС p(2)=0,26 p(2/0)= p(ai, aj)/p(aj)=0,01/0,2=0,05 p(2/1)= p(ai, aj)/p(aj)=0,05/0,4=0,125 p(2/2)= p(ai, aj)/p(aj)=0,2/0,4=0,5 Вычислим энтропию H(1кс)=-(0,2*log20,2+2*0,4*log20,4)=1,52 H(2кс))=-(0,25*log20,25+0,49*log20,49+0,26*log20,26)=1,51 H(1-2кс)= )=-(0,15*log20,15+0,04*log20,04….)=2,7 H(ai)+H(aj)>=H(aiaj) Энтропия играет очень важную роль в теории информации, определяя минимально возможную среднюю длину кодового слова. Максимум энтропии – когда символы равновероятны и независимы. Так, для бернуллиевских источников средняя длина кодового слова не может быть меньше безусловной энтропии, для марковских источников связности n — меньше условной энтропии nго порядка, и для любого источника — меньше H. Для русского языка H0=5, H1=4,4, H2=3,5, H3=3, Hпредельная=1,4 Парадоксы основанные на условных вероятностях – 3 двери(Монте-Холла), 2 конверта, парадокс коробок Бертрана Кодирование дискретных источников информации Обозначим через 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 [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с.