Метод фурье лямбда появляется

Обновлено: 29.01.2025

Традиционная техника “начального уровня”, сравнения текущего изображения с эталоном основывается на рассмотрении изображений как двумерных функций яркости (дискретных двумерных матриц интенсивности). При этом измеряется либо расстояние между изображениями, либо мера их близости.

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

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

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

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

Постановка задачи

Пусть даны два изображения X и Y – изображение и образец, размеров (N1,N2) и (M1,M2) соответственно и Ni > Mi
Требуется найти координаты образца Y в полном изображении X и вычислить оценочную величину — меру близости.

образец

в изображении

Корреляция как мера между изображениями

Эта величина хорошо известна из курса математики и геометрии, посвященного линейным пространствам, где носит название скалярного произведения. Будем использовать в качестве меры между изображениями формулу:

Данная величина получена из операции скалярного произведения векторов (рассматривая изображения как векторы в многомерном пространстве). И даже более — эта же формула представляет собой и стандартную статистическую формулу критерия для гипотезы о совпадении двух вероятностных распределений.

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

Свёртка двух функций

FхF’(0) = SUM F(i)^2 – скалярное произведение вектора F на самого себя
GхG’(0) = SUM G(j)^2– скалярное произведение вектора G на самого себя
FхG’(0) = SUM F(i)*G(i) – скалярное произведение двух векторов F и G

Преобразование Фурье

Преобразование Фурье функции f вещественной переменной является интегральным и задаётся следующей формулой:

Кроме того, существуют разнообразные обобщения данного понятия.

Многомерное преобразование Фурье

Преобразование Фурье функций, заданных на пространстве ℝ^n, определяется формулой:

Обратное преобразование в этом случае задается формулой:

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

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

Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.

Формулы дискретных преобразований

Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:

Фурье-преобразования для вычисления свёртки

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

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

FFT – операция прямого преобразования Фурье
BFT – операция обратного преобразования Фурье

Фурье-преобразования для вычисления корреляции

Пусть (t) равна корреляции получаемой в результате сдвига одного вектора, относительно другого на шаг t
Тогда, как уже показано ранее, выполняется

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

Где CONJUGATE ( FFT(G) ) – матрица, составленная из сопряжённых элементов матрицы FFT(G)
Таким образом, получаем

Фурье-преобразования для решения задачи

При использовании формулы для оценки расстояния между изображениями при сдвиге (i,j) относительно друг друга

= XxY’ = BFT ( FFT(X) * CONJUGATE ( FFT(Y) ) )
|X|^2 = = XxX’xE’ = BFT ( FFT(X) * CONJUGATE ( FFT(X) ) * CONJUGATE ( FFT(E) ) ) = BFT ( SQUAREMAGNITUDE( FFT(X) ) * CONJUGATE ( FFT(E) ) )
|Y|^2 = = YxY’xE’ = BFT ( FFT(Y) * CONJUGATE ( FFT(Y) ) * CONJUGATE ( FFT(E) ) )

(i,j) – скалярное произведение двух изображений, получаемых при сдвиге (i,j) относительно друг друга изображений X и Y
E – изображение размера равному минимальным размерам X и Y, и заполненное единичными значениями (то есть “кадр” в котором сравниваются X и Y)
|X|(i,j) – норма общей части изображения X при сдвиге (i,j)
|Y|(i,j) – норма общей части изображения Y при сдвиге (i,j)
FFT – операция прямого двухмерного дискретного преобразования Фурье
BFT – операция обратного двухмерного дискретного преобразования Фурье
CONJUGATE – операция вычисления матрицы из сопряжённых элементов
SQUAREMAGNITUDE– операция вычисления матрицы квадратов амплитуд элементов

Упрощение формул для решения поставленной задачи

При решении задачи для поиска одного образца, дополнительное нормирование образца является излишним, а также вычисление нормы у общей части может быть заменено на сумму яркостей пикселей в этой общей части или на сумму квадратов яркостей в этой общей части
При использовании формулы для оценки расстояния между изображениями при сдвиге (i,j) относительно друг друга

= BFT ( FFT(X) * CONJUGATE ( FFT(Y) ) )
= BFT ( SQUAREMAGNITUDE( FFT(X) ) * CONJUGATE ( FFT(E) ) )

