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