Программные методы защиты информации. Часть 1. Крыжановская Ю.А. - 31 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

31
гибкость будет гораздо выше, чем у ближайшего “конкурента” — алгоритма
JPEG. Коэффициент компрессии - 2-2000 - задается пользователем .
Рекурсивный (волновой) алгоритм
Английское название рекурсивного сжатия — wavelet. На русский язык оно
переводится как волновое сжатие и как сжатие с использованием всплесков . Этот
вид архивации известен довольно давно и напрямую исходит из идеи использова-
ния когерентности областей . Ориентирован алгоритм на цветные и черно - белые
изображения с плавными переходами. Идеален для картинок типа рентгеновских
снимков . Коэффициент сжатия задается и варьируется в пределах 5-100. При по-
пытке задать больший коэффициент на резких границах , особенно проходящих по
диагонали, проявляется “лестничный эффект” — ступеньки разной яркости раз-
мером в несколько пикселов .
Идея алгоритма заключается в том , что мы сохраняем в файл разницу —
число между средними значениями соседних блоков в изображении, которая
обычно принимает значения , близкие к 0.
Так , два числа a
2 i
и a
2 i+1
всегда можно представить в виде b
1
i
=(a
2i
+a
2i+1
)/2 и
b
2
i
=(a
2
i
-a
2
i+1
)/2. Аналогично последовательность a
i
может быть попарно переведе-
на в последовательность b
1,2
i
.
Пример 24: пусть сжимается строка из 8 значений яркости пикселов (a
i
):
(220, 211, 212, 218, 217, 214, 210, 202). Получим следующие последовательности
b
1
i
, и b
2
i
: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Заметим , что значения b
2
i
доста-
точно близки к 0. Повторим операцию , рассматривая b
1
i
как a
i
. Данное действие
выполняется как бы рекурсивно , откуда и название алгоритма. Мы получим из
(215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты ,
округлив до целых и сжав , например, с помощью алгоритма Хаффмана с фикси -
рованными таблицами, мы можем поместить в файл.
Заметим , что преобразование к цепочке применялось только два раза. Ре-
ально можно позволить себе применение wavelet-преобразования 4-6 раз. Более
того, дополнительное сжатие можно получить , используя таблицы алгоритма
Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана
для ближайшего в таблице значения ). Эти приемы позволяют достичь заметных
коэффициентов сжатия .
Алгоритм для двумерных данных реализуется аналогично. Если у нас есть
квадрат из 4 точек с яркостями a
2i,2j
, a
2i+1
, 2j, a
2i, 2j+1
, и a
2i+1
, 2j+1, то
Исходное B
1
B
2
изображение B
3
B
4
Используя эти формулы , мы для изображения 512х512 пикселов получим
после первого преобразования 4 матрицы размером 256х256 элементов . 
                                            31
гибкость будет гораздо выше, чем у ближайшего “конкурента” — алгоритма
JPEG. Коэффициент компрессии - 2-2000 - задается пользователем.
Рекурсивный (волновой) алгоритм
        Английское название рекурсивного сжатия — wavelet. На русский язык оно
переводится как волновое сжатие и как сжатие с использованием всплесков. Этот
вид архивации известен довольно давно и напрямую исходит из идеи использова-
ния когерентности областей. Ориентирован алгоритм на цветные и черно-белые
изображения с плавными переходами. Идеален для картинок типа рентгеновских
снимков. Коэффициент сжатия задается и варьируется в пределах 5-100. При по-
пытке задать больший коэффициент на резких границах, особенно проходящих по
диагонали, проявляется “лестничный эффект” — ступеньки разной яркости раз-
мером в несколько пикселов.
        Идея алгоритма заключается в том, что мы сохраняем в файл разницу —
число между средними значениями соседних блоков в изображении, которая
обычно принимает значения, близкие к 0.
        Так, два числа a2i и a2i+1 всегда можно представить в виде b1i=(a2i+a 2i+1)/2 и
b 2i=(a2i-a2i+1)/2. Аналогично последовательность ai может быть попарно переведе-
на в последовательность b1,2i.
        Пример 24: пусть сжимается строка из 8 значений яркости пикселов (a i):
(220, 211, 212, 218, 217, 214, 210, 202). Получим следующие последовательности
b 1i, и b2i: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Заметим, что значения b2i доста-
точно близки к 0. Повторим операцию, рассматривая b 1i как ai. Данное действие
выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из
(215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты,
округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фикси-
рованными таблицами, мы можем поместить в файл.
        Заметим, что преобразование к цепочке применялось только два раза. Ре-
ально можно позволить себе применение wavelet-преобразования 4-6 раз. Более
того, дополнительное сжатие можно получить, используя таблицы алгоритма
Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана
для ближайшего в таблице значения). Эти приемы позволяют достичь заметных
коэффициентов сжатия.
        Алгоритм для двумерных данных реализуется аналогично. Если у нас есть
квадрат из 4 точек с яркостями a 2i,2j, a 2i+1, 2j, a2i, 2j+1, и a2i+1, 2j+1, то




                Исходное              B1    B2
                изображение          B3    B4
      Используя эти формулы, мы для изображения 512х512 пикселов получим
после первого преобразования 4 матрицы размером 256х256 элементов.

Страницы