Сжатие по методу WIC (Wavelet Image Compression)

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

Под wavelet-преобразованием подразумевают множество базисных функций, которые формируют компактное описание видеосигнала. Анализ изображений, построенных на таких базисах, осуществляется по двум переменным - масштабу и сдвигу. Это позволяет разделить крупные и мелкие детали изображений, одновременно локализуя их на временной шкале. Таким образом, учитывается важное для практики обстоятельство: протяженные объекты анализируемых данных лежат в низкочастотной области спектра, а короткие - в высокочастотной. Особенностью wavelet- преобразования является возможность сжатия и восстановления видеоинформации даже для слабоконтрастных изображений.

Несомненное преимущество применения этого преобразования - возможность представлять быстро изменяющиеся сигналы в компактной форме. Подобно широко используемому быстрому преобразованию Фурье (БПФ), wavelet-преобразование (DWT) обратимо и может служить инструментом анализа характеристик сигналов (спектральный анализ и др.). В отличие от БПФ (где базисными функциями служат синусы и косинусы) wavelet-преобразования формируют родительские функции более сложной формы. Их исходный набор обеспечивает получение бесконечного числа новых форм функций. Поскольку wavelet-функции ограничены в пространстве, с их помощью можно локализовать пространственный объект с высокой степенью точности.

Непрерывное вейвлет-преобразование одномерного сигнала определяется следующим образом:

Результат преобразования - функция, зависящая от двух переменных: от координаты - x и масштаба - a .Используемая здесь функция w(x) является базисной. На каждом масштабе первоначальный базис w растягивается по горизонтали и сжимается по вертикали. Затем он сдвигается в точку x исследуемой функции и свертывается с ней. В литературе данный метод часто называют многомасштабным анализом.

Первоначальная функция f (t) может быть восстановлена с помощью формулы:

где C_χ - норма базисной функции w

Восстановление сигнала возможно, если норма определена.

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

Простейший всплеск – функция, на основе которой строится базис Хаара:

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

Рекурсивно волновое сжатие – wavelet сжатие – это сжатие с использованием всплесков. В отличие от Фурье анализа и ДКП всплески определены лишь на части области задания аргумента и могут рассматриваться как отличающиеся по масштабу и местоположению реплики единственной базовой функции, называемой порождающей или материнской функцией.

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

Так два числа a2i и a2i+1 можно представить в виде: b¹_i=( a_2i+ a_2i+1)/2 и b²_i=(a_2i - a_2i+1)/2, аналогично последовательность a_i может быть попарно переведена в последовательность b^1,2_i. Данное преобразование можно применять последовательно несколько раз к результатам предыдущего преобразования.

Для двух мерного случая (квадрата из 4-х точек с яркостями a_2i,2j, a_2i,2j+1, a_2i+1,2j, a_2i+1,2j+1) наипростейшим преобразованием может быть преобразование следующего вида:

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

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

При выполнении двумерного вейвлет-анализа с использованием преобразования Хаара для разложения изображения вначале выполняется разложение по строкам, а затем по столбцам. Результатом разложения являются 4 матрицы HH0, HL0, LH0, LL0, соответствующие фильтрации фильтром h₁(n) по строкам и столбцам, фильтром h₁(n) по строкам и фильтром h₀(n) по столбцам, фильтром h0(n) по строкам и фильтром h₁(n) по столбцам, и фильтром h₀(n) по строкам и столбцам. Далее низкочастотная матрица LL0 подвергается вейвлет разложению. Его результатом являются матрицы HH1, HL1, LH1, LL1:. Такое разложение повторяется r раз, как показано на рис. 5. Результатом разложения является набор из 3r+1 матриц уменьшающейся размерности. Каждая матрица подвергается скалярному или векторному квантованию и последующему кодированию. Выбор числа уровней квантования или шага квантования производится исходя из требуемого сжатия и соответствующего распределения битов между матрицами.

Рис. 5. Трёхуровневое вейвлет преобразования изображения

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

При дискретном вейвлет-преобразовании (ДВП) анализируется сигнал с помощью блока анализа, направляющего входной сигнал x на два фильтра с импульсными откликами h (низкочастотный) и g (высокочастотный) соответственно. После прохождения фильтров сигналы прореживаются вдвое, т.е. сигнал, содержащий N элементов, преобразуется в N / 2 – элементные выходы двух каналов. Блок анализа осуществляет один уровень прямого вейвлет преобразования.

Блок синтеза выполняет обратное преобразование. В оба канала этого блока после каждого входного отсчета вставляется нулевой отсчет.

Рис. 6. Схема ДВП разложения.

Удлиненные таким образом вдвое сигналы поступают на фильтры с импульсными откликами u и v , а затем складываются. Два канала, содержащие по N / 2 элементов каждый, объединяется в один сигнал, состоящий из N элементов. Блок синтеза осуществляет один уровень обратного вейвлет преобразования. Низкочастотный фильтр задает скейлинг-функцию (масштабирующую функцию), а высокочастотный фильтр определяет всплеск.

Результатом М-кратного пропускания коэффициентов фильтра u / v через верхний канал блока синтеза будет вейвлет или скейлинг-функция на масштабном уровне M. Схема такого процесса представлена на рис.6.

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

Алгоритм быстрого пирамидального иерархического разложения сигнала в векторы данных половинной длины позволяет получить множество коэффициентов разложения (для разрешения 1/2, 1/4, 1/8 и т. д.). Cтепень сжатия при wavelet-преобразовании зависит от необходимого разрешения.

Сегодня у специалистов не вызывает сомнения, что эти алгоритмы кодирования обладают рядом преимуществ по сравнению с алгоритмами, построенными на основе дискретного косинусного преобразования Фурье, которое используется в кодеках JPEG, MPEG-1, MPEG-2. В частности, подобное разложение применяется в новых стандартах сжатия JPEG2000 и WIC.

Квантование

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

Для решения этой задачи стандарт JPEG определяет простой механизм именуемый квантованием (quantization), представ­ляющим, в свою очередь, условное название (division). Чтобы выполнить квантование коэффициентов DCT, доста­точно просто разделить их на другое значение и округлить до ближайшего целого числа:

Квантованное значение = Округление (Коэффициент/ Значение кванта)

Чтобы обратить процесс, следует выполнить умножение:

Коэффициент = Квантованное значение х Значение кванта

При выборе в качестве значения кванта числа 20, более поло­вины коэффициентов на Рис. 7 было бы преобразовано в нули.

Рис. 8. Примеры таблиц квантования из стандарта JPEG

Рис. 9. Результаты квантования дискретных значений