Технология вейвлетов

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: контрольные 9 класс, понятие культуры
| Добавил(а) на сайт: Ульяна.

Различают сжатие изображений без потерь и с потерями. Первое характеризуется незначительными коэффициентами сжатия (от 3 до 5 раз) и находит применение в телевидении, медицине, аэрофотосъемке и других приложениях. При сжатии изображения с допустимыми потерями коэффициент сжатия может достигать сотен раз. Популярность вейвлет – приобразования
(ВП) во многом объясняется тем, что оно успешно может использоваться для сжатия изображения как без потерь, так и с потерями. Так, коэффициент сжатия видеосигнала в видеокодеках семейства ADV6xx варьируется от 3 до 350 и больше раз.

Причин успешного применения несколько.

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

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

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

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

Рассмотрим основные проблемы, возникающие при сжатии изображения при помощи вейвлет – приобразования и возможные пути их решения.

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

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

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

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

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

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

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

Д.Вилласенор систематически протестировал все биортогональные блоки фильтров минимального порядка с длиной фильтров R2 код для R2 будет префиксом кода для R1 . Такие коды имеют большой практический интерес по следующим причинам:

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. Оптимизация нульдеревьев по критерию скорость - искажение