В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 156
Текст из файла (страница 156)
Элементы, отстоящие дальше от левого верхнего угла, соответствуют уровню более точной детализации, то есть более высокочастотныл» элементарным волнам. Как н раньше, сжатие может осуществляться при помоши порогового значения и удаления элементов, значение которых по модулю меньше порога. Для обратного преобразования выполним следующие действия с формулой (21.7): (21.8) (Ъ")-'ТЪУ ' = (%')-гЪ"РЪ'Ж'4 = Р. Две нужные нам матрицы легко определить: 1 1 1 1 1 1 -1 -1 (%") '= 1 — 1 О 0 0 О 1 -1 Таким образом, мы можем интерпретировать строку как сумму общего средне го значения и семи элементарных волн, умноженных на состгветствуюШие коэффициенты. 1 1 1 1 — 1 — 1 — 1 -1 Масштаб 1 1 1 -1 -1 0 0 0 0 Масштаб 2 1 -1 О 0 0 0 0 О Масштаб 4 Рнс.
21.7. Матрица, образованнее элементарными еолнемн Хеара Двумерное сжатие с помощью элементарных волн Хаара Одномерное волновое преобразование Хаара заключается в обработке вектора-строки значений пикселов длины Ф= 2". двумерное волновое преобразование Хаара включает обработку матрицы т1'х 1т'значений пикселов. По существу, при двулсерном волновом преобразовании Хаара сначала выполняются операции усреднения и дифференцирования с каждым рядом матрицы пикселов, а затем та же операция выполняется с каждым столбцом результата.
Рассмотрим для примера матрицу пикселов 4 х 4; 18 14 12 4 10 6 8 8 16 4 8 0 12 0 4 4 1 1 1 1 1 1 -1 -1 2 -2 0 О 0 0 2 -2 12 4 2 4 8 О 2 0 7 3 6 4 5 1 6 О 1 1 1 0 1 1 -1 О 1 -1 0 1 Π— 1 1 — 1 8 2 4 2 2 О -2 0 2 2 О 2 1 1 О 2 67а Глава 21. Сжатие с потерями 21.3. Стандарт дРЕЕ В79 Таким образом, 8 2 4 2 2 0 -2 0 2 2 0 2 1 1 О 2 1 1 1 1 1 1 — 1 — 1 1 -1 0 О 1 1 1 0 1 1 — 1 0 1-101 1 -1 0 -1 0 0 1 -1 14 6 8 4 0 4 2 2 4 4 2 — 2 2 2 2 -2 1 1 1 0 1 1 -1 0 18 14 12 4 10 6 8 8 16 4 8 0 12 0 4 4 1 -1 0 1 1 -1 0 -1 21.3. Стандарт 4РЕО Рио. 21.8. Режимы работы алгоритма.ПРЕС Обьединенная группа экспертов по обработке фотоизображений О ошт Р!тотойгарйу Ехреггэ Сгонр, 1РЕС) представляет собой совместный проект 1ЯО и 1Т(1-Т.
Группа 1РЕС разработала набор стандартов сжатия неподвижных изображений с непрерывно изменяющимся тоном, как монохромных, так и цветных. Стандарт) РЕС создавался как стандарт общего назначения, способный удовлетворить 1пирокий спектр потребностей в таких областях, как настольные издательские системы, графические произведения, передача фотографий по телефонным линиям и использование изображений в медицинских целях. Чтобы осознать необходимость в сжатии изображений, рассмотрим следуюн1ие данные.
Типичное оцифрованное цветное изображение состоит из 512 х 480 пикселов. Каждый пиксел представляется 24 битами (по 8 бит для каждого из трех цветовых составляющих: красного, зеленого и синего). Таким образом, для хранения подобного изображения требуется 737 280 байт. Передача такого изображения по каналу 181)Ы с пропускной способностью 64 Кбит/с займет более полутора минут. Алгоритм сжатия 1РЕС позволяет сохранить »отличнее» качество изображения, оставив информации примерно всего 1 бит на пиксел, то есть сжав изображение в 24 раза.
При таком коэффициенте сжатия объем памяти, занимаемый изображением, уменьшается до 30 720 байт, а для передачи по 64-килобитной линии потребуется менее 4 секунд. Для различных типов изображений требуются разные алгоритмы. Соответственно, стандартом 1РЕС определено четыре режима работы (рис. 21.8): + Последовательный режим работы, основанный на дискретном косинуснои преобразовании.
Каждый компонент кодируется за один проход слева направо, сверху вниз. + Проврвссивный режим работы„основанный на дискретном косинусном нрвобразовании. Изображение кодируется за несколько проходов, для приложений с низкой скоростью передачи данных зто позволяет получателю на- ~ блюдать постепенное появление принимаемого изображения с медленной прорисовкой мелких деталей. Алгоритм этого режима основан на алгоритме последовательного режима. + режим работы без потерь. Изображение кодируется с гарантией точного восстановления оригнна ла.
+ Иерархический режим работы. Изображение кодируется с различным разрешением, так что к уровням низкого разрешения можно получить доступ, не распаковывая изображение с полным разрешением. Этот режим может использоваться вместе с любым из трех других режимов. Последовательный режим 0СТ Последовательный режим ВСТ предоставляет ко»лбинаци1о высоких значений коэффициента сжатия и хорошее качество распакованного изображения.
Обе фазы сжатия и распаковки состоят из трех основных этапов, проиллюстрированных на рис. 21.9. На рисунке показана последовательность шагов для обработки монохромного (однокомпонентного) изображения. Этот алгоритм последовательно обрабатывает поток из блоков монохромного изображения размером 8 х 8. Сжатие цветного изображения включает сжатие каждого из трех компонентов по отдельности. Работая с цветными изображениями, злгоритм может либо обрабатывать каждый компонент как отдельное изображение, либо обрабатывать блоки 8 х 8 кажного компонента по очереди. Прямое дискретное косинусное преобразование Алгоритм сжатия начинает обработку каждого блока 8 х 8, смещая уровень отсче- тов, так что они попадают н диапазон от — 128 до 127.
Затем каждый блок отобра- жается на область частот путем дискретного косинусного преобразования, опре- деленного формулой (21.5). 21.3. Стандарт дРЕО 661 660 Глава 21. Сжатие с потерями Пвт-кодер Исходное изобрюкв низ (8 8 блоков) Сжатое изображение (8 х 8 блоков) ССТ-декодер Искоднсе изобрюкение (эх 8 блоков) постановленное изобрвжение (8 к 8 блоков) Рис. 21.10. Эффект квантования Распаковка Рис. 21.9. Последовательный алгоритм ПРЕС Квантование В результате работы алгоритма дискретного косинусного преобразования (ПСТ) получается матрица коэффициентов.
На вход алгоритма поступает матрица из 8-битовых значений. Для точных значений ПСТ-коэффициентов, как правило, требуется больше разрядов. Квантование уменьшает количество разрядов, необходимое для представления каждого ()СТ-коэффициента, Кроме того, в результате квантования в ПСТ-матрице появляется множество нулевых значений, что позволяет достичь более высоких коэффициентов сжатия. Квантование применяется независимо к каждому из 64 элементов 1)СТ-лсатрицы, причем к различным элементам кнантование может быть применено в разной степени.
В любом случае низкочастотные компоненты квантуются в меньшей степени, чем высокочастотные. Причина этого в том, что гизменения высокочастотных составляюсцих менее заметны. чем низкочастотных, Квантование реализуется через таблицу квантования 8 зс 8, пример которой показан на рис. 21.10 а. Для заданной таблицы квантования с элементами Д(и, о) и ПСТ-матрицы с элементами 5(и, с) выполняются следующие вычисления: К(и,о)=гоппс( = ' ) +0,5 . '( Ц(и,о)~ ~Я(и,о) Здесь (х) представляет собой максимальное целое число, меньшее х, Эта функ- ция округляет до ближайшего целого значения.
Например, гошн1(8/16) = гоипс((0,5) = 1, гоппс((7/16) = гоши((0,4375) = О, гоипс((8/15) = пшпс((0,533) = 1, гоцпс1(7/15) = гоппс((0,466) = 1. Если число меньше, чем половина коэффициента квантования, тогда оно округляется до нуля. При тщательном подборе таблицы квантования можно добиться высокого коэффициента сжатия при еле заметных для человеческого глаза искажениях. Стандартом 4 РЕС не определяется точное содержание таблицы квантования, а предлагается набор таблиц, одна из которых показана на рис. 21.10, а. На рис. 21,10, б показан результат применения этой таблицы к Е)СТ-матрице, представленной на рис.
21 4, Гг. В результате квантования многие члены матрицы обнуляются, что увеличивает эффективность сжатия. Сжатие без потерь Последняя основная фаза процесса сжатия заключается в применении алгоритма сжатия без потерь. Этот алгоритм включает два подготовительных этапа, за которыми следует фактическое кодирование. Сначала элемент (О, 0) квантованной ПСТ-матрицы, представляющий собой среднее значение всех пикселов блока, кодируется относительно такого же элемента предыдущего блока: П1РР = 1)Сс — РВ.ЕП.
Здесь 1)1РР представляет собой результат разностного кодирования, 1)С, — элемент (О, 0) 1-го блока 8 х 8, а РКЕП вЂ” элемент (О, 0) предыдущего блока. Подобное разностное кодирование эффективна по двум причинам. Во-первых, высока корреляция средних значений двух соседних блоков. Во-вторых, средние значения часто содержат значительную долю общего значения изображения.
Затем остальные значения матрицы упорядочиваются зигзагообразно, как показано на рис. 21.11 (шахлтатная клетка нанесена для наглядности). Посколысу 662 Глава 21. Сжатие с потерями 21.3. Стандарт.>РЕЯ 663 Увеличение Компонент с нулевой частотой Увеличение вертикальной частоты Рис. 21.12. Восстановление иэображения Я(7, 7) Рис. 21.11. Зигзагообразное сканирование Распаковка многие высокочастотные компоненты с большой вероятностью равны О, в результате такого упорядочивания появляются длинные последовательности нулей, которые могут быть заменены символом конца блока. Например, последовательность для матрицы на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