(i,j) – скалярное произведение двух изображений, получаемых при сдвиге (i,j) относительно друг друга изображений X и Y
E – изображение размера равному минимальным размерам X и Y, и заполненное единичными значениями (то есть “кадр” в котором сравниваются X и Y)
(i,j) – норма (сумма яркостей пикселей) общей части изображения X при сдвиге (i,j)
FFT – операция прямого двухмерного дискретного преобразования Фурье
BFT – операция обратного двухмерного дискретного преобразования Фурье
CONJUGATE – операция вычисления матрицы из сопряжённых элементов
SQUAREMAGNITUDE– операция вычисления матрицы квадратов амплитуд элементов

Алгоритм поиска фрагмента в полном изображении

Пусть даны два изображения X и Y – изображение и образец, размеров (N1,N2) и (M1,M2) соответственно и Ni > Mi
Требуется найти координаты образца Y в полном изображении X и вычислить оценочную величину — меру близости.

Расширить изображение Y до размера (N1,N2), дополнив его нулями
Сформировать изображение E из единиц размера (M1,M2) и расширить до размера (N1,N2), дополнив его нулями
Вычислить = BFT ( FFT(X) * CONJUGATE ( FFT(Y) ) )
Вычислить = BFT ( SQUAREMAGNITUDE( FFT(X) ) * CONJUGATE ( FFT(E) ) )
Вычислить M[i,j] = (f + [i,j])/(f + [i,j])
В матрице M найти элемент с максимальным значением – координаты этого элемента и являются искомой позицией образца в полном изображении, а значение равно оценке меры сравнения.

Примеры реализации

Во многих случаях задача получения (вычисления) спектра сигнала выглядит следующим образом. Имеется АЦП, который с частотой дискретизации Fd преобразует непрерывный сигнал, поступающий на его вход в течение времени Т, в цифровые отсчеты — N штук. Далее массив отсчетов подается в некую программку, которая выдает N/2 каких-то числовых значений (программист, который ~~утянул из инета~~ написал программку, уверяет, что она делает преобразование Фурье).

Чтобы проверить, правильно ли работает программа, сформируем массив отсчетов как сумму двух синусоид sin(10*2*pi*x)+0,5*sin(5*2*pi*x) и подсунем программке. Программа нарисовала следующее:

рис.1 График временной функции сигнала

рис.2 График спектра сигнала

На графике спектра имеется две палки (гармоники) 5 Гц с амплитудой 0.5 В и 10 Гц — с амплитудой 1 В, все как в формуле исходного сигнала. Все отлично, программист молодец! Программа работает правильно.

Это значит, что если мы подадим на вход АЦП реальный сигнал из смеси двух синусоид, то мы получим аналогичный спектр, состоящий из двух гармоник.

Итого, наш реальный измеренный сигнал, длительностью 5 сек, оцифрованный АЦП, то есть представленный дискретными отсчетами, имеет дискретный непериодический спектр.

Теперь ~~начальство решило~~ мы решили, что 5 секунд — это слишком долго, давай измерять сигнал за 0.5 сек.

рис.3 График функции sin(10*2*pi*x)+0,5*sin(5*2*pi*x) на периоде измерения 0.5 сек

рис.4 Спектр функции

Что-то как бы не то! Гармоника 10 Гц рисуется нормально, а вместо палки на 5 Гц появилось несколько каких-то непонятных гармоник. Смотрим в интернетах, что да как…

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

рис.5 Добили нулей до 5 сек

рис.6 Получили спектр

Все равно не то, что было на 5 секундах. Придется разбираться с теорией. Идем в Википедию — источник знаний.

2. Непрерывная функция и представление её рядом Фурье

Математически наш сигнал длительностью T секунд является некоторой функцией f(x), заданной на отрезке (X в данном случае — время). Такую функцию всегда можно представить в виде суммы гармонических функций (синусоид или косинусоид) вида:

(1), где:

k — номер тригонометрической функции ( номер гармонической составляющей, номер гармоники)
T — отрезок, где функция определена (длительность сигнала)
Ak — амплитуда k-ой гармонической составляющей,
θk- начальная фаза k-ой гармонической составляющей

Этот ряд может быть также записан в виде:

(2),
где , k-я комплексная амплитуда.

(3)

Связь между коэффициентами (1) и (3) выражается следующими формулами:

$<A_k></p> <p>=\sqrt$

Итого:
Математической основой спектрального анализа сигналов является преобразование Фурье.

