10457

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

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

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

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

Русский

2013-03-26

63 KB

27 чел.

Алгоритмы сжатия на основе вейвлет-преобразования. Алгоритм 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


 

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

22592. Права та форми власності на землю 64 KB
  Земля в Україні може перебувати у приватній комунальній та державній власності. Суб'єкти права власності на землю. а громадяни та юридичні особи на землі приватної власності; б територіальні громади які реалізують це право безпосередньо або через органи місцевого самоврядуванні на землі комунальної власності; в держава яка реалізує це право через відповідні органи державної влади на землі державної власності.
22593. Цивільне - правові угоди та договори 33.93 KB
  Угоди укладають як юридичні так і фізичні особи. Угоди бувають односторонніми для виникнення такої угоди достатньо волевиявлення однієї сторони; двосторонніми для виникнення угоди необхідні зустрічні волевиявлення двох сторін; багатосторонніми для їх виникнення необхідне волевиявлення трьох і більше сторін. Деякі угоди можуть бути як платними такі безоплатними наприклад договір схову.
22594. Договір найму жилого приміщення 30.71 KB
  Договір найму жилого приміщення в будинках що належать громадянам на правах особистої власності укладається з власником будинку. Предметом договору найму жилого приміщення в будинках державного і громадського житлового фонду є окрема квартира чи інше ізольоване житлове приміщення а також одноквартирний жилий будинок. Не можуть бути самостійним предметом договору найму: жиле приміщення яке хоча і є ізольованим але розмір якого менший від установленого для надання одній особі; частина кімнати або кімнат з'єднаних з іншою кімнатою...
22595. Контролер локальних дисків 63.5 KB
  Програмування контролера НГМД 765 і мікросхеми прямого доступу до пам'яті 8237. Мікросхема контролера НГМД 765 фірми NEC управляє мотором і головками накопичувача на дискетах і обробляє потоки даних що направляються в або з дискових секторів. Один контролер встановлений на платі адаптора дисків може обслуговувати до чотирьох НГМД. За винятком випадків пов'язаних із захистом від копіювання програмістам не доводиться програмувати мікросхему контролера НГМД напряму.
22596. Імітаційна модель процесора 97.5 KB
  Команда як послідовність деяких дій над даними виконується по тактам мікропрограма команди. Команда має вигляд: Код команди 1й операнд 2й операнд . Найчастіше результат команди заноситься за місцем першого операнда. Формат операндів закладається у формат команди.
22597. Визначення швидкодії обчислювальної системи 80 KB
  2; текстові операції 0.2; файлові операції 0.35; операції сортування 0.15; текстові операції 0.
22598. Робота з регістрами CMOS-memory 45.5 KB
  Приведемо тут тільки короткі зведення: Номер регістра Використання 10H тип накопичувача НГМД 12H тип накопичувача фіксованого диска 14H периферія 15H пам'ять на системній платі молодший байт 16H пам'ять на системній платі старший байт 17H загальна пам'ять молодший байт 18H загальна пам'ять старший байт 30H пам'ять понад 1 мегабайту молодший байт 31H пам'ять понад 1 мегабайту старший байт Кожний з трьох каналів мікросхеми таймера 8253 8254 для AT складається з трьох регістрів. Доступ до кожної групи з трьох регістрів здійснюється...
22599. Контроль клавіатурного вводу 32 KB
  Скенкод це однобайтне число молодші 7 бітів якого представляють ідентифікаційний номер призначений кожній клавіші. На всіх машинах крім AT старший біт коду говорить про те чи була клавіша натиснута біт = 1 код натискання або відпущена біт = 0 код звільнення. Наприклад 7бітный скенкод клавіші В 48 або 110000 в двійковій системі.
22600. Управління відеоадаптером IBM PC 35.5 KB
  Однак вона також встановлює режим екрана управляє курсором і для кольорового графічного адаптора управляє кольором. Розмір і розташування цих буферів міняється з системою режимом екрана а також кількістю заздалегідь відведеної пам'яті. Коли в буфері зберігається декілька образів екрана то кожний окремий образ називають екранною сторінкою. Цього досить для відображення одного графічного екрана без сторінок або від чотирьох до восьми екранів тексту в залежності від числа символів в рядку 40 або 80.