В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 155
Текст из файла (страница 155)
Как и в случае анализа Фурье, эти коэффициенты позволяют упростить обработку сигнала или изображения. Простейшая элементарная волна, прил«еняемая в волновом анализе, называется элементарной волной Хаара (Нааг мате!ет) и определяется следующим образом: Из этой базовой элементарной волны мы можем получить следуюшии набор функций: На рнс. 21.5 показаны некоторые из этих элементарных волн Хаара. Обратите внимание на то, что с увеличением парал«стра 1 элементарная волна становится более короткой, то есть частота элементарной волны растет.
Параметр й сдвигает элементарную волну по оси х (во времени или в пространстве), Волновое представление позволяет использовать так называемый анализ с перемен««ым разрешеиики («по10гезо1п11оп апа1увЬ). Сжатые версии базовой алементарной волны, сдвинутые в соответствующие области сигнала или изображения, могут представлять высокочастотные составляющие. Несжатые версии базовой элементарной волны соответствуют низкочастотным, медленно изменяющимся компонентам. Добавляя все более сжатые элементарные волны, можно представлять сигнал или изображение с произвольной степенью разрешения или точности.
Более того„подобное представление с переменным разрешением люжет найти очевидное применение для сжатия и прогрессивного преобразования: + Изображение можно сжать, отбросив коэффициенты с относительна небольшими значениями. В результате будут отброшены элементарные волны, вклад которых в формирование изображения невелик. + Передачу изображения по сети можно начинать с низкочастотных компонентов.
По мере приема более высокочастотных компонентов к изобра«кению будет добавляться все больше деталей, а разрешение изображения будет увеличиваться, то есть изображение будет становиться четче. Одномерное сжатие с помощью элементарных волн Хаара Чтобы понять, как можно использовать элементарные волны Хаара для сжатия изображения в одном направлении, воспользуемся примером из ~159). 672 Глава 21.
Сжатие с потерями 21.2. Волновое сжатие 673 Рассмотрим строку из восьми значений данных, которые могут быть рядом из матрицы 8 к 8 пикселов, значение каждого из которых соответствует яркости, Их значения равны. 64 48 16 32 56 56 48 24 Мы будем преобразовывать изображение в три этапа, используя процесс, называемый усреднением и дифференцированием: 64 48 16 32 56 56 48 24 56 24 56 36 8 -8 О 12 40 46 16 10 8 -8 0 12 43 -3 16 10 8 -8 О 12 На первом шаге вычисляются средние значения последовательных пар чисел из исходной строки. в результате чего получа»отея первые четыре числа второй строки.
Остальные четыре значения второй строки вычисляются как разности тех >ке пар чисел первого ряда. Таким образом, последние четыре числа второго ряда прсдставля»от собой уровень более мелкой детализации, отра>кзющи»3 изменения изображения. Первые четыре числа отражают фоновый уровень, к которому для воспроизведения оригинального изображения необходимо добавить более мелкие детали. На следующем шаге обрабатываются только первые четыре числа, которые снова попарно усредняются и дифференцируются. В результате мы получаем два числа, представляюшие уровень меньшей степени детализации.
На последнем шаге усредняются и дифференцируются два первых значения предыдущего ряда. Все разностные значения показаны полужирным шрифтом. Обратите внимание на то, что первое значение последнего ряда представляет собой среднее значение всех восьми чисел исходного изображения. Мы ма>кем сделать несколько наблюдений: + Этот процесс обратим. Путем соатветствуюших сложений и вычитаний мы можем снова получить из последнего ряда исходный ряд. + Этот процесс можно обобщить применительно к строкам любой длины. Для строки из 2» элементов требуются 7» этапов обработки.
Любая строка, длина которой не равна степени 2, может быть дополнена пулял»и. + Области, в которых исходныс данные изменяются незначительно, после преобразования выглядят как последовательносги неболыних или нулевых значений. + Преобразованное представление позволяет осуществить сжатие без потерь, так как обычно преобразованные данные содержат нулевые значения. В нашем примере седьмой элемент в преобразованном представлении равен нулю. Путем группового кодирования можно получить сжатую версию.
+ Значительно большей степени сжатия, хотя и с потерями данных, можно добиться„игнорируя области малых изменений. Чтобы продемонстрировать последнее утверждение, зададим некоторое пороговое значение е и обнулим все злементы преобразованной строки, модуль которых не превышает е. Например, при пороговом значении 4 из строки удаляется второй элемент, в результате чего получится строка (43, О, 16, 10, 8, — 8, О, 12). Поместим эту строку в последний ряд пустой таблицы и вычислим по ней исходные данные: 67 51 19 35 53 53 45 21 59 27 53 33 8 -8 0 12 40 43 16 10 8 -8 О 12 43 0 16 10 8 -8 0 12 На рис. 21.6, а полученный результат сравнивается с исходными данными, Соответствие оказывается довольно близким.
На черно-белом дисплее эти два изображения были бы практически идентичными. Теперь установим пороювое значение е = 8. При этом мы устраним ец»е два элемента в сжатой строке и получим строку (43, О, 16, 10, О, О, О, 12). Распакуем эту строку: (59, 59, 27, 27, 53, 53, 45, 21) Этот результат сравнивается с исходными данными на рис. 21. 6, б. Данное приближение основывается только на пяти из исходных восьми значений, но прцбли>кение остается довольно неплохим. 60 70 40 1 3 30 20 10 0 0 ! 1 2 3 4 6 6 7 6 1 2 3 4 6 6 7 В Исходные данные - — -Данные после сжатия Рис. 21.6.
Сжатие при помощи элементарных волн Хаара Представление в виде матрицы Для вычислений мы можем преобразовать только что описанные операции в простые конструкции линейной алгебры. Обратите внимание на то, что первый элеме»п' в преобразованной строке представляет собой просто среднее значение всех точек исходных данных, то есть сумму всех значений, деленную на 8.
Второй элемент ег4 Глава 21. Сжатиес потерями 21.2. Волновое сжатие 6 г5 представляет собой разность средних значений первых и последних четырех то- чек и т. д. Таким образом, мы можем представить данное преобразование в виде следующего произведения вектора и матрицы: 1 1 2 0 1 1 2 0 1 1 -2 0 1 1 — 2 0 (64 48 16 32 56 48 24) х — х 8 1 — 1 0 2 1-102 1 -1 Π— 2 1 -1 Π— 2 = (43 -3 16 10 8 — 8 0 12). Определим два последних сомножителя в предыдущей формуле как матрицу %'. Мы можем восстановить исходные данные из преобразованных данных с помощью обратной матрицы: 1 1 1 -1 -1 -1 Убедиться в том, что матрица Ъг ' является обратной по отношению к (т', можно, перемножив эти матрицы: 1 1 1 — 1 — 1 — 1 1 1 1 1 1 1 1 1 1 — 1 1 1 -1 -1 О О 0 0 О 1 1 -1 О 0 0 О О 1 — 1 О 0 0 0 0 1 0 0 0 0 0 0 О 0 1 — 1 -1 0 0 0 О 0 0 1 х — х 8 — 1 О О 0 1 -1~ 1 1 1 1 1 1 1 1 1 -1 1 1 — 1 -1 0 0 0 0 О 1 1 — 1 0 0 0 0 О 1 — 1 0 О 0 0 О 1 0 0 0 О 0 0 О 0 1 — 1 — 1 0 0 0 0 0 0 -1 0 О 0 1 -1 4 О О 0 -4 0 0 0 0 4 0 0 0 — 4 0 0 0 0 4 0 0 О -4 0 О 0 0 4 О 0 0 — 4 1 0 0 0 0 0 0 О 1 0 0 0 0 0 0 0 1 0 0 0 О 0 0 О 1 0 0 О 0 0 0 0 1 О О 0 0 0 О 0 1 0 0 0 0 0 0 О 1 0 0 0 О 0 0 0 1 1 2 1 1 2 0 0 0 1 1 -2 1 1 -2 1 — 1 0 1 -1 0 1 — 1 0 1 -1 0 С помощью обратной матрицы %'-' мы можем восстановить исходные данные из преобразованных данных: 1 1 1 1 1 1 1 1 1 1 -1 -1 О 0 0 0 1 -1 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 1 1 1 1 -1 -1 — 1 -1 (43 — 3 16 10 8 -8 0 12) х = (64 48 16 32 56 48 24) Представление в виде элементарных волн Хаара Предыдущая формула предлагает способ выражения преобразования в виде суммы элементарных волн Хаара.
Вспомним, что нам необходимо сформировать семейство элементарных волн, сжимая базовую элементарную волну в разное число раз и смещая ее по оси абсцисс. Таким образом, мы получим злементарную волну полного размера, две элементарные волны половинного размера, четыре элементарные волны размера 1/4 и т. д. С помощью подобных уменьшенных и сдвинутых элементарных волн мы можем представить ряды обратной матрицы %-', как показано на рис. 21.7.
Прежде чем продолжить, определим новую функцию, называемую масштабируюшей функцией Хаара; 1, если О<х<1, ор(х) = 0 в противном случае. Теперь несложно выразить исходную строку данных в виде суммы элементарных волн Хаара и масштабирующей функции Хаара: Ф 43 гр(х) — 3Ч'оо+ 16Ч'со+ 10Ч'с1 + 8Ч'ао — 8%л + ОЧ'м + 12Ч'ож 0 4 О О О О -4 О 0 О 0 О 4 0 0 0 0 — 4 0 0 2 0 0 4 0 2 0 0 -4 0 -2 0 0 0 4 -2 0 ΠΠ— 4 О 0 О 0 1 1 — 1 -1 0 0 О О О 0 0 0 1 — 1 О О 0 0 1 -1 б7Б Гпава 21. Сжатие с потерямн 21.2. Волновое сжатие 677 Первый шаг двумерного волнового преобразования Хаара состоит из одномерного преобразования каждого ряда, осушествляемого путем умножения матриц РЮ, для чего используется версия 4 х 4 матрицы Ж, определенной в предыдущем подразделе: Г сст ° 18 14 12 4 1 1 2 0 12 4 2 4 1 1 — 2 О 1-102 1 -1 0 — 2 8 0 2 0 7 3 6 4 5 1 6 0 10 6 8 8 16 4 В 0 12 0 4 4 1 х — х 4 Следуюц1ий шаг состоит в выполнении одномерного преобразования каждого столбца.
Для этого матрица преобразования столбцов транспонируется, затем умножается на преобразующую матрицу, после чего результат снова транспонируется. С тем жс успехом можно транспонировать преобразующую матрицу и умножить ее на матрицу преобразованных столбцов: Масштаб 2 0 О 0 0 1 1 -1 -1 (21.7) Т = ((РЮ)'Ю)' = %"РЖ. Здесь знак ' означает транспонирование. Таким образом, двумерное волновое преобразование исходной матрицы Р равно Масштаб 4 — Ч~г— О О 1 -1 0 0 0 0 Т=%"РЪ'= — х 1 4 Масштаб 4 0 0 0 0 1 — 1 0 0 Масштаб 4 0 0 0 0 0 0 1 -1 Преобразованная матрица Т содержит среднее значение всех элементов исходной матрицы в левом верхнем углу (8), а остальные элементы соответствуют разностям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