Преобразование Фурье позволяет представить непрерывную функцию f(x) (сигнал), определенную на отрезке в виде суммы бесконечного числа (бесконечного ряда) тригонометрических функций (синусоид и\или косинусоид) с определёнными амплитудами и фазами, также рассматриваемых на отрезке . Такой ряд называется рядом Фурье.

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

Например, на графике рис.7 исходная функция определена на отрезке <-T\2, +T\2>, а ряд Фурье представляет периодическую функцию, определенную на всей оси х.

Это происходит потому, что синусоиды сами являются периодическими функциями, соответственно и их сумма будет периодической функцией.

рис.7 Представление непериодической исходной функции рядом Фурье

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

Периоды гармонических составляющих кратны величине отрезка , на котором определена исходная функция f(x). Другими словами, периоды гармоник кратны длительности измерения сигнала. Например, период первой гармоники ряда Фурье равен интервалу Т, на котором определена функция f(x). Период второй гармоники ряда Фурье равен интервалу Т/2. И так далее (см. рис. 8).

рис.8 Периоды (частоты) гармонических составляющих ряда Фурье (здесь Т=2π)

Соответственно, частоты гармонических составляющих кратны величине 1/Т. То есть частоты гармонических составляющих Fk равны Fk= к\Т, где к пробегает значения от 0 до ∞, например к=0 F0=0; к=1 F1=1\T; к=2 F2=2\T; к=3 F3=3\T;… Fk= к\Т (при нулевой частоте — постоянная составляющая).

Пусть наша исходная функция, представляет собой сигнал, записанный в течение Т=1 сек. Тогда период первой гармоники будет равен длительности нашего сигнала Т1=Т=1 сек и частота гармоники равна 1 Гц. Период второй гармоники будет равен длительности сигнала, деленной на 2 (Т2=Т/2=0,5 сек) и частота равна 2 Гц. Для третьей гармоники Т3=Т/3 сек и частота равна 3 Гц. И так далее.

Шаг между гармониками в этом случае равен 1 Гц.

Таким образом сигнал длительностью 1 сек можно разложить на гармонические составляющие (получить спектр) с разрешением по частоте 1 Гц.
Чтобы увеличить разрешение в 2 раза до 0,5 Гц — надо увеличить длительность измерения в 2 раза — до 2 сек. Сигнал длительностью 10 сек можно разложить на гармонические составляющие (получить спектр) с разрешением по частоте 0,1 Гц. Других способов увеличить разрешение по частоте нет.

Существует способ искусственного увеличения длительности сигнала путем добавления нулей к массиву отсчетов. Но реальную разрешающую способность по частоте он не увеличивает.

3. Дискретные сигналы и дискретное преобразование Фурье

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

Обычная схема измерения и оцифровки сигнала выглядит следующим образом.

рис.9 Схема измерительного канала

Сигнал с измерительного преобразователя поступает на АЦП в течение периода времени Т. Полученные за время Т отсчеты сигнала (выборка) передаются в компьютер и сохраняются в памяти.

рис.10 Оцифрованный сигнал — N отсчетов полученных за время Т

Какие требования выдвигаются к параметрам оцифровки сигнала? Устройство, преобразующее входной аналоговый сигнал в дискретный код (цифровой сигнал) называется аналого-цифровой преобразователь (АЦП, англ. Analog-to-digital converter, ADC) ( Wiki).

Одним из основных параметров АЦП является максимальная частота дискретизации (или частота семплирования, англ. sample rate) — частота взятия отсчетов непрерывного во времени сигнала при его дискретизации. Измеряется в герцах. (( Wiki))

Согласно теореме Котельникова, если непрерывный сигнал имеет спектр, ограниченный частотой Fмакс, то он может быть полностью и однозначно восстановлен по его дискретным отсчетам, взятым через интервалы времени , т.е. с частотой Fd ≥ 2*Fмакс, где Fd — частота дискретизации; Fмакс — максимальная частота спектра сигнала. Другими слова частота оцифровки сигнала (частота дискретизации АЦП) должна как минимум в 2 раза превышать максимальную частоту сигнала, который мы хотим измерить.

А что будет, если мы будем брать отсчеты с меньшей частотой, чем требуется по теореме Котельникова?

Рис. 11. Появление ложного сигнала низкой частоты при недостаточно высокой частоте дискретизации

