5. Анализ методов сжатия при разных критериях оценки качества восстановленного изображения

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

Введение

Алгоритмы сжатия изображений можно разделить на два основных класса: алгоритмы сжатия без потерь восстановленной информации и алгоритмы сжатия с частичной потерей восстановленной информации. В случае сжатия изображений наибольший интерес представляют алгоритмы сжатия с частичной потерей информации, которые обеспечивают более высокие коэффициенты сжатия. На настоящий момент известны два наиболее широко распространенных алгоритма сжатия с потерей информации: JPEG и JPEG2000. Алгоритм JPEG имеет в своей основе дискретное косинусное преобразование (ДКП), которое применяется к неперекрывающимся блокам изображения размером 8х8 пикселов. Данный метод сжатия изображений был исследован в большом числе работ [1-3]. К основным недостаткам данного метода относятся: распад кодируемого изображения на отдельные блоки по 8х8 пикселов при больших коэффициентах сжатия; появление ложных контуров; плохое описание нестационарного во времени сигнала коэффициентами Фурье-преобразования. Для преодоления указанных недостатков был предложен новый стандарт сжатия изображений JPEG2000, основу которого составляет вейвлет-преобразование. В этом случае все изображение раскладывается по базисным вейвлет-функциям, локализованным как во временной, так и в частотной областях. Это дает возможность создавать алгоритмы быстрого вейвлет-преобразования, а также не разбивать изображение на отдельные независимые блоки. Благодаря такому подходу в вейвлет-коэффициентах образуются длинные цепочки подряд идущих нулей, которые эффективно сжимаются энтропийными кодерами.

  Вейвлет-преобразование

Суть метода состоит в разложении сигнала по базисным функциям локализованным как в пространстве, так и во времени. Это позволяет учитывать нестационарность сигнала в коэффициентах вейвлет-преобразования. Кроме того, масштабируемость базисных функций позволяет анализировать сигнал изображения с разной степенью детализации, что находит свое применение в кратномасштабном анализе (КМА) [1,3].

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

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

  Сеточный метод

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

                  (1)

где  - массив элементов изображения, взятых с шагом ;  - общее количество сеток.

Сетки  подбираются таким образом, чтобы выполнялось условие

                                                    (2)

В узлах сеток  находятся наблюдения, по которым производится оценивание неизвестных элементов (рис. 2).

Ошибки оценивания сетки  определяются как

                                                      (3)

где – оценка элемента . Погрешность восстановления данного элемента изображения

                                                   (4)

где – квантованное значение ошибки , которая определяется как

                                                           (5)

где – шаг квантования;  - округление до ближайшего целого.

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

  Сравнительный анализ вейвлет-кодера и сеточного алгоритма

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

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

Для сравнения алгоритмов сжатия использовались изображения размером 128х128 элементов с 256 градациями серого (рис. 3). В качестве меры погрешности восстановления использовалось нормированное среднеквадратическое отклонение, определяемое как

                                          (6)

где  – дисперсия погрешности оценивания;  - дисперсия сигнала изображения. Кривые сжатия тестовых изображений приведены на рис. 4.

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

                                                (7)

где  - восстановленное значение элемента изображения.

Кривые сжатия тестовых изображений с оценкой потерь (7) представлены на рис. 5. Сравнительный анализ кривых рис. 4 и рис. 5 показывает заметный выигрыш сеточного метода сжатия по сравнению с вейвлет-сжатием.

Псевдоградиентное оценивание неизвестных элементов изображения

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

    (8)

Коэффициенты  в (8) необходимо выбрать таким образом, чтобы .

Одним из методов определения коэффициентов , минимизирующие функционал  является процедура рекуррентного градиентного оценивания [4], имеющая следующий вид:

                                            (9)

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

Реализация рассмотренного метода сложна в вычислительном плане, т.к. на каждом шаге нужно пересчитывать . Значительно меньшего объёма вычислений требуют псевдоградиентные (ПГ) алгоритмы [5] вида:

                             (10)

где  некоторое случайное направление, удовлетворяющее условию псевдоградиентности:

                                            (11)

где «» – знак скалярного произведения векторов, т.е.  в среднем составляет острый угол  с истинным градиентом .

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

                                (12)

Процедура оценки принимает вид:

                          (13)

  Сравнительный анализ сеточных методов кодирования изображений

Оценим эффективность представленного алгоритма оценивания неизвестных элементов по сравнению с фильтром Кламана, который дает оптимальные оценки для  тестовых изображений рис. 3а) и рис. 3б), а также с интерполирующим фильтром с заданными коэффициентами.

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

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

  Список литературы

1. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования., ВУС, 1999. С. 1-204.

2. Зелов С. Стандарт JPEG-кодирование неподвижных изображений Компьютер Пресс №5, 1997 с. 82-84.

3. Д.С. Ватолин. Алгоритмы сжатия изображений www.useic.ru\~dv\ fractal\index.htm.

4. Уидроу Б., Стирнз С. Адаптивная обработка сигналов: Пер. с англ. – М.: Радио и связь, 1989. – 440 с.: ил.

5. Прикладная теория случайных процессов и полей / Васильев К.К., П 75 Драган Я.П., Казаков В.А. и др.; Под ред. Васильева К.К., Омельченко В.А. Ульяновск: УлГТУ, 1995. 256 с.

Наместников Сергей Михайлович, 1978 г.р., аспирант каф. «Системы автоматизированного проектирования» Ульяновского государственного технического университета. Год окончания ВУЗа – 2001. Направление научных исследований: Статистические методы обработки изображений.

Васильев Константин Константинович, 1948 г.р., д.т.н., профессор, зав. каф. «Системы автоматизированного проектирования» Ульяновского государственного технического университета. Закончил Ленинградский электротехнический институт в 1972 г. Направление научных исследований: статистический анализ случайных полей заданных на многомерных сетках. Год защиты докторской диссертации – 1985.