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

005019675

На правах рукописи

Строганов Сергей Александрович

Применение диадических вейвлетов для цифровой обработки сигналов

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2012

532089711651

Работа выполнена в ФГБОУ ВПО Российском государственном геологоразведочном университете имени Серго Орджоникидзе.

Научный руководитель: доктор физико-математических наук, Любушин Алексей Александрович.

Научный консультант: кандидат физико-математических наук, Фарков Юрий Анатольевич.

Официальные оппоненты: Кюркчан Александр Гаврилович, доктор физико-математических наук, профессор, заведующий кафедрой теории вероятностей и прикладной математики ФГБОУ ВПО Московский Технический Университет Связи и Информатики.

Гавриков Михаил Борисович, кандидат физико-математических наук, старший научный сотрудник ФГБУН Институт прикладной математики им. М.В. Келдыша РАН.

Ведущая организация: ФГБУН Институт математики имени С. Л. Соболева Сибирского отделения РАН.

Защита состоится 14 мая 2012 г. в 14 часов на заседании диссертационного совета Д 212.142.03 при ФГБОУ ВПО Московском государственном технологическом университете «СТАНКИН», расположенном по адресу: 127055, Москва, Вадковский переулок, д. За.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО Московского государственного технологического университета «СТАНКИН».

Автореферат разослан 13 апреля 2012 г. Ученый секретарь диссертационного совета,

к.т.н., доцент

Семячкова Б.Г.

Общая характеристика работы

Актуальность работы

В последнее время активно развиваются различные методы цифровой обработки сигналов. В настоящее время в России в этой области активно работают В.В. Сергеев, В. М. Чернов, М.В. Гашников, A.A. Потапов и другие. Из зарубежных специалистов можно отметить С. Малла, Э. Айфичера, Б. Джервиса, Г. Штарка, М. Фрейзера, Р. Гонсалеса и Р. Вудса. В частности, широкое распространение и развитие получили методы, основанные на использовании вейвлетов. В некоторых работах на русском языке вейвлеты называют всплесками. Одной из первых задач, в которой вейвлеты продемонстрировали свои преимущества, стала задача хранения дактилоскопических изображений. В США разработан и активно применяется национальный стандарт сжатия дактилоскопических изображений, основанный на применении биортогональных вейвлетов. Этот стандарт позволяет достигать коэффициента сжатия 1:15. Для широкого класса изображений, в том числе для фотографий, методы цифровой обработки, основанные на использовании вейвлетов, показывают лучшие результаты, чем другие методы обработки изображений. В стандарте JPEG2000 для решения задач кодирования и сжатия изображений используется вейвлет-преобразование. Применяемые в диссертации методы используют элементы общей теории дискретных преобразований Уолша и связаны с недавними результатами Б. Сендова (В. Sendov), В. Лэнга (W.C. Lang), В.Ю.Протасова, Ю.А.Фаркова и Ф. Шаха (F.A.Shah) о вейвлетах, определяемых с помощью функций Уолша. Одной из центральных проблем при использовании вейвлетов для цифровой обработки сигналов является выбор вейвлета. Например, в монографии С. Малла излагается метод выбора оптимального вейвлет-базиса для нелинейной аппроксимации сигнала, а в работах A.A. Любушина выбор оптимального вейвлет-базиса поз-

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

Цель диссертационной работы

1. Построение ортогональных и биортогональных диадических вейвлет-базисов в пространствах периодических и непериодических последовательностей.

2. Разработка алгоритма дискретного диадического вейвлет-преобразова-ния.

3. Применение диадических вейвлетов для оценки гладкости шума в модели малых блоков земной коры.

4. Применение диадических вейвлетов в задачах цифровой обработки изображений.

Научная новизна

1. Построены ортогональные и биортогональные диадические вейвлет-бази-сы в пространствах последовательностей и приведено их полное описание.

2. Исследованы системы диадических вейвлет-фильтров, разработан алгоритм построения многоэтапных биортогональных диадических вейвлет-базисов на основе систем вейвлет-фильтров.

3. Разработан алгоритм дискретного диадического вейвлет-преобразова-ния на основе быстрого преобразования Уолша.

4. Приведены примеры применения диадических вейвлетов в задачах кодирования изображений, а также для оценки гладкости низкочастотных микросейсмических колебаний.

Практическая значимость

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

Основные результаты диссертации докладывались на следующих конференциях:

1. IX международная конференция «Новые идеи в науках о Земле» (ИГРУ им. Серго Орджоникидзе, г. Москва, 2009 г.).

2. VI Международный симпозиум "Ряды Фурье и их приложения"(ЮФУ, г. Новороссийск, 2010 г.).

3. Российская конференция «Методы сплайн-функций», посвященная 80-летию со дня рождения Ю. С. Завьялова (Институт математики им. С.Л. Соболева СО РАН, г. Новосибирск, 2011 г.).

4. X международная конференция «Новые идеи в науках о Земле» (РГГ-РУ им. Серго Орджоникидзе, г. Москва, 2011 г.).

Публикации. Материалы диссертации опубликованы в 8 печатных работах, из них три статьи в рецензируемых журналах [1-3], одна статья в сборниках трудов конференций [5] и 4 тезисов докладов [4, 6-8].

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

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии. Общий объем диссертации 110 страниц включая 11 рисунков, 8 таблиц и два приложения. Библиография включает 48 наименований на 6 страницах.

Содержание работы

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

