половины частоты дискретизации. Для косинусных коэффициентов отражение четное, а для синусных – нечетное.
Двумерное ДПФ
Для изображений, представляющих собой двумерный сигнал, спектром является также двумерный сигнал. Базисные функции преобразования Фурье имеют
± |
|
|
2πk1n1 |
|
|
|
|
|
|
|
2πk2 n2 |
|
|||
вид hk1 ,k2 |
(n1 |
, n2 ) = sin |
|
± |
|
|
, причем фазы также могут быть раз- |
N1 |
|
||||||
|
|
|
|
N2 |
|
||
личны. На изображении каждая из этих базисных функций представляют собой волну определенной частоты, определенной ориентации и определенной фазы.
Здесь 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] – его спектр):
|
N1 |
−1N 2 −1 |
|
X [k1,k2 ] = ∑∑x[n1,n2 ] e− jn1k1 (2π N1 )e− jn2 k2 (2π N 2 ) |
|||
|
n1 =0 n2 =0 |
||
|
1 |
|
N1 −1N 2 −1 |
x[n1,n2 ] = |
|
∑∑X [k1,k2 ] e jn1k1 (2π N1 )e jn2 k2 (2π N 2 ) |
|
|
|
||
|
N1N2 k1 =0 k2 =0 |
||
Непосредственное вычисление двумерного ДПФ по приведенным формулам требует огромных вычислительных затрат. Однако можно доказать, что двумерное ДПФ обладает свойством сеперабельности, т.е. его можно вычислить последовательно по двум измерениям. Для вычисления двумерного ДПФ достаточно вычислить одномерные комплексные ДПФ всех строк изображения, а затем вычислить в результирующем «изображении» одномерные комплексные ДПФ всех столбцов. При этом результаты всех одномерных комплексных ДПФ нужно записывать на место исходных данных для этих ДПФ. Например, при вычислении одномерного ДПФ первой строки изображения нужно результат ДПФ записать в первую строку этого изображения (он имеет тот же размер). Для этого нужно каждый «пиксель» хранить в виде комплексного числа.
Таким образом, эффективный алгоритм вычисления ДПФ изображения заключается в вычислении одномерных БПФ сначала от всех строк, а потом – от всех столбцов изображения.
20
Упражнения
1.Частота дискретизации сигнала равна 44100 Гц. Размер БПФ равен 4096. Какова длина анализируемого блока в секундах? По каким частотам (в герцах) будет разложен сигнал?
2.Какое частотное разрешение спектра мы получим в предыдущем примере? Какой размер БПФ нужно использовать, чтобы получить частотное разрешение около 4 Гц?
Ответы
1.Продолжительность сигнала из 4096 точек при данной частоте дискретизации составляет 0.0929 секунды. Сигнал будет разложен на постоянную составляющую (0 Гц) и частоты, кратные частоте первой синусоиды разложения. Период первой синусоиды равен 4096 точкам, что по времени составляет примерно 0.0929 секунды. Значит, частота первой синусоиды будет 10.77 Гц. Частота второй будет 21.53 Гц. И так далее. Частота последней синусоиды, с номером 2048 будет равна половине частоты дискретизации, 22050 Гц.
2.Частотное разрешение равно 10.77 Гц. Очевидно, что при фиксированной частоте дискретизации частотное разрешение пропорционально размеру БПФ. Чтобы получить разрешение 4 Гц, нужно увеличить размер БПФ примерно в 2.5 – 3 раза. Так как размер БПФ может быть равен только степеням двойки, то можно принять размер БПФ за 16384 и получить разрешение 2.7 Гц.
21