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

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

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

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

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

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

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

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

Комплексное ДПФ

До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим теперь ДПФ на случай комплексных сигналов. Пусть x[n], n=0,…,N-1 - исходный комплексный сигнал, состоящий из N комплексных чисел. Обозначим X[k], k=0,…N-1 - его комплексный спектр, также состоящий из N комплексных чисел. Тогда справедливы следующие формулы прямого и обратного преобразований Фурье:

Если по этим формулам разложить в спектр действительный сигнал, то первые N/2+1 комплексных коэффициентов спектра будут совпадать со спектром "обычного" действительного ДПФ, представленным в "комплексном" виде, а остальные коэффициенты будут их симметричным отражением относительно половины частоты дискретизации. Для косинусных коэффициентов отражение четное, а для синусных - нечетное.

Двумерное ДПФ

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

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

Здесь N 1 xN 2 - размер исходного сигнала, он же - размер спектра. k 1 и k 2 - это номера базисных функций (номера коэффициентов двумерного ДПФ, при которых эти функции находятся). Поскольку размер спектра равен размеру исходного сигнала, то k 1 = 0,…,N 1 -1; k 2 = 0,…,N 2 -1.

n 1 и n 2 - переменные-аргументы базисных функций. Поскольку область определения базисных функций совпадает с областью определения сигнала, то n 1 = 0,…,N 1 -1; n 2 = 0,…,N 2 -1.

Двумерное ДПФ (в комплексной форме) определяется следующими формулами (здесь x - исходный сигнал, а X - его спектр):

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

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

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

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

Даётся программный код для прямого и обратного преобразования Фурье. Рассматривается быстрое преобразование Фурье.

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

Для расчёта преобразования Фурье обычно используется ускоренная процедура расчёта - т.н. быстрое преобразование Фурье (БПФ). Это позволяет в значительной мере сократить процессорное время на достаточно сложные и ресурсоёмкие математические расчёты.

1 Комплексные числа

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

Код класса для описания комплексных чисел (разворачивается) """

""" Комплексное число. """

Public Class ComplexNumber """

""" Действительная часть комплексного числа. """

Public Real As Double = 0 """

""" Мнимая часть комплексного числа. """

Public Imaginary As Double = 0 Public Sub New() Real = 0 Imaginary = 0 End Sub """

""" Создаёт комплексное число. """

""" Действительная часть комплексного числа. """ Мнимая часть комплексного числа. Public Sub New(ByVal r As Double, Optional ByVal im As Double = 0) Real = r Imaginary = im End Sub Private usCult As New Globalization.CultureInfo("en-US") "используем культуру "en-US" чтобы целая и дробная части разделялись точкой, а не запятой """

""" Возвращает строку, состоящую из действительной и мнимой части, разделённых символом табуляции. """

Public Overrides Function ToString() As String Return (Real.ToString(usCult) & ControlChars.Tab & Imaginary.ToString(usCult)) End Function End Class

2 Прямое дискретное быстрое преобразование Фурье

На вход функции передаётся массив комплексных чисел. Действительная часть которого представляет произвольный дискретный сигнал, с отсчётами через равные промежутки времени. Мнимая часть содержит нули. Число отсчётов в сигнале должно равняться степени двойки. Если ваш сигнал короче, то дополните его нулями до числа, кратного степени 2: 256, 512, 1024 и т.д. Чем длиннее сигнал, тем у рассчитанного спектра будет выше разрешение по частоте.