Чтобы избежать эффекта алиасинга перед АЦП ставят специальный антиалиасинговый фильтр — ФНЧ (фильтр нижних частот), который пропускает частоты ниже половины частоты дискретизации АЦП, а более высокие частоты зарезает.

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

Сравнивая с рядом Фурье

видим, что они совпадают, за исключением того, что время в ДПФ имеет дискретный характер и число гармоник ограничено величиной N/2 — половиной числа отсчетов.

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

рис.12 Периодическая функция f(x) с периодом Т0, с периодом измерения Т>T0

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

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

Рис.13 Пример функции и спектра сигнала кинематической погрешности редуктора

Рис.14 Пример функции и спектра сигнала вибрации ротора

Некоторые итоги

1. Реальный измеренный сигнал, длительностью T сек, оцифрованный АЦП, то есть представленный набором дискретных отсчетов (N штук), имеет дискретный непериодический спектр, представленный набором гармоник (N/2 штук).

Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.

(с) xkcd

FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?
Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT)
Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки
Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать
Зачем перед АЦП и после ЦАП ставят аналоговые фильтры
Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно)
Как по цифровой последовательности восстанавливают исходный сигнал

Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”

Начать надо, наверное, с того что обычное преобразование Фурье — это некая такая штука которая, как можно догадаться из названия, преобразует одни функции в другие, то есть ставит в соответствие каждой функции действительного переменного x(t) её спектр или фурье-образ y(w):

Если приводить аналогии, то примером аналогичного по смыслу преобразования может послужить например дифференцирование, превращающее функцию в её производную. То есть преобразование Фурье — такая же, по сути, операция как и взятие производной, и её часто обозначают схожим образом, рисуя треугольную “шапочку” над функцией. Только в отличие от дифференцирования которое можно определить и для действительных чисел, преобразование Фурье всегда “работает” с более общими комплексными числами. Из-за этого постоянно возникают проблемы с отображением результатов этого преобразования, поскольку комплексные числа определяются не одной, а двумя координатами на оперирующем действительными числами графике. Удобнее всего, как правило, оказывается представить комплексные числа в виде модуля и аргумента и нарисовать их по раздельности как два отдельных графика:

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

Заскучали? Погодите, еще немного, с занудной частью статьи, объясняющей как интерпретировать графики, мы скоро покончим :). Но перед этим следует понять одну крайне важную вещь: хотя все вышеприведенные графики спектров были нарисованы для некоторых ограниченных диапазонов значений (в частности, положительных чисел), все эти графики на самом деле продолжаются в плюс и минус бесконечность. На графиках просто изображается некоторая “наиболее содержательная” часть графика, которая обычно зеркально отражается для отрицательных значений параметра и зачастую периодически повторяется с некоторым шагом, если рассматривать её в более крупном масштабе.

Определившись с тем, что же рисуется на графиках, давайте вернемся собственно к преобразованию Фурье и его свойствам. Существует несколько разных способов как определить это преобразование, отличающихся небольшими деталями (разными нормировками). Например в наших ВУЗах почему-то часто используют нормировку преобразования Фурье определяющую спектр в терминах угловой частоты (радианов в секунду). Я буду использовать более удобную западную формулировку, определяющую спектр в терминах обычной частоты (герцах). Прямое и обратное преобразование Фурье в этом случае определяются формулами слева, а некоторые свойства этого преобразования которые нам понадобятся — списком из семи пунктов справа:

Первое из этих свойств — линейность. Если мы берем какую-то линейную комбинацию функций, то преобразование Фурье этой комбинации будет такой же линейной комбинацией образов Фурье этих функций. Это свойство позволяет сводить сложные функции и их фурье-образы к более простым. Например, фурье-образ синусоидальной функции с частотой f и амплитудой a является комбинацией из двух дельта-функций расположенных в точках f и -f и с коэффициентом a/2:

Если взять функцию, состоящую из суммы множества синусоид с разными частотами, то согласно свойству линейности, фурье-образ этой функции будет состоять из соответствующего набора дельта-функций. Это позволяет дать наивную, но наглядную интерпретацию спектра по принципу “если в спектре функции частоте f соответствует амплитуда a, то исходную функцию можно представить как сумму синусоид, одной из которых будет синусоида с частотой f и амплитудой 2a”. Строго говоря, эта интерпретация неверна, поскольку дельта-функция и точка на графике — это совершенно разные вещи, но как мы увидим дальше, для дискретных преобразований Фурье она будет не так уж и далека от истины.

