3.5.1. Ортогональные преобразования

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

,

которая в общем случае примет следующий вид: . Каждый вектор-столбец матрицы  называется «базисным вектором».

Важной задачей является определение коэффициентов преобразования . Основное требование заключается в том, чтобы после преобразования величина  была бы большой, а все остальные величины  стали бы малыми. Основное соотношение  предполагает, что  будет большим, если веса  будут усиливать соответствующие величины . Это произойдет, например, если компоненты векторов  и  имеют близкие значения и одинаковые знаки. Наоборот,  будет малым, если веса  будут малыми, и половина из них будет иметь знак, противоположный знаку соответствующего числа . Поэтому, если получаются большие , то векторы  имеют сходство с исходным вектором , а малые  означают, что компоненты  сильно отличаются от . Следовательно, базисные векторы  можно интерпретировать как инструмент для извлечения некоторых характерных признаков исходного вектора.

На практике веса  не должны зависеть от исходных данных. В противном случае, их придется добавлять в сжатый файл для использования декодером. Это соображение, а также тот факт, что исходные данные являются пикселами, то есть, неотрицательными величинами, определяет способ выбора базисных векторов. Первый вектор, тот, который, порождает , должен состоять из близких, возможно, совпадающих чисел. Он будет усиливать неотрицательные величины пикселов. А все остальные векторы базиса должны наполовину состоять из положительных чисел, а на другую половину - из отрицательных. После умножения на положительные величины и их сложения, результат будет малым числом. (Это особенно верно, когда исходные данные близки, а мы знаем, что соседние пикселы имеют, обычно, близкие величины.) Напомним, что базисные векторы представляют собой некоторый инструмент для извлечения особенностей из исходных данных. Поэтому хорошим выбором будут базисные векторы, которые сильно различаются друг от друга и, поэтому, могут извлекать разные особенности. Это приводит к мысли, что базисные векторы должны быть взаимно ортогональными. Если матрица преобразования  состоит из ортогональных векторов, то преобразование называется ортогональным. Другое наблюдение, позволяющее правильно выбирать базисные векторы, состоит в том, что эти векторы должны иметь все большие частоты изменения знака, чтобы извлекать, так сказать, высокочастотные характеристики сжимаемых данных при вычислении преобразованных величин.

Этим свойствам удовлетворяет следующая ортогональная матрица:

.                      (3.5)

Первый базисный вектор (верхняя строка ) состоит из одних единиц, поэтому его частота равна нулю. Все остальные векторы имеют две +1 и две -1, поэтому они дадут маленькие преобразованные величины, а их частоты (измеренные количеством смен знаков в строке) возрастают. Эта матрица подобна матрице преобразования Адамара Уолша (см. уравнение (3.11)). Для примера, преобразуем начальный вектор (4,6,5,2):

.

Результат вполне ободряющий, поскольку число  стало большим (по сравнению с исходными данными), а два других числа стали малыми. Вычислим энергии исходных и преобразованных данных. Начальная энергия равна , а после преобразования энергия стала , что в четыре раза больше. Энергию можно сохранить, если умножить матрицу преобразования  на коэффициент 1/2. Новое произведение  будет равно . Итак, энергия сохраняется и концентрируется в первой компоненте, и она теперь составляет  от общей энергии исходных данных, в которых на долю первой компоненты приходилось всего 20%.

Другое преимущество матрицы  состоит в том, что она же делает обратное преобразование. Исходные данные (4,6,5,2) восстанавливаются с помощью произведения .

Теперь мы в состоянии оценить достоинства этого преобразования. Квантуем преобразованный вектор (8.5,1.5,–2.5,0.5) с помощью его округления до целого и получаем (9,1,–3,0). Делаем обратное преобразование и получаем вектор (3.5,6.5,5.5,2.5). В аналогичном эксперименте мы просто удалим два наименьших числа и получим (8.5,0,–2.5,0), а потом сделаем обратное преобразование этого грубо квантованного вектора. Это приводит к восстановленным данным (3,5.5,5.5,3), которые также весьма близки к исходным. Итак, наш вывод: даже это простое и интуитивное преобразование является хорошим инструментом для «выжимания» избыточности из исходных данных. Более изощренные преобразования дают результаты, которые позволяют восстанавливать данные с высокой степенью схожести даже при весьма грубом квантовании.

Одни художники отображают солнце в желтое
 пятно, а другие желтое пятно в солнце.
- Пабло Пикассо