Встроенные нулевые деревья вейвлет-преобразований - Embedded Zerotrees of Wavelet transforms

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

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

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

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

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

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

Вступление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Начальный порог T0: (Предположим, что CМаксимум - наибольший коэффициент.)

Threshold-0119.png

2. Порог Tя уменьшается до половины значения предыдущего порога.

Threshold-01192.png

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

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

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

(1) Проход доработки (или подчиненный проход)

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

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

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

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

Смотрите также

Рекомендации

внешняя ссылка

  • Клеменс Валенс (2003-08-24). «Кодировка EZW». В архиве из оригинала от 03.02.2009.