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


 

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

38867. Совершенствование управлением постоянными и переменными затратами при формировании финансовых результатов на предприятии СПК «Куяштыр» Аскинского района 1.04 MB
  Понятие затрат предприятия существенно различается в зависимости от их экономического назначения. Четкое разграничение затрат по их роли в процессе воспроизводства является определяющим моментом в теории и практической деятельности. Переменные и постоянные затраты это два основных типа издержек.
38868. Призначення, будова і принцип роботи приладу типу МТМ-РЭ-160 366 KB
  Управління технологічними процесами з використанням автоматичних засобів включає в себе виконання наступних основних задач: контроль параметрів процесів (температури, тиску в апаратах, складу і якості рідин і газів і т. д.); регулювання параметрів (підтримання їх у заданих значеннях)
38869. Изучение системно-характерологических отношений личности с разным уровнем готовности к риску 247 KB
  Техногенные прорывы плотин дамб шлюзов перемычек аварии на коммунальных системах жизнеобеспечения и предприятиях внезапное обрушение зданий сооружений аварии на энергетических системах пожары взрывы транспортные аварии аварии с выбросом радиоактивных химических и биологических веществ; 3 экологическиеизменение состояния суши атмосферы гидросферы и биосферы; 4 биологические инфекционные заболевания эпидемии нашествия насекомых и животных и 5 социального характеравойны революции региональные конфликты и т. По...
38870. Разработка однолинейной схемы электрической подстанции 561.5 KB
  Расчет параметров короткого замыкания. Расчет параметров цепи короткого замыкания необходим для дальнейшей проверки выбранных токоведущих частей и оборудования подстанции по режиму короткого замыкания на термическую и электродинамическую стойкость и для проверки чувствительности релейной защиты. Последствиями термического и электродинамического воздействия токов короткого замыкания могут быть: механическое разрушение сборных шин частей аппаратуры токоведущих частей генераторов и трансформаторов; перегрев и расплавление...
38871. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ И ЗАЩИТЕ ДИПЛОМНЫХ РАБОТ (ПРОЕКТОВ) 432.5 KB
  В методических указаниях включены основные требования предъявляемые к структуре содержанию и оформлению дипломной работы проекта; краткие рекомендации по содержанию дипломной работы проекта и оформлению отзыва и рецензии; описана процедура защиты дипломной работы проекта. ВЫБОР НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ [5] 3 ВЫБОР ТЕМЫ ДИПЛОМНОЙ РАБОТЫ ПРОЕКТА [5.3 Формулирование темы дипломной работы проекта [5.5] 4 НАУЧНОЕ РУКОВОДСТВО ДИПЛОМНОЙ РАБОТОЙ ПРОЕКТИРОВАНИЕМ [6] 5 ИЗЛОЖЕНИЕ МАТЕРИАЛОВ ДИПЛОМНОЙ РАБОТЫ ПРОЕКТА [7] 6 СТРУКТУРА И...
38872. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ДИПЛОМНЫХ РАБОТ 619.5 KB
  Дипломная работа - выпускная квалификационная работа студента, предназначенная для объективного контроля степени сформированности знаний, умений и навыков решать задачи по видам профессиональной деятельности, установленным образовательным стандартом специальности, и предусматривающая проведение анализа и разработки актуальных вопросов, проблем в соответствующей области знаний согласно требованиям задания на выпускную квалификационную работу.
38873. МЕТОДИЧНІ ВКАЗІВКИ до виконання розділу «ОХОРОНА ПРАЦІ » в дипломних проектах 406 KB
  Передбачити в технологічних цехах та відділеннях де може статися вибух пожежа отруєння людей відділення отримання спирту та інші аварійне освітлення. Основними організаційними заходами є: експлуатація обладнання у відповідності з технічними характеристиками згідно паспорту заводувиробника; проведення своєчасного профілактичного ремонту обладнання; розміщення обладнання з підвищеним рівнем шуму і вібрації в ізольованому приміщенні дробильнопресове відділення; дотримання режимів праці та відпочинку; використання...
38874. МЕТОДИЧНІ ВКАЗІВКИ ЩОДО ВИКОНАННЯ дипломної роботи 200.5 KB
  Мета роботи – презентація студентом вміння виконувати наукове дослідження з теорії та вміння використовувати теоретичні знання для вирішення конкретних практичних завдань, а також виявлення ступеня підготовки випускника до самостійної практичної діяльності.
38875. Производство леворина. Ферментация с получением мицелиальной массы 295 KB
  Массовая доля основного вещества не менее 985; 2.Массовая доля влаги не более 05; 3.Массовая доля веществ нерастворимых в соляной кислоте не более 01 В состав питательной среды на ферментации 4.Массовая доля влаги не более 9; 5.