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


 

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

76526. Виды речевых ошибок: методика работы по их предупреждению и исправлению 29 KB
  Употребление слов в несвойственных им значениях. Повторение однокоренных слов в одном предложении тавтология: Писатель ярко описывает события того дня. Речевая недостаточность возникает в случае когда пропущено нужное слово. Употребление лишних слов.
76527. Отбор теоретических понятий при изучении фонетики, графики и орфоэпии 31 KB
  Необходимо при изучении словообразования: буквы имеющие два один звук. Цель изучения:осознаное усвоение звуковой системы языка; знакомство с орфоэпическими нормами СРЛЯ; формирование орфографических навыков.Задачи:Формирование основных фонетических понятий: звук слог ударение интонация;Дать представление о русской графике как науке устанавливающей общие принципы передачи звучащей речи на письме;Развивать фонематический слух учащегося и на этой основе формировать орфографическую грамотность школьника;Закрепить умение обозначить звуки...
76529. Русский язык как предмет изучения. Место русского языка в ряду других учебных предметов. Межпредметные связи на уроках русского языка 34.5 KB
  Место русского языка в ряду других учебных предметов. Межпредметные связи на уроках русского языка.На каждом уровне выделяются след основные линии: система языка или знания о языке сформированные в виде понятий способов действия а также владения самим языком и его нормами. В содержание стандарта случены отдельные сведения которые отсутствуют в современных учебниках но в то же время представляют собой ближайшую перспективу для совершенствования курса родного языка.
76530. Цели и задачи обучения русскому языку. Структура и содержание курса русского языка в средней школе 29.5 KB
  Языковая часть курса в каждой теме представлена тремя компонентами: а сведения о языке подлежащие усвоению; б умения и навыки в области культуры речи языкового анализа практические умения общеучебные умения; в способ деятельности через учебник В структуре школьной программы по русскому языку выделяются два уровня: уровень программы в целом и уровень программы каждого класса. Структура программы в целом делится на органически связанные но самостоятельные программы для каждого класса. Структура программы второго уровня уровня каждого...
76531. Методическая система, содержание ее компонентов 53 KB
  Классификация Текучева основа: использование разных источников знаний: Рассказ или слово учителя; Беседа; Разбор; Наблюдение. Классификация Лидия Прокофьевна Федоренко основа: использование разных источников знаний 3 группы методов обучения. пунктуационный диктант контрольный контроль знаний и обучающие...
76534. Значение и место учебника по русскому языку. Анализ учебника русского языка 30 KB
  В этой книге излагаете материал в соответствии с программой по предмету. Цель использования учениками: получение необходимой информации приобретения комплекса умения и навыков Для учителя: источник методической системы который помогает определить методику работы на разных этапах усвоения учебного материала чему и как учить. Систематизирующую: материал представлен в системе усвоение по системе от простого к сложному. Весь теоретический материал может быть представлен в учебниках разными способами: дедукция способ мышления основой является...