42011

Вычислительные машины, системы и сети

Лабораторная работа

Информатика, кибернетика и программирование

Цель работы Изучение преобразования Фурье и его основных свойств а также методики получения быстрого преобразования Фурье БПФ. Теоретические сведения Ортогональные функции Для лучшего понимания вопроса о рядах Фурье дадим определение ортогональным функциям.

Русский

2013-10-26

1.32 MB

25 чел.

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет

информатики и радиоэлектроники»

Кафедра электронных вычислительных машин

М.М. Лукашевич, Р.Х. Садыхов

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

по дисциплине «Цифровая обработка сигналов и изображений»

для студентов специальности I-40 02 01

«Вычислительные машины, системы и сети»

В 2-х частях

Часть 1

Минск 2011


      Лабораторный практикум содержит перечень лабораторных работ по дисциплине «Цифровая обработка сигналов и изображений», читаемой студентам специальности «Вычислительные машины, системы и сети». В 1-й части рассматриваются вопросы обработки сигналов и изображений с помощью дискретных преобразований. Уделяется внимание оптимизации вычислений путем создания быстрых алгоритмов расчета и обучения.


Содержание

ДИСКРЕТНЫЕ ПРЕОБРАЗОВАНИЯ

  1.  Лабораторная работа №1. Преобразование Фурье……………………
  2.  Лабораторная работа №2. Операции корреляции и свертки…………
  3.  Лабораторная работа №3. Преобразование Уолша…………………...
  4.  Лабораторная работа №4. Вейвлет – преобразование………………..


ДИСКРЕНЫЕ ПРЕОБРАЗОВАНИЯ

Лабораторная работа №1

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

1. Цель работы

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

2. Теоретические сведения

Ортогональные функции

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

              (1.1)

При множество {Un(t)} называется ортонормированным.

Ряд Фурье

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

Впервые в 1807 году французский математик и физик Жан Батист Жозеф Фурье показал, что любую произвольную функцию можно представить в виде бесконечной суммы синусных и косинусных членов:

,              (1.2)

где (рад/с) – основная угловая частота, которая связана с периодом T функции соотношением . Частоты называют гармониками, так как они кратны основной частоте . В данном случае речь идет о системе ортогональных функций вида .

Коэффициенты {a0, an, bn} из формулы (1.2) можно вычислить с учетом ортогональности множества функций {cos n0t, sin n0t} на периоде T:

             (1.3)

              (1.4)

              (1.5)

С учетом этих соотношений:

                 (1.6)

               (1.7)

.                (1.8)

Раздел математики, устанавливающий соотношение между функцией и коэффициентами и , называется гармоническим анализом, а представление (1.2) – рядом Фурье.

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

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

Семейство преобразований Фурье

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

Семейство преобразований Фурье (преобразование Фурье, ряды Фурье, дискретные ряды Фурье и дискретное преобразование Фурье) представлено на рис. 1.1 – 1.4.

Рис. 1.1. Преобразование Фурье: сигнал непрерывный и апериодический

Рис. 1.2. Ряды Фурье: сигнал непрерывный и периодический

Рис. 1.3. Дискретные ряды Фурье: сигнал дискретный и апериодический

Рис. 1.4. Дискретное преобразование Фурье:

(дискретные ряды Фурье) сигнал дискретный и периодический

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

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

Основная идея ДПФ ни чем не отличается от ПФ (см. рис. 1.5).

Рис. 1.5. Основная идея ДПФ

Для получения представления x(t) (1.2) рядом Фурье в комплексной форме необходимо использовать соотношения в виде формулы Эйлера:

;

; .              (1.9)

Тогда

          (1.10)

Введем коэффициент

.

Тогда

или ;

.              (1.11)

Следовательно,

;

;

.               (1.12)

Таким образом, если {X(m)} означает последовательность X(m) конечных действительных или комплексных чисел, где , то дискретное преобразование Фурье этой последовательности определяется как

, где ,  , ,        (1.13)

.              (1.14)

Выражения (1.13), (1.14) составляют пару преобразований Фурье.

Функции W km являются N-периодическими, т.е. W km=W (k+N)m=W k(m+N).

Следовательно, последовательности {Cx(k)}, {X(m)} также являются N-периодическими, т.е.

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

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

б) теорема комплексной сопряженности: если {X(m)}={X(0), X(1),… ,X(N-1)} – такая последовательность действительных чисел, что N/2 – целое число и X(m)Cx(k), то

.            (1.15)

Из (1.13) следует, что где W=e-i2/N.

Тогда, подставляя вместо k (N/2+l), будем иметь

 

т.к. WNm=-1.

в) теорема сдвига: если Z(m)Cz(k)и Z(m)=X(m+h), , то

Cz(k)=W -khCx(k).               (1.16)

Доказательство:

Z(m)Cz(k), т.е. , .

С учетом подстановки Z(m)=X(m+h), будем иметь .

Осуществляя замену переменных m+h=r, указанное соотношение будет иметь вид .

Так как

,

, когда p и q удовлетворяют условию

|p-q|=N-1, то Cz(k)=W -khCx(k).

Аналогично при Z(m)=X(m-h) , Cz(k)=W khCx(k).

Можно выделить следующие области применения ДПФ:

  1.  цифровой спектральный анализ
  2.  анализаторы спектра
  3.  обработка речи
  4.  обработка изображений
  5.  распознавание образов
  6.  проектирование фильтров
  7.  вычисление импульсной характеристики по частотной
  8.  вычисление частотной характеристики по импульсной
  9.  быстрое преобразование Фурье (БПФ) – простой алгоритм для эффективного вычисления ДПФ.

ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ (ДПФ)

  1.  Периодический сигнал может быть разложен на сумму выбранных должным образом косинусоидальных и синусоидальных функций (Жан Батист Жозеф Фурье, 1807).
  2.  ДПФ работает с конечным числом (N) оцифрованных по времени отсчетов X(m). Когда эти группы отсчетов повторяются, они становятся периодическими с точки зрения преобразования.
  3.  Комплексный спектральный выход ДПФ C(k) является результатом свертки входных отсчетов с базисными функциями синуса и косинуса.

Быстрое преобразование Фурье (БПФ)

Быстрое преобразование Фурье (FFT) является не более, чем алгоритмом для ускоренного вычисления ДПФ путем сокращения требуемого числа операций умножения и сложения. Данное преобразование было предложено в 1960-ых годах. Алгоритм быстрого преобразования Фурье значительно сокращает количество арифметических операций и объем памяти, необходимой для вычисления ДПФ. ДПФ может быть сильно упрощено, если использовать свойства симметрии и периодичности коэффициентов поворота.

При вычислении N-точечного ДПФ требуется вычислений с комплексными числами, а при реализации N-точечного БПФ вычислений с комплексными числами. Вычислительная эффективность БПФ по сравнению с ДПФ становится весьма существенной, когда количество точек БПФ увеличивается до нескольких тысяч (табл. 1.1).

