1 (664884), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

2.1. Базовый вейвлет – кодер изображения

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

2.1.1. Выбор вейвлетов для сжатия изображения

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

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

Прототипами базисных функций для разделимого преобразования являются функции ф(х)ф(у), ф(х)(у), (х)ф(у) и (х)(у). На каждом шаге преобразования выполняется два разбиения по частоте, а не одно. Предположим, имеем изображение размером N х N. Сначала каждая из N строк изображения делится на низкочастотную и высокочастотную половины. Получается два изображения размерами N × N / 2. Далее, каждый столбец делится аналогичным образом. В результате получается четыре изображения размерами N / 2 × N / 2: низкочастотное по горизонтали и вертикали, высокочастотное по горизонтали и вертикали, низкочастотное по горизонтали и высокочастотное по вертикали и высокочастотное по горизонтали и низкочастотное по вертикали.

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

Д.Вилласенор систематически протестировал все биортогональные блоки фильтров минимального порядка с длиной фильтров <=36. В дополнение к вышеперечисленным критериям учитывалась также чувствительность аппроксимации с низким разрешением к сдвигам функции f(x). Наилучшим фильтром, найденным в этих экспериментах, оказался сплайновый фильтр 7/9. Этот фильтр наиболее часто используется в вейвлет - изображений. В частности, в видеокодеках семейства ADV6xx применяются именно эти фильтры.

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

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

Семейство многообещающих фильтров было разработано И.Баласингамом и Т.Рамстадом. Процедура разработки заключалась в комбинировании классических методов разработки фильтров с идеями теории вейвлетов. Получившиеся фильтры значительно превосходят популярные фильтры 7/9.

2.1.2. Осуществление преобразования на границах изображения

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

2.1.3. Квантование

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

На практике обычно применяется намного более простой равномерный квантователь с «мертвой» зоной. Интервалы квантования имеют размер ^, кроме центрального интервала (возле нуля), чей размер обычно выбирается 2^ . Коэффициенту, попавшему в некоторый интервал, ставится в соответствие значение центроида этого интервала. В случае асимптотически высоких скоростей кодирования равномерное квантование является оптимальным. Хотя в практических режимах работы квантователи с «мертвой» зоной субоптимальны, они работают почти так же хорошо, как квантователи Ллой-да-Макса будучи намного проще в исполнении. Кроме того, они робастны к изменениям распределения коэффициентов в субполосе. Дополнительным их преимуществом является то, что они могут быть вложены друг в друга для получения вложенного битового потока.

2.1.4. Энтропийное кодирование

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

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

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

2.1.5. Меры искажения, взвешенные с учетом восприятия человеком

СКО (среднеквадратическая ошибка) не всегда хорошо согласуется с визуально наблюдаемой ошибкой. Рассмотрим, например, два изображения, которые полностью одинаковы, кроме небольшой области. Хотя визуально разность между этими изображениями хорошо заметна, СКО будет примерно одинаковой. Учет системы человеческого зрения в схеме сжатия является трудной задачей. Было проведено множество исследований, но в силу трудностей с математическим описанием системы зрения человека подходящей меры найдено не было. Известно, что в человеческом глазу выполняется операция многомасштабного представления изображений. Глаз более чувствителен к искажениям в низкочастотной области. Отсюда существует возможность улучшения визуального качества реконструированного изображения путем взвешивания СКО субполос в соответствии с чувствительностью глаза в различных частотных диапазонах. Веса для наиболее часто используемого фильтра 7/9 были вычислены А.Ватсоном.

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

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

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

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

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

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

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

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

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

2.3. Кодирование посредством нульдерева

Из теории кодирования с погрешностью известно, что оптимальное распределение бит достигается в случае, если сигнал поделен на субполосы, содержащие «белый» шум. Для реальных сигналов это достигается в случае неравномерной ширины субполос: в области НЧ они более узки, чем в области ВЧ. Вот почему вейвлет –преобразование обеспечивает компактность энергии.

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

2.3.1. Алгоритм Льюиса и Ноулеса

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

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

