В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 153
Текст из файла (страница 153)
Примером такой обработки является преобразование В11гТ (Вшточз — Ъ'Ьее!ег Тгапз(огш — преобразование Бзрроуза — Унлера). Преобразование ВЖТ выполняется сразу над целым блоком данных; единственное ограничение состоит в размере буфера. Для строки длины Ф преобразование В1ЧТ формирует массив из Лгразличных строк длины Л'. При этом каждый символ в исходной строке используется в качестве начала циклической перестановки исходной строки (это логическая операция; в фактической реализации используются указатели или другой метод экономии памяти).
Например, если исходная строка представляет собой слово ЕБЕРААТ, тогда формируется логическая матрица, показанная ниже слева. Для удобства ряды оригинальной матрицы помечаются по порядку. Затем ряды матрицы сортируются в лексикографическом порядке (по алфавиту), в результате чего получается матрица, показанная ниже справа. Окончательный результат преобразования представляет собой правый столбец показанной справа сортированной матрицы и целые числа, указывающие позицию первого символа оригинальной строки в выходной ст!юке. В нашем примере выходная строка выглядит как РАЯТЕЕЛ, а целое число равно 5. Затем эта выходная строка может быть сжата с помощью обычного алгоритма сжатия, например алгоритма Хаффмана.
После того как сжатые данные распаковываются, исходная строка восстанавливается путем обратного преобразования. 50 Е 5 Е Р Л А Т 84 А А Т Е 8 Е Р 51 5 Е Р Л А Т Е 85 А Т Е Б Е Р А 52 Е Р А А Т Е Я 82 Е Р А А Т Е Б 53 Р Л А Т Е 5 Е 50 Е 8 Е Р Л А Т 84 А А Т Е 5 Е Р 53 Р А А Т Е 5 Е 55 Л Т Е 5 Е Р А 51 8 Е Р Л А Т Е . 56 Т Е 5 Е Р А А 56 Т Е Я Е Р А Л а) на первый взгляд преобразование может показаться необратимым, тем не менее, оно обратимо. Опишите алгоритм обратного преобразования для восстановления исходной входной строки; б) каким образом преобразование ВЪ'Т может улучшить производительность алгоритма сжатия? Барбара Байи ~Руп Ртгс)еля). Коиер Чари Соломона р(х) = ( — ~~Р С(ДЯ(у)ссж~ Г2 ~(2х+ 1)ку' 1 т Ж г=е ы яо> 1г м', псг ои] (21.1) Здесь: /1/ 12,1=0, '11, у'>О.
— = — Хр() 5(0) 1 х> /~ дг„ Глава 21 Сжатие с потерями В Токийском метро сотрулникн заняты нсключитеть- но собиранием потерянной обуви и оторванных в давке рукавов. Слсатие данных без потерь накладывает жеспсую нижнюю границу на размер любого файла илн сообщения. Этой границей является энтропия этого файла. Сжатие данных без потерь позволяет восстановить исходные несжатые данные с точностью до бита, Эта характеристика, как правило, необходима для текстовых файлов, баз данных, двоичных обьектных файлов и т. д.
Однако существует много пшов файлов, для которых не требуется абсолютно точно~о восстановления исходных данных. Примеры таких файлов — аудтю- и видеоклипы, а также неподвижные изображения. В этих случаях допускается некоторое количество ошибок прн восстановлении исходных данных, и может применяться сжатие с потерями. Ключевым вопросом сжатия с потерями является компромисс между коэффициентом сжатия и точностью восстановленных данных. В общем, должно быть ясно, что чем выше коэффициент сжатия для данного алгоритма сжатия, тем ниже точность восстановленных данных. Цель любого алгоритма сжатия с потерями заключается в достижении высоких коэффициентов сжатия за счет потери некоторых битов таким образом, чтобы восстановленные данные были достаточно близки к оригиналу.
Эта глава начинается с описания дискретного косинусного преобразования.' Затем мы изучим волновое сжатие, быстрый и эффективный метод, становящийся все более популярным. Затем мы обсудим стандарт сжатия неподвижных изображений ) РЕЯ. Наконец, последний раздел посвящен стандарту МРЕСч предназначенному для сжатия видеоизображения. 21.1. Дискретное косинусное преобразование Дискретное косинусное преобраювание (1)! всгеге Созше ТгапЫогш, 1) СТ) представляет собой преобразование массива пнкселов в массив значений пространствен- 2цй. Дискретное косинусное преобразование б61 ной частоты'. Это преобразование обратимо с точностью до ошибок округления.
Дискретное косинусное преобразование не производит сжатия, но преобразует информацию об изображении в форму, более удобную для сжатия. Одномерное дискретное косинусное преобразование Будет проще понять работу дискретного косинусного преобразования в двух из- мерениях (именно такая форма применяется в алгоритмах МРЕС и ) РЕП), если мы сначала рассмотрим одномерное дискретное косинусное преобразование.
Определение Предположим, что у нас есть одномерное изображение, представляющее собой линейный массив из Ф пикселов, каждый из которых обозначается некоторым значением яркости)>(х) (О < х < Ж). Таким образом, п(х) представляет собой пространственную функцию (а не функцию времени). Это изображение можно представить в виде суммы пространственно-частотных компонентов с частотами, изменяющимися от 0 до Ргг — 1: Это напоминает представление непрерывной функции в виде ряда Фурье. В данном случае мы представляем дискретную функцию)>(х), а частотные компоненты определены только для дискретных значений частот. Чтобы получить формулу (21.1), нужно вычислить коэффициенты (Яиг), О < /'< )ч). Обратите внимание на то, что первое слагаемое формулы (21.1) представляет собой компонент с нулевой частотой, то есть постоянную составляющую.
Это слагаемое должно быть равно среднему значению р(х). Поэтому ' Функшщ времени может быть выражена во времгииой области путем присвоения значения юяслгв~у моменту времени. Эта функция также может быть про>ссивлепа з виде ряда Фурье илн преобразованияя Фурье, в случае чего мы получаем представление функции в частотиой облигти. Листогтг~по, функция, изменяющаяся в пространстве (в олпом, двух или трех измерениях), могьсг быть прейс гавлепа в виде сумМы или интеграла частотных составляющих, гце кзжаая о жтапляющзя про!жта аз ягч собой синусоиду, язменяюпвчося це во времени, а в тчхстрзнствг. Такие функции назыяаются про.
страитиоеии*сми и ирогтраигтиеиио-частоитыми соо:гиетственно. 662 Глава 21. Сжатие с потерями 1 5(0) = — Хр(х). в(го о гв -,] — огг1т нн [~ * хг]. (21.2) 20 20 Общая формула для 5(/) выглядит следующим образом: Формула (21.2) называется одномерным дискретным косипусным преобразованием функции р(х), а формула (21.1) представляет собой обратное дискретное косинусное преобразование функции 5(/). Пример Расслготрим пример, в которовг блок из восьми пиксслов одноцветного изображения подвергается дискрепгому косинусному преобразованию.
Как правило, двумерное дискретное косинусное преобразование применяется к блоку размером 8 х 8 пикселов, так что данный пример представляет собой вполне реалистичную одномерную версикь В примере для обозначения яркости пикселов используются 8-битовые значения, так что О обозначает белый цвет, а 255 — черный. Это также типично для одноцветных изображений.
43 138 148 183 208 254 248 148 р(0) р(1) д(2) д(3) д(4) д(5) р(6) р(7) — 85 10 20 55 80 126 120 Я(0) Я(1) Я(2) Я(3) Я(4) Я(5) Я(6) Я(7) 122 -129 — 95 26 — 73 4 — 31 -11 — 85 10 20 55 80 128 120 Рис. 21.1. Пример одномерного дискретного кссннусного преобразования На рис. 21.1, а показано исходное изображение, а на рис. 21.1, 6 — вектор зна- чений яркости для этого изображения.
Для удобства вычтем из каждого изобра- / 21.1. Дискретное косииусное преобразование 663 жения 128 — такая операция называется свеи(ениэм уровня (1ече1 эЫ(1) — так, чтобы диапазон всех возможных значений яркости был симметричен относительно О (от — 128 до 127), в результате получим рис. 21.1, а. Затем производится дискретное косинусноспреобразование: 5(/) = — С(/) ~ р(х)соз ~ 1 ' [(2х+ 1)л/1 Эти вычислении соответствуют значениям, показанным на рис. 21.1, к Чтобы проверить полученные значения, сосчитаем обратное дискретное косинусное преобразование: 7 ~(2х+ 1)в/1 р(х) = — ~ С(7)5(/)соз~ 2 7=о 16 В результате мы получим значения, показанные на рис.
21.1, д, которые точно совпадают с исходными значениями. Стоит показать предыдущую формулу в развернутом виде, чтобы подчеркнуть природу дискретного косинусного преобразования: р(х) = — 5(0) соэ[О] + — соз[(2х+ 1)п /161 + 1 5(1) вГ8 2 + — сев[(2х+1)2п/16]+ сов[(2х+1)Зп/16]+ 5(2) 5(3) 2 2 + — (сов[(2х+ 1)4п/16]+ — сов[(2х+ 1)5п/161+ 574) 5(5) 2 2 + — сов[(2х+ 1)бл/16]+ — сов[(2х+ 1)7п/16]. 5(6) 5(7) 2 2 Таким образом, функция р(х) может быть представлена в виде взвешенной суммы восьми косинусных функций. На рис.
21.2 показаны эти восемь функций, называемые базисными косинусными функциями. На каждом графике изображена косинусная функция дискретной пространственной переменной х. Каждая из этих дискретных функций представляет собой обычную косинусную функцию, дискрстиаированную по восьми отсчеталь Этим функциям присуши несколько важных свойств. + Заоеригенность. Взвешенная сумма этих восьми функций может быль вычислена для каждого из восьми значений пиксслов.
+ Минимальность. Ни одна из восьми волновых форм не может быть представлена взвешенной комбинацией других волновых функций, и для завершенности требуются все восемь волновых форм, + Уникальность. Никакой другой набор косинусных функций, кроме масштабированных версий этих восьми волновых форм, не может использоваться для представления всех возможных последовательностей восьми значений пикселов.
664 Глава 2П Сжатие с потерями Здесь 11/ 12, У = О, а ~ 1,/>О для / = и или м Рис. 21.2. Базисные дискретные косинуснье функции Зги свойства также применимы к общему случаю использования Лт косинус- ных функций для предстанления одномерного изображения из Х пикселов. 1 2т гп Дискретное косинусное преобразование 665 Таким образом, любая дискретная функция (р(х), 0 < х < Л) может быть представлена при помощи набора дискретных косинусных функций (соз((2х + 1) х х и//21У), 0 </< )У). Обратите внимание на то, что в данном примере большая часть амплитуд дискретного косинусного преобразования сконцентрирована на низких частотах, включая нулевую частоту (/ = О).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
