<< Предыдущая Оглавление Следующая >>


5. Алгоритмы быстрых вычислений

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

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

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

Первый этап

Второй этап

При этом для определения элементов матрицы  требуется только  операций, т.е. экономится четыре операции.

Принцип описанный выше на примере преобразования Адамара, можно применить для быстрого вычисления многих других преобразований. Разработаны быстрые алгоритмы для преобразования Фурье, четного косинусного, Адамара. В общем случае для преобразования Карунена-Лоэва быстрого алгоритма не найдено, однако известны приближенные алгоритмы преобразования Карунена-Лоэва для марковских процессов.

 


<< Предыдущая Оглавление Следующая >>