Алгоритм MPEG

Алгоритм S3TC.

Алгоритм 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 и Хаффмана.

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

Это алгоритм сжатия видео, здесь используется предположение, что соседние кадры мало отличаются друг от друга. Поэтому достаточно описать лишь разницу между ними. В этом алгоритме изображение как и в 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...

Здесь 12 кадров от I до I фрейма. Это основано на требовании произвольного доступа, согласно которому начальная точка должна повторяться каждые 0.4 секунды. Соотношение P и B основано на опыте.

Чтобы декодер мог работать, необходимо, чтобы первый P-фрейм в потоке встретился до первого B, поэтому сжатый поток выглядит так:

0 x x 3 1 2 6 4 5...

где числа - это номера кадров. xx может не быть ничем, если это начало последовательности, или B-фреймы -2 и -1, если это фрагмент из середины потока.

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