10457

Алгоритмы сжатия на основе вейвлет-преобразования. Алгоритм SPIHT

Научная статья

Исторические личности и представители мировой культуры

Алгоритмы сжатия на основе вейвлетпреобразования. Алгоритм SPIHT. Изображение полученное при помощи вейвлетпреобразования можно сжимать различными способами. Большинство из них можно отнести к одной из двух категорий. К первой категории относятся способы сводящиеся

Русский

2013-03-26

63 KB

25 чел.

Алгоритмы сжатия на основе вейвлет-преобразования. Алгоритм SPIHT.

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

Алгоритм SPIHT (Set Partitioning In Hierarchical Tree), разработанный Amir Said и William Pearlman в 1996 году, является одним из наиболее эффективных алгоритмов сжатия изображений с потерями. Он стал отправной точкой для дальнейших исследований по сжатию изображений с потерями на основе вейвлет - анализа. К преимуществам данного алгоритма относятся:

  •  Возможность выбора степени сжатия в широких пределах – от 4 до 0,1 бит/пиксел.
  •  Отсутствие блочности изображения при высоких степенях сжатия.
  •  В случае, если начиная с какого-то места часть данных теряется, возможно восстановление всего изображения (с худшим качеством).
  •  Возможность того, что результирующий объем данных будет иметь строго заданный размер.

К недостаткам данного алгоритма следует отнести:

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

Алгоритм SPIHT заключается в следующем.

Над изображением осуществляется вейвлет – преобразование с использованием биортогонального базиса вейвлетов "CDF 9/7". В качестве альтернативы можно использовать базис Хаара. Как правило, используется пятикратное вейвлет – преобразование.

Как известно, вейвлет – спектр имеет иерархическую структуру, в которой каждому коэффициенту, за исключением самых низкочастотных (с левой верхней части спектра) и самых высокочастотных (в 1, 3 и 4 квадрантах), соответствуют 4 коэффициента – потомка. Низкочастотные коэффициенты, которые на рисунке 1 обозначены звездочкой, передаются в начале файла (информационного пакета) и далее не рассматриваются.

Рисунок 1. Иерархия в вейвлет – спектре для случая четырехкратного вейвлет - преобразования.

Для реализации алгоритма вейвлет – спектр рассматривается как совокупность N битовых плоскостей, где N = [log2(A)]. Здесь A – значение наибольшего вейвлет - коэффициента

Введем некоторые определения.

Множеством прямых потомков коэффициента с координатами i, j, обозначаемое O(i, j) называются 4 коэффициента с координатами {(2i, 2j), (2i+1, 2j), (2i, 2j+1), (2i+1, 2j+1)}.

Множеством всех потомков коэффициента с координатами i, j, обозначаемое D(i, j) называется множество прямых потомков коэффициента вместе со всеми множествами прямых потомков всех потомков.

Множеством дальних потомков L(i, j) называется множество D(i, j)-O(i, j). Каждое из этих множеств может быть и пустым. Схематически эти множества изображены на рисунке 2.

Рисунок 2. Множества O, D и L.

Пусть имеется множество T, состоящее из одного или нескольких коэффициентов. Значимостью множества Sn(T) называется булева функция, которая для отдельного коэффициента принимает значение "истинно", если коэффициент больше или равен 2n. В противном случае функция принимает значение "ложно". Для случая, когда T представляет собой множество, функция принимает значение "истинно", если хотя бы один коэффициент из этого множества является значимым. В противном случае функция принимает значение "ложно". Таким образом, формально можно записать:

.

Введем еще некоторые множества – список незначимых коэффициентов (LIP, list of insignificant pixels), список значимых коэффициентов (LSP, list of significant pixels) и список незначимых множеств (LIS, list if insignificant sets). В списке незначимых множеств могут быть множества типа D(i, j) – так называемые множества типа A, и множества типа L(i, j) – так называемые множества типа B. Первоначально все коэффициенты находятся в LIP, а те из них, которые имеют ненулевое множество потомков, заносятся еще и в LIS как объекты типа А. В конце работы алгоритма, при передаче всех битовых плоскостей, все коэффициенты должны находится в LSP.

