§ 12. Дискретное и быстрое преобразования Фурье

Циекретное преобразование Фурье представление тригонометрического ряда Фурье, которое связывает идеальные отсчеты изображения, имеющею конечные размеры, с идеальными

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

Конечно, реальных измерениях нельзя получить идеальные отсчеты. Формула (12.1) практически означает следующее: «эффективная ширина полосы спектра пространственных частот» [величина, определенная и § 6, см. абзац после формулы (6.11)] намного меньше где А — меньшее из значений А, и

Поскольку изображение имеет конечные размеры, к нему применимы формулы (10.1) и (10.2), так что отсчеты изображения следующим образом связаны с отсчетами его фурьс-спектра:

Желательно было бы найти формулу, аналогичную формуле (12.2), определяющую каждое значение как сумму значений Такую формулу можно получить, если величины выбираются как целые кратные величин А, и например:

В этом случае справедливо соотношение

при всех целых числах -символ Кронекера определен равенствами (9.9). Следовательно, левая часть равенства (12.4) есть «дискретная дельта-функиия», которая играет ту же самую роль по отношению к рядам Фурье, что и дельта-функция 6 по отношению к интегралам Фурье. Умножая значения на и проводя суммирование от до по и от до по получаем

что прямо следует из соотношений (12.2) и (12.4).

Теперь применим методы, введенные в данном параграфе, а также в § 10. к функции которая в § 4 называлась идеальным искаженным изображением. Рассмотрим формулу (3.4). Любая ФРТ имеет практически конечную протяженность в том смысле, что она пренебрежимо мала вне некоторой конечной области плоскости изображения. Кадром рассеяния точки, обозначаемым через (согласно обозначениям, введенным в § 7), будем называть прямоугольник со сторонами, параллельными осям х и у, достаточно большой, чтобы в него точно вписывалась указанная выше область. Область можно построить, поместив центр области на внешней границе кадра и затем обойдя всю границу. Наружные края области опишут периметр области Теперь представим себе, что плоскость изображения покрывается бесконечным множеством смежных неперекрываюшихся прямоугольников, каждый из которых имеет те же размеры, что и область На каждый из этих прямоугольников накладывается кадр того же размера, что и область 1), с центром, совпадающим с центром данного прямоугольника. Идеальное искаженное изображение будет повторяться в каждом из этих кадров. Внешние части смежных изображений перекрываются, поскольку перекрываются смежные кадры. Получающееся при этом периодическое изображение о называемое периодически продолженным (с перекрыванием) идеальным искаженным изображением, может быть представлено в виде

причем пространственные периоды этого изображения равны соответствующих периодов изображения определенных в § 10. Обозначив из упоминаемых выше смежных не перекрывающихся друг с другом прямоугольников через с учетом определений (6.12) и можно вывести из формулы (12.6) следующее выражение:

причем в каждом слагаемом второй суммы величины х и у равны, соответственно, выражениям первой суммы, так что каждая область интегрирования в первой сумме становится областью во второй сумме. Обратимся теперь к равенству (12.4) и посмотрим, что получится, если умножить обе его части на величину

и перейти к пределу при . Как нетрудно видеть, дельта-символ Кронекера переходит в дельта-функцию Дирака; например:

что после подстановки в соотношение (12.7) вместе с определением

дает

Поскольку из формул (3.4), (12.9) и теоремы о свертке (7.7) следует равенство

где функции, определенные в § 6 и 8, соответственно, выражение (12.10) сводится к виду

где [в силу формул (6.4). (10.4) и (12.11)]

Эта формула обсуждается далее в § 14.

Формулами (12.2) и (12.5), которые соответствуют формулам преобразования Фурье (6.13) и (6.12), определяется дискретное преобразование Фурье (ДПФ). Идеальные отсчеты изображения, входящие в эти формулы, являются идеальными отсчетами самогб истинного изображения при условии, что оно не выходит за пределы прямоугольника а значения равны нулю при При этих условиях ДПФ может быть столь же «точным», как и обычное преобразование Фурье.

