5.3. Дискретное преобразование Фурье

5.3.1. Спектр периодической функции

Рассмотрим преобразование Фурье от периодической функции , где  – функция одного периода, повторяющаяся с периодом T. Такую периодическую функцию можно описать как свертку функции  с функцией одного периода :

           (5.12)

Тогда, согласно свойствам преобразования Фурье (таблица 5.1), спектр периодической функции  можно вычислить как произведение фурье-образа функции  и фурье-образа функции одного периода :

          (5.13)

Таким образом, спектр периодической функции с периодом T существует только в отдельных точках, то есть является дискретным с шагом 1/T (рис.5.1), причем огибающая дискретного спектра – фурье-образ одного периода функции (теорема о спектре периодической функции).

Рис.5.1. Периодическая функция и ее спектр

5.3.2. Спектр дискретной функции

Чтобы описать дискретную функцию, можно представить исходную функцию в виде произведения огибающей  и функции отсчетов :

          (5.14)

Спектр дискретной функции с шагом дискретизации  будет периодической функцией с периодом , а в пределах одного периода – спектр огибающей выборки (рис.5.2).  При этом частота Найквиста  – предельная частота, на которой повторяющиеся спектры выборки не пересекаются (теорема о спектре дискретной функции).

Рис.5.2. Дискретная функция и ее спектр

5.3.3. Теорема о выборке

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

Теорема о выборке (известна так же как теорема Уиттекера – Шеннона или теорема Котельникова) формулируется следующим образом: любая двумерная функция с финитным фурье-образом однозначно определяется выборкой с шагами  и , величина которых удовлетворяет неравенствам:

,           (5.15)

где  и  – предельные частоты в фурье-образе этой функции.

Рис.5.3. Теорема о выборке

5.3.4. Дискретное преобразование Фурье (ДПФ)

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

          (5.16)

где m – номер элемента в выборке функции, k – номер элемента в выборке фурье-спектра, N – размерность выборок.

Обратное ДПФ определяется выражением:

          (5.17)

Вычисление преобразования Фурье путём выполнения непосредственно суммирования является неэффективным, поэтому для вычисления дискретного фурье-образа функций, как правило, используется один из алгоритмов быстрого преобразования Фурье (БПФ). Разработано большое количество быстрых алгоритмов для вычисления преобразования Фурье, многие из которых реализованы в виде библиотек на различных языках программирования.

Одной из наиболее эффективных и удобных в использовании библиотек является FFTW. Существенное увеличение производительности вычислений в этой библиотеке достигается за счёт того, что во время выполнения выбирается наиболее подходящий алгоритм БПФ для данного количества элементов выборки.

Все быстрые алгоритмы, включая алгоритмы библиотеки FFTW работают наиболее эффективно с выборками, размерность которых является 2ⁿ, то есть 2, 4, 16, 32, 64, 128, 256, 512, 1024, 2048 и т.д. Поэтому, при использовании быстрых алгоритмов желательно задавать размерность выборки равную 2ⁿ.

Из теоремы о выборке следует, что если количество элементов в выборке функции и выборке спектра одинаково и равно N, шаги по функции и по спектру связаны между собой соотношениями:

 ,           (5.18)

5.3.5. Сдвиговое дискретное преобразование Фурье (СДПФ)

Одномерное СДПФ

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

 
  Рис.5.4. Вид спектра функции:
  а) после непрерывного преобразования Фурье
  б) после дискретного преобразования Фурье

Преодолеть неудобства использования ДПФ позволяет его модификация, которая осуществляется на основе теоремы о сдвиге преобразования Фурье. Пусть сдвиг нулевого отсчёта функции относительно начала координат составляет , а сдвиг нулевого отсчёта фурье-образа относительно начала его координат составляет . Тогда дискретное представление прямого преобразования Фурье примет вид:

          (5.19)

где  – величина сдвига функции;  – величина сдвига спектра.

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

СДПФ легко выражается через ДПФ тривиальным раскрытием скобок в выражении (5.20):

          (5.20)

Как видно из выражения (5.20), вычисление СДПФ можно выполнить в 3 этапа:

1. Домножение выборки функции на сдвиговую экспоненту , обеспечивающую смещение спектра.
2. Выполнение ДПФ, с использованием любого алгоритма БПФ.
3. Домножение выборки спектра на сдвиговую экспоненту , компенсирующее смещение выборки.

Аналогичное выражение и процедура вычисления используется для обратного СДПФ.

Двумерное СДПФ

Для двумерного преобразования Фурье необходимо сдвигать функцию и спектр в направлении x и направлении y:

          (5.21)

где ,  – величина сдвига функции; ,  – величина сдвига спектра.

Для получения фурье-образов с привычным расположением начала координат в центре выборки в соответствии с выражением необходимо выполнить СДПФ с параметрами сдвига ,  и , . СДПФ с параметрами сдвига ,  и , , совпадает с ДПФ и обладает всеми его свойствами.

Двумерное СДПФ выражается через ДПФ следующим образом:

          (5.22)

Двумерное СДПФ можно выполнить в 3 этапа:

1. Домножение выборки функции на сдвиговые экспоненты , , обеспечивающие смещение спектра.
2. Выполнение ДПФ, с использованием любого алгоритма БПФ.
3. Домножение выборки спектра на сдвиговые экспоненты , , компенсирующие смещение выборки.

Аналогичное выражение и процедура вычисления используется для обратного двумерного СДПФ.