10.10. АЛГОРИТМЫ ВЫЧИСЛЕНИЙВ общем случае, чтобы выполнить унитарное преобразование матрицы изображения, содержащей Основной идеей этих быстрых вычислительных алгоритмов является разделение всей задачи на ряд этапов, причем результаты, полученные на предыдущих этапах, многократно используются на последующих этапах. В качестве примера рассмотрим процесс вычисления коэффициентов преобразования Адамара с неупорядоченной матрицей для последовательности из четырех элементов
Для этого необходимо выполнить Первый этап
Второй этап
При этом для определения элементов матрицы Ход вышеуказанных вычислений можно описать с помощью графа (рис. 10.10.1). Общее число операций равно половине числа ребер, соединяющих вершины графа. Другой способ представления того же процесса заключается в факторизации матрицы, когда матрицу преобразования Адамара
Число операций равно половине числа ненулевых элементов в обеих матрицах-сомножителях. Рис. 10.10.1. Граф вычисления коэффициентов преобразовании Адамара для четырехэлементной последовательности. (Сплошные линии обозначают операции сложения, пунктирные - вычитания.) Принципы, описанные выше на примере преобразования Адамара, можно применить для быстрого вычисления многих других преобразований. Разработаны быстрые алгоритмы для преобразований Фурье [35], четного косинусного [12], синусного [13], Адамара [17], Хаара [1] и наклонного [26]. В общем случае для преобразования Карунена-Лоэва быстрого алгоритма не найдено, однако известны приближенные алгоритмы преобразования Карунена-Лоэва для марковских процессов. Для большинства одномерных унитарных преобразований порядок требуемого числа арифметических операций равен Унитарные преобразования, основанные на базисных векторах синусоидального характера (преобразования Фурье, косинусное, синусное), можно выполнить косвенным путем, пользуясь алгоритмом так называемого
Произведя замену переменных
можно получить выражение
Формула (10.10.7) описывает совокупность следующих операций: 1. Поэлементное умножение последовательности 2. Свертка результатов предыдущей операции с ядром 3. Поэлементное умножение полученной последовательности на множители с квадратичной фазой На рис. 10.10.2 приведена структурная схема алгоритма вычисления коэффициентов преобразования Фурье с использованием метода Рис. 10.10.2. Блок-схема алгоритма преобразования Фурье с использованием метода
|