Каталог :: Математика

Курсовая: Реализация метода непрерывного Вейвлет преобразования для одномерных массивов

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ

ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) МИФИ Кафедра 17

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К УЧЕБНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ ТЕМА: “РЕАЛИЗАЦИЯ МЕТОДА НЕПРЕРЫВНОГО ВЕЙВЛЕТ ПРЕОБРАЗОВАНИЯ ДЛЯ ОДНОМЕРНЫХ МАССИВОВ ” Выполнил студент группы К7-171 Лукаш В.В. Научный руководитель Башашин М.В. Москва, 1999

ОГЛАВЛЕНИЕ

1. ВВЕДЕНИЕ 2. ПОСТАНОВКА ЗАДАЧИ 3. ПОДХОДЫ К АНАЛИЗУ СИГНАЛОВ СО СЛОЖНЫМИ ЧАСТОТНО- ВРЕМЕННЫМИ ХАРАКТЕРИСТИКАМИ 3.1 Методы обработки нестационарных сигналов 3.2 Краткий обзор преобразования Фурье 3.3 Основные положения вейвлет-анализа 4. РЕАЛИЗАЦИЯ АЛГОРИТМА 4.1 Методы вычисления непрерывного вейвлет преобразования и их сравнение с точки зрения реализации 4.1.1 Во временной области 4.1.2 В частотной области 4.2 Выбор материнского вейвлета 4.3 Система “клиент-сервер” как способ повышения скорости алгоритма 4.3.1 Функции “клиента” 4.3.2 Функции “сервера” 5. ЗАКЛЮЧЕНИЕ 6. СПИСОК ЛИТЕРАТУРЫ 7. ПРИЛОЖЕНИЯ

1. ВВЕДЕНИЕ