Код для расчёта прямого быстрого преобразования Фурье на VB.NET (разворачивается) """

""" Рассчитывает спектр сигнала методом быстрого преобразования Фурье. Использовать только (N/2+1) возвращаемых значений (до половины частоты дискретизации). """

""" Сигнал, содержащий количество отсчётов, кратное степени двойки, и состоящий из действительной и мнимой частей. Все мнимые части сигнала заполнены нулями. """ Возвращает массив комплексных чисел спектра. """ Значимы только первые N/2+1, остальные - симметричная часть, соответствующая отрицательным частотам. """ Первое значение спектра - это постоянная составляющая, последнее - соответствует половине частоты дискретизации (частота Найквиста). """ Значения выше половины частоты дискретизации - не использовать. """ Public Shared Function FFT(ByVal signal As ComplexNumber()) As ComplexNumber() Dim order As Integer = signal.Length "порядок ДПФ CheckFftOrder(order) "Проверяем, что порядок равен степени двойки Dim spectrumLen As Integer = order \ 2 Dim j As Integer = spectrumLen "Бит-реверсная сортировка: For i As Integer = 1 To order - 2 If (i < j) Then Dim tmpRe As Double = signal(j).Real Dim tmpIm As Double = signal(j).Imaginary signal(j).Real = signal(i).Real signal(j).Imaginary = signal(i).Imaginary signal(i).Real = tmpRe signal(i).Imaginary = tmpIm End If Dim k As Integer = spectrumLen Do Until (k > j) j -= k k \= 2 Loop j += k Next "Цикл по уровням разложения: For level As Integer = 1 To CInt(Math.Log(order) / Math.Log(2)) Dim lvl As Integer = CInt(2 ^ level) Dim lvl2 As Integer = lvl \ 2 Dim tmp As Double = Math.PI / lvl2 Dim sr As Double = Math.Cos(tmp) Dim si As Double = -Math.Sin(tmp) Dim tr As Double = 0 Dim ur As Double = 1 Dim ui As Double = 0 For jj As Integer = 1 To lvl2 "Цикл по спектрам внутри уровня For i As Integer = (jj - 1) To (order - 1) Step lvl "Цикл по отдельным "бабочкам" Dim ip As Integer = i + lvl2 tr = signal(ip).Real * ur - signal(ip).Imaginary * ui "Операция "бабочка" Dim ti As Double = signal(ip).Real * ui + signal(ip).Imaginary * ur signal(ip).Real = signal(i).Real - tr signal(ip).Imaginary = signal(i).Imaginary - ti signal(i).Real = signal(i).Real + tr signal(i).Imaginary = signal(i).Imaginary + ti Next tr = ur ur = tr * sr - ui * si ui = tr * si + ui * sr Next Next "Заполняем массив комплексных чисел, обработанных БПФ: Dim spectrum(order - 1) As ComplexNumber For i As Integer = 0 To order - 1 With signal(i) spectrum(i) = New ComplexNumber(.Real, .Imaginary) End With Next Return spectrum End Function

3 Обратное дискретное быстрое преобразование Фурье

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

Код для расчёта обратного быстрого преобразования Фурье на VB.NET (разворачивается) """

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

""" Спектр сигнала, содержащий количество отсчётов, кратное степени двойки, и состоящий из действительной и мнимой частей. Public Shared Function InverseFFT(ByVal spectrum As ComplexNumber()) As ComplexNumber() Dim order As Integer = spectrum.Length "Порядок обратного ДПФ. CheckFftOrder(order) "Изменение арифметического знака элементов мнимой части: For i As Integer = 0 To spectrum.Length - 1 spectrum(i).Imaginary = -spectrum(i).Imaginary Next "Вычисление прямого БПФ: Dim directFFT As ComplexNumber() = FFT(spectrum) "Деление на order во временной области со сменой арифметического знака мнимой части: Dim signal(directFFT.Length - 1) As ComplexNumber For i As Integer = 0 To directFFT.Length - 1 Dim ReX As Double = directFFT(i).Real / order Dim ImX As Double = -directFFT(i).Imaginary / order signal(i) = New ComplexNumber(ReX, ImX) Next Return signal End Function

Ну и конечно же, опишем использовавшийся метод, который проверяет число элементов переданного массива:

"""

""" Проверяет, является ли порядок БПФ степенью двойки, и если нет - вызывает исключение. """

