Двумерное сжатие с помощью элементарных волн Хаара

Представление в виде элементарных волн Хаара

Представление в виде матрицы

Для вычислений мы можем преобразовать только что описанные операции в про­стые конструкции линейной алгебры. Обратите внимание на то, что первый элемент в преобразованной строке представляет собой просто среднее значение всех точек исходных данных, то есть сумму всех значений, деленную на 8. Второй элемент представляет собой разность средних значений первых и последних четырех то­чек и т. д. Таким образом, мы можем представить данное преобразование в виде следующего произведения вектора и матрицы:

Определим два последних сомножителя в предыдущей формуле как матри­цу W. Мы можем восстановить исходные данные из преобразованных данных с помощью обратной матрицы:

Убедиться в том, что матрица W^-1 является обратной по отношению к W, мож­но, перемножив эти матрицы:

С помощью обратной матрицы W^-1 мы можем восстановить исходные данные из преобразованных данных:

Предыдущая формула предлагает способ выражения преобразования в виде сум­мы элементарных волн Хаара. Вспомним, что нам необходимо сформировать се­мейство элементарных волн, сжимая базовую элементарную волну в разное число раз и смещая ее по оси абсцисс. Таким образом, мы получим элементарную волну полного размера, две элементарные волны половинного размера, четыре элемен­тарные волны размера 1/4 и т. д. С помощью подобных уменьшенных и сдвину­тых элементарных волн мы можем представить ряды обратной матрицы W^-1, как показано на рис. 10.7.

Прежде чем продолжить, определим новую функцию, называемую масштаби­рующей функцией Хаара:

Теперь несложно выразить исходную строку данных в виде суммы элементар­ных волн Хаара и масштабирующей функции Хаара:

Таким образом, мы можем интерпретировать строку как сумму общего средне­го значения и семи элементарных волн, умноженных на соответствующие коэф­фициенты.

Рис. 10.7. Матрица, образованная элементарными волнами Хаара

Одномерное волновое преобразование Хаара заключается в обработке векто­ра-строки значений пикселов длины N = 2ⁿ. Двумерное волновое преобразование Хаара включает обработку матрицы N x N значений пикселов. По существу, при двумерном волновом преобразовании Хаара сначала выполняются операции усреднения и дифференцирования с каждым рядом матрицы пикселов, а затем та же операция выполняется с каждым столбцом результата. Рассмотрим для примера матрицу пикселов 4 x 4:

Первый шаг двумерного волнового преобразования Хаара состоит из одномер­ного преобразования каждого ряда, осуществляемого путем умножения матриц PW, для чего используется версия 4x4 матрицы W, определенной в предыдущем подразделе:

Следующий шаг состоит в выполнении одномерного преобразования каждого столбца. Для этого матрица преобразования столбцов транспонируется, затем умножается на преобразующую матрицу, после чего результат снова транспо­нируется. С тем же успехом можно транспонировать преобразующую матрицу и умножить ее на матрицу преобразованных столбцов:

(10.7)

Здесь знак ' означает транспонирование. Таким образом, двумерное волновое преобразование исходной матрицы Р равно

Преобразованная матрица Т содержит среднее значение всех элементов исход­ной матрицы в левом верхнем углу (8), а остальные элементы соответствуют разностям. Элементы, отстоящие дальше от левого верхнего угла, соответству­ют уровню более точной детализации, то есть более высокочастотным элемен­тарным волнам. Как и раньше, сжатие может осуществляться при помощи по­рогового значения и удаления элементов, значение которых по модулю меньше порога.

Для обратного преобразования выполним следующие действия с формулой (10.7):

(10.8)

Две нужные нам матрицы легко определить:

Таким образом,