Преобразование Хартли в задачах цифровой обработки двумерных сигналов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ПРЕОБРАЗОВАНИЕ ХАРТЛИ В ЗАДАЧАХ ЦИФРОВОЙ ОБРАБОТКИ ДВУМЕРНЫХ СИГНАЛОВ
1. ОДНОМЕРНОЕ ДПХ
Важное место в задачах обработки сигналов занимает дискретное преобразование Фурье (ДПФ) N-точечной последовательности у (п), которое определяется по формуле
М-1 _
Y (k) =Jo у (n) exp (-i nk), k = 0, 1… N-1. (1)
Исходная последовательность y (n) может быть единственным образом восстановлена из ее спектра Фурье Y (к) с помощью обратного преобразования
N-1
У (п) — Н'-1 к? о Y (k)exp (i^-nk). п = О, 1… N-1. (2)
Как следует из формул (1) и (2), последовательность коэффициентов ДПФ Y (k), а также последовательность у (п), восстановленная из Y (k) обратным преобразованием Фурье, могут рассматриваться как периодические с периодом N [1], т. е. для любых целых кип
х& lt-*>- = *& lt-*. «>-• У («& gt- = *& lt-"-««>-•
Наличие быстрых методов реализации ДПФ [2−4] делает его эффективным средством для вычисления свертки, корреляции двух функций целочисленного аргумента, оценки спектральной плотности и решения других задач, связанных со спектральным разложением сигналов.
Если последовательность у (п) вещественна, то преобразование Фурье является информационно избыточный, а именно: вещественная часть Y (к)
четная функция, мнимая — нечетная [1], т. е. с учетом периодичности
Y (N-k) = Y*(k), (3)
где звездочка означает комплексное сопряжение. Для использования указанной симметрии в целях ускорения вычислений может быть применен алгоритм совмещенного ДПФ [5], что примерно вдвое сокращает временные затраты.
Более эффективным средством (чем алгоритм совмещенного ДПФ) обработки вещественных сигналов является дискретное преобразование Хартли (ДПХ) [б], которое при введенном определении дискретного преобразования Фурье
представляет собой разность действительной (четной) и мнимой (нечетной) частей преобразования Фурье, ДПХ можно записать в виде [7]:
и -1
YH (k) =nZo y (n)cas (-jp-nk), k = О, 1. N-l, (4)
где casa = cosa + sina. Обратное преобразование Хартли совпадает с прямым с точностью до масштабного коэффициента N"1:
М-1
У (n) = N& quot-'kIo YH (k)cas (-22-nk), n — о, l. N-l.
ДПХ связано с ДПФ следующими формулами [8]:
2Re[Y (k)) = YH (k) + YH (N-k) —
2Im[Y (k)] = ~YH (k) + YH (N-k). (5)
Заметим, что для четной функции у (п) выполняется соотношение Y (N-k) =
н
Yu (k), и тогда из (5) следует, что Y (k) = Y ik), т. е. ДПФ совпадает с ДПХ. н н
Известны быстрые алгоритмы вычисления ДПХ [7, 9, 10]. Их применение с
последующим выполнением операций (5) позволяет, так же как и использование алгоритма совмещенного ДПФ, сократить затраты времени на вычисление дискретного спектра Фурье почти вдвое.
Но преобразование Хартли имеет ряд дополнительных преимуществ. Во-первых, ядро обратного ДПХ совпадает с ядром прямого преобразования, во-вторых, при реализации ДПХ используется только вещественная арифметика. Кроме того, нет необходимости всегда вычислять действительную и мнимую часть преобразования Фурье по формулам (5), многие задачи можно решить, непосредственно используя значения спектра Хартли, определяемые формулой (4). Рассмотрим возможность использования ДПХ в некоторых конкретных задачах.
2. ОДНОМЕРНАЯ СВЕРТКА
Циклическая свертка z (n) двух вещественных периодических (с периодом N) последовательностей х (п) и у (п) определяется соотношением
И-1
z (n) =к?0 х (к)у (n-k), п = О, 1… N-1. (6)
непосредственное вычисление свертки по формуле (6) является весьма трудоемкой операцией для больших N, и при расчетах на ЭВМ выражений типа (6) используется метод ДПФ, который основан на известном соотношении [1] для Фурье-спектров сигналов:
____ Z (k) = X (k) • У (к),
где Z (k), Х (к), У (к) — дискретные преобразования Фурье последовательностей z (n), х (п), у (п) соответственно. При этом вычисление свертки сводится к вычислению трех ДПФ (двух прямых и обратного), а также к перемножению спектров входных сигналов х (п) и у (п).
В работе [7] показана связь между спектрами Хартли последовательностей, участвующих в свертке:
2ZH (k) = xH (k)[YH (k) + YH (N& quot-k)] + VN~k) [YH (k) «YH (N-k)], (7)
где Z (k), X (к) и У (к) — ДПХ последовательностей z (n), х (п) и у (п) н н н
соответственно. Выражение (7) показывает, что вместо ДПФ для реализации циклической свертки может быть применен аппарат ДПХ.
Если одна из функций, например у (п), является четной, то ее ДПХ -также четная последовательность: YH (N-k) = Ун (к), и равенство (7) сводится к умножению спектров Хартли:
ZH (k) = XH (k)YH (k) —
В этом случае применение ДПХ эквивалентно применению ДПФ.
3. ОЦЕНКА СПЕКТРАЛЬНОЙ ПЛОТНОСТИ МОЩНОСТИ
Спектральная плотность мощности периодического сигнала у (п) определяется как взвешенный квадрат модуля его Фурье-спектра:
Фу (к) — N'-11У (к) I2.
Так как для вещественного сигнала у (п) выполняется равенство (3), то IY (N-k) |2 = IY (k) |2, ¦ тогда «з формул (5) следует, что
2iy (k) = 2*y (N-k) = N-'[IYH (k)|2 + IYH (N-k)|2]. (8)
Равенство (8) означает, что спектральная плотность мощности сигнала может быть рассчитана непосредственно на ДПХ.
— 170 —
B (n) = М_1Ю?0 y (ra)y (m+n), n = О, 1… N-l
4. ОЦЕНКА АВТОКОВАРИАЦИОННОЙ ФУНКЦИИ Автоковариационная функция (АКФ) периодического сигнала у (п)
н-i
(n) = 1Г
У
может быть представлена в виде циклической свертки
N -1
У& quot-) = N''kZo y (k)y (n-k), n = 0, 1… N-l,
где y (k) = y (-k), и вычислена методом ДПФ.
В соответствии с дискретной формой теоремы Винера-Хинчина, АКФ связана со спектром мощности следующим соотношением:
1N — i
В (n) = N& quot-1 Z Ф (k)exp (^-nk), п = 0, 1_________ N-1.
у к=о у N
В силу четности спектральной плотности МОЩНОСТИ Фу (к) вещественной функции для вычисления АКФ вместо обратного ДПФ можно использовать обратное ДПФ:
N-1
By (n) = N_1kZ:o фу (к)саэ (-jp-nk), п = 0, 1… N-1.
Во всех описанных вьше задачах использование ДПХ вместо классического ДПФ позволяет добиться существенного (примерно в два раза) сокращения вычислительной сложности.
5. ПРЕОБРАЗОВАНИЕ ХАРТЛИ ДВУМЕРНЫХ СИГНАЛОВ
Двумерное ДПФ функции y (nif п2) целочисленных аргументов и обратное ДПФ определяются по формулам:
N-l N-1 2п
Y (kt, k2) -z nr=0 y (n, n^expt-i^ (niki + ryyi,
k, k = 0, 1… N-l?
1 2
(9)
N-l N-l
У (n, n) = N& quot-2 Z_o kZ=0 У (кг, k2) exp[i N (niki + n2k2)]
1? 12
n, n = 0, 1… N-l.
i 2
Обычно для эффективной реализации ДПФ используют свойство разделимости преобразования (9), т. е. тот факт, что
expC-i-fLfnk + n2k2)] = ехрС-і-ІП-п^ЗехрС-і-^п^].
Двумерное ДПФ выполняется с помощью последовательности одномерных преобразований: сначала осуществляется ДПФ по строкам с помощью ядра
-171-
ехр (-1 -§^п2к2), а затем с помощью ядра ехр (-1 п^) — по столбцам.
Двумерное ДПХ может быть задано двумя способами [11]. Во-первых, по
аналогии с одномерным ДПХ как сумма действительной и мнимой частей
двумерного ДПФ, и тогда
хн (к1'-к2) = Ао Ао У (& quot-1. пг) сав[|2-(п1к1 + пЛ)], (10)
1 2
к2 = 0, 1… N-1.
Это преобразование, в отличие от двумерного ДПФ, не является
разделимым, что затрудняет его эффективную реализацию. Можно определить двумерное ДПХ и по-другому, как разделимое преобразование
*"& lt-*.• V * А Ао *& lt-"-,• п2& gt-саа<-|^пЛ>-са8(-в2-пЛ>->-
1 2
к^ к2 = 0, 1… N-1.
При этом выполнение двумерного преобразования (как и двумерного ДПФ) сводится к последовательности 2Ы одномерных преобразований.
Обратные преобразования для введенных ДПХ совпадают с прямыми с точностью до масштабирующего коэффициента Ы-2.
Неразделимое ДПХ (формула (10)) по аналогии с одномерным случаем связано с ДПФ следующими формулами [11]:
2Не[У (к, к2)] = Ун (к1, к2) + У^Н-к^ Н-к2) — (11. 1)
21т[У (к, к2)] = -Ун (к1# к2) + Ун (Н-к1, Н-к2). (11. 2)
Непосредственной проверкой можно убедиться, что для разделимого ДПХ справедливы соотношения
2Ее[У (к, к2) ] = Уя (Н-к1, к2) + Ув (к1. Н-к2)? (12. 1)
21т[У (к, к2)] = -Ун (к1, к2) + Уд (Н-к1, Н-к2). (12. 2)
Из формул (12) следует, что элементы разделимого ДПХ могут быть получены из комплексных коэффициентов ДПФ следующим образом:
?н (к1' к2) — Кв[У (м-к1,ка)] - 1т[У (к, к2)]. (13)
Вычитая равенство (11. 2) из (11. 1) и равенство (12. 2) из (12. 1). легко убедиться в справедливости приведенного в работе [11] соотношения для пересчета спектров Хартли:
2№ V — № *2& gt-+*я<-Н-V кг& gt-+№ И-к2)-Ув (М-к, Н-к2). (14)
Складывая попарно равенства (11. 1), (11. 2) и (12. 1), (12. 2). получаем аналогичную формулу для расчета разделимого преобразования из ДПХ с неразделимым ядром:
Известно несколько способов [12] вычисления двумерного неразделимого преобразования Хартли, но, по-видимому, наиболее эффективным является способ, связанный с предварительным вычислением разделимого ДПХ, а затем пересчетом спектра по формуле (14).
ей: у (Н-п1, М-п2) = у (п1,п2), то ее преобразования (как Фурье, так и Хартли в обеих формах) также центрально-симметричны. Тогда выражения (11)-(15) значительно упрощаются и вместо них мы имеем:
Из равенств (16)* и (17) следует, что для осесимметричной (по обеим осям) функции у (п, п2) все три преобразования тождественны.
Пусть г (п, п) — циклическая свертка двух вещественных последовательностей х (п, п^) и у (п1(п2). В работе [1] приведена формула для расчета ДПХ функции г (п1"п2) через ДПХ последовательностей х (п1,п2) и у (п1(п2).
При этом вычисление свертки сводится к вычислению трех преобразований Хартли (двух прямых и одного обратного) и расчету спектра Хартли функции г (п, п) по формуле (18).
Поскольку спектры X (к, к) и У (к, к) пересчитываются из ДПХ с
г1 1 2 Н 1 2
разделимым ядром X (к, к) и Уд (к1,к2) соответственно, то вычисление ДПХ последовательности г (п, п) можно сделать более эффективным. Заметим, что из формул (11), (12) следует, что
Если уСп^п) — четная функция, т. е. обладает центральной симметри-
У (к, к2) = ун (кг* к2) — У (к, к2) = Уи (К-кг, к2).
(16)
(17)
6. ВЫЧИСЛЕНИЕ ДВУМЕРНОЙ СВЕРТКИ ПРИ ПОМОЩИ ДПФ
(18)
Тогда
Применение формулы (20) для расчета разделимого ДПХ последовательности z (п^, п^) позволяет избежать пересчета спектров Хартли последовательности y (nit п2). Пересчет спектров Хартли функций x (nifn2) и z (nitn2) целесообразно производить по схеме, изложенной в [12]. С учетом домножения на масштабирующий множитель процедура вычисления спектра ZR (kit kg) из разделимых ДПХ Хв (к. к) и УГк. к) с использованием формулы (20)
1 2 R 1 2 ^
включает в себя 3,5 N умножений и 5,5 N сложений.
Из равенства Z (kt, k2) = Х (к}, к2) Y (kjt к2) с помощью формул (12) и (13) можно получить выражение, непосредственно связывающее элементы
разделимых ДПХ:
Расчет ДПХ гв (к1Э к2) непосредственно по формуле (21) может быть выполнен с использованием б№ умножений и 5И2 сложений. Таким образом, способ вычисления разделимого ДПХ свертки г (п1Э п2) из разделимых ДПХ ХИ^к1,к2^ * УИ^к1,к2^ С ПРОМ0ЖУТОЧНЫМ вычислением НвДвЛИМЫХ ДПХ Хн (к1*к2^
* ^н^к1,кг^ (Формула (20)) представляется более эффективным, чем непо-
средственный расчет ги (к1,к2) по формуле (21).
Если одна из функций, участвующих в свертке, например у (п1Эп2) четная, то выражения (18) и (21) упрощаются и принимают соответственно вид:
(21)
и
(22)
В случае, когда функция у (п1, п2) обладает свойством осевой симметрия (по обеим осям), Ун (Н-к1,к2) = ^(к^к^ и равенство (23) может быть записано как
Ук, Л& gt- - х"& lt-к,-кг>-ув<-к1'-к2>-- & lt-24>-
Равенства (22) и (24) означают, что если одна из функций, участвующих в свертке, обладает свойством какой-либо симметрии, то для вычисления свертки вместо ДПФ может быть использовано преобразование Хартли без
дополнительных затрат при вычислении спектра свертки: для центральной
симметрии — ДПХ с неразделимым ядром, для осевой симметрии — разделимое ДПХ.
Равенство (23) может быть использовано при применении разделимого преобразования Хартли для вычисления свертки двух функций, одна из которых центрально-симметрична.
7. ОЦЕНКА СПЕКТРАЛЬНОЙ ПЛОТНОСТИ И АКФ ДВУМЕРНОГО СИГНАЛА
С учетом формул (11) легко получить выражение для спектральной плотности мощности двумерного сигнала:
4Фу (к^к. ,) = 4М-2|У (к1,к2)|2 = Н-2|[ун (к1,кг) + ««(Н-к,. Н-к2)]
і 2
+
[*"(кГ V — ГН& lt-"--*Г Н-к2& gt-]2}'-
откуда
2*"(к1. к2) = м-г[ї2(к. к2) + **(*¦*,. Н-к2& gt-]. Аналогично для разделимого ДПХ с помощью формул (12) получим:
[V *"•к2& gt--ув ('-,-к, — и-к,& gt-]*+[ї,(«-к,. кг>-+їв<-к,-н-к2"]2}.
4Ф (к, к) = N *
у'- 1 2
АКФ двумерного сигнала у (п, п & gt- может быть вычислена как обратное ДПФ функции фу (к1"к2)» Т- е-
в (П,.п) = н-2 I I- * (к к) ехр[1^-(п к + пк)1.
у V ь =п '- I- -I
к =0 к =0 1 2
Спектральная плотность * (к^ к2) — центрально-симметричная функция,
поэтому для нее ядро обратного ДПФ совпадает с ядром прямого
преобразования, и тогда, воспользовавшись формулами (16) и (17) для четной функции, получим:
Таким образом, для оценки АКФ двумерного вещественного сигнала следует вычислить обратное неразделимое ДПХ его спектральной плотности.
Использование разделимого преобразования для этой цели приводит, в соответствии с формулой (25), к необходимости перестановки результирующей матрицы для размещения отсчетов АКФ на своих местах.
8. ЗАКЛЮЧЕНИЕ
В статье была рассмотрена возможность применения, дискретного
преобразования Хартли вместо ДПФ при вычислении свертки, оценке
спектральной плотности мощности и автоковариационной функции цифрового
сигнала. Исследовано различие двух форм ДПХ: с разделимым и неразделимый ядром. Показано, что оба варианта преобразования Хартли равно применимы в указанных задачах. Приведены формулы для пересчета спектров в различных базисах. Сделан вывод о целесообразности использования разделимого ДПХ при обработке двумерных сигналов.
Литература
1. Оппенгейм A.B., Шафер Р. В. Цифровая обработка сигналов / Пер. с англ. — М.: Связь, 1979. — 416 с.
2. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов / Пер. с англ. — М: Мир, 1978. — 848 с.
3. Burrus C. S., Eschenbasher Р.W. An in-place, in-order
prime factor FFT algorithm. — IEEE, Trans. Acoust., Speach, Signal Processing, 1981, ASSP-29, N 4, p. 806−817.
4. Капорин U.E. Новый алгоритм БПФ. Журнал вычислительной
математики и математической физики, 1980, т. 20, N 4,
с. 1054−1058.
5. Ярославский Л. П. Введение в цифровую обработку изображений. — М.: Советское радио, 1979. — 312 с.
6. Сороко Л. М., Стриж Т. А. Спектральные преобразования на ЭМВ. — Дубна: ОИЯИ, 1972. — 136 С.
7. Брейсуэлл Р. Н. Быстрое преобразование Хартли. ТИИЭР, 1984, Т. 72, N 8, С. 19−28.
8. Bracevell R.N. Discrete Hartley Transform. JOSA, 1983, v. 73, N 12, p. 1832−1835.
9. Прадо Ж. Замечания к статье «Быстрое преобразование
Хартли». ТИИЭР, 1985, т. 73, N 12, С. 182−183.
10. Сергеев В. В., Усачев A.B. Новый алгоритм быстрого пре-
образования Хартли. — В наст, сборнике.
11. Кумарсен Р., Гупта П. К. Алгоритм с векторным основанием
для вычисления двумерного дискретного преобразования Хартли. ТИИЭР, 1986, т. 74, N 5, с. 149−151.
12. Брейсуэлл Р-Н., Бъюнеман О., Хао X., Вилласенор Дж.
Быстрое двумерное преобразование Хартли. ТИИЭР, 1986, т. 74, N 9, с. 128−129.

ПоказатьСвернуть
Заполнить форму текущей работой