Сплайн-всплесковая обработка потоков структурированной информации

СПЛАЙН-ВСПЛЕСКОВАЯ 
ОБРАБОТКА ПОТОКОВ 
СТРУКТУРИРОВАННОЙ 
ИНФОРМАЦИИ

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

2-е издание

Ответственный редактор  
Ю. К. Демьянович

УДК 519.6
ББК 22.19
С71

С71
Сплайн-всплесковая обработка потоков структурированной
информации / И. Г. Бурова, Ю. К. Демьянович, Т. О. Евдокимова,
О. Н. Иванцова; отв. ред. Ю. К. Демьянович. 2-е изд. — СПб.: Изд-во
С.-Петерб. ун-та, 2021. — 331 с.
ISBN 978-5-288-06103-5

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

УДК 519.6
ББК 22.19

ISBN 978-5-288-06103-5

©
Санкт-Петербургский
государственный университет, 2021

©
И. Г. Бурова, Ю. К. Демьянович,
Т. О. Евдокимова, О. Н. Иванцова, 2020

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Глава 1. Простейшие сплайн-всплесковые разложения. . . . . . . . . . .
14

§ 1. Всплески кусочно-постоянных сплайнов.. . . . . . . . . . . . . . . . . . . . . . .
14
§ 2. Сплайн-всплесковое разложение первого порядка .. . . . . . . . . . . . .
22
§ 3. Сплайн-всплески второго порядка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
§ 4. Об асимптотике координатных сплайнов .. . . . . . . . . . . . . . . . . . . . . .
59
§ 5. О двусторонних оценках координатных сплайнов .. . . . . . . . . . . . .
70
§ 6. Сплайн-всплесковые разложения третьего порядка .. . . . . . . . . . .
86

Глава 2. Всплески обобщенной гладкости . . . . . . . . . . . . . . . . . . . . . . . .
132

§ 1. Свойства сплайнов лагранжева типа . . . . . . . . . . . . . . . . . . . . . . . . . . .
132
§ 2. Псевдонепрерывность сплайнов лагранжева типа .. . . . . . . . . . . . .
140
§ 3. Обобщенная гладкость сплайнов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
151
§ 4. Сингулярные сплайны . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
172

Глава 3. Всплески эрмитова типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
186

§ 1. Всплесковое представление потоков первой высоты.. . . . . . . . . . .
186
§ 2. Всплески второй высоты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
194
§ 3. О всплесках третьей высоты.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
206
§ 4. О реализации сплайн-всплесков эрмитова типа . . . . . . . . . . . . . . . .
215

Глава 4. Обобщенные потоки и их обработка. . . . . . . . . . . . . . . . . . . . .
234

§ 1. Обработка целочисленных потоков .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
234
§ 2. Всплесковая обработка потоков в метрических
пространствах.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
258
§ 3. Вложенность пространств и всплесковые разложения
на многообразии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
275

Дополнение. О вложенных симплициальных подразделениях . . .
293

Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
316

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

3

ВВЕДЕНИЕ

Постоянный рост объема числовых информационных потоков стимулирует дальнейшее развитие и совершенствование средств их обработки.
Структура и характер этих потоков существенно зависят от области человеческой деятельности (экономика, медицина, техника и т. п.), от средств
и способов получения информации, от качества каналов связи и скорости их обработки. Большая часть подобных потоков не обрабатывается
из-за невозможности извлечения полезной информации в приемлемое время или по причинам экономической нецелесообразности. Таким образом,
увеличение скорости и качества обработки числовых информационных потоков остается актуальной задачей. Последнее время во многих способах
обработки этих потоков (методах дискретного преобразования Фурье, различных средствах фильтрации, методах вэйвлетного разложения) наблюдается тенденция учитывать дополнительную информацию о потоках и
создавать адаптивные алгоритмы. При классических способах вэйвлетной
обработки как исходный поток, так и результат обычно приходится ассоциировать с равномерными сетками. Применение неравномерной адаптивной сетки в случае быстро меняющегося числового потока (адаптивность
по «временн´ой» переменной) в таких методах весьма затруднительно. Заметим, что предложенные ранее сплайн-всплесковые (вэйвлетные) разложения свободны от перечисленных недостатков.
Числовой поток, ассоциируемый с некоторой одномерной сеткой (сеткой на интервале вещественной оси), принято называть одномерным. Одномерные числовые потоки возникают при дискретизации (и оцифровке)
некоторого физического параметра, поступающего от аналогового устройства. При этом упомянутая вещественная ось является осью времени (отсюда понятие «временн´ой» переменной). В ряде случаев поток приходится ассоциировать и с пространственной сеткой. В качестве примера можно
рассмотреть значения температуры нагретой детали в априори заданных

