Методы сжатия статических изображений, алгоритм SPIHT (стр. 1 из 2)

МИНИСТЕРСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

"ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ"

ФАКУЛЬТЕТ ЭЛЕКТРОСВЯЗИ

Реферат на тему:

Методы сжатия статических изображений, алгоритм SPIHT

по дисциплине:

"Цифровая обработка речи и изображения"

Выполнил студент гр. ПО941

Гаманович С.В.

Минск 2011

Методы сжатия статических изображений, алгоритм SPIHT

Основные методы сжатия статических изображений:

· Снижение глубины цвета

· Метод главных компонент

· Фрактальное сжатие

· Сжатие на основе предсказателей

· ДИКМ

· Иерархическая сеточная интерполяция

· JPEG

· Вейвлетная компрессия

· JPEG 2000

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

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

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

DjVu (от фр. déjà vu - "уже виденное") - технология сжатия изображений с потерями, разработанная специально для хранения сканированных документов - книг, журналов, рукописей и прочее, где обилие формул, схем, рисунков и рукописных символов делает чрезвычайно трудоёмким их полноценное распознавание. Также является эффективным решением, если необходимо передать все нюансы оформления, например, исторических документов, где важное значение имеет не только содержание, но и цвет и фактура бумаги; дефекты пергамента: трещинки, следы от складывания; исправления, кляксы, отпечатки пальцев; следы, оставленные другими предметами и т.д.

JPEG 2000 (или jp2) - графический формат, который вместо дискретного косинусного преобразования, применяемого в формате JPEG, использует технологию вейвлет-преобразования, основывающуюся на представлении сигнала в виде суперпозиции базовых функций - волновых пакетов.

В результате такой компрессии изображение получается более гладким и чётким, а размер файла по сравнению с JPEG при одинаковом качестве оказывается меньшим. JPEG 2000 полностью свободен от главного недостатка своего предшественника: благодаря использованию вейвлетов, изображения, сохранённые в этом формате, при высоких степенях сжатия не содержат артефактов в виде "решётки" из блоков размером 8х8 пикселей. Формат JPEG 2000 так же, как и JPEG, поддерживает так называемое "прогрессивное сжатие", позволяющее по мере загрузки видеть сначала размытое, но затем всё более чёткое изображение.

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

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

вейвлетная компрессия изображение алгоритм

Рисунок 1 - пример фрактала

Фрактальный алгоритм позволяет сжимать изображения в сотни и даже тысячи раз.

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

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

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

Фрактальные методы можно рассматривать, как альтернативу технологиям, основанным на преобразовании Фурье, например, таким как JPEG. Новые технологии, такие как фрактальные должны рассматриваться не только как конкуренты, но и как союзники в установлении новых стандартов.

Алгоритм SPIHT (Пространственно Упорядоченные Иерархические Деревья) представляет собой метод сжатия изображений с потерями и обладает высокой чувствительностью. Его легко реализовывать, он работает быстро и дает прекрасные результаты при сжатии любых типов изображений.

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

Другая отличительная черта алгоритма SPIHT состоит в использовании им вложенного кодирования. Это свойство можно определить следующим образом: если кодер, использующий вложенное кодирование, производит два файла, большой объема М бит и маленький объема nбит, то меньший файл совпадает с первыми Mбитами большего файла.

Следующий пример удачно иллюстрирует это определение. Предположим, что три пользователя ожидают некоторое отправленное им сжатое изображение. При этом им требуется различное качество этого изображения. Первому из них требуется качество, обеспечиваемое 10 KB образа, а второму и третьему пользователю необходимо качество, соответственно, в объеме 20 KB и 50 КВ. Большинству методов сжатия изображения с частичной потерей данных потребуется сжимать исходный образ три раза с разным качеством, для того, чтобы сгенерировать три различных файла, требуемых объемов. А метод SPIHT произведет для этих целей всего один файл, и пользователям будут посланы три начальных фрагмента этого файла, длины которых соответственно равны 10 KB,20 KB и 50 КВ.

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

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

Рисунок 2 - поддиапазоны и уровни вейвлетного разложения.

Начнем с общего описания метода SPIHT. Обозначим пикселы исходного изображения р через pij. Любое множество фильтров Т может быть использовано для преобразования пикселов в вейвлетные коэффициенты (или коэффициенты преобразования) Cij. Эти коэффициенты образуют преобразованный образ с. Само преобразование обозначается с = Т (р). При прогрессирующем методе передачи декодер начинает с того, что присваивает значение ноль реконструированному образу с. Затем он принимает (кодированные) преобразованные коэффициенты, декодирует их и использует для получения улучшенного образа с, который, в свою очередь, производит улучшенное изображение р = Т-1 (с). Основная цель прогрессирующего метода состоит в скорейшей передаче самой важной части информации об изображении. Эта информация дает самое большое сокращение расхождения исходного и реконструированного образов. Для количественного измерения этого расхождения метод SPIHT использует среднеквадратическую ошибку MSE (mean squared error).

Самые большие (по абсолютной величине) коэффициенты Cij несут в себе информацию, которая больше всего сокращает расхождение MSE, поэтому прогрессирующее кодирование должно посылать эти коэффициенты в первую очередь. В этом заключается первый важный принцип SPIHT. Другой принцип основан на наблюдении, что наиболее значимые биты двоичных представлений целых чисел стремятся быть единицами, когда эти числа приближаются к максимальным значениям. (Например, в 16-битном компьютере число +5 имеет представление 0|000.0101, а большое число +65382 запишется в виде 0|111111101100110. Это наводит на мысль, что старшие биты содержат наиболее значимую часть информации, и их также следует посылать (или записывать в сжатый массив данных) в первую очередь.

Главным недостатком этого алгоритма является большой объем информации координат передаваемых значимых коэффициентов

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