Таблица 1.1

Эффективность БПФ

N

Умножений при ДПФ

Умножений при БПФ

Эффективность БПФ

256

65 536

1 024

64 : 1

512

262 144

2 304

114 : 1

1 024

1 048 576

5 120

205 : 1

2 048

4 194 304

11 264

372 : 1

4 096

16 777 216

24 576

683 : 1

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

Мы будем предполагать далее, что N=2n. При этом общность не теряется, так как N выбирается достаточно большим для того, чтобы удовлетворять теореме дискретизации Котельникова, т.е.

N  2BT,

где B – полоса частот сигнала x(t); T – его длительность.

 Теорема Котельникова-Найквиста-Шеннона: если сигнал таков, что его спектр ограничен частотой F, по после дискретизации сигнала с частотой не менее 2F можно восстановить непрерывный сигнал по полученному цифровому сигналу абсолютно точно. Для этого нужно проинтерполировать цифровой сигнал «между отсчетами» специального вида функциями.

Рассмотрим случай вещественно-значной последовательности {X(m)} при N=8. Из свойства комплексной сопряженности ДПФ следует, что

; .       

Тогда

; ;      

W=e-i2/8=e-i/4;          

.          (1.17)

Используя свойство N-периодичности экспонент, для N=8 матрица будет иметь вид

 .

Из свойства симметрии экспоненциальных функций следует, что

 Wk+N/2=-Wk, где .

То есть W4=-W0;

 W5=-W1;

 W6=-W2;

 W7=-W3.

Тогда матрица F будет иметь вид

 .

Используя двоичную инверсию (перестановку) строк,

(0,1,2,3,4,5,6,7) (0,4,2,6,1,5,3,7) будем иметь

 =

= .               (1.18)

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

                (1.19)

Подставляя выражения для A11 и B11 в (1.18) получим

;       

;       

;       

.             (1.20)

Наконец, на последнем шаге получим

        (1.21)

 

Описанный алгоритм удобно представить графически (рис. 1.6).

Рис. 1.6. Граф-схема быстрой процедуры вычисления коэффициентов преобразования Фурье

Для определения степеней W на одном шаге необходимо выразить последовательность l=0, 1, 2, …, N/2-1 в виде (n-1) – разрядных двоичных последовательностей. В результате для N=16, к примеру, получим множество

S1=(000,001,010,011,100,101,110,111).

Для получения S2 необходимо выполнить двоичную инверсию каждой (n-1)-разрядной последовательности множества S1, т.е.

S2=(000,100,010,110,001,101,011,111),

и записать двоичную последовательность в виде десятичных чисел

S3=(0,4,2,6,1,5,3,7),

и таким образом имеем W0, W4, W2, W6, W1, W5, W3, W7. (табл. 1.2).

Итерация r для БПФ состоит из 2r-1 групп, где (N=2n). Для N=16, .


Таблица 1
.2

Значения степени W

Номер итерации

Степени W (N=16)

1

W0 W0 W0 W0   W0 W0 W0 W0   W0 W0 W0 W0   W0 W0 W0 W0

2

W0 W0 W0 W0   W0 W0 W0 W0   W4 W4 W4 W4   W4 W4 W4 W4

3

W0 W0 W0 W0   W4 W4 W4 W4   W2 W2 W2 W2   W6 W6 W6 W6

4

W0 W0 W4 W4   W2 W2 W6 W6   W1 W1 W5 W5   W3 W3 W7 W7

 

Первый элемент первой строки таблицы равен нулю. Последующие первые элементы каждой из строк  определяются как ns=N/2s , где , N=2n. Каждая k строка таблицы получается прибавлением элемента nk-1 к каждому элементу предыдущих строк. Тогда таблица будет иметь вид

0

n1

n2 (n1+n2)

n3 (n1+n3) (n2+n3) (n1+n2+n3)

n4 (n1+n4) (n2+n4) (n1+n2+n4)   …

.

.

nk    …

Требуемая последовательность Ln, соответствующая двоичной инверсии, определяется как Ln=(0, n1, n2, (n1+n2), n3, (n1+n3), …, nk, …). В качестве примера рассмотрим случай для N=16. Тогда n1=8, n2=4, n3=2, n4=1, т.е. таблица будет иметь вид

0

8

4 12

2 10 6 14

1 9 5 13 3 11 7 15

Ln=(0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15).

Для обработки исходных данных (которые предполагаются комплексными) с помощью алгоритма БПФ требуется 2N ячеек оперативной памяти. Поэтому выходной массив может храниться в тех же ячейках памяти, что и исходный массив. Процедура перестановки данных может потребовать дополнительно 2N ячеек памяти. Таким образом, для алгоритма БПФ необходимо примерно 4N ячеек. В противоположность этому прямой метод требует приблизительно 2N2  ячеек памяти, т.к. необходимо запомнить N2 значений степеней W.

В общем виде матрицу преобразования Фурье в факторизованной форме можно представить как

.               (1.22)

Для N=8  , где ; I4 – единичная матрица размерностью 44; D1  диагональная матрица с элементами W0;

.      

D2 -диагональная матрица с элементами W0, W2:

;

; .

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

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

Алгоритм БПФ (FFT) с прореживанием по времени (decimation-in-time, DIT)

Рис. 1.7. Граф-схема алгоритма БПФ с прореживанием по времени

Рис. 1.8. Операция «бабочка» в алгоритме БПФ с прореживанием по времени

Алгоритм быстрого преобразования Фурье с прореживанием по времени можно выразить следующим образом.

АЛГОРИТМ БПФ(a, N, dir)

{

  1.  Если длина вектора равна 1, вернуть a.
  2.  Разбить вектор a на четную часть aчет = (a0,a2,…,aN-2)

и нечетную aнечет = (a1,a3,…,aN-1).

  1.  Рекурсивно вызвать БПФ на каждой из частей

bчет = БПФ(aчет)

bнечет = БПФ(aнечет)

  1.  Объединение результатов.
  2.  (инициализация) Присвоить  значение главного комплексного корня N-й степени из единицы

  1.  (инициализация) Присвоить
  2.  В цикле вычислить левую и правую часть одновременно:

for( j=0; j < N/2; j++)

{

 

 

 

}

  1.  Вернуть вектор y.

}

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

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

Рис. 1.9. Дерево рекурсий для 8 элементов

Алгоритм БПФ (FFT) с прореживанием по частоте (decimation-in-frequency, DIF)

При реализации алгоритма БПФ с прореживанием по частоте первоначально выполняется операция бабочка, а затем проводится разбиение вектора на две части («верхнюю» и «нижнюю»).

Рис. 1.10. Граф-схема алгоритма БПФ с прореживанием по частоте