5

Введение

точках. Совокупность этих точек образует упомянутую пространственную
(двумерную) сетку, точки являются узлами этой сетки. О равномерности такой сетки говорить вряд ли возможно: выбор узлов может зависеть
от конфигурации детали, условий нагревания, условий измерения и т. п.
Нетрудно представить ситуацию, когда потребуется трехмерная пространственная сетка: измерение светимости определенных точек внутри полупрозрачного нагретого объекта (например, шарового слоя звезды в астрофизике). Совокупность измерений в упомянутых узлах в определенные
моменты времени удобно рассматривать как пространственно-временной
поток (при большом количестве узлов сложнее рассматривать эти измерения как набор отдельных одномерных потоков).
Общая схема сплайн-всплескового (вэйвлетного) разложения состоит в
следующем:
1) для экономной обработки и передачи исходного информационного
потока исходная сетка адаптивно укрупняется;
2) по исходной и вложенной в нее (укрупненной) сеткам строятся ассоциированные с сетками линейные пространства, обладающие соответствующим свойством вложенности;
3) упомянутое объемлющее пространство проектируется на вложенное,
давая сплайн-всплесковое (вэйвлетное) разложение;
4) результатом являются основной поток (ассоциированный с укрупненной сеткой) и всплесковый (вэйвлетный) поток.
Цель данной книги — в дальнейшей разработке предложенного ранее
сплайн-всплескового (вэйвлетного) подхода, совершенствование адаптивных алгоритмов декомпозиции/реконструкции, учитывающих пространственную и временн´ую структуру исходного информационного потока.
Остановимся более подробно на предыстории рассматриваемых методов. Информационные потоки большой плотности и объема возникают
при решении суперсложных задач на современных параллельных вычислительных системах. Заметим, что скорость обработки таких потоков еще
не позволяет своевременно решать задачи, связанные с прогнозом развития землетрясений, цунами, ураганов, метеоритной опасности и т. п., а
также решать задачи прогноза техногенных катастроф. Очевидно, что исследования в области способов обработки числовых потоков актуальны.
Основная задача такой обработки — сокращение объема числового потока за счет выявления и отбрасывания несущественных (с той или иной
точки зрения) частей. Обработка числового потока может производиться в двух направлениях: сохранения аппроксимации и сохранения основных спектральных характеристик. Классическим аппаратом обработки в
первом случае являются сплайны, а аппаратом обработки во втором слу

Введение
7

