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


 

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

35768. Творчий проект «Кухонна дошка» 492 KB
  2 Визначення собівартості виробу Матеріал Ціна одиниці вимірювання грн Витрата матеріалів Вартість витрат грн. Вмат Брусок липовий 1000 грн м3 00063 м3 63 Усього 63 3. г при тарифі на електроенергію 025 вартість спожитої електроенергії складає Ве=025 035=009 грн Матеріальні витрати Мв=ВматВс = 665 грн 009 грн = 674 грн.= 3132 грн.
35769. Творчий проект на тему:«Лічильна гладь» 69 KB
  Вишивка один з найбільш поширених видів декоративного мистецтва в якому орнаментальне та сюжетне зображення на тканині шкірі повсті виконується різними ручними або машинними швами. Вишивка виникла з появою шитва на примітивному одязі людини кам‘яного віку. Уже в першому тисячолітті до нашої ери вишивка досягла високого художнього рівня в народів Стародавнього Вавілону Греції Риму Китаю Індії Ірану. Особливою пишністю відзначалася вишивка Візантії.
35770. Торт Наполеон. Творчий проект 1.56 MB
  Самореалізуватися при виконанні роботи своїми руками. Після закінчення роботи їх потрібно насухо витерти. Організація робочого місця ТБ при роботі ВИМОГИ БЕЗПЕКИ ПЕРЕД ПОЧАТКОМ РОБОТИ. ВИМОГИ БЕЗПЕКИ ПІД ЧАС РОБОТИ Увалено і чітко виконуйте вказівки вчителя.
35772. Творческий проект. Тема: Табуретка 171 KB
  Табуреты это стулья без спинок или короткие скамьи для только исключительно одного человека. Римляне делали крепления подвижными так появляются складываемые табуреты. Сейчас табуреты практически любые сиденья без спинок и подлокотников. Актуальность: табуреты очень пригодятся в жизни потому что они компактны в отличии от стульев и их удобнее переносить.
35773. КУКЛА-КОРМИЛКА (или ХОЗЯЮШКА). Творческий проект 140 KB
  Историческая справка Наиболее распространенной игрушкой в России еще в первые десятилетия ХХ века была тряпичная кукла. Кукла была предметом полным внутреннего значения и смысла. Кукла была неотъемлемой частью праздников русской деревни: сева жатвы уборки урожая многочисленных ритуалов и обрядов.
35774. Рисунок «Капитан Джек Воробей». Творческий проект 6.12 MB
  После долгих размышлений я решила что Джонни Депп подходящая кандидатура так как он очень известный актер с красивой внешностью.Мне очень нравится его роль капитана Джека Воробья в фильме Пираты Карибского моря поэтому я решила нарисовать его именно в этом образе. Обоснование выбора цветовой гаммы и использования материалов Так как на стенах школы уже висят две работы нарисованные простыми карандашами я решила на этот раз сделать рисунок цветным.
35775. Маркетинговый анализ компании 39 KB
  Ваша задача проанализировать маркетинговую деятельность компании и найти новое направление развития компании. Маркетинговый анализ компании. Описание компании Название принадлежность к бизнесу малый средний крупный Давайте примем принадлежность к бизнесу по вашим представлением т. Сфера деятельности компании принадлежность к отрасли определение по категориям географические ценовые границы классификация товаров и или услуг Домашнее задание 1.