Лекции по "Компьютерной графике"

 

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

2. Требования  к алгоритмам компрессии.

 

Одни  приложения могут предъявлять различные  требования к алгоритмам компрессии, с другой стороны для других приложений эти же требования могут быть не актуальны.  

• Высокая степень компрессии. Данное требование почти всегда актуально, хотя есть и исключения. Хотя в большинстве случаев приходится искать некоторый компромисс со следующим требованием, а именно
• Высокое качество изображения, которое, вообще говоря, противоречит выполнению предыдущего. Кстати, довольно часто алгоритм предоставляет возможность выбора качества архивации (например, JPEG), и соответственно, степени архивации. В случае необходимости 100% соответствия используются алгоритмы сжатия без потерь.
• Высокая скорость компрессии. Интуитивно понятно, что чем больше времени мы будем анализировать изображение, тем лучше будет результат. Таким образом, оно также может входить в противоречие с двумя предыдущими. В некоторых алгоритмах, например фрактальном, можно управлять временем компрессии, естественно, в некоторый (возможно незаметный) ущерб качеству.

Стоит также отметить, что важно также  не только сама скорость, а скорее ее зависимость от, например, размеров изображения. Реализация фрактального алгоритма “в лоб” приведет вообще говоря, к зависимости n² от площади изображения.

• Высокая скорость декомпрессии. Достаточно универсальное требование, хотя стоит отметить, что иногда более, а иногда менее актуально.
• Возможность постепенного проявления изображения, т.е. возможность показать огрубленное изображение, использовав только начало файла. Данное требование стало актуально в web, когда пользователь может, например, решить, продолжать ему закачку большой картинки или нет, скачав только его часть. Иногда эта возможность является свойством алгоритма (например, wavelet), иногда алгоритм можно модифицировать. (В алгоритме Motion JPEG, например, изменили порядок записи коэффициентов,  чтобы сначала шли низко, потом средне, а потом высокочастотные компоненты изображения. В алгоритме Interlaced GIF поступили еще проще, просто записывая строчки изображения не подряд, а через четыре)
• Устойчивость к ошибкам, или локальность нарушений при порче фрагмента файла. В случае широковещания в сети, или цифрового телевидения, не исключена возможность того, что часть данных не дойдет до пользователя. Не хотелось бы, чтобы порча одного маленького кусочка приведет к невозможности посмотреть весь фильм целиком.
• Редактируемость. Под редактируемостью понимается минимальная степень ухудшения качества изображения, при его повторном сохранении после редактирования. Если изображение было сжато с потерями, потом разжато, потом слегка отредактировано (например, пара пикселей поменяли цвет), то этот параметр определит, насколько изображение потеряет в качестве еще. Иногда, изображение может терять в качестве даже безо всякого редактирования, что обусловлено, скорее всего, несовершенством реализации алгоритма, иногда же, например, при фрактальном сжатии, самим алгоритмом.
• Небольшая стоимость аппаратной и (или) эффективность программной реализации. Это требование важно, например, при проектировании алгоритмов сжатия текстур, с учетом дальнейшей интеграции этих алгоритмов в видеочип. Также стоит оценить эффективность таких технологий MMX, 3DNow! и Katmai, и возможность эффективного распараллеливания алгоритмов. 

 

Вообще  говоря, в каждом конкретном случае одни требования нам более важны, другие менее важны, или совсем безразличны. Более того, иногда выбор того или иного алгоритма определяется некоторыми специфическими требованиями. Например, при архивации текстур нам бы хотелось получить информацию о конкретном пикселе как можно меньшими затратами.  
 
 

3. Критерии  сравнения алгоритмов.

 

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

4. Алгоритмы архивации без  потерь.

 

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

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

Алгоритм  RLE. 

Суть  алгоритма состоит в том, что  сначала вытягивается по строкам  растра, а потом повторяющиеся  пиксели заменяются парой (счетчик, значение).

В формате PCX это реализовано следующим  образом: в выходной поток пишется  либо непосредственно значение пикселя (если в двух его старших разрядах не единицы):

[ XX значение  ]

либо  пара

[ 11 счетчик   ] [ что повторять ]