В первой главе рассматриваются биортогональные диадические вей-влеты в пространстве периодических последовательностей 12(Ж,ц). Пространство состоит из комплексных последовательностей

х = (..., х(—1), г(0),а;(1),х(2),...)

таких, что х^ + АО = х(^) для всех з 6 Для удобства изложения определены также числа = N/2". 1 < и < п.

Двоичная свертка векторов х и у из I2определяется по формуле

N-1

(х * у)(1) := х{1 Ш ¿)у0'). I е

3—0

где ф - операция поразрядного сложения по модулю 2.

Для каждого х 6 определяется также оператор сдвигаТк : 12(Ъц) -»

такой, что (Ткх)(1) := х{1®к), I е Далее доказываются следующие

равенства:

х*у = Ыху, {х,у} = N(5,у), 2\х{1) = и>к(1/Юх,

{Ткх., 1}у) = (г, Тшу>, (я, Тку) = х*у{к),

где {ад,} - система функций Уолша, а, х- дискретное преобразование Уолша последовательности х. По формуле

в(и, у) = {т2ки}^ и {ад^1 (1)

определяется множество двоичных сдвигов последовательностей и, V € 12(Жц). Если для некоторых и, V, я, г е множества В(и, у) и г), определен-

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

Теорема 1. Пусть и,у,з,т € 12{Системы В(и,у) и В(в,т) являются биортогональными диадическими вейвлет-базисами в12(Хц) тогда и только тогда, когда

и{1) и{1 + М) \ / ЭД Щ \=_2_/ю\

у{1) Щ + Ы^ ) + + ) № 1 )

для всех I = 0,1,..., N1 — 1.

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

удовлетворяют условию

и{1)Щ+и(1 + N1)7(1 + N1) = 2/ЛГ2, (3)

для любого I — 0,1,..., N1 — 1, а последовательности у,т € задать

равенствами

«(¿) = (-1)'я(1Ф0, т(0 = (-1)'«(1ф/)! /е2ц. (4)

Доказано, что в этом случае множества В(и, у) и г) являются биорто-гональными диадическими вейвлет-базисами в На основе этого утвер-

ждения предложен следующий метод построения вейвлет-базиса первого этапа:

1) выбираются последовательности и, в е так, чтобы они удовлетворяли условиям (3);

2) по формуле (4) определяются последовательности у, т €

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

Далее рассматривается разложение векторах € /2(2Г)) по базисам В(и, и) и В (я, т). Для вычисления координат вектора х в этих базисах путем умножения х на матрицу перехода требуется № комплексных умножений. Чтобы быстро вычислить координаты вектора х в базисе В(и,у) (или В (б, т)) требуется использовать тот факт, что (х, Т^и) = х*й(2к) и аналогично для V. В итоге вектор х в базисе В(и, у) можно представить в виде двух сверток с последующим отбрасыванием координат с нечетными индексами. Для описания быстрого перехода от евклидового стандартного базиса к вейвлет-базису и обратно, для 0 < V < п вводятся следующие операторы: О" : —)• /2(2дО

8

и U" : l2(—> î2(Zn), определяемые по формулам

(D"x)(j) = x{2»j), ,,ru S,-S J y(j/2")' еслиj делится на 2",

(uvv)b) = <

1 0, если j не делится на 2 ,

где х 6 /2(Zn), J/ G £2(Za'J, j = 0,1,..., iV — 1. Эти операторы называются операторами сгущающей и разрежающей выборки соответственно.

Разложение вектора х е l2(Zn) по базисам B(u,v) и B{s,t) происходит по формулам

JV,-1 Ni-l

® = £ (D(x * û)(fc))Г»и + £ * v)(k))Tav (5)

fc=0 k=0

и

x = (D(x*s)(k))T2ks+ J2 (D(x*r){k))T2kT. (6)

Формулы (5) и (6) называются формулами анализа первого этапа. Восстановление вектора х происходит по формулам синтеза первого этапа:

t*U(D(x*v)) + s*U(D(x* и)) = х

V * и{Б{х * г)) + и * и(0(х * а)) = х.

Затем для некоторого натурального т < п рассматривается система В{<р,ф), определяемая по формуле

