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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Порог Ti _{снижается} до половины значения предыдущего порога.

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

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

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

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

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

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

(2) Значительный пас (или доминирующий пас)

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

Пример

DCT data                          ZeroTree scan order (EZW)
 63 -34  49  10   7  13 -12   7    A  B BE BF E1 E2 F1 F2
-31  23  14 -13   3   4   6  -1    C  D BG BH E3 E4 F3 F4
 15  14   3 -12   5  -7   3   9   CI CJ DM DN G1 G2 H1 H2
 -9  -7 -14   8   4  -2   3   2   CK CL DO DP G3 G4 H3 H4
 -5   9  -1  47   4   6  -2   2   I1 I2 J1 J2 M1 M2 N1 N2
  3   0  -3   2   3  -2   0   4   I3 I4 J3 J4 M3 M4 N3 N4
  2  -3   6  -4   3   6   3   6   K1 K2 L1 L2 O1 O2 P1 P2
  5  11   5   6   0   3  -4   4   K3 K4 L3 L4 O3 O4 P3 P4

D1: pnzt p    ttt  tztt tttttptt (20 codes)
    PNZT P(t) TTT  TZTT     TPTT   (D1 by M-EZW, 16 codes)
    PNZT P(t) Z(t) TZ(p)    TPZ(p) (D1 by NM-EZW, 11 codes)
      P N (t), P or N above zerotree scan
      P N Z(t p), p=pair T, t=triple T, P/N + TT/TTT in D1 code
S1: 1010
D2: ztnp tttttttt
S2: 1001 10 (Shapiro PDF end here)
D3: zzzz zppnppnttnnp tpttnttttttttptttptttttttttptttttttttttt
S3: 1001 11 01111011011000
D4: zzzzzzztztznzzzzpttptpptpnptntttttptpnpppptttttptptttpnp
S4: 1101 11 11011001000001 110110100010010101100
D5: zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt
S5: 1011 11 00110100010111 110101101100100000000 110110110011000111
D6: zzzttztttztttttnnttt
( http://www.polyvalens.com/wavelets/ezw/ )

Detailed: (new S is first, other computed by before cycles)
s-step      1                21               321
   val   D1 S1       R1   D2 S2       R2   D3 S3. ...   R3 ... D4,S4...
A   63   P  1  >=48  56   Z  .1 >=56  60   Z  ..1 >=60  62
B  -34   N  0   <48 -40   T  .0  <40 -36   Z  ..0  <36 -36
C  -31   IZ     <32   0   N  1. >=24 -28   Z  .1. >=28 -30
D   23   T      <32   0   P  0. <24   20   Z  .1. >=20  22

BE  49   P  1  >=48  56      .0  <56  52   Z  ..0  <52  50
BF  10   T      <32   0                    P  0    <12  10
BG  14   T      <32   0                    P  1   >=12  14
BH -13   T      <32   0                    N  1   >=12 -14
CI  15   T      <32   0   T      <16   0   P  1   >=12  14
CJ  14   IZ     <32   0   T      <16   0   P  1   >=12  14
CK  -9   T      <32   0   T      <16   0   N  0    <12 -10
CL  -7   T      <32   0   T      <16   0   T        <8   0
DM   3			  T      <16   0   T        <8   0
DN -12			  T      <16   0   N  1   >=12 -14
DO -14			  T      <16   0   N  1   >=12 -14
DP   8			  T      <16   0   P       <12  10

E1   7   T      <32   0                    .E,F,G,H(1,2,3,4)
E2  13   T      <32   0                    .I,J,K(1,2,3,4)
E3   3   T      <32   0                    .N,O,P(1,2,3,4)
E4   4   T      <32   0                    .
J1  -1   T      <32   0                    .
J2  47   P  0  >48   40       1 >=40  44   .
J3  -3   T      <32   0
J4   2   T      <32   0

D = dominant pass (P=positive, N=negative, T=ZeroTree, IZ=Izolated zero)
S = subordinate pass;
(R = back reconstructed value)

См. также

• Установить разделение в иерархических деревьях (SPIHT)

Ссылки

• Дж. М. Шапиро (1993). «Кодирование встроенных изображений с использованием нулевых деревьев вейвлет-коэффициентов». Транзакции IEEE по обработке сигналов . 41 (12): 3445–3462. CiteSeerX   10.1.1.131.5757 . дои : 10.1109/78.258085 . ISSN   1053-587X . S2CID   18047405 . Збл   0841.94020 . Викиданные   Q56883112 .

Внешние ссылки

• Клеменс Валенс (24 августа 2003 г.). «Кодировка EZW» . Архивировано из оригинала 3 февраля 2009 г.