В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 154
Текст из файла (страница 154)
Это типично для изображений. Как правило, яркость изменяется постепенно, и резкие переходы встречаются нечасто. Соответственно, высокие пространственные частоты вносят в изображение незначительный вклад Важность низкочастотных составляющих иллюстрирует рис. 21.3, на котором показана последовательность частичных султм для етого примера. На каждом графике к сумме добавляется еще одно слагаемое. На первом графгике изображена всего олна составляющая с нулевой частотой, а на последнем — все восемь компонентов взвешенных частот. Уже после сложения первых трех или четырех составляющих общая форма конечной функции становится очевидной, а последние несколько слагаемых мало что меняя>т в общей картине. График в правом нижнем углу рисунка полностью представляет функцию р(х), н чем можно убедиться, сравнив его с рис.
21.1, е. Важность частотного представления изображения, выполненного при помощи дискретного косинусного преобразования, заключается в следующем. Если вклад высокочастотных составляющих невелик, как зто обычно и бывает. тогда можно удалить эти составляющие или представить их меньшим количеством битов. Имея дело с исходным изображением, то есть с пространственной функцией, оперируя в области частот, а не с дискретным косинусным преобразованием, данный тип сжатия осуществить сложно. Двумерное дискретное косинусное преобразование Лвумерное дискретное косинусное преобразование является ключевым для стан- дартов (РЕС и МРЕ0. Как и раньше, мы начнем с математического определения, а затем рассмотрим пример. Определение Так же как любой линейный массив из Хпикселов может быль представлен в виде взвешенной суммы тУ косинусных функций с различными частотами„и матрица из 1т'х )у пикселов может быть представлена нзвешепной суммой ттГх гтт косинус- ных функций.
Формула выглядит следующим образом: р(х,у) = — ~',~~Г~С(и)С(п)с(и,р)соз~ 2 л' 'е-' Г(2х+ 1)яи1 Г(2у+ 1)пи ~ сон " . (21.3) Х „=с „ 2)У ~ ~ ЪЧ 666 Глава 21. Сжатие с потерямн 5(О,О) 1 = —,ХХр( у) 1 Я.(л-( 5(0,0) = — 1) ~) р(х,у). (т =о к=о (21А) (21.5) 7 7 ХХР( У) 5(0, О) = — ~ ~~) т)(х, у) = 8 8.,=о «=о 64 Рнс.
21.3. Суммирование дискретных косинуснык функций дпя примера на рнс. 21.1 Как следует из формулы (21.3), двумерный массив пикселов может быть пред- ставлен произведениями пространственно-частотных компонентов в горизонталь- ~ 21.1. Дискретное косинусное преобразование 667 ном и вертикальном измерениях. Отдельные косинусные сомножители те же самые, что и в одномерном случае. Таким образом, для дискретного косинусного преобразования 8 х 8 используются те же косинусные функции, что и на рис. 21.3. Как и при одномерном преобразовании, слагаемое с нулевой частотой должно быть равно среднему значению функции р(х).
В данном случае зто — 5(0, О)/Х, Поэтому Общая формула для 5(г") выглядит следующим образом: 2 ~(2х+ 1)тти1 Г(2у+ 1)ти)1 5(и, и) = — С(и)С(и) от ~ р(х, у) сов ~, ~ сов~ Формула (21.4) называется двумерным дискретным косинусным преобразованием функции ))(х, у). Пример Мы рассмотрим пример (взятый из 16]), в котором квадратный массив из 64 пикселов (8 х 8) одноцветного изображения подвергается дискретному косинусному преобразоват(ию. В стш(нарте ) РЕС изображения обрабатываются блоками по 8 х 8. Этот размер был выбран по двум причинам. Во-первых, сложность вычислений быстро растет с увеличением размера обрабатываемого блока, поэтому блоки больших размеров оказывают чрезмерное давление на вычислительные ресурсы.
Во-вторых, исследования различных изображений показали, что ограничения обрабатываемой области этими размерами не приводят к существенным потерям точности. На рис. 21.4, и показана матрица значений яркости после смещения уровня в диапазон от — 128 до 127. Обратите внимание на то, что значения пикселов изменяются незначительно.
Это типично для больших изображений: в любом блоке 8 х 8, скорее всего, изменения яркости будут небольшими. Затем производится преобразование: с( )о( )22 !"(2 +!) ! !'(2 +!) В результате датнтых вычислений получается матрица, показанная на рис. 21А. б. Верхний левый элемент матрипы представляет собой значение 5(0, 0), соответствующее среднему значению матрицы, умноженное на 8: 21.2. Волновое сжатие 669 Элементарная волна 2т А, = — ! 6(х)йх, То 2 т А„= — ~ и(х) сгв(2пн !ох)Йх, о 2 В„= — ~ д(х) з!п(2хттДх)бх. Т, рея. 21 Мц Пример двумерного дискретного косинусного преобразования 3начение этого элемента значительно превосходит значения всех остальных элементов, которые уменьшаются с ростом частоты (с удалением от левого верхнего элелоента матрицы). Это типично для многих изображений.
Другими словалои, можно сказать, что большая часть информации в типичном изображении находится в области низкочастотных составляющих. Другими словами, как правило, у изображений нет резких изменений яркости. Для проверки этих значений можно осуществить обратное дискретное косинусное преобразование: р(х, у) = — ~~, ~~> С(и)С(е)5(и, р) соз~ сох ~ ~. (21.6) т Г(2х+ 1)пи1 Г(2у+ 1)по1 4 „=о.=о 16 ~ ~ 16 В результате подобных преобразований мы получим исходные входные данные, показанные на рис. 21А, а. 21.2. Волновое сжатие В последние годы значительный интерес получило использование метода волнового сжатия (гуаче1е1 сошргеевюп) изображений.
Двумя заслуживающими внимания примерами использования данного метода являются система идентификации отпечатков пальцев ФБР и последняя версия широко применяемого стандарта .)РЕС вЂ” )РЕП 2000. Привлекательность метода волнового сжатия заключается во впечатгиктших коэффициентах сжатия при высоких скоростях. Метод волнового сжатия также обладает высокой гибкостью. Например, он позволяет представлять различные области изображения с различными степенями разрешения и точности. Кроме того, метод волнового сжатия хорошо подходит для прогрессивной передачи изображения, при которой сначала передается нечеткая версия изображения.
а более мелкие детали пересылаются в ходе передачи позднее. В этом разделе представляется только краткий обзор этого масштабного и сложного вопроса. Мы начнем с ключевых понятий метода волнового сжатия. В оставшейся части этого раздела обсуткдается метод Хаара (Нааг), являющийся наиболее простым лгетодом волнового сжатия. Хороший способ познакомиться с понятием элементарной волны (жауе!ег) — срав- нениее с представлением функции в виде ряда Фурье. Любая периодическая функ- ция одной переменной д(х) может быть представлена в виде ряда Фурье: и(х) = — + ~ И, сгв(2тту',х) + В„з1п(2яп1,х)$ А, 2 3десь Д представляет собой величину, обратную периоду функции (Д = 1тТ). Частота го называется основной частотой (аппо!ап1епга! (тес)пенсу) или основной гармоникой ((цпс!запев!а! Ьагшошс). Кратные уо частоты называют гармониками (Ьагшошсэ).
Таким образом, периодическая функция с периодом Т моокет быть представлена как сумма синусоид с частотами, кратными частотего = 1/Т, Как правило, разложение в ряд Фурье применяется к функции времени (то есть аргумент х соответствует времени), но эта операция также применима и к пространственной функции, что уместно при обработке изображений. По существу, ряды Фурье показывают, что лтобая периодическая функцли может быть полностью ошгсана суломой синусоид с частотами, кратными основной частоте. Говорят, что ряды Фурье представляют функцию в области частот, тогда как оригинальная функция определена во временной области илп в пространстве в зависил1остн от того, относится аргумент х ко времени или к пространству.
Используемые при разложении в ряд Фурье коэффициенты вычисляются по следующим формулам: Таким образом. по представлению функции в виде ряда Фурье легко восстановить ее временную или пространственную форму. Непериодическая функция тоже может быть представлена в области частот прп помощи преобразования Фурье. В этом случае вместо суммы дискретных гармоник функция представляется в непрерывном диапазоне частот в виде частотного спектра. Однако основные принципы здесь те же. Преобразование Фурье так>хе обратимо, то есть можно по частотному спектру функции получить ее временное или пространственное представление, Понятие представления Фурье можно распространить на двумерные функции и в таком виде использовать для обработки изображений. Анализ Фурье представляет собой мощный инструмент, позволяющий решать многие проблемы, которые очень сложно решать другими методами.
Коэффициетггы Фурье можно вычислять, хранить, передавать и использовать для восстапов- 21.2. Волновое сжатие 671 670 Глава 2ц Сжатие с потерями чво ч л1 Рис. 21.5. Элементарные волны Хзврв 1 1, О<х< —, 2 1 — <х<1, 2 О, в остальных областях. Ч а«(х) 1, яг ' <х< й+ — 2', 21 -1, й+ — 2' <х<(й+1)2', 21 «(х) 1 а«(2 х в) О, в остальных областях. лен«гя исходного сигнала или функции. Прн решении многих проблем значительно проще оперировать коэффициентами Фурье (в области частот), чем исходной функцией (во временной или пространственной области). Однако анализ Фурье плохо подходит для рабаты с функциями, определенными на коротком интервале аргул«ента (в отличие от функций, заданных в диапазоне — < х < + ), а также с функциями, значение которых резко и значительно изменяется.
Такими характеристиками обладают изображения, имеющие ограниченную протяженность в пространстве и, как правило, содержащие резкие края или области с резко изменяющимися характеристиками. Для обработки таких изображений, а также для многих других целей анализ элементарных волн подходит лучше, чем анализ Фурье. Как представление Фурье, волновое представление включает суммирование нескольких элементарных функций. В анализе Фурье в качестве элементарной функции используется синусоида, заданная на всей вещественной аси. В волновом анализе элементарной функцией является элементарная волна, представляющая собой функцию, отличную от нуля только на конечном отрезке значений аргумента и равную нулю для всех остальных значений аргумента.
Функция представляется в виде суммы элементарных волн, каждая из которых, в свою очередь, представляет собой растянутую или суженную единичную элементарную волну, называему«о материнской элементарной волной (шотЬег ъ аче1ег). Путем анализа элементарных волн может быть осуществлено волновое преобразование сигнала, протяженного во времени, или изображения, в результате которого ма>хна получить соответствующие коэффициенты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
