Автореферат (Моделирование адаптивных сплайн-всплесков для двумерных и трехмерных цифровых сигналов)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиГЕРАСИМОВ ИВАН ВЛАДИМИРОВИЧМОДЕЛИРОВАНИЕ АДАПТИВНЫХСПЛАЙН-ВСПЛЕСКОВ ДЛЯ ДВУМЕРНЫХИ ТРЕХМЕРНЫХ ЦИФРОВЫХ СИГНАЛОВ05.13.18 — математическое моделирование,численные методы и комплексы программАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукСанкт-Петербург2017Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего образования «Санкт-Петербургский государственный университет».Научныйруководитель:доктор физико-математических наук, профессорДемьянович Юрий Казимирович, заведующий кафедрой параллельных алгоритмов ФГБОУ ВО «СанктПетербургский государственный университет»Официальныеоппоненты:доктор физико-математических наук, профессорРепин Сергей Игоревич, главный научный сотрудникФГБУН «Санкт-Петербургское отделение Математического института им.

В. А. Стеклова» РАНдоктор технических наук, профессорХодаковский Валентин Аветикович, заведующий кафедрой «математика и моделирование» ФГБОУ ВО«Петербургский государственный университет путейсообщения Императора Александра I»Ведущаяорганизация:ФГАОУ ВО «Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” им.В. И. Ульянова (Ленина)»Защита состоится: «.....» ........................... 2017 г. в ......... часов на заседании диссертационного совета Д 212.232.50 по защите диссертаций на соисканиеученой степени кандидата наук, на соискание ученой степени доктора наук приСанкт-Петербургском государственном университете по адресу: 198504, СанктПетербург, Петродворец, Университетский пр., д. 35, ауд.

327.Отзывы на автореферат в 2-х экземплярах просим направлять по адресу:198504, Санкт-Петербург, Петродворец, Университетский пр., д. 35, ученомусекретарю диссертационного совета Д 212.232.50 Г. И. Курбатовой.С диссертацией можно ознакомиться в научной библиотеке имени М. Горького Санкт-Петербургского государственного университета по адресу: 199034,Санкт-Петербург, Университетская наб., д 7/ 9.

Диссертация и авторефератдиссертации размещены на сайте www.spbu.ru.Автореферат разослан «.....» ........................... 2017 г.Ученый секретарь диссертационного советад-р физ.-мат. наук, проф.Г. И. Курбатова3Общая характеристика работыАктуальность темы. С широким распространением цифровых технологий и в связи с научно-техническим прогрессом непрерывно возрастают объемычисловых информационных потоков. Передача по компьютерным сетям и обработка этих потоков требуют значительных сетевых и компьютерных ресурсов.Для экономии упомянутых ресурсов применяются различные методы сжатияинформационных потоков.

Большое распространение получил как класс методов сжатия без потери информации (кодирование Шеннона-Фэно, Хемминга,исправляющие коды Хаффмана, коды Рида-Соломона и др.), так и класс методов сжатия с контролируемой потерей информации. К последним относитсяаппарат сплайнов, конечно-элементная аппроксимация (здесь упомянем именаШонберга, Зенкевича, Куранта, Стрэнга, Михлина). Свойствами обоих указанных классов обладают методы всплесковых (называемых также вейвлетными)разложений.

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

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

Чем выше его аппроксимативные свойства, тем больше возможностей уменьшить объем основного потока, сохраняя заданную точностьупомянутого восстановления (без всплескового потока), что фактически позволяет произвести замену дискретной математической модели ее менее требовательным к ресурсам приближением. Как известно, гибкими аппроксимативными свойствами обладают пространства сплайнов: вычислительные методыоснованные на сплайнах позволяют выбрать нужный порядок аппроксимации(который оказывается асимптотически оптимальным по N -поперечнику стан-4дартных компактов) и выбрать подходящую (вообще говоря, неравномерную)сетку в зависимости от характеристик изменения поступающего потока (сохраняя исходную сетку в областях быстрого изменения потока и разрежая еев областях его медленного изменения).

Исходный поток можно связать с равномерной сеткой и соответствующим сплайном, а основной поток — связатьсо сплайном на укрупненной сетке. Основные задачи таковы: 1) определениеалгоритма укрупнения исходной сетки, и 2) построение соответствующих вложенных пространств сплайнов и способов проектирования объемлющего пространства на упомянутое вложенное пространство. Для размерностей большеединицы укрупнение исходной сетки представляет определенную проблему. Дело в том, что наиболее удобные и часто встречающиеся аппроксимирующиепространства (Куранта, Зламала, Женишека, Аргириса) связаны с правильной(в топологическом смысле) триангуляцией или с симплициальным подразделением (в двумерном и трехмерном случаях соответственно), но не каждое изтаких подразделений допускает локальное укрупнение с сохранением свойстваправильности (в частности, триангуляция, широко используемая в методе конечных элементов не может локально укрупняться).В данной работе предлагаются алгоритмы построения адаптивных локальных аппроксимаций Куранта и Зламала на симплициальных подразделениях,допускающих локальное укрупнение.

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

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

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

Для проектирования и реализации5программного обеспечения применяются принципы объектно-ориентированного программирования с элементами поддержки функционального программирования.Основные результаты, выносимые на защиту1. Новые математические модели симплициального подразделения плоскогослоя и его локального двумерного укрупнения.2. Калибровочные соотношения для функций Зламала, соответствующие однократному локальному измельчению триангуляции, а также одношаговому идвухшаговому укрупнению триангуляции специального вида.3.

Алгоритмы симплициальных подразделений области, которые допускают локальное трехмерное укрупнение, порождают вложенные пространства Куранта и Зламала, а также приводят к адаптивному разложению исходногоцифрового потока.4. Комплекс программных интерфейсов и конкретных классов, реализующихкомпьютерное моделирование адаптивного построения симплициального подразделения предложенного в работе вида. Возможность параллелизма вычислений, как результат примененной технологии.Научная новизна. Все результаты диссертационной работы, выносимые назащиту и представленные выше в пунктах 1–4, получены впервые и обладаютновизной.Теоретическая и практическая значимость.

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