чае служат всплески (за рубежом чаще употребляется термин вэйвлеты
(wavelets)). Оказалось, что сплайны и всплески тесно связаны между собой: каждая цепочка вложенных пространств минимальных сплайнов порождает всплесковое разложение. Поскольку мощность множества упомянутых цепочек — континуум, то такова же мощность множества предлагаемых всплесковых разложений. Удивительно, что все они находят простую реализацию в виде явно выписываемых формул декомпозиции и реконструкции. Кроме того, эти всплесковые разложения наследуют хорошо исследованные асимптотически оптимальные (по N-поперечнику) аппроксимацинные свойства сплайнов. Правда, в случае неравномерной сетки формулы несколько усложняются (они зависят и от рассматриваемой
сетки), но неравномерная сетка весьма существенна для аппроксимации
функций с особенностями.
К настоящему моменту опубликовано много исследований в области
вэйвлетов (см. [9–16, 18, 20, 27, 31, 36–39, 43, 46, 47, 49–52, 55, 60, 61]).
Имеется ряд книг по теории вэйвлетов, среди которых особого упоминания застуживают труды И. Добеши «Десять лекций по вэйвлетам» [27],
К. Чуи «Введение в вэйвлеты» [46], С. Малла «Вэйвлеты в обработке
сигналов» [31], И. Я. Новикова, В. Ю. Протасова, М. А. Скопиной «Теория
всплесков» [36]. Эти исследования в основном отражают классический
подход к вэйвлетам, который базируется на различных вариантах преобразования Фурье, применямых к кратномасштабному соотношению с
целью получить масштабирующую функцию и в конечном счете вэйвлетное разложение. Потребность строить вэйвлетные разложения для неинвариантных относительно сдвига областей привела Свелденса к лифтинговой схеме, а стремление не ограничиваться лишь одной масштабирующей
функцией породило понятие нестационарных всплесков (И. Я. Новиков).
Интерес к области всплесковых (вэйвлетных) разложений связан с широким применением этих разложений в теории информации и в задачах
обработки больших массивов чисел. Основными методами исследования
являются методы математического анализа, методы алгебры и функционального анализа, различные методы обработки числовых потоков [7, 30,
35, 40, 44, 45]. Информационные числовые массивы (называемые также
цифровыми сигналами или информационными потоками) столь велики,
что в первую очередь создаются средства их экономного компьютерного
представления, обработки, хранения и передачи по каналам связи. Для
достижения этих целей из информационного потока выделяют основной
поток (несущий основную информацию), уточняющий информационный
поток (его иногда называют вэйвлетным потоком) и поток с несущественной информацией (который обычно отбрасывают). Иногда последний по

Введение

