Рекурсивный (волновой) алгоритм

Английское название рекурсивного сжатия — wavelet. На русский язык оно переводится как волновое сжатие и как сжатие с использованием всплесков. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Коэффициент сжатия варьируется в пределах 5 - 100.

Идея алгоритма заключается в том, что вместо кодирования собственно изображений сохраняется разница между среднимизначениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.

Так, два числа a _{2 i} и a _{2 i+1} всегда можно представить в виде b¹_i = =(a _{2 i} + a _{2 i+1} )/2 и b²_i =(a _{2 i} - a _{2 i+1} )/2. Аналогично последовательность a_i может быть попарно переведена в последовательность b^1,2_i.

Рассмотрим пример. Пусть мы сжимаем строку из восьми значений яркости пикселов (a_i): (220, 211, 212, 218, 217, 214, 210, 202). Получим следующие последовательности b_1i, и b_2i: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Заметим, что значения b_2i достаточно близки к 0. Повторим операцию, рассматривая b_1i как a _i. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Из (215.5, 215, 215.5, 206) получим (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана, можно считать результатом кодирования. Заметим, что мы применяли наше преобразование к цепочке только два раза. Реально можно позволить себе применение wavelet -преобразования 4-6 раз, что позволит достичь заметных коэффициентов сжатия.

Алгоритм для двумерных данных реализуется аналогично.

Если у нас есть квадрат из четырех точек с яркостями a_2i ,_2j , a_2i+1 , _2j, a_2i , _2j+1 , и a_2i+1 , a _2j+1 , то

(1)

Используя эти формулы, для изображения 512х512 пикселов получим после первого преобразования уже 4 матрицы размером 256х256 элементов (рис. 1, 2)

Исходное изображение	B^1	B^2
B^3	B^4

Рис. 1. Рис. 2.

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

Можно повторить преобразование и получить вместо первой матрицы 4 матрицы размером 128х128.

Повторив преобразование в третий раз, получим в итоге 4 матрицы 64х64, 3 матрицы 128х128 и 3 матрицы 256х256. Дальнейшее сжатие происходит за счет того, что в разностных матрицах имеется большое число нулевых или близких к нулю значений, которые после квантования эффективно сжимаются.

Методы сжатия подвижных изображений (видео)

Основной проблемой в работе с подвижными изображениями являются большие объемы данных, с которыми приходится иметь дело. Например, при записи на компакт-диск в среднем качестве на него можно поместить несколько тысяч фотографий, более 10 часов музыки и всего полчаса видео. Видео телевизионного формата требует потока данных примерно 240 Мбит/с (1,8 Гбит/мин). При этом обычные методы сжатия, ориентированные на кодирование отдельных кадров (в том числе и JPEG), не спасают положения, поскольку даже при уменьшении битового потока в 10 - 20 раз он остается чересчур большим для практического использования.

При сжатии подвижных изображений учитывается наличие в них нескольких типов избыточности, в частности:

Ø когерентность (одноцветность) областей изображения – незначительное изменение цвета изображения в его соседних пикселах;

Ø подобие между кадрами – использование того факта, что при скорости 25 кадров в секунду различие в соседних кадрах очень незначительно.

С середины 80-х гг. многие западные университеты и лаборатории фирм работали над созданием алгоритма компрессии цифрового видеосигнала. Появилось достаточно большое число внутрифирменных стандартов.

В 1992 году был представлен стандарт кодирования MPEG-I. Сейчас используется стандарт MPEG-2.

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

MPEG сжимает последовательность движущихся образов, используя корреляцию между последовательными движущимися изображениями. Создается три типа изображений: интра-изображения (I – изображения), предсказанные (P-изображения) и изображения двунаправленного предсказания (B- изображения). В MPEG каждое изображение в последовательности может быть полностью сжато с использованием алгоритма JPEG – это I- изображения. Затем процесс сравнивает последовательные I- изображения и идентифицирует часть образа, которая была перемещена. Части образа, которые не были перемещены, переносятся в промежуточное изображение с помощью памяти декодера. После этого процесс отбирает подмножество промежуточных изображений, а затем предсказывает (посредством линейной интерполяции между I-изображениями) и корректирует расположение частей образа, которые были перемещены. Эти предсказанные и скорректированные образы являются P-изображениями. Между I и P изображениями находятся B-изображения, которые включают стационарные части образа, не охваченные движущимися частями (рис. 3)

Рис. 3. Последовательность изображений при сжатии MPEG

Одним из основных понятий при сжатии нескольких изображений является макроблок - матрица пикселов 16х16 элементов (размер изображения должен быть кратен 16). Отдельные макроблоки сжимаются независимо.

Существует достаточно много алгоритмов, сжимающих статические изображения. Из них чаще всего используются алгоритмы на базе дискретного косинусного преобразования. Алгоритм сжатия отдельных кадров в MPEG похож на соответствующий алгоритм для статических изображений - JPEG. При этом к макроблокам применяется ДКП.

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

Дата добавления: 2014-01-07