{ТМйО1 и {ТМ^О1 и • • ■ и {^«ийГ1 и {Т2тк^-\ (7)

где ф\, Ф2, ■ ■ ■, Фт, <Рт £ и система В(!р, ф), определяемая аналогично

по векторам ф\, ф2, ■. ■, Фт, <?т £ Если системы В(<р, ф) и В(<р, ф) обра-

зуют пару биортогональных базисов в 12{Ъц), тогда они называются т-этапными биортогональными диадическими вейвлет-базисами в пространствеI2'

9

Для построения подобных вейвлет-базисов нужно выбрать т-этапную последовательность диадичесикх биортогональных вейвлет-фильтров «ь вь VI, п, и2, б'2, «2,75,..., ит, вт, ут, тт, таких, что и„, е /2(2лг„_,)

для любого г/ = 1,2,..., тп и любого / = 0,1,..., А^, выполнено равенство

/ й„(/) и^ + лд \ I МО %(1) \ =_2_[ 1 0 ] \ %(1) %{1 + К) ) \ %(1 + ду ЩТ+Щ) К-1 \ о 1 у '

Если положить V?! — щ, !р = в1, г/.'1 = -ф = Т\ и определить у;,,, £>„, три для ^ = 2,..., тп по формулам

¥>к = <ри-1 * С/"-1 («к), ■ф„ = <ри_1*и,"1(у,/) (9)

и

^ = ^ = (Ю)

то последовательности порождают т-этапный вейвлет-базис с

пространстве Соответственно, задача построения диадических много-

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

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

Пример 1. Пусть даны комплексные числа 60,61,60.61 такие, что

Ь0Ь0 + Ь1Ь1 = 1. (11)

Положим

„ _ А + Ь1 бр - Ь1 п п\ А+Ь. ~ ^ п т

Тогда системы {Тм«}*^1 и {Тк-.я})^1 являются биортогональными и удовлетворяют условию (3). Таким образом, для каждых значений параметров ^сь ¿01 ¿1 последовательности и, в порождают биортогональные диадические вейвлет-базисы в пространстве €

Во второй главе рассматриваются диадические вейвлеты в пространстве непериодических последовательностей 12{Ъ+). Процесс построения диа-дических вейвлетов в этом пространстве в целом аналогичен подходу, изложенному в главе 1. Основное отличие заключается в том, что пространство 12(1>+) является бесконечномерным, поэтому дополнительно требуется доказывать полноту полученных вейвлет-систем.

Еще одним отличием является тот факт, что свертка двух последовательностей из пространства ¿2(2+) не всегда принадлежит этому пространству, поэтому при построении диадических вейвлет-систем порождающие последовательности приходится выбирать из более узкого класса последовательностей - пространства

Несмотря на то, что пространство 12{Ъ+) позволяет рассматривать бесконечные сигналы, на практике встречаются только сигналы конечной длины. Поэтому отдельно рассматриваются последовательности и, у, й, г, все элементы которых, начиная с некоторого индекса М, равны нулю. Доказаны следующие две леммы.

Лемма 1. Пусть М € М, М < N = 2" и и,у,з,т таковы, что системы {Т2ки}к£%+и{Т2кУ}кег+ и {Т2кв}кех+и{Т2кт}кег+ являются биортогональными диадическими вейвлет-базисами первого этапа в пространстве 12(Х+). Положим

и(т) -- в(тп) — ь(тп) = т(тп) = 0 для всех т > М.

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

щдГ)(т) = и(т), т — 0,1,..., N — 1,

и аналогично определим последовательности и(л')> г(л')- Тогда множества {Т2кЩя)}к=о и и (Тг^лг)}^1 и {Т2ктт}^ являются биортогональными диадическими вейвлет-базисами первого этапа в пространстве 12{Ъц).

Лемма 2. Пусть пеМ,Л, = 2"ии,»,8,т таковы, что множества {Т^и}^'^ и {Т2кУ}^01 и {ТЪя}^1 и {Т2кт)к=о являются биортогональными диадическими вейвлет-базисами первого этапа в пространстве 12{Ъц). Определим последовательность и^) равенствами

и аналогично определим последовательности г'(^), т^. Кроме того, положим

М(лт)(пг) = = — т(ло(т) = О для всех т> N.

Тогда системы }7.^. и и и {^2

являются биортогональными диадическими вейвлет-базисами первого этапа в пространстве 12{Ъ+).

Эти две леммы показывают, что последовательности вейвлет-фильтров с конечным количеством ненулевых элементов могут порождать как базисы в пространстве 12(Х®), так и базисы в пространстве 12{Ъ+).

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

«(дг)(т) = и(т), т = 0,1,..., N — 1,

(13)

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

1) представление входного изображения в виде массива его вейвлет-коэф-фициентов;

2) квантование вейвлет-коэффициентов;

3) восстановление изображения и подсчет величины РЭИЕ;

4) замена параметров для достижения наилучшего значения РБКП.

При проведении численных экспериментов на этапе квантования использовались два метода:

1) аналогично подходу из книги Уэлстида выбиралось заданное количество наибольших по модулю вейвлет-коэффициентов (10%, 5% и 1%), остальные коэффициенты полагались равными нулю (метод А);

2) к вейвлет-коэффициентам применялось равномерное квантование с мертвой зоной в окрестности нуля (этот метод квантования используется в стандарте ЛРЕС2000). В этом случае каждый вейвлет-коэффициент ё(х, у) квантуется по формуле

\<1(*,У)\