причем  повторяемый символ повторяется  число раз, на единицу большую  счетчика (не имеет смысл повторять 0 раз). Например, строку из 64 повторяющихся байтов мы превратим в два байта. С другой стороны, если в двух старших разрядах пикселя – единицы, и он не повторяется, то мы будем вынуждены записать:

[ 11   000000  ] [ значение      ]

то есть, в худшем случае увеличим размер файла в два раза.

Данный  алгоритм рассчитан на изображения  с большими областями, залитыми одним  цветом. В основном на черно-белые. 

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

Например  цепочка (04,50,00,03,F1,30,60,03,11) распакуется в следующую цепочку (50,50,50,50,F1,30,60,11,11,11). Это позволяет значительно сократить размеры изображений, которые плохо пакуются предыдущим алгоритмом. 

Алгоритм  LZW. 

Основан на упаковке не только повторяющихся  символов, но и повторяющихся последовательностей. Существует огромное количество различных  реализаций алгоритма сжатия LZW (Lempel, Ziv, Welch). Наиболее распространенный формат, использующий такой алгоритм – GIF. Рассмотрим одну из реализаций:

1. Создаем таблицу на 4096 элементов, каждый элемент таблицы соответствует цепочке символов, первые 256 – последовательности, состоящие из одного соответствующего символа. Для кода очистки (ClearCode) и кода конца информации (CodeEndOfInformation) зарезервированы значения 256 и 257. соответственно под коды цепочек остаются значения 258…4095.
2. Берем очередной символ из входной последовательности и добавляем его в конец текущей цепочки (в начале цепочка пуста).
3. Проверяем, есть ли в нашей таблице текущая цепочка. Если есть, то запоминаем ее код и переходим к шагу 2.
4. Если цепочки нет, то заносим ее в таблицу. В выходную последовательность заносим запомненный код, а текущая цепочку полагаем равной последнему считанному символу. Далее переходим к шагу 2. Если таблица закончилась – нужно записать в выходной поток код очистки и перейти к шагу 1.

 

Пусть мы сжимаем  последовательность 0,1,1,2,1,1,1. Тогда, согласно изложенному выше алгоритму добавим к изначально пустой цепочке “0” и проверим, есть ли цепочка “0” в таблице. Поскольку мы при инициализации занесли в таблицу все цепочки из одного символа, то цепочка “0” есть в таблице. Далее мы читаем следующий символ “1” из входного потока и проверяем, есть ли цепочка “0,1” в таблице. Такой цепочки в таблице пока нет. Мы заносим в таблицу цепочку “0,1” (с первым свободным кодом 258) и записываем в поток код “0”. Можно коротко представить архивацию так:

• “0” — есть в таблице;
• “0,1” — нет. Добавляем в таблицу <258>“0,1”. В поток: <0>;
• “1,1” — нет. В таблицу: <259>“1,1”. В поток: <1>;
• “1,2” — нет. В таблицу: <260>“1,2”. В поток: <1>;
• “2,1” — нет. В таблицу: <261>“2,1”. В поток: <2>;
• “1,1” — есть в таблице;
• “1,1,1” — нет. В таблицу: “1,1,1” <262>. В поток: <259>;

Последовательность  кодов для данного примера, попадающих в выходной поток: <0>, <1>, <1>, <2>, <259>.

Данный  алгоритм можно улучшить, заметив, что  в компрессированном файле не может появится значение 512, до того как появилось 511. Таким образом, числа можно записывать сначала как 9-ти битные, потом, после встречи числа 512 как 10 битные, и так далее.  

Алгоритм  Хаффмана. 

Использует  то, что некоторые символы во входной  цепочке встречаются более часто, чем другие. Сжатие происходит за счет того, что символы кодируются разным кол-вом битов, тем, что встречаются чаще соответствует более короткий код, чем для тех, что встречаются реже.  Например, есть цепочка в которой встречаются символы A,B,C,D. При обычной кодировке каждый из них можно закодировать 2 битами A=00,B=01,C=10,D=11. И цепочка из 1000 символов будет иметь длину 2000 бит. Если некоторые символы встречается более часто, чем другие (например, в цепочке 800 символов A, 100 символов B, 50 символов С и 50 символов D), то если сопоставить символам коды разной длины A=0, B=10, C=110,D=111, то общая закодированной длина цепочки составит 800*1+100*2+50*3+50*3=1300 бит. Правда еще придется хранить таблицу соответствия кодов, но она занимает сравнительно немного места при больших размерах цепочек. Обычно коэффициент сжатия составляет около 2-х. Этот алгоритм редко применяют самостоятельно, но вместе с алгоритмом RLE или LZW он дает неплохие результаты.

 