ток вообще не рассматривается: в этом случае исходный поток должен
однозначно восстанавливаться по основному и вэйвлетному потокам. Вопрос о том, какая информация является основной, какая уточняющей, а
какая несущественной, выходит за рамки математических исследований и
решается в каждом отдельном случае специалистом предметной области.
Задача математических исследований состоит в том, чтобы предоставить
предметному специалисту достаточно широкий набор средств для выделения необходимых информационных потоков.
В простейшем случае исходный сигнал отождествляется с функцией,
которая задана на интервале (α, β) вещественной оси; дальше эту функцию называем первоначальной. Для компьютерной обработки строится
дискретный сигнал, представляющий собой сеточную функцию, определяемую как значения первоначальной функции (или результатов ее сглаживания) в узлах некоторой сетки (сеточную функцию и сетку назовем
исходными). Использование исходной сеточной функции позволяет построить приближение к первоначальной функции с помощью того или
иного аппарата аппроксимации или интерполяции. Линейное пространство таких приближений (будем называть его аналогично предыдущему — исходным пространством) затем представляют в виде прямой суммы пространств, одно из которых называют основным, а второе — вэйвлетным. Часто основное пространство связывают с сеткой, получающейся выбрасыванием узлов из исходной сетки, а подпространство вэйвлетов
определяют операцией проектирования исходного пространства на основное. Таким образом, порождается разложение упомянутого приближения
на основную и вэйвлетную составляющие. Центральными здесь оказываются два момента: вложенность основного пространства в исходное и
задание операции проектирования исходного пространства на основное.
Представления элементов этого разложения в базисах рассматриваемых
пространств порождают соответствующие соотношения между коэффициентами этих представлений. Соотношения, позволяющие перейти от коэффициентов базиса исходного пространства к коэффициентам базисов
основного и вэйвлетного пространств, называются формулами декомпозиции, а соотношения, дающие обратный переход, — формулами реконструкции.
Каждое из упомянутых выше пространств иногда также разлагают в
прямую сумму некоторых подпространств и, возможно, продолжают этот
процесс дальше; разложения подобного рода называются вэйвлет-пакетами.
Важнейшими вопросами, которые волнуют исследователей, являются
вычислительная сложность (объем используемых ресурсов вычислитель

Введение
9

ной системы: памяти, каналов передачи результатов, времени счета), свойства гладкости и устойчивости решения интересующих задач, аппроксимационные и интерполяционные свойства, а также ряд других свойств
(компактность носителя базисных функций, скорость их убывания на бесконечности — в случае некомпактного носителя и т. д.)
В случае, когда (α, β) = R1, а сетка — равномерная, удается применить мощный аппарат гармонического анализа (в пространстве функций
L2(R1) и в пространстве последовательностей l2). Этому случаю посвящено большое количество исследований (см., например, [31] и имеющуюся
там библиографию). Для цифровых потоков с резко меняющимися характеристиками (со сменой плавного поведения на скачкообразное и наоборот) весьма важно использовать неравномерную сетку, приспосабливаемую к обрабатываемому потоку. Публикаций, касающихся неравномерной
сетки и ситуаций, когда (α, β) не совпадает с вещественной осью, не много [11, 12, 38, 47]. Непосредственное применение гармонического анализа
в подобных случаях затруднительно.
Исследования в области обработки больших числовых массивов информации восходят к трем источникам, возникшим независимо друг от друга:
к классической теории сплайнов, к методу конечных элементов и к теории вэйвлетов. В соответствии с этим можно выделить по крайней мере
три направления развития теории обработки упомянутых массивов. Первое направление берет свое начало от работ Шонберга [57]; здесь исходным моментом является решение какой-либо задачи интерполяции (задачи
Лагранжа, Эрмита или Эрмита — Биркгофа) в классе функций с «кусочными» свойствами и с предопределенной гладкостью в узлах рассматриваемой сетки [1–6, 8, 17, 19, 21, 23, 24, 28, 29, 32, 34, 41, 42, 48, 53, 54, 56–59,
62]. Заметим, что если исходный массив числовой информации задан как
сеточная функция на мелкой сетке, то замена данной сеточной функции
на результат решения интерполяционной задачи для крупной сетки, являющейся подмножеством мелкой сетки, может рассматриваться как сжатие
исходного массива числовой информации. Аппроксимационные свойства и
вычислительная простота получаемых сплайнов всякий раз исследуются
дополнительно. Сюда относятся современные исследования по обобщенным сплайнам, так называемым ECT-B-сплайнам (см., например, [48]).
В таких работах для построения сплайнов на сеточных промежутках используются различные ECT-системы, которые при определенных условиях удается гладко «склеить» в узлах.
Второе направление опирается на аппроксимационные свойства рассматриваемых функций, где определение базисных функций связано с решением аппроксимационных соотношений, рассматриваемых как система

Введение