(1{X, у) = sign{¿{х, у))

Д, (14)

Д

где - целая часть числа, а Д - шаг квантования(метод В).

На этапе замены параметров вейвлета использовался рекурсивный генетический алгоритм, в котором целевой функцией являлась величина РЭКИ.

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

13

диадических вейвлетов сравнивались с результатами классических вейвле-тов Хаара, Добеши и биортогональных вейвлетов 9/7. В приведенных ниже таблицах семейство диадических вейвлетов из примера 1 обозначено Б1ас12. При квантовании методом А наилучшие результаты полученные с помощью диадических вейвлетов совпали с соответствующими результатами с использованием вейвлета Хаара. Результаты кодирования изображений с использованием квантования методом В приведены в таблицах 1 и 2.

Таблица 1. Значения PSNR для кодирования изображений с использованием равномерного квантования при Д = 25

Xaap Добеши 2 Добеши 3 9/7 Diad2

lena 30,269 30,7794 30,895 30,8476 32,1969

winter 27,9076 27,4528 27,4491 27,3506 28,0635

rose 30,0886 30,7862 30,848 30,7404 32,722

bridge 27,6703 27,8367 27,9107 27,8176 29,2073

bird 33,6583 34,1995 34,1716 34,1706 37,0073

goldhill 28,9705 29,0937 29,0987 29,0128 30,8039

rentgen 33,4646 34,7148 34,8296 34,6202 37,4696

Из таблиц 1 и 2 видно, что для рассматриваемых изображений диадиче-ские вейвлеты имеют преимущество по сравнению с вейвлетами Хаара, Добеши и 9/7.

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

A.A. Любушиным предложен следующий алгоритм оценки гладкости низкочастотных микросейсмических колебаний.

Таблица 2. Значения PSNR для кодирования изображений с использованием равномерного квантования при Д — 50

Xaap Добеши 2 Добеши 3 9/7 Diad2

lena 26,5705 26,9963 27,1921 27,0934 29,7269

winter 23,6092 23,5419 23,5522 23,4673 25,3426

rose 26,3883 27,0317 27,1635 27,1866 30,0729

bridge 24,079 24,2955 24,3748 24,3238 26,7547

bird 30,2007 30,5725 30,5684 30,6482 34,8034

goldhill 25,7242 25,9855 25,9216 25,9409 28,6729

rentgen 30,059 31,108 31,2156 31,1372 35,4092

1. Выбирается некоторое множество вейвлет-базисов.

2. Из сигнала производится удаление тренда локальными полиномами восьмого порядка.

3. Для каждого вейвлет-базиса из выбранного множества

- вычисляется дискретное вейвлет-преобразование сигнала;

- по формуле

Е=-^Р] V], Рз = 5 = X)

3 3

где й, - вейвлет-коэффициенты сигнала, вычисляется энтропия квадратов вейвлет-коэффициентов.

4. В качестве показателя гладкости сигнала выбирается показатель гладкости вейвлета с наименьшим значением энтропии.

A.A. Любушин использовал в своих работах вейвлеты Добеши порядков 1-10 и симлеты, порядков 4-10 (под порядком понимается число обнуляемых моментов у материнской функции). В качестве показателя гладкости для этих вейвлетов был выбран порядок вейвлета. A.A. Любушиным было показано, свойство гладкости волновых форм сейсмического шума отражает подготовку сильного землетрясения, а именно, задолго перед сейсмической катастрофой 11 марта 2011 г. в Японии среднее число обнуляемых моментов сейсмического шума на станциях сети F-net, после устранения трендов, обусловленных приливами, существенно возросло, то есть шум стал более гладким.

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

X<a\t) + a[o)X<a>(f - 1) + <4a)X{a)(t - 2) = £(a)(i), (15)

где X^(t) - колебание блока; а = 1 ,...,т- индекс, нумерующий различные малые блоки земной коры, общим числом ш; i £ Z - целочисленный временной индекс, нумерующий последовательные отсчеты; ^(t) - случайный процесс, накачивающий энергией блок с номером а ; (а^а^) - параметры блока (коэффициенты авторегрессии), задающие передаточные и резонансные свойства блока. Под случайными процессами ^'"'(i) будем понимать последовательности независимых случайных величин с нулевым средним и с одинаковой дисперсией а2 , распределенных по Гауссу с плотностью вероятности е~х*/(о \/2ir), иными словами, независимые гауссовские белые шумы. Процесс консолидации малых блоков моделируется резким уменьшением стандартного отклонения <5 разброса параметров (af\ а^1) около среднего вектора (а'"' = 0, а^ = 0.5), что эквивалентно более равномерному распределению свойств земной коры внутри большого консолидированного блока,

16

образующегося из большого числа малых блоков.

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

Рис. 1. Показатель гладкости шума для ортогональных вейвлетов Добеши (число обнуляемых моментов). Сплошная линия - среднее значение для положения правого конца скользящего окна < 20000. Пунктирная линия - среднее значение для положения правого конца скользщего окна > 22000

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

1 + а + Ь+ с + а + Р + 7 и(1) = 1 + а + Ь+ с — а — Р — 7

4V2 4\/2

1 + а — Ь — с+ а— /3 — 7 «(3) = l + a — Ь — с — а + Р + у

4^2

1— а + Ь — с — а + Р — 7 и(5) = 1— а+6 — с + а — Р + у

4л/2 4а/2

1 — а — Ь+ с— а — Р + 7 «(7) = 1— а — b+ с+ а + Р — 7

4V2 4у/2

где а, 6, с, а, Р,7 е С : |а|2 + |а|2 = |6|2 + \р\2 = |с|2 + |7|2 = 1, а, 7 ф 0. Построение и оценки гладкости этих диадических вейвлетов представлены соответственно в работе Е.А. Родионова и Ю.А. Фаркова, опубликованной в "Математических заметках"в 2009 г.

Вычислительные эксперименты проводились с использованием данных сети F-net за период с начала 1997 года, по июль 2011 года. На рисунке 2 представлены графики изменения показателя гладкости по всем станциям сети F-net, дополнительно сглаженные во временном окне длиной 30 суток. Видна основная деталь поведения всех показателей гладкости шума: во временном интервале с начала 2002 до 2004 гг. произошло плавное повышение гладкости, причем средний уровень параметров гладкости оставался высоким вплоть до землетрясения 11.03.2001. После сейсмической катастрофы показатели гладкости на графиках (а) и (б) резко упали и, таким образом, параметры гладкости волновых форм низкочастотных микросейсм в формах Добеши и диадических вейвлетов обладают прогностическими свойствами, что делает их перспективным в использовании в прогностических системах мониторинга.

а

б

6

4

б

1.8

1.6

1.4

1.2

1

0.8

1997 1999 2001 2003 2005 2007 2009 2011 2013

Рис. 2. Графики различных показателей гладкости волновых форм микросейсмического шума, усредненные по всем станциям сети Р-пе1 и сглаженные по времени в окне длиной 30 суток: (а) - оценка с использованием вейвлетов Добеши и симлетов, (б) - оценка с использованием диадических вейвлетов

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

Основные результаты работы

1. Построены диадические ортогональные и биортогональные вейвлет-бази-сы в пространствах периодических и непериодических последовательностей. Приведено их полное описание.

2. Разработан алгоритм построения диадических вейвлет базисов с использованием стационарных и нестационарных систем вейвлет-фильтров.

3. Разработаны алгоритмы прямого и обратного дискретных диадических вейвлет-преобразований на основе быстрого преобразования Уолша. Получены оценки быстродействия этих алгоритмов.

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

5. Показано, что в задачах кодирования изображений, диадические вейвле-ты не уступают, а зачастую превосходят классические вейвлеты Хаара и Добеши, а также биортогональный базис 9/7.

6. Показано, что диадические вейвлеты обладают прогностическими свойствами при оценке гладкости низкочастотных микросейсмических колебаний.

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

Список публикаций в изданиях, рекомендованных ВАК

1. Строганов С. А. Оценка гладкости низкочастотных микросейсмических колебаний при помощи диадических вейвлетов. // Геофизические исследования. 2012. Т. 13, № 1. С. 60-65.

2. Фарков Ю.А., Строганов С.А. О дискретных диадических вейвлетах для обработки изображений. // Известия вузов. Математика. 2011. № 7. С. 57-66.

3. Farkov Yu.A., Maksimov-A.Yu., Stroganov S.A. On biorthogonal wavelets related to the Walsh functions. // International Journal of Wavelets, Multiresolution and Information Processing. 2011. Vol. 9, по. 3. P. 485-499.

Список публикаций в сборниках трудов научных конференций

4. Максимов А.Ю., Строганов С.А. О применении диадических вейвлетов для сжатия изображений // Современные проблемы теории функций и их приложения: Тез. докл. 14-й Саратов, зимн. шк., поев, памяти акад. П.Л. Ульянова. Саратов: Изд-во Саратов, ун-та, 2008. С. 108-109.

5. Строганов С.А. О дискретных диадических вейвлетах их применении для обработки изображений. // XVIII Международная конференция "Математика. Экономика. Образование."VI Международный симпозиум "Ряды Фурье и их приложения."Междисциплинарный семинар "Информационно-коммуникационные технологии."Труды. Ростов н/Д: Изд-во ЮФУ, 2010. С. 4-8.

6. Строганов С.А. О дискретных диадических вейвлет-преобразованиях // X международная конференция «Новые идеи в науках о Земле», Москва, РГГРУ, 12-15 апреля 2011. Доклады. Том 3. М: Экстра-принт, 2011. С. 208.

7. Строганов С.А. О применении диадических биортогональных дискретных всплесков для обработки изображений // Методы сплайн-функций. Российская конференция, посвящённая 80-летию со дня рождения Ю.С. За-

вьялова (Новосибирск, 31 января - 2 февраля 2011 г.): Тез. докладов. Новосибирск: ИМ СО РАН, 2011.

8. Строганов С.А., Фарков Ю.А. О диадических фреймах, определяемых по вейвлетам на полупрямой. //IX Международная конференция «Новые идеи в науках о Земле». Москва, РГГРУ, 14-17 апреля 2009 года. Доклады. Том 3. М: РГГРУ, 2008.

Подписано в печать: 11.04.2012 Объем: 1,0 усл. п.л. Тираж: 100 экз. Заказ № 102 Отпечатано в типографии «Реглет» 119526, г. Москва, Страстной бульвар, д. 6, стр. 1 (495) 978-43-34; www.reglet.ru

61 12-1/815

ФГБОУ ВПО Российский государственный геологоразведочный университет им. Серго Орджоникидзе

На правах рукописи

Строганов Сергей Александрович

Применение диадических вейвлетов для цифровой обработки сигналов

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. ф.-м. н.

Любушин Алексей Александрович

Научный консультант к. ф.-м. н.

Фарков Юрий Анатольевич

Москва - 2012

Содержание

Введение ......................................................................4

Глава 1. Диадические вейвлеты в пространстве .....18

1.1. Основные определения.......................18

1.2. Диадические вейвлеты первого этапа в ..........23

1.3. Итерационные вейвлеты в .................32

1.4. Примеры...............................46

1.5. Выводы................................49

Глава 2. Диадичеакие вейвлеты в пространстве 12{Ъ+)......50

2.1. Основные определения.......................50

2.2. Диадические вейвлеты первого этапа в ¿2(2,+)..........56

2.3. Итерационные вейвлеты в 12(.................63

2.4. Примеры...............................70

2.5. Выводы................................71

Глава 3. Применение диадических вейвлетов к цифровой обработке сигналов..............................72

3.1. Применение диадических вейвлетов для кодирования изображений .................................73

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

3.3. Применение диадических вейвлетов к оценке гладкости микросейсмического шума.........................85

3.4. Выводы . ...............................89

Заключение..................................91

Литература..................................92

Приложение А. Примеры изображений...............98

А.1. Тестовые изображения.......................98

А.2. Примеры восстановленных изображений.............99

Приложение Б. Тексты программ ..................104

Б.1. Прямое дискретное диадическое вейвлет-преобразование одномерного сигнала ........................... 104

Б.2. Обратное дискретное диадическое вейвлет-преобразование одномерного сигнала..........................105

Б.З. Прямое пирамидальное дискретное диадическое вейвлет-пре-

образование двумерного сигнала..................106

Б.4. Обратное пирамидальное дискретное диадическое вейвлет-преобразование двумерного сигнала..................108

Введение

В последнее время активно развиваются различные методы цифровой обработки сигналов. В России и за рубежом к настоящему времени опубликовано большое количество работ, посвященных цифровой обработке сигналов, в том числе монографии Э. Айфичера и Б. Джервиса [1], Р. Гонсалеса и Р. Вудса [5], С. Малла [13], Г. Штарка [32], а также под редакциями A.A. Потапова [15] и В.А. Сойфера [14]. В частности, широкое распространение и развитие получили методы, основанные на использовании вейвлетов. В некоторых работах на русском языке вейвлеты называют всплесками. Одной из первых задач, в которой вейвлеты продемонстрировали свои преимущества, стала задача хранения дактилоскопических изображений. В США разработан и активно применяется национальный стандарт сжатия дактилоскопических изображений, основанный на применении биортогональных вейвлетов [33]. Этот стандарт позволяет достигать коэффициента сжатия 1:15. Для широкого класса изображений, в том числе для фотографий, методы цифровой обработки, основанные на использовании вейвлетов, показывают лучшие результаты, чем другие методы обработки изображений (см. [5, 13, 27, 32]). В стандарте JPEG2000 для решения задач кодирования и сжатия изображений используется вейвлет-преобразование. В книгах М. Фрейзера [31] и S. А. Broughton, K.M. Bryan [34] в задачах фильтрации сигналов, а также для решения дифференциальных уравнений используются вейвлеты Хаара и Добеши [6, 16]. Применимые в диссертации методы используют элементы общей теории дискретных преобразований Уолша и связаны с недавними результатами Б. Сендова (В. Sendov) [43-45], В. Лэнга (W.C. Lang) [41], В.Ю. Протасова [17], Ю.А. Фаркова [28, 29, 35, 36] и Ф. Шаха (F.A.Shah) [46, 47] о вейвлетах, определяемых с помощью функций Уолша. Одной из центральных проблем

при использовании вейвлетов для цифровой обработки сигналов является выбор вейвлета. Например, в [13] изложен метод выбора оптимального вей-влет-базиса для нелинейной аппроксимации сигнала, а в работе A.A. Любу-шина [9] выбор оптимального вейвлет-базиса позволяет оценивать гладкость низкочастотных микросейсмических колебаний. Таким образом, построение новых вейвлет-базисов и расширение возможностей их адаптации к анализу и обработке сигналов являются актуальными научными задачами.

Целью настоящей работы является:

1. Построение ортогональных и биортогональных диадических вейвлет-базисов в пространствах периодических и непериодических последовательностей.

2. Разработка алгоритма дискретного диадического вейвлет-преобразова-ния.

3. Применение диадических вейлветов для оценки гладкости шума в модели малых блоков земной коры.

4. Применение диадических вейвлетов в задачах цифровой обработки изображений.

Основные результаты работы:

1. Построены ортогональные и биортогональные диадические вейвлет-бази-сы в пространствах последовательностей и приведено их полное описание.

2. Исследованы системы диадических вейвлет-фильтров, разработан алгоритм построения многоэтапных биортогональных диадических вейвлет-базисов на основе систем вейвлет-фильтров.

3. Разработан алгоритм дискретного диадического вейвлет-преобразова-ния на основе быстрого преобразования Уолша.

4. Приведены примеры применения диадических вейвлетов в задачах кодирования изображений, а также для оценки гладкости низкочастотных микросейсмических колебаний.

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

1. Кодирование и сжатие данных, в частности фотографий и рентгеновских снимков.

2. Оценка гладкости низкочастотных микросейсмических колебаний и использование полученных данных в системах мониторинга.

Диссертация состоит из введения, трех глав, заключения и библиографии. Общий объем диссертации 110 страниц, включая 11 рисунков, 8 таблиц и два приложения. Библиография включает 48 наименований на 6 страницах.

В первой главе рассматриваются биортогональные диадические вей-влеты в пространстве периодических последовательностей ^{Ъы)- Пространство состоит из комплексных последовательностей

х = (..., х(-1), я:(0), ®(1), ж(2),...)

таких, что х^ + N) — х{у) для всех ] б Ъ. Для удобства изложения определены также числа Ыи = Ы/2й, 1 < и < п.

Двоичная свертка векторов х и у из /2(Ждг) определяется по формуле

N-1

(х * у){1) := ^ х{1 0 I е ZN,

з=о

где © - операция поразрядного сложения по модулю 2.

Для каждого х € /2(^дг) определяется оператор сдвига Тк : —

12{Ъм) такой, что (Ткх){1) :=х(1фк), I е Ъ^. Для любых х, у € 12{Zдr), к,1 £ Ън доказываются равенства:

(Ткх,Т1у) = {х,Тшу), (х,Тку) = х * у (Л),

где - система функций Уолша, ах- дискретное преобразование Уолша последовательности гг. По формуле

ленные по формуле (1.12) образуют пару биортогональных базисов в 12(Ж*м), то эти множества называются биорто г опальными диадическими вейвлет-

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

Теорема 1.2.1. Пусть и,у,в,т £ Системы В (и, у) и В(з,т) явля-

ются биорто зональными диадическими вейвлет-базисами в 12{Ъ^) тогда и только тогда, когда

хТу = Иху, (х,у) = М(х,у), Ткх{1) = и)к{1/Ы)х,

базисами первого этапа в 12{^/у). Последовательности и,у,з,т называются

для всех I = 0,1,..., — 1.

Затем показывается, что для построения вейвлет-базисов первого этапа необязательно задавать четыре последовательности, удовлетворяющих условиям этой теоремы. Можно выбрать последовательности и, б € 12(^дг), которые удовлетворяют условию

ЩЩ + и{1 + И^ЩТЩ = 2/И2, (3)

для любого I = 0,1,..., — 1, а последовательности у,т Е 12{Ъдг) задать равенствами

у{1) = (-1)г5(1©0> т{1) = (-1)^(1 ©/), 1еъм. (4)

Доказано, что в этом случае множества В(и, у) и В(в, т) являются биортого-нальными диадическими вейвлет-базисами в /2(Ждг). На основе этого утверждения формулируется следующий метод построения вейвлет-базиса первого этапа:

1) выбираются последовательности и, в Е ¿2(^дг) так, чтобы они удовлетворяли условиям (3);

2) по формуле (4) определяются последовательности у,т Е 12{Ъдг).

Получившиеся в итоге последовательности и, 5, г>, т удовлетворяют условиям теоремы 1.2.1 и порождают пару биортогональных диадических вейвлет-базисов первого этапа в 12{Ъ^).

Далее рассматривается разложение вектора х Е 12{1>дг) по базисам В(и, у) и £>(з,т). Для вычисления координат вектора х в этих базисах путем умножения х на матрицу перехода требуется ./V2 комплексных умножений. Чтобы быстро вычислить координаты вектора х в базисе В(и,у) (или В(з,т)) требуется использовать тот факт, что (^Т^и) = х*й(2к) и аналогично для у. В итоге вектор х в базисе В(и, у) можно представить в виде двух сверток с последующим отбрасыванием координат с нечетными индексами. Для описания

быстрого перехода от евклидового стандартного базиса к вейвлет-базису и обратно, для 0 < v < п вводятся следующие операторы: Dv : 12{Ъ^) —> ¿2(Z/v„) и Uv : 12{ZNv) —> l2{Zjv), определяемые по формулам

D"(x)(j)=x(2»j),

y(j/2v), если j делится на 21/,

^(î/)C7')=<

I 0, если j не делится на 2",

где х g /2(Zjv), у g 12(Znu), j? = 0,1,.. ., tv — 1. Эти операторы называются операторами сгущающей и разрежающей выборки соответственно.

Разложение вектора х g 12{^n) по базисам B(u,v) и B(s,t) происходит по формулам

Ni~l Ni-1

x=Y, * u)(k))T2ku + J2 (D(x * v)(k))T2kv (5).

k=0 k=0

и

Ni — 1 iVi-1

® = № * s)(k))T2ks + ^ (£>(* * r){k))T2kt. (6)

k=Q k=0

Формулы (5), (6) называются формулами анализа первого этапа. Восстановление вектора х происходит по формулам синтеза первого этапа:

т * U(D(x * v)) + s * U(D(x * и)) — x

и

v * U(D(x * г)) + й * U(D(x * s)) = ж.

Затем для некоторого натурального m < п рассматривается система В(ср,ф), определяемая по формуле

{адлйо1 U {^^jSo1 U • • • U {Т*»кФт№О1 U (7)

где Ф1, ф2, ■ ■ ■ ? Фт, Рт ^ ¿2(Z?v), и система определяемая аналогично

по векторам ^ ф2,..., фт, (рт g /2(zjv). Если системы В((р,ф) и В((р,ф)

9

образуют пару биортогональных базисов в тогда они называются

т-этапными биортогоналъными диадическими вейвлет-базисами в пространстве 12{ЪЫ).

Доказывается, что для построения подобных вейвлет-базисов нужно выбрать т-этапную последовательность диадичесикх биортогональных вейвлет-фильтров и\, 51, VI, гьи2, 52, т2,... ,ит, 5т, ит, тто, таких, ЧТО и„,Уу, ву.Ту 6 для любого V = 1, 2,..., га и любого I = 0,1,..., Л^ выполнено равенство

ии{1) и„{1 + К)

%{1) зд + лд

( Ш Ш \ 2/10,

•

С П I ЛГ \ О П I ЛГ ^ / /V" 1 П 1 I

\

%{1 + лд т„(/ + Иу) ) М1-1 \ О 1

Если положить = щ, (р = 51, ф\ = ф — т\ и определить (ри, (ри, фу, фь для V = 2,..., га по формулам

^ = 1 * и" (и„), фи = (ру-1 * г/" (9)

и

- * ^1(51/), ^ = * (10)

то последовательности <р„, фу, фу порождают га-этапный вейвлет-базис с пространстве 12(Ъ^). Соответственно, задача построения диадических многоэтапных базисов сводится к выбору последовательности вейвлет-фильтров. Кроме того, доказано, что последовательность вейвлет-фильтров может быть построена с использованием порождающих последовательностей вейвлет-бази-са первого этапа. Такие последовательности фильтров называют стационарными.

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

Во второй главе рассматриваются диадические вейвлеты в пространстве непериодических последовательностей 12{Ъ+). Процесс построения диа-дических вейвлетов в этом пространстве в целом аналогичен подходу, изложенному в главе 1. Основное отличие заключается в том, что пространство +) является бесконечномерным, поэтому дополнительно требуется доказывать полноту полученных вейвлет-систем.

Еще одним отличием является тот факт, что свертка двух последовательностей из пространства не всегда принадлежит этому пространству, поэтому при построении диадических вейвлет-систем порождающие последовательности приходится выбирать из более узкого класса последовательностей - пространства 11('Ж+).

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

Лемма 2.4.1. Пусть М Е Щ, М < N = 2п и и, у, в^т таковы, что системы {Т2ки}кеъ+^{Т2к^}ке1+ и {Т^й^^и^^т}^^ являются биорто г опальными диадическими вейвлет-базисами первого этапа в пространстве 12(Ъ+). Положим

и(т) = й(ш) = у(т) — т(т) = 0 для всех т > М.

Определим последовательность и^щ равенствами

и{Ы){т) — и(т), т ~ 0,1,..., N — 1, (11)

и аналогично определим последовательности з^уу^ут^у Тогда множества {Т2кЩм)}£01 и {Т2ку(М)}к=0 и {т2к8(м)}к=о и {т2кЦм)}к=о являются

биортогоналъными диадическими вейвлет-базисами первого этапа в пространстве 12{Ъц).

Лемма 2.4.2. Пусть п 6 М, Я = 2п и и,у,в,т таковы, что множества {Т2ки}к^ и {Т2ки}^ и {Т2кв}^ и {Т2кт}^ являются биортогоналъными диадическими вейвлет-базисами первого этапа в пространстве 12{Ъц). Определим последовательность и^ равенствами

= и(т), га = 0,1,..., ЛГ — 1, (12)

и аналогично определим последовательности «(дг), ^(дг)) г(ло- Положим

щы){т) = 5(дг)(т) = = т^){т) — О для всех га > N.

Тогда множества {Т2ки^)}к^+^{Т2кУ{щ}кеЪ+ и {Т2кЗ(М)}к^+и{Т2кцМ)}ке%+ являются биортогоналъными диадическими вейвлет-базисами первого этапа в пространстве 12{Ъ+).

Эти две леммы показывают, что последовательности вейвлет-фильтров с конечным количеством ненулевых элементов могут порождать как базисы в пространстве 12(йр}), так и базисы в пространстве ¿2(Z+).

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

1) представление входного изображения в виде массива его вейвлет-коэф-фициентов;

2) квантование вейвлет-коэффициентов;

3) восстановление изображения и подсчет величины РЭМИ,;

4) замена параметров для достижения наилучшего значения PSNR.

При проведении численных экспериментов на этапе квантования использовались два метода:

1) аналогично подходу из книги Э. Уэлстида [27] выбиралось заданное количество наибольших по модулю вейвлет-коэффициентов (10%, 5% и 1%), остальные коэффициенты полагались равными нулю (метод А);

2) к вейвлет-коэффициентам применялось равномерное квантование с мертвой зоной в окрестности нуля (этот метод квантования используется в стандарте ЛРЕС2000 [40]). В этом случае каждый вейвлет-коэффициент ¿(х, у) квантуется по формуле

d(x,y) = sign (d(x,y))

А, (13)

А

где J - целая часть числа, а А - шаг квантования (метод В).

На этапе замены параметров вейвлета использовался рекурсивный генетический алгоритм [3], в котором целевой функцией являлась величина PSNR.

Эксперименты проводились на наборе тестовых изображений в градациях серого, размером 256 на 256 точек. Результаты, полученные для семейств диадических вейвлетов сравнивались с результатами классических вейвлетов Хаара, Добеши и биортогональных вейвлетов 9/7. Результаты кодирования изображений с использованием квантования из стандарта JPEG 2000 приведены в таблицах 3.1 - 3.6. Из этих таблиц видно, что при использовании метода кодирования из стандарта JPEG2000 для рассматриваемых изображений диадические вейвлеты имеют преимущество по сравнению с вейвлетами Хаара, Добеши и 9/7.

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

В работе [9] предложен следующий алгоритм оценки гладкости низкочастотных микросейсмических колебаний.

1. Выбирается некоторое множество вейвлет-базисов.

2. Из сигнала производится удаление тренда локальными полиномами восьмого порядка.

3. Для каждого вейвлет-базиса из выбранного множества

- вычисляется дискретное вейвлет-преобразование сигнала;

- по формуле

Е = - Y^Рз 1о§2Pj, Pj = d)/S, S = £4 j j

где dj - вейвлет-коэффициенты сигнала, вычисляется энтропия квадратов вейвлет-коэффициентов.

4. В качестве показателя гладкости сигнала выбирается показатель гладкости вейвлета с наименьшим значением энтропии.

A.A. Любушин использовал в своих работах вейвлеты Добеши порядков 1-10 и симлеты, порядков 4-10 (под порядком понимается число обнуляемых моментов у материнской функции). В качестве показателя гладкости для этих вейвлетов был выбран порядок вейвлета. A.A. Любушиным было показано, свойство гладкости волновых форм сейсмического шума отражает подготовку сильного землетрясения, а именно, задолго перед сейсмической катастрофой 11 марта 2011 г. в Японии среднее число обнуляемых моментов сейсмического шума на станциях сети F-net, после устранения трендов,

обусловленных приливами, существенно возросло, то есть шум стал более гладким [11].

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