Любые исследования обычно укладываются в следующую схему: 1. Сбор информации (фиксация среднестатистических данных, прием данных от тех или иных датчиков и т. п.) 2. Анализ полученных данных (выделение характерных особенностей, визуализация, отсеивание аномальных значений, определение периодичностей, частотного спектра и т. д.) В результате первого шага получается некий массив данных, который будем называть сигналом. В силу многообразия встречающихся в природе сигналов часто приходится сталкиваться с сигналами, имеющими сложные частотно-временные характеристики (простым примером служит электрокардиограмма человека). Данная работа посвящена изучению и реализации непрерывного вейвлет преобразования для случая дискретного сигнала. Традиционным подходом к исследованию числовых рядов является преобразование Фурье, в результате которого получается частотный спектр сигнала. Недостатком преобразования Фурье является то, что частотные компоненты не могут быть локализованы во времени, в связи с чем иногда невозможно получить исчерпывающей информации о сигнале. В таких случаях для анализа сигнала целесообразно применять вейвлет преобразование (ВП), которое позволяет получить частотно-временную развертку сигнала, дающую существенно больше информации, чем в случае Фурье-анализа. Возвращаясь к двум ступеням исследований, заметим, что сбор информации и анализ данных часто неудобно проводить совместно, иногда это происходит в разных лабораториях, а, следовательно, возникает необходимость создания распределенной системы “клиент-сервер”. 2. ПОСТАНОВКА ЗАДАЧИ Для разработки модуля анализа основных характеристик электрокардиограммы (ЭКГ) человека в компьютерном кардиологическом комплексе необходимо реализовать алгоритм непрерывного вейвлет преобразования. Для этого следует: · изучить теоретические основы непрерывного вейвлет преобразования; · исследовать способы реализации непрерывного вейвлет преобразования; · сравнить методы реализации алгоритмов и выбрать способы их ускорения. При проведении исследований использовать среду Matlab 5.0, разработанный алгоритм реализовать в среде программирования Delphi 5.0. 3. ПОДХОДЫ К АНАЛИЗУ СИГНАЛОВ СО СЛОЖНЫМИ ЧАСТОТНО-ВРЕМЕННЫМИ ХАРАКТЕРИСТИКАМИ 3.1 Методы обработки нестационарных сигналов Вейвлет преобразование стремительно завоевывает популярность в столь разных областях, как телекоммуникации, компьютерная графика, биология, астрофизика и медицина. Благодаря хорошей приспособленности к анализу нестационарных сигналов 1 оно стало мощной альтернативой преобразованию Фурье в ряде медицинских приложений. Так как многие медицинские сигналы нестационарны, методы вейвлет анализа используются для распознавания и обнаружения ключевых диагностических признаков. Однако, прежде чем ставить перед собой задачу отбора подходящих методов анализа сигнала, необходимо ответить на следующие вопросы: · Является ли сигнал стационарным ? · Какие характеристики сигнала исследуются ? В данной работе изучаются частотно-временные характеристики нестационарных сигналов, что и определяет особый подход к выбору метода. Преобразование Фурье представляет сигнал, заданный во временной области, в виде разложения по ортогональным базисным функциям (синусам и косинусам), выделяя таким образом частотные компоненты. Недостаток преобразования Фурье заключается в том, что частотные компоненты не могут быть локализованы во времени, что накладывает ограничения на применимость данного метода к ряду задач (например, в случае изучения динамики изменения частотных параметров сигнала на временном интервале). Большинство медицинских сигналов имеет сложные частотно-временные характеристики. Как правило, такие сигналы состоят из близких по времени, короткоживущих высокочастотных компонент и долговременных, близких по частоте низкочастотных компонент. Для анализа таких сигналов нужен метод, способный обеспечить хорошее разрешение и по частоте, и по времени. Первое требуется для локализации низкочастотных составляющих, второе – для разрешения компонент высокой частоты. Существует два подхода к анализу нестационарных сигналов такого типа. Первый – локальное преобразование Фурье (short-time Fourier transform). Следуя по этому пути, мы работаем с нестационарным сигналом, как со стационарным, предварительно разбив его на сегменты (окна), статистика которых не меняется со временем. Второй подход – вейвлет преобразование. В этом случае нестационарный сигнал анализируется путем разложения по базисным функциям, полученным из некоторого прототипа путем сжатий, растяжений и сдвигов. Функция прототип называется материнским, или анализирующим вейвлетом. ___________________________ 1 - то есть таких, у которых характеристики меняются во времени [5b] 3.2 Краткий обзор преобразования Фурье Классическим методом частотного анализа сигналов является преобразование Фурье, суть которого можно выразить формулой (1)
Результат преобразования Фурье – амплитудно-частотный спектр, по которому можно определить присутствие некоторой частоты в исследуемом сигнале. В случае, когда не встает вопрос о локализации временного положения частот, метод Фурье дает хорошие результаты. Но при необходимости определить временной интервал присутствия частоты приходится применять другие методы. Одним из таких методов является является обобщенный метод Фурье (локальное преобразование Фурье). Этот метод состоит из следующих этапов: 1. в исследуемой функции создается “окно” – временной интервал, для которого функция f(x)¹0, и f(x)=0 для остальных значений; 2. для этого “окна” вычисляется преобразование Фурье 3. “ окно” сдвигается, и для него также вычисляется преобразование Фурье “Пройдя” таким “окном” вдоль всего сигнала, получается некоторая трехмерная функция, зависящая от положения “окна” и частоты. Данный подход позволяет определить факт присутствия в сигнале любой частоты, и интервал ее присутствия. Это значительно расширяет возможности метода по сравнению с классическим преобразованием Фурье, но существуют и определенные недостатки. Согласно следствиям принципа неопределенности Гейзенберга в данном случае нельзя утверждать факт наличия частоты w0 в сигнале в момент времени t0 - можно лишь определить, что спектр частот (w1 ,w2) присутствует в интервале (t1,t2). Причем разрешение по частоте (по времени) остается постоянным вне зависимости от области частот (времен), в которых производится исследование. Поэтому, если, например, в сигнале существенна только высокочастотная составляющая, то увеличить разрешение можно только изменив параметры метода. В качестве метода, не обладающего подобного рода недостатками, был предложен аппарат вейвлет анализа. [2] 3.3 Основные положения вейвлет-анализа Различают дискретный и непрерывный вейвлет анализ, аппарат которых можно применять как для непрерывных, так и для дискретных сигналов. Cигнал анализируется путем разложения по базисным функциям, полученным из некоторого прототипа путем сжатий, растяжений и сдвигов (2). Функция-прототип называется анализирующим (материнским) вейвлетом. Вейвлет - функция должна удовлетворять 2-м условиям: 1. Среднее значение (интеграл по всей прямой) равен 0. 2. Функция быстро убывает при t ® ∞. Обычно, функция-вейвлет обозначается буквой ψ. В общем случае вейвлет преобразование функции f(t) выглядит так: (2) где t – ось времени, x – момент времени, s – параметр, обратный частоте, a (*) – означает комплексно-сопряженное.

