Метод квантования цветов медианным сечением.

1. Первый шаг состоит в отсечении "краёв" куба, которые не содержат пикселов. К примеру, если у всех пикселов значения красной компоненты не меньше, чем 8 и не больше, чем 250, то отбрасываются части куба от R=0 до R=7 и от R=251 до R=255.

2. Второй шаг заключается в разрезании полученного параллелепипеда на два в срединной точке (медиане) самой длинной стороны. Если самая длинная сторона параллельна оси ‘B’, то компьютер выбирает срединное синее значение из всех синих значений представленных в параллелепипеде (к примеру, 50.000-ое вхождение в отсортированном списке из 100.000 синих значений) и разрезает в этой точке. Теперь параллелепипед разделен на два параллелепипеда меньшего размера, содержащих одинаковое количество пикселов.

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

4. Медианное сечение повторно применяется для того, чтобы разделить куб на 8, 16, 32, 64, 128и 256 параллелепипедов (можно остановиться в любой момент, в зависимости от того, сколько цветов в палитре нужно получить). Они содержат примерно одно и то же количество пикселов.

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

Лекция 17,18 Форматы растровых файлов

Изображения можно хранить в растровом (как массив пикселов) или векторном виде

(как набор примитивов). Любой графический файл состоит из заголовка

и данных. В заголовке располагаются:

1. Идентификатор формата (первые несколько байт). Например, в формате BMP это - 2 символа 'BM' (BitMap), в формате GIF - GIF87a.

2. Тип данных (RGB или палитра, тип упаковки, кол-во битов на пиксел)

3. Размеры изображения

4. Дополнительные параметры (разрешение, строка описания и т.п.)

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

Формат BMP

struct BMP_header

{

char ID[2]; // 'BM' для Windows BitMap

long FSize; // размер файла

long Ver; // версия BMP (=0)

long Image; // положение изображения в файле

long Misc; // должно быть 40

long Width; // ширина изображения

long Height; // высота изображения

short Num; // кол-во изображений (должно быть =1)

short Bits; // кол-во бит на пиксел

// 1 - монохромная (2 значения в палитре), 4,8 - палитра, 24 - RGB

long Comp; // Тип компрессии, 0 - несжатый, 1 - RLE8, 2 - RLE4

long ISize; // размер изображения в байтах

long XRes; // кол-во точек на метр вдоль оси X

long YRes; // кол-во точек на метр вдоль оси Y

long PSize; // Кол-во индексов палитры (16 или 256)

long PImportant; //Кол-во важных для отображения индексов палитры (0 - все важные)

}; // 54 bytes

Палитра находится сразу после заголовка.

FILE *ifile=fopen("имя", "rb");

BMP_header bmp_header;

fread (&bmp_header, sizeof(bmp_header), 1, ifile);

if (bmp_header.Bits==24)

{

fseek(ifile,bmp_header.Image, SEEK_SET);

line_size=(bitmap_width*3+3)&0xFFFFFFFC;

unsigned char *line=new unsigned char[line_size];

for(y=bitmap_height-1;y>=0;y--)

{

fread (line, line_size, 1, ifile);

for(x=0;x<bitmap_width;x++)

bitmap[y*bitmap_width+x]=(line[x*3+2]<<16)+(line[x*3+1]<<8)+(line[x*3+0]<<0);

}

delete line;

}

else

if (bmp_header.Bits==8)

{

long Palette[256];

fread(Palette,256*4,1,ifile);

fseek(ifile,bmp_header.Image, SEEK_SET);

line_size=(bitmap_width+3)&0xFFFFFFFC;

unsigned char *line=new unsigned char[line_size];

for(y=bitmap_height-1;y>=0;y--)

{

fread (line, line_size, 1, ifile);

for(x=0;x<bitmap_width;x++)

bitmap[y*bitmap_width+x]=Palette[line[x]];

}

delete line;

}