Рис. 1.11. Операция «бабочка» в алгоритме БПФ с прореживанием по частоте

АЛГОРИТМ БПФ(a, N, dir)

{

  1.  Если длина вектора равна 1, вернуть a.
  2.  
  3.  Присвоить  значение главного комплексного корня N-й степени из единицы
  4.  Присвоить

for( j=0; j < N/2; j++)

{

 

 

 

}

  1.  Рекурсивно вызвать БПФ на каждой из частей

y = БПФ(b)

y = БПФ(c)

  1.  Объединение результатов.

  1.  Вернуть вектор y.

}


Преобразование вещественных и мнимых компонент в амплитуду и фазу

3. Задание

1. Ознакомьтесь с теоретической частью.

2. Для заданного сигнала реализовать ДПФ и алгоритм быстрого преобразования Фурье (БПФ) (прямое и обратное преобразования). Результат работы программы – амплитудный и фазовый спектр сигнала.

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

4. Оформить отчет.

Содержание отчета:

  1.  исходные данные;
  2.  краткое описание алгоритма работы программы;
  3.  график заданной функции, график по результатам прямого преобразования, график по результатам обратного преобразования;
  4.  анализ вычислительной сложности ДПФ и БПФ, пояснение полученных результатов;
  5.  выводы.

Таблица 3.1

Варианты задания

№ варианта

Сигнал

Алгоритм БПФ

N

1

y=cos(3x)+sin(2x)

БПФ с прореживанием по времени

8

2

y=sin(3x)+cos(x)

БПФ с прореживанием по частоте

16

3

y=cos(2x)+sin(5x)

БПФ с прореживанием по времени

32

4

y=sin(2x)+cos(7x)

БПФ с прореживанием по частоте

64

5

y=cos(x)+sin(x)

БПФ с прореживанием по времени

8

6

y=sin(x)+cos(4x)

БПФ с прореживанием по частоте

16

7

y=cos(5x)+sin(6x)

БПФ с прореживанием по времени

32

8

y=sin(5x)+cos(x)

БПФ с прореживанием по частоте

64

4. Контрольные вопросы

1. Для чего используются ортогональные преобразования?

2. Дать определение ортогональным и ортонормальным функциям.

3. Доказать, что Фурье – базис является ортогональным.

4. Дать определение преобразования Фурье.

5. Каковы основные свойства дискретного преобразования Фурье?

6. Каким образом осуществляется быстрое преобразование Фурье?

7. В чем заключается преимущество быстрого преобразования Фурье?


Лабораторная работа №2

Операции свертки и корреляции

1. Цель работы

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

2. Теоретические сведения

Свертка – это математический способ комбинирования двух сигналов для формирования третьего сигнала. Это один из самых важных методов ЦОС. Пользуясь стратегией импульсного разложения, системы описываются сигналом, называемым импульсной характеристикой. Свертка важна, так как она связывает три сигнала: входной сигнал, выходной сигнал и импульсную характеристику.

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

Корреляция, так же, как свертка, использует два сигнала для получения третьего. Этот третий сигнал называется корреляционным сигналом двух входных сигналов.

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

Если {X(m)} и {Y(m)} – последовательности действительных чисел, для которых X(m)Cx(k), Y(m)Cy(k), и свертка этих последовательностей определяется как

,  ,            (2.1)

то

Cz(k)=Cx(k)Cy(k).          

Доказательство

Вычисляя Z(m), получим

.                (2.2)

Подставляя в (2.2) соотношение свертки (2.1), получим

.

Согласно теореме сдвига, имеем

.       

Таким образом,

.     

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

Теорема корреляции

Если X(m)Cx(k) и Y(m)Cy(k), а их функция корреляции определяется соотношением

, где ,             (2.3)

то ,

где - комплексное сопряженное

Доказательство

По определению имеем

.                (2.4)

Подставляя (2.3) в (2.4) и меняя порядок суммирования, получаем

Применяя теорему сдвига, будем иметь

.

Так как , то .

Таким образом, .

Если последовательности {X(m)} и {Y(m)} идентичны друг другу, то

, .

Обратное ДПФ  последовательности есть .

Тогда

, т.е. справедлива теорема Парсеваля.


Матричное представление корреляции и свертки

Если {X(m)} и {Y(m)}  две N-периодические последовательности действительных чисел, то операции корреляции и свертки определяются соответственно как

       

Если N=4, то

При N=4 для свертки будем иметь

Так как   при ,

  при , то

.

В общем виде корреляцию двух последовательностей можно записать как

.

В свою очередь, соотношение свертки можно записать в общем виде как

 

.

Если последовательности {X(m)} и {Y(m)} аналогичны друг другу, то

, где .

Это соотношение определяет автокорреляцию последовательности {X(m)}.

С использованием БПФ схема вычислений корреляции будет иметь вид рис.2.1.

Рис. 2.1. Схема вычисления корреляции

В свою очередь, схему вычисления свертки можно представить как показано на рис.2.2.

Рис. 2.2. Схема вычисления свертки


3. Задание

1. Ознакомьтесь с теоретической частью.

2. Для заданных сигналов реализовать:

  1.  операцию свертки в соответствии с формулой 2.1 и операцию корреляции – формула 2.2;
  2.  операцию свертки на основе БПФ (рисунок 2.1) и операцию корреляции на основе БПФ (рисунок 2.2).

Вывести исходные сигналы, результаты свертки и корреляции

3. Сравните вычислительную сложность вычисления свертки и корреляции предложенными алгоритмами (количество операций сложения и умножения).

4. Напишите отчет.

Содержание отчета:

  1.  исходные данные;
  2.  краткое описание алгоритма работы программы;
  3.  графики заданных функций, графики результатов свертки и корреляции;
  4.  анализ и пояснение полученных результатов;
  5.  выводы.

Таблица 2.1

Варианты задания

№ варианта

Заданная функция

N для БПФ

1

y=cos(3x); z=sin(2x)

8

2

y=sin(3x); z=cos(x)

16

3

y=cos(2x); z=sin(5x)

8

4

y=sin(2x); z=cos(7x)

16

5

y=cos(x); z=sin(x)

8

6

y=sin(x); z=cos(4x)

16

7

y=cos(5x); z=sin(6x)

8

8