Главным элементом в вейвлет анализе является функция-вейвлет. Вообще говоря, вейвлетом является любая функция, отвечающая двум вышеуказанным условиям. Наибольшей популярностью пользуются два изображенных на рисунке 1 вейвлета: Рис 1. Примеры вейвлетов. Сверху изображен вейвлет “сомбреро” (Mexican Hat), названный так благодаря своему внешнему виду. На нижней части рисунка 1 изображен вейвлет Морле. График любого вейвлета выглядит примерно также, как и вейвлет Морле. Заметим, что вейвлет Морле – комплекснозначный, на рисунке изображены его вещественная и мнимая составляющие. Итак, у нас имеется некоторая функция f(t), зависящая от времени. Результатом ее вейвлет-анализа будет некоторая функция W(x,s), которая зависит уже от двух переменных: от времени и от частоты (обратно пропорционально). Для каждой пары x и s рецепт вычисления вейвлет преобразования следующий: 1. Функция вейвлет растягивается в s раз по горизонтали и в 1/s раз по вертикали. 2. Далее он сдвигается в точку x. Полученный вейвлет обозначается ψ(x,s). 3. Производится усреднение в окрестности точки s при помощи ψ(x,s). В результате вырисовывается вполне наглядная картина, иллюстрирующая частотно-временные характеристики сигнала. По оси абсцисс откладывается время, по оси ординат – частота (иногда размерность оси ординат выбирается так: log(1/s), где s-частота), а абсолютное значение вейвлет преобразования для конкретной пары x и s определяет цвет, которым данный результат будет отображен (чем в большей степени та или иная частота присутствует в сигнале в конкретный момент времени, тем темнее будет оттенок).

Рис 2. Вейвлет преобразование стационарного сигнала. Данный рисунок показывает результаты вейвлет анализа для сигнала, представляющим из себя наложение двух синусоид различной частоты. Частотные характеристики данного сигнала не меняются во времени (сигнал стационарный), что хорошо видно на верхней части рисунка 2. По рисунку 3 удобно сравнить результаты, которые дают преобразование Фурье и вейвлет преобразование. Исходный сигнал изображен на рис (3a). Как видно из рис (3c) преобразование Фурье дает информацию о том спектре частот, который присутствует в сигнале в промежутке времени от 0 до 1 сек., при этом нам неизвестно когда именно та или иная частота реально присутствовала в сигнале. В то же время вейвлет преобразование (3b) дает исчерпывающую картину динамики изменения частотных характеристик во времени. Все это указывает на то, что вейвлет преобразование существенно более информативно по сравнению с преобразованием Фурье.

Рис 3. Сравнение методов анализа. 4. РЕАЛИЗАЦИЯ АЛГОРИТМА 4.1 Методы вычисления непрерывного вейвлет преобразования и их сравнение с точки зрения реализации Существует два разных пути проведения вейвлет преобразования. Речь идет о расчетах во временной и частотной областях. При работе во временной области мы имеем дело с функциями, аргументами которых являются временные параметры, а в случае частотной – частотные. В частотной области используется механизм быстрого преобразования Фурье. [5c] Частотная область дает возможность использовать готовые программные продукты для вычисления быстрого преобразования Фурье. В случае отсутствия таковых частотный метод существенно усложняется. Алгоритм, реализованный в частотной области, работает быстрее. К достоинствам алгоритма во временной области можно отнести относительную простоту в реализации (программировании). При выполнении работы была выбрана временная область. 4.1.1 Реализация во временной области Прежде всего, нам необходимо определить материнский вейвлет. Допустим, мы выбрали некоторую функцию, удовлетворяющую необходимым условиям: ψ0 (η), где η – безразмерный период. В данной работе рассматривается случай непрерывного вейвлет преобразования для дискретного сигнала. Итак, нам дана временная серия X, со значениями xn, в моменты времени nÎ[0,N-1], где N – количество измерений. Каждая величина разделена по времени на постоянную величину dt. Получив основную формулу для материнского вейвлета, необходимо иметь возможность изменять размеры вейвлета. Для этого строится так называемый "масштабированный" вейвлет который будет иметь вид: (3) s – параметр, обратный частоте. Вычисление вейвлет преобразования является сверткой искомой временной серии с функцией-вейвлетом. Основная формула имеет вид : (4) в данном случае (*) – означает комплексно-сопряженное. Результатом расчета Wn(s) по формуле (4) будет комплексное число. В качестве конечного результата берется абсолютное значение полученного комплексного числа. [5a] Блок – схема алгоритма:

Блок-схема: решение: n=N-1 ? ,?

нет
да
Получение результата вейвлет преобразования для пары значений n,s
Блок-схема: решение: Весь спектр частот изучен ? нет
да
Конец
4.1.2 Реализация в частотной области Вейвлет преобразование можно провести в частотной области. Для этого снова в первую очередь необходимо определить материнский вейвлет. Расчет по данной схеме происходит следующим образом: преобразование Фурье самого вейвлета (в данном случае будем рассматривать вейвлет Морле) сконцентрировано вокруг некоторой выделенной частоты w0 ≠ 0. Поэтому преобразование Фурье вейвлета, растянутого в s раз, будет сконцентрировано вокруг частоты w 0/s (см рис. 4).

Рис 4. Преобразование Фурье функции вейвлета. Так как свертка функций эквивалентна их перемножению в частотной области, “строка” s = const на изображении вейвлет преобразования показывает эволюцию изучаемой функции на частотах, близких w0/s. То есть умножение Фурье-спектра исходной функции на пик в точке w0/s в частотной области (то есть на Фурье-образ растянутого вейвлета) вырезает из этой функции все то, что дает вклад в ее спектр на частотах, близких w0/s. В результате получается развертка спектрального компонента во времени. [1] Основные формулы имеют вид: (5) где (*) – означает комплексно-сопряженное, а знак (^) – преобразование Фурье. (6) (7) Блок – схема алгоритма:

Блок-схема: решение: n=N-1 ? ,?

