Второй  алгоритм Байера. Применяется в основном для получения черно-белых изображений (с глубиной цвета в 1 бит), хотя его  можно модифицировать и для изображений с большей глубиной цвета. Для его работы сначала требуется построить матрицу. Она получается из нулевой матрицы 1х1 в результате рекуррентного соотношения. 
 

        

 
 
 

Ее размер определяется кол-вом битов, исходного  изображения. Сколько бит в его  глубине цвета, столько элементов  должно быть в матрице.  Например, если оно имеет 16 цветов, то достаточно матрицы 4х4, если 256 – 16х16.

Затем значение яркости пиксела сравнивается со значением в матрице и если яркость больше – пиксел подсвечивается, если меньше – то нет (I=(I < matrix[x % 8][y % 8]) ? 0 : 0xFF).

Этот  алгоритм просто вносит некоторые ошибки в изображение, но за счет этого оно выглядит лучше. Например, если оно имеет среднюю яркость, то подсветится половина пикселов на этом участке, чем больше будет яркость – тем больше их будет подсвечено и тем ярче будет казаться эта область наблюдателю. Одним из недостатков является то, что кол-во бит должно быть кратно 2-м (2,4,6,8) и то, что на полученном изображении можно выделить четкую сетку. 

Палитры и оптимизация  палитр.

Одним из вариантов представления изображений  является палитровый режим, когда в  массиве пикселов хранятся не сами цвета, а их индексы в таблице цветов (палитре). Такие режимы позволяют более компактно хранить изображения в памяти и на диске. Например, когда требуется сохранить чертеж, то достаточно палитры из 2-х цветов. При палитризации изображения обычно применяют и псевдотонирование для сохранения большего качества (обычно диффузное). Но даже псевдотонирование вряд ли будет эффективно, если цвета палитры плохо подобраны. В конечном счете, программа должна сделать все возможное для того, чтобы краски палитры как можно лучше соответствовали оттенкам изображения.

Существует  проблема выбора цветовой палитры, с  помощью которой можно отобразить картинку с количеством оттенков, превышающим количество цветов в  палитре, процесс подбора цветов палитры называют оптимизацией палитры. Хотя иногда бывают случаи, когда палитра строго задана (например, вывод изображения на экран, в палитровом режиме в EGA или в Windows).

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

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

Представьте себе картинку с загородной дорогой, где преобладают синие, коричневые, желтые, зеленые тона, и где-то в  одном углу оказался маленький красный, дорожный знак "стоп". Если красный цвет более нигде на этой картинке не встречается, то он не попадет в палитру, и, следовательно, "кирпич" будет окрашен в какой-то другой цвет.

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

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

Метод медианного сечения делит куб на набор (256) параллелепипедов, каждый из которых содержит примерно одинаковое количество пикселов. При таком разбиении куба центральная точка каждого параллелепипеда представляет оптимальный выбор для цветовой палитры. И в самом деле, в той области куба, которая густо заполнена точками, будет больше параллелепипедов и, соответственно, в палитру попадет больше цветов.

А там, где точек меньше, оттуда и цветов будет взято меньше. Ни один цвет не будет отброшен полностью. Тем  же цветам, которые встречаются чаще, будет отдано предпочтение. Обратимся еще раз к примеру с загородной дорогой.

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

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

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;

      } 
 
 
 
 
 
 
 
 
 

Сжатие  графической информации

 
 

Память, необходимая для хранения растрового изображения, вычисляется, как произведение его ширины на высоту и на количество бит на пиксел. К примеру, для хранения RGB фотографии 800 на 600 пикселей нужно примерно 1.4 мегабайта. Для ее передачи по internet c скоростью полтора килобайта (14400) в секунду нужно около 15 минут – т.е. довольно большое время. Или, к примеру, на хранение часового фильма, в котором 30 таких кадров в секунду, нужно 150 гигабайт. Таким образом, алгоритмы архивации информации, ориентированные на изображения, весьма актуальны.

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

1. Типы  изображений.

 

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

• Схематические изображения. Изображения с небольшим  количеством цветов, и большими областями, заполненными одним цветом (деловая  графика, чертежи).
• Фотореалистичные изображения (цифровые или отсканированные фотографии, изображения созданные в программах 3D –визуализации).
• Текстуры, накладываемые на поверхности.