3.5.6. Преобразование Уолша-Адамара

Выше уже упоминалось (см. стр.149), что это преобразование мало эффективно для сжатия данных. Но оно очень быстро, так как его можно вычислять, применяя только сложение, вычитание и, иногда, сдвиг вправо (что эквивалентно делению на 2 двоичного представления величин).

Для заданного блока  пикселов  (здесь  должно быть степенью двойки, ), его двумерное прямое и обратное преобразования Уолша-Адамара (они обозначаются WHT и IWHT, соответственно) определяются с помощью следующих уравнений:

,                      (3.11)

,                (3.12)

где  - это результат преобразования (то есть, коэффициенты WHT), величина  равна биту  в двоичном представлении целого числа , а  определяется с помощью  из следующих рекуррентных соотношений:

                     (3.13)

Рис. 3.42. Упорядоченные ядра WHT при N = 4.

(Напомним, что  определяется из соотношения ). Рассмотрим, например, . Нулевой, первый и второй биты равны соответственно, 0, 1, 1, поэтому ,  и . Величины  и  называются ядрами (или базисными изображениями) WHT. Их матрицы совпадают. Элементами матриц служат числа +1 и -1, которые умножаются на . В результате, преобразование WHT состоит из умножения пикселов на +1 или -1, сложения и деления суммы на . Но поскольку , деление можно делать, сдвигая разряды чисел вправо на  позиций.

Рис. 3.43. Базисные изображения 8x8 для WHT и программа Matlab.

Ядра WHT изображены в графической форме на рис. 3.42 при , где белый цвет означает +1, а черный -1 (для наглядности множитель  опущен). Строки и столбцы в блоках занумерованы значениями  и  от 0 до 3, соответственно. Число смен знаков в строке или в столбце матрицы называется частотностью строки или столбца. Строки и столбцы на этом рисунке упорядочены по возрастанию частотности. Некоторые авторы предпочитают изображать ядра неупорядоченно, так, как это было определено Уолшем и Адамаром ( см. [Gonzalez 92]).

Сжатие изображений с помощью WHT делается так же, как и для DCT с заменой уравнений (3.9) и (3.10) на (3.11) и (3.12).

Пример: На рис. 3.43 изображены 64 базисных изображения WHT и программа для их вычисления и построения на графике. Рассмотрен случай . Каждое базисное изображение - это таблица пикселов размера 8x8.