информационный портал по вопросам биомедицинской инженерии

Сейчас на сайте 0 пользователей и 0 гостей.

Вход в систему

аватар: Ба-хуссейн Абдулазиз
Ба-хуссейн А.А. БМП-109

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

  Многие сигналы удобно анализировать, раскладывая их на синусоиды (гармо-ники). Тому есть несколько причин. Например, подобным образом работает человеческое ухо. Оно раскладывает звук на отдельные колебания различных частот. Кроме того, можно показать, что синусоиды являются «собственными функциями» линейных систем (т.к. они проходят через линейные системы, не изменяя формы, а могут изменять лишь фазу и амплитуду). Еще одна причина в том, что теорема Котельникова формулируется в терминах спектра сигнала.
Преобразование Фурье (Fourier transform)– это разложение функций на сину-соиды (далее косинусные функции мы тоже называем синусоидами, т.к. они отличаются от «настоящих» синусоид только фазой). Существует несколько видов преобразования Фурье.
1. Непериодический непрерывный сигнал можно разложить в интеграл Фурье.
2. Периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье.
3. Непериодический дискретный сигнал можно разложить в интеграл Фурье.
4. Периодический дискретный сигнал можно разложить в конечный ряд Фу-рье.
Компьютер способен работать только с ограниченным объемом данных, следо-вательно, реально он способен вычислять только последний вид преобразова-ния Фурье. Рассмотрим его подробнее.

ДПФ вещественного сигнала
 
Пусть дискретный сигнал x[n] имеет период N точек. В этом случае его можно представить в виде конечного ряда (т.е. линейной комбинации) дискретных си-нусоид:  
 
Эквивалентная запись (каждый косинус раскладываем на синус и косинус, но теперь – без фазы)


 
Рис. 1. Базисные функции ряда Фурье для 8-точеченого дискретного сигнала. Слева – косинусы, справа – синусы. Частоты увеличиваются сверху вниз.
 
Базисные синусоиды имеют кратные частоты. Первый член ряда (k=0) – это константа, называемая постоянной составляющей (DC offset) сигнала. Самая первая синусоида (k=1) имеет такую частоту, что ее период совпадает с перио-дом самого исходного сигнала. Самая высокочастотная составляющая (k=N/2) имеет такую частоту, что ее период равен двум отсчетам. Коэффициенты Аk  и Bk называются спектром сигнала (spectrum). Они показывают амплитуды си-нусоид, из которых состоит сигнал. Шаг по частоте между двумя соседними синусоидами из разложения Фурье называется частотным разрешением спектра.
На рис. 1 показаны синусоиды, по которым происходит разложение дискретно-го сигнала из 8 точек. Каждая из синусоид состоит из 8 точек, то есть является обычным дискретным сигналом. Непрерывные синусоиды показаны на рисун-ке для наглядности.
 
  Как мы увидим далее, для каждого сигнала можно однозначно определить ко-эффициенты Ak иBk . Зная эти коэффициенты, можно однозначно восстано-вить исходный сигнал, вычислив сумму ряда Фурье в каждой точке. Разложе-ние сигнала на синусоиды (т.е. получение коэффициентов) называется прямым преобразованием Фурье. Обратный процесс – синтез сигнала по синусоидам – называется обратным преобразованием Фурье (inverse Fourier transform). 
 
  Алгоритм обратного преобразования Фурье очевиден (он содержится в форму-ле ряда Фурье; для проведения синтеза нужно просто подставить в нее коэф-фициенты). Рассмотрим алгоритм прямого преобразования Фурье, т.е. нахож-дения коэффициентов Ak и  Bk .
 
   Система функций   от аргумента n является ор-тогональным базисом в пространстве периодических дискретных сигналов с периодом N. Это значит, что для разложения по ней любого элемента про-странства (сигнала) нужно посчитать скалярные произведения этого элемента со всеми функциями системы, и полученные коэффициенты нормировать. То-гда для исходного сигнала будет справедлива формула разложения по базису с коэффициентами Ak и Bk.
 
   Итак, коэффициенты Ak и Bk вычисляются как скалярные произведения (в не-прерывном случае – интегралы от произведения функций, в дискретном случае – суммы от произведения дискретных сигналов):
  Возникает вопрос: почему в исходном сигнале N чисел, а описывается он с по-мощью N+2 коэффициентов? Вопрос разрешается следующим образом: коэффициенты  всегда равны нулю (т.к. соответствующие им «базисные» сигналы тождественно равны нулю в дискретных точках), и их можно отбро-сить при вычислении обратного и прямого преобразований Фурье.
 
