<< Предыдущая Список Следующая >>


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

Введение

 

В последнее время большой интерес представляют методы сжатия изображений на основе вейвлет-преобразований [1,2,3]. Они сочетают в себе простоту реализации, хорошее визуальное качество восстановленного изображения, высокие коэффициенты сжатия, возможность представления изображения на разных уровнях разрешения. Благодаря указанным достоинствам, вейвлет-преобразование является основой нового стандарта сжатия изображений JPEG2000. В данном стандарте используется лифтинговая схема, которая позволяет с меньшими вычислительными затратами выполнять вейвлет-преобразование непосредственно во временной области. При этом, для оценивания неизвестных элементов изображения применяют разделимые интерполирующие фильтры. Применение разделимых фильтров обусловлено наличием математического аппарата для расчета вейвлет-фильтров в одномерном случае [1,4]. Единственным возможным обобщением данного математического аппарата на многомерный случай является реализация разделимых вейвлетов. Главные причины препятствующие построению неразделимых вейвлетов является сложность факторизации двумерных полиномов и отсутствие строгих критериев оптимизации вейвлет-фильтров [1,4].

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

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

Известные работы в этом направлении [2,3] для коррекции вейвлет-коэффициентов используют высокочастотную фильтрацию вычисленной низкочастотной составляющей. Однако реализацию такого высокочастотного фильтра  также сложно описать в двумерном случае. Лифтинговая схема

 

Пусть имеется конечная последовательность . Требуется представить данную последовательность меньшим числом отсчетов. Для этого разобъем  на две последовательности:

                                

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

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

Для достижения этой цели в работах [1,2,3] предлагается изменить элементы последовательности , по которым производится оценивание, на величину, зависящую от вычисленных ошибок  согласно выражению:

,

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

.                                   (1)

Восстановление последовательности выполняется в три этапа. Сначала по  и  восстанавливаются элементы  , затем по  восстанавливаются , где  - оператор оценивания неизвестных элементов с помощью интерполирующего фильтра . На последнем этапе осуществляется объединение последовательностей  и  в последовательность . Так как при оценивании ошибок  используются наблюдения , а при восстановлении оценки , то для избежания эффекта «элайзинга» [1], на коэффициенты интерполирующего фильтра накладывается условие:

.

Если для получения оценки  используется низкочастотный фильтр с коэффициентами , а обновление определяется выражением (1), то получаем биортогональное вейвлет-преобразование Коэна-Добеши-Фово [1] с коэффициентами низкочастотного фильтра .

  Способ оценивания нечетных элементов с помощью произвольных интерполирующих фильтров

 

Используя лифтинговую схему, можно конструировать различные биортогональные вейвлеты, выбирая соответствующий оператор предсказания  и оператор обновления . При этом оператор предсказания должен быть таким, чтобы минимизировалась ошибка восстановления при минимизации энтропии ошибок оценивания . На сегодняшний день не известны строгие критерии, позволяющие проводить оптимизацию оператора предсказания. Основной оценкой его эффективности является максимальная гладкость базисных функций, построенных на основе коэффициентов интерполирующего фильтра [1,4]. Данная проблема обусловливает сложность синтеза и адаптации интерполирующего фильтра . Поэтому для минимизации дисперсии ошибок оценивания  предлагается применить другой интерполирующий фильтр , на коэффициенты которого не накладывается никаких ограничений. В этом случае схема кодирования выглядит следующим образом:

                                 (2)

где  - оператор предсказания на основе интерполирующего фильтра .

Анализ выражения (2) показывает, что оценивание ошибок  выполняется на основе преобразованных элементов  . Это необходимо для того, чтобы при восстановлении в ошибки  не вносились дополнительные погрешности, и, как следствие, в восстановленное изображение.

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

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

                                 (3)

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

  Двумерный случай оценивания элементов изображения

 

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

,

 

.

 

В этих обозначениях преобразование  запишется:

,             (4)

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

Выражение (4) можно изменить, сохранив возможность полного восстановления исходного изображения:

,

где  -  матрица ошибок оценивания вычисленных по столбцам матрицы .

Элементы, стоящие в четных столбцах матрицы  (при ), будем оценивать с помощью интерполирующего фильтра  по наблюдениям :

,

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

 

Оценку элемента  будем искать в виде линейной комбинации:

.

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

.                             (5)

При стандартном подходе к кодированию изображения выражение (5) перепишется в виде:

.             (6)

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

  Адаптация низкочастотного фильтра

 

Оценки элементов последовательности  по наблюдениям  будем искать в виде:

.

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

                                   (7)

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

При этом скалярные множители  должны удовлетворять двум условиям: ; , которые для широкого класса функций потерь и ПРВ помех обеспечивает сходимость оценок  рекуррентной процедуры (7) к точке минимума . Данному условию удовлетворяет, например, последовательность .

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

                                          

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

                                   

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

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

,                         

а процедура оценки

                     (8)

 

Для сокращения объема вычислений целесообразно производные в выражении (8) заменить конечными разностями.

  Вычислительная сложность предложенного алгоритма кодирования

 

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

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

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

  Численные эксперименты

 

В качестве входных данных использовались изображения 128x128 отсчетов каждое с 256 градациями серого представленные на рис. 2. Первое тестовое изображение имеет высокие корреляционные связи между элементами. Второе имеет большое количество резких переходов и низкие корреляционные связи. 

Результаты работы алгоритмов кодирования представлены на рис. 3. По оси ординат отложены потери, по оси абсцисс  - коэффициент сжатия.

 

 

 

Анализ кривых сжатия тестовых изображений показывает выигрыш предложенного метода адаптивного оценивания для обоих тестовых изображений. При этом вычислительная сложность предложенного алгоритма на этапе восстановления в сравнении с алгоритмом основанном на лифтинговой схеме уменьшается примерно на 5%. Выигрыш в качестве восстановленного изображения при равных коэффициентах сжатия составляет от 2 до 5%. Дальнейшее развитие работы направлено на сокращение вычислительной сложности алгоритма кодирования и повышения качества восстановленного изображения.

  Заключение

 

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

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

 

Литература

 

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

2.        W. Sweldens. Nonlinear Wavelet Transform for Image Coding via Lifting.

3.        A.R. Calderbank, I. Daubechies, W. Sweldens. Wavelet Transform that Map Integers to Integers.

4.        Добеши И. Десять лекций по вейвлетам. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 464 стр.

5.        Методы компьютерной обработки изображений / Под ред. В.А. Сойфера. – М.: Физматлит, 2001. – 784 с.

6.        Васильев К.К. Крашенинников В.Р. Методы фильтрации многомерных случайных полей. – Саратов: Изд-во Сарат. ун-та, 1990. – 128 с.

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

8.        Адаптация и обучение в автоматических системах, Я.З. Цыпкин, Главная редакция физико-математической литературы изд-ва “Наука”, М., 1968, 400 стр.

 


<< Предыдущая Список Следующая >>