y=sin(5x); z=cos(x

16

4. Контрольные вопросы

1. Для чего используются понятия “корреляция” и “свертка” в такой области, как цифровая обработка сигналов и изображений?

2. Привести описание операций “свертка” и “корреляция”.

3. Каким образом связаны понятия “свертка”, “корреляция” и БПФ?

4. Привести теорему свертки, теорему корреляции.


Лабораторная работа №3

Преобразование Уолша

1. Цель работы

Изучение преобразования Уолша и его основных свойств, а также методики получения быстрого преобразования Уолша (БПУ).

2. Теоретические сведения

Особый класс систем ортогональных функций составляют системы кусочно-постоянных функций, таких как функции Уолша, Адамара и Хаара. Эти системы имеют большое практическое значение, особенно для цифровых систем, поскольку они характеризуются высокоэффективными алгоритмами быстрых преобразований.

В 1923 году американский ученый Уолш получил полную систему ортонормированных функций, которая дополняет систему функций Радемахера. Множество функций Уолша обычно разделяется на три группы, отличающиеся порядком расположения в системе.

Общеприняты следующие упорядочения (способы определения функций Уолша):

  1.  упорядочение по частоте (по Уолшу с помощью функций Радемахера);
  2.  упорядочение по Пэли (диадическое);
  3.  упорядочение по Адамару, где под частотой функции понимается число пересечений нулевого уровня в единицу времени.

Рассмотрим способ, основанный на взаимосвязи функций Уолша с функциями Радемахера и способ, основанный на матрицах Адамара.

Функции Радемахера получаются из синусоидальных функций с помощью соотношения

 ,               (3.1)

где аргумент t – безразмерное время, т.е. время, нормированное к произвольному интервалу , а целое положительное число k – порядок функции. Символом sign (сигнум-функция) обозначается функция:

               (3.2)

Функции Радемахера принимают одно из двух значений и имеют вид меандра.

Функции Радемахера ортонормированны с единичной весовой функцией на интервале , т.к. для любых двух функций , имеют место соотношения:

              (3.3)

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

Рис. 3.1 Функции Радемахера для N=8

Обозначив для краткости r(m,t)=rm(t), для N=8 будем иметь:

Если =  ++++----

=  ++--++--

=  +-+-+-+-,

где “+” соответствует +1, а “–” соответствует –1.

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

Рис. 3.2. Первые восемь функций Уолша

В свою очередь функции Уолша можно представить следующим образом:

wal(0,t)=  ++++++++

wal(1,t)=r1= ++++----

wal(2,t)=r1r2= ++----++

wal(3,t)=r2= ++--++--

wal(4,t)=r2r3= +--++--+

wal(5,t)=r1r2r3= +--+-++-

wal(6,t)=r1r3= +-+--+-+

wal(7,t)=r3= +-+-+-+-

Сопоставление этих функций с функциями Радемахера позволяет составить очевидные соотношения, согласно которым каждая функция Уолша wal(n,t) с номером n , входящая в систему из функций, является произведением степеней первых n функций Радемахера.

Принцип нахождения показателей этих степеней определяется двоичным представлением номера функции n. Примем следующие обозначения для разрядов, составляющих двоичное представление числа n: - первый разряд, - второй разряд, и так далее до , то есть r-го разряда двоичного представления натурального числа n. При такой нумерации оказывается старшим разрядом числа n, а - младшим. может принимать одно из двух значений – нуль или единица. Будем считать, что по определению. Используя символ для обозначения операции поразрядного сложения по модулю 2, способ построения функций Уолша можно выразить аналитически для любого в виде следующего соотношения:

             (3.4)

Поясним применение данной формулы на примере шестой функции Уолша (n=6), входящей в систему размером . Произведение состоит из трех множителей вида:

при k=1 ,

при k=2 ,

при k=3 .

На основе двоичного представления числа n=6 не сложно установить, что , , .

Таким образом, , , и по формуле:

.

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

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

Пусть gn-1gn-2g2g1g0 – кодовое слово в n-разрядном двоичном коде Грея, соответствующее двоичному числу bn-1bn-2b2b1b0. Тогда gi может быть получена как

 gi=bi  bi+1, 0  i  n-2;

 gn-1=bn-1,

где  означает сложение по модулю два, которое определяется как

 0  0=0

1  0=1

0  1=1

1  1=0

Например, код Грея, соответствующий двоичному числу 101101, может быть образован как на рис. 3.3. Трехразрядный код Грэя показан в табл. 3.1.

Рис. 3.3. Преобразование двоичного кода в код Грея

Таблица 3.1

Трехразрядный код Грэя

Десятичное число

Код Грея

Двоичный код

g2

g1

g0

b2

b1

b0

0

0

0

0

0

0

0

1

0

0

1

0

0

1

2

0

1

1

0

1

0

3

0

1

0

0

1

1

4

1

1

0

1

0

0

5

1

1

1

1

0

1

6

1

0

1

1

1

0

7

1

0

0

1

1

1

Преобразование кода Грея в двоичный код начинается с цифры самого левого разряда и движения вправо, принимая bi=gi, если число единиц, предшествующих gi , четно и (черта обозначает инвертирование), если число единиц, предшествующих gi , нечетно. При этом нулевое число единиц считается четным. Пример двоичного числа, соответствующее коду Грея 1001011, показан на рис. 3.4.

Рис. 3.4. Преобразование кода Грея в двоичный код

Приведем некоторые свойства функций Уолша.

1. Функции Уолша ортонормированны на интервале :

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

.

3. Функции Уолша обладают свойством симметрии, проявляющимся в том, что все выводы относительно i справедливы также и относительно t. Например, свойство мультипликативности с учетом свойства симметрии запишется в виде

.

4. Умножение любой функции самой на себя дает функцию нулевого порядка , так как в результате получаются только произведения вида (+1)(+1) и (-1)(-1). Таким образом,

.

5. Очевидно также, что умножение на не изменяет функцию .

Способ нумерации функций в системе называется упорядочением. Функции Уолша, сформированные в соответствии с выражением (3.4), упорядочены по Уолшу.

В ряде практических задач целесообразно пользоваться иными способами упорядочения. Часто применяются функции Уолша, упорядоченные по Адамару [had(h,t)] и по Пэли [pal(p,t)].

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

Остановимся на упорядочении по Адамару. При N=2n матрица Адамара может быть получена с помощью соотношения

;    

.

Матрица Адамара также может быть получена из ядра c помощью кронекеровского произведения, т.е.

.

Далее (табл. 3.2, 3.3) приводятся нумерация функций Уолша в базисе из 16 функций при различных способах упорядочения и нумерация для базиса из 8 функций. Сравнение таблиц показывает, что нумерация одних и тех же функций в упорядочении Адамара меняется в зависимости от размерности базиса.


Таблица 3.2

Нумерация функций Уолша

при различных способах упорядочения, N=16

Таблица 3.3

Нумерация функций Уолша

при различных способах упорядочения, N=8

wal(n,t)

had(h,t)

pal(p,t)

wal(n,t)

had(h,t)

pal(p,t)

0

0

0

0

0

0

1

8

1

1

4

1

2

12

3

2

6

3

3

4

2

3

2

2

4

6

6

4

3

6

5

14

7

5

7

7

6

10

5

6

5

5

7

2

4

7

1

4

8

3

12

9

11

13

10

15

15

11

7

14

12

5

10

13

13

11

14

9

9

15

1

8

Быстрое преобразование Уолша можно получить с помощью технологии разбиения матриц. Графическая схема алгоритма показана на рис. 3.5. Рассмотрим вывод алгоритма для N=8. При N=8 в матричном виде преобразование Уолша можно записать как

.

Используя соотношение , H(3) можно выразить через  H(2), что приводит к

.

Из разбиения матрицы следует, что

и ,

где  ;

.

Подставляя вместо , будем иметь

  и

.

Тогда получим

;

;

;

.

Так как , то окончательно получим

Для N=2n:

1. Общее число итераций равно n=log2N. Индекс r принимает значения r=1,2,..., n.

2. В r итерации участвует 2r-1 групп по N/2r-1 элементов. Половина элементов в каждой группе связана с операцией сложения, а другая половина – с операцией вычитания.

3. Общее число арифметических операций, необходимое для вычисления всех коэффициентов преобразования,  равняется приблизительно Nlog2N.

На рис. 3.5 приведена граф-схема процедуры быстрого алгоритма Уолша.

Рис. 3.5. Процедура быстрого алгоритма Уолша

3. Задание

1. Ознакомьтесь с теоретической частью.

2. Для заданного сигнала реализовать ДПУ и алгоритм быстрого преобразования Уолша (БПУ) (прямое и обратное преобразования).

  1.  для ДПУ использовать функции Уолша, упорядоченные по частоте;
  2.  для БПУ сохранить логику алгоритма из лабораторной работы №1.

3. Сравнить ДПУ с методом дискретного преобразования Уолша по вычислительной сложности (количество операций сложения и умножения).

4. Оформить отчет.

Содержание отчета:

  1.  исходные данные;
  2.  краткое описание алгоритма работы программы;
  3.  график заданной функции, график по результатам прямого преобразования, график по результатам обратного преобразования;
  4.  анализ вычислительной сложности ДПУ и БПУ, пояснение полученных результатов;
  5.  выводы.

4. Контрольные вопросы

1. Для чего используются ортогональные преобразования?

2. Доказать, что базис Уолша является ортогональным.

3. Дать определение преобразованию Уолша.

4. Каковы основные свойства преобразования Уолша?

5. Каким образом осуществляется быстрое преобразование Уолша?

6. В чем заключается преимущество быстрого преобразования Уолша?


Лабораторная работа №4

Вейвлет-преобразование

1. Цель работы

Изучение основ вейвлет-анализа, непрерывного вейвлет-преобразования (НВП), дискретизированного НВП, дискретного вейвлет-преобразования (ДВП), методики быстрого вейвлет-преобразования (БВП) с помощью алгоритма Маллата и лифтинговой схемы.

2. Теоретические сведения

Методы обработки стационарных сигналов

Большинство сигналов, встречающихся на практике, представлено во временной области, т.е. сигнал есть функция времени. Таким образом, при отображении сигнала на графике одной из координат (независимой) является ось времени, а другой координатой (зависимой) – ось амплитуд. Таким образом, получаем амплитудно-временное представление сигнала. Для большинства приложений обработки сигналов это представление не является наилучшим. Во многих случаях наиболее значимая информация скрыта в частотной области сигнала. Частотный спектр есть совокупность частотных (спектральных) компонент и он отображает наличие тех или иных частот в сигнале. Частота измеряется в Герцах (Гц), или в числе периодов в секунду. На рис. 4.1 представлены три косинусоиды: 3, 10 и 50 Гц соответственно.

Рис. 4.1 Косинусоиды с частотой 3, 10 и 50 Гц соответственно

Классическим методом частотного анализа сигналов является преобразование Фурье, суть которого пояснялась в лабораторной работе №1.

Результат преобразования Фурье – амплитудно-частотный спектр, по которому можно определить присутствие некоторой частоты в исследуемом сигнале. Результаты преобразования Фурье трех косинусоид (3, 10 и 50 Гц соответственно) представлены ниже на рис. 4.2.

Рис. 4.2. Результаты преобразования Фурье

косинусоид с частотой 3, 10 и 50 Гц соответственно

Приведем еще один пример стационарного сигнала

, его график и результаты преобразования Фурье (рис. 4.3).

Рис. 4.3. Стационарный сигнал, результаты ПФ данного сигнала

Большинство реальных сигналов имеет сложные частотно-временные характеристики. Как правило, такие сигналы состоят из близких по времени, короткоживущих высокочастотных компонент и долговременных, близких по частоте низкочастотных компонент.

Сигнал на рис. 4.4 нестационарный. Его частота непрерывно изменяется во времени (четыре частотные компоненты соответствуют частотам 100, 50, 25, 10 Гц.)

Рис. 4.4. Нестационарный сигнал

Спектр этого сигнала (ПФ) будет иметь вид (рис. 4.5):

Рис. 4.5. Спектр нестационарного сигнала

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

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

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

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

Краткий обзор оконного преобразования Фурье

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

Одним из таких методов является обобщенный метод Фурье (оконное преобразование Фурье, ОПФ). Этот метод состоит из следующих этапов:

1. в исследуемой функции создается «окно» – временной интервал, для которого функция f(x)0, и f(x)=0 для остальных значений;

2. для этого «окна» вычисляется преобразование Фурье;

3. «окно» сдвигается, и для него также вычисляется преобразование Фурье.

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

Рис. 4.6. Оконное преобразование Фурье:

функция f(t) перемножается с оконной функцией g(t), и вычисляются коэффициенты произведения f(t)g(t). Затем процедура повторяется для

сдвигов окна g(t-t0), g(t-2t0), …

Данный подход позволяет определить факт присутствия в сигнале любой частоты и интервал ее присутствия. Это значительно расширяет возможности метода по сравнению с классическим преобразованием Фурье, но существуют и определенные недостатки. Согласно следствиям принципа неопределенности Гейзенберга в данном случае нельзя утверждать факт наличия частоты 0 в сигнале в момент времени t0 - можно лишь определить, что спектр частот (1,2) присутствует в интервале (t1,t2). Причем разрешение по частоте (по времени) остается постоянным вне зависимости от области частот (времен), в которых производится исследование. Узкое окно обеспечивает временное разрешение, а широкое – частотное. Проблема состоит в том, что приходится выбирать окно «раз и навсегда», то есть для анализа сигнала, тогда как разные его участки могут потребовать применения разных окон.

Поэтому, если, например, в сигнале существенна только высокочастотная составляющая, то увеличить разрешение можно только, изменив параметры метода. В качестве метода, не обладающего подобного рода недостатками, был предложен аппарат вейвлет - анализа.

Основные положения вейвлет-анализа

Различают дискретный и непрерывный вейвлет-анализ, аппарат которых можно применять как для непрерывных, так и для дискретных сигналов.

Cигнал анализируется путем разложения по базисным функциям, полученным из некоторого прототипа путем сжатий, растяжений и сдвигов. Функция-прототип называется анализирующим (материнским) вейвлетом.

Вейвлет-функция должна удовлетворять двум условиям:

  1.  Среднее значение (интеграл по всей прямой) равно 0.
  2.  Функция быстро убывает при t  ∞.

Обычно, функция-вейвлет обозначается буквой ψ. В общем случае непрерывное вейвлет-преобразование (CWT) функции f(t) выглядит так:

,               (4.1)

где - параметр сдвига, s – параметр масштаба, функция – это «материнский вейвлет», то есть функция преобразования.

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

Основные вейвлетообразующие функции, или материнские вейвлеты, приведены в табл. 4.1.

Наиболее распространенные вещественные базисы конструируются на основе производных функции Гаусса (. Это обусловлено тем обстоятельством, что функция Гаусса имеет наилучшие показатели локализации как во временной, так и в частотной областях.

На рис. 4.7 показаны вейвлеты первых четырех порядков и модули их спектральной плотности. При получаем вейвлет первого порядка, называемый WAVE-вейвлетом с равным нулю нулевым моментом. При получаем MHAT-вейвлет, называемый «мексиканская шляпа» (mexican hat – похож на сомбреро). У него нулевой и первый моменты равны нулю. Он имеет лучшее разрешение, чем WAVE-вейвлет.

Совместное использование вейвлетов для ВП существенно повышает точность вейвлет-анализа.

Таблица 4.1

Основные материнские вейвлеты

Вейвлеты

Аналитическая запись

Спектральная плотность  

Вещественные непрерывные базисы

Гауссовы:

– первого порядка, или WAVE-вейвлет,

– второго порядка, или MHAT-вейвлет «мексиканcкая шляпа» – mexican hat),

n-го порядка,

DOG – difference of gaussians

LP-Littlewood & Paley

Вещественные дискретные

HAAR-вейвлет

FHAT-вейвлет, или «французская шляпа» (French hat – похож на цилиндр)

Комплексные

Морле (Morlet)

Пауля (Paul) (чем больше n, тем больше нулевых моментов имеет вейвлет)

Рис. 4.7. Вейвлеты первых четырех порядков и модули их спектральной плотности

Наиболее простой пример дискретного вейвлета – это HAAR-вейвлет. Недостатком его являются несимметричность формы и негладкость – резкие границы в t-области, вследствие чего возникает бесконечное чередование «лепестков» в частотной области, хотя и убывающих как .

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

t

Среди комплексных вейвлетов в наиболее часто используется базис, основанный на хорошо локализованном и во временной и в частотной областях вейвлете Морле. Характерный параметр позволяет изменять избирательность базиса. Вещественная и мнимая части – это амплитудно-модулированные колебания.

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

При ВП мы не имеем частотного параметра, как это было при ОПФ. Вместо него здесь имеется параметр масштаба, который можно определить как величину, обратную частоте. Параметр масштаба в вейвлет-анализе имеет аналогию с масштабом географических карт. Большое значение масштаба соответствуют малому количеству деталей, глобальному представлению сигнала, а низкие значения масштаба позволяют различить детали. Аналогично, в терминах частоты, низкие частоты соответствуют глобальной информации о сигнале (которая содержится на всей его протяженности), а высокие частоты – детальной информации, скрытым особенностям, которые имеют обычно малую протяженность. Масштабирование, как математическая операция, расширяет или сжимает сигнал. Поэтому, при расширяет сигнал, а при сжимает его.

В настоящее время большинство вычислений выполняют компьютеры. Это означает, что ни ПФ, ни ОПФ, ни НВП не могут быть практически вычислены путем взятия интегралов. Так как интегралы при вычислении заменяются суммами, то достаточно логичным будет применить дискретизацию частотно-временной области, то есть перейти к дискретизированному НВП. Параметр масштаба s дискретизируется на логарифмической сетке, а параметр времени дискретизируется в соответствии с параметром масштаба, что означает, что на разных масштабах имеет место различная частота дискретизации. Чем больше s, тем меньше временных отсчетов мы берем – поэтому для низких частот получаем хорошую частотную и скудную временную информацию, а для высоких частот наоборот. Дискретизированное НВП будет определяться следующим выражением:

,                (4.2)

Из-за некоторых недостатков от дискретизированного НВП перешли к дискретному вейвлет-преобразованию (ДВП).

Для начала определим понятие субполосное кодирование (subband coding). Это результат свертки сигнала с несколькими полосовыми фильтрами и децимацией результата. Совокупность набора фильтров и дециматоров называется банком фильтров. Каждый получившийся в результате преобразования сигнал несет в себе информацию о спектральной составляющей исходного сигнала при некотором пространственном (временном) масштабе. Для обратного синтеза сигнала выполняется операция интерполяции субполосных сигналов, фильтрация и их сложение. Использование субполосного кодирования вкупе с кратномасштабным анализом (multiresolution analysis), который представляет собой процесс декомпозиции сигнала на различных частотах и различном разрешении одновременно, позволяет получить масштабно-временное представление сигнала. Разрешение сигнала изменяется за счет фильтрации сигнала и является мерой количества детальной информации в нем, масштаб изменяется за счет интерполяции и децимации. Интерполяция соответствует увеличению частоты дискретизации сигнала, а децимация понижению. Эти процедуры осуществляются добавлением новых отсчетов между существующими отсчетами сигнала и удалением некоторых отсчетов из сигнала соответственно.

В ходе ДВП сигнал анализируется в различных частотных полосах с различным разрешением путем декомпозиции на грубую аппроксимацию (полусуммы соседних значений сигнала) и детали (полуразности соседних значений сигнала). Таким образом, определены два множества функций: масштабирующие функции и вейвлеты, соответствующие низкочастотным (НЧ) и высокочастотным (ВЧ) фильтрам.

          (4.3)

           (4.4)

Эта особенность была замечена Маллатом и изложена им в одной из своих работ.

               (4.5)

               (4.6)

Эти два выражения определяют два фильтра: низкочастотный и высокочастотный. Добавляя к этой группе фильтров два дециматора, использование которых обусловлено избыточностью данных получаемых с выходов фильтров, получаем банк фильтров анализа (рис. 4.8). Следует отметить, что операция децимации в данном случае удаляет из сигнала нечетные компоненты и оставляет четные. Единичное применение такого банка фильтров к сигналу делит его на две части, в одной из которых содержатся высокие частоты сигнала, а в другой низкие. В матричном виде это выглядит так:

,                 (4.7)

где An, Dn фильтрующие матрицы размерностью 2n-1 x 2n, построенные на основании коэффициентов фильтра в зависимости от разрядности x и претерпевшие децимацию – удаление нечетных строк; x – исходный сигнал; an-1 и dn-1 – низкочастотная и высокочастотная составляющие сигнала x.

Рис. 4.8. ДВП. Процедура анализа:

A, D – фильтрующие матрицы (низкочастотная и высокочастотная),

2↓ - дециматор, v0 и v1 - an-1 и dn-1 соответственно

Так как строки комбинированной матрицы (состоящей из An, Dn) взаимно ортогональны, так же, как и столбцы, то квадратная матрица инвертируема. Процедура инвертирования в этом случае соответствует процедуре транспонирования матрицы. Полученная матрица [AT DT] представляет собой банк фильтров синтеза сигнала. Умножение этой матрицы на исходную справа дает нам единичный вектор I. Следовательно, мы имеем ортогональный банк фильтров синтеза – анализа (рис. 4.9).

Рис. 4.9. ДВП. Процедура анализа:

v0 и v1 - an-1 и dn-1 соответственно, 2↑ - интерполятор,

F и G – добавляющий и вычитающий фильтры соответственно

Интерполятор представляет собой узел, который вставляет между двумя значениями сигнала третье – нуль. Работа фильтров F и G восстанавливает исходный сигнал x. Таким образом, две эти схемы вместе образуют банк фильтров ДВП.

Аналогично появлению в свое время быстрого ПФ (БПФ), появилось быстрое вейвлет – преобразование (БВП, FWT). БВП вытекает из классического ДВП рекурсивным применением последнего, что возможно благодаря принципу кратномасштабного анализа (рис. 4.10).

Рис. 4.10. БВП. Логарифмическое дерево банков фильтров

Сигнал x поступает на вход первого банка фильтров в дереве. После преобразования и децимации коэффициенты ВЧ фильтра bj,k сохраняются, так как они являются выходом на своем уровне «логарифмического дерева». Выходы же НЧ фильтра после децимации, когда в выходном сигнале остались только четные компоненты, поступают на вход следующего банка фильтров, где процедура повторяется. Выходом второго уровня являются коэффициенты bj-1,k. Эта схема будет повторяться L=log2N раз, где N это число компонент в исходном сигнале. В итоге мы получим L-1 векторов с ВЧ фильтров и общее среднее – выход последнего НЧ фильтра, то есть полную декомпозицию сигнала. Применение такого рекурсивного алгоритма и есть БВП. Это преобразование подходит для любого сигнала, длина которого есть степень двойки, а также для любых вейвлетов, относящихся к классу ортогональных. Следует также добавить, что БВП обладает и обратным преобразованием, которое строится с использованием инверсного ДВП, когда в соответствие каждому блоку анализа на каждом уровне ставится блок синтеза. Таким образом, имеет место обратная рекурсия. Впервые такая связь между вейвлетами и фильтрами была открыта Стивеном Маллатом, поэтому в его честь этот алгоритм называют «алгоритмом Маллата» или «пирамидой Маллата».

Другим подходом к реализации БВП является лифтинговая схема (lifting scheme). Подобная реализация БВП позволяет конструировать очень многие типы вейвлетов, включая ортогональные, биортогональные, вейвлет Хаара и другие, вне зависимости от преобразования Фурье.

Лифтинговая схема, как и алгоритм Маллата, включает в себя два блока: блок анализа и блок синтеза сигнала. Рассмотрим блок анализа (рис. 4.11).

Рис. 4.11. Лифтинговая схема, блок анализа

На рисунке показано, что вектор входных значений sj  поступает на вход блока разделения (Split), который представляет собой устройство разбиения входного сигнала на две подпоследовательности по определенному закону с целью максимально «декоррелировать» сигнал. Одним из необходимых условий при проведении такой операции является возможность обратного восстановления сигнала из двух его подпоследовательностей, что используется на этапе анализа в блоке объединения (Merge) (рис. 4.12). Достаточно часто применяется разделение сигнала на две последовательности, состоящие из четных (even) и нечетных (odd) отсчетов исходного сигнала. Такая процедура получила название Lazy wavelet Transform – «ленивое» (не требующее больших усилий) вейвлет преобразование, которое задается выражением:

(evenj-1; oddj-1) := Split (sj)               (4.8)

Следующий блок в схеме анализа – это блок предсказания (Predict). На предыдущем шаге мы разделили исходный сигнал на две подпоследовательности четных и нечетных отсчетов. Если структура сигнала имеет локальную корреляцию, то четные и нечетные отсчеты будут сильно коррелированны. То есть, другими словами, имея одну подпоследовательность, должна быть возможность предсказать другую с заданной точностью. Всегда используется подпоследовательность четных отсчетов, чтобы предсказать подпоследовательность нечетных. В данном случае (вейвлет Хаара) нечетный отсчет sj;2l+1 будет использовать своего левого соседа sj;2l как предсказание. Тогда уточняющая разность dj-1;l будет являться разностью нечетного отсчета и предсказания:

dj-1;l = sj;2l+1 - sj;2l;                 (4.9)

Таким образом, операция предсказания определяется следующим выражением:

dj-1 = oddj-1 - P(evenj-1)              (4.10)

Рис. 4.12. Лифтинговая схема, блок синтеза

И, наконец, последний блок – блок обновления (Update). Коэффициенты, полученные на предыдущем этапе, необходимы чтобы «поднять» или «подтянуть» («обновить») оставшуюся часть отсчетов сигнала, так как вторая половина будет сохранена и анализироваться не будет. После процедуры четная подпоследовательность будет содержать информацию обо всем сигнале, так как, используя оператор предсказания, множество s будет дополняться информацией о множестве d, поскольку к этому моменту вместо множества d в памяти хранятся коэффициенты d* преобразования (характеризующие множество d). Обновление четной подпоследовательности определяется следующим выражением:

sj-1 = evenj-1 + U(dj-1).              (4.11)

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

3. Задание

1. Ознакомьтесь с теоретической частью.

2. Для заданного сигнала выполнить БВП (алгоритм Маллата). Сигнал представить в базисе Хаара. Максимальный уровень разложения N=4.

 Фильтры анализа: НЧ [1/2, 1/2];

             ВЧ [1/2, -1/2].

 Фильтры синтеза: НЧ [1, 1];

            ВЧ  [1, -1].

Вывести сигнал на каждом из четырех уровней разложения.

3. Напишите отчет.

Содержание отчета:

  1.  исходные данные (заданный сигнал);
  2.  краткое описание алгоритма работы программы;
  3.  результаты работы программы;
  4.  анализ и пояснение полученных результатов;
  5.  выводы.

Исходные данные: одномерный дискретный сигнал

  1.  1 вариант: 6, 1, 13, 4, 8, 11, 13, 12, 10, 6, 2, 7, 12, 10, 6, 8
  2.  2 вариант: 1, 6, 4, 13, 11, 8, 12, 13, 6, 10, 7, 2, 10, 12, 8, 6 
  3.  3 вариант: 10, 6, 2, 7, 12, 10, 6, 8, 6, 1, 13, 4, 8, 11, 13, 12 
  4.  4 вариант: 6, 10, 7, 2, 10, 12, 8, 6, 1, 6, 4, 13, 11, 8, 12, 13 
  5.  5 вариант: 6, 10, 6, 1, 2, 7, 13, 4, 12, 10, 8, 11, 10, 6, 13, 12 
  6.  6 вариант: 10, 6, 6, 1, 7, 2, 13, 4, 12, 10, 11, 8, 6, 10, 12, 13
  7.  7 вариант: 1, 4, 8, 6, 13, 11, 13, 12, 6, 10, 2, 7, 10, 12, 6, 8

4. Контрольные вопросы

1. Назовите основные недостатки преобразования Фурье при анализе нестационарных сигналов.

2. Поясните суть оконного преобразования Фурье, его преимущества по сравнению с преобразованием Фурье и недостатки по сравнению с вейвлет-преобразованием.

3. Поясните основные положения вейвлет-анализа.

4. Назовите основные этапы реализации алгоритма Маллата.

5. Назовите основные этапы реализации лифтинговой схемы.


ЛИТЕРАТУРА

  1.  Ярославский Л.П. Введение в цифровую обработку изображений. – М.: Сов. радио, 1979.
  2.  Садыхов Р.Х., Чеголин П.М., Шмерко В.П. Методы и средства обработки сигналов в дискретных базисах. – Мн.: Наука и техника, 1987.
  3.  Прэтт У. Цифровая обработка изображений. – М.: Мир, 1982.
  4.  Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. – М.: Мир, 1988.
  5.  Беллман Р. Введение в теорию матриц. – М.: Наука, 1976.
  6.  Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. – М.: Мир, 1978.
  7.  Абламейко С.В., Лагуновский Л.М. Обработка изображений: технология, методы, применение. – Мн.: Институт технической кибернетики НАНБ, 1999.
  8.  Садыхов Р.Х., Мачнев А.Г. Систолические процессоры цифровой обработки изображений в двумерных базисах. – Мн. : Институт технической кибернетики НАНБ, 1996.
  9.  Эндрюс Г. Применение вычислительных машин для обработки изображений. – М.: Наука, 1977.
  10.  Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. – М.: Наука, 1989.
  11.  Гонсалес Р., Вудс Р. Цифровая обработка изображений. - М.: Техносфера, 2005.
  12.  Сэломон Д. Сжатие данных, изображений и звука: Учеб. пособие для вузов. - М.: Техносфера, 2004.
  13.  Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии: Учеб. пособие. - М.: Триумф. 2003.


 

А также другие работы, которые могут Вас заинтересовать

52788. Классный час. Наши меньшие друзья 109.5 KB
  Параскевич Олененок Однажды пограничники шли из наряда на заставу. Пограничники осторожно подошли к дереву и увидали маленького олененка. Следов оленихи пограничники не обнаружили и взяли олененка с собой. Пограничники давали олененку печенье и конфеты.
52789. “ОЙ РОДЕ НАШ КРАСНИЙ, РОДЕ НАШ ПРЕКРАСНИЙ…” ВИХОВНИЙ ЗАХІД 81 KB
  Батько мати брат сестричка І всі інші члени роду – Всі належать до одного Українського народу. дійові особи: мати батько хлопчик дівчинка Дівчинка. Мати. Заходь доню будемо хліб виймати На рушник долі його викладати.
52790. Виховання духовності на уроках образотворчого мистецтва 56.5 KB
  Учитель музики: Україна – це щира пісня яка завжди була поруч з людиною у радості і смутку у праці і відпочинку. Це пісня. Сьогодні пісня у нас в гостях. Входить дівчинка в українському вбранні та виконує українську пісню Учитель образотворчого мистецтва: І полетіла пісня неозорими просторами України полями та лісами горами та полонинами містами та селами.
52791. Наш край у 1960-1980-ті роки. Дудчани: на вістрі часу і подій 77.5 KB
  Випереджувальне завдання: підготувати звіт груп про соціологічне опитування мешканців села Дудчани ХІД УРОКУ І. А що думають пересічні громадяни нашої країни зокрема села про ті часи ІІІ. Вивчення нового матеріалу Звіт про соціологічне опитування мешканців села Дудчани 1 група. У процесі облаштування ділянки біля Будинку культури та насадженні липової алеї в честь загиблих у Велику Вітчизняну війну односельчан брали участь жителі села учні школи та вчителі.
52792. Тематична відкрита виховна година-зустріч в 4-Б класі до Дня Збройних Сил України «У здоровому тілі – здоровий дух» 121.5 KB
  Україна Учитель: Україна Край наш рідний Золота чарівна сторона Земля твоя рястом уквітчана зелом закосичена. Учитель: Діти. Учитель: Так діти козаки горді веселі кмітливі й незалежні сміливі і відважні сильні спритні здорові духом.Степаненка Питання Відповіді Учитель: Подякуємо діти і привітаємо зі святом Юрія Івановича.
52793. Влияние духовной жизни на здоровье человека 33.5 KB
  Донецка Интегрированный урок курсов Этика и Основы здоровья в 5м классе на тему Влияние духовной жизни на здоровье человека Подготовила: учитель Пак В. Тема: Влияние духовной жизни на здоровье человека. Цель урока: рассказать ученикам о влиянии духовной жизни на здоровье человека; подвести их к выводу о взаимосвязи духовного и физического здоровья; привить стремление к духовнонравственному благополучию; формировать ответственность за свое здоровье жизнь и здоровье других людей. На прошлом уроке мы с вами говорили о том что...
52794. Урок духовності. Весна – красна 53 KB
  Хід уроку Учитель: Доброго дня учні Доброго дня гості Сьогодні ми побуваємо в гостях у наших предків ознайомимося з національними скарбами українського народу щоб зрозуміти наскільки багата наша культура і невичерпна духовність. Пісня В саду гуляла Учитель: Традиції залишаються вірними собі. Пісня Два кольори Учитель: традиції залишаються а земля змінюється і оновлюється. Учитель: 1 березня 14 березня за новим стилем день Явдохи це свято є вісником весни.
52795. СТАНОВЛЕНННЯ ДУХОВНОСТІ ОСОБИСТОСТІ 32 KB
  Вибір соціальногуманістичного змісту життя диктує шляхи й засоби реалізації високого суспільного ідеалу – виховання вільної гармонійної духовноінтелектуальної високоморальної творчої особистості адаптованої до нових умов різнобічно розвиненої соціально зрілої яка успішно засвоює цінніснонормативний досвід попередніх поколінь людства й свого народу виробляючи свій власний досвід діяльності творчості спілкування. Де пролягає шлях до духовності учня Насамперед через духовність вчителя мудрого наставника який...