Собственно алгоритм заключается в следующем.

1. Фиксируем и передаем в выходной поток номер битовой плоскости, начиная с N. Пусть это будет n.

2. Для каждого коэффициента с(i, j) из LIP:

2.1 передается в выходной поток значимость этого коэффициента Sn(i, j),

2.2 если коэффициент значимый, то в выходной поток передается его знак (только один раз), а сам коэффициент переносится в LSP.

3. Для каждого объекта из LIS:

3.1 если это объект типа A, то:

3.1.1 выводится значимость Sn(D(i, j)),

3.1.2 если множество D(i, j) значимо, то

3.1.2.1 для каждого элемента с(k, l) из O(i, j) выводится значимость этого элемента и

3.1.2.1.1 если это элемент значимый, то в выходной поток передается его знак (только один раз), а сам элемент заносится в LSP

3.1.2.1.2 если это элемент не значимый, элемент заносится в LIP.

3.1.2.2 Если множество L(i, j) существует, то элемент с(i, j) заносится в конец LIS как элемент типа B. В противном случае элемент удаляется из LIS.

3.2 если это объект типа B, то:

3.2.1 выводится значимость Sn(L(i, j)),

3.2.2 если множество L(i, j) значимо, то

3.2.2.1 каждый элемент с(k, l) из O(i, j) заносится в LIS как элемент типа A,

3.2.2.2 элемент с(i, j) удаляется из LIS.

4. Для каждого коэффициента c(i, j) из LSP выводится n-й бит, за исключением случаев, когда этот коэффициент был добавлен в LSP при текущем n.

5. Величина n уменьшается на 1 и переходим к шагу 1, до тех пор, пока n>0.

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

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

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

Процедура сжатия с использованием алгоритма SPIHT можно разделить на две основные части: вейвлет - преобразование и кодирование вейвлет – коэффициентов. Количество операций, необходимых для вейвлет – преобразования можно вычислить точно. Так, для изображения размером форматом NхM пикселов и вейвлета "CDF 9/7", который имеет длину 9, для вычисления пятикратного вейвлет – спектра необходимо следующее количество операций:

1-й шаг преобразования: 4*9*(N*M)

2-й шаг преобразования: 4*9*[N/2]*[M/2]

3-й шаг преобразования: 4*9*[N/4]*[M/4]

4-й шаг преобразования: 4*9*[N/8]*[M/8]

5-й шаг преобразования: 4*9*[N/16]*[M/16]

При большем количестве шагов вейвлет – преобразования количество операций стремится к 2*4*9*(N*M). Эту формулу удобно применять и при пяти шагах вейвлет – преобразования – ее погрешность составит 4*9*[N/16]*[M/16]. Все операции имеют вид "умножение с накоплением" (MMAC). Для сжатия изображения размером 512 на 512 пикселов (как на приведенном примере) потребуется 18 874 368. При использовании более короткого вейвлета (в пределе – вейвлета Хаара) количество операций уменьшается и в приведенном примере может составлять до 2 097 152.

Количество операций на этапе кодирования можно оценить следующим образом. Как правило, для каждого коэффициента осуществляются следующие операции: вычисление значимости, передача значимых бит, вычисление значимости множеств O, D и L. Заметим, что для большинства коэффициентов эти множества или пусты, или малы, или не являются значимыми. Беря, с запасом, что количество битовых плоскостей равно 12, причем в среднем только 6 бит в плоскости являются значимыми, получаем, что потребуется 12+6 операций побитового сложения, 24 операции пересылки и еще 7 операций вида передать бит, то есть всего 49 операций на коэффициент. Таким образом, для кодирования потребуется 49* N*M операций. Всего же в случае вейвлета "CDF 9/7" потребуется 121*N*M операций, а в случае вейвлета Хаара - 85*N*M операций.