уравнений (эти исследования появились в связи с теорией метода конечных элементов [25, 33, 54, 61–63]). При таком подходе интерполяционные
свойства и алгоритмы минимизации вычислительной сложности (вложенность пространств и вэйвлетное представление цепочки вложенных пространств) приходится устанавливать дополнительно. Выбор порождающей
m + 1-компонентной вектор-функции ϕ(t), заданной на интервале (α, β),
определяет семейства конечномерных пространств на элементарных сеточных интервалах рассматриваемой (конечной или бесконечной) сетки
X = {xj}, X ⊂ (α, β), а выбор цепочки A векторов со свойством полноты
приводит к пространству (X, A, ϕ)-сплайнов. Условия гладкости эквивалентны определенным алгебраическим соотношениям между значениями
ϕ(t) (и ее производных) в узлах сетки и векторами цепочки A. Требование
максимальной гладкости сплайнов (при выбранной вектор-функции ϕ(t) с
отличным от нуля вронскианом из ее компонент) однозначно (с точностью
до постоянных отличных от нуля множителей) определяет цепочку A. При
этом однозначно определяется также пространство (X, A, ϕ)-сплайнов, которое в этом случае называется пространством Bϕ-сплайнов [54].
Третье направление — теория вэйвлетов — в основу кладет вычислительную простоту, отражением чего является кратномасштабное уравнение [27, 31, 36, 37, 39, 46, 49–52, 55, 60, 61]. Исследования в данном направлении приводят в первую очередь ко вложенности получаемых пространств и к вэйвлетному представлению соответствующей цепочки вложенных пространств, что уменьшает вычислительную сложность. Остальные свойства с б´ольшим или м´еньшим успехом исследуются дополнительно (см., например, [31]).
Предлагаемые в данной книге исследования в основном относятся ко
второму направлению, поскольку исходными здесь являются аппроксимационные соотношения. Они также связаны с третьим направлением, ибо
посвящены вэйвлетным разложениям. Наша цель состоит в том, чтобы по
системе вложенных неравномерных сеток построить вэйвлетное разложение цепочки вложенных пространств сплайнов и установить соответствующие формулы декомпозиции и реконструкции.
Представленное здесь направление исследований в основном ведет к
полному отказу от масштабирующих функций. Основу книги составляют результаты, полученные авторами, их учениками и последователями в
течение последнего десятилетия. В опубликованном ими цикле работ место кратномасштабного уравнения заняли калибровочные соотношения,
а источником для построения координатных функций рассматриваемых
сплайновых пространств явились аппроксимационные соотношения. Полученные здесь результаты приводят к нетрадиционным разложениям вло

Введение
11

женных сплайновых пространств, как правило, существенно более простым, чем те, которые использовались в классическом случае.
Рассматриваемый в монографии подход в отличие от классического
вносит ряд особенностей в построение всплескового (вэйвлетного) разложения, что нередко упрощает ситуацию по сравнению с классическим подходом. Перечислим эти особенности:
1. Основой построений служат аппроксимационные соотношения; это
в конечном счете позволяет получить сплайн-вэйвлетные разложения с асимптотически оптимальным порядком аппроксимации по Nпоперечнику стандартных компактов.
2. Отпадает необходимость построения масштабирующей функции и
кратномасштабного соотношения; нет нужды в «кратномасштабном
анализе».
3. Объемлющее пространство представляется в виде прямой суммы
вложенного в него пространства и пространства вэйвлетов; ортогональность этих пространств не требуется.
4. Проводимые построения не требуют введения скалярного произведения или нормы: достаточно рассматривать линейные пространства
функций с топологией поточечной сходимости. Нормированные пространства нужны лишь в оценках аппроксимации.
5. Предоставляется широкий выбор среди (вообще говоря, неполиномиальных) сплайновых пространств, которые определяются генерирующей функцией, фиксацией носителей координатных сплайнов и
полной цепочкой векторов.
6. Естественным образом (по предложенной в монографии схеме) вводятся, в том числе и неполиномиальные, сплайн-вэйвлетные разложения лагранжева типа, эрмитова типа, а также сплайн-вэйвлетные
разложения на дифференцируемом многообразии.
Монография содержит введение, четыре главы, раздел, озаглавленный
нами «Дополнение», приложение с рисунками и список литературы.
Первая глава посвящена сплайн-всплесковым разложениям на неравномерной сетке.
Рассмотрены пространства кусочно-постоянных сплайнов (называемых
сплайнами нулевого порядка) и их всплесковые разложения; исследуются всплесковые разложения для пространств сплайнов первого порядка
и второго порядка. Предметом анализа становятся асимптотика координатных сплайнов второго порядка на последовательности измельчающихся сеток, принадлежащих фиксированному классу квазиравномерности; а
также двусторонние оценки непрерывно дифференцируемых координатных сплайнов второго порядка. Обнаруживаются достаточные условия их