""" Порядок БПФ. Private Shared Sub CheckFftOrder(ByVal order As Integer) Dim chk As Double = Math.Abs(Math.Floor(Math.Log(order, 2)) - Math.Log(order, 2)) If (chk > 0.0001) Then Throw New ArgumentException(String.Format("Длина массива ({0}) не кратна степени двойки.", order)) End If End Sub

4 Проверка прямого и обратного преобразования Фурье

Теперь давайте проверим, что наши функции работают. Для этого пропустим произвольный сигнал через механизм прямого преобразования Фурье, а затем «соберём» его обратно с помощью обратного преобразования Фурье. Восстановленный сигнал должен практически совпадать с исходным. Ошибки округления, возникающие при работе с числами в компьютере, имеют место быть, поэтому сигналы не будут идентичны полностью, но их отклонение друг от друга должно быть пренебрежимо малым.

Для примера в качестве исходного сигнала возьмём функцию синуса и сформируем данные длиной 128 отсчётов вот таким образом:

Dim cn(127) As ComplexNumber For i As Integer = 0 To cn.Length - 1 cn(i) = New ComplexNumber(Math.Sin(i * 3 * Math.PI / 180)) Next

Получим вот такой сигнал:

Здесь по оси X - номера отсчётов во временной области, по оси Y - амплитуда. Обратим внимание, что сигнал состоит только из действительных частей, а мнимая часть на всём отрезке равна "0".

Теперь передадим этот сигнал на вход функции FFT(). По полученным в ходе прямого преобразования Фурье массивам комплексных чисел построим два графика - действительной (Re) и мнимой (Im) частей спектра:

Здесь по оси X - отсчёты в частотной области, по оси Y - амплитуда. Чтобы получить реальные значения частоты, необходимо рассчитать их, учитывая, что "0" оси Y соответствует нулевой частоте, максимум оси Y соответствует частоте дискретизации.

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

Как видно, восстановленный сигнал полностью повторяет исходный.

Пусть f (x 1 , x 2) – функция двух переменных. По аналогии с одномерным преобразованием Фурье можно ввести двумерное преобразование Фурье:

Функция при фиксированных значениях ω 1 , ω 2 описывает плоскую волну в плоскости x 1 , x 2 (рисунок 19.1).

Величины ω 1 , ω 2 имеют смысл пространственных частот и размерность мм −1 , а функция F(ω 1 , ω 2) определяет спектр пространственных частот. Сферическая линза способна вычислять спектр оптического сигнала (рисунок 19.2). На рисунке 19.2 введены обозначения: φ - фокусное расстояние,

Рисунок 19.1 – К определению пространственных частот

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

Рисунок 19.2 – Вычисление спектра оптического сигнала с использованием
сферической линзы

Факторизация . Если двумерный сигнал факторизуется,

то факторизуется и его спектр:

Радиальная симметрия . Если двумерный сигнал радиально-симметричен, то есть

Где – функция Бесселя нулевого порядка. Формулу, определяющую связь между радиально-симметричным двумерным сигналом и его пространственным спектром называют преобразованием Ганкеля.

ЛЕКЦИЯ 20. Дискретное преобразование Фурье. Низкочастотный фильтр

Прямое двумерное дискретное преобразование Фурье (ДПФ) преобразует изображение, заданное в пространственной координатной системе (x, y ), в двумерное дискретное преобразование изображения, заданное в частотной координатной системе (u,v ):

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

Видно, что ДПФ является комплексным преобразованием. Модуль этого преобразования представляет амплитуду спектра изображения и вычисляется как корень квадратный из суммы квадратов действительной и мнимой частей ДПФ. Фаза (угол сдвига фазы) определяется как арктангенс отношения мнимой части ДПФ к действительной. Энергетический спектр равен квадрату амплитуды спектра, или сумме квадратов мнимой и действительной частей спектра.

Теорема о свертке

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

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

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

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

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

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

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

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

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

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

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

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

		2π k (n + ϕ k )
	x = ∑ C k cos		(ряд Фурье)
	k = 0

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

	2 π kn		2 π kn
x = ∑ A k cos		+ ∑ B k sin		(ряд Фурье)
k = 0		k = 0

Рис. 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 .

			2 π kn		2 π kn			от аргумента n является ор-
	Система функций					K = 0,...,

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

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

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

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

N − 1

2 π ki , приk = 1,...,

A k=

∑ x cos

−1

N i = 0

N − 1

A k=

∑ x cos2 π ki , приk = 0,

N i = 0

N − 1

2 π ki

NB 0 иB N 2 всегда равны нулю (т.к. соответствующие им «базисные» сигналы тождественно равны нулю в дискретных точках), и их можно отбросить при вычислении обратного и прямого преобразований Фурье. Итак, мы выяснили, что спектральное представление сигнала полностью эквивалентно самому сигналу. Между ними можно перемещаться, используя прямое и обратное преобразования Фурье. Алгоритм вычисления этих преобразований содержится в приведенных формулах. Вычисление преобразований Фурье требует очень большого числа умножений (около N 2 ) и вычислений синусов. Существует способ выполнить эти преобразования значительно быстрее: примерно заN log2 N операций умножения. Этот способ называется быстрым преобразованием Фурье(БПФ, FFT, fast Fourier transform). Он основан на том, что среди множителей (синусов) есть много повторяющихся значений (в силу периодичности синуса). Алгоритм БПФ группирует слагаемые с одинаковыми множителями, значительно сокращая число умножений. В результате быстродействие БПФ может в сотни раз превосходить быстродействие стандартного алгоритма (в зависимости от N). При этом следует подчеркнуть, что алгоритм БПФ является точным. Он даже точнее стандартного, т.к. сокращая число операций, он приводит к меньшим ошибкам округления. Однако у большинства алгоритмов БПФ есть особенность: они способны работать лишь тогда, когда длина анализируемого сигнала N является степенью двойки. Обычно это не представляет большой проблемы, так как анализируемый сигнал всегда можно дополнить нулями до необходимого размера. Число N называется размеромили длиной БПФ(FFT size). Комплексное ДПФ До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим теперь ДПФ на случай комплексных сигналов. Пусть x , n =0,…,N -1 – исходный комплексный сигнал, состоящий изN комплексных чисел. ОбозначимX , k =0,…N -1 – его комплексный спектр, также состоящий изN комплексных чисел. Тогда справедливы следующие формулы прямого и обратного преобразо- ваний Фурье (здесь j = − 1): N − 1 X [ k] = ∑ x[ n] e− jnk (2 π N ) n= 0 N − 1 ∑ X [ k ] e jnk(2 π N) N k = 0 Если по этим формулам разложить в спектр действительный сигнал, то первые N /2+1 комплексных коэффициентов спектра будут совпадать со спектром «обычного» действительного ДПФ, представленным в «комплексном» виде, а остальные коэффициенты будут их симметричным отражением относительно

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

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

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 соответствующими пиками.

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