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

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

Прямое преобразование:

Обратное преобразование:

Обозначения:

§ N - количество значений сигнала, измеренных за период, а также количество компонент разложения;

§ - измеренные значения сигнала (в дискретных временных точках с номерами , которые являются входными данными для прямого преобразования и выходными для обратного;

§ - N комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;

§ - обычная (вещественная) амплитуда k-го синусоидального сигнала;

§ arg(X k ) - фаза k-го синусоидального сигнала (аргумент комплексного числа);

§ k - частота k-го сигнала, равная , где T - период времени, в течение которого брались входные данные.

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

Рассмотрим некоторый периодический сигнал x (t ) c периодом равным T. Разложим его в ряд Фурье:

Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: x n = x (t n ), где , тогда эти отсчеты через ряд Фурье запишутся следующим образом:

Используя соотношение: , получаем:

где

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

Умножим теперь скалярно выражение для x n на и получим:

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

Эта формула описывает прямое дискретное преобразование Фурье .

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

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

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

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

1. Основные определения преобразования Фурье
2. Дискретное преобразование Фурье, включая быстрое преобразование Фурье
3. Применение Фурье-преобразования (некоторые примеры практического применения преобразования Фурье)

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

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

Переменные представляют собой угловые частоты. Таким образом, представляет собой функцию ƒ(m,n) в частотной области. является комплекснозначной функцией с соответствующими частотами . Частоты находятся в пределах диапазона , . Отметим, что F (0,0) представляется в виде суммы всех переменных ƒ(m,n) . По этой причине F (0,0) часто называют постоянной составляющей преобразования Фурье.

Обратное двумерное преобразование Фурье представляется выражением

Т.е. это выражение представляет ƒ(m,n) в виде суммы бесконечного числа сложных экспоненциальных функций (синусоид) с различными частотами. Амплитуда и фаза определяют вклад частот в представление .

Визуализация Фурье-преобразования

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

Прямоугольная функция

На рисунке внизу с использованием функции mesh визуализировано значения амплитуд, которые получены при Фурье-преобразовании прямоугольной функции, представленной на предыдущем рисунке. Визуализацию амплитуды еще называют визуализацией преобразований Фурье.

Амплитуда изображения прямоугольной функции

Пик функции находится в центре и отображает значение F (0,0), которое является суммой всех значений ƒ(m,n) . Все остальные составляющие представляют собой распределение энергии по вертикальным и горизонтальным частотам.

Другой путь визуализации Фурье-преобразования заключается в отображении значений в виде изображения.

Логарифмическое представление Фурье-преобразования прямоугольной функции

Рассмотрим примеры преобразования Фурье функций различных простых форм.

Примеры Фурье преобразования функций различных простых форм

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

Дискретные косинусные преобразования представляют изображение в виде суммы синусоид с различной амплитудой и частотой. Функция dct2 в приложении Image Processing Toolbox реализует двумерные дискретные косинусные преобразования изображений. Одна из особенностей дискретного преобразования Фурье состоит в том, что некоторые локальные участки изображения можно охарактеризовать небольшим количеством коэффициентов дискретного преобразования Фурье. Это свойство очень часто используется при разработке методов сжатия изображений. Например, дискретное косинусное преобразование является основой международного стандарта, который используется в алгоритме сжатия изображений с потерями JPEG. Название формата “JPEG” состоит из первых букв названия рабочей группы, которая принимала участие в разработке этого стандарта (Joint Photographic Experts Group).

Двумерное дискретное косинусное преобразование матрицы A с размерами реализуется согласно следующему выражению

Значения B pq называют коэффициентами дискретного косинусного преобразования матрицы A .

(Следует отметить, что индексы матрицы в MATLAB всегда начинаются с 1, а не с 0. Поэтому элементы матрицы, которые представлены в MATLAB как A(1,1) и B(1,1), будут соответствовать элементам A 00 и B 00 из приведенной выше формулы.)

Обратное дискретное косинусное преобразование реализуется согласно выражениям

Выражение обратного дискретного косинусного преобразования может интерпретироваться как представление матрицы A с размерами в виде суммы следующих функций

Эти функции называются основными (базовыми) функциями дискретного косинусного преобразования. Коэффициенты дискретного косинусного преобразования B pq можно рассматривать как весовые при каждой базовой функции. Например, для матрицы с размером элементов существует 64 базовые функции, что продемонстрировано на изображении.

64 базовые функции, которые получены для матрицы с размерами элементов

Горизонтальные частоты увеличиваются слева направо, а вертикальные – сверху вниз.

Матрица дискретных косинусных преобразований

Приложение Image Processing Toolbox предлагает два различных пути реализации дискретных косинусных преобразований. Первый метод реализован в функции dct2. Функция dct2 использует быстрое преобразования Фурье для ускорения вычислений. Второй метод использует матрицу дискретных косинусных преобразований, которая возвращается функцией dctmtx. Матрица преобразований T формируется согласно следующего выражения

Для матрицы A с размерами представляет собой матрицу с размерами , где каждый столбец содержит одномерное дискретное косинусное преобразование A . Двумерное дискретное косинусное преобразование A вычисляется как B=T*A*T’ . Обратное двумерное дискретное косинусное преобразование B вычисляется как T’*B*T.

Дискретные косинусные преобразования и сжатие изображений

В алгоритме сжатия изображений JPEG исходное изображение разделяется на блоки с размерами или элементов. Далее для каждого блока вычисляется двумерное дискретное косинусное преобразование. Коэффициенты дискретных косинусных преобразований квантируются, кодируются и передаются. Получатель JPEG–данных декодирует коэффициенты дискретного косинусного преобразования, вычисляет обратное двумерное дискретное косинусное преобразование в каждом блоке и далее совмещает их вместе в одно изображение.

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

I = imread("cameraman.tif"); I = im2double(I); T = dctmtx(8); B = blkproc(I,,"P1*x*P2",T,T"); mask = ; B2 = blkproc(B,,"P1.*x",mask); I2 = blkproc(B2,,"P1*x*P2",T",T); imshow(I); figure, imshow(I2)

На рисунке представлено два изображения – исходное и реконструированное. При реконструкции изображения использовалось только 15 % коэффициентов дискретных косинусных преобразований. Однако, следует отметить, что качество реконструированного изображения является довольно приемлемым. Для просмотра других свойств дискретного косинусного преобразования см. функцию dctdemo.

Преобразования Радона

Функция radon в приложении Image Processing Toolbox вычисляет матрицу проекций изображения вдоль заданных направлений. Проекция двумерной функции f(x,y) равна интегралу вдоль указанной линии. Функция Радона представляет собой вычисление проекций изображения на оси, которые задаются углами в градусах относительно горизонтали против часовой стрелки. На рисунке показана проекция некоторой фигуры под указанным углом

Параллельно-лучевая проекция с углом поворота theta

На рисунке внизу показаны горизонтальные и вертикальные проекции для простой двумерной функции.

Горизонтальная и вертикальная проекции некоторой простой функции

Проекции могут вычисляться вдоль произвольного угла theta. Встроенная в приложение Image Processing Toolbox функция radon вычисляет проекции изображения вдоль определенных направлений. Проекция двумерной функции f(x,y) на ось x’ представляет собой линейный интеграл

Таким образом, оси x’ y’ задаются поворотом на угол против часовой стрелки.

На изображении внизу проиллюстрировано геометрию преобразования Радона.

Геометрия преобразования Радона

Визуализация преобразований Радона

При проведении преобразований Радона необходимо указать исходное изображение и вектор углов theta.

Radon(I,theta);

R представляет собой матрицу, в которой каждый столбец является преобразованием Радона для одного из углов, который содержится в векторе theta. Вектор xp содержит соответствующие координаты вдоль оси x. Центральный пиксель I определяется согласно выражению floor((size(I)+1)/2).

Рассмотрим, как в преобразованиях Радона вычисляются проекции. Рассмотрим проекции под углом 0° и 45°.

I = zeros(100,100); I(25:75, 25:75) = 1; imshow(I)

Radon(I,); figure; plot(xp,R(:,1)); title("R_{0^o} (x\prime)")

Преобразования Радона при 0°

Figure; plot(xp,R(:,2)); title("R_{45^o} (x\prime)")

Преобразования Радона при 45°

Преобразования Радона при большом числе углов часто отображается в виде изображения. В данном примере рассмотрено преобразования Радона для изображения в виде квадрата при диапазоне углов от 0° до 180° с дискретностью 1°.

Theta = 0:180; = radon(I,theta); imagesc(theta,xp,R); title("R_{\theta} (X\prime)"); xlabel("\theta (degrees)"); ylabel("X\prime"); set(gca,"XTick",0:20:180); colormap(hot); colorbar

Преобразования радона с использованием 180 проекций

Использование преобразований Радона при детектировании линий

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

Наибольший пик в матрице R соответствует =1° и x´= -80. Из центра исходного изображения проводится линия под углом на расстояние x’. Перпендикулярно к этой линии проводится прямая, которая соответствует прямой на исходном изображении. Кроме того, на изображении присутствуют и другие линии, которые представлены в матрице R соответствующими пиками.

Геометрия преобразования Радона при детектировании прямых линий

Обозначим через

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

. (3.21)

Если сигнал существует только внутри прямоугольника со сторонами элементов (рис. 3.4.а), то сигнал определен на всей плоскости и является на ней прямоугольно-периодическим (рис. 3.4.б).

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

Базисные функции этого двумерного представления - двумерные комплексные экспоненты (иногда называемые комплексными синусоидами)

(3.23)

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

Коэффициенты Фурье ряда (3.22) образуют двумерный частотный спектр сигнала и определяются формулой прямого преобразования Фурье:

(3.24)

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

Заметим, что для точного представления дискретного сигнала с двумерным периодом элементов согласно формулам БПФ достаточно конечного числа базисных функций (3.23) - ряд (3.22) является конечным. Это и понятно, поскольку сам представляемый сигнал содержит в одном периоде конечное число точек, т.е. имеет конечное число степеней свободы. Ясно, что число степеней свободы в спектре не может отличаться от числа степеней свободы в самом сигнале.

Остановимся на наиболее существенных свойствах двумерного дискретного спектра Фурье. Вычислим спектральные коэффициенты (3.24) в частотных точках :

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

,

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

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

,

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

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

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

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

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

Преобразование Фурье (Fourier transform)– это разложение функций на синусоиды (далее косинусные функции мы тоже называем синусоидами, т.к. они отличаются от «настоящих» синусоид только фазой). Существует несколько видов преобразования Фурье.

1. Непериодический непрерывный сигнал можно разложить в интеграл Фурье.

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

3. Непериодический дискретный сигнал можно разложить в интеграл Фурье.

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

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

ДПФ вещественного сигнала

Пусть дискретный сигнал x имеет периодN точек. В этом случае его можно представить в виде конечного ряда (т.е. линейной комбинации) дискретных синусоид:

Эквивалентная запись (каждый косинус раскладываем на синус и косинус, но теперь – без фазы):

Рис. 6 . Базисные функции ряда Фурье для 8-точеченого дискретного сигнала. Слева – косинусы, справа – синусы. Частоты увеличиваются сверху вниз.

Базисные синусоиды имеют кратные частоты. Первый член ряда (k =0) – это константа, называемаяпостоянной составляющей (DC offset ) сигнала. Самая первая синусоида (k =1) имеет такую частоту, что ее период совпадает с периодом самого исходного сигнала. Самая высокочастотная составляющая (k =N /2) имеет такую частоту, что ее период равен двум отсчетам. КоэффициентыA k и

B k называютсяспектром сигнала (spectrum ). Они показывают амплитуды си-

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

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

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

Алгоритм обратного преобразования Фурье очевиден (он содержится в формуле ряда Фурье; для проведения синтеза нужно просто подставить в нее коэффициенты). Рассмотрим алгоритм прямого преобразования Фурье, т.е. нахождения коэффициентов A k иB k .

тогональным базисом в пространстве периодических дискретных сигналов с периодом N . Это значит, что для разложения по ней любого элемента пространства (сигнала) нужно посчитать скалярные произведения этого элемента со всеми функциями системы, и полученные коэффициенты нормировать. Тогда для исходного сигнала будет справедлива формула разложения по базису с коэффициентамиA k иB k .

Итак, коэффициенты A k иB k вычисляются как скалярные произведения (в не-

прерывном случае – интегралы от произведения функций, в дискретном случае

– суммы от произведения дискретных сигналов):

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

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

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

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

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

Только функции sin и cos c частотами k/T будут взаимно ортогональны, а это является непременным условием преобразования Фурье. Набор первых функций разложения в ряд Фурье приведен на рисунке 1. При этом длительность функций совпадает с длительностью анализа T .

Теперь спектр сигнала будет выглядеть так, как это показано на рисунке 2.

В данном случае формула вычисления прямого преобразования Фурье (4) преобразуется к следующему виду:

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

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

Теперь рассмотрим как изменились свойства дискретного преобразования Фурье (ДПФ) по сравнению с прямым преобразованием Фурье на ограниченном интервале времени. Когда мы рассматривали дискретизацию аналогового сигнала, мы выяснили, что спектр входного сигнала должен быть ограничен по частоте. Это требование ограничивает количество дискретных составляющих спектра сигнала. Первоначально может показаться, что мы можем ограничить спектр сигнала частотой f д /2, что соответствует количеству частотных составляющих K = N /2 . Однако это не так. Несмотря на то, что спектр сигнала для действительных отсчетов сигнала для положительных частот и отрицательных частот симметричен относительно 0, отрицательные частоты могут потребоваться для некоторых алгоритмов работы со спектрами, например, для . Еще больше отличие получается при выполнении дискретного преобразования Фурье над комплексными отсчетами входного сигнала. В результате для полного описания спектра цифрового сигнала требуется N частотных отсчетов (k = 0, ..., N/2 ).