Сжатие с использованием вейвлет

Сжатие с использованием вейвлет

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

Существенную роль в алгоритмах вейвлетной компрессии играет концепция представления результатов вейвлет-разложения в виде нуль-дерева (zero-tree).

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

Суть метода

Вейвлетная компрессия в современных алгоритмах компрессии изображений позволяет значительно (до двух раз).[источник не указан 817 дней] повысить степень сжатия чёрно-белых и цветных изображений при сравнимом визуальном качестве по отношению к алгоритмам предыдущего поколения, основанным на дискретном косинусном преобразовании, таких, например, как JPEG.

Для работы с дискретными изображениями используется вариант вейвлет-преобразования, известный как алгоритм Малла, названный в честь его изобретателя Стефана Малла́ (фр. Stephane Mallat). Исходное изображение раскладывается на две составляющие — высокочастотные детали (состоящие в основном из резких перепадов яркости), и сглаженную уменьшенную версию оригинала. Это достигается применением пары фильтров, причём каждая из полученных составляющих вдвое меньше исходного изображения. Как правило, используются фильтры с конечным импульсным откликом, в которых пикселы, попавшие в небольшое «окно», умножаются на заданный набор коэффициентов, полученные значения суммируются, и окно сдвигается для расчёта следующего значения на выходе. Между вейвлетами и фильтрами есть тесная связь. Вейвлеты непосредственно не фигурируют в алгоритмах, но если итерировать соответствующие фильтры на изображениях, состоящих из единственной яркой точки, то на выходе будут все отчётливей проступать вейвлеты.

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

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

Федеральное бюро расследований (ФБР), США, ввело стандарт на вейвлетное сжатие изображений отпечатков пальцев. Впрочем, свобода выбора фильтров может оказаться очень полезной в задаче сжатия: алгоритмы, основанные на принципе «наилучшего базиса», подбирают оптимальный фильтр для отдельных участков изображения, а алгоритмы, использующие вейвлет-пакеты, достигают эффективного представления деталей, варьируя глубину фильтрации на разных участках.

Сжатие видеопоследовательностей

Ещё одна проблема состоит в том, как эффективно использовать схожесть последовательных кадров при сжатии видео. В ранних алгоритмах, таких как Motion JPEG, этот фактор игнорировался, и кадры сжимались индивидуально. MPEG использует алгоритм сравнения блоков, который старается выделить участки, изменившиеся при смене кадра. Блоки же, которые не изменились, можно не сохранять. При третьем подходе, удобном для вейвлетного сжатия, время рассматривается как третье измерение массива данных, к которому применяется алгоритм Малла. Отсутствие перемещений проявляется в обнулении соответствующих деталей по временному направлению. Наконец, надо заметить, что вейвлет-преобразование само по себе ничего не сжимает. Оно лишь осуществляет препроцессинг изображения, после которого эффективность обычных методов сжатия резко возрастает, причём даже при использовании универсальных алгоритмов и программ (таких, как LZW и pkzip), не адаптированных к конкретной задаче. Впрочем, использование методов кодирования, учитывающих структуру вейвлет-преобразования, может существенно повысить степень сжатия. Один из широко используемых методов такого типа — метод нуль-дерева (англ. zero-tree compression). Он основан на предположении, что если некоторая область изображения не содержит нетривиальной информации на некотором уровне разрешения, то с большой вероятностью она не будет информативной и на более тонком уровне разрешения. Вейвлет-преобразование изображения можно хранить в виде дерева, корнем которого является сильно сглаженная версия оригинала, а ветви, представляющие отдельные блоки, обрываются на том уровне, где дальнейшая обработка не даёт заметного уточнения. Такое дерево можно с успехом сжать обычными методами типа арифметического кодирования, которые используются почти во всех алгоритмах сжатия.

Реализации

Наиболее известный алгоритм вейвлетной компрессии — JPEG 2000. Вейвлет-компрессия используется также при кодировании в формат DjVu. Существует также множество нестандартизированных алгоритмов кодирования изображений и видео-последовательностей основанных на вейвлет-компрессии и предназначенных для специализированного применения. Например одними из самых известных алгоритмов, применяемых в системах видеонаблюдения является Motion Wavelet и 3D Wavelet.


Примеры вейвлетной компрессии:


Wikimedia Foundation. 2010.

Нужна курсовая?

Полезное


Смотреть что такое "Сжатие с использованием вейвлет" в других словарях:

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

  • Сжатие видео — (англ. Video compression)  уменьшение количества данных, используемых для представления видеопотока. Сжатие видео позволяет эффективно уменьшать поток, необходимый для передачи видео по каналам радиовещания, уменьшать пространство,… …   Википедия

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

  • Wavelet — Вейвлеты (от англ. wavelet), всплески (написание вэйвлеты уже почти не употребляется)  это математические функции, позволяющие анализировать различные частотные компоненты данных. Описание В начале развития области употреблялся термин «волночка»  …   Википедия

  • Всплески — Вейвлеты (от англ. wavelet), всплески (написание вэйвлеты уже почти не употребляется)  это математические функции, позволяющие анализировать различные частотные компоненты данных. Описание В начале развития области употреблялся термин «волночка»  …   Википедия

  • Всплеск (математика) — Вейвлеты (от англ. wavelet), всплески (написание вэйвлеты уже почти не употребляется)  это математические функции, позволяющие анализировать различные частотные компоненты данных. Описание В начале развития области употреблялся термин «волночка»  …   Википедия

  • Motion Wavelet — алгоритм компрессии российской разработки для передачи и хранения видеоданных специально в цифровых системах видеонаблюдения. Вместо дискретного косинусного преобразования (англ. Discrete Cosine Transform сокр. DCT), характерного для MPEG2, MPEG4 …   Википедия

  • ICER — Разработан NASA, JPL Опубликован 2002 2003 Тип формата Графический формат Развит в ICER 3D ICER  формат сжатия изображений с использованием вейвлет преобразования. Используется в миссиях NASA, в частности в марсианских. Имеет режимы сжатия с …   Википедия

  • ГОСТ Р 52210-2004: Телевидение вещательное цифровое. Термины и определения — Терминология ГОСТ Р 52210 2004: Телевидение вещательное цифровое. Термины и определения оригинал документа: 90 (телевизионный) демультиплексор: Устройство, предназначенное для разделения объединенных потоков данных цифрового телевизионного… …   Словарь-справочник терминов нормативно-технической документации

  • CineForm — семейство продуктов для нелинейного монтажа цифрового видео высокой четкости американской компании CineForm Inc. Содержание 1 Разновидности формата CineForm 2 История …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»