Квантование нульдеревом основано на наблюдении, что если коэффициент мал, его отпрыски на дереве зачастую тоже малы. Это объясняется тем, что значимые коэффициенты возникают вблизи контуров и текстур, которые локальны. Нетрудно увидеть, что это является разновидностью предсказания. А.Льюис и Г.Ноулес свели это предсказание к минимуму, предположив, что если какой - коэффициент незначимый, то все его потомки также будут незначимыми. Дерево или субдерево, которое содержит (по крайней мере, так предполагается) только незначимые коэффициенты, называется нульдеревом.

А.Льюис и Г.Ноулес использовали следующий алгоритм квантования вейвлет – коэффициентов. Вначале каждый узел квантуется квантователем, оптимальным для плотности распределения Лапласа. Если значение узла меньше некоторого порога, его потомки игнорируются. Эти потомки будут восстановлены декодером как нули. Иначе осуществляется переход к четырем отпрыскам узла, и процедура повторяется. Если узел не имеет отпрысков (является листом), начинает обрабатываться следующий корневой узел и т.д.

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

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

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

2.3.2. Алгоритмы Шапиро и Саида – Перельмана

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

Методы, рассмотренные ниже, свободны от этого недостатка.

Шапиро разработал элегантный метод, названный алгоритмом вложенного нульдерева (Embedded Zerotree Wavelet coder - EZW). Данный кодер основан на передаче и ненулевых данных, и карты значений. Биты, отводящиеся для кодирования карты значений, могут превалировать в общем потоке бит, особенно на низких скоростях. Однако в карте значений, порождаемой изображениями, существует очень большая избыточность, которая и используется для достижения малых скоростей кодирования. Если имеется незначащий родительский узел, то очень вероятно, что потомки также будут незначимы. Так что в большинстве случаев генерируется символ нульдерева. Если вероятность этого события p близка к 1, то количество информации p log p, содержащееся в нем, близко к нулю. Значит, среднее число бит, требующихся для кодирования карты значений, мало. Если один или более потомков незначимого узла является значимым, генерируется символ «изолированного нуля». Вероятность этого события ниже, следовательно, для кодирования требуется большее количество бит. Это плата за то, чтобы не допустить значительного искажения за счет ошибочного порождения нульдерева.

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

интерес по следующим причинам:

1) возможность точного регулирования скорости передачи;

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

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

Алгоритм Шапиро генерирует вложенный код побитовым способом. В основе метода EZW лежат следующие основные операции.

Вначале выполняется частичное упорядочивание коэффициентов по амплитуде. Оно реализуется путем сравнения величины каждого вейвлет – коэффициента (ВК) с некоторым порогом Т. Если ВК > Т, то выносится решение о том, что коэффициент значимый, в противном случае – незначимый. Сканирование производится от низкочастотных полос к высокочастотным.

Для кодирования знака и позиции всех коэффициентов используется двухбитный символ. Этот символ может быть: « ± » - знак ВК; «0» – показывает, что ВК незначащий; «корень нульдерева» - показывает, что ВК незначащий вместе со всеми ВК данной пространственной области из более высокочастотных полос. Таким образом, используется межполосная, пространственная корреляция ВК. После вычисления и передачи карты значений для значащих коэффициентов должны быть переданы биты, уточняющие их значение («карта данных»). Далее карта данных и карта значений сжимаются арифметическим кодером. В том случае, если не исчерпан ресурс скорости передачи, порог Т делится на два и процесс повторяется.

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

А.Саид и В.Перельман улучшили алгоритм EZW. Их версия кодера называется «установка подразделений в иерархических деревьях» (Set Partition In Hierarchical Trees - SPIHT). Имеется общедоступная программная реализация этого кодера, которая очень быстра. Так, сжатие изображения размером 512х512 в 100 раз занимает на компьютере Р-166 порядка 0.1 секунды. При этом качество восстановленного изображения весьма приемлемо. Вложенные кодеры обладают одной интересной особенностью: чем больше коэффициент сжатия, тем меньше время работы кодера. Это объясняется тем, что требуется осуществление меньшего числа уточнений. SPIHT превосходит EZW примерно на 0.3 -6 дБ за счет кодирования не одиночных, а параллельных нульдеревьев.

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

2.3.3. Оптимизация нульдеревьев по критерию скорость - искажение

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

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

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

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

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

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

2.4. Современные направления исследований

Характеристики

Список файлов реферата