На правах рукописи
Елистратов Николай Александрович
РЕШЕНИЕ ОБРАТНОЙ ПРОБЛЕМЫ
N-МЕРНЫХ АФФИННЫХ САМОПОДОБНЫХ ФУНКЦИЙ
МЕТОДОМ ГОЛОСОВАНИЯ ДЛЯ ВСПЛЕСК-МАКСИМУМОВ
Специальность 05.13.18 - «Математическое моделирование, численные
методы и комплексы программ»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Москва - 2011 г.
Работа выполнена в ФГБОУ ВПО Московском государственном технологическом университете «СТАНКИН».
Научный руководитель: доктор физико-математических наук, профессор Холщевникова Наталья Николаевна
Официальные оппоненты: доктор физико-математических наук, профессор Латышев Анатолий Васильевич кандидат физико-математических наук Галатенко Владимир Владимирович Ведущее предприятие: ГОУ ВПО Российский государственный геологоразведочный университет имени Серго Орджоникидзе
Защита состоится «13» декабря 2011 г. в 12 часов на заседании диссертационного совета Д 212.142.03 при ФГБОУ ВПО Московском государственном технологическом университете «СТАНКИН» по адресу:
127055, Москва, Вадковский переулок, д. 3а.
С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО Московского государственного технологического университета «СТАНКИН».
Автореферат разослан «11» ноября 2011 г.
Ученый секретарь диссертационного совета, к.т.н., доц. Семячкова Е.Г.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы В настоящее время значительный интерес для таких областей как компьютерная графика, распознавание образов, обработка и сжатие изображений, теория динамических систем, геофизика, всплеск-анализ, психология и многих других представляет изучение фрактальных объектов.
Модели самоподобных детерминированных и случайных фракталов успешно применяются при описании изображений природных объектов.
Изучение моделей хаотической динамики, таких как DLA (diffusion limited aggregation, модели роста, ограниченного диффузией) и странных аттракторов, показывает, что они также обладают свойствами самоподобия. В теории всплесков самоподобные фракталы применяются для построения кратномасштабных анализов (КМА).
В настоящей работе проведено исследование класса многомерных самоподобных фракталов – аффинных самоподобных функций, описываемых функциональными уравнениями с уточняющим оператором. Уточняющий оператор представляет собой сумму аффинных функциональных операторов.
В частности, масштабирующие функции КМА являются примерами аффинных самоподобных функций. Аттракторы IFS (Iterated Function Systems, системы итерируемых функций) можно описать с помощью их характеристических функций, которые также являются аффинными самоподобными.
При изучении самоподобных фракталов мощные средства предоставляет непрерывный всплеск-анализ. В работе используется непрерывное всплескпреобразование, ассоциированное с группой подобий евклидова пространства, и вводится его обобщение.
Важным свойством самоподобных фракталов является то, что довольно сложные структуры, имеющие фрактальную природу, можно описать с помощью небольшого набора параметров. Генерирование самоподобных фракталов является довольно простой задачей, нашедшей применение при получении изображений природных ландшафтов и текстур в компьютерной графике. В то время как численный анализ свойств самоподобия сигналов является более сложной обратной задачей. Зная параметры самоподобия, можно эффективно кодировать видео и изображения. Не менее важным является получение фрактальных характеристик при изучении физических явлений, например, таких как землетрясения. В одномерном случае известно решение обратной задачи методом моментов, для решения такой задачи в двумерном случае применяют геометрические методы, метод моментов и всплесканализ. Решение двумерной задачи получено для довольно узкого класса фракталов. Значительный интерес представляет данная задача в многомерном случае для аффинных самоподобных функций.
Таким образом, актуальной научной проблемой диссертационного исследования является разработка новых методов получения фрактальных характеристик многомерных аффинных самоподобных функций.
Целью настоящей работы является разработка методов численного решения обратной задачи для многомерных аффинных самоподобных функций с использованием всплеск-анализа.
Научная новизна 1. Для анализа многомерных аффинных самоподобных функций предложено обобщение непрерывного всплеск-преобразования, обладающее свойствами самоподобия в отношении таких функций.
2. Разработан метод численного решения обратной задачи для многомерных аффинных самоподобных функций, особенностью которого является вычислительная устойчивость и подавление шумовой составляющей сигнала.
3. Разработан алгоритм вычисления обобщенного непрерывного всплескпреобразования, вычислительная сложность которого ниже по сравнению с прямым методом за счет использования быстрого преобразования Фурье.
4. Доказано утверждение о распространении до самых малых масштабов линий всплеск-максимумов обобщенного непрерывного всплескпреобразования с всплесками Гаусса, что позволяет повысить устойчивость разработанного метода к численным погрешностям всплескпреобразования в тех областях, где оно близко к нулю.
Практическая ценность. Разработан комплекс программ, реализующих вычисление обобщенного всплеск-преобразования, объединение точек всплеск-максимумов в кривые и восстановление параметров двумерных аффинных самоподобных функций. Разработанные методы, вычислительные алгоритмы и комплексы программ могут быть использованы при решении следующих задач:
1. Анализ и сжатие изображений, содержащих самоподобные фракталы, при этом теоретически достижимо весьма эффективное сжатие за счет того, что аффинные самоподобные функции описываются при помощи относительно небольшого набора параметров.
2. Распознавание образов объектов, обладающих свойствами аффинного самоподобия.
3. Анализ объектов, описываемых моделями хаотической динамики в молекулярной физике, геофизике и метеорологии.
Установленное свойство обобщенного непрерывного всплескпреобразования о распространении его всплеск-максимумов до самых малых масштабов является важной характеристикой, позволяющей разрабатывать новые методы анализа многомерных сигналов, такие как локализация особенностей и оценка спектра.
Методы исследования. В работе применяются методы функционального анализа, методы теории интегральных и дискретных преобразований, таких как преобразование Фурье и всплеск-преобразование, методы теории самоподобных фракталов Хатчинсона, теории всплесков, теории матриц, методы теории компьютерного зрения. Разработка программного обеспечения проводилась в среде MATLAB.
Апробация результатов. Представленные в работе результаты докладывались и обсуждались на следующих конференциях и семинарах:
1. Научный семинар по теории всплесков под руководством профессора Н.Н. Холщевниковой кафедры «Математика» МГТУ «Станкин» (г. Москва, 2008 г.);
2. XI научная конференция МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» – ИММ РАН» по математическому моделированию и информатике (МГТУ «Станкин», г. Москва, 2008 г.);
3. I международная конференция «Моделирование нелинейных процессов и систем» (МГТУ «Станкин», г. Москва, 2008 г.);
4. IX международная конференция «Новые идеи в науках о земле» РГГРУ, (РГГРУ им. Серго Орджоникидзе, г. Москва, 2009 г.) 5. XIII научная конференция МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» – ИММ РАН» по математическому моделированию и информатике (МГТУ «Станкин», г. Москва, 2010 г.);
6. Семинар по теории ортогональных и тригонометрических рядов под руководством профессора М.К.Потапова, профессора В.А.Скворцова, профессора М.И.Дьяченко механико-математического факультета МГУ им. М.В.Ломоносова (г. Москва, декабрь 2010 г.);
7. X международная конференция «Новые идеи в науках о земле» РГГРУ, (РГГРУ им. Серго Орджоникидзе, г. Москва, 2011 г.) 8. XIV научная конференция МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» – ИММ РАН» по математическому моделированию и информатике (МГТУ «Станкин», г. Москва, 2011 г.);
9. II международная конференция «Моделирование нелинейных процессов и систем» (МГТУ «Станкин», г. Москва, 2011 г.);
Публикации. Основные результаты работы опубликованы в 7 печатных работах, в числе которых 1 публикация в издании, рекомендованном ВАК, 5 - в сборниках трудов научных конференций и 1 - в периодическом издании.
Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы из 75 наименований. Общий объем диссертации – 120 страниц, включая 16 рисунков, 1 таблицу и 1 приложение.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулированы цели и задачи исследования, научная новизна и практическая ценность работы. Приведено описание структуры диссертации и краткое содержание работы.
В первой главе приводится постановка задачи. Рассматривается модель аффинных самоподобных функций – функций f : R n C, являющихся решениями уравнений вида где N 1, ri R n, pi R \ {0}, M i – действительная квадратная невырожденная матрица, для которой обратная матрица M i1 определяет сжимающий оператор в R n с евклидовой нормой.
Если решение f имеет компактный носитель supp ( f ) – замыкание множества x R n | f ( x ) 0, то supp ( f ) содержится в компактном множестве D, таком что где – аффинные отображения, соответствующие уравнению (1):
Ti ( x ) M i1 x ri. Такие множества D называются аффинными самоподобными. Если N 1, то D содержит только один элемент, являющийся неподвижной точкой T1, поэтому далее рассматриваются уравнения (1), где N 2.
Примеры рассматриваемых в работе множеств приведены на рис. 1,2.
Рассматриваются уравнения (1), для которых отображения Ti удовлетворяют условию открытого множества (open set condition, OSC): существует открытое множество O, такое что Ti (O) T j (O) при i j и Ti (O ) O для всех i. При этом если D имеет пустую внутренность, int( D), то дополнительно предполагается D O (рис. 2). Если же int(D), то предполагается, что мера Лебега пересечений Ti (D) T j ( D), i j, равна нулю (рис. 1).
Si g ( x ) pi | det M i | g ( M i ( x ri )), уравнения (1) оказываются локализованными:
Для одномерной аффинной самоподобной функции f : R C, удовлетворяющей уравнению (1), непрерывное всплеск-преобразование (НВП) с всплеск-функцией L2 (R) также представляет собой самоподобную структуру. В этом случае M i li R, li 1, ri R, и выполняется равенство где множества Bi (a ) зависят от множеств локализации Ti ( D) операторов Si.
На этом свойстве всплеск-преобразования основан подход Хвонга и Малла (Hwang, Mallat) численного восстановления параметров ( pi, li, ri ) одномерных самоподобных функций, использующий алгоритм голосования для всплеск-максимумов. Поставлена задача обобщения указанного подхода для x R n, n 2 с компактным носителем supp ( f ), являющейся решением некоторого уравнения вида (1), ставится вопрос численного восстановления параметров ( pi, M i, ri ) этого уравнения по значениям f ( x ) в узлах некоторой сетки.
Исследуются свойства многомерных аффинных самоподобных функций. Рассматриваются функции g : R n C, принадлежащие линейному пространству, замкнутому относительно линейных преобразований координат, т.е. если g ( x ), то g (M ( x r )). Вводятся понятия локального самоподобия и локального самоподобия на множестве. Функция g называется локально самоподобной относительно аффинного оператора S, Sg p | det M | g ( M ( x r )), если существует открытое множество E, такое Если пространство есть пространство эквивалентных относительно меры Лебега функций, то g 0 на E означает, что мера Лебега множества { x E | g ( x ) 0} отлична от нуля, а равенство (3) должно выполняться почти всюду на E.
Множество G называется максимальным открытым множеством локального самоподобия функции g относительно S, если G есть объединение всех таких открытых множеств E, для которых выполняется (3). При этом говорят, что g локально самоподобна относительно S на G.
Если int( D), то рассматривается пространство эквивалентных относительно меры Лебега функций.
Вводятся обозначения: пусть ( j1,, jk ) {1,, N }k – некоторый набор E j1 jk T j1 jk (E ). Далее доказывается следующее утверждение:
Пусть f есть решение с компактным носителем уравнения (1), K R n \ supp ( f ), тогда 1. f локально самоподобна относительно S j1 jk на int(O j1 jk K ) ;
2. f локально самоподобна относительно S 11 jk на 3. f локально самоподобна относительно S j1 jk S iim, k m, на Для других композиций прямых и обратных операторов Si функция f не является локально самоподобной.
Во второй главе рассмотрено непрерывное всплеск-преобразование функции f L2 ( R n ), ассоциированное с группой подобий n -мерного евклидова пространства (НВП с вращениями):
где L2 ( R n ) – всплеск-функция, a 0,U SOn, b R n, SOn – n -мерная группа матриц вращения, т.е. det U 1. Показано, что такое НВП обладает свойстом, аналогичным свойству (2) для n -мерных самоподобных функций (1), т.е. когда M i liVi, li 1, Vi SOn и отображения Ti являются преобразованиями подобия. Когда M i представляет собой матрицу общего вида, то такое НВП указанным свойством не обладает.
Данная проблема решается путем модификации преобразования (4).
При помощи полярного разложения всякую матрицу M, det M 0, можно представить в виде M lHV, где l 0, V SOn, H – симметрическая положительно определенная матрица, наибольшее собственное значение которой равно 1. Вводится обобщенное НВП:
так что если матрица M i имеет разложение M i li H iVi, то для преобразования (5) аффинной самоподобной функции с уравнением (1) верно где множества Bi (a) зависят от множеств локализации операторов Si. Таким образом, для обобщенного НВП (5) и преобразования с вращениями (4) характерно свойство, аналогичное свойству (2) одномерного НВП. Преобразование (4) есть частный случай (5) при H E, где E – единичная матрица.
Установленное свойство также характерно и для всплеск-максимумов соответствующих преобразований. Точкой всплеск-максимума преобразования W H f называется точка (a,U, b), являющаяся точкой строгого локального максимума функции |W H f (a,U, b) |, рассматриваемой как функция переменной b при фиксированных a, U. Значение W H f (a,U, b) в точке всплескмаксимума называется всплеск-максимумом преобразования W H f.
Если функция f локально самоподобна относительно оператора S на Q, Sf ( x ) p det M f (M ( x ri )), M lHV, то выполняется равенство где множества BQ (a) определяются множеством Q на каждом масштабе a.
При этом всплеск-максимумы и точки всплеск-максимумов W H f и Wf связаны определенными соотношениями:
1. Пусть (a1,U1, b1 ), b1 BQ (a) – точка всплеск-максимума Wf, тогда (a2,U 2, b2 ) (la1,VU1, M (b1 r )) – точка всплеск-максимума W H f, причем 2. Пусть (a1,U1, b1 1 ), b1 1 BQ (a) – ближайшая в евклидовой метрике | x1 x2 | к (a1,U1, b1 ) точка всплеск-максимума Wf, тогда существует ближайшая в метрике | H 1 ( x1 x2 ) | к (a2,U 2, b2 ) точка всплеск-максимума В третьей главе исследуется вопрос численной реализации обобщенного НВП. Получено представление численной версии НВП в виде дискретной свертки с параметрами. Эффективный алгоритм вычисления таких дискретных сверток получен с использованием быстрого преобразования Фурье.
Если объем выборки исследуемого сигнала f равен T n, то вычисление всплеск-преобразования на каждом масштабе по предложенному алгоритму требует O(T n log 2 T ) операций, в то время как прямой метод вычисления требует O(T 2n ) операций.
В качестве всплеск-функции выбирается всплеск Гаусса – частная производная многомерной функции Гаусса. Доказывается следующее утверждение:
са, где 0 – действительная положительно определенная матрица порядка n, x T означает транспонирование вектора-столбца x. Пусть всплеск-функция U U 0 SOn принадлежат кривым, сходящимся к точкам пространства (0,U 0, b).
Таким образом, для всплесков Гаусса всплеск-максимумы распространяются до самых малых масштабов a.
Доказанное утверждение обобщает результаты, принадлежащие Хюммелю, Юию и Поджио (Hummel, Yuille, Poggio). Доказательство основано на применении метода Фурье и на принципе максимума для уравнения теплопроводности.
На рис. 3 изображены линии всплеск-максимумов преобразования Wf (a,U / 3, b) характеристической функции множества «двойной дракон»
(рис. 1), где U / 3 - матрица поворота на угол / 3. Преобразование вычислено с двумерным всплеском «мексиканская шляпа»
Рис. 3. Линии всплеск-максимумов характе- Рис. 4: Двумерный всплеск «мексиканская Применение доказанного свойства всплеск-максимумов для всплесков Гаусса состоит в том, что при вычислении дискретной версии всплескпреобразования могут возникнуть численные погрешности в тех областях, где всплеск-преобразование близко к нулю. За счет объединения точек всплеск-максимумов в кривые возможно удалить ложные всплескмаксимумы, возникающие в результате таких численных погрешностей.
Далее проводится обобщение одномерного подхода Хвонга и Малла, предлагается алгоритм с голосованием для всплеск-максимумов в пространстве параметров ( p, M, r ) аффинной самоподобной функции f. В алгоритме используется подобие Wf и W H f, и установленные соотношения (6), (7), связывающие всплеск-максимумы. Приводится обоснование алгоритма, основанное на описании всех возможных аффинных операторов, относительно которых аффинная самоподобная функция локально самоподобна (утверждение в первой главе).
Для двумерного случая разработан комплекс программ для среды MATLAB, реализующих вычисление дискретной версии обобщенного всплеск-преобразования с всплесками Гаусса, объединение точек всплескмаксимумов в кривые и восстановление параметров аффинных самоподобных функций по предложенному алгоритму с голосованием.
Рис. 5: Распределения голосов в пространстве неизвестных параметров. Пики голосов соответствуют параметрам уравнения Работоспособность алгоритма исследуется на ряде модельных примеров аффинных самоподобных функций. В частности рассматриваются характеристические функции аффинных самоподобных множеств. На рис. 5 приведена визуализация результатов работы программного комплекса для характеристической функции множества «двойной дракон» (рис. 1). Пики голосов соответствуют параметрам ( pi, M i, ri ) уравнения аффинной самоподобной функции.
Для получения исходных данных используются алгоритмы генерирования самоподобных фракталов, такие как алгоритм случайной итерации.
Рис. 6: Множество «тройной Исследуется возможность восстановления параметров для приближенно самоподобных и зашумленных данных. Предполагается, что к исходному сигналу f [i, j ] добавлен белый шум:
где n[i, j ] – случайная последовательность, такая что E (n[i, j ]n[k, l ]) 2 i,k j,l, где i, j – символ Кронекера, E – среднее значение.
Таблица 1: Зашумленный и восстановленный сигналы, значения SNR SNR, дБ Восстановление SNR, дБ Для оценки степени зашумленности используется показатель отношения сигнала к шуму (signal to noise ratio, SNR):
В результате вычислительных экспериментов установлено, что наличие случайных шумов даже в случае, когда шум имеет ту же энергию, что и сам сигнал, позволяет восстанавливать параметры аффинных самоподобных функций. Это связано с тем, что всплеск-преобразование содержит эти шумы только на самых малых масштабах.
В заключении приводятся основные результаты работы.
В приложение вынесены тексты программ основных алгоритмов решения поставленных в работе задач.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Разработаны методы численного решения обратной задачи для многомерных аффинных самоподобных функций с использованием всплесканализа, имеющие большое значение в вопросах, связанных с цифровой обработкой сигналов, распознаванием образов, анализом моделей хаотической динамики в молекулярной физике, геофизике и метеорологии.2. На основе выявленных свойств самоподобия НВП (непрерывного всплеск-преобразования) с вращениями для самоподобных функций было получено обобщенное НВП, которое обладает такими же свойствами самоподобия в отношении аффинных самоподобных функций.
3. Разработан алгоритм численного восстановления параметров аффинного самоподобия, причем восстановление происходит посредством голосования для всплеск-максимумов обобщенного НВП в пространстве параметров аффинных операторов.
4. Получено обоснование того, что точки всплеск-максимумов обобщенного НВП для всплесков Гаусса принадлежат кривым, распространяющимся до самых малых масштабов, что позволяет повысить устойчивость алгоритма к численным погрешностям в тех областях, где НВП близко к нулю.
«