Дерево

QTCQ

Близким к методу SPIHT является алгоритм QTCQ (quadtree classification and trellis coding, классификация четвертичных деревьев и решетчатое кодирование) из работы [Banister, Fischer 99], который использует меньше списков, чем SPIHT, и явно формирует классы вейвлетных коэффициентов для дальнейшего квантования с помощью методов ACTCQ и TCQ из [Joshi, Crump, Fischer 93].

Этот метод основан на пространственно ориентированных деревьях, построенных для SPIHT. Этот тип деревьев является особым случаем четвертичных деревьев. Алгоритм кодирования является итеративным. На n-той ...

Пространственно ориентированное дерево

Множества Т^ создаются и разделяются с помощью специальной структуры данных, которая называется пространственно ориентированным деревом. Эта структура определяется с использованием пространственных соотношений между вейвлетными коэффициентами и различными уровнями пирамиды поддиапазонов. Многочисленные наблюдения показывают, что поддиапазоны каждого уровня пирамиды демонстрируют определенную пространственную симметрию (см. рис. 4.7Ь). Любые пространственные особенности изображения такие, как прямые края, равномерные области, остаются легко различимыми на всех уровнях.

...

LZSS

Эта версия LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982 [Storer 82]. Базовый алгоритм был улучшен по трем направлениям: (1) упреждающий буфер сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три.

Двоичное дерево поиска - это двоичное дерево, в котором левое поддерево каждого узла А содержит узлы, меньшие чем Л, а узлы правого поддерева все больше А Поскольку узлы нашего двоичного дерева состоят из строк (или слов), прежде всего необходимо определиться, как эти ...

Кодовое переполнение

Более серьезную проблему может создать кодовое переполнение. Это случится, если на дерево поступит слишком много символов и оно станет слишком высоким. Сами коды не хранятся на дереве, так как они меняются все время, и компрессор должен вычислять код символа X каждый раз заново при его появлении.

1. Кодер должен обнаружить символ X на дереве. Дерево следует реализовать в виде массива структур, состоящих из узлов. Поиск в этом массиве будет линейным.

2. Если X не найден, то вырабатывается код esc, за которым следует несжатый код символа. Затем ...

Переполнение счетчика

Счетчики частот символов сохраняются на дереве в виде чисел с фиксированной разрядностью. Поля разрядов могут переполниться. Число без знака из 16 двоичных разрядов может накапливать счетчик до числа 216 — 1 = 65535. Простейшее решение этой проблемы заключается в наблюдении за ростом счетчика в корне дерева, и, когда он достигает максимального значения, следует сделать изменение масштаба всех счетчиков путем их целочисленного деления на 2. На практике это обычно делается делением счетчиков листьев с последующим вычислением счетчиков всех внутренних узлов дерева. Каждый ...

Модификация дерева

Основная идея заключается в проверке дерева при появлении каждого нового входного символа. Если дерево не является деревом Хаффмана, его следует подправить. Рис. 1.15 дает представление о том, как это делается. Дерево на рис. 1.15а содержит пять символов А, В, С, D и Е. Для всех символов указаны их текущие частоты (в круглых скобках). Свойство Хаффмана означает, что при изучении дерева по всем уровням слева направо и снизу вверх (от листьев к корню) частоты будут упорядочены по возрастанию (неубыванию). Таким образом, нижний левый узел (А) имеет наименьшую частоту, а верхний правый ...