Для каждого из коэффициентов самой НЧ области существует три таких дерева, соответствующих трем порядкам фильтрации.
Квантование нульдеревом основано на наблюдении, что если коэффициент мал, его отпрыски на дереве зачастую тоже малы. Это объясняется тем, что значимые коэффициенты возникают вблизи контуров и текстур, которые локальны. Нетрудно увидеть, что это является разновидностью предсказания. А.Льюис и Г.Ноулес свели это предсказание к минимуму, предположив, что если какой - коэффициент незначимый, то все его потомки также будут незначимыми. Дерево или субдерево, которое содержит (по крайней мере, так предполагается) только незначимые коэффициенты, называется нульдеревом.
А.Льюис и Г.Ноулес использовали следующий алгоритм квантования вейвлет – коэффициентов. Вначале каждый узел квантуется квантователем, оптимальным для плотности распределения Лапласа. Если значение узла меньше некоторого порога, его потомки игнорируются. Эти потомки будут восстановлены декодером как нули. Иначе осуществляется переход к четырем отпрыскам узла, и процедура повторяется. Если узел не имеет отпрысков (является листом), начинает обрабатываться следующий корневой узел и т.д.
Данный алгоритм является эффективным в силу двух причин. Во-первых, в силу хорошей «упаковки» энергии вейвлет - преобразованием и, во-вторых, за счет совместного кодирования нулей. Для кодирования нулей обычно применяется кодер длин серий. Для повышения эффективности на вход этого кодера коэффициенты должны подаваться в определенном порядке. Например, в JPEG применено зигзагообразное сканирование. Наверное, наиболее важным вкладом этой работы была демонстрация того, что область вейвлет – коэффициентов прекрасно приспособлена для работы кодера длин серий. В самом деле, генерируются большие серии нулей и не надо передавать их длину, так как высота дерева известна. Аналогично JPEG данный алгоритм является разновидностью скалярного/векторного квантования. Каждый (значимый) коэффициент квантуется отдельно, а символы, соответствующие малым коэффициентам, образуют вектор. Этот вектор состоит из символа нульдерева и последовательности нулей длиной до конца дерева.
Характеристики алгоритма Льюиса и Ноулеса незначительно превосходят JPEG хотя визуальное качество изображений лучше. Недостатком алгоритма является способ порождения и распознавания нульдеревьев. Как было отмечено, если коэффициент мал, то скорее всего его потомки будут малы, но может быть, и нет. В случае если это не так, обнуляются значимые коэффициенты, и алгоритм Льюиса и Ноулеса ведет к большим искажениям.
Преимуществом этого алгоритма является его простота. Нульдеревья порождаются путем простого сравнения амплитуд коэффициентов, и не требуется дополнительной информации об их местоположении. Однако эта простота дается ценой невысокой эффективности. Детальный анализ этого взаимообмена привел к появлению следующего поколения кодеров с применением нульдеревьев.
2.3.2. Алгоритмы Шапиро и Саида – Перельмана
Идеи, лежащие в основе алгоритма Льюиса и Ноулеса, легли в основу многих современных кодеров изображения. Основным недостатком данного алгоритма является возможность ошибочного порождения нульдерева, так как оно генерируется не из реальных данных, а на основе априорных предположений. Если потомки некоторого узла окажутся больше своего родителя (что нечасто, но все - бывает), алгоритм Льюиса и Ноулеса приводит к значительным искажениям.
Методы, рассмотренные ниже, свободны от этого недостатка.
Шапиро разработал элегантный метод, названный алгоритмом вложенного нульдерева (Embedded Zerotree Wavelet coder - EZW). Данный кодер основан на передаче и ненулевых данных, и карты значений. Биты, отводящиеся для кодирования карты значений, могут превалировать в общем потоке бит, особенно на низких скоростях. Однако в карте значений, порождаемой изображениями, существует очень большая избыточность, которая и используется для достижения малых скоростей кодирования. Если имеется незначащий родительский узел, то очень вероятно, что потомки также будут незначимы. Так что в большинстве случаев генерируется символ нульдерева. Если вероятность этого события p близка к 1, то количество информации p log p, содержащееся в нем, близко к нулю. Значит, среднее число бит, требующихся для кодирования карты значений, мало. Если один или более потомков незначимого узла является значимым, генерируется символ «изолированного нуля». Вероятность этого события ниже, следовательно, для кодирования требуется большее количество бит. Это плата за то, чтобы не допустить значительного искажения за счет ошибочного порождения нульдерева.
Алгоритм EZW генерирует вложенный, иерархический код. Подобные кодеры позволяют осуществить прогрессивную передачу изображения с последовательным уточнением его на приеме. При этом изображение вначале аппроксимируется небольшим количеством бит, а потом эта аппроксимация уточняется. Вложенный код имеет то свойство, что при R1>R2 код для R2 будет префиксом кода для R1. Такие коды имеют большой практический
интерес по следующим причинам:
1) возможность точного регулирования скорости передачи;
2) возможность восстановления всего изображения при прекращении приема декодером бит в любой точке. При этом изображение будет максимально хорошего качества для данного числа бит. Это применимо для передачи по каналам с потерями, а также для приложений вещания. В этом случае кодер генерирует высокоскоростной высококачественный поток, который передается по каналам различной пропускной способности декодерам различной вычислительной возможности. Последние выделяют из него нужные им субпотоки;
3) возможность быстрого просмотра изображений в удаленной базе данных. Для поиска достаточно и грубой копии, а при нахождении нужного изображения оно декодируется полностью.
Алгоритм Шапиро генерирует вложенный код побитовым способом. В основе метода EZW лежат следующие основные операции.
Вначале выполняется частичное упорядочивание коэффициентов по амплитуде. Оно реализуется путем сравнения величины каждого вейвлет – коэффициента (ВК) с некоторым порогом Т. Если ВК > Т, то выносится решение о том, что коэффициент значимый, в противном случае – незначимый. Сканирование производится от низкочастотных полос к высокочастотным.
Для кодирования знака и позиции всех коэффициентов используется двухбитный символ. Этот символ может быть: « ± » - знак ВК; «0» – показывает, что ВК незначащий; «корень нульдерева» - показывает, что ВК незначащий вместе со всеми ВК данной пространственной области из более высокочастотных полос. Таким образом, используется межполосная, пространственная корреляция ВК. После вычисления и передачи карты значений для значащих коэффициентов должны быть переданы биты, уточняющие их значение («карта данных»). Далее карта данных и карта значений сжимаются арифметическим кодером. В том случае, если не исчерпан ресурс скорости передачи, порог Т делится на два и процесс повторяется.
Верхние ряды бит содержат много нулей, так как многие коэффициенты имеют значение ниже порога. Роль нульдерева заключается в предотвращении передачи этих нулей. Символ нульдерева может снова и снова передаваться для данного коэффициента, пока он не станет больше текущего порога. После этого передается его квантованное значение.
А.Саид и В.Перельман улучшили алгоритм EZW. Их версия кодера называется «установка подразделений в иерархических деревьях» (Set Partition In Hierarchical Trees - SPIHT). Имеется общедоступная программная реализация этого кодера, которая очень быстра. Так, сжатие изображения размером 512х512 в 100 раз занимает на компьютере Р-166 порядка 0.1 секунды. При этом качество восстановленного изображения весьма приемлемо. Вложенные кодеры обладают одной интересной особенностью: чем больше коэффициент сжатия, тем меньше время работы кодера. Это объясняется тем, что требуется осуществление меньшего числа уточнений. SPIHT превосходит EZW примерно на 0.3 -6 дБ за счет кодирования не одиночных, а параллельных нульдеревьев.
Можно показать, что EZW и SPIHT являются членами большого семейства алгоритмов, в которых карта значений имеет древовидную структуру.
2.3.3. Оптимизация нульдеревьев по критерию скорость - искажение
В рассмотренных кодерах нульдеревья порождались только на основе анализируемых данных. Однако рассмотрим следующий гипотетический пример. Пусть изображение имеет большую равномерную область. Соответствующие ей вейвлет - будут малы, будет генерироваться нульдерево, и на кодирование тратится малое число бит. Предположим теперь, что среди этой области имеется один резко отличающийся по значению пиксель. Этот пиксель приведет к появлению большого вейвлет и нульдерево порождаться не будет.
Неточное кодирование одного пиксела не приведет к большому искажению изображения. В нашем примере эффективность кодера может быть существенно повышена путем игнорирования соответствующего коэффициента и построения нульдерева. Возникает вопрос: каким образом определять, стоит ли отбрасывать коэффициенты, «мешающие» построению нульдерева.
Введение нульдерева для группы вейвлет является, по сути, разновидностью квантования. Значения коэффициентов, которые мы кодируем посредством нульдерева, не являются в общем случае нулевыми. Значимые коэффициенты также подвергаются квантованию. Если сэкономить часть бит путем порождения больших нульдеревьев, высвободившийся ресурс бит можно направить на более точное квантование значимых коэффициентов. Задачей является оптимальное распределение ограниченного ресурса бит между двумя видами квантователей для достижения меньшего искажения.