нет
да
Получение результата вейвлет преобразования для пары значений n,s
Блок-схема: решение: Весь спектр частот изучен ? нет
да
Конец
4.2 Выбор материнского вейвлета В качестве материнского вейвлета подходит любая функция, удовлетворяющая двум вышеуказанным условиям. Для реализации алгоритма в качестве анализирующего вейвлета было решено воспользоваться вейвлетом Морле (рис. 5). Это было сделано по трем причинам: · вейвлет Морле один из наиболее популярных [1] и широко применяется · он обладает значительной наглядностью · он прост в вычислительном плане, что ускоряет работу алгоритма
рис 5. Вейвлет Морле. Фактически вейвлет Морле является произведением комплексной синусоиды на гауссиан. , (8) где y является значением вейвлет функции с безразмерным периодом h, а w0 - волновой параметр (при реализации w0=6). Необходимо также отметить, что вейвлет Морле является комплекснозначным, то есть имеет действительную и мнимую части. 4.3 Система “клиент-сервер” как способ повышения эффективности алгоритма Сбор информации обычно подразумевает накопление большого объема данных, которые требуют тщательной обработки. Часто подобный анализ предусматривает использование мощного дорогостоящего вычислительного оборудования. Иногда, в силу специфики эксперимента, оборудование, необходимое для снятия экспериментальных данных и оборудование, необходимое для их обработки, вообще невозможно разместить в пределах одного исследовательского комплекса. При этом возникает задача объединения всей системы в единый комплекс и обеспечения эффективной передачи данных между отдельными компонентами. В данной работе предложен вариант создания распределенной системы ”клиент- сервер”, состоящей из двух независимых приложений, связь между которыми осуществляется по технологии “Socket Connection”. В данном случае взаимодействие строится на основе “гнезд” Windows. Для установления связи соответствующим образом настраиваются TCP/IP протоколы машин “клиента” и “сервера”, а также, идентификация портов “прослушивания”. “Socket Connection” обеспечивает очень быструю связь, а следовательно, гарантирует эффективную передачу данных. Это оправдано в том случае, если большой объем собранных данных пересылать на мощный сервер-обработчик, а затем получать назад результаты сложных вычислений. 4.3.1 Функции “клиента” В предложенной системе функции приложения клиента состоят в: · формировании сигнала, подлежащего дальнейшему анализу (данный сигнал имеет нестационарные частотно-временные характеристики) · визуализации заданного сигнала · настройке соединения через “Socket Connection” · обеспечении передачи данных, подлежащих обработке · обеспечении приема обработанных данных · обеспечении наглядной графической визуализации полученных результатов · обеспечении выборочного контроля полученного результата 4.3.2 Функции “сервера” В предложенной системе функции приложения сервера состоят в: · обеспечении приема данных, подлежащих анализу · обработке данных с помощью запрограммированного алгоритма непрерывного вейвлет преобразования · обеспечении визуального наблюдения за ходом обработки поступивших данных · настройке соединения через “Socket Connection” · обеспечении передачи обработанных данных 5. ЗАКЛЮЧЕНИЕ В ходе выполнения работы были рассмотрены следующие подходы к анализу нестационарных сигналов: · преобразование Фурье · локальное преобразование Фурье · непрерывное вейвлет преобразование Была проведена сравнительная оценка данных методов и сделаны выводы относительно достоинств и недостатков таковых, а также степени их применимости к тем или иным задачам. Преобразование Фурье не дает информации о динамике изменения частотных характеристик во времени. Локальное преобразование Фурье имеет постоянное разрешение по частоте (по времени) вне зависимости от области частот (времен), в которых производится исследование. Поэтому, если, например, в сигнале существенна только высокочастотная составляющая, то увеличить разрешение можно только изменив параметры метода. Для анализа нестационарных сигналов с широким спектром частот хорошо подходит аппарат непрерывного вейвлет преобразования, не обладающий подобными недостатками. Рассмотрены два варианта реализации непрерывного вейвлет преобразования: в частотной и временной областях. В ходе их сравнения было принято решение проводить реализацию во временной области. Частотная область предполагает использование аппарата преобразования Фурье. С точки зрения реализации частотная область удобна при наличии готовых библиотек вычисления преобразования Фурье. В случае отсутствия таковых реализацию удобнее проводить во временной области. На основе непрерывного вейвлет преобразования реализована программа, позволяющая проводить анализ дискретных нестационарных сигналов. В целях ускорения работы алгоритма предложена и разработана распределенная система “клиент-сервер”, в которой взаимодействие между компонентами осуществляется по технологии “Socket Connection”. 6. СПИСОК ЛИТЕРАТУРЫ 1. “Компьютерра” №8 1998г. 2 марта 2. “Непрерывное вейвлет преобразование как средство анализа ЭКГ человека” (пояснительная записка к учебно-исследовательской работе) Хафизов А.Р. 1998г. 3. “Delphi 3” Osier, Batson and Grobman , Borland Press 1997 4. “Delphi 2” М. Канту, 1 и 2 тома, 1997г 5. Источники в Internet: a) http://relpress.website.ru/currier/5/wavelet/wavelet.htm; b) http://www.public.iastate.edu/~rpolikar/WAVELETS/WTpart1.html c) http://paos.colorado.edu/research/wavelets/ 6. ПРИЛОЖЕНИЯ a) Описание программы. Рис.6 Сигнал. В разделе “Сигнал” клиента формируется нестационарный сигнал, с которым далее проводится вейвлет анализ. Рис.7 Соединение. В разделе “Соединение” настраивается связь между компонентами через TCP/IP протокол, а также отображается состояние приложения-клиента. Рис.8 Результат. В разделе “Результат” проводится визуализация полученного результата. Переключатель “С выделением” включает опцию выделения частоты, максимально присутствующей в сигнале в конкретный момент времени. В разделе “Контроль” содержатся выборочные результаты вейвлет преобразования (при n=20 и n=80). Рис. 9 Сервер. В функции сервера входит прием, обработка и возвращение результата по TCP/IP протоколу.