МИНИСТЕРСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИРЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования
«ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖСВЯЗИ»
ФАКУЛЬТЕТ ЭЛЕКТРОСВЯЗИ
Реферат на тему:
Методы сжатия статических изображений,алгоритм 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,20KB и 50 КВ.
На одном из его этапов применяется вейвлетное преобразование.Кроме того, основная структура данных этого алгоритма, пространственно ориентированноедерево, использует тот факт, что различные поддиапазоны отражают разные геометрическиеособенности образа. Преобразования Хаара можно применять к изображению несколькораз подряд. При этом образуются различные области (поддиапазоны), состоящие из среднихи деталей данного образа. Преобразование Хаара является очень простым и наглядным,но для лучшего сжатия стоит использовать другие вейвлетные фильтры, которые лучшеконцентрируют энергию изображения.
Различные вейвлетные фильтры будут давать разные коэффициентысжатия для разных типов изображений. Однако исследователям пока не до конца ясно,как построить наилучший фильтр для каждого типа образов. Независимо от конкретноиспользуемого фильтра, образ разлагается на поддиапазоны так, что нижние поддиапазонысоответствуют высоким частотам изображения, а верхние поддиапазоны отвечают низкимчастотам образа, в которых концентрируется основная часть энергии изображения. Поэтомуможно ожидать, что коэффициенты деталей изображения уменьшаются при перемещенииот высокого уровня к более низкому. Кроме того, имеется определенное пространственноеподобие между поддиапазонами. Части образа, такие как пики, занимают одну и ту жепространственную позицию во всех поддиапазонах.
/>
Рисунок 2 — поддиапазоны и уровни вейвлетного разложения.
Начнем с общего описания метода SPIHT. Обозначим пикселыисходного изображения р через pij. Любое множество фильтров Т может быть использованодля преобразования пикселов в вейвлетные коэффициенты (или коэффициенты преобразования)Cij. Эти коэффициенты образуют преобразованный образ с. Само преобразование обозначаетсяс = Т (р). При прогрессирующем методе передачи декодер начинает с того, что присваиваетзначение ноль реконструированному образу с. Затем он принимает (кодированные) преобразованныекоэффициенты, декодирует их и использует для получения улучшенного образа с, который,в свою очередь, производит улучшенное изображение р = Т-1 (с). Основная цель прогрессирующегометода состоит в скорейшей передаче самой важной части информации об изображении.Эта информация дает самое большое сокращение расхождения исходного и реконструированногообразов. Для количественного измерения этого расхождения метод SPIHT используетсреднеквадратическую ошибку MSE (mean squared error).
/>
Самые большие (по абсолютной величине) коэффициентыCij несут в себе информацию, которая больше всего сокращает расхождение MSE, поэтомупрогрессирующее кодирование должно посылать эти коэффициенты в первую очередь. Вэтом заключается первый важный принцип SPIHT. Другой принцип основан на наблюдении,что наиболее значимые биты двоичных представлений целых чисел стремятся быть единицами,когда эти числа приближаются к максимальным значениям. (Например, в 16-битном компьютеречисло +5 имеет представление 0|000.0101, а большое число +65382 запишется в виде0|111111101100110. Это наводит на мысль, что старшие биты содержат наиболее значимуючасть информации, и их также следует посылать (или записывать в сжатый массив данных)в первую очередь.
Главным недостатком этого алгоритма является большойобъем информации координат передаваемых значимых коэффициентов />. Для тогочтобы оптимизировать данный процесс в алгоритме SPIHT поступают следующим образом.Разбивают все множество коэффициентов на подмножества />, например,так как показано на рисунке 3.
/>
Рисунок 3 — пример расположения множеств Tk
Затем, просматривают каждое множество /> и проверяют,имеются ли в них значимые коэффициенты />, т.е. коэффициенты,удовлетворяющие условию />. Если найденв множестве /> хотя быодин такой коэффициент, то такое множество также считается существенным. Предположим,что в нашем примере значимым множеством является только />. Тогдаоно разбивается на подмножества />, для которыхвыполняется такая же проверка коэффициентов />. И такдалее пока не дойдем до множеств, состоящих из одного коэффициента. В результатедекодеру передается битовая информация, указывающая, является ли конкретное множество/> значимымили нет. Благодаря иерархической структуре множеств />, общийобъем информации о расположении значимых коэффициентов становится меньше, чем простаяпередача их координат.
Основные шаги кодера SPIHT
Шаг 1: Для заданного сжимаемого изображениявычислить его вейвлетное преобразование, используя подходящие вейвлетные фильтры,разложить его на коэффициенты преобразования qj и представить их в виде целых чиселфиксированной разрядности. Предположим, что коэффициенты представлены в виде целыхчисел со знаком, разрядность которых равна 16, причем самый левый бит является знаковым,а в остальных двоичных 15 разрядах записан модуль этого числа. (Отметим, что такоепредставление отличается от комплементарного представления чисел со знаком, котороетрадиционно применяется в компьютерах.) Значения этих чисел меняются в диапазонеот — (215 — 1) до (215 — 1). Присвоим переменной n значение n = [log2 (215 — 1) J = 14.
Шаг 2: Сортировка. Передать число I коэффициентовкоторые удовлетворяют неравенству 2n
Шаг 3: Поправка. Передать (n — 1) — ые самые старшие биты всех коэффициентов, удовлетворяющихнеравенству \c{j\ > 2n. Эти коэффициенты были выбранына шаге сортировки предыдущей итерации цикла (не этой итерации!).
Шаг 4: Итерация. Уменьшить n на 1. Если необходимо сделать еще однуитерацию, пойти на Шаг 2. Обычно последняя итерация совершается при n = 0, но кодер может остановиться раньше.В этом случае наименее важная часть информации (некоторые менее значимые биты всехвейвлетных коэффициентов) не будет передаваться. В этом заключается естественноеотбрасывание части информации в методе SPIHT. Это эквивалентно скалярному квантованию,но результат получается лучше, поскольку коэффициенты передаются в упорядоченнойпоследовательности. В альтернативе кодер передает весь образ (то есть, все битывсех вейвлетных коэффициентов), а декодер может остановить процесс декодированияв любой момент, когда восстанавливаемое изображение достигло требуемого качества.Это качество или предопределяется пользователем, или устанавливается декодером автоматическипо затраченному времени.
Рассмотрим подробно, что собой представляет кодированиев алгоритме SPIHT
Прежде всего отметим, что кодер и декодер должны использоватьединый тест при проверке множеств на существенность. Алгоритм кодирования используеттри списка, которые называются: список существенных пикселов (LSP, list of significantpixels), список несущественных пикселов (LIP, list of insignificant pixels) и списокнесущественных множеств (LIS, list of insignificant sets).
В эти списки заносятся координаты (i,j) так, что всписках LIP и LSP они представляют индивидуальные коэффициенты, а в списке LIS онипредставляют или множество T> (i,j), или множество C (i,j).
Список LIP содержит координаты коэффициентов, которыебыли несущественными на предыдущей стадии сортировки. В текущей стадии они проверяются,и если множество является существенным, то они перемещаются в список LSP. Аналогичномножества из LIS тестируются в последовательном порядке, и если обнаруживается,что множество стало существенным, то оно удаляется из LIS и разделяется.
Новые подмножества, состоящие более чем из одного элемента,помещаются обратно в список LIS, где они позже будут подвергнуты тестированию, аодноэлементные подмножества проверяются и добавляются в список LSP или LIP в зависимостиот результатов теста. Стадия поправки передает n-ный самый старший бит записей изсписка LSP.
Производительность алгоритма SPIHT можно повысить с помощьюэнтропийного кодирования выхода, но из опытов известно, что это вносит весьма незначительноеулучшение, которое не покрывают временные расходы на его выполнение кодером и декодером.Оказывается, что распределение знаков и индивидуальных битов вейвлетных коэффициентов,производимых на каждой итерации, близко к равномерному, поэтому энтропийное кодированиене дает эффекта сжатия.