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

РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

(ТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ)

САМООРГАНИЗУЮЩИИЕСЯ СИСТЕМЫ 
 

Курсовая  работа на тему

<<wavelеts>> 
 
 
 
 

Титов Вячеслав

Группа КС-72-08 
 
 
 
 
 
 
 
 
 

Москва 2011 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание.

1.Идея и возможности вейвлет-преобразования………………...3

2.Свойства  вейвлетов............................................................................4

3.Дискретное  вейвлет преобразование…………………………….11

4.Применения дискретного вейвлет преобразования.........14

  Заключение…………………………………………………………………………16

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  1.  Идея и возможности вейвлет-преобразования

  Вейвлет-технологии начали серьёзно развиваться в 80–90 годы прошлого века, хотя первый тип  вейвлета был описан ещё в 1909 году учёным Хааром. Многие типы и семейства вейвлетов были названы именами учёных, которые внесли большой вклад в разработку теоретических основ вейвлетов: Мейер, Добеши, Маллат.

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

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

  Противоположный пример – импульсная базисная дельта-функция d(t).Она чётко локализована во временной области и потому идеально подходит для представления разрывов сигнала. Но она не несёт информации о частоте сигнала и потому плохо приспособлена для представления сигналов на заданном отрезке времени.

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

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

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

       

  Сравнение представления сигналов в различных  областях 
 

 
 
 

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

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

 

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

  2.  Свойства вейвлетов

  Вейвлет («короткая волна», «всплеск») –  это волновая форма сигнала эффективно ограниченной длительности, которая  имеет среднее значение ноль.

  

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

 
 

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

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

  Математически процесс анализа Фурье представлен преобразованием Фурье: 

 

  которое является суммой по всему времени  сигнала f(t) умноженного на комплексную экспоненту.

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

 

Аналогично, непрерывное  прямое Wavelet-преобразование определяется как сумма по всему времени сигнала, умноженного на масштабируемые, сдвинутые версии вейвлет функции: 

 

Где ψ(t) – Wavelet-функция, f(t) – сигнал.

Результатом НВП  будет вейвлет коэффициенты N(τ, a), которые являются функцией позиции τ и масштаба a. 
 

  Преобразование исходного сигнала 

  Амплитудно-временное  представление нестационарного сигнала и его результатнепрерывного вейвлет преобразования

  Масштабирование вейвлета просто означает его растяжение (или сжатие).

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

 
 

  Чем больше частота, тем более сжатая синусоида.

  Масштабный  коэффициент действует и на вейвлеты. Чем меньше масштаб, тем более  «сжатым» будет вейвлет. 

  Из  диаграмм видно, что для синусоиды sin(wt) масштаб а обратно пропорционален частотеw. Аналогично, с вейвлет-анализом, масштаб обратно пропорционален частоте сигнала.

  Сдвиг вейвлета просто означает задержку или ускорение его фронта. Математически задержка функции на k представляется в виде:

Вейвлет функция                           Сдвинутая вейвлет функция  
 
 

  Семейства вейвлет-функций

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

Haar

 
 

Daubechies

Morlet-преобразование

Mexican Hat-преобразование

 
 
 
 
 
 
 

  Непрерывное прямое вейвлет-преобразование

  Для создания НВП необходимо выполнить  следующих пять шагов:

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

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

3.  Сдвинуть вейвлет вправо и повторять шаг 1 и 2 до тех пор, пока Вы не исследуете весь сигнал.

4.  Масштабировать (растянуть) вейвлет и повторить шаги 1 – 3.

5.  Повторить шаги 1 – 4 для всех масштабов.

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

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

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

  Из  графиков видно, что чем выше масштаб, тем «протяженнее» вейвлет. Чем  протяженнее вейвлет, тем длиннее  часть сигнала, с которой он сравнивается, и более крупные черты сигнала  будут измерены вейвлет коэффициентами.

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

  Малый масштаб а Þ Сжатый вейвлет Þ быстро изменяющиеся составляющие Þ высокая частотаw.

  Большой масштаб а Þ Растянутый вейвлет Þ медленно изменяющиеся, крупные черты Þ низкая частота w.

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

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

где f(t) – восстановленный сигнал, ψ(t) – вейвлет-функция, С(t, a) – вейвлет коэффициенты, которые являются функцией позиции t и масштаба a, Kψ – коэффициент, зависящий от выбора вейвлет-функции, R – область ограничения сигнала.

3.  Дискретное вейвлет преобразование.

