Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Пример

Предполагается, что изображение размера 4x4 уже преобразовано и полученные 16 коэффициентов сохранены в памяти компьютера в виде целых чисел со знаком длины б бит (знаковый бит, за которым следует 5 битов модуля числа). Все они показаны на рис. 4.40 вместе с единственным пространственно ориентированным деревом. Алгоритм кодирования инициализирует список LIP одноэлементным множеством {(1,1)}, список LIS множеством {Р(1,1)}, а список LSP делает пустым. Наибольший коэффициент равен 18, поэтому переменная п равна [l°g2 18J =4. Приведем первые две итерации. Сортировка 1: 2П = 16.

Существен ли (1,1)? Да. Выход: 1. LSP = {(1,1)}. Выход: бит знака: 0. Существенно ли Р(1,1)? Нет. Выход: 0.

LSP = {(1,1)}, LIP - 0, LIS = {£>(1,1)}. На выходе три бита.

Поправка: нет ничего на выходе (эта шаг работает с коэффициентами, отсортированными при итерации п — 1). Уменьшаем п до 3. Сортировка 2: 2П = 8.

Существенно ли Х>(1,1)? Да. Выход: 1. Существен ли (1,2)? Нет. Выход: 0. Существен ли (2,1)? Нет. Выход: 0. Существен ли (2,2)? Нет. Выход: 0. LIP-{(1,2), (2,1), (2,2)}, LIS-{£(1,1)}. Существенно ли £(1,1)? Да. Выход: 1. LIS = {Z>(1,2), £>(2,1), £>(2,2)}. Существенно ли Х>(1,2)? Да. Выход: 1. Существен ли (1,3)? Да. Выход: 1. LSP = {(1,1), (1,3)}. Выход: бит знака: 1. Существен ли (2,3)? Да. Выход: 1. LSP- {(1,1), (1,3), (2,3)}. Выход: бит знака: 1. Существен ли (1,4)? Нет. Выход: 0. Существен ли (2,4)? Нет. Выход: 0. LIP-{(1,2), (2,1), (2,2), (1,4), (2,4)}, LIS = {Z>(2,1), £>(2,2)}. Существенно ли Х>(2,1)? Нет. Выход: 0. Существенно ли Х>(2,2)? Нет. Выход: 0. LIP = {(1,2), (2,1), (2,2), (1,4), (2,4)}, LIS = {23(2,1), 23(2,2)}, LSP = {(1,1), (1,3), (2,3)}. Четырнадцать битов на выходе.

Поправка 2: после итерации 1, в списке LSP находится запись (1,1), чье значение 18 — 100Kb-Один бит на выходе. Уменьшаем п до 2. Сортировка 3: 22-4.

Существен ли (1,2)? Да. Выход: 1.

LSP = {(1,1), (1,3), (2,3), (1,2)}. Выход: бит знака: 1. Существен ли (2,1)? Нет. Выход: 0. Существен ли (2,2)? Да. Выход: 1.

LSP = {(1,1), (1,3), (2,3), (1,2), (2,2)}. Выход: бит знака: 0. Существен ли (1,4)? Да. Выход: 1. LSP = {(1,1), (1,3), (2,3), (1,2), (2,2), (1,4)}. Выход: бит знака: 1.

Существен ли (2,4)? Нет. Выход: 0.

LIP = {(2,1), (2,4)}.

Существенно ли D(2,1)? Нет. Выход: 0.

Существенно ли D(2,2)? Да. Выход: 1.

Существен ли (3,3)? Да. Выход: 1.

LSP = {(1,1), (1,3), (2,3), (1,2), (2,2), (1,4), (3,3)}. Выход: бит

знака: 0.

Существен ли (4,3)? Да. Выход: 1.

LSP = {(1,1), (1,3), (2,3), (1,2), (2,2), (1,4), (3,3), (4,3)}. Выход:

бит знака: 1.

Существен ли (3,4)? Нет. Выход: 0.

LIP = {(2,1), (2,4), (3,4)}.

Существен ли (4,4)? Нет. Выход: 0.

LIP = {(2,1), (2,4), (3,4), (4,4)}.

LIP = {(2,1), (2,4), (3,4), (4,4)}, LIS = {D(2,1)},

LSP={(1,1), (1,3), (2,3), (1,2), (2,2), (1,4), (3,3), (4,3)}.

Шестнадцать битов на выходе.

Поправка 3: после итерации 2, в списке LSP записаны (1,1), (1,3)

и (2,3), со значениями, соответственно, 18 = 100102, 8 = 10002 и

13 = 11012.

Три бита на выходе.

После двух итераций общее число битов на выходе равно 37.

Похожие материалы