При сжатии потоковых данных и использовании пятикратного вейвлет – преобразования необходимый объем памяти для вычисления вейвлет – преобразования и хранения коэффициентов составляет (25+8)*(M+8) слов при использовании базиса "CDF 9/7" и (25+1)*(M+1) слов при использовании базиса Хаара. Размер слова зависит от разрядности изображения (обычно число бит слова равно разрядности изображения плюс число шагов преобразования) и, как правило, составляет 16 бит. Кроме того, потребуется память для хранения множеств O, D и L – (М+8)*8 для множеств О и D (M+8)*2 для множества L в случае базиса "CDF 9/7" и (М+1)*8 для множеств О и D (M+1)*2 для множества L в случае базиса Харра.


O(i, j)

(i, j)

L(i, j)

i, j


 

А также другие работы, которые могут Вас заинтересовать

69457. Разработка трехмерной графической модели проводящей системы сердца 2.04 MB
  В работе приводится подробное описание модели и использованного средства разработки. Это позволяет использовать работу в учебных целях, а также она может использоваться специалистами при моделировании как нормальных, так и патологических работах сердца.
69458. Духовная ситуация времени и правовая подготовка студента педагогического Вуза 55 KB
  Так в курсе Основы права в институтах народного хозяйства делался упор на уголовно-правовую ответственность хозяйственных работников в технических Вузах на соблюдении норм техники безопасности и т.
69459. Присоединение Прибалтики к России, Эстляндия и Лифляндия в составе России 33.5 KB
  Прибалтика состоящая из Эстляндии Курляндии и Лифляндии была как известно присоединена к России в ходе Северной войны 1700-1721 которую вела Россия со Швецией за выход к Балтийскому морю. В результате победы России по Ништадтскому мирному договору 1721 г.
69460. Присоединение Северного Кавказа к России. Кавказская война 25.5 KB
  С присоединением к России территорий Закавказья территория Северного Кавказа была как бы независимым анклавом внутри Российского государства. госств заставлял обезопасить свои тылы тем более что многие народы в надежде избавиться от притязаний Турок стремились...
69461. Продажа Аляски. Явный и скрытый механизм сделки 28 KB
  Явный и скрытый механизм сделки Причины продажи Аляски: 1 опасность применения силы со стны США в целях присоединения этой территории; 2 убыточность РАК; 3 желание сохранить дружественные отношения с США; 4 Опасность распространения республиканских идей...
69462. Лирика А. С. Пушкина: особенности мироотношения поэта, жанровая динамика 37.12 KB
  Лицейский период 1811-1817 осваивает жанры и стили. Ода, элегия, политические стихи, эпиграммы, пародии. Основной – жанр дружеского послания. – пограничный между прозой и поэзией. «К товарищам». Поэт - ленивец, отказывающийся от социальных обязанностей, свободный, профессиональный литератор.
69463. Рассказ в русской литературе 18.27 KB
  Человек испытывает универсальные чувства понятные всем. Все о чем пишет Казаков предельно просто: универсальные чувства страха обиды восторга отчаяния и др. Движение человека от жизни дневной к жизни ночной где дневная жизнь расценивается как инерция ночь же позволяет...
69464. Розанов. Легенда о Великом Инквизиторе 17.84 KB
  Религия нечто высокое и сделать ей возможно другого человека способность войти в ее миросозерцание высшая цель. Здесь надломленность человеческих сил неспособность их продолжать тот путь по который от скрытого начала к скрытому же концу ведет человека провидение.
69465. Сатира в литературе 1920-х годов 18.38 KB
  В 1920-ые годы возникла необходимость в так называемом «отдыхе». Человек на протяжении последних лет был погружен в атмосферу революций, гражданских войн – «кровавых» событий. Пьесы, которые ставились на сцене театра, имели «лечебное» воздействие; театр – это место, где собирается масса народа; происходящее на сцене...