ДПФ является теоретической основой для вывода алгоритма быстрого преобразования Фурье (БПФ). который революционизировал многие методы численного расчета спектров. Алгоритм БПФ будет представлен ниже в данном параграфе. Его вычислительная эфективность столь высока, что даже при вычислении свертки лучше всего, пользуясь теоремой о свертке (7.7). проводить компьютерные расчеты по схеме При вычислении корреляции необходимо аналогичным образом использовать теорему о корреляции (7.8). Заметим, что программы БПФ, как правило, ориентированы на число отсчетов сигнала, равное некой целой степени двойки.

В этом случае суммирование не может проводиться в симметричных пределах, как в формулах (12.2) и (12.5). Эго обычно вызывает поначалу некоторые трудности у пользователя, но после краткого знакомства с; алгоритмом БПФ все его особенности становятся достаточно ясными.

Во многих практических случаях желательно иметь возможность изменять разрешение, с которым рассчитываются спектры. Допустим, в некотором практическом приложении известно, что для дискретизации заданной функции достаточно точек, расположенных лруч друга на расстоянии А. Соответственно этим отсчетам функция в ДПФ должна быть вычислена только в точках, расположенных с интервалом , где Каким образом можно уменьшить интервал дискретизации вдоль оси и, на которой требуется рассчитать функцию Очевидно, что функция должна быть преобразована так, чтобы она занимала большой отрезок оси Но предположим, что функция равна нулю вне отрезка длиной Единственный ответ на наш вопрос — нужно взять дополнительные отсчеты нулевой величины вне отрезка длиной Фактически следует взять новый отрезок длиной где величина должна представлять собой степень двойки, если используется обычная программа БПФ. Интервал дискретизации для дополнительных отсчетов должен быть равен Посредством такого простого приема, при котором «функция дополняется пулями», можно разместить рассчитанные отсчеты функции вдоль оси и с интервалом, равным или и т. д. Тот же самый прием может бы использован в двумерном случае и в случаях большей размерности. Заданная функция должна быть дополнена нулями (т. е. отсчетами нулевой величины) вне прямоугольной области, в которой она отлична от нуля.

Чтобы проводить вычисления по формулам (12.2) и (12.5) с использованием алгоритма БПФ, заменим соотношения (12.3) равенствами

и положим, что единицы длины но осям х и у равны соответственно. Тогда выражения (12.2) и (12.5) преобразуются к виду

При выполнении алгоритма БПФ величины рассматриваются как периодические с периодами, равными соответственно, по Таким образом,

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

Отметим, что если функция вещественная, то в силу формулы (8.2) все значения тоже вещественны. Кроме того, знаки в показателях степени и формулах (12.15) и (12.16) в некоторых работах меняют местами. Это не имеет значения, если используемые данные организуются в полном согласии с компьютерной программой. какова бы она ни была.

Решающим преимуществом алгоритма БПФ перед прямым вычислением ДПФ является его быстродействие. Для изображения размером элементов с комплексными значениями прямые вычисления ДПФ требуют операций (умножения и сложения) над комплексными числами, тогда как соответствующее число операций для БПФ равно Например, при вычисления ускоряются в 4096 раз. Имеются две причины такого увеличения быстродействия. Во-первых, двумерное можно рассматривать как -точечных одномерных Во-вторых, если то каждое одномерное -точечное БПФ может быть разложено на Множеств одномерных -точечных БПФ. Чтобы ясно представлять себе как это второе обстоятельство приводит к увеличению

вычислительной эффективности, нужно записать формулу (12.16) в одномерной форме:

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

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

где

Здесь для для для для Таким образом, для расчета требуемых коэффициентов А необходимо только комплексных операций. При использовании формул (12.21), (12.22) и (12.19) получается всего операций. Эту процедуру можно выполнить раз, что приводит к суммам, каждая из которых содержит два члена. Тогда полное число комплексных операций будет равно

Таково число операций, необходимое для расчета всех значений с помощью описанной выше процедуры. Программная реализация

(см. § 48) такой процедуры и есть алгоритм Уменьшение числа операций по сравнению с операциями, требуемыми для прямого расчета по формуле (12.18), будет заметным, если достаточно большое число. Выигрыш в числе операций получается равным примерно Этим объясняется широкий интерес к алгоритму БПФ и все возрастающее его применение в вычислительной практике.

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