Алгоритм  JPEG. 

Это алгоритм сжатия с потерями придуманный Объединенной группой экспертов по фотографии (Joint Photographic Experts Group). Хорошо подходит для фото-изображений, имеет коэффициент сжатия до 20. В нем изображение проходит через несколько стадий сжатия:

1. сначала оно прореживается по цвету. Человеческий глаз более чувствителен к изменениям яркости, чем и изменению цвета. Сначала изображение переводится в систему YUV (Y-яркость, U,V- цветовые составляющие). Затем цветовые составляющие прореживаются, так, что из каждого квадратика пикселов 2х2 исходного изображения получается один пиксел (фактически изображение приводится к вдвое меньшему разрешению). За счет этого происходит сжатие в (4+4+4)/(4+1+1)=2,66 раз.
2. Изображение разбивается на квадратики 8х8 пикселов и к каждому такому квадратику применяется дискретное косинусное преобразование (по каждой составляющей). Его цель – перейти к спектру значений яркости и цветности в квадратике. Так как глаз более чувствителен к низкочастотным составляющим спектра, а высокочастотные воспринимаются как шум – можно отбросить несколько высокочастотных коэффициентов, и за счет этого получить сжатие. Чем больше коэффициентов будет отброшено, тем больше коэффициент сжатия и искажения изображения.
3. Наконец, эти коэффициенты кодируются с помощью RLE и Хаффмана.

 

Алгоритм S3TC. 

Это алгоритм сжатия текстур (S3 Texture Compression). Это достаточно простой метод, изображение разбивается на квадратики 4х4, каждый квадратик приводится к палитре в 4 цвета. Таким образом, начальное изображение пакуется с коэффициентом (16*4*4)/(16*4+2*4*4)=2,66. Это сжатие с потерями. При этом распаковка происходит очень быстро, что важно для текстур. 

Алгоритм  MPEG. 

Это алгоритм сжатия видео, здесь используется предположение, что соседние кадры мало отличаются друг от друга. Поэтому достаточно описать лишь разницу между ними. В этом алгоритме изображение как и в JPEG прореживается по цвету, а затем разбивается на блоки 16x16. Первый кадр кодируется как обычное изображение, а для последующего для каждого блока ищется наиболее похожий блок в предыдущем кадре. Причем он может быть смещен на некоторый вектор. Если блоки совпадают полностью – можно просто сохранить этот вектор, если отличаются – то можно сохранить разницу между ними, она должна занять меньше места, чем сам блок. Кроме того, можно посчитать среднее между блоком с предыдущего кадра и блоком со следующего, которое может лучше соответствовать данному.

 

 
 

Существует  три типа закодированных кадров. I-фремы - это кадры, закодированные как неподвижные изображения - без ссылок на последующие или предыдущие. Они используются как стартовые.

P-фреймы - это кадры, предсказанные из  предыдущих I- или P-кадров. Каждый  блок в P-фрейме может идти  с вектором и разностью коэффициентов  ДКП от соответствующего блока последнего раскодированного I или P, или может быть закодирован как в I, если не соответствующего блока не нашлось.

И, наконец, существуют B-фреймы, которые предсказаны  из двух ближайших I или P-фреймов, одного предыдущего и другого - последующего. Соответствующие блоки ищутся в этих кадрах и из них выбирается лучший. Ищется прямой вектор, затем обратный и вычисляется среднее между соответствующими блоками в прошлом и будущем. Если это не работает, то блок может быть закодирован как в I-фрейме.

Последовательность  раскодированных кадров обычно выглядит как

I B B P B B P B B P B B I B B P B B P B ...