Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов сжатия изображений 9
1.1. Постановка задачи 9
1.2. Методы сжатия без потерь 10
1.2.1. Арифметический алгоритм, коды Шеннона-Фэно и Хаффмена 10
1.2.2. Сравнительный анализ статистических методов сжатия 12
1.3. Методы дифференциальной импульсной кодовой модуляции и иерархической сеточной интерполяции 13
1.3.1. Дифференциальная импульсная кодовая манипуляция 14
1.3.2. Метод иерархической сеточной интерполяции 15
1.3.3. Сравнительный анализ методов сжатия, основанных на оценивании элементов изображения 20
1.4. Применение ортогональных разложений для сжатия изображений 22
1.4.1. Преобразование Адамара 23
1.4.2. Преобразование Карунена-Лоэва 25
1.4.3. Дискретное косинусное преобразование 26
1.4.4. Сравнительный анализ методов кодирования с преобразованием 28
1.5. Сжатие изображений на основе вейвлет-преобразований 31
1.5.1. Базисные вейвлет-функции 31
1.5.2. Кратномасштабный анализ 35
1.5.3. Преобразование Хаара. Декомпозиция изображения 36
1.5.4. Сравнительный анализ вейвлет-преобразований 39
1.6. Сравнительный анализ методов сжатия на основе иерархической сеточной интерполяции и вейвлет-преобразования 40
1.7. Выводы 42
ГЛАВА 2. Сжатие изображений на основе метода иерархической сеточной интерполяции 44
2.1. Постановка задачи 44
2.2. Структура сеточного алгоритма сжатия 45
2.3. Оптимальное калмановское оценивание в алгоритме иерархической сеточной интерполяции 51
2.4. Псевдоградиентное оценивание в алгоритме иерархической сеточной интерполяции 55
2.5. Сравнительный анализ сеточных методов 60
2.6. Выводы 70
ГЛАВА 3. Сжатие изображений на основе лифтинговой схемы 72
3.1. Постановка задачи 72
3.2. Лифтинговая схема 73
3.3. Отличия лифтинговой схемы от сеточного метода 79
3.4. Коррекция вейвлет-коэффициентов на основе двумерных интерполирующих фильтров 84
3.5. Структура вейвлет-кодера с коррекцией вейвлет-коэффициентов 87
3.6. Сравнительный анализ алгоритмов сжатия на основе вейвлет-преобразования и сеточного метода 93
3.7. Выводы 100
ГЛАВА 4. Особенности программной реализации алгоритмов сжатия 102
4.1. Постановка задачи 103
4.2. Особенности программной реализации при сжатии изображений разными методами 103
4.3. Особенности работы алгоритмов кодирования на границах изображений 106
4.4. Особенности реализации псевдоградиентных алгоритмов оценивания 108
4.5. Применение предложенных алгоритмов 111
4.6. Выводы 112
Заключение 113
Библиографический список 115
Приложение №1. Описание стандарта JPEG 128
- Сравнительный анализ методов сжатия, основанных на оценивании элементов изображения
- Сравнительный анализ методов сжатия на основе иерархической сеточной интерполяции и вейвлет-преобразования
- Оптимальное калмановское оценивание в алгоритме иерархической сеточной интерполяции
- Коррекция вейвлет-коэффициентов на основе двумерных интерполирующих фильтров
Введение к работе
Актуальность темы. В последние годы быстро развиваются системы передачи, обработки и хранения изображений и видеопоследовательностей. Эффективным способом сокращения интенсивности цифрового потока является сжатие передаваемых данных с последующим восстановлением на принимающей стороне. Известные методы сжатия без потерь, как правило, показывают низкую эффективность при работе с изображениями. Поэтому целесообразно применять методы сжатия с потерей информации, которые позволяют достигать более высоких коэффициентов сжатия при сохранении хорошего качества восстановления.
На основе проведенного анализа работ по сжатию изображений можно выделить алгоритмы кодирования, ориентированные на преобразование стационарных и нестационарных сигналов. Для стационарных сигналов наибольшее распространение получил метод сжатия на основе дискретного косинусного преобразования. Он показывает хорошие результаты для кодирования квазипериодических сигналов. Описание нестационарных сигналов целесообразно выполнять с помощью вейвлет-преобразования, позволяющего получить высокие коэффициенты сжатия для сигналов, которые описываются кусочно-полиномиальными функциями. Обобщение методов Фурье и вейвлет-преобразований для обработки двумерных сигналов приводит к известным разделимым преобразованиям. Они обладают выраженной анизотропией, связанной с искусственно введенными координатными осями при построении разделимых алгоритмов кодирования. Однако пространственные свойства большинства реальных изображений изотропны, характерной для разделимых порождающих фильтров. В связи с этим является актуальной задача повышения эффективности кодирования широких классов изображений за счет использования неразделимых алгоритмов.
Цель работы. Целью работы является разработка и моделирование алгоритмов сжатия изображений, обладающих малой вычислительной
сложностью и обеспечивающих высокие коэффициенты сжатия за счет применения двумерных неразделимых преобразований. Для достижения названной цели необходимо решить следующие задачи.
Провести сравнительный анализ известных алгоритмов кодирования изображений.
Разработать алгоритмы сжатия на основе метода иерархической сеточной интерполяции с использованием двумерных неразделимых преобразований как для известных моделей изображений, так и для реальных в условиях априорной неопределенности.
Синтезировать улучшенные алгоритмы сжатия на основе вейвлет-преобразований с использованием двумерных неразделимых фильтров, для широких классов реальных квазиизотропных изображений.
Провести статистическое моделирование известных и разработанных алгоритмов сжатия. Определить класс изображений, для которых целесообразно применять предложенные алгоритмы, а также изучить особенности их программной реализации.
Осуществить программную реализацию предложенных алгоритмов сжатия с возможностью их модификации для различных прикладных задач.
Методы исследования базируются на теории вероятностей, теории случайных процессов и полей, математической статистике. При разработке программного обеспечения применялись численные методы, методы объектно-ориентированного программирования в среде Microsoft Visual C++.
Научная новизна. В диссертации получены следующие новые научные результаты.
Предложен сеточный алгоритм на основе адаптивной псевдоградиентной процедуры, обеспечивающий большие на 2-5% коэффициенты сжатия для типовых реальных изображений по сравнению с алгоритмом на основе векторного фильтра Калмана.
С помощью статистического моделирования установлено, что для однородных изотропных случайных полей алгоритм сжатия на основе
псевдоградиентной процедуры имеет выигрыш 3-8% по величине коэффициентов сжатия по сравнению с алгоритмом на основе фильтра Калмана.
Предложен алгоритм сжатия на основе вейвлет-преобразования с коррекцией вейвлет-коэффициентов с помощью двумерного неразделимого фильтра, обеспечивающий большие на 3-7% коэффициенты сжатия для типовых реальных изображений по сравнению с аналогичным вейвлет-кодером без коррекции коэффициентов.
Статистическое моделирование алгоритма кодирования на основе вейвлет-преобразования с коррекцией вейвлет-коэффициентов показало, что наибольший выигрыш 5-10% коэффициентов сжатия по сравнению с алгоритмами JPEG и JPEG2000 достигается для однородных изотропных случайных полей.
Проведенное исследование сеточного алгоритма на основе псевдоградиентной процедуры показало проигрыш 2-3% коэффициентов сжатия для имитированных случайных полей с известными разделимыми экспоненциальными корреляционными функциями по сравнению с алгоритмом на основе фильтра Калмана.
Практическая значимость. Представлено конкретное описание двух классов алгоритмов сжатия изображений, допускающее их непосредственное использование при проектировании современных и перспективных систем передачи и обработки изображений. Структура разработанных алгоритмов сжатия изображений предоставляет разработчикам возможность эффективной программно-аппаратной реализации на различных типах вычислительных систем. Предложенные способы кодирования изображений могут быть использованы в системах хранения больших объемов графической информации, где нет сильных ограничений на скорость сжатия. Результаты диссертационной работы внедрены в учебный процесс.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих НТК:
III-IV Всероссийские научно-практические конференции «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2001 г., 2004 г.);
Международная научно-техническая конференция «Телевидение: передача и обработка изображений» (Санкт-Петербург, 2002, 2003 гг.);
LVII- LVIII научные сессии, посвященные Дню радио (Москва, 2002, 2003 гг.);
VI-VII Международная конференция «Распознавание образов и анализ изображений» (В. Новгород, 2002 г.; С. Петербург, 2004 г.);
V-VI Международные конференции и выставки «Цифровая обработка сигналов и ее применение» (Москва, 2003, 2004 гг.);
ежегодные конференции профессорско-преподавательского состава Ульяновского государственного технического университета (2001-2004 гг.).
Содержание работы. В первой главе представлен анализ известных работ в области сжатия изображений. Описаны алгоритмы сжатия без потерь и с потерей информации. Представлены сравнительные характеристики сжатия разных классов алгоритмов для четырех тестовых изображений. Рассмотрены классические методы кодирования сигналов на основе преобразований Фурье, Карунена-Лоэва, Адамара. Приведены результаты сжатия тестовых изображений на основе данных преобразований. Описаны алгоритмы кодирования ДИКМ и иерархической сеточной интерполяции, основанные на оценивании неизвестных элементов изображения. Большое внимание уделено методу кодирования на основе вейвлет-преобразования. Рассмотрено ортогональное вейвлет-преобразование Хаара и биортогональное вейвлет-преобразование, используемое в стандарте сжатия JPEG2000. Представлены сравнительные характеристики сжатия разных вейвлет-преобразований.
Вторая глава посвящена разработке и исследованию алгоритмов иерархической сеточной интерполяции с разными операторами оценивания элементов изображения. Приведено описание сеточного алгоритма для случайных полей, заданных авторегрессионными уравнениями первого порядка
на основе оптимального фильтра Калмана. Описан алгоритм кодирования на
основе процедуры псевдоградиентного оценивания для изображений с
неизвестными статистическими характеристиками. Представлены
сравнительные характеристики предложенных алгоритмов.
В третьей главе представлен алгоритм сжатия на основе вейвлет-преобразования с коррекцией вейвлет-коэффициентов двумерными неразделимыми фильтрами. Описаны основные отличия алгоритмов сжатия на основе вейвлет-преобразования и сеточного метода. Представлены сравнительные характеристики вейвлет-преобразования с сеточным методом.
Четвертая глава посвящена вопросам практической реализации предложенных алгоритмов сжатия. Приведено описание разработнных соискателем программных пакетов для алгоритмов на основе вейвлет-преобразования и иерархической сеточной интерполяции. Рассмотрены алгоритмы обработки границ изображений при разных методах сжатия. Описаны особенности реализации псевдоградиентных процедур. Приведены результаты обработки имитированных и реальных изображений описанными алгоритмами кодирования.
Сравнительный анализ методов сжатия, основанных на оценивании элементов изображения
В задачах передачи, обработки и хранения изображений большое значение приобретают методы сжатия данных. Это связано, прежде всего, с тем, что данные в таких системах, как правило, составляют интенсивные цифровые потоки. Поэтому даже незначительное сокращение информации позволит увеличить объем передачи и хранения данных. В этом случае качество работы алгоритмов сжатия непосредственно сказывается на эффективности применения систем. При этом основная доля обрабатываемой информации приходится на изображения и видеопоследовательности. В связи с этим весьма важной представляется задача анализа существующих методов сжатия изображений. При этом, учитывая дискретный характер большинства современных систем передачи, хранения и обработки информации, целесообразно ограничить обзор цифровыми методами обработки данных.
Для решения поставленной задачи в п. 1.2. проводится анализ методов сжатия без потерь информации, которые могут быть применены к любым типам данных. В п. 1.3. рассматриваются такие методы как дифференциальная импульсная кодовая модуляция (ДИКМ) и метод иерархической сеточной интерполяции (ИСИ), ориентированные на сжатие изображений. Алгоритмы сжатия на основе унитарных преобразований рассмотрены в п. 1.4. В п. 1.5. представлены алгоритмы сжатия на основе вейвлет-преобразований. Сравнительный анализ методов на основе вейвлет-преобразования и ИСИ приведен в п. 1.6.
Методы сжатия без потерь включают в себя два основных этапа: статистическое моделирование и кодирование. На этапе статистического моделирования производится оценивание вероятности появления символов в кодируемом сообщении [23, 80, 82, 83]. На этапе кодирования входным данным ставятся в соответствие коды переменной длины, исходя из вычисленной статистики, таким образом, чтобы короткие коды соответствовали наиболее вероятным значениям символов, а длинные менее вероятным.
На сегодняшний день известно несколько подходов к оцениванию статистики источника сообщений [25, 82, 83]. В самом простом случае предполагается, что статистика известна априори и может быть использована при построении кодов переменной длины. Преимуществом такого подхода является простота реализации и возможность восстановления информации без передачи на приемную сторону таблицы вероятностей появления символов в сообщении. Во втором случае статистика сообщения формируется на основе кодируемых данных [82]. Сформированная статистика передается кодеру, на основе которого осуществляется сжатие данных. Недостатком такого подхода является необходимость передачи на приемную сторону вычисленной статистики. Третий подход состоит в адаптивном построении статистики сообщения в процессе кодирования [82]. Особенностью такого метода является то, что статистика вычисляется динамически во время кодирования. При этом на приемную сторону нет необходимости передавать дополнительную информацию, т.к. она может быть вычислена по сжатым данным.
Одним из первых методов кодирования информации основанный на статистике исходных данных стал алгоритм Шеннона-Фэно [25, 80]. Работа алгоритма начинается с разделения кодируемых символов на две приблизительно равновероятные группы. Первой группе символов ставится в соответствие 0, для второй группы, - 1. Далее каждая группа снова разделяется на две приблизительно равновероятные подгруппы. Для символов первой подгруппы добавляется код 0, для второй, - код 1, и.т.д.
Другим примером построения кодов переменной длины является алгоритм Хаффмена [83]. Работа алгоритма начинается с формирования последовательности символов сообщения в порядке возрастания или убывания вероятности их появления. Затем последовательно объединяются в два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. Таким образом, строится дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него. Результирующий код представляется цепочкой бит, записанных от корня дерева до его соответствующего листа.
Алгоритм сжатия по Хаффмену приводит к лучшим результатам, в случаях, когда вероятности появления символов в сообщении - целые отрицательные степени двойки.
При произвольной статистике кодируемого сообщения хорошие результаты показывает арифметический алгоритм [82], который способен достигать нижней энтропийной границы. Основная идея арифметического кодирования состоит в представлении символов входного потока вещественными интервалами в диапазоне от 0 до 1. Процесс кодирования начинается с уменьшения интервала [0,1) в соответствии с вероятностью появления кодируемого символа в сообщении. При появлении очередного символа процесс повторяется, сужая все больше и больше исходный интервал. Полученный интервал единственным образом описывает исходное сообщение и может быть использован для однозначного восстановления информации.
Сравнительный анализ методов сжатия на основе иерархической сеточной интерполяции и вейвлет-преобразования
В предыдущем разделе предполагалось, что модель кодируемого изображения соответствует авторегрессии первого порядка. В большинстве реальных случаев модель изображения, как правило, известна не полностью. Поэтому рассмотренные алгоритмы оценивания не всегда будут приводить к желаемым результатам. В связи с этим становятся актуальными вопросы построения хороших оценок, в смысле минимума дисперсии ошибок, в условиях априорной неопределенности.
Оптимальная оценка xtJ должна минимизировать функционал Аналитическое вычисление коэффициентов а фильтра (2.1) из условия минимума J (а) возможно для изображений с известной корреляционной функцией. Кроме того, коэффициенты корреляции могут меняться в пространстве. В связи с этим целесообразно вычислять коэффициенты интерполирующего фильтра а непосредственно по имеющимся наблюдениям. Существуют известные подходы для нахождения параметров а , например, метод моментов [25], состоящий в том, что оценки измеряемых параметров выбираются так, чтобы теоретические значения нескольких моментов оказались равными их выборочным значениям. Однако в этом случае коэффициенты фильтра должны быть выражены через коэффициенты корреляции, что в общем случае сделать сложно. Другим способом минимизации функционала J(a) является градиентный метод [68, 95, 102]. В этом случае процедура рекуррентного оценивания имеет вид: где ап+1 - очередное за ап приближение к точке минимума ап\ VJ{cc) градиент функционала J(cc); jun - положительная числовая последовательность, влияющая на длину шагов процедуры (2.10); а0 начальное приближение. Применению данных методов в обработке изображений препятствует необходимость многократных и громоздких вычислений VJ(a), каждое из которых обычно включает в себя обработку всех отсчетов изображения. Значительно сократить объем вычислений можно, если вместо VJ(a) взять его усечение VQ{a). В результате вместо значения градиента будет использоваться его значение со случайной ошибкой 5п. Однако при центрировании ошибки М\дп}=0 процедура итерационного поиска имеет вид ««+1 =«„ -Mn Qific») Дальнейшего уменьшения вычислительной сложности можно достичь путем замены градиента VQ(a) на псевдоградиент [68]: где Рп - некоторое направление, удовлетворяющее условию псевдоградиентности [70]: где «» - знак скалярного произведения векторов. Условие (2.12) гарантирует, что направление J3n, в среднем, будет составлять острый угол с градиентом. В работе [64] был предложен псевдоградиент Д, = sign в себе хорошие результаты построения прогноза элементов изображения, устойчивость к резким изменениям вектора наблюдения и высокое быстродействие. Псевдоградиентная процедура оценивания коэффициентов интерполирующего фильтра а в этом случае принимает вид: Таким образом, при поиске коэффициентов а необходимо просмотреть все элементы в направлении развертки и для каждого оцениваемого значения элемента выполнить шаг процедуры (2.13). Сходимость оценки обеспечивается за счет постепенного уменьшения параметра цп при увеличении п. Для нестационарных сигналов может существовать множество локальных оптимумов, тогда полученная оценка будет зависеть от выбора начального приближения а0. Определение такого значения вектора а0, при котором процедура (2.13) достигнет наилучшего приближения, является сложной задачей. В работе [49] показано, что при обработке изображения с плавной неоднородностью алгоритм (2.13) дает результаты, сравнимые с потенциально достижимыми. Например, если коэффициент корреляции между соседними элементами в левом верхнем углу изображения размеров 128x128 равен 0.8, а в правом нижнем 0.95, то СКО ошибки прогноза на 5-10% больше по сравнению с оптимальным прогнозом при известных коэффициентах корреляции. Вычисленные коэффициенты а необходимо передать на приемную сторону для восстановления изображения. Сократить объем служебной информации можно, например, если положить коэффициенты интерполирующего фильтра симметричными относительно оцениваемого элемента. Для вычисления оценок (2.1) необходимо определить область локальных состояний D. Очевидно, область D нужно выбирать так, чтобы она содержала ближайшие от оцениваемого элемента наблюдения и обеспечивала высокую точность оценивания при небольшом числе арифметических операций. При этом наблюдения целесообразно располагать симметрично относительно оцениваемого элемента, т.к. это позволит вдвое сократить число коэффициентов фильтра, необходимых для передачи на приемную сторону для восстановления изображения. Исходя из данных положений, хорошим выбором при оценивании элементов хи+1 и xl+2j+x является область D, приведенная на рис. 2.7, а. Область D для оценивания элементов xMj и xMJ+2 с учетом увеличения числа наблюдений zjJ+x и zi+2J+l, представлена на рис. 2.7, б. Оценка центрального отсчета xi+lJ+i строится по всем восьми наблюдениям (рис. 2.7, в). Такой порядок восстановления элементов изображения позволяет уменьшить дисперсию ошибок оценивания и увеличить коэффициент сжатия.
Оптимальное калмановское оценивание в алгоритме иерархической сеточной интерполяции
Другим методом кодирования является разложение сигнала по базисным функциям. Среди известных методов преобразований для сжатия реальных изображений наиболее перспективным является вейвлет-преобразование, которое может быть реализовано на основе набора низко- и высокочастотных фильтров. Свертку входного сигнала с коэффициентами фильтров можно представить как скалярное произведение векторов, по которым производится разложение, а результат - как проекции входного сигнала на соответствующие базисные функции. Однако при таком представлении вейвлет-преобразования сложно выполнять синтез вейвлет-фильтров, учитывать краевые эффекты, выполнять неравномерную декомпозицию кодируемого изображения. Синтез алгоритмов сжатия на основе вейвлет-преобразования проще осуществлять с помощью лифтинговой схемы, которая описывает вейвлет-преобразование во временной области. Это дает возможность объединить преимущества методов ИСИ и вейвлет-преобразования при синтезе алгоритма кодирования. Вместе с тем лифтинговая схема представляет разделимое преобразование, которое обладает выраженной анизотропией, связанной с искусственно введенными координатными осями. Однако пространственные свойства большинства реальных изображений изотропны.
Таким образом целью данной главы является повышение коэффициента сжатия широких классов изображений за счет применения неразделимых преобразований в лифтинговой схеме кодирования.
В данном параграфе представлены новые идеи, лежащие в основе конструирования вейвлетов во временной области. Данный метод позволяет создавать вейвлеты второго поколения, не являющиеся растяжением и сдвигами только одной функции [26, 138-143]. Кроме того, лифтинговая схема позволяет конструировать различные биортогональные вейвлеты путем выбора соответствующих операторов оценивания и обновления [26].
Пусть имеется дискретный сигнал fin). Обозначим его отсчеты через Л0к = f(k), к є Z. Требуется представить этот сигнал меньшим числом коэффициентов, что эквивалентно увеличению интервала дискретизации. В этом случае получить точное восстановление сигнала не всегда возможно. Поэтому необходимо стремиться к уменьшению разницы между исходным и восстановленным сигналами в соответствии с выбранной мерой. Очевидно, качество восстановления будет зависеть от способа разбиения кодируемого сигнала. Например, можно уменьшить число коэффициентов A0jc, оставив четные отсчеты. В результате получается новая последовательность где отрицательный индекс используется для обозначения последовательности меньшей длины. Если нечетные отсчеты сохранить в последовательности у_хк = Я02к+1, то восстановление исходной последовательности возможно путем объединения коэффициентов Я_и с коэффициентами у_и, которые называются вейвлет коэффициентами. Данный пример показывает, что ни на способ разбиения последовательности данных, ни на размеры субпоследовательностей не налагается никаких ограничений. Единственным требованием является наличие процедуры, позволяющей восстановить {л0к} по {я_{к} и {r_u}. Наиболее простой возможностью разбиения является деление отрезка сигнала пополам. Однако при кодировании реальных полутоновых изображений, деление на четную и нечетную части предпочтительнее, так как эти последовательности, как правило, более коррелированы между собой. Для получения обратимого компактного представления исходного сигнала нужно стремиться, чтобы вейвлет-коэффициенты были малы. Этого можно достичь путем оценивания нечетных элементов последовательности Я0А на основе наблюдений Д_и. Тогда коэффициенты у_;к можно заменить разностью между истинным значением нечетного элемента {\к} и его оценкой Р(Л_ик): Вейвлет-коэффициенты у_хк показывают, насколько исходный сигнал не соответствует модели, на основе которой построен оператор оценивания Р. При этом, если сигнал коррелирован, то значения большинства вейвлет-коэффициентов будут малы. При соответствующем выборе оператора Р, заменяя исходный сигнал меньшими последовательностями я_м] и { -_, А}, получим обратимое компактное представление сигнала. В случае, если исходный сигнал описывается кусочно-линейной функцией вида f(x) = ax на интервалах [к,2к],к є Z, то для оценивания нечетных элементов целесообразно выбрать оператор Р(Я_1к) = \ll(x_lk +Я_и+1). При этом значения вейвлет-коэффициентов, определенные по формуле (3.1), будут равны нулю. В общем случае полагают [139-141], что сигнал реальных изображений на интервалах [к,2к],к є Z лучше описывать с помощью полиномов. Соответственно, оператор оценивания Р позволяет вычислить полиномиальную оценку неизвестных элементов по множеству неполных наблюдений {л_1к}. Последовательность {я_и}, представляющая четные элементы {\к), также можно разбить на две последовательности {я_2к} и {г_2,Л- После выполнения п итераций исходный сигнал оказывается разложенным в вейвлет-базис \я_„к,у_пк,...,у_Хк\. Так как вейвлет-коэффициенты представляют собой ошибки оценивания, то последовательность их квантованных значений, как правило, имеет малую энтропию и эффективно кодируется методами сжатия без потерь.
Обозначим через N количество отсчетов, на основе которых строится оценка нечетных элементов. Тогда для кусочно-линейной аппроксимации N = 2, для кубической N = 4 и т.д. В общем случае N показывает гладкость интерполяционной функции р, применяемой для вычисления вейвлет-коэффициентов. Функция ф называется дуальным вейвлетом, а N - число дуальных нулевых моментов:
На рис. 3.1. показан процесс, называемый интерполяционным подразделением, для линейной и кубической интерполяции. Несмотря на то, что на каждом шаге схемы используется кубический полином, предельная функция в общем случае не будет полиномиальной. Предположим, что исходный сигнал - отсчеты кубического полинома. В этом случае интерполяционный полином, проходящий через четыре точки, будет тем же самым полиномом, и все вновь порождаемые отсчеты будут принадлежать ему, в пределе воспроизводя его. Таким образом, используя N отсчетов, можно строить полином степени N-1. Так как оператор оценивания Р основан на полиномиальной интерполяции, то чем выше порядок функции ф, тем лучше аппроксимация коэффициентов у на основе коэффициентов к.
Коррекция вейвлет-коэффициентов на основе двумерных интерполирующих фильтров
Предложенный алгоритм на основе коррекции вейвлет-коэффициентов показывает выигрыш коэффициентов сжатия на 5-10% при квадратичной функции потерь по сравнению с сеточным методом. При этом представляется важной задача определения классов изображений, для которых может быть получен наибольший выигрыш и наибольший проигрыш данного алгоритма по сравнению с известными алгоритмами JPEG и JPEG2000. Для этого выберем тестовые изображения (рис. 2.11).
Результаты статистического моделирования представлены на рис. 3.13. Здесь по оси абсцисс отложен коэффициент сжатия, по оси ординат - потери, вычисленные по формуле (1.3).
Анализ результатов статистического моделирования для стационарных тестовых изображений показывает выигрыш по величине коэффициентов сжатия на 5-7% вейвлет-кодера с коррекцией вейвлет-коэффициентов по сравнению с алгоритмом JPEG2000 для волновой модели изображения. Это связано с лучшим построением оценки неизвестных элементов с помощью двумерных неразделимых фильтров, в отличии от алгоритмом JPEG и JPEG2000, которые используют разделимые преобразования при анализе и синтезе кодируемого сигнала. Лучшие результаты коэффициентов сжатия на 3-5% показывает алгоритм MrSID по сравнению с вейвлет-кодером с коррекцией вейвлет-коэффициентов.
Для случайных полей Хабиби применение неразделимых фильтров не приводит к заметному выигрышу, т.к. хорошая оценка может быть получена с помощью разделимых фильтров. Промежуточные результаты сжатия получаются для модели изображения с кратными корнями.
Помимо свойств, связанных с изотропностью, выделим неоднородные случайные поля представленые на рис. 2.14. Результаты статистического моделирования показаны нарис. 3.14.
Анализ результатов статистического моделирования для неоднородных тестовых изображений, также как и для однородных, показывает лучшие на 2-3% результаты сжатия вейвлет-кодера с коррекцией вейвлет-коэффициентов для волновой модели изображения по сравнению с алгоритмом JPEG2000. Это связано с гладкостью и изотропным характером синтезированного изображения, для которого двумерные неразделимые фильтры лучше учитывают корреляционные зависимости между соседними элементами. Лучшие на 2-4% результаты показывает алгоритм MrSID по сравнению с вейвлет-кодером с коррекцией вейвлет-коэффициентов. Сравнительный анализ сжатия однородных и неоднородных случайных полей показывает лучшие результаты предложенного алгоритма для однородных изображений. Таким образом, наибольшие коэффициенты сжатия могут быть получены для однородных изотропных случайных полей. 1. Предложен алгоритм сжатия на основе вейвлет-преобразования с коррекцией вейвлет-коэффициентов с помощью двумерного неразделимого фильтра, обеспечивающий большие на 3-7% коэффициенты сжатия для типовых реальных изображений по сравнению с аналогичным вейвлет-кодером без коррекции коэффициентов. 2. Проведенные исследования алгоритма сжатия на основе вейвлет преобразования с коррекцией вейвлет-коэффициентов показали, что для изотропных однородных случайных полей коэффициенты сжатия на 2-3% выше, чем для неоднородных анизотропных случайных полей при равных потерях. 3. Алгоритм сжатия на основе иерархической сеточной интерполяции обеспечивает большие коэффициенты сжатия на 10-20% по критерию минимума максимальной ошибки по сравнению с вейвлет-кодером. При квадратической функции потерь большие коэффициенты сжатия на 5-10% позволяет достичь алгоритм кодирования на основе вейвлет-преобразования по сравнению с алгоритмом на основе иерархической сеточной интерполяции. 4. Сравнительный анализ реконструкции сжатых изображений показал, что визуальное качество восстановленных изображений сжатых на основе вейвлет-кодера выше по сравнению с визуальным качеством восстановления изображений на основе сеточного метода. В предыдущих разделах решены задачи синтеза различных алгоритмов сжатия на основе сеточных методов и вейвлет-преобразования с использованием лифтинговой схемы для разных моделей изображений и при разных критериях качества оценки потерь. Предложенные алгоритмы выгодно отличаются от известных по степени сжатия при сохранении величины потерь и вычислительной скорости восстановления сжатого изображения. Вместе с тем, практическое применение разработанных алгоритмов имеет ряд особенностей, связанных с наличием границ кадров реальных изображений, объемом памяти ЭВМ, конечной точностью представления вещественных величин при реализации на ЭВМ и ограничениями по скорости выполнения операций. Исследованию этих особенностей построения реальных систем кодирования изображения и посвящен настоящий раздел. В п. 4.2 представлено описание разработанных программных пакетов для сжатия изображений размером 128x128 отсчетов с 256 градациями серого для сеточных методов и вейвлет-кодеров. В п. 4.3 рассмотрены вопросы построения обработки границ изображения сеточными методами и вейвлет-кодерами на основе лифтинговой схемы, выполнение целочисленного преобразования сеточных методов, удобных для реализации на ЭВМ. В п. 4.4 проанализированы вопросы особенности реализации псевдоградиентных алгоритмов оценивания элементов изображения. В п. 4.5 приведены результаты обработки имитированных и реальных изображений различными алгоритмами кодирования.
Похожие диссертации на Разработка и моделирование алгоритмов сжатия изображений на основе неразделимых преобразований
