3.5.2. Матричные преобразования

Рассмотрим двумерный массив данных, представленный в виде матрицы размером 4x4

.

(здесь в первом столбце стоит вектор из предыдущего примера). Применим наше простое преобразование к каждому столбцу матрицы . Результат равен

.

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

.

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

Далее будут обсуждаться следующие преобразования:

1. Дискретное косинус-преобразование (DCT, discrete cosine transform, см. § 3.5.3 и § 3.7.2) является хорошо изученным и весьма эффективным преобразованием, которое применяется в таких методах компрессии, как JPEG и MPEG. Известные алгоритмы быстрого вычисления DCT делают этот метод особенно притягательным в конкретных приложениях.

2. Преобразование Кархунена-Лоэвэ ( KLT, Karhnnen Loeve transform, § 3.5.8) является теоретически наилучшим с точки зрения концентрации энергии (или, что то же самое, удаления корреляции пикселов). К сожалению, его коэффициенты не фиксированы, а зависят от исходных данных. Вычисление этих коэффициентов (базиса преобразования) делается медленно, как и нахождение самих преобразованных величин. Поскольку преобразование зависит от исходных данных, приходится сохранять его коэффициенты в сжатом файле. По этим причинам, а также из-за того, что DCT дает примерно то же качество, но с большим выигрышем по быстродействию, метод KLT редко используется на практике.

3. Преобразование Уолша-Адамара (WHT, Walsh-Hadamard transform, § 3.5.6) быстро вычисляется (при этом используется только сложение и вычитание), но его характеристики, выраженные в терминах концентрации энергии, хуже, чем у DCT.

4. Преобразование Хаара [Stollnitz 96] является очень простым и быстрым. Оно является простейшим вейвлетным преобразованием, которое будет обсуждаться в § 3.5.7 и в главе 4.