Второе свойство преобразования Фурье — это независимость амплитудного спектра от сдвига сигнала по времени. Если мы подвинем функцию влево или вправо по оси x, то поменяется лишь её фазовый спектр.

Третье свойство — растяжение (сжатие) исходной функции по оси времени (x) пропорционально сжимает (растягивает) её фурье-образ по шкале частот (w). В частности, спектр сигнала конечной длительности всегда бесконечно широк и наоборот, спектр конечной ширины всегда соответствует сигналу неограниченной длительности.

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

Шестое свойство говорит о симметрии фурье-образов. В частности, из этого свойства следует что в фурье-образе действительнозначной функции (т.е. любого “реального” сигнала) амплитудный спектр всегда является четной функцией, а фазовый спектр (если его привести к диапазону -pi. pi) — нечетной. Именно по этой причине на графиках спектров практически никогда не рисуют отрицательную часть спектра — для действительнозначных сигналов она не дает никакой новой информации (но, повторюсь, и нулевой при этом не является).

Наконец последнее, седьмое свойство, говорит о том, что преобразование Фурье сохраняет “энергию” сигнала. Оно осмысленно только для сигналов конечной продолжительности, энергия которых конечна, и говорит о том, что спектр подобных сигналов на бесконечности быстро приближается к нулю. Именно в силу этого свойства на графиках спектров как правило изображают только “основную” часть сигнала, несущую в себе львиную долю энергии — остальная часть графика просто стремится к нулю (но, опять же, нулем не является).

Вооружившись этими 7 свойствами, давайте посмотрим на математику “оцифровки” сигнала, позволяющую перевести непрерывный сигнал в последовательность цифр. Для этого нам понадобится взять функцию, известную как “гребенка Дирака”:

Вместо непрерывной функции после подобного перемножения получается последовательность дельта-импульсов определенной высоты. При этом согласно свойству 5 преобразования Фурье, спектр получившегося дискретного сигнала есть свертка исходного спектра с соответствующей гребенкой Дирака. Несложно понять, что исходя из свойств свертки, спектр исходного сигнала при этом как бы “копируется” бесконечное число раз вдоль оси частот с шагом 1/T, а затем суммируется.

Заметим, что если исходный спектр имел конечную ширину и мы использовали достаточно большую частоту дискретизации, то копии исходного спектра не будут перекрываться, а следовательно и суммироваться друг с другом. Несложно понять что по подобному “свернутому” спектру будет легко восстановить исходный — достаточно будет просто взять компоненту спектра в районе нуля, “обрезав” лишние копии уходящие на бесконечность. Простейший способ это сделать — это домножить спектр на прямоугольную функцию, равную T в диапазоне -1/2T. 1/2T и нулю — вне этого диапазона. Подобный Фурье-образ соответствует функции sinc(Tx) и согласно свойству 4, подобное умножение равнозначно свертке исходной последовательности дельта-функций с функцией sinc(Tx)

То есть с помощью преобразования Фурье мы получили способ легко восстановить исходный сигнал из дискретизированного по времени, работающий при условии что мы используем частоту дискретизации, по крайней мере вдвое (из-за наличия в спектре отрицательных частот) превышающую максимальную частоту присутствующую в исходном сигнале. Этот результат широко известен и называется “теорема Котельникова / Шеннона-Найквиста”. Однако, как несложно теперь (понимая доказательство) заметить, этот результат вопреки широко распространенному заблуждению определяет достаточное, но не необходимое условие для восстановления исходного сигнала. Все что нам требуется — это добиться того, чтобы интересующая нас часть спектра после дискретизации сигнала не накладывалась друг на друга и если сигнал достаточно узкополосный (имеет малую “ширину” ненулевой части спектра), то этого результата часто можно добиться и при частоте дискретизации намного ниже чем удвоенная максимальная частота сигнале. Подобная техника называется “undersampling” (субдискретизация, полосовая дискретизация) и довольно широко используется при обработке всевозможных радиосигналов. Например, если мы берем FM-радио действующее в полосе частот от 88 до 108 МГц, то для его оцифровки можно использовать АЦП с частотой всего 43.5 МГц вместо предполагающихся по теореме Котельникова 216 МГц. При этом, правда, понадобится качественный АЦП и хороший фильтр.

