10.2. Новые идеи в области сжатия изображений, связанные с вейвлет-преобразованием

Базовый вейвлет-кодер, описанный в разделе 10.1, использует общие принципы кодера с преобразованием, то есть основан на эффектах декорреляции и перераспределения энергии. Математическая теория вейвлет-преобразования позволяет создавать совершенно новые и эффективные методы сжатия. Эти методы лежат в основе алгоритмов, описываемых в разделах 10.3 и 10.5. В данном разделе покажем главные идеи этих методов.

Кодирование с преобразованием основано на том, что большая часть энергии сосредоточивается в малом количестве коэффициентов, которые квантуются в соответствии с их значением. Эта парадигма, являясь достаточно мощной, основывается на нескольких предположениях, которые не всегда верны. В частности, предполагается, что изображение порождается гауссовским источником, что не соответствует действительности. С.Маллат и Ф.Фальзон показали, как это несоответствие приводит к неверным результатам при кодировании с низкими скоростями.

Пусть - случайный вектор длиной определенный как

Здесь есть случайная целая величина, равномерно распределенная от 0 до случайная величина, с равной вероятностью принимающая значения и - независимы. Вектор имеет нулевое среднее и ковариационную матрицу с элементами

Ковариационная матрица является циркулянтной, так что преобразованием Карунена-Лоэва для нее является просто преобразование Фурье. Однако преобразование Фурье вектора очень неэффективно с точки зрения кодирования.

Энергия на частоте к будет равна Это означает, что энергия Y распределена по всей низкочастотной половине базиса Фурье и частично - по высокочастотной половине. Таким образом, преобразование Карунена-Лоэва «упаковало» энергию двух ненулевых коэффициентов в примерно коэффициентов. Конечно, было бы выгоднее кодировать Y в исходном виде, без всякого преобразования.

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

Вообще говоря, развитие идей кодирования с преобразованием заключается в снятии ограничения на линейную аппроксимацию изображения, так как оператор выбора является нелинейным. В работах Р.Девора, С.Маллата и Ф.Фальзона показано, что проблема кодирования изображения может быть эффективно решена в рамках теории нелинейной аппроксимации. Отсюда возникает и ряд различий в алгоритмах работы традиционных и вейвлет-кодеров. В случае линейной аппроксимации изображение представляется фиксированным числом базисных векторов Карунена-Лоэва. Далее, какое-то число малых коэффициентов трансформанты приравнивается к нулю. Идея нелинейной аппроксимации заключается в аппроксимации изображения путем адаптивного выбора самих базисных функций. Информация о выбранных базисных функциях хранится в бинарной карте значений и передается декодеру, как дополнительная информация. В разделе 10.3 будут описаны нульдеревья, являющиеся исключительно важной структурой данных для кодирования карты значений.

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

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

Решетчатое квантование коэффициентов, рассматриваемое в разделе 10.5, гораздо ближе по своей сути к векторному квантованию, чем к кодированию с преобразованием.

Таблица 10.1. Сравнение кодеров, описываемых в главе по отношению сигнал/шум (см. скан)

Итак, развитие идей кодирования с преобразованием заключается в основном во введении некоторого оператора выбора. Информация о выборе должна быть передана декодеру, как дополнительная информация. Она может быть в виде нульдеревьев или в виде обобщенных классов энергии. Метод «обратного оценивания распределения», предложенный К.Рамчандраном, основан на другом подходе. Считается, что дополнительная информация является избыточной и может быть получена декодером непосредственно из данных. Использование данного метода приводит к хорошим показателям кодирования.

В табл. 10.1 (см. стр.155) представлены сравнения пикового отношения сигнал/шум для кодеров, которые будут обсуждаться далее. В качестве тестовых использовались полутоновые портретные изображения размером 512 х 512.

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