Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

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

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Герасимов Иван Владимирович. Моделирование адаптивных сплайн-всплесков для двумерных и трехмерных цифровых сигналов: диссертация ... кандидата Физико-математических наук: 05.13.18 / Герасимов Иван Владимирович;[Место защиты: ФГБОУ ВО Санкт-Петербургский государственный университет], 2017

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

Зламала 41

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение 105

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

Введение к работе

Актуальность темы. С широким распространением цифровых технологий и в связи с научно-техническим прогрессом непрерывно возрастают объемы числовых информационных потоков. Передача по компьютерным сетям и обработка этих потоков требуют значительных сетевых и компьютерных ресурсов. Для экономии упомянутых ресурсов применяются различные методы сжатия информационных потоков. Большое распространение получил как класс методов сжатия без потери информации (кодирование Шеннона-Фэно, Хемминга, исправляющие коды Хаффмана, коды Рида-Соломона и др.), так и класс методов сжатия с контролируемой потерей информации. К последним относится аппарат сплайнов, конечно-элементная аппроксимация (здесь упомянем имена Шонберга, Зенкевича, Куранта, Стрэнга, Михлина). Свойствами обоих указанных классов обладают методы всплесковых (называемых также вейвлетными) разложений. Для этих методов характерно разложение исходного информационного потока на два потока: на основной поток и на уточняющий (всплеско-вый) поток. Для построения адекватной математической модели, часто бывает достаточно передать по линиям связи лишь основной поток, а уточняющий поток передать позже (или вообще не передавать). Всплесковое разложение характеризуется двумя неотъемлемыми свойствами: 1) по основному и всплес-ковому потокам однозначно восстанавливается исходный поток, что позволяет при необходимости вернуться к исходной, более точной математической модели, 2) сумма размерностей пространства основных потоков и пространства всплесковых потоков равна размерности пространства исходных потоков. Для разложения существенна локальность координатных функций: это позволяет проводить локальные уточнения основного потока по требованию адресата, передавая лишь соответствующую часть всплескового потока. На пути получения локальности или полулокальности координатных функций (т.е. их быстрого убывания на бесконечности) в классической теории всплесков приходится преодолевать значительные трудности; эта проблема получила лишь частичное решение. Весьма существенна вычислительная сторона: формулы разрабатываемых численных методов должны быть достаточно просты, в частности, не связанны с вычислением прямого и обратного преобразований Фурье и с предельным переходом в бесконечном произведении. Заметим, что исходный поток может быть восстановлен приближенно по основному потоку (без привлечения всплескового потока); поэтому существенны аппроксимативные свойства основного потока. Чем выше его аппроксимативные свойства, тем больше возможностей уменьшить объем основного потока, сохраняя заданную точность упомянутого восстановления (без всплескового потока), что фактически позволяет произвести замену дискретной математической модели ее менее требовательным к ресурсам приближением. Как известно, гибкими аппроксимативными свойствами обладают пространства сплайнов: вычислительные методы основанные на сплайнах позволяют выбрать нужный порядок аппроксимации (который оказывается асимптотически оптимальным по N-поперечнику стан-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее, рассмотрим произвольный треугольник T T, задаваемый своими вершинами Измельчение триангуляции с сохранением правильности может быть осуществлено добавлением дополнительного узла на одну из сторон треугольника Т и восстановлением ребра, соединяющего новый узел с противолежащей вершиной. Без умаления общности будем считать, что новый узел рз добавляется во внутреннюю точку ребра ро–рь Таким образом рз = g-po + (l— q)-pi для некоторого вещественного числа q Є (0,1). Два треугольника получающиеся в результате разбиения треугольника Т обозначим Ті и 2.

Легко видеть, что существует девять базовых элементов Зламала, принимающих ненулевые значения на треугольниках Ті и Т2. Будем использовать обозначение ujk, к Є {0,... , 3} для базовых элементов, центральные узлы которых расположены в вершинах треугольников. Для тех элементов, центральными узлами которых являются середины сторон, будем использовать обозначение uJij, где tj и tj — концы соответствующей стороны.

Итак, базовый элемент UJQ исходной триангуляции выражается как линейная комбинация базовых элементов измельченной триангуляции следующим образом: _ бо о + (1 — 2д)(1 — q)uj2, + оз — 2 23? t Є Ті, х о + (1 — 2д)(1 — q)uj2, — 2 g оои 2" 23 2 22 Выражение для базового элемента UJ\ можно получить из только что полученных соотношений (7) формальной подстановкой (1 — q) вместо q и заменой соответствующих индексов. Впрочем, нетрудно вывести соотношения и непосредственно. -і \ Q( +Q) q(l—q) — гтп uj\ + q(2q — 1 x 3 — v 0 чо оз — 0 23, t Є ili, 6ch —— UJ\ + (Д2д — 1) х з + 2 6o i3 — 2 6o 23, t Є U-2 Выражение для u)2 очевидным образом тривиально: UJ2 = UJ2 Для базовых элементов, центральные узлы которых относятся ко второму типу, калибровочные выражения получаются аналогично. Так, для woi выражение принимает вид uoi = 4д(1 — q)uj2, + (2 — q)qujQ2, + (1 — q )оои + ?(1 — ) 23, а для элементов 6 02 и 6 12 6 02 = 02 + (1 — ) 23 и, соответственно, 6 12 = 6о 12 + qUJ23 Заметим, что полученные здесь результаты согласуются с кратномасштабными разложениями выведенными в [34]. 1.3 Задача локального укрупнения правильной триангуляции Произвольная правильная триангуляция, вообще говоря, не допускает локального укрупнения. Для преодоления этой трудности было предложено [2, 29] использовать триангуляцию специального вида. Такой специальной триангуляцией, например, является заданная следую 23 щей таблицей инциденций Рж,у Рж+4,у Рж+2,у+2 Рж+4,у Рж+4,у+4 Рж+2,у+2 Рж+4,у+4 Рж,у+4 Рж+2,у+2 Рж,у+4 Рж,у Рж+2,у+2 (8) где рх/у — вектор с целочисленными координатами х и у, кратными четырем, ж, у Є {4& & Є Z}. В некоторых ситуациях удобнее воспользоваться ее альтернативным определением, как сформулированно ниже. На приведенное определение подразделения двумерной области будем далее ссылаться как на способ (Q).

Способ (Q). Эквивалентным способом задания приведенной специальной триангуляции будет указание набора семейств прямых, которые подразделяют интересующую нас область на треугольники. Таким семейством, например, является х = 4&i, у = 4&2, х = у + 4&з, х = —у + 4&4, где параметры семейств &1, . . . , &4 Є Z.

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

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

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

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

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

Для двумерного случая М2 ситуация несколько усложняется, поскольку произвольная правильная триангуляция, вообще говоря, не может быть локально укрупнена с сохранением правильности. Одним из подходов в данном случае может являться использование триангуляции специального вида, например, как это сделано в [2] (см. также предыдущие главы настоящей работы).

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

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

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

Можно заметить, что приведенная триангуляция не является единственно возможной, допускающей локальное укрупнение. Другим примером может служить триангуляция, построенная из прямоугольных треугольников с соот- ношением сторон 1 : 3 : 2 (cм. рис. 5).

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

Вопрос о возможности локального укрупнения симплициального подразделения в М3 является весьма актуальным. К сожалению, непосредственное применение подхода аналогичного изложенному выше, применяемому в случае меньшего числа измерений, наталкивается на трудности, а именно — на невозможность построить трехмерный невырожденный симплекс, который можно было бы разбить на два меньших симплекса подобных исходному. Здесь уместно также указать на полученный в [72] результат. Будем гово 43 рить, что подразделение симплекса является подразделением «красного»4 типа, если оно сохраняет углы. В указанной работе для произвольного целого п 2 доказывается невозможность разбить невырожденный n-мерный симплекс при помощи «красного» подразделения на конгруэнтные симплексы меньшего размера.

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

Теорема 3. Пусть G I3 - невырожденный (имеющий ненулевой объем) симплекс. Не существует такого разбиения S на два меньших симплекса Si и 2, каждый из которых может быть получен подобным преобразованием

Доказательство. Обозначим ребра S через ХІ, І Є {1,..., 6}. Без умаления общности положим XQ = 1. (Возможно пропорционально изменить длины всех ребер симплекса, чтобы добиться такой нормировки.) При разбиении симплекса на два меньших, на одном из ребер S фиксируется точка, отличная от концов ребра, которая соединяется с двумя оставшимися вершинами симплекса. Без потери общности будем считать, что эта дополнительная точка располагается на ребре я?б, и разбивает его на два меньших отрезка, которые мы обозначим Xj и х%. Отрезки, соединяющие эту точку с двумя другими вершинами S обозначим XQ и X\Q. Таким образом, по построению, симплекс Si задается ребрами

X\, %2, #з, Ж7, XQ и ЖЮ, а 2 задается ребрами Х\, Жз, ж4, #8, XQ и X\Q.

Предположим теперь, вопреки утверждаемому в теореме, что Si и S2 подобны исходному симплексу S. Это означает, что существуют такие коэффициенты пропорциональности 0 k\, k,2 1, что выполняются соотношения подобия вида Xi = km Xj. Здесь ХІ — ребро STO, а Xj — соответствующее ребро S.

Соответствие между ребрами симплексов S и STO можно указать следующим способом. Пронумеруем произвольным образом вершины каждого симплекса STO числами от 1 до 4. Каждая перестановка номеров вершин определит соответствие ребер S и STO. Всего существует 4! вариантов соответствия вершин симплексов, и, следовательно, есть 4! -4! = 576 вариантов разбиения S на Si и S2

В англоязычной литературе: red refinement с указанием соответствия вершин. Каждый такой вариант задает систему линейных уравнений, в которых переменными являются величины Х{. К каждой системе добавляются еще два уравнения xj + х8 = XQ и XQ = 1, справедливые по построению.

Последовательное рассмотрение полученных 576 систем уравнений показывает, что 380 из них содержат уравнение вида (1 — кт) Xj = 0, которое не может соответствовать невырожденному симплексу. Проверив оставшиеся 196 систем, убеждаемся что все они являются несовместными.

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

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

Набору симплексов (симплициальному комплексу) будем сопоставлять четырехстолбцовую таблицу инциденций, в которой каждая строка содержит множество вершин одного из симплексов, а число строк равно числу рассматриваемых симплексов (строки, дублирующие представление одного симплекса исключаются). Таблицы, отличающиеся порядком строк или/и порядком вершин в строках, представляют один и тот же симплициальный комплекс; такие таблицы считаем эквивалентными, так что все множество таблиц распадается на классы эквивалентных таблиц, называемые табличными классами. Количество элементов (таблиц) в табличном классе равно (2А)кК\, где К — число симплексов рассматриваемого комплекса. Любая таблица данного табличного класса называется его представителем; таблица полностью определяет табличный класс. Соединением двух таблиц назовем приписывание строк второй таблицы под строками первой с исключением дублирующих строк (порядок исключения значения не имеет). Пусть УХ — множество правильных симплици-альных комплексов, содержащее объединение и пересечение любых двух из них, а N — множество соответствующих им табличных классов. Введем операцию сложения табличных классов в N. Под суммой двух табличных классов подразумевается такой табличный класс, представителем которого является таблица, полученная соединением двух таблиц — представителей этих классов. Операцию сложения табличных классов обозначим знаком -j_ .

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

Итак, предъявляя таблицу инциденций, можно применять слова «табличный класс», а также слова «симплициальный комплекс»; этой вольностью иногда будем пользоваться в дальнейшем. Предположим, что в пространстве R3 проведены плоскости, параллельные координатным плоскостям и находящиеся на единичном расстоянии друг от друга; будем считать, что множество этих плоскостей содержит координатные плоскости. В результате получим единичные (замкнутые) кубы, объединение которых исчерпывает R3.

В пространстве R3 трехмерных векторов рассмотрим множество Z3 векторов с целочисленными компонентами; через Z32 обозначим множество векторов с четными компонентами.

Каждая из только что перечисленных таблиц относится к одной из шести граней куба; каждая таблица определяет группу из четырех симплексов с «основанием» на соответствующей грани (обозначим ее Г). При таком подразделении каждая из граней представляет собой квадрат с проведенными в нем диагоналями. Симплициальное подразделение куба с такой топологической структурой (и с такой геометрией) будем называть подразделением вида Л.

В дальнейшем рассматривается совокупность Qi упомянутых кубов, содержащихся в некоторой области Q пространства М3; считая, что Уі = {1 r{s)Qi J s Є (Ці}, IVh =11 Qi Будем считать, что любой куб из рассматриваемой совокупности кубов Qi имеет симплициальное подразделение вида Л: подразделение любого из них может быть получено параллельным переносом рассматриваемого куба на вектор s Є Qi. Ясно, что объединение рассматриваемых подразделений всех кубов совокупности Qi является топологически правильным симплициальным комплексом; этот комплекс обозначим 9JTi.

Каждая из шести групп симплексов, определяемых соответствующими таблицами , і = 1,2,..., 6, допускает два варианта укрупнения; например, первая из этих групп (характеризуемая таблицей 1) допускает такие варианты укрупнения:

Заметим, что каждое из этих укрупнений сохраняет топологическую правильность подразделения куба Q1 (они не требуют каких-либо изменений в осталь 69 ных группах); при этом вместо двух диагоналей на рассматриваемой грани Г сохраняется лишь одна из них. Однако, для сохранения правильности подразделения, получаемого из 9JTi, необходимо произвести аналогичное укрупнение еще в одном кубе — а именно, в кубе, для которого Г — общая грань с кубом Q\. Такое «совместное» укрупнение будем называть элементарным укрупнением.

Очевидно, что элементарные укрупнения носят локальный характер в 9JTi и приводят к правильному симплициальному подразделению (они не требуют каких-либо дополнительных преобразований для сохранения правильности получаемого симплициального комплекса).

Теперь преобразуем таблицу инциденций \ перестановкой строк; в результате получится новая таблица инциденций Si, которая будет представлять прежний табличный класс и определять прежнее симплициальное подразделение куба Q\:

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

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

Многие важные в теоретической и прикладной математике задачи приводят к необходимости рассмотрения подразделения некоторой области в эвклидовом пространстве на непересекающиеся элементы. В число таких задач входит аппроксимация функций, заданных на конечных областях в Rn. Типичным вариантом подразделения конечной области в эвклидовом пространстве является задание правильного симплициального подразделения, т.е. такого, что никакая вершина ни одного образующего подразделение симплекса, не может оказаться во внутренней точке одномерного ребра другого симплекса. Симплициальное подразделение областей пространства R2 представляет собой триангуляцию. При компьютерной обработке информационных потоков насущной потребностью является возможное уменьшение объема пересылаемых и обрабатываемых данных. Применительно к методам, использующим симплици-альное подразделение, эта необходимость приводит к задаче локального укрупнения подразделения. В одномерном случае, локальное укрупнение подразделения осуществляется тривиальным образом, простым выбрасыванием лишних узлов. Получающаяся в результате такой операции сетка является, вообще говоря нерегулярной, что может несколько усложнить решение задачи аппроксимации функции, заданной на подразделенной области. Вопросы, возникающие при применении спалайн-аппроксимации на нерегулярной сетке, были рассмотрены, например, в работах [15, 27].

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

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

Попытки распространить аналогичный подход на симплициальное подразделение областей большего числа измерений наталкивается на дополнительные сложности. Одна из причин невозможности прямого обобщения триангуляции специального вида заключается в том, что уже в R3 никакой невырожденный симплекс невозможно разбить на два меньших, каждый из которых подобен исходному большему. Соответствующее утверждение было сформулировано в [5]. В той же работе предлагается один из вариантов выхода из сложившейся ситуации, который приводит к способу симплициального подразделения плоского слоя. Трехмерный слой разбивается на призмы с треугольными основаниями, а каждая призма в свою очередь разбивается на три симплекса. Для завершения описания способа специального симплициального подразделения требуется указание того, каким именно образом плоский слой разбивается на призмы, и как следует разделять каждую призму на симплексы, чтобы разбиения соседних призм было согласовано. Оба этих вопроса решаются в [5] конструктивно. Во-первых, описывается разбиение слоя на призмы, являющееся естественным обобщением триангуляции специального вида. Во-вторых, предлагается пара методов, позволяющих согласованно разбить все призмы на симплексы. Также приводится доказательство корректности означенных методов.

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

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

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

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

В качестве средства разработки был выбран объектно-ориентированный язык программирования Java [65]. Объектная ориентированность языка позволяет наглядно выразить зависимости таких объектов как точка, дуга, симплекс и подразделения разных видов, включая зависимости наследования. Другой особенностью языка Java, повлиявшей на его выбор, является поддержка технологии Streams, появившейся в стандартной библиотеке, начиная с восьмой версии [67].