Итак, мы выяснили, что спектральное представление сигнала полностью экви-валентно самому сигналу. Между ними можно перемещаться, используя пря-мое и обратное преобразования Фурье. Алгоритм вычисления этих преобразо-ваний содержится в приведенных формулах.
 
  Вычисление преобразований Фурье требует очень большого числа умножений (около ) и вычислений синусов. Существует способ выполнить эти преобра-зования значительно быстрее: примерно за  операций умножения. Этот способ называется быстрым преобразованием Фурье (БПФ, FFT, fast Fourier transform). Он основан на том, что среди множителей (синусов) есть много повторяющихся значений (в силу периодичности синуса). Алгоритм БПФ группирует слагаемые с одинаковыми множителями, значительно сокра-щая число умножений. В результате быстродействие БПФ может в сотни раз превосходить быстродействие стандартного алгоритма (в зависимости от N). При этом следует подчеркнуть, что алгоритм БПФ является точным. Он даже точнее стандартного, т.к. сокращая число операций, он приводит к меньшим ошибкам округления.
 
  Однако у большинства алгоритмов БПФ есть особенность: они способны рабо-тать лишь тогда, когда длина анализируемого сигнала N является степенью двойки. Обычно это не представляет большой проблемы, так как анализируе-мый сигнал всегда можно дополнить нулями до необходимого размера. Число N называется размером или длиной БПФ (FFT size).
Комплексное ДПФ
  До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим те-перь ДПФ на случай комплексных сигналов. Пусть x[n], n=0,…,N-1 – исходный комплексный сигнал, состоящий из N комплексных чисел. Обозначим X[k], k=0,…N-1 – его комплексный спектр, также состоящий из N комплексных чи-сел. Тогда справедливы следующие формулы прямого и обратного преобразо-ваний Фурье
  Если по этим формулам разложить в спектр действительный сигнал, то первые N/2+1 комплексных коэффициентов спектра будут совпадать со спектром «обычного» действительного ДПФ, представленным в «комплексном» виде, а остальные коэффициенты будут их симметричным отражением относительно половины частоты дискретизации. Для косинусных коэффициентов отражение четное, а для синусных – нечетное.
Двумерное ДПФ
Для изображений, представляющих собой двумерный сигнал, спектром являет-ся также двумерный сигнал. Базисные функции преобразования Фурье имеют вид
причем фазы также могут быть раз-личны. На изображении каждая из этих базисных функций представляют собой волну определенной частоты, определенной ориентации и определенной фазы.
Здесь N1xN2 – размер исходного сигнала, он же – размер спектра. k1 и k2 – это номера базисных функций (номера коэффициентов двумерного ДПФ, при ко-торых эти функции находятся). Поскольку размер спектра равен размеру ис-ходного сигнала, то k1 = 0,…,N1-1; k2 = 0,…,N2-1.
n1 и n2 – переменные-аргументы базисных функций. Поскольку область опре-деления базисных функций совпадает с областью определения сигнала, то n1 = 0,…,N1-1; n2 = 0,…,N2-1.
Двумерное ДПФ (в комплексной форме) определяется следующими формула-ми (здесь x[n1,n2] - исходный сигнал, а X[k1,k2] – его спектр): 
Непосредственное вычисление двумерного ДПФ по приведенным формулам требует огромных вычислительных затрат. Однако можно доказать, что дву-мерное ДПФ обладает свойством сеперабельности, т.е. его можно вычислить последовательно по двум измерениям. Для вычисления двумерного ДПФ дос-таточно вычислить одномерные комплексные ДПФ всех строк изображения, а затем вычислить в результирующем «изображении» одномерные комплексные ДПФ всех столбцов. При этом результаты всех одномерных комплексных ДПФ нужно записывать на место исходных данных для этих ДПФ. Например, при вычислении одномерного ДПФ первой строки изображения нужно результат ДПФ записать в первую строку этого изображения (он имеет тот же размер). Для этого нужно каждый «пиксель» хранить в виде комплексного числа.

Таким образом, эффективный алгоритм вычисления ДПФ изображения заклю-чается в вычислении одномерных БПФ сначала от всех строк, а потом – от всех столбцов изображения. 

Комментарии

Отправить комментарий

Содержание этого поля является приватным и не предназначено к показу.
  • Доступны HTML теги: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <img> <table> <td> <tr> <hr> <div> <span> <h1> <h2> <h3> <h4> <h5> <h6> <p> <pre> <adress> <center>
  • Строки и параграфы переносятся автоматически.

Подробнее о форматировании

5 + 6 =
Решите эту простую математическую задачу и введите результат. Например, для 1+3, введите 4.

Комментарии