Замечу, что “дублирование” высоких частот частотами меньших порядков (алиасинг) — непосредственное свойство дискретизации сигнала, необратимо “портящее” результат. Поэтому если в сигнале в принципе могут присутствовать частоты высокого порядка (то есть практически всегда) перед АЦП ставят аналоговый фильтр, “отсекающий” все лишнее непосредственно в исходном сигнале (так как после дискретизации делать это уже будет поздно). Характеристики этих фильтров, как аналоговых устройств, неидеальны, поэтому некоторая “порча” сигнала при этом все равно происходит, и на практике из этого следует что наибольшие частоты в спектре, как правило, недостоверны. Чтобы уменьшить эту проблему, сигнал нередко сэмплируют с завышенной частотой дискретизации, ставя при этом входной аналоговый фильтр на меньшую полосу пропускания и используя только нижнюю часть теоретически доступного частотного диапазона АЦП.

Еще одно распространенное заблуждение, кстати, — это когда сигнал на выходе ЦАП рисуют “ступеньками”. “Ступеньки” соответствуют свертке дискретизированной последовательности сигналов с прямоугольной функцией ширины T и высоты 1:

Спектр сигнала при таком преобразовании умножается на фурье-образ этой прямоугольной функции, а у подобной прямоугольной функции это снова sinc(w), “растянутый” тем сильнее, чем меньше ширина соответствующего прямоугольника. Спектр дискретизированного сигнала при подобном “ЦАП” поточечно умножается на этот спектр. При этом ненужные высокие частоты с “лишними копиями” спектра обрезаются не полностью, а верхняя часть “полезной” части спектра, напротив, ослабляется.

Однако вернемся обратно к преобразованию Фурье. Описанное выше преобразование Фурье, примененное к заранее дискретизированной последовательности сигналов называется преобразованием Фурье дискретного времени (DTFT). Спектр получаемый подобным преобразованием всегда 1/T-периодичен, поэтому спектр DTFT полностью определяется её значениями на отрезке [0. 1/T), поэтому часто этим отрезком спектр DTFT и ограничивают. При этом результат DTFT несмотря на то что это спектр дискретизированного сигнала — по-прежнему “аналоговая” функция. Кроме того, для “обычных” действительнозначных сигналов вторая половина этого спектра в силу свойства 6 зеркально повторяет левую половину, отраженную относительно частоты Найквиста 1/2T.

Пользуясь уже хорошо нам знакомым свойством 5, несложно сообразить, что при подобном умножении исходный сигнал прсто сворачивается со спектром функции окна. Например если мы пытаемся измерить спектр синусоиды (дельта-функцию), но ограничиваем интервал измерений прямоугольным окном, то в получившимся спектре на месте дельта-функции мы увидим спектр окна — т.е. Tsinc(T(x-f)):

В данном случае T — это длина интервала которым мы ограничили наш сигнал, так что чем длиннее будет входной сигнал — тем “уже” и ближе к истинной дельта-функции будет наблюдаемый нами спектр. Конечная “ширина” главного лепестка приводит к невозможности уверенно различать наличие в исходном сигнале синусоид близких друг к другу по частоте, а наличие “боковых лепестков” вносит небольшие искажения и в далеко расположенные частоты, мешая точному измерению амплитуды отдельных частот, особенно если нужно измерять спектр в областях небольшой амплитуды при наличии в спектре на порядок более мощных компонент. Этот эффект называют “спектральной утечкой” и полностью победить его для бесконечных сигналов невозможно, но чем длиннее интервал на котором измеряется сигнал — тем меньше влияние этой утечки. Выбором функции окна можно контролировать “ширину” этой утечки, либо концентрируя её вокруг главной частоты (сильно “размывая” спектр, но зато не мешая соседним частотам), либо размазывая её повсюду (размытие пиков уменьшается но сильно растет “шум” и как следствие — погрешность измерения амплитуды отдельных частот). Заметьте, что выбранная частота дискретизации в спектральной утечке почти не играет роли — короткий отрезок сигнала можно сэмплировать хоть на 10 ГГц, но это увеличит только количество поддающихся измерению частот, тогда как точность определения каждой отдельной частоты все равно останется низкой.