Дискретное  вейвлет преобразование одномерного  сигнала

  Цифровая  обработка сигнала требует его  дискретизации. Как и в случае преобразования Фурье существует дискретная форма вейвлет преобразования. Выше было отмечена определенная степень  свободы в выборе базиса вейвлет  преобразования. В данном разделе  нами будет использоваться один из самых простых вейлвет базисов  – базис Хаара.

  Рассмотрим  дискретизированный и квантованный сигнал (сигнал 1) – рисунок 1 (а). Будем  постепенно усреднять данный сигнал, усредняя попарно его отсчеты. Таким  образом, каждый шаг усреднения будет  сокращать разрешение сигнала в 2 раза (т.е. для его представления  будет требоваться в два раза меньшее число отсчетов). Однако при таком усреднении мы теряем часть  информации о сигнале, для того чтобы  восстановить сигнал после усреднения нам потребуется дополнительная информация. Будем сохранять разности между усредненным отсчетом и  отсчетами, из которых усредненный  отсчет состоит при более высоком  разрешении. Данные разности показывают детали сигнала – его флуктуации вокруг среднего при данном уровне разрешения. На рисунке 1 детализирующее коэффициенты показаны в правой части  рисунков 1 (б, в, г, д). Теперь воспользовавшись детализирующими коэффициентами мы сможем восстановить прежнею форму  сигнала.

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

Сигнал 1, изображенный на рисунке 1 (а), может быть представлен  так:

 

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

 

Рисунок 1 – Усреднение дискретизированного сигнала 

Рисунок 1.2 
 
 
 
 

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

  Рассмотрим  теперь процедуру усреднения сигнала, проиллюстрированную на рисунке 1, с  точки зрения только что введенных  базисов. Рассмотрим конкретный сигнал, заданный следующим вектором значений – [9 7 3 5]. С помощью масштабирующей функции Хаара мы можем представить  сигнал так, как это изображено на рисунке 1.3.

Рисунок 1.3 – Представление  исходного сигнала в базисе Хаара

Проведем процедуру  декомпозиции сигнала на две части  – усредненный сигнал с двое уменьшенным  разрешением и детализирующие коэффициенты. Получим следующий вектор  = [8 4 | 1 –1], представление которого в базисе Хаара с помощью масштабирующей функции и вейвлетов изображено на рисунке 1.4.

Рисунок 1.4 – Представление  усредненного сигнала в базисе Хаара

Выделим в векторе [8 4 | 1 –1] часть, представляющую усредненный  сигнал (первая половина вектора), и  проведем относительно неё повторное  усреднение и нахождение детализирующих коэффициентов. Получим следующий  вектор – [6 | 2 1 –1] представление которого в базисе Хаара с помощью масштабирующей функции и вейвлетов изображено на рисунке 1.5.

Рисунок 1.5 – Представление  дважды усредненного сигнала в базисе Хаара

Таким образом, мы представили  исходный сигнал с помощью его  усредненной части (среднего по сигналу) и детализирующих коэффициентов. Отметим, что размерность исходного и  преобразованного векторов совпадают, это говорит о том, что при  преобразовании не было потерь информации и, следовательно, возможно полное восстановление исходного вектора. Шаги описанной  процедуры ещё раз проиллюстрированы  на рисунке 1.6. 

  Рисунок 1.6 – Представление сигнала в  базисе Хаара

  Отметим, что если мы будем восстанавливать  сигнал после его разложения в  базисе Хаара, то мы можем остановить процесс восстановления «на полпути» и получить представление сигнала  с заданным разрешением. Другими  словами нами получен математический инструмент изменения разрешения сигнала 

4.  Применения дискретного вейвлет преобразования.

 

 

Сжатие  изображений. JPEG 2000

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

  Одной из таких дополнительных функции  является ROI (Region of Interest). ROI позволяет  динамически в пространстве и  во времени повышать разрешение изображения. Под динамическим повышением разрешения изображения в пространстве понимается то, что мы можем повысить разрешение только выделенной области изображения. Под динамическим повышением разрешения изображения во времени понимается то, что мы можем повышать разрешение выделенной области изображения  постепенно, шаг за шагом.

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

Поиск изображений по образцу 
 

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

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

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Многомасштабное редактирование

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

 

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

Заключение

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

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

  Список  литературы  

  1.  И.М. Дремин, О.В. Иванов, В.А. Нечитайло. Вейвлеты и их использование. – Успехи физических наук, 2001

  2.  Wavelet Digest – www.wavelet.org

  3.  Br. Vidakovic, P. Mueller. Wavelets for kids – Duke University.

  4.  А. Переберин. Многомасшабные методы синтеза и анализа изображений – Москва, 2001.

5.  А. Петров. Вейвлеты и их приложения – Рыбинск, РГАТА 2007