Главная > Моделирование, обработка сигналов > Быстрые алгоритмы в цифровой обработке изображений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.3.1. Лево-циркулянтное преобразование порядка 2

Фаза 1

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

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

Рис. 4.1. Алгоритм порядка 2

Равенства указаны на изображении с использованием символики для умножения, принятой в Фортране.

Напомним, наконец, что основное выражение (4.45) полностью симметрично относительно Это удобное свойство использовано в принятых здесь обозначениях. Итак, наряду с каждым которое является функцией (скажем, определяемой таблицей, имеется переменная а», которая является точно такой же функцией

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

Имея это в виду, учитываем только те арифметические операции, которые явно указаны в схеме алгоритма. В нашем случае это 2 умножения и 4 сложения, для которых выбраны обозначения приведенные на рис. 4.1. Заметим, что 2 умножения — это тот минимум, который определяется теоремой Винограда (см. правую колонку в табл. 4.1).

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