Интересным частным случаем является ситуация, в которой сигнал с набором дискретных частот nF дискретизируется на частоте mF, где m,n — целые числа. В этом случае нули “окна” и расположение дельта-функций в спектре в точности совпадают и хотя частоты все равно “размазываются”, но их амплитуда в точках mF совпадает с истинной — “шум” равен нулю. Это свойство позволяет доказать аналог теоремы Котельникова для дискретного преобразования Фурье, но на практике такие сигналы, к сожалению, фактически не встречаются.

Итак, со “входом” мы разобрались — из непрерывной функции бесконечной длины мы получили конечное число дискретных отсчетов, с которыми можем работать а взамен получили ограничения по ширине спектра и утечку частот. Однако “выход” DTFT по-прежнему является непрерывной функцией, работать с которой компьютеру проблематично. На практике эту проблему решают очень просто — полный отрезок [0,1/T) делят на k равных частей и считают DTFT в точках fi=i/kT, где i = 0,1,… k-1. Получившуюся конструкцию называют “дискретным преобразованием Фурье” (DFT).

Последнее преобразование удобно нормализовать, убрав из него T и вопросы связанные с выбором “окна”. Эту нормализованную запись часто используют в качестве определения DFT как преобразования последовательности из N комплексных чисел:

Прелесть преобразования Фурье записанного в такой форме — в том что сохраняя все достоинства DTFT, подобное DTF для “гладких” k (например, степеней двойки) можно вычислять чрезвычайно быстро, за время порядка k log(k). Соответствующие алгоритмы называют “быстрым преобразованием Фурье” (БПФ, FFT) и их, вообще говоря, существует несколько. С практической точки зрения, впрочем, их все можно рассматривать как “черные ящики”, получающие последовательность комплексных чисел на входе и выдающих последовательность комплексных чисел на выходе. Таким образом, работа с дискретизированным сигналом конечной длины сводится к тому, что этот сигнал вначале умножается на подходящую взвешивающую функцию, затем дополняется нужным числом нулей справа и передается в алгоритм БПФ.

Ну вот, в общем, и всё. Надеюсь преобразование Фурье и алгоритмы БПФ будут теперь для Вас простыми, понятными и приятными в обращении инструментами.

Возьмём классическую задачу – работу со звуком. Теперь добавим конкретики.

Ваш друг приносит запись своего живого выступления. И это очень удачное выступление. Но! Хотя запись делали на хороший микрофон, в ней всё равно присутствует шум. Друг просит помочь убрать его или хотя бы уменьшить.

Здесь и пригодится знание преобразования Фурье.

Что такое звук в математическом смысле?

Отдельная нота – это гармонический сигнал с определённой частотой и амплитудой.

Как правило, мелодию, речь или иной звуковой сигнал можно представить как сумму гармонических сигналов. Шумом в таком случае мы называем слагаемые, соответствующие любым нежелательным звукам.

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

Здесь g(t) – это исходный сигнал (в нашем случае запись друга). В контексте преобразования Фурье его называют оригиналом. G(f) – изображение по Фурье, а параметром f выступает частота.

Возможно, вам уже знакомо это определение. Но знаете ли вы, как происходит это преобразование? Если бы увидели его впервые, поняли бы, как с его помощью анализировать исходный сигнал?

Геометрическая интерпретация преобразования Фурье

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

В дальнейшем обсуждении предполагается, что вы знакомы с векторами, интегрированием и понятием комплексного числа. Если каких-то знаний вам всё-таки не хватает, ознакомьтесь с материалами из нашей подборки по вузовской математике.

1. Наматываем сигнал

Давайте начнём с самого простого случая. Рассмотрим гармонический сигнал, совершающий 3 колебания в секунду (f₀ = 3с -1 ):

Отобразим g(t) на комплексную плоскость. Для этого введём радиус-вектор, который равномерно вращается по часовой стрелке. Его длина в каждый момент времени равна модулю значения сигнала, а частота вращения выбирается произвольным образом.

Теперь построим траекторию движения конца вектора, совершающего полный оборот за две секунды, или, другими словами, с частотой вращения f_В = 0.5 об/с.

Выглядит, будто мы намотали исходный сигнал на начало координат. В минимумах сигнала полученная "намотка" сливается с началом координат, а при приближении к максимумам – отклоняется.

Пока выглядит не особо информативно, не так ли?

А теперь увеличим частоты намотки.

Сначала график распределяется довольно симметрично относительно начала координат до частоты вращения f_В = 3 об/с. Затем максимумы резко смещаются в правую полуплоскость, а намотка перестаёт напоминать узор спирографа.

2. Ищем центр масс

Посмотрим внимательнее, что происходит. В качестве характеристики намотки возьмём усреднённое значение всех её точек – центр масс (отметим его оранжевым цветом).

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

Мы видим два пика: в точках f_В = 0 об/с и f_В = 3 об/с. На основании такого поведения центра масс уже можно судить о частоте исходного сигнала (он колеблется с f = 3с -1 ).

Тогда что означает всплеск на низких частотах?

3. Анализируем влияние смещения

Возможно, вы обратили внимание, что рассматриваемый нами сигнал смещён на единицу. Сдвиг был введён для наглядности, но именно он приводит к усложнению поведения центра масс.

При нулевой частоте всё отображение сигнала на комплексной плоскости располагается на оси абсцисс. На малых частотах намотка по-прежнему группируется в правой полуплоскости.

Как только мы убираем сдвиг, т. е. берём сигнал вида g(t) = cos (6πt), намотка при низких частотах сдвигается влево по оси абсцисс.

Построение радиус-вектора остаётся аналогичным. Его длина равна модулю значения сигнала, направление вращения – положительное. Но при смене знака g(t) направление вектора меняется на противоположное.

Сейчас вы увидите, как меняется намотка и х-координата центра масс несмещённого сигнала.

Таким образом, на графике остался только один резкий скачок.

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

4. Выделяем частоты полигармонического сигнала

Мы наблюдаем два пика в точках f_В = 2 об/с и f_В = 3 об/с, что соответствует частотному составу исходной суммы.

Отметим ещё один интересный факт, верный как для х-координаты, так и для преобразования Фурье. Преобразование для суммы сигналов и сумма преобразований сигналов имеют один и тот же вид. Т. е. преобразование Фурье линейно.

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

Вывод преобразования Фурье

В самом начале рассмотрения мы отобразили исходный сигнал на комплексную плоскость. Такой выбор не случаен – это позволяет рассматривать точки на плоскости как комплексные числа и использовать формулу Эйлера для описания намотки:

Геометрически это соотношение означает, что при любом φ точка e iφ на комплексной плоскости лежит на единичной окружности.

Построим радиус-вектор e iφ при разных значениях φ.

При изменении φ на 2π вектор проходит полный оборот против часовой стрелки, так как 2π – длина единичной окружности. Чтобы задать скорость вращения вектора, показатель степени домножаем на ft, а для смены направления вращения – на -1.

Тогда намотка сигнала g(t) описывается как g(t)e -2π ift .

Теперь вычисляем центр масс. Для этого отметим N произвольных точек на графике намотки и вычислим среднее:

Если мы будем увеличивать количество рассматриваемых точек, придём к предельному случаю:

где t₁ и t₂ – границы интервала, на котором рассматривается сигнал.

Выражение перед интегралом представляет собой масштабирующий коэффициент, но не отражает поведение центра масс. Потому его можно отбросить.

Полученное выражение и будет являться преобразованием Фурье с той разницей, что в общем виде интегрирование задаётся на интервале от -∞ до +∞.

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

Применение преобразования Фурье для фильтрации

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

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

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

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

где — период повторения сигнала. Спектр состоит из дискретных гармоник, равноотстоящих по частоте с шагом рад/с.

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

Для начала рассмотрим, что будет происходить, если мы будем увеличивать период повторения периодического сигнала. На рисунке 1 показаны временные осциллограммы периодической последовательности прямоугольных импульсов , а также амплитудный спектр , при различном периоде повторения с, с и с, при амплитуде сигнала равной 2 В.

Рисунок 1. Амплитудный спектр периодической последовательности прямоугольных импульсов
при увеличении периода повторения

Из рисунка 1 видно, что при увеличении периода , гармоники спектра приближаются друг к другу, потому что расстояние между гармониками обратно пропорционально периоду . Амплитуды гармоник при этом уменьшаются из-за уменьшения средней мощности сигнала на одном периоде повторения.

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

Подставим в уравнение (1) для сигнала выражение для коэффициентов ряда Фурье :

Непериодический сигнал можно получить как предельный переход периодического сигнала (2) при стремящимся к бесконечности:

Читайте также: