Моделирование адаптивных сплайн-всплесков для двумерных и трехмерных цифровых сигналов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Герасимов, Иван Владимирович

• Герасимов, Иван Владимирович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Герасимов, Иван Владимирович

Оглавление

Введение

1 Аппроксимационные и калибровочные соотношения для функций Зламала (двумерный случай)

1.1 Аппроксимационные соотношения

1.2 Калибровочные соотношения для однократного измельчения триангуляции

1.3 Задача локального укрупнения правильной триангуляции

1.4 Калибровочные соотношения при локальном укрупнении триангуляции

1.5 Процедура мультишагового укрупнения триангуляции

1.6 Калибровочные соотношения при двухшаговом укрупнении триангуляции

2 Симплициальное подразделения слоя в К3 и аппроксимация

Зламала

2.1 О прямых обобщениях специальной триангуляции в пространстве К3

2.2 Построение симплициального подразделения специального вида

2.3 Укрупнение симплициального подразделения

2.4 Аппроксимационные соотношения

2.5 Калибровочные соотношения для измельчения симплициального подразделения

2.6 Калибровочные соотношения для укрупнения симплициального подразделения

2.7 Калибровочные соотношения при дроблении симплициального подразделения в случае плоско-параллельного сечения слоя

2.8 Замечания о калибровочных соотношениях

3 Трехмерное локально-укрупняемое симплициальное подразделение

3.1 Изложение идеи симплициального подразделения

3.2 Формальное изложение специального симплициального подразделения в R3

3.3 Определение симплициального подразделения

3.4 Некоторые вспомогательные обозначения

3.5 Базовое укрупнение симплициального подразделения

3.6 Дополнительное укрупнение подразделения

3.7 Изоморфизм исходного и результирующего подразделений

3.8 Об обобщении на случай иного числа измерений

4 Компьютерное моделирование задачи построения симплициального подразделения специального вида

4.1 Базовый интерфейс источника данных

4.2 Элементарные типы данных

4.3 Генерация исходного подразделения

4.4 Ограничение потока данных

4.5 Укрупнение подразделения

4.6 Приложение с графическим пользовательским интерфейсом

Заключение

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

Приложение A

Приложение Б

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

Введение

С широким распространением цифровых технологий и в связи с научно-техническим прогрессом непрерывно возрастают объемы числовых информационных потоков, передающихся по компьютерным сетям и обрабатываемых вычислительными системами. Математические модели могут представляться цифровыми потоками, имеющими значительный объем. В связи с этим стали актуальными различные методы сжатия информации, как без потери информации (кодирование Шеннона-Фэно, Хемминга, исправляющие коды Хаффмана, коды Рида-Соломона и др.) [51, 61, 64, 80, 86], так и сжатие с контролируемой потерей информации при использовании различных вариантов аппроксимации и интерполяции (сплайны, конечно-элементная аппроксимация, связанные с именами Шонберга, Зенкевича, Куранта, Стрэнга, Михлина) [32, 40, 52, 84, 90, 91]. В определенном смысле промежуточное положение занимают вейвлетные разложения: по исходному потоку числовой информации генерируется два потока: так называемый основной поток, содержащий основную часть интересующей информации и всплесковый (вейвлетный) поток, содержащий уточняющую информацию. Для построения адекватной математической модели, часто достаточно передать по линиям связи лишь основной поток, а уточняющую информацию (вейвлетный поток) можно передать позже (или вообще не передавать). Вейвлетное разложение характеризуется двумя неотъемлемыми свойствами: 1) по основному и всплесковому потокам однозначно восстанавливается исходный поток, что позволяет при необходимости вернуться к исходной, более точной математической модели, 2) сумма размерностей пространства основных потоков и пространства всплесковых потоков равна размерности пространства исходных потоков. Для всплескового разложения существенна локальность координатных функций: локальные координатные функции (т.е. координатные функции с малым носителем) позволяют проводить локальные уточнения основного потока по требованию адресата, передавая лишь соответствующую часть уточняющего (всплескового) потока. На пути получения локальности или полулокальности координатных функций (полулокальность здесь означает достаточно быстрое убывание координатных функций на бесконечности) в классической теории всплесков приходится преодолевать большие трудности, однако, эта проблема получила лишь частичное решение (см. [39]).

Весьма существенна вычислительная сторона: формулы разрабатываемых численных методов должны быть достаточно просты, в частности, не связанны с вычислением прямого и обратного преобразований Фурье, а также с предельным переходом в бесконечном произведении, как это приходится делать в классической теории вейвлетов, ибо численная реализация этих преобразований вносит погрешности и требует значительных компьютерных ресурсов. Исходный поток восстанавливается приближенно по основному потоку (без привлечения всплескового потока), что фактически позволяет произвести замену дискретной математической модели ее менее требовательным к ресурсам приближением. Таким образом, весьма существенны аппроксимативные свойства основного потока: чем выше его аппроксимативные свойства, тем больше возможностей уменьшить объем основного потока, сохраняя заданную точность упомянутого восстановления (без всплескового потока). Как известно, гибкими аппроксимативными свойствами обладают пространства сплайнов: вычислительные методы, основанные на сплайнах, позволяют выбрать нужный порядок аппроксимации (который оказывается асимптотически оптимальным по Ж-поперечнику стандартных компактов) и выбрать подходящую (вообще говоря, неравномерную) сетку в зависимости от характеристик изменения поступающего потока (сохраняя исходную сетку в областях быстрого изменения потока и разрежая ее в областях его медленного изменения). Таким образом, исходный поток (как правило) связывается с равномерной сеткой и со сплайном — элементом выбранного пространства сплайнов на этой сетке. Основной поток связывают со сплайном из вложенного пространства, построенного на вложенной (более крупной и, возможно, неравномерной) сетке. В одномерном случае основными задачами являются: выбор пространств сплайнов, на исходной и на вложенной сетках (так чтобы пространство на вложенной сетке было подпространством пространства на исходной сетке) и выбор алгоритма локального укрупнения исходной сетки (в зависимости от скорости изменения исходного потока). Для размерностей больше единицы укрупнение исходной сетки представляет определенную проблему. Дело в том, что наиболее удобные и часто встречающиеся аппроксимирующие пространства (Куранта, Зламала, Женишека, Аргириса) [44, 47, 52, 94, 95, 96, 97] связаны с правильной (в топологическом смысле) триангуляцией или с симплициальным подразделением (в двумерном и трехмерном случаях соответственно), но не каждое из таких подразделений допус-

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

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

Историческая справка

В классической теории вейвлетов используется кратно-масштабный анализ. Рассматриваются вейвлетные разложения, основанные на вейвлетах Хаара [60], а также другие мультивейвлетные базисные функции. Классический вейвлет-ный анализ базируется на непрерывном и дискретном преобразованиях Фурье, с помощью которых можно сформулировать вейвлет преобразования, используя линейные преобразования аргумента единственной функции и ограничиваясь тем самым лишь равномерными сетками на вещественной оси и, как правило, лишь пространством Ь2 (см., например, [39]). Однако, для быстро меняющихся потоков равномерные сетки представляются недостаточными, но перейти к неравномерной сетке в рамках кратно-масштабного анализа и предыдущей техники весьма затруднительно. В дальнейшем был разработан другой подход к построению вейвлетных разложений (см. [2, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 21, 22, 23, 25, 26, 27, 28, 29, 30, 37, 38, 55]). В предлагаемой работе этот подход применяется к сплайн-всплесковому разложению числовых информационных потоков, ассоциированных с областями трехмерного пространства:

) = сзШ К)'

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

основное пространство; проектирование первого из них на второе порождает всплесковое разложение.

Привлекательными свойствами этой модели являются локальность, устойчивость, простота алгоритмов декомпозиции и реконструкции поступающих потоков, асимптотическая оптимальность по Ж-поперечнику стандартных компактов [12]. Локальность, в свою очередь, позволяет обеспечить параллельность производимых вычислений (см. [24, 37]).

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

Исследования в области обработки больших числовых массивов информации восходят к трем источникам, возникшим независимо друг от друга: к классической теории сплайнов, к методу конечных элементов и к теории вейвле-тов. В соответствии с этим можно выделить по крайней мере три направления развития теории обработки упомянутых массивов. Первое направление берет свое начало от работ Шонберга [84]; здесь исходным моментом является решение какой-либо задачи интерполяции (задачи Лагранжа, Эрмита или Эрмита-Биркгофа) в классе функций с «кусочными» свойствами и с определенной гладкостью в узлах рассматриваемой сетки (см. [50, 78, 85]). Заметим, что если исходный массив числовой информации задан как сеточная функция на мелкой сетке, то замена этой сеточной функции на результат решения интерполяционной задачи для крупной сетки (являющейся подмножеством мелкой сетки) может рассматриваться как сжатие исходного массива числовой информации. Аппроксимационные свойства и вычислительная простота получаемых сплайнов всякий раз исследуются дополнительно. Сюда относятся современные исследования по обобщенным сплайнам, так называемым ЕСТ-В-сплайнам (см., например, [50, 78]); в этих работах для построения сплайнов на сеточных промежутках используются различные ЕСТ-системы, которые при определенных условиях удается гладко «склеить» в узлах.

Второе направление опирается на аппроксимационные свойства рассматриваемых функций, где определение базисных функций связано с решением ап-проксимационных соотношений, рассматриваемых как система уравнений (эти исследования появились в связи с теорией метода конечных элементов, см. [40, 58, 90]); при таком подходе интерполяционные свойства и алгоритмы минимиза-

ции вычислительной сложности (вложенность пространств и вейвлетное представление цепочки вложенных пространств) приходится устанавливать дополнительно. Выбор порождающей т + 1-компонентной вектор-функции ф(Ь), заданной на интервале (а, в), определяет семейства конечномерных пространств на элементарных сеточных интервалах рассматриваемой (конечной или бесконечной) сетки X = {xj}, X С (а, в), а выбор цепочки А векторов со свойством полноты приводит к пространству (X, А, ^)-сплайнов. Условия гладкости эквивалентны определенным алгебраическим соотношениям между значениями ф(Ь) (и ее производных) в узлах сетки и векторами цепочки А. Требование максимальной гладкости сплайнов (при выбранной вектор-функции ф(Ь) с отличным от нуля вронскианом из ее компонент) однозначно (с точностью до постоянных отличных от нуля множителей) определяет цепочку А; при этом однозначно определяется также пространство (X, А, ^)-сплайнов, которое в этом случае называется пространством В^-сплайнов (см. [15, 20]).

Третье направление — теория вейвлетов — в основу кладет вычислительную простоту, отражением чего является кратно-масштабное уравнение (см. [31, 39, 53, 75, 87]); исследование последнего приводит в первую очередь ко вложенности получаемых пространств и к вейвлетному представлению соответствующей цепочки вложенных пространств (это ведет к минимизации вычислительной сложности численных методов); остальные из перечисленных выше свойств с большим или меньшим успехом исследуются дополнительно (см., например, [39]).

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

Иллюстрация схемы построений (одномерный случай)

В этом пункте дадим иллюстрацию применяемых методов в одномерном случае. Другие примеры могут быть найдены в работах [13, 18, 21, 38] и др.

Пусть £ — линейное пространство вещественных функций, заданных на

интервале (а, в) £ R1. Рассмотрим сетку

X : ... < x-2 < x-1 < x0 < x1 < x2 < ..., lim Xj = a, lim Xj = ß,

j —У — TO j —>+TO

и вектор-функцию ^>(t)= (^0(t), ^(t),... , ^>m(t))T, t £ (a,ß) с компонентами из пространства L: ф £ L, i £ {0,1,..., m}.

В дальнейшем наряду с интервалом (а, в) рассматривается также отрезок [а, b], содержащийся в этом интервале: [а, b] С (а, в). След рассматриваемых здесь функций на этом отрезке позволяет рассматриваемые дальше бесконечные суммы заменить конечными, от бесконечномерных пространств перейти к конечномерным, а бесконечные потоки числовой информации заменить конечными, не нарушая схемы рассуждений и сохраняя правильность получаемых результатов.

Рассмотрим множество G линейных функционалов g(s) £ L*, Gd= {g(s)}s£z, со свойством

suppg(s) С (xs,xs+1) Vs £ Z. (1)

Действие функционала g(s) на функцию u £ L обозначается острыми скобками (g(s),u), а действие этого функционала на вектор-функцию ip(t) дает вектор-столбец с числовыми компонентами по формуле

5),ф = (<g(s),^o), (g(s),v 1),..., <g(s),^m»T. Пусть выполнено условие

det(<g(s), ф, <g(s+1), ф),..., <g(s+m), ф) = 0 Vs £ Z. (2)

Положим

a

def (g (5),ф). (3)

Из (2) следует, что система векторов а5, а5+1,..., а5+то+1 линейно независимая при каждом в £ Z. Рассмотрим аппроксимационные соотношения

к

»¿^й = <£(*) У £ (Хк,Хк+1) Ук £ Z, (4)

г=к—т

виррш8 С [ж5,ж5+то+1] Уй е Z. (5)

Благодаря условию (2) из соотношений (4) - (5) функции определяются однозначно на множестве Ми^2(ж5,ж5+1). Предположим, что ша е £.

Учитывая свойство (1) и обозначение (3), видим, что система функционалов биортогональна системе функций {о^}^:

и в) = j Vj, s G Z. (6)

Рассмотрим линейное пространство

S = S(X» = L{ub}bgz, (7)

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

XX : ... < Ж_2 < Ж_ 1 < Ж0 < Ж1 < Ж2 < ..., lim Xj = a, lim Xj = ß, XX С X,

j—У — TO j —+TO

то аналогично предыдущему с этой сеткой можно связать функции ихi и натянутое на них линейное пространство X = S(X, ^>), которое при определенных условиях (например, в случае сплайнов максимальной гладкости) содержится в пространстве S(X,

Рассмотрим проектирование P пространства S в пространство S, задаваемое формулой

Pu =f ^(X(B),u)ws Vu G S(X,p), (8)

sG Z

где {X(s)}sGz _ система функционалов, биортогональная системе координатных функций {Ui}iGZ.

Заметим, что при каждом фиксированном t G (xk,, Xk+i) сумма в правой части формулы (8) содержит не более, чем m + 1 слагаемых:

k

Pu(t) =f ^ (X(s),u)us(t) Vt G (Xk,Xk+i). (9)

s=k—m

Проектирование Р определяет вейвлетное разложение

§ = §+Ш. (10)

Если для исходного потока с = (..., С—2, с-1, С0, с1, С2,...) числовой информации

рассмотреть функцию и(£)^ ^С]ш](£), то ее проекция и=Ри на пространство

§ имеет вид

и = ^^ агШг

и таким образом, определяет поток а = (..., а—2, а—^ а0, а1, а2,...), соответствующий укрупненной сетке, а также определяется вейвлетный поток Ь=(... , Ь—2, Ь-1, Ь0, Ь1, Ь2,...) из разложения т= и-и по базису пространства §: т = ^5 Ь^. Переход от потока с к потокам а и Ь называется декомпозицией, а обратный переход — реконструкцией.

В частном случае т = 1, = (1,£)т при X\Х = {хк+1}, формулы декомпозиции имеют вид

аг = сг при г ^ к — 1, аг = сг+1 при г ^ к,

, Л • / / I. Хк+2 — Хк+1 , Хк+1 — Хк

Ь] = 0 при ; = к, Ьк =---ск—1 + Ск---Ск+1.

Хк+2 — Хк Хк+2 — Хк

Формулы реконструкции можно записать в виде

С] = а] + Ь] при ] ^ к — 1,

Хк+2 — Хк+1 . Хк+1 — Хк .7

Ск =-• ак- 1 +--• ак + Ьк,

Хк+2 — Хк Хк+2 — Хк

С] = а]—1 + Ь] при ^ ^ к + 1.

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

Из предыдущего видно, что в основе предлагаемого подхода к построению вейвлетного разложения лежат аппроксимационные соотношения; поэтому порядок аппроксимации такого разложения асимптотически оптимален по Х-поперечнику стандартных компактов.

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

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

Для обеспечения возможности построения сплайн-всплескового разложения в двумерном случае, необходимо определить дополнительные ограничения на используемую триангуляцию. Значительное число работ посвящено вопросам возможности измельчения и укрупнения триангуляции с сохранением правильности, а также о свойствах триангуляции, пригодной для разбиения двумерных областей (см., например, [1, 33, 35, 36, 56, 89]).

В работах [29, 42, 43] была использована триангуляция специального вида, допускающая локальное укрупнение. Использование указанной триангуляции позволяет произвести сплайн-всплесковое разложение с получением вложенности пространств Куранта и Зламала [4, 29].

В настоящей работе предлагается алгоритм построения симплициально-го подразделения, обладающего способностью к локальному укрупнению, что позволяет произвести сплайн-вейвлетное разложение функции, заданной на соответствующей трехмерной области. Схожие вопросы проявляются в задачах, связанных с методом конечных элементов и другими разделами математики, где, однако, чаще требуется рассматривать измельчения сетки (см. [3, 45, 46, 48, 63, 69, 71, 73, 74, 76, 79, 81, 82, 83, 92, 93]). Необходимо отметить, что структуры, аналогичные полученным в настоящей работе, были описаны при рассмотрении проблемы заполнения эвклидова пространства тетраэдрами [59, 70, 88, 89]. В данной работе, из использования подразделений указанного вида выстраивается алгоритм укрупнения симплициального подразделения, пригодный для проведения схемы построения сплайн-всплескового разложения.

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

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

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

Основные результаты, выносимые на защиту

1. Новые математические модели симплициального подразделения плоского слоя и его локального двумерного укрупнения.

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

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

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

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

Теоретическая и практическая значимость. Работа имеет в основном теоретическую направленность. В числе теоретических результатов предло-

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

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

Публикации по материалам диссертации. Материалы, содержащие основные результаты диссертационной работы, изложены в 4 опубликованных в печати работах [4, 5, 6, 19], 3 из них — в рецензируемых изданиях, входящих в список ВАК [4, 5, 19].

Работа [19] выполнена в соавторстве с научным руководителем, профессором Ю. К. Демьяновичем. В указанной публикации диссертанту принадлежит идея алгоритма построения симплициального подразделения, подробно рассмотренного в третьей главе диссертационной работы.

Апробация работы. Результаты диссертационной работы были представлены на семинарах кафедры параллельных алгоритмов математико-меха-нического факультета СПбГУ, кафедры компьютерных технологий и программной инженерии ГУАП, доложены на семинаре по вычислительной математике при СПбПУ, а также представлены в виде докладов на 45-й конференции «Процессы управления и устойчивость» в 2015 году и конференции СПИСОК-2016.

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

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

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

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

В работах М. Крыжека и С. Кротова (см. [72]) установлено, что при размерности пространства п > 2 невозможно разбить невырожденный п-мерный симплекс на конгруэнтные симплексы меньшего размера с сохранением углов.

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

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

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

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

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

В четвертой главе приведены результаты компьютерного моделирования задачи построения симплициального подразделения специального вида в двумерном и трехмерном случаях. Моделью является симплициальное подразделение представленное неориентированным графом. Был разработан и реализован общий программный интерфейс для подразделения. В качестве простейших его реализаций определены конкретные классы, задающие симплици-альное подразделение специального вида без явно заданных ограничений области. Наследуемыми классами следующего уровня реализована возможность задавать границы области либо явно (например, как простой параллелепипед), либо по более сложным условиям, включающим в себя вычисления оценок для отдельных узлов. На следующем этапе реализована возможность производить модификацию части симплициально подразделенной области либо путем измельчения, либо за счет укрупнения. Программный интерфейс (API) разработан таким образом, чтобы он хорошо сочетался с поддержкой технологии Streams, которая появилась в языке Java 8 [65, 67]. Эта технология позволяет использовать встроенную в стандартный инструментарий JDK3 поддержку параллельных вычислений. В компьютерном приложении реализован графический пользовательский интерфейс для наглядной демонстрации производимых преобразований. Его основные составные части включают в себя поле для графического отображения подразделения и форму для ввода параметров преобразования.

Список литературы диссертационного исследования кандидат наук Герасимов, Иван Владимирович, 2016 год

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

[1] Арсентьева, Е. П. Об измельчении триангуляции вблизи границы области / Е.П.Арсентьева // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2011. Вып. 1. С. 76-84.

[2] Арсентьева, Е. П. Адаптивные сплайн-вэйвлетные разложения двумерных потоков числовой информации / Е. П. Арсентьева, Ю. К. Демьянович // Сб. Пробл. мат. ан. 56, 2011. С. 3-22.

[3] Арсентьева, Е. П. Алгоритмы невырожденного симплици-ального подразделения с измельчением вблизи границы / Е. П. Арсентьева, Ю. К. Демьянович // В: Компьютерные инструменты в образовании. Информатика. 2011. С. 23-30.

[4] Герасимов, И. В. Алгоритм построения аппроксимации Зламала при локальном укрупнении триангуляции / И. В. Герасимов // Компьютерные инструменты в образовании, вып. 2, 2014. С. 20-28.

[5] Герасимов, И. В. Способ локального укрупнения симплициального подразделения в R3 / И. В. Герасимов // Компьютерные инструменты в образовании, вып. 6, 2014. С. 3-11.

[6] Герасимов, И. В. Аппроксимация Зламала для укрупняемого симплици-ального подразделения слоя / И. В. Герасимов // Процессы управления и устойчивость: Труды 45-й международной научной конференции аспирантов и студентов / под ред. Н.В.Смирнова, Т.Е.Смирновой. СПб.: Издат. Дом С.-Петерб. гос. ун-та, Т. 2, 2015. С. 390-397.

[7] Демьянович, Ю. К. Об аппроксимации и сходимости метода сеток в эллиптических задачах / Ю.К.Демьянович // ДАН, 170, № 1 1966. С. 27-30.

[8] Демьянович, Ю. К. Вэйвлеты & минимальные сплайны / Ю.К.Демьянович. - СПб.: Изд. СПбГУ, 2003. 463 с.

[9] Демьянович, Ю.К. Гладкость пространств сплайнов и всплесковые разложения / Ю.К.Демьянович // Доклады АН, Т. 401 4, 2005. С. 493-442.

[10] Демьянович, Ю.К. Вейвлетный базис В-сплайнов для неравномерной сетки / Ю.К.Демьянович // Математическое моделирования, Т. 18 10, 2006. С. 123-126.

[11] Демьянович, Ю. К. Локальный базис всплесков на неравномерной сетке / Ю.К.Демьянович // Записки научных семинаров ПОМИ. Т. 334, СПб., 2006. С. 84-110.

[12] Демьянович, Ю. К. Об асимптотических разложениях координатных сплайнов / Ю. К. Демьянович // Записки научных семинаров ПОМИ. Т. 359, СПб., 2008. С. 17-30.

[13] Демьянович, Ю. К. Негладкие сплайн-вэйвлетные разложения и их свойства / Ю. К. Демьянович // Записки научных семинаров ПОМИ. 24 Т. 395, СПб., 2011. С. 31-60.

[14] Демьянович, Ю. К. Сплайн-вэйвлеты при однократном локальном укрупнении сетки / Ю.К.Демьянович // Численные методы и вопросы организации вычислений. XXV. Записки научных семинаров ПОМИ. Т. 405, СПб., 2012. С. 97-118.

[15] Демьянович, Ю. К. Теория сплайн-всплесков / Ю. К. Демьянович. — СПб.: Изд-во С.-Петерб. ун-та, 2013. — 526 с.

[16] Демьянович, Ю. К. Адаптивные свойства сплайн-вейвлетной аппроксимации / Ю.К.Демьянович, М.В.Анолик, О.Н.Иванцова // Сб. Пробл. мат. ан. 78, 2015. С. 57-73.

[17] Демьянович, Ю. К. О сплайн-всплесковой декомпозиции на отрезке / Ю.К.Демьянович, Б. Г. Вагер // Записки научных семинаров ПОМИ. 27 Т. 428, СПб., 2014. С. 107-131.

[18] Демьянович, Ю. К. Новый вариант вэйвлетного разложения пространств сплайнов / Ю. К. Демьянович, М. В. С. Габр // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2009. Вып. 4, С. 58-68.

[19] Демьянович, Ю.К. О локальных укрупнениях симплициальных подразделений / Ю. К. Демьянович, И. В. Герасимов // Сб. Пробл. мат. ан. 84, 2016. С. 67-82.

[20] Демьянович, Ю. К. Об аппроксимации В^-сплайнами / Ю. К. Демьянович, В. О. Дронь, О. Н. Иванцова // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2013. Вып. 3. С. 67-72.

[21] Демьянович, Ю. К. Всплесковое (вейвлетное) разложение пространств периодических В-сплайнов второй степени на неравномерной сетке / Ю. К. Демьянович, А. В. Зимин // Вестн. С.-Петерб. ун-та. Сер. 1: Математика. Механика. Астрономия. 2006. Вып. 3. С. 72-83.

[22] Демьянович, Ю. К. Аппроксимации курантова типа и их вэйвлетное разложение / Ю. К. Демьянович, А. В. Зимин // Сб. Пробл. мат. ан. 37, 2008. С. 3-22.

[23] Демьянович, Ю. К. Новые представления сплайн-вэйвлетных разложений / Ю. К.Демьянович, О. Н. Иванцова // Сб. Пробл. мат. ан. 46, 2010. С. 73104.

[24] Демьянович, Ю. К. О параллельном вэйвлетно-сплайновом сжатии на неравномерной сетке / Ю. К. Демьянович, О. М. Косогоров // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2008. Вып. 2, С. 3-10.

[25] Демьянович, Ю. К. О вычислении матриц декомпозиции в сплайн-вейвлетном разложении / Ю. К. Демьянович, О. М. Косогоров // Методы вычислений. Изд. СПб. ГУ. 2010. С. 73-98.

[26] Демьянович, Ю. К. О вэйвлетных разложениях линейных пространств над произвольным полем и о некоторых приложениях / Ю.К.Демьянович, А.Б.Левина // Математическое моделирование, Т. 20, № 11, 2008. С. 104-108.

[27] Демьянович, Ю. К. Негладкие сплайн-вэйвлетные разложения на отрезке

/ Ю.К.Демьянович, И.Д.Мирошниченко // Сб. Пробл. мат. ан. 63, 2012. С. 35-53.

[28] Демьянович, Ю. К. Гнездовые сплайн-вэйвлетные разложения / Ю. К. Демьянович, И. Д. Мирошниченко // Сб. Пробл. мат. ан. 64, 2012. С. 35-53.

[29] Демьянович, Ю. К. Локальное укрупнение триангуляции и двумерные сплайн-вэйвлеты / Ю. К. Демьянович, Л. М. Романовский // Труды конф. СПИСОК-2012, С. 177-182

[30] Демьянович, Ю. К. Сплайн-всплесковое укрупнение аппроксимаций куран-тового типа / Ю. К. Демьянович, Л. М. Романовский // Записки научных семинаров ПОМИ. Т. 419, СПб., 2013. С. 77-110.

[31] Добеши, И. Десять лекций по вэйвлетам, перевод с английского / И. Добеши. — Ижевск: 2001. 463 с.

[32] Зенкевич, О. С. Конечные элементы и аппроксимация, перевод с английского / О. С. Зенкевич, К. Морган. — М.: Мир, 1986. - 320 с.

[33] Лебединская, Н. А. Многопоточный алгоритм сплайн-вейвлетного сжатия цифрового представления сигнала / Н. А. Лебединская, Д. М. Лебединский // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2008. Вып. 1. С. 95-100.

[34] Лебединская, Н. А. Кратномасштабное разложение для аппроксимации Зламала / Н.А.Лебединская, Д.М.Лебединский // Вестн. С.-Петерб. унта. Сер. 1: Математика. Механика. Астрономия. 2009. Вып. 1. С. 18-22.

[35] Лебединская, Н. А. Преобразование триангуляций при помощи элементарных операций / Н. А. Лебединская, Д. М. Лебединский // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2009. Вып. 1. С. 84-86.

[36] Лебединская, Н. А. Измельчение триангуляции при помощи разбиения ребра / Н. А. Лебединская, Д. М. Лебединский // Вестн. С.-Петерб. ун-та. Сер. 1: Математика. Механика. Астрономия. 2009. Вып. 2. С. 59-62.

[37] Макаров, А. А. О распараллеливании вэйвлетных методов сжатия информации / А.А.Макаров // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2007. Вып. 4. С. 45-49.

[38] Макаров, А. А. Один вариант сплайн-вэйвлетного разложения пространств B-сплайнов / А.А.Макаров // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2009. Вып. 3. С. 59-71.

[39] Малла, С. Вэйвлеты в обработке сигналов, перевод с английского / С.Малла. - М.: Мир, 2005. - 671 с.

[40] Михлин, С. Г. Вариационно-сеточная аппроксимация / С. Г. Михлин // Зап. науч. семинаров ЛОМИ АН СССР. Т. 48, 1974. С. 32-188.

[41] Петухов, А. П. Введение в теорию базисов всплесков / А. П. Петухов. — СПб.: 1999. - 132 с.

[42] Романовский, Л. М. Об алгоритме локального укрупнения триангуляции / Л. М. Романовский // Компьютерные инструменты в образовании, вып. 2, 2014. С. 29-34.

[43] Романовский, Л. М. Реализация алгоритма локального укрупнения триангуляции / Л. М. Романовский // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика и процессы управления. 2014. Вып. 3. С. 111-117.

[44] Сьярле, Ф. Метод конечных элементов для эллиптических задач, перевод с английского / Ф. Сьярле. — М.: Мир, 1980. - 512 с.

[45] Adier, A. On the bisection method for triangles / A. Adler // Math. Comp. 40, 1983. P. 571-574.

[46] Bansch, E. Local mesh refinement in 2 and 3 dimensions / E. Bansch // IMPACT Comput. Sci. Eng. 3, 1991. P. 181-191.

[47] Bramble, J. H. Triangular Elements in the Finite Element Method / J. H. Bramble, M. Zlamal // Mathematics of Computation. Vol. 24, Num. 112, 1970. P. 809-820.

[48] Brandts, J., On nonobtuse simplicial partitions / J.Brandts, S. Korotov, M.KhZek, J. Sole // SIAM Rev. 51, 2009. P. 317-335.

[49] Bruno, E., Parallel Array Operations in Java 8 [Электронный ресурс] / E.Bruno // URL:http://www.drdobbs.com/jvm/parallel-array-operations- in- java-8/240166287 (дата обращения: 22.05.16)

[50] Buchwald, B. Construction of B—splines for generalized spline spaces from local ECT—systems / B. Buchwald, G. Miihlbach // Journal of Computational and Applied Mathematics 159, 2003. P. 249-267.

[51] Cormen, T.H. Introduction to Algorithms (3rd ed.) / T. H.Cormen, C. E. Leiserson, R. L. Rivest C. Stein - MIT, 2009. - 1292 с.

[52] Courant, R. // Bull. Am. Math. Soc., 49, № 1, 1943. P. 394-409.

[53] Daubechies, I. Factoring wavelet transforms into lifting steps / I. Daubechies, W. Sweldens // Bell Laboratories, Lucent Technologies, 1996. P. 1-27.

[54] Davydov, O. Interpolation by C1 splines of degree q ^ 4 on triangulation / O. Davydov, G. Nurnberg // J. Comput. and Appl. Math., 2000. Vol. 126. P. 159-183.

[55] Dem'yanovich, Y. K. Structure of two-nested spline-wavelet decomposition / Y. K. Dem'yanovich, V. O. Dron' //J. mathematical sciences, Vol. 189. 3, 2013. C. 388-401.

[56] Eppstein, D. Tiling space and slabs with acute tetrahedra / D. Eppstein, J.M.Sullivan, A. Ungor // Comput. Geom.: Theory and Appl. 27, 2004. P. 237-255.

[57] Fano, R. M. The transmission of information / R. M. Fano // Technical Report № 65, Cambridge (Mass.), USA: Research Laboratory of Electronics at MIT, 1949.

[58] Goel, J. J. Construction of basis functions for numerical utilization of Ritz's method / J. J. Goel // Numer. Math. 12 1968. P. 435-447.

[59] Goldberg, M. Three infinite families of tetrahedral space-fillers / M. Goldberg //J. Combin. Theory (A) 16, 1974. P. 348-3354.

[60] Haar, A. Zur Theorie der orthogonalen Funktionensysteme (перевод на английский: On the Theory of Orthogonal Function Systems.) / A. Haar // Mathematische Annalen, 69 3, 1910. P. 331-371.

[61] Hamming, R. W. Error detecting and error correcting codes / R.W.Hamming // Bell System Technical Journal, 29 (2), 1950. P. 147-160.

[62] Hannukainen, A. On global and local mesh refinements by a generalized conforming bisection algorithm / A. Hannukainen, Korotov, S., KnZek, M. // J. Comp. and App. Math. Vol. 235, 2, 2010. P. 419-436.

[63] Horst, R. On generalized bisection of n-simplices / R. Horst // Math. Comp. 66, 1997. P. 691-698.

[64] Huffman, D. A. A method for the construction of minimum redundancy codes / D.A.Huffman // Proc. of the I.R.E., 40, 1952. P. 1098-1101.

[65] Java 8 Central [Электронный ресурс] URL:http://www.oracle.com/ technetwork/java/javase/overview/java8-2100321.html (дата обращения: 22.05.16)

[66] Java 8 SE Documentation, Spliterator [Электронный ресурс] URL:https:// docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html (дата обращения: 22.05.16)

[67] Java 8 Streams Technology [Электронный ресурс] URL:https: //docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html

(дата обращения: 22.05.16)

[68] Java SE 9 OpenJDK Project [Электронный ресурс] URL:http://openjdk. java.net/projects/jdk9/index.html (дата обращения: 22.05.16)

[69] Korotov, S. Acute type refinements of tetrahedral partitions of polyhedral domains / S. Korotov, M. KnZek // SIAM J. Numer. Anal. 39, 2001. P. 724733.

[70] Korotov, S. Local nonobtuse tetrahedral refinements of a cube / S. Korotov, M.KriZek // Appl. Math. Lett. 16, 2003. P. 1101-1104.

[71] Korotov, S. Global and local refinement techniques yielding nonobtuse tetrahedral partitions / S. Korotov, M. KSSek // Comput. Math. Appl. 50, 2005. P. 1105-1113.

[72] Korotov, S. Red refinements of simplices into congruent subsimplices / S. Korotov, M.KriZek // Comput. Math. Appl. 67, Issue 12, 2014. P. 21992204.

[73] KriZek, M. Nonobtuse tetrahedral partitions / M. KnZek, J. Pradlova // Numer. Methods Partial Differential Equations 16 (2000), P. 327-334.

[74] Liu, A. On the shape of tetrahedra from bisection / A.Liu, B.Joe // Math. Comp. 63, 1994. P. 141-154.

[75] Mallat, S. A Wavelet Tour of Signal Processing: The Sparse Way (3rd ed.) / S. Mallat. - New York: Academic Press, 2008. - 832 p.

[76] Maubach, J. M. Local bisection refinement / J. M. Maubach // SIAM J. Sci. Comput. 13, 1992. P. 210-227.

[77] Maxima — вычислительная система компьютерной алгебры [Электронный ресурс] URL:http://maxima.sourceforge.net/ru/index.html (дата обращения: 22.05.16)

[78] Miihlbach, G. ECT — B—splines defined by generalized divided differences / G. Miihlbach // Journal of Computational and Applied Mathematics 187, 2006. P. 96-122.

[79] Plaza, A. Local refinement of simplicial grids based on the skeleton / A. Plaza, G.F.Carey // Appl. Numer. Math. 32, 2000. P. 195-218.

[80] Reed, I. S. Polynomial Codes over Certain Finite Fields / I. S. Reed, G. Solomon // Journal of the Society for Industrial and Applied Mathematics 8 (2), 1960. P. 300-304.

[81] Rivara, M.-C. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques / M.-C. Rivara // Internat. J. Numer. Methods Engrg., 20, 1984. P. 745-756.

[82] Rivara, M.-C. Selective refinement/derefinement algorithms for sequences of nested triangulations / M.-C. Rivara // Internat. J. Numer. Methods Engrg., 28, 1989. P. 2889-2906.

[83] Rivara, M.-C. A 3D refinement algorithm suitable for adaptive and multigrid techniques / M.-C. Rivara, C. Levin // Commun. Appl. Numer. Methods Engrg. 8, 1992. P. 281-290.

[84] Schoenberg, A. Contributions to the problem of approximation of equidistant data by analytic functions / A. Schoenberg // Quart. Appl. Math., Vol. 4, 1946. P. 112-141.

[85] Schumaker, L. L. Spline Functions. Basic Theory / L. L. Schumaker. — New York: Waley Interscience, 1981. - 548 p.

[86] Shannon, C. E. A Mathematical Theory of Communication / C. E. Shannon // Bell System Technical Journal, 27, 1948. P. 379-423.

[87] Skopina, M. Multiresolution analysis of periodic functions / M. Skopina // East Journal on Approximations. 1997. Vol. 3. № 2. P. 614-627.

[88] Sommerville, D. M. Y. Space-filling Tetrahedra in Euclidean Space / D. M. Y. Sommerville // Edinburgh, Proc. Roy. Soc., Vol. 41, 1923. P. 49-57.

[89] Sommerville, D. M. Y. Division of space by congruent triangles and tetrahedra / D. M. Y. Sommerville // Edinburgh, Proc. Roy. Soc., Vol. 43, 1923. P. 85-116.

[90] Strang, G. Fourier analysis of the finite element method in Ritz-Galerkin theory / G.Strang, G. Fix // Stud. Appl. Math. 48, №3, 1969. P. 265-273.

[91] Strang, G. An Analysis of the Finite Element Method (2nd ed.) / G.Strang, G. Fix. — Wellesley: WellesleyCambridge Press, MA, 2008.

[92] Stynes, M. Subdivision of simplexes — is bisection best? / M. Stynes // Irish Math. Soc. Newsl. 8, 1983. P. 38-44.

[93] Todd, M. Optimal dissection of simplices / M.Todd // SIAM J. Appl. Math. 34, 1978. P. 792-803.

[94] Zenisek, A. Interpolation Polynomials on the Triangle / A. Zenisek // Numer. Math. 15, 1970. P. 283-296.

[95] Zenisek, A. Polynomial approximation on tetrahedrons in the finite element method. / A. Zenisek // J. Approx. Theory 7, 1973. P. 334-351.

[96] Zlamal, M. On the Finite Element Method / M. Zlamal // Numer. Math. 12 1968. P. 394-409.

[97] Zlamal, M. A Finite Element Procedure of the Second Order of Accuracy / M. Zlamal // Numer. Math. 14, 1970. P. 394-402.