Исследуем
особенности спектрального представления
дискретного сигнала, который задан на
отрезке
своими отсчётами
,
взятыми соответственно в моменты
времени
;
полное число отсчётов
(
-
интервал дискретизации).
Методика изучения таких дискретных сигналов состоит в том, что полученная выборка отсчётных значений мысленно повторяется бесконечное число раз. В результате сигнал становится периодическим.
Сопоставив такому сигналу некоторую математическую модель можно воспользоваться разложением в ряд Фурье и найти соответствующие амплитудные коэффициенты. Совокупность этих коэффициентов образует спектр дискретного периодического сигнала.
Воспользуемся моделью в виде последовательности дельта-импульсов. Тогда исходное колебание будет выражено формулой:
(5.1)
Где
– выборочные значения аналогового
сигнала.
-
дискретное преобразование Фурье (ДПФ)
(5.4)
Основные свойства ДПФ
1. ДПФ- линейное преобразование т.е. сумме сигналов отвечает сумма их ДПФ
2.
Число различных коэффициентов
,
вычисляемых по формуле (5.4), равно числу
N
за период; при
коэффициент
3.
Коэффициент
(постоянная составляющая) является
средним значением всех отсчётов:
5.
Пусть отсчётные значения
– вещественные числа. Тогда коэффициенты
ДПФ, номера которых располагаются
симметрично относительно /2,
образуют сопряжённые пары:
Задача
дискретного спектрального анализа
может быть поставлена и по-иному.
Допустим, что коэффициенты
,
образующие ДПФ, заданы. Положим в формуле
(5.2)
и
учтём, что суммируется лишь конечное
число членов ряда, которые отвечают
гармоникам, содержащимся в спектре
исходного сигнала.
Таким образом, получаем формулу для вычисления отсчётных значений
(5.5)
Очевидно, что (5.5) представляет собой формулу обратного дискретного преобразования Фурье (ОДПФ) .
11 Алгоритм быстрого преобразования Фурье. Число вычислительных операций. Сравнение дискретного и быстрого преобразования Фурье.
=0,
1, 2,…,( /2)-1
(5.7)
Учтём, что последовательности коэффициентов, относящихся к чётной и нечётной частям входного массива, являются периодическими с периодом N/2:
Кроме
того, входящий в формулу (5.7) множитель
при
можно преобразовать так:
Отсюда находим выражение для второй половины множества коэффициентов ДПФ
(5.8)
Формулы (5.7) и (5.8) лежат в основе алгоритма БПФ. Далее вычисления строят по итерационному принципу: последовательности отсчётов с чётными и нечётными номерами вновь разбивают на две части. Процесс продолжают до тех пор, пока не получается последовательность, состоящая из единственного элемента. ДПФ этого элемента совпадает с ним самим.
Число
операций, необходимых для вычисления
БПФ оценивается как
.
Выигрыш в скорости вычислений по сравнению с традиционным ДПФ достигает сотен и даже тысяч при достаточных длинах входных массивов.
12.. Z - преобразование и его свойства. Применение Z - преобразования.
При анализе и синтезе дискретных и цифровых устройств Z-преобразование играет такую же роль, как интегральные преобразования Фурье по отношению к непрерывным сигналам.
Пусть
–
числовая последовательность, конечная
или бесконечная, содержащая отсчётные
значения некоторого сигнала. Поставим
ей в однозначное соответствие сумму
ряда по отрицательным степеням комплексной
переменнойZ:
(5.9)
Эта
сумма называется Z-преобразованием
последовательности
.
Свойства дискретных последовательностей
чисел можно изучать, исследуя ихZ-преобразования
обычными методами математического
анализа.
Данное
выражение имеет смысл при |Z|>
.
Обратное Z- преобразование
Пусть
x(z)
– функция комплексной переменной Z.
Замечательное свойство Z-преобразование
состоит в том, что функция x(z)
определяет всю бесконечную совокупность
отсчётов (
).
Действительно,
умножим обе части ряда (5.9) на множитель
:
Интегралы от всех слагаемых правой части обратятся в нуль, за исключением слагаемого с номером m, поэтому:
(5.11)
Данное выражение носит название обратное Z-преобразование.
Важнейшие свойства Z -преобразования:
1.
Линейность
.
Если
и
- некоторые дискретные сигналы, причём
известны соответствующиеZ-преобразования
x(z)
и y(z),
то сигналу
будет отвечать преобразованиепри любых постоянных
и
.
Доказательство проводится путём
подстановки суммы в формулу (5.9).
2.
Z
-преобразование
смещённого сигнала
.
Рассмотрим дискретный сигнал
,
получающийся из дискретного сигнала
путём сдвига на одну позицию в сторону
запаздывания, т.е. когда
.
Непосредственно вычисляяZ-преобразование,
получаем следующий результат:
Таким
образом, символ
служит оператором единичной задержки
(на один интервал дискретизации) вZ-области.
3. Z -преобразование свёртки . Пусть x(z) и y(z) – непрерывные сигналы, для которых определена свёртка:
(5.13)
Применительно
к дискретным сигналам по аналогии с
(5.13) принято вводить дискретную свёртку
– последовательность чисел общий член
которой:
Подобную дискретную свёртку называют линейной
Вычислим Z-преобразование дискретной свёртки:
(5.15)
Итак, свёртке двух дискретных сигналов отвечает произведение Z-преобразований.
Линейная фильтрация изображений может осуществляться как в пространственной, так и в частотной области. При этом считается, что "низким" пространственным частотам соответствует основное содержание изображения - фон и крупноразмерные объекты, а "высоким" пространственным частотам - мелкоразмерные объекты, мелкие детали крупных форм и шумовая компонента.
Традиционно для перехода в область пространственных частот используются методы, основанные на $\textit{преобразовании Фурье}$. В последние годы все большее применение находят также методы, основанные на $\textit{вейвлет-преобразовании (wavelet-transform)}$.
Преобразование Фурье.
Преобразование Фурье позволяет представить практически любую функцию или набор данных в виде комбинации таких тригонометрических функций, как синус и косинус, что позволяет выявить периодические компоненты в данных и оценить их вклад в структуру исходных данных или форму функции. Традиционно различаются три основные формы преобразования Фурье: интегральное преобразование Фурье, ряды Фурье и дискретное преобразование Фурье.
Интегральное преобразование Фурье переводит вещественную функцию в пару вещественных функций или одну комплексную функцию в другую.
Вещественную функцию $f(x)$ можно разложить по ортогональной системе тригонометрических функций, то есть представить в виде
$$ f\left(x \right)=\int\limits_0^\infty {A\left(\omega \right)} \cos \left({2\pi \omega x} \right)d\omega -\int\limits_0^\infty {B\left(\omega \right)} \sin \left({2\pi \omega x} \right)d\omega , $$
где $A(\omega)$ и $B(\omega)$ называются интегральными косинус- и синус-преобразованиями:
$$ A\left(\omega \right)=2\int\limits_{-\infty }^{+\infty } {f\left(x \right)} \cos \left({2\pi \omega x} \right)dx; \quad B\left(\omega \right)=2\int\limits_{-\infty }^{+\infty } {f\left(x \right)} \sin \left({2\pi \omega x} \right)dx. $$
Ряд Фурье представляет периодическую функцию $f(x)$, заданную на интервале $$, в виде бесконечного ряда по синусам и косинусам. То есть периодической функции $f(x)$ ставится в соответствие бесконечная последовательность коэффициентов Фурье
$$ f\left(x \right)=\frac{A_0 }{2}+\sum\limits_{n=1}^\infty {A_n } \cos \left({\frac{2\pi xn}{b-a}} \right)+\sum\limits_{n=1}^\infty {B_n \sin \left({\frac{2\pi xn}{b-a}} \right)} , $$
$$ A_n =\frac{2}{b-a}\int\limits_a^b {f\left(x \right)} \cos \left({\frac{2\pi nx}{b-a}} \right)dx; \quad B_n =\frac{2}{b-a}\int\limits_a^b {f\left(x \right)} \sin \left({\frac{2\pi nx}{b-a}} \right)dx. $$
Дискретное преобразование Фурье переводит конечную последовательность вещественных чисел в конечную последовательность коэффициентов Фурье.
Пусть $\left\{ {x_i } \right\}, i= 0,\ldots, N-1 $ - последовательность вещественных чисел - например, отсчеты яркости пикселов по строке изображения. Эту последовательность можно представить в виде комбинации конечных сумм вида
$$ x_i =a_0 +\sum\limits_{n=1}^{N/2} {a_n } \cos \left({\frac{2\pi ni}{N}} \right)+\sum\limits_{n=1}^{N/2} {b_n \sin \left({\frac{2\pi ni}{N}} \right)} , $$
$$ a_0 =\frac{1}{N}\sum\limits_{i=0}^{N-1} {x_i } , \quad a_{N/2} =\frac{1}{N}\sum\limits_{i=0}^{N-1} {x_i } \left({-1} \right)^i, \quad a_k =\frac{2}{N}\sum\limits_{i=0}^{N-1} {x_i \cos \left({\frac{2\pi ik}{N}} \right)}, $$
$$
b_k =\frac{2}{N}\sum\limits_{i=0}^{N-1} {x_i \sin \left({\frac{2\pi ik}{N}} \right)},
\quad
i\le k Основное отличие между тремя формами преобразования Фурье заключается в том,
что если интегральное преобразование Фурье определено по всей области
определения функции $f(x)$, то ряд и дискретное преобразование Фурье
определены только на дискретном множестве точек, бесконечном для ряда Фурье
и конечном для дискретного преобразования. Как видно из определений преобразования Фурье, наибольший интерес для систем
цифровой обработки сигналов представляет дискретное преобразование Фурье.
Данные, получаемые с цифровых носителей или источников информации,
представляют собой упорядоченные наборы чисел, записанные в виде векторов
или матриц. Обычно принимается, что входные данные для дискретного преобразования
представляют собой равномерную выборку с шагом $\Delta $, при этом величина
$T=N\Delta $ называется длиной записи, или основным периодом. Основная
частота равна $1/T$. Таким образом, в дискретном преобразовании Фурье
производится разложение входных данных по частотам, которые являются целым
кратным основной частоты. Максимальная частота, определяемая размерностью
входных данных, равна $1/2 \Delta $ и называется $\it{частотой Найквиста}$. Учет частоты Найквиста
имеет важное значение при использовании дискретного преобразования. Если
входные данные имеют периодические составляющие с частотами, превышающими
частоту Найквиста, то при вычислении дискретного преобразования Фурье
произойдет подмена высокочастотных данных более низкой частотой, что может
привести к ошибкам при интерпретации результатов дискретного преобразования. Важным инструментом анализа данных является также $\it{энергетический спектр}$. Мощность сигнала на
частоте $\omega $ определяется следующим образом: $$
P \left(\omega \right)=\frac{1}{2}\left({A \left(\omega \right)^2+B \left(\omega \right)^2} \right) .
$$ Эту величину часто называют $\it{энергией сигнала}$ на частоте $\omega $. Согласно теореме
Парсеваля общая энергия входного сигнала равна сумме энергий по всем
частотам. $$
E=\sum\limits_{i=0}^{N-1} {x_i^2 } =\sum\limits_{i=0}^{N/2} {P \left({\omega _i } \right)} .
$$ График зависимости мощности от частоты называется энергетическим спектром
или спектром мощности. Энергетический спектр позволяет выявлять скрытые
периодичности входных данных и оценивать вклад определенных частотных
компонент в структуру исходных данных. Кроме тригонометрической формы записи дискретного преобразования Фурье
широко используется $\it{комплексное представление}$. Комплексная форма записи преобразования Фурье широко
используется в многомерном анализе и в частности при обработке изображений. Переход из тригонометрической в комплексную форму осуществляется на
основании формулы Эйлера $$
e^{j\omega t}=\cos \omega t+j\sin \omega t,
\quad
j=\sqrt {-1} .
$$ Если входная последовательность представляет собой $N$ комплексных чисел, то
ее дискретное преобразование Фурье будет иметь вид $$
G_m =\frac{1}{N}\sum\limits_{n=1}^{N-1} {x_n } e^{\frac{-2\pi jmn}{N}},
$$ а обратное преобразование $$
x_m =\sum\limits_{n=1}^{N-1} {G_n } e^{\frac{2\pi jmn}{N}}.
$$ Если входная последовательность представляет собой массив вещественных
чисел, то для нее существует как комплексное, так и синусно-косинусное
дискретное преобразование. Взаимосвязь этих представлений выражается
следующим образом: $$
a_0 =G_0 ,
\quad
G_k =\left({a_k -jb_k } \right)/2,
\quad
1\le k\le N/2;
$$ остальные $N/2$ значений преобразования являются комплексно сопряженными и не
несут дополнительной информации. Поэтому график спектра мощности дискретного
преобразования Фурье симметричен относительно $N/2$. Простейший способ вычисления дискретного преобразования Фурье (ДПФ) -
прямое суммирование, оно приводит к $N$ операциям на каждый коэффициент. Всего
коэффициентов $N$, так что общая сложность $O\left({N^2} \right)$. Такой
подход не представляет практического интереса, так как существуют гораздо
более эффективные способы вычисления ДПФ, называемые быстрым преобразованием
Фурье (БПФ), имеющее сложность $O (N\log N)$.
БПФ применяется только к последовательностям, имеющим длину (число
элементов), кратную степени 2. Наиболее общий принцип, заложенный в алгоритм
БПФ, заключается в разбиении входной последовательности на две
последовательности половинной длины. Первая последовательность заполняется
данными с четными номерами, а вторая - с нечетными. Это дает возможность
вычисления коэффициентов ДПФ через два преобразования размерностью $N/2$. Обозначим $\omega _m =e^{\frac{2\pi j}{m}}$, тогда $G_m =\sum\limits_{n=1}^{(N/2)-1} {x_{2n} } \omega
_{N/2}^{mn} +\sum\limits_{n=1}^{(N/2)-1} {x_{2n+1} }
\omega _{N/2}^{mn} \omega _N^m $. Для $m < N/2$ тогда можно записать $G_m =G_{\textrm{even}} \left(m \right)+G_{\textrm{odd}}
\left(m \right)\omega _N^m $. Учитывая, что элементы ДПФ с индексом
б ольшим, чем $N/2$, являются комплексно сопряженными к элементам с индексами
меньшими $N/2$, можно записать $G_{m+(N/2)} =G_{\textrm{even}} \left(m \right)-G_{\textrm{odd}}
\left(m \right)\omega _N^m $. Таким образом, можно вычислить БПФ длиной $N$,
используя два ДПФ длиной $N/2$. Полный алгоритм БПФ заключается в рекурсивном
выполнении вышеописанной процедуры, начиная с объединения одиночных элементов в пары,
затем в четверки и так до полного охвата исходного массива данных. Дискретное преобразование Фурье для двумерного массива чисел размера
$M\times N$ определяется следующим образом: $$
G_{uw} =\frac{1}{NM}\sum\limits_{n=1}^{N-1} {\sum\limits_{m=1}^{M-1} {x_{mn}
} } e^{{-2\pi j\left[ {\frac{mu}{M}+\frac{nw}{N}} \right]} },
$$ а обратное преобразование $$
x_{mn} =\sum\limits_{u=1}^{N-1} {\sum\limits_{w=1}^{M-1} {G_{uw} } }
e^{ {2\pi j\left[ {\frac{mu}{M}+\frac{nw}{N}}
\right]} }.
$$ В случае обработки изображений компоненты двумерного преобразования Фурье
называют $\textit{пространственными частотами}$. Важным свойством двумерного преобразования Фурье является возможность его
вычисления с использованием процедуры одномерного БПФ: $$
G_{uw} =\frac{1}{N}\sum\limits_{n=1}^{N-1} { \left[
{\frac{1}{M}\sum\limits_{m=0}^{M-1} {x_{mn} e^{\frac{-2\pi jmw}{M}}} } \right] } e^{\frac{-2\pi jnu}{N}},
$$ Здесь выражение в квадратных скобках есть одномерное преобразование строки
матрицы данных, которое может быть выполнено с одномерным БПФ. Таким
образом, для получения двумерного преобразования Фурье нужно сначала
вычислить одномерные преобразования строк, записать результаты в исходную
матрицу и вычислить
одномерные преобразования для столбцов полученной
матрицы. При вычислении двумерного преобразования Фурье низкие частоты будут
сосредоточены в углах матрицы, что не очень удобно для дальнейшей обработки
полученной информации. Для перевода получения представления двумерного
преобразования Фурье, в котором низкие частоты сосредоточены в центре
матрицы, можно выполнить простую процедуру, заключающуюся в умножении
исходных данных на $-1^{m+n}$. На рис. 16 показаны исходное изображение и его Фурье-образ. Полутоновое изображение и его Фурье-образ (изображения получены в системе LabVIEW) Свертка функций $s(t)$ и $r(t)$ определяется как $$
s\ast r\cong r\ast s\cong \int\limits_{-\infty }^{+\infty } {s(\tau)} r(t-\tau)d\tau .
$$ На практике приходится иметь дело с дискретной сверткой, в которой
непрерывные функции заменяются наборами значений в узлах равномерной сетки
(обычно берется целочисленная сетка): $$
(r\ast s)_j \cong \sum\limits_{k=-N}^P {s_{j-k} r_k }.
$$ Здесь $-N$ и $P$ определяют диапазон, за пределами которого $r(t) = 0$. При вычислении свертки с помощью преобразования Фурье используется свойство
преобразования Фурье, согласно которому произведение образов функций в
частотной области эквивалентно свертке этих функций во временн ой области. Для вычисления сверки необходимо преобразовать исходные данные в частотную
область, то есть вычислить их преобразование Фурье, перемножить результаты
преобразования и выполнить обратное преобразование Фурье, восстановив
исходное представление. Единственная тонкость в работе алгоритма связана с тем, что в случае
дискретного преобразования Фурье (в отличие от непрерывного) происходит
свертка двух периодических функций, то есть наши наборы значений задают
именно периоды этих функций, а не просто значения на каком-то отдельном
участке оси. То есть алгоритм считает, что за точкой $x_{N }$ идет не ноль, а
точка $x_{0}$, и так далее по кругу. Поэтому, чтобы свертка корректно
считалась, необходимо приписать к сигналу достаточно длинную
последовательность нулей. Линейные методы фильтрации относятся к числу хорошо структурированных
методов, для которых разработаны эффективные вычислительные схемы,
основанные на быстрых алгоритмах свертки и спектральном анализе. В общем
виде линейные алгоритмы фильтрации выполняют преобразование вида $$
f"(x,y) = \int\int f(\zeta -x, \eta -y)K (\zeta , \eta) d \zeta d \eta ,
$$ где $K(\zeta ,\eta)$ - ядро линейного преобразования. При дискретном представлении сигнала интеграл в данной формуле вырождается
во взвешенную сумму отсчетов исходного изображения в пределах некоторой
апертуры. При этом выбор ядра $K(\zeta ,\eta)$ в соответствии с тем или
иным критерием оптимальности может привести к ряду полезных свойств
(гауссовское сглаживание при регуляризации задачи численного
дифференцирования изображения и др.). Наиболее эффективно линейные методы обработки реализуются в частотной
области. Использование Фурье-образа изображения для выполнения операций фильтрации
обусловлено прежде всего более высокой производительностью таких операций.
Как правило, выполнение прямого и обратного двумерного преобразования Фурье
и умножение на коэффициенты Фурье-образа фильтра занимает меньше времени,
чем выполнение двумерной свертки исходного изображения. Алгоритмы фильтрации в частотной области основываются на теореме о свертке.
В двумерном случае преобразование свертки выглядит следующим образом: $$
G\left({u,v} \right)=H\left({u,v} \right)F\left({u,v} \right),
$$ где $G$ - Фурье-образ результата свертки, $H$ - Фурье-образ фильтра, а
$F$ - Фурье-образ исходного изображения. То есть в частотной области двумерная
свертка заменяется поэлементным перемножением образов исходного изображения
и соответствующего фильтра. Для выполнения свертки необходимо выполнить следующие действия. Связь между функцией фильтра в частотной и пространственной области можно
определить, используя теорему о свертке $$
\Phi \left[ {f\left({x,y} \right)\ast h(x,y)} \right]=F\left({u,v}
\right)H\left({u,v} \right),
$$ $$
\Phi \left[ {f\left({x,y} \right)h(x,y)} \right]=F\left({u,v} \right)\ast
H\left({u,v} \right).
$$ Свертка функции с импульсной функцией может быть представлена следующим
образом: $$
\sum\limits_{x=0}^M {\sum\limits_{y=0}^N {s\left({x,y} \right)}
} \delta \left({x-x_0 ,y-y_0 } \right)=s(x_0 ,y_0).
$$ Фурье-преобразование импульсной функции $$
F\left({u,v} \right)=\frac{1}{MN}\sum\limits_{x=0}^M
{\sum\limits_{y=0}^N {\delta \left({x,y} \right) } } e^{ {-2\pi
j\left({\frac{ux}{M}+\frac{vy}{N}}
\right)} }
=\frac{1}{MN}.
$$ Пусть $f(x,y) = \delta (x,y)$, тогда свертка $$
f\left({x,y} \right)\ast h(x,y)=\frac{1}{MN}h\left({x,y} \right),
$$ $$
\Phi \left[ {\delta \left({x,y} \right)\ast h(x,y)} \right]=\Phi
\left[ {\delta \left({x,y} \right)} \right]H\left({u,v}
\right)=\frac{1}{MN}H\left({u,v} \right).
$$ Из этих выражений видно, что функции фильтра в частотной и пространственной
областях взаимосвязаны через преобразование Фурье. Для данной функции
фильтра в частотной области всегда можно найти соответствующий фильтр в
пространственной области, применив обратное преобразование Фурье. То же верно
и для обратного случая. Используя данную взаимосвязь, можно определить
процедуру синтеза пространственных линейных фильтров.
{$\textit{Идеальный фильтр низких частот}$} $H(u,v)$ имеет вид
$$H(u,v) = 1, \quad \mbox{если }D(u,v) < D_0 ,$$
$$H(u,v) = 0, \quad \mbox{если }D(u,v) \ge D_0 ,$$
где $D\left({u,v} \right)=\sqrt {\left({u-\frac{M}{2}} \right)^2+\left({v-\frac{N}{2}} \right)^2}$ - расстояние от центра частотной плоскости. {$\textit{Идеальный высокочастотный фильтр}$} получается путем
инверсии идеального низкочастотного фильтра: $$
H"(u,v) = 1-H(u,v).
$$ Здесь происходит полное подавление низкочастотных компонент при сохранении
высокочастотных. Однако как и в случае идеального низкочастотного фильтра,
его применение чревато появлением существенных искажений. Для синтеза фильтров с минимальными искажениями используются различные
подходы. Одним из них является синтез фильтров на основе экспоненты. Такие
фильтры привносят минимальные искажения в результирующее изображение и
удобны для синтеза в частотной области. Широко используемым при обработке изображений является семейство фильтров на
основании вещественной функции Гаусса. $\textit{Низкочастотный гауссовский фильтр}$ имеет вид $$
h\left(x \right)=\sqrt {2\pi } \sigma Ae^{-2\left({\pi \sigma
x} \right)^2} \mbox{ и } H\left(u \right)=Ae^{-\frac{u^2}{2\sigma ^2}}
$$ Чем уже профиль фильтра в частотной области (чем больше $\sigma $), тем он
шире в пространственной. {$\textit{Высокочастотный гауссовский фильтр}$} имеет вид $$
h\left(x \right)=\sqrt {2\pi } \sigma _A Ae^{-2\left({\pi \sigma _A x}
\right)^2}-\sqrt {2\pi } \sigma _B Be^{-2\left({\pi \sigma _B x} \right)^2 },
$$ $$
H\left(u \right)=Ae^{-\frac{u^2}{2\sigma _A^2 }}-Be^{-\frac{u^2}{2\sigma
_B^2 }}.
$$ В двумерном случае {$\it{низкочастотный}$} фильтр гаусса
выглядит следующим образом: $$
H\left({u,v} \right)=e^{-\frac{D^2\left({u,v} \right)}{2D_0^2 }}.
$$ {$\it{Высокочастотный}$} гауссовский фильтр имеет вид $$
H\left({u,v} \right)=1-e^{-\frac{D^2\left({u,v} \right)}{2D_0^2 }}.
$$ Рассмотрим пример фильтрации изображения (рис. 1) в частотной области
(рис. 17 - 22). Заметим, что частотная фильтрация изображения может
иметь смысл как сглаживания ($\textit{низкочастотная фильтрация}$), так и выделения контуров и мелкоразмерных
объектов ($\textit{высокочастотная фильтрация}$). Как видно из рис. 17, 19, по мере нарастания "мощности" фильтрации в низкочастотной
составляющей изображения все сильнее проявляется эффект "кажущейся расфокусировки" или
$\it{размытия}$ изображения. В то же время в высокочастотную составляющую, где в начале
наблюдаются лишь контура объектов, постепенно переходит большая часть
информационного содержания изображения (рис. 18, 20 - 22). Рассмотрим теперь поведение высокочастотных и низкочастотных фильтров
(рис. 23 - 28)
в присутствии аддитивного гауссовского шума на изображении (рис. 7). Как видно из рис. 23, 25, свойства низкочастотных фильтров по
подавлению аддитивной случайной помехи аналогичны свойствам ранее
рассмотренных линейных фильтров - при достаточной мощности фильтра помехи
подавляются, однако платой за это является сильное размытие контуров и
"расфокусировка" всего изображения. Высокочастотная составляющая
зашумленного изображения перестает быть информативной, так как помимо
контурной и объектовой информации там теперь также полностью присутствует и
шумовая компонента (рис. 27, 28). Применение частотных методов наиболее целесообразно в случае, когда известны
статистическая модель шумового процесса или/и оптическая передаточная
функция канала передачи изображения. Учесть такие априорные данные удобно,
выбрав в качестве восстанавливающего фильтра обобщенный управляемый
(параметрами $\sigma$ и $\mu$) фильтр следующего вида: $$
F(w_1,w_2)=
\left[
{ \frac
{1}
{P(w_1,w_2)}
}\right]
\cdot
\left[
{\frac
{{\vert P(w_1,w_2) \vert }^2}
{\vert P(w_1,w_2) \vert ^2 + \alpha \vert Q(w_1,w_2) \vert ^2}
}\right].
$$ где $0 < \sigma < 1$, $0 < \mu < 1$ - назначаемые параметры фильтра,
$P(w_{1}$, $w_{2})$ - передаточная функция системы, $Q(w_{1}$, $w_{2})$ -
стабилизатор фильтра, согласованный с энергетическим спектром фона. Выбор
параметров $\sigma = 1$, $\mu = 0$ приводит к чисто инверсной фильтрации,
$\sigma =\mu = 1$ к \it{винеровской фильтрации}, что позволяет получить изображение, близкое к
истинному в смысле минимума СКО при условии, что спектры
плотности мощности
изображения и его шумовой компоненты априорно известны. Для дальнейшего
улучшения эффекта сглаживания в алгоритм линейной (винеровской) фильтрации
вводят адаптацию, основанную на оценке локальных статистик: математического
ожидания $M(P)$ и дисперсии $\sigma (P)$. Этот алгоритм эффективно фильтрует
засоренные однородные поверхности (области) фона. Однако при попадании в
скользящее окно обработки неоднородных участков фона импульсная
характеристика фильтра сужается ввиду резкого изменения локальных статистик,
и эти неоднородности (контуры, пятна) передаются практически без
расфокусировки, свойственной неадаптивным методам линейной фильтрации. К достоинствам методов линейной фильтрации следует отнести их ясный
физический смысл и простоту анализа результатов. Однако при резком ухудшении
соотношения сигнал/шум, при возможных вариантах площадного зашумления и
наличии высокоамплитудного импульсного шума линейные методы предварительной
обработки могут оказаться недостаточными. В этой ситуации значительно более
мощными оказываются нелинейные методы. Введение
На лабораторном занятии были изучены возможности по дискретному тригонометрическому преобразованию (ДТП) со следующих точек зрения: 1. Проверили свойство обратимости заданного ДТП. 2. Исследовали линейность предложенного ДТП. 3. Изучили особенности повтора спектра у проверяемого ДТП. 4. Определили наличие симметричного отражения спектра у ДТП, а именно 4.1. наличие центральной симметрии, 4.2. наличие осевой (вертикальной) симметрии. 5. Рассмотрели влияние фазовых сдвигов сигнала на результирующее ДТП. 6. Проверили наличие свойства подобия для заданного преобразования. 7. Исследовали возможность фильтрации сигналов с помощью заданного ДТП. 8. Проверили экспериментально сохранение энергии исследуемым ДТП. 9. Обнаружили связь данного ДТП с дискретным преобразованием Фурье. Так же были рассмотрены различные входные сигналы для более представительного анализа. Наиболее известным среди дискретных функциональных преобразований является дискретное преобразование Фурье (ДПФ) Дискретное преобразование Фурье
Дискретное преобразование Фурье определяет линейчатый спектр дискретизованной периодической функции времени. Обратное дискретное преобразование Фурье позволяет восстановить функцию времени по ее спектру. Эти преобразования обычно сокращенно называют соответственно ДПФ и ОДПФ. ДПФ служит для анализа периодических функций, и его можно получить исходя из теории рядов Фурье. Пусть x0(t) - непрерывная периодическая функция с периодом Р и частотой f0 = 1/P так что Функцию x0(t) можно разложить в ряд Фурье: где коэффициенты разложения Х0(n) заданы формулой Обычно x0(t) является действительной функцией, и тогда Х0(n) - комплексные (но это ограничение не обязательно). Поскольку мы рассматриваем x0 как функцию времени, то Х0(n) можно назвать комплексным спектром x0(t). По действительной и мнимой частям X0(n).можно найти амплитуду и фазу составляющих, образующих колебание x0(t). Рассмотрим дискретизацию периодической функции x0(t). Для того чтобы эту функцию можно было дискретизовать однозначно, в ее спектре не должно быть составляющих с частотой, выше некоторой частоты f1 т. е. где n1 - целое значение n, задающее частоту f1. На фиг. 1 показаны такой ограниченный спектр и колебание, которому он соответствует. интервал дискретизации Т равен так что число отсчетов на период будет Фиг. 1. Периодическая функция x0(t) с ограниченной полосой частот и ее спектр X0(n). 1В результате дискретизации получаем периодическое, нормализованное относительно Т колебание вида Это колебание определено на интервале, равном его периоду, т. е. Поскольку x(t/T) – периодическая функция для расчета коэффициентов ряда Фурье используется соотношение (2) (Замена Р на /V в делителе и пределах интегрирования соответствует переходу к нормализованной переменной.) Подставляя выражение (3), получаем Известно, что Окончательно с учетом того, что по определению Соотношение, связывающее x(k) с Х(n), может быть получено непосредственно из формулы (1), если подставить t=kT и учесть, что при ограниченной ширине спектра функции x0(t) сумма содержит конечное число членов. Итак, Следует заметить, что x(k) -периодическая функция, т. е. и аналогично Тот факт, что спектр является периодическим, объясняется периодичностью спектра любой дискретизованной функции, а его дискретный характер связан с тем, что сама дискретизуемая функция также периодическая. Итак, при дискретизации периодической функции x0(t) соотношение (4) позволяет по выборкам x0(t) найти спектр Х(n), который на интервале 0 ≤ n ≤ N - 1 в точности равен спектру Х0(n) исходной периодической функции. Функция x(k) и ее спектр графически представлены на фиг. 2. Поскольку соотношение (5.4) получено на основании теоремы отсчетов, оно является точным и экономичным (при расчетах) эквивалентом исходного интегрального соотношения (2) и может быть использовано для вычисления коэффициентов разложения на ЭВМ. Соотношения (4) и (5) будем называть дискретным преобразованием Фурье (ДПФ) и обратным дискретным преобразованием Фурье (ОДПФ) соответственно. Заметим, что переменная n меняется здесь от нуля до N-1. Получаемый спектр можно интерпретировать следующим образом. Первые (N/2-1) точек Х(n) -соответствуют (N/2 - 1) спектральным линиям Х0(n) на положительных частотах, как показано на фиг. 5.3, а последние (N/2-1) точек Х(n) соответствуют (N/2-1) спектральным линиям на отрицательных частотах. Пара преобразований, заданная соотношениями (4) и (5), встречается и в другом виде. Например, множитель 1 / N и знак минус у экспоненты могут быть записаны как в прямом, так и в обратном преобразовании, общий смысл при этом не меняется. Естественно, спектр в этом случае нельзя непосредственно отождествлять с тем, который определен формулой (2). Иногда оба преобразования приводятся с одинаковыми множителями (1 / N)1/2. Фиг. 2. Дискретизированная периодическая функция x(k) и ее периодический спектр Х(n). Фиг. 3. Соотношение между коэффициентами ряда Фурье и ДПФ. Свойства ДПФ
Некоторые свойства ДПФ играют в практических вопросах обработки сигналов важную роль. Линейность
Если xр(n) и ур(n) - периодические последовательности (с периодом в N отсчетов каждая), а Хр(k) и Yp(k) - их ДПФ, то дискретное преобразование Фурье последовательности хр(n) + + ур(n) равно Хр(k) + Yp(k). Это положение справедливо и для последовательностей конечной длины. Сдвиг
Если последовательность хр(n) периодическая с периодом в N отсчетов, а ее ДПФ равно Хр(k), то ДПФ периодической последовательности вида хр(n-n0) будет равно. Фиг. 4. К определению ДПФ сдвинутой последовательности. При анализе последовательностей конечной длины необходимо учитывать специфический характер временного сдвига последовательности. Так, на фиг. 4, а изображена конечная последовательность х (п) длиной в N отсчетов. Там же крестиками изображены отсчеты эквивалентной периодической последовательности хр(n), имеющей то же ДПФ, что и х(n). Чтобы найти ДПФ сдвинутой последовательности х(n - n0), причем n0 < N, следует рассмотреть сдвинутую периодическую последовательность Хр(n - n0) и в качестве эквивалентной сдвинутой конечной последовательности (имеющей ДПФ j принять отрезок последовательности хр(n - n0) в интервале 0 ≤ n ≤ N - 1. Таким образом, с точки зрения ДПФ последовательность х(n – n0) получается путем кругового сдвига элементов последовательности х(n) на n0 отсчетов Свойства симметрии
Если периодическая последовательность хр(n) с периодом в./V отсчетов является действительной, то ее ДПФ Хр(k) удовлетворяет следующим условиям симметрии: Аналогичные равенства справедливы и для конечной действительной последовательности х(n), имеющей N-точечное ДПФ X(k). Если ввести дополнительное условие симметрии последовательности хp(n), т. е. считать, что то окажется, что Хр(k) может быть только действительной. Поскольку чаще всего приходится иметь дело с действительными последовательностями, то, вычислив одно ДПФ, можно получить ДПФ двух последовательностей, используя свойства симметрии (6). Рассмотрим действительные периодические последовательности хр(n) и ур(n) с периодами в N отсчетов и N-точечными ДПФ Хр(k) и Yp(k) соответственно. Введем комплексную последовательность zp(n) вида Ее ДПФ равно Выделяя действительную и мнимую части равенства (10), получим Действительные части Хр(k) и Yp(k) симметричны, а мнимые - антисимметричны, поэтому их легко разделить, используя операции сложения и вычитания: Итак, вычисляя одно N-точечное ДПФ, удается преобразовать сразу две действительные последовательности длиной по N отсчетов. Если эти последовательности являются еще и симметричными, то число операций, необходимых для получения их ДПФ, можно сократить еще больше. Похожая информация. Традиционная техника “начального уровня”, сравнения текущего изображения с эталоном основывается на рассмотрении изображений как двумерных функций яркости (дискретных двумерных матриц интенсивности). При этом измеряется либо расстояние между изображениями, либо мера их близости. Как правило, для вычисления расстояний между изображениями используется формула, являющаяся суммой модулей или квадратов разностей интенсивности: Одним из методов, позволяющих значительно сократить количество вычислений, является применение Фурье преобразований и дискретных Фурье преобразований для расчёта меры совпадения двух изображений при различных смещениях их между собой. Вычисления при этом происходят одновременно для различных комбинаций сдвигов изображений относительно друг друга. Наличие большого числа библиотек, реализующих Фурье преобразований (во всевозможных вариантах быстрых версий), делает реализацию алгоритмов сравнения изображений не очень сложной задачей для программирования. Примечание:
Преобразование Фурье (ℱ) - операция, сопоставляющая одной функции вещественной переменной другую функцию, также вещественной переменной. Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие - гармонические колебания с разными частотами. Преобразование Фурье функции f вещественной переменной является интегральным и задаётся следующей формулой: Разные источники могут давать определения, отличающиеся от приведённого выше выбором коэффициента перед интегралом, а также знака «−» в показателе экспоненты. Но все свойства будут те же, хотя вид некоторых формул может измениться. Кроме того, существуют разнообразные обобщения данного понятия. Обратное преобразование в этом случае задается формулой: Как и прежде, в разных источниках определения многомерного преобразования Фурье могут отличаться выбором константы перед интегралом. Обратное преобразование: Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор: И хотя подобные свойства присущи многим линейным преобразованиям, для практического применения, для вычисления операции свёртки, согласно данному нами определению, используется формула Пусть Используемое программное обеспечение
Из предыдущего раздела о дискретизации непрерывных сигналов следует, что реальные сигналы могут быть описаны выборками как в спектральной, так и во временной области. И дискретный спектр, и дискретный сигнал полностью описывают исходный непрерывный (континуальный) сигнал. Однако чтобы найти дискретный спектр по заданному дискретному сигналу, надо проделать трудоемкие расчеты: сначала по дискретному сигналу восстановить непрерывный сигнал, затем с помощью преобразования Фурье найти непрерывный спектр, затем его дискретизировать. Аналогичную процедуру необходимо проделать для обратного преобразования. Непосредственный переход от дискретного сигнала к дискретному спектру и наоборот возможен с использованием дискретного преобразования Фурье. Рассмотрим непрерывный сигнал конечной длительности с числом степеней свободы, равным Для этого сигнала можно записать разложение в ряд Котельникова: С помощью обычного преобразования Фурье найдем спектр этого сигнала: Непосредственное вычисление интеграла в этой формуле - процедура трудоемкая. Однако это нетрудно сделать другим способом. Рассмотрим спектр который определяется выражением Применив к нему обратное преобразование Фурье, получим, что ему соответствует временная функция Очевидно, справедливо и обратное соотношение Применяя теорему о запаздывании, можно записать Подставляя (3.2) в (3.1), получим окончательное выражение для спектра Чтобы перейти к дискретному преобразованию Фурье, значения спектра в выражении (3.3) нужно вычислять не для всех значений частоты, а для дискретных (выборочных): В результате получим окончательную формулу для дискретного преобразования Фурье Свойства дискретного преобразования Фурье во многом аналогичны свойствам обычного преобразования Фурье. Отметим только одно специфическое свойство, которое можно назвать периодичностью дискретного преобразования Фурье. Рассмотрим значение определяемое формулой (3.4) для где целое число: Таким образом, дискретное преобразование Фурье является периодической функцией частоты с периодом, равным Это свойство аналогично свойству периодичности спектра дискретизированных сигналов, которое рассматривалось в гл. 2. Перейдем теперь к выводу обратного дискретного преобразования Фурье, позволяющего определять выборки сигнала по выборкам спектра. Для этого воспользуемся обычным обратным преобразованием Фурье Спектральную плотность сигнала запишем в виде ряда Котельникова и подставим в интеграл обратного преобразования Фурье Интеграл в выражении аналогичен вычисленному ранее интегралу (3.2). Пользуясь этой аналогией, запишем Подставляя (3.6) в (3.5), получим выражение для временной функции Полагая в соотношении получим формулу для определения значений дискретного сигнала т. е. приходим к обратному дискретному преобразованию Фурье где А принимает значения от 0 до Иногда для удобства записи, используя свойство периодичности дискретного преобразования Фурье, изменяют пределы суммирования в выражении (3.8) и обратное дискретное преобразование Фурье записывают в виде Для иллюстрации применим дискретное преобразование Фурье к дискретизированному треугольному импульсу (рис. описываемому пятью выборочными значениями Подставим это выражение дискретного сигнала в формулу дискретного преобразования Фурье (3.4) Для сравнения найдем спектральную плотность исходного треугольного импульса: Легко видеть, что дискретный спектр (3.11) неточно описывает спектральную плотность треугольного импульса (3.12). Значения несколько отличаются от соответствующих значений спектра треугольного импульса (рис. 3.1, б). Теперь подставим дискретные значения спектра (3.11) в выражение для обратного дискретного преобразования Фурье (3.8): Несмотря на отличие значений дискретного спектра от значений непрерывного, полученный результат полностью совпадает с формулой исходного дискретного сигнала (3.11). Рассмотренный пример показывает, что дискретное преобразование Фурье не всегда точно описывает спектр исходного непрерывного сигнала, подобно тому, как Рис. 3.1. Дискретное преобразование Фурье дискретизированного треугольного импульса дискретизированный сигнал не всегда точно описывает исходный непрерывный сигнал. Однако связь между дискретным сигналом и его дискретным преобразованием Фурье всегда носит взаимно однозначный характер и формулу прямого и обратного преобразований Фурье являются строгими при любом числе дискретных значений. Поэтому аппарат дискретных преобразований Фурье имеет самостоятельное значение и может быть применен к любым числовым последовательностям. В этом случае формулы дискретного преобразования Фурье должны быть несколько изменены, так как для абстрактной числовой последовательности значения интервала дискретизации и длительности сигнала не имеют смысла. Поэтому коэффициент перед суммой в формуле (3.4) опускают, заменяют на отсчетные значения сигнала и спектра обозначают через и формулу дискретного преобразования Фурье записывают в виде При этом обратное дискретное преобразование Фурье имеет вид Значения вычисленные по формуле (3.14), отличаются от выборочных значений спектра непрерывного колебания в раз. Для определения выборочных значений надо значения вычисленные по формуле (3.14), умножить на величину интервала дискретизации по времени : Покажем, что преобразования (3.14), (3.15) являются взаимно обратными. Для этого возьмем произвольную числовую последовательность с помощью дискретного преобразования Фурье (3.14) найдем последовательность и применим к ней обратное дискретное преобразование Фурье (3.15). Получившуюся при этом последовательность обозначим Поменяем порядок суммирования и несколько преобразуем это выражение: Внутренняя сумма выражения (3,16) равна нулю, если и равна если Следовательно, при т. е. числовые последовательности совпадают друг с другом. Таким образом, при последовательном применении к любой числовой последовательности прямого и обратного дискретного преобразования Фурье получают в результате ту же последовательность. Проиллюстрируем это положение простейшими примерами. 1. Рассмотрим простейший дискретный сигнал, состоящий из одного отсчетного значения, равного а. Подставляя эту простейшую последовательность в формулу дискретного преобразования Фурье (3.14), получим Таким образом, дискретное преобразование Фурье отдельного числового значения равно этому же значению. Другое важное применение дискретного преобразования Фурье - вычисление сигнала на выходе фильтра с заданной частотной характеристикой. Если задан входной сигнал то для него можно вычислить дискретное преобразование Фурье Если теперь умножим на частотную характеристику фильтра, то получим дискретное преобразование Фурье выходного сигнала: После этого с помощью обратного дискретного преобразования Фурье можно найти сигнал на выходе фильтра. Если входной сигнал имеет большую длительность, его обработку с помощью дискретного преобразования Фурье можно производить по частям. Для этого берут первые N отсчетов входного сигнала, вычисляют их дискретное преобразование Фурье и после умножения на частотную характеристику фильтра с помощью обратного дискретного преобразования Фурье вычисляют первые N отсчетов выходного сигнала. После этого аналогичным путем обрабатывают следующие N отсчетов входного сигнала и т. д. Для повышения точности обработки сигнала обрабатываемые серии отсчетов могут частично перекрываться. Преимуществом такого метода обработки сигналов является отсутствие каких-либо ограничений на вид частотной характеристики фильтра. Например, частотная характеристика может быть идеальной прямоугольной формы, что невозможно реализовать с помощью обычных фильтров. Обработку сигналов с помощью дискретного преобразования Фурье нельзя назвать цифровой фильтрацией в полном смысле слова. Обычные цифровые фильтры, работающие в реальном масштабе времени, производят обработку сигнала непрерывно по мере его поступления, а вычисление выходного сигнала с помощью дискретного преобразования Фурье может быть произведено лишь после того, как станет известным полностью входной сигнал или хотя бы первая серия из N его отсчетов. Поэтому при использовании дискретного преобразования Фурье выходной сигнал может быть получен только с некоторым запаздыванием по отношению к входному сигналу. Однако в ряде практических применений такое запаздывание выходного сигнала не играет существенной роли, и тогда обработка сигналов с использованием дискретного преобразования Фурье оказывается целесообразной.Комплексное представление преобразования Фурье.
Быстрое преобразование Фурье.
Двумерное преобразование Фурье.
Свертка с использованием преобразования Фурье.
Фильтрация изображений в частотной области.
d(X,Y) = SUM (X - Y)^2
Если помимо простого сравнения двух изображений требуется решить задачу обнаружения позиции фрагмента одного изображения в другом, то классический метод “начального уровня”, заключающийся в переборе всех координат и вычисления расстояния по указанной формуле, как правило, терпит неудачу практического использования из-за требуемого большого количества вычислений.Постановка задачи
Например, найти:в изображении
Корреляция как мера между изображениями
Согласно определению, корреляцией
Эта величина хорошо известна из курса математики и геометрии, посвященного линейным пространствам, где носит название скалярного произведения. Будем использовать в качестве меры между изображениями формулу:m(X,Y) = SUM (X * Y) / (SQRT (SUM X ^2) * SQRT (SUM Y ^2))
или m(X,Y) =
Данная величина получена из операции скалярного произведения векторов (рассматривая изображения как векторы в многомерном пространстве). И даже более - эта же формула представляет собой и стандартную статистическую формулу критерия для гипотезы о совпадении двух вероятностных распределений.
При вычислении корреляции между фрагментами изображений, если одно изображение меньше другого, будем делить только на значение норм у пересекающийся частей.Свёртка двух функций
Согласно определению, свёрткой двух функций F и G называется функция FхG:
Пусть G’(t) = G(-t) и F’(t) = F(-t), тогда, очевидна справедливость равенств:
Так же очевидно, что FхG’(t) равна корреляции получаемой в результате сдвига одного вектора, относительно другого на шаг t (это легко проверить явной подстановкой значений в формулу корреляции).
Многомерное преобразование Фурье
Преобразование Фурье функций, заданных на пространстве ℝ^n, определяется формулой:
Дискретное преобразование Фурье
Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) - это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.Формулы дискретных преобразований
Прямое преобразование:
Фурье-преобразования для вычисления свёртки
Одним из замечательных свойств преобразований Фурье является возможность быстрого вычисления корреляции двух функций определённых, либо на действительном аргументе (при использовании классической формулы), либо на конечном кольце (при использовании дискретных преобразований).
Где
Проверить правильность равенства довольно легко – явно подставив в формулы Фурье-преобразований и сократив получившиеся формулы Фурье-преобразования для вычисления корреляции
Тогда, как уже показано ранее, выполняется
Если используются реализации алгоритма трансформации Фурье через комплексные числа, то такие преобразования обладают ещё одним замечательным свойством:FFT(G’) = CONJUGATE (FFT(G))
Где CONJUGATE (FFT(G)) – матрица, составленная из сопряжённых элементов матрицы FFT(G)
Таким образом, получаемФурье-преобразования для решения задачи
m(X,Y) (i,j) =
получаем, что
ГдеУпрощение формул для решения поставленной задачи
При решении задачи для поиска одного образца, дополнительное нормирование образца является излишним, а также вычисление нормы у общей части может быть заменено на сумму яркостей пикселей в этой общей части или на сумму квадратов яркостей в этой общей части
При использовании формулы для оценки расстояния между изображениями при сдвиге (i,j) относительно друг другаm(X,Y) (i,j) =
получаем, что
ГдеАлгоритм поиска фрагмента в полном изображении
Примечание:
При использовании дискретного преобразования Фурье, матрица M содержит также элементы от циклического сдвига изображений между собой. Поэтому, если не требуется анализировать циклический сдвиг кадров, то поиск максимального элемента в матрице M нужно ограничить областью (0,0)-(N1-M1, N2-M2).Примеры реализации
Реализованные алгоритмы являются частью библиотеки с открытым исходным кодом FFTTools. Интернет-адрес: github.com/dprotopopov/FFTTools
///
/// Попался, который кусался
Литература
