Вставить ed Нулевые деревья вейвлет-преобразований

редактировать

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

Рассматривая преобразованные коэффициенты как дерево (или деревья) с самыми низкими частотными коэффициентами в корневом узле и с дочерними элементами каждого узла дерева, которые являются пространственно связанными коэффициентами в следующем более высоком частотного поддиапазона существует высокая вероятность того, что одно или несколько поддеревьев будут полностью состоять из коэффициентов, которые равны нулю или почти нулю, такие поддеревья называются нулевыми деревьями . В связи с этим мы используем термины узел и коэффициент как синонимы, и когда мы ссылаемся на дочерние элементы коэффициента, мы имеем в виду дочерние коэффициенты узла в дереве, где расположен этот коэффициент. Мы используем дочерние элементы для ссылки на непосредственно подключенные узлы ниже в дереве и потомки для ссылки на все узлы, которые находятся ниже определенного узла в дереве, даже если они не подключены напрямую.

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

EZW использует четыре символа для представления (a) корня нулевого дерева, (b) изолированного нуля (коэффициент, который не имеет значения, но имеет значимые потомки), (c) значимый положительный коэффициент и (d) значительный отрицательный коэффициент. Таким образом, символы могут быть представлены двумя двоичными битами. Алгоритм сжатия состоит из ряда итераций через доминирующий проход и подчиненный проход, порог обновляется (уменьшается в два раза) после каждой итерации. Доминирующий проход кодирует значимость коэффициентов, которые еще не были признаны значимыми в предыдущих итерациях, путем сканирования деревьев и выдачи одного из четырех символов. Дочерние элементы коэффициента сканируются только в том случае, если коэффициент оказался значимым или если коэффициент был изолированным нулем. Подчиненный проход испускает один бит (самый значимый бит каждого коэффициента, который еще не испускался) для каждого коэффициента, который был признан значимым в предыдущих проходах значимости. Поэтому подчиненный проход аналогичен кодированию битовой плоскости.

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

С тех пор производительность кодирования EZW превзошла SPIHT и многие его производные.

Содержание
  • 1 Введение
  • 2 Встроенное вейвлет-кодирование нулевого дерева
    • 2.1 A. Кодирование коэффициента карты значимости
      • 2.1.1 1. Корень нулевого дерева
      • 2.1.2 2. Изолированный ноль
      • 2.1.3 3. Положительный значимый коэффициент
      • 2.1.4 4. Отрицательный значимый коэффициент
    • 2.2 B. Определяющий порог
      • 2.2.1 1. Начальный порог T 0 : ( Предположим, что C max является наибольшим коэффициентом.)
      • 2.2.2 2. Пороговое значение T i уменьшено до половины значения предыдущего порогового значения.
    • 2.3 C. Порядок сканирования для коэффициентов
    • 2.4 D. Двухпроходное кодирование битовой плоскости
      • 2.4.1 (1) Проход уточнения (или подчиненный проход)
      • 2.4.2 (2) Значительный проход (или доминирующий проход)
  • 3 См. Также
  • 4 Ссылки
  • 5 Внешние ссылки
Введение

Встроенный вейвлет-алгоритм с нулевым деревом (EZW), разработанный Дж. Шапиро в 1993 году, обеспечивает масштабируемую передачу и декодирование изображений. Он основан на четырех ключевых концепциях: во-первых, это должно быть дискретное вейвлет-преобразование или иерархическая декомпозиция поддиапазонов; во-вторых, он должен прогнозировать отсутствие важной информации при исследовании самоподобия, присущего изображениям; в-третьих, он имеет энтропийно-кодированное квантование последовательного приближения и, в-четвертых, он позволяет достичь универсального сжатия данных без потерь с помощью адаптивного арифметического кодирования.

Кроме того, алгоритм EZW также содержит следующие особенности:

(1) Дискретное вейвлет-преобразование, которое может использовать компактное представление с множественным разрешением в изображении.

(2) Кодирование нулевого дерева, которое обеспечивает компактное представление карт значимости с кратным разрешением.

(3) Последовательное приближение для компактного представления значимых коэффициентов с множественной точностью.

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

(5) Адаптивное многоуровневое арифметическое кодирование, которое является быстрым и эффективным методом энтропийного кодирования строк символов.

Встроенное вейвлет-кодирование нулевого дерева

A. Кодирование коэффициента карты значимости

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

1. Корень нулевого дерева

Если величина коэффициента меньше порога T, а все его потомки меньше T, то этот коэффициент называется корнем нулевого дерева. И если коэффициент был помечен как корень нулевого дерева, это означает, что все его потомки не имеют значения, поэтому помечать его потомков нет необходимости.

2. Изолированный ноль

Если величина коэффициента меньше порогового значения T, но у него все еще есть некоторые важные потомки, то этот коэффициент называется изолированным нулем.

3. Положительный значимый коэффициент

Если величина коэффициента больше порогового значения Т на уровне Т, а также положительна, то это положительный значимый коэффициент.

4. Отрицательный значимый коэффициент

Если величина коэффициента больше порогового значения Т на уровне Т, а также отрицательна, то это отрицательный значимый коэффициент.

Б. Определение порога

Порог, использующийся выше, может быть определен как тип ниже.

1. Начальный порог T 0 : (Предположим, C max является наибольшим коэффициентом.)

Threshold-0119.png

2. Порог T i снижен до половины значения предыдущего порога.

Threshold-01192.png

С. Порядок сканирования для коэффициентов

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

Д. Двухпроходное кодирование битовой плоскости

(1) Проход уточнения (или подчиненный проход)

Определяет, находится ли коэффициент в интервале [Ti, 2Ti). И бит уточнения кодируется для каждого значимого коэффициента.

В этом методе он будет посещать значимые коэффициенты в соответствии с величиной и порядком растра в поддиапазонах.

(2) Важный проход (или доминирующий проход)

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

См. Также
Ссылки
Внешние ссылки
Викискладе есть средства массовой информации, относящиеся к EZW.
Последняя правка сделана 2021-05-19 08:28:10
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте