какое свойство не относится к дискретному преобразованию фурье
Свойства дискретного преобразования Фурье
DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов
Распространяется под лицензией LGPL v3
Приведем их еще раз:
Везде далее в этом разделе считается, что и индексируют временные и спектральные отсчеты соответственно.
В данном разделе будут рассмотрены некоторые свойства ДПФ.
При умножении сигнала на константу ДПФ сигнала также умножается на константу:
Видно, что при циклическом сдвиге с опережением, первые отчетов переносятся из начала в конец выборки.
При запаздывании последние отчетов переносятся из конца выборки в начало.
Тогда ДПФ сдвинутого сигнала равно:
С учетов введенных замен, выражение (9) можно записать:
Почему мы должны говорить о циклическом сдвиге при рассмотрении ДПФ? Ответ кроется в переходе от ДВПФ к ДПФ. ДПФ возвращает дискретный спектр, который соответствует периодическому сигналу. Периодический сигнал получается из исходной выборки путем бесконечного повторения по времени как это показано на рисунке 1 пунктирными линиями. Т.е. ДПФ это спектр периодического сигнала. А значит при сдвиге периодического сигнала по времени мы получаем циклическую задержку.
Пусть сигнал есть результат циклической свертки сигналов и :
Поменяем местами операции суммирования:
Таким образом, ДПФ циклической свертки двух сигналов равен произведению ДПФ этих сигналов.
Это свойство позволяет использовать алгоритмы быстрого преобразования Фурье для вычисления сверток сигналов.
Тогда ДПФ сигнала равно:
Произведем циклический сдвиг спектра и рассмотрим ОДПФ, тогда:
Таким образом, циклический частотный сдвиг ДПФ осуществляется умножением сигнала на комплексную экспоненту.
Важно отметить, что после умножения на комплексную экспоненту вещественного сигнала, результирующий сигнал будет комплексным, а его спектр перестанет быть симметричным.
Рассмотрим теперь и :
Красным отмечены чисто вещественные и спектральные составляющие.
В случае нечетного только первый спектральный отсчет ДПФ вещественного сигнала является вещественным.
Остальные спектральные отсчеты в общем случае комплексные.
В силу симметрии ДПФ вещественного сигнала мы можем произвести частотную инверсию спектра сигнала путем перестановки спектральных составляющих.
Рассмотрим инверсный спектр для :
На рисунке 4 показано, что частотная инверсия спектра соответствует циклическому частотному сдвигу спектра на спектральных отсчетов в сторону опережения, или запаздывания.
Тогда сигнал с инверсным по частоте спектром, согласно свойству о частотном сдвиге спектра (19), равен:
Нулевой отчет ДПФ есть сумма отсчетов сигнала.
Простыми словами о преобразовании Фурье
Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.
(с) xkcd
Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”
Начать надо, наверное, с того что обычное преобразование Фурье — это некая такая штука которая, как можно догадаться из названия, преобразует одни функции в другие, то есть ставит в соответствие каждой функции действительного переменного x(t) её спектр или фурье-образ y(w):
Если приводить аналогии, то примером аналогичного по смыслу преобразования может послужить например дифференцирование, превращающее функцию в её производную. То есть преобразование Фурье — такая же, по сути, операция как и взятие производной, и её часто обозначают схожим образом, рисуя треугольную “шапочку” над функцией. Только в отличие от дифференцирования которое можно определить и для действительных чисел, преобразование Фурье всегда “работает” с более общими комплексными числами. Из-за этого постоянно возникают проблемы с отображением результатов этого преобразования, поскольку комплексные числа определяются не одной, а двумя координатами на оперирующем действительными числами графике. Удобнее всего, как правило, оказывается представить комплексные числа в виде модуля и аргумента и нарисовать их по раздельности как два отдельных графика:
График аргумента комплексного значения часто называют в данном случае “фазовым спектром”, а график модуля — “амплитудным спектром”. Амплитудный спектр как правило представляет намного больший интерес, а потому “фазовую” часть спектра нередко пропускают. В этой статье мы тоже сосредоточимся на “амплитудных” вещах, но забывать про существование пропущенной фазовой части графика не следует. Кроме того, вместо обычного модуля комплексного значения часто рисуют его десятичный логарифм умноженный на 10. В результате получается логарифмический график, значения на котором отображаются в децибелах (дБ).
Обратите внимание что не очень сильно отрицательным числам логарифмического графика (-20 дБ и менее) при этом соответствуют практически нулевые числа на графике “обычном”. Поэтому длинные и широкие “хвосты” разнообразных спектров на таких графиках при отображении в “обычные” координаты как правило практически исчезают. Удобство подобного странного на первый взгляд представления возникает из того что фурье-образы различных функций часто необходимо перемножать между собой. При подобном поточечном умножении комплекснозначных фурье-образов их фазовые спектры складываются, а амплитудные — перемножаются. Первое выполняется легко, а второе — сравнительно сложно. Однако логарифмы амплитуды при перемножении амплитуд складываются, поэтому логарифмические графики амплитуды можно, как и графики фаз, просто поточечно складывать. Кроме того, в практических задачах часто удобнее оперировать не «амплитудой» сигнала, а его «мощностью» (квадратом амплитуды). На логарифмической шкале оба графика (и амплитуды и мощности) выглядят идентично и отличаются только коэффициентом — все значения на графике мощности ровно вдвое больше чем на шкале амплитуд. Соответственно для построения графика распределения мощности по частоте (в децибелах) можно не возводить ничего в квадрат, а посчитать десятичный логарифм и умножить его на 20.
Заскучали? Погодите, еще немного, с занудной частью статьи, объясняющей как интерпретировать графики, мы скоро покончим :). Но перед этим следует понять одну крайне важную вещь: хотя все вышеприведенные графики спектров были нарисованы для некоторых ограниченных диапазонов значений (в частности, положительных чисел), все эти графики на самом деле продолжаются в плюс и минус бесконечность. На графиках просто изображается некоторая “наиболее содержательная” часть графика, которая обычно зеркально отражается для отрицательных значений параметра и зачастую периодически повторяется с некоторым шагом, если рассматривать её в более крупном масштабе.
Определившись с тем, что же рисуется на графиках, давайте вернемся собственно к преобразованию Фурье и его свойствам. Существует несколько разных способов как определить это преобразование, отличающихся небольшими деталями (разными нормировками). Например в наших ВУЗах почему-то часто используют нормировку преобразования Фурье определяющую спектр в терминах угловой частоты (радианов в секунду). Я буду использовать более удобную западную формулировку, определяющую спектр в терминах обычной частоты (герцах). Прямое и обратное преобразование Фурье в этом случае определяются формулами слева, а некоторые свойства этого преобразования которые нам понадобятся — списком из семи пунктов справа:
Если взять функцию, состоящую из суммы множества синусоид с разными частотами, то согласно свойству линейности, фурье-образ этой функции будет состоять из соответствующего набора дельта-функций. Это позволяет дать наивную, но наглядную интерпретацию спектра по принципу “если в спектре функции частоте f соответствует амплитуда a, то исходную функцию можно представить как сумму синусоид, одной из которых будет синусоида с частотой f и амплитудой 2a”. Строго говоря, эта интерпретация неверна, поскольку дельта-функция и точка на графике — это совершенно разные вещи, но как мы увидим дальше, для дискретных преобразований Фурье она будет не так уж и далека от истины.
Второе свойство преобразования Фурье — это независимость амплитудного спектра от сдвига сигнала по времени. Если мы подвинем функцию влево или вправо по оси x, то поменяется лишь её фазовый спектр.
Третье свойство — растяжение (сжатие) исходной функции по оси времени (x) пропорционально сжимает (растягивает) её фурье-образ по шкале частот (w). В частности, спектр сигнала конечной длительности всегда бесконечно широк и наоборот, спектр конечной ширины всегда соответствует сигналу неограниченной длительности.
Четвертое и пятое свойства самые, пожалуй, полезные из всех. Они позволяют свести свертку функций к поточечному перемножению их фурье-образов и наоборот — поточечное перемножение функций к свертке их фурье-образов. Чуть дальше я покажу насколько это удобно.
Наконец последнее, седьмое свойство, говорит о том, что преобразование Фурье сохраняет “энергию” сигнала. Оно осмысленно только для сигналов конечной продолжительности, энергия которых конечна, и говорит о том, что спектр подобных сигналов на бесконечности быстро приближается к нулю. Именно в силу этого свойства на графиках спектров как правило изображают только “основную” часть сигнала, несущую в себе львиную долю энергии — остальная часть графика просто стремится к нулю (но, опять же, нулем не является).
Вооружившись этими 7 свойствами, давайте посмотрим на математику “оцифровки” сигнала, позволяющую перевести непрерывный сигнал в последовательность цифр. Для этого нам понадобится взять функцию, известную как “гребенка Дирака”:
Гребенка Дирака — это просто периодическая последовательность дельта-функций с единичным коэффициентом, начинающаяся в нуле и идущая с шагом T. Для оцифровки сигналов, T выбирают по возможности малым числом, T
Дискретное преобразование Фурье
DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов
Распространяется под лицензией LGPL v3
Однако для задач цифровой обработки гораздо удобнее было бы иметь как дискретный сигнал, так и дискретный спектр данного сигнала, который можно сохранить в памяти цифрового устройства.
В данном разделе мы произведем переход к дискретному преобразованию Фурье (ДПФ) — одного из распространенных инструментов спектрального анализа сигналов, широко применяемого в самых разных отраслях науки и техники.
Пусть исходный дискретный сигнал ограничен во времени и содержит ненулевых отсчетов, взятых с интервалом дискретизации с. Данное предположение на практике всегда выполняется, потому что мы не можем получить бесконечное число отсчетов сигнала. Тогда длительность дискретного сигнала равна cекунд, и можно записать как:
Графически процесс повторения сигнала во времени представлен на рисунке 1.
При этом минимальный период повторения сигнала, при котором сигнал и его повторения не накладываются друг на друга, равен секунд.
Повторение сигнала с минимальным периодом показано на рисунке 2.
Заметим, что (5) является именно спектром, а не спектральной плотностью, потому что мы получили как результат разложения в ряд Фурье. Это означает, что единицы измерения совпадают с единицами измерения исходного сигнала.
Если мы будем оперировать только с индексами входного сигнала и спектральных отсчетов (положив ), то получим выражение дискретного преобразования Фурье:
Фурье-вычисления для сравнения изображений
Традиционная техника “начального уровня”, сравнения текущего изображения с эталоном основывается на рассмотрении изображений как двумерных функций яркости (дискретных двумерных матриц интенсивности). При этом измеряется либо расстояние между изображениями, либо мера их близости.
Как правило, для вычисления расстояний между изображениями используется формула, являющаяся суммой модулей или квадратов разностей интенсивности:
Если помимо простого сравнения двух изображений требуется решить задачу обнаружения позиции фрагмента одного изображения в другом, то классический метод “начального уровня”, заключающийся в переборе всех координат и вычисления расстояния по указанной формуле, как правило, терпит неудачу практического использования из-за требуемого большого количества вычислений.
Одним из методов, позволяющих значительно сократить количество вычислений, является применение Фурье преобразований и дискретных Фурье преобразований для расчёта меры совпадения двух изображений при различных смещениях их между собой. Вычисления при этом происходят одновременно для различных комбинаций сдвигов изображений относительно друг друга.
Наличие большого числа библиотек, реализующих Фурье преобразований (во всевозможных вариантах быстрых версий), делает реализацию алгоритмов сравнения изображений не очень сложной задачей для программирования.
Постановка задачи
образец
в изображении
Корреляция как мера между изображениями
m(X,Y) = SUM ( X[i,j] * Y[i,j] ) / ( SQRT ( SUM X[i,j] ^2 ) * SQRT ( SUM Y[i,j] ^2 ) )
Данная величина получена из операции скалярного произведения векторов (рассматривая изображения как векторы в многомерном пространстве). И даже более — эта же формула представляет собой и стандартную статистическую формулу критерия для гипотезы о совпадении двух вероятностных распределений.
Примечание:
При вычислении корреляции между фрагментами изображений, если одно изображение меньше другого, будем делить только на значение норм у пересекающийся частей.
Свёртка двух функций
Преобразование Фурье
Преобразование Фурье (ℱ) — операция, сопоставляющая одной функции вещественной переменной другую функцию, также вещественной переменной. Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами.
Преобразование Фурье функции f вещественной переменной является интегральным и задаётся следующей формулой:
Разные источники могут давать определения, отличающиеся от приведённого выше выбором коэффициента перед интегралом, а также знака «−» в показателе экспоненты. Но все свойства будут те же, хотя вид некоторых формул может измениться.
Кроме того, существуют разнообразные обобщения данного понятия.
Многомерное преобразование Фурье
Преобразование Фурье функций, заданных на пространстве ℝ^n, определяется формулой:
Обратное преобразование в этом случае задается формулой:
Как и прежде, в разных источниках определения многомерного преобразования Фурье могут отличаться выбором константы перед интегралом.
Дискретное преобразование Фурье
Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.
Формулы дискретных преобразований
Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:
Фурье-преобразования для вычисления свёртки
Одним из замечательных свойств преобразований Фурье является возможность быстрого вычисления корреляции двух функций определённых, либо на действительном аргументе (при использовании классической формулы), либо на конечном кольце (при использовании дискретных преобразований).
И хотя подобные свойства присущи многим линейным преобразованиям, для практического применения, для вычисления операции свёртки, согласно данному нами определению, используется формула
Фурье-преобразования для вычисления корреляции
Пусть (t) равна корреляции получаемой в результате сдвига одного вектора, относительно другого на шаг t
Тогда, как уже показано ранее, выполняется
Фурье-преобразования для решения задачи
Упрощение формул для решения поставленной задачи
Алгоритм поиска фрагмента в полном изображении
Примеры реализации
Реализованные алгоритмы являются частью библиотеки с открытым исходным кодом FFTTools. Интернет-адрес: github.com/dprotopopov/FFTTools
Какое свойство не относится к дискретному преобразованию фурье
Перед началом изложения хочу выразить благодарность Олегу Красноярову за присланное письмо, в котором были кратко рассмотрены альтернативные алгоритмы БПФ, менее известные, чем широко использующийся вариант. Практически полностью это письмо легло в основу подраздела Быстрое преобразование Фурье.
Преобразование Фурье
Итак, преобразование Фурье бывает двух видов: дискретное и непрерывное. Непрерывное используется математиками в аналитических исследованиях, дискретное применяется во всех остальных случаях.
также существует обратное преобразование, которое позволяет по образу H(f) восстановить исходную функцию h(t):
Очевидно, что образ H(f) является комплексной функцией вещественного аргумента, но также и h(t) может принимать не только вещественные, но и комплексные значения.
Применение преобразования Фурье является столь обширной темой, что этот вопрос не будет подниматься в этой статье. Можно только перечислить несколько областей: анализ сигналов, фильтрация, ускоренное вычисление корелляции и свертки, использование в алгоритмах быстрого умножения чисел, и во многих других случаях оно также находит свое применение.
Свойства непрерывного преобразования Фурье
В таблице ниже описана связь свойств прообраза h и образа H.
Следующая таблица показывает, как меняется образ при изменении прообраза. Пусть запись 
обозначает, что H(f) является образом h(t). Тогда имеют место следующие отношения:
Следующий набор свойств относится к операциям свертки и корелляции. Свертка функций g и h определяется, как 
. Корелляция функций g и h определяется, как 
. В таком случае имеют место следующие отношения:
Дискретное преобразование Фурье
С непрерывным преобразованием Фурье удобно работать в теории, но на практике мы обычно имеем дело с дискретными данными. Очень часто у нас дано не аналитическое выражение преобразуемой функции, а лишь набор её значений на некоторой сетке (обычно на равномерной). В таком случае приходится делать допущение, что за пределами этой сетки функция равна нулю, и аппроксимировать интеграл интегральной суммой:
В случае равномерной сетки эта формула упрощается. Также на равномерной сетке обычно избавляются от шага, чтобы получить безразмерную формулу:
Обратное преобразование в таком случае будет иметь вид
Определенное таким образом, дискретное преобразование Фурье сохраняет практически все свойства непрерывного (разумеется, с учетом перехода к дискретному множеству).
Быстрое преобразование Фурье
Сколько операций требуется на проведение дискретного преобразования Фурье? Посчитав по определению ( N раз суммировать N слагаемых), получаем величину порядка N 2 . Тем не менее, можно обойтись существенно меньшим числом операций.
Изобретение БПФ привело к потрясающему всплеску популярности преобразования Фурье. Целый ряд важных задач раньше решался за время порядка N 2 , но после проведения преобразования Фурье над исходными данными (за время порядка Nlog2 N) решается практически мгновенно. Преобразование Фурье лежит в основе цифровых корелляторов и методов свертки, активно используется при спектральном анализе (практически в чистом виде), применяется при работе с длинными числами.
Как уже говорилось выше, существуют алгоритмы БПФ для произвольного числа отсчетов, но наиболее широкое распространение получил только алгоритм для случая N = 2 k , что является существенным ограничением. Почему же это произошло?
Причина этого в том, что алгоритм, построенный по методу Cooley-Tukey, обладает рядом очень хороших технологических свойств. Структура алгоритма и его базовые операции не зависят от числа отсчетов (меняется только число прогонов базовой операции «бабочка»). Алгоритм легко распараллеливается с использованием базовой операции и конвееризуется, а также легко каскадируется (коэфициенты БПФ для 2N отсчетов могут быть легко получены преобразованием коэфициентов двух БПФ по N отсчетов, полученных «прореживанием» через один исходных 2N отсчетов). Алгоритм прост и компактен, не требует дополнительной оперативной памяти и допускает обработку данных «на месте». Существует целый ряд оптимизированных именно для этого алгоритма DSP-процессоров (это одновременно и причина, и следствие).
Всё это и обусловило популярность в инженерно/программистской среде именно этого алгоритма, и, соответственно, выбора именно 2 k отсчетов при использовании БПФ. Правда, попутно это привело к незаслуженному забвению широкими массами альтернативных алгоритмов, некоторые из которых (что следует отметить) требуют меньше вещественных операций на один отсчет, чем алгоритм Cooley-Tukey. Например, мне доводилось читать описание алгоритма, который по этому показателю на 20-40% (в зависимости от числа отсчетов) превосходил алгоритм Cooley-Tukey.
© Сергей Бочканов, Олег Краснояров