Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Преобразование Кархунена-Лоэвэ

Преобразование Кархунена-Лоэвэ (его еще называют преобразованием Хотеллинга) имеет наилучшую эффективность в смысле концентрации энергии изображения, но по указанным выше причинам, оно имеет скорее теоретическое, нежели практическое значение. Данное изображение следует разделить на к блоков по п пикселов в каждом, обычно, п — 64, но допускаются и другие значения, а число к зависит от размера изображения. Рассматриваются векторы блоков, которые обозначаются Ъ^г\ при г = 1,2,..., к. Усредненный вектор равен b - (Eib(0) А- Вводится новое семейство векторов v(2) _ ^(i) _ g дЛЯКОТОрОГО усредненный вектор (]Tjv^) А равен нулю. Матрицу преобразования (KLT) размера п х п, которую мы будем строить, обозначим через А. Результатом преобразования вектора v^ будет весовой вектор w^ = Av'1'. Усреднение вектора w^ также равно нулю. Построим матрицу V, столбцами которой будут служить векторы v^. столбцами w^ :

Рассмотрим также матрицу W со

V=(v(1>v(2),...,vW),W=(w<1>W(2»,...,W«).

Матрицы V и W имеют п строк и к столбцов. Из определения векторов w(2) заключаем, что W = А • V.

Все п векторов коэффициентов с^ преобразования Кархунена-Лоэвэ определяются равенствами

c^ = (wf\wf\...,wf)),j = l,2,...,n.

Таким образом, вектор с^^ состоит из j-ых элементов весовых векторов w^ при г = 1,2,..., &.

Рассмотрим матрицу-произведение W • WT. Элемент строки а и столбца Ь этой матрицы равен сумме произведений

(W • WT) =J2 и£Ц° = £ 4а)с^ = с<а» • с<*>, для а, Ъ € [1, п].

(3.17) Тот факт, что среднее каждого вектора w^ равно нулю означает, что каждый диагональный элемент (W • WT) .. матрицы-произведения является дисперсией (с множителем A:) j-ro элемента (или j-ои координаты) вектора w^

В недиагональные элементы матрицы (W • WT) являются ковариа-циями векторов w^, то есть, элемент (W • WT) . равен ковариации координат а и 6 векторов w^. Из уравнения (3.17) также видно, что эти величины равны скалярным произведениям с^ • с^ векторов с^а) и с^. Одной из основных задач преобразования изображения является приведение его к декоррелированной форме координат векторов. Теория вероятности говорит о том, что две координаты являются декоррелированными, если их ковариация равна нулю (другая цель - это концентрация энергии, но эти две задачи тесно связаны). Значит, необходимо найти матрицу А, такую, что произведение W • WT будет диагональной матрицей. Из определения матрицы W находим, что

W • WT = (AV) • (AV)T = A (v • VT) AT.

Матрица V • VT является симметрической, ее элементами служат ковариации координат векторов v^

Раз матрица V • VT - симметрическая, то ее собственные векторы ортогональны. Нормализуем их (то есть, сделаем их ортонормаль-ными) и выберем их в качестве строк матрицы А. 

При таком выборе матрицы А матрица W • WT будет диагональной, причем элементы диагонали являются собственными числами матрицы V • VT. Матрица А служит матрицей преобразования Кархунена-Лоэвэ; ее строки являются базисными векторами KLT, а энергией (дисперсией) преобразованных векторов служат собственные числа Ai, А2,..., Ап матрицы V • VT.

Базисные векторы для KLT вычисляются с помощью пикселов исходного изображения, то есть, они зависят от исходных данных. В конкретном методе сжатия эти векторы следует записывать в сжатый файл для использования декодером. Кроме того не известен быстрый метод вычисления этих векторов. Все эти факты делают метод KLT сугубо теоретическим без реальных приложений.