Нестационарные сплайн-вейвлеты в ГИС и САПР линейно-протяженных пространственных объектов*

Библиогафический список

1. Проектирование автомобильных дорог: справочник инженера-дорожника / под ред. Г.А.Федотова. - М. : Транспорт, 1989. - 437 с.

2. Бойков, В.Н. Сплайны в трассировании автомобильных дорог / В.Н. Бойков, Б.М. Шумилов. - Томск : Изд-во ГУ Томский ЦНТИ, 2001. - 164 с.

3. Отчет о НИР Трассирование автомобильных дорог с применением кривых Безье. - Томск. -2004. - 104 с.

S.R. LUST, M.A. ELUGACHEV, V.O. MOTUZ

DESIGNING OF MODERN HIGHWAY INTERSECTIONS

Analysis of designing methods of the highway interchange and the ways of improving the design decisions is presented in the article. The problem of development of more flexible horizontal curving models based on improvement of tracing methods is considered. After solving this problem it will be possible to increase curving continuity in comparison with traditional methods of transport intersection designing.

УДК 625.7 : 519.5

Б.М. ШУМИЛОВ, докт. физ.-мат. наук, профессор,

Э.А. ЭШАРОВ, аспирант

НЕСТАЦИОНАРНЫЕ СПЛАЙН-ВЕЙВЛЕТЫ В ГИС И САПР ЛИНЕЙНО-ПРОТЯЖЕННЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ*

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

Введение

Для описания линейно-протяженных объектов в ГИС и САПР традиционно используются геометрические примитивы типа отрезка прямой, дуги окружности и составленные из них кривые. Этих возможностей явно недостаточно для моделирования такого криволинейного пространственного объекта, как трасса автомобильной дороги. В частности, прямая линия является кратчайшим расстоянием между соседними точками. Однако существующие нормы проектирования ограничивают прямолинейное проложение дороги в плане, и проек-

* Работа поддержана региональным конкурсом грантов РГНФ, проект № 06-02-64202 а/Т и программой проведения фундаментальных исследований в области естественных, технических и гуманитарных наук, проект № 2.1.2.1276.

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

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

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

1. Методология построения модели

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

Так как в процессе проектирования ведется разбивка трассы в виде пикетов, то удобнее выражать переменные координаты X, У, Z точек этой трассы при помощи одного параметра I - текущей длины трассы, 0 < I < Ь. В этом случае на любом интервале трасса дороги в плане и продольном профиле описывается единственным сочетанием трех функций:

х = УКО, У = У2(0, г = Уэ(/).

Путь движущейся точки (в терминах дорожного проектирования точка -это автомобиль, а путь - его траектория, в первом приближении совпадающая с очертаниями трассы автомобильной дороги) определяется при помощи значений радиуса-вектора г = [х, у, г]Г, которые он принимает в последовательные моменты времени. Значение параметра I задает координатный вектор точки на трассе дороги:

г(1) = МО, У2(0, Уз(0Г.

В пакете программ автоматизированного проектирования автомобильных дорог (САПР «ТМогСАБ/ЯоАБ», ООО «Индорсофт», г. Томск) [3]) трасса автомобильной дороги описывается как набор отрезков прямой и дуг окружностей, к которым добавлены сопряжения кривых плана дугами клотоид и кривыми Безье, а также интерполяция кривых профиля кубическими сплайнами. В процессе редактирования плана и профиля пользователь производит операции с геометрическими элементами изображения явным образом - либо передвигая контрольные точки, либо прибегая к «прямому манипулированию» [4]. Тем не менее при создании кривых (и поверхностей) часто бывает полезным косвенный контроль пользователя, когда указываются лишь целевая функция и несколько ограничивающих условий, а затем компьютер самостоятельно определяет «лучший» геометрический элемент, удовлетворяющий обозначенным условиям. Такой процесс создания часто называют вариационным моделированием [5], поскольку в качестве целевой функции берется, как правило, минимум какого-либо интеграла, что составляет предмет вариационного исчисления.

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

Ь 2

минимизировать л У1 /)| & при данных ограничениях, для г = 1, 2, 3.

0

Нахождение кривой (или поверхности) с минимальной кривизной, удовлетворяющей заданным ограничениям, осуществляется с помощью метода конечных элементов [5], в котором в роли неизвестных выступает конечный набор чисел - коэффициентов линейной комбинации известных базисных функций и(1) = [ма(/), ..., ит(1)]. Например, функция уг(/) записывается так:

т

У г /1 ) = ^ Х]Ы] /1 )= и/^

] =1

где х = [хь... , хт\Т - множество неизвестных коэффициентов.

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

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

(2) оказывается плохо обусловленной для базиса В-сплайнов [7]. Эту плохую обусловленность можно объяснить тем, что каждая функция базиса В-сплайнов

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

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

2. Вейвлеты в анализе временных сигналов и пространственных полей

Термин «вейвлет» (в переводе - маленькая волна) ввели Гроссман и Морле в середине 80-х годов в связи с анализом свойств сейсмических и акустических сигналов [8, 9]. Вейвлеты стали необходимым математическим инструментом во многих исследованиях. Их используют в тех случаях, когда результат анализа некоего сигнала должен содержать не только перечисление его характерных частот (масштабов), но и сведения об определенных локальных координатах, при которых эти частоты проявляют себя. Таким образом, анализ и обработка нестационарных (во времени) или неоднородных (в пространстве) сигналов разных типов представляют собой основное поле применений вейвлет-анализа. Общий принцип построения базиса вейвлет-преобразования состоит в использовании масштабного преобразования и смещений. Любой из наиболее часто применяемых вейвлетов порождает полную ортонормирован-ную систему функций с конечным носителем, построенных с использованием масштабного преобразования и сдвигов. Именно за счет изменения масштабов вейвлеты способны выявить различие в характеристиках на разных шкалах, а путем сдвига проанализировать свойства сигнала в разных точках на всем изучаемом интервале. В силу свойства полноты этой системы можно сделать обратное преобразование. При анализе нестационарных сигналов, за счет свойства локальности, вейвлеты получают существенное преимущество перед преобразованием Фурье, которое дает только глобальные сведения о частотах (масштабах) исследуемого сигнала, поскольку используемая при этом система функций (синусы, косинусы или комплексные экспоненты) определена на бесконечном интервале.

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

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

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

3. Примеры построения систем базисных сплайн-вейвлетов

Один из конструктивных подходов к построению вейвлетов состоит в использовании базисных 5-сплайнов.

3.1. Пусть степень восполняющего многочлена равна нулю. Двухмасштабное соотношение для 5-сплайна 1-го порядка определяется следующим образом:

Рассмотрим этот случай подробнее. Пусть имеется одномерный дискретный сигнал S = {*;}/е2, 2 - множество целых чисел. Согласно (3), каждой паре элементов с индексами 2/ и 2/+1,/еЪ поставим в соответствие значения:

Эти два значения формируют два новых сигнала V = {//ег и W = {к/}/е2, один из которых является огрубленной версией исходного сигнала (каждой паре элементов S соответствует их среднее арифметическое), а другой содержит информацию (будем называть ее детализирующей), необходимую для восстановления исходного сигнала. Действительно:

52 / = V/ + V/ ,

*2/+1 = V/- - К; , ; е 2.

Поставим в соответствие сигналу S произвольный уровень разрешения 1. Выпишем рекуррентные формулы для вычисления элементов сигналов для любого разрешения г0 < 1:

^+1,2 / + ^+1,2/+1 +1,2 / ^+1,2/+1

V. . =-------—--------—— V  = -

',/~ 2 ’ ',/“ 2 ’

Н—1 2,...!>/0, vIl,/=*/, /е2.

Восстановление сигнала выполняется по формулам:

V+12/ = \/ + К,./ > К+1,2/+1 = \/ — >] 6 2>

= 70 >/0 + 1>...>/1 — 1.

Формулы (4) и (5) определяют, соответственно, прямое и обратное преобразование Хаара одномерного дискретного сигнала на любом уровне разрешения.

Коэффициенты разложения к,>/ называют вейвлет-коэффициентами. Данный класс вейвлетов называется вейвлетами Хаара [7-10] (рис. 1, а):

Кн

Система уравнений (3), (6) решается в явном виде и дает обратное соотношение вида

Фо

При этом соотношение (7) представляет собой ортогональное разложение пространства сплайнов на густой сетке на пространство сплайнов на прореженной сетке и пространство вейвлетов. В теории вейвлетов это свойство принято называть условием полуортогональности. Дополнительно, вейвлет Хаара обладает свойствами ортонормальности, то есть

С , (1, к = I,

] Кн(х — 1)Кн(х — к)^с = 5к =|о к ^ .

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

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

3.2. Пусть степень восполняющего многочлена равна единице. Двухмасштабное соотношение для 5-сплайна 2-го порядка имеет вид (рис. 1, б):

ФЛО = 2 ФД20 + Ф1

Соответствующий класс полуортогональных вейвлетов иногда называют вейвлетами Стремберга [7] (рис. 2, а):

Рис. 1. График функции мн

К сожалению, в отличие от случая Хаара не существует конечных формул разложения и восстановления сигнала вида (4), (5). Поэтому приходится обходиться приближенными соотношениями для главных коэффициентов разложения [10] либо прибегать к матричным методам обработки, реализованным в пакете МЛТЬЛБ [11].

В [10] было показано, что вейвлеты, обладающие свойством полуорто-гональности, могут быть построены на минимальном носителе [0, 2т-1], где т - порядок сплайна. В частности, для т = 2 получаем отрезок [0, 3]. Это противоречит случаю вейвлета Хаара, для которого носитель составляет отрезок [0, 1] с [0, 2]. Поэтому далее рассматривается попытка построения вейвлета Ч'гОО с меньшим носителем [0, 2] с [0, 3] (рис. 2, б).

а) б)

Рис. 2. График функции м^Х)

Предполагая выполненными условия симметрии, можно записать аналитическое выражение функции ^2(х) в виде:

2д0 х, 0 < х < 1

^( х) =

2

1

2д0 (1 — х) + 2д1 (2х — 1), — < х < 1

¥2(2 — х), 1 < х < 2.

Соотношение ортогональности принимает вид:

2

| (х)^2 (х — 1)ёх = 0.

1

Аналог соотношения разложения (7) принимается в виде

2 0 0

^ аг Ф1(2х — 0 = £ Ь/^2(х — 1) + ^ Ск Ф1 (х — к).

=—2 /=—1 к=—1

Для симметричного случая, когда Ъ.1 = Ь0, с_1 = с0, получаем следующую систему уравнений:

ао = 2Ьо 4о + ^ а1 = —2Ь0 4о + ^

, 1

а2 = Ьо 4о + 2 ^

которая очевидным образом приводит к соотношениям разложения для четных и нечетных индексов соответственно:

Ф1 (2 х — 2) + 2ф1 (2 х) + ф1 (2 х + 2) = —[2 (х — 1) + (х)] + Ф1( х — 1) + ф1 (х),

24о

— 1 1

Ф1 (2х — 1) = -—¥2(х) + -ФДх).

44о 2

Оставшийся свободным параметр д0 определяется из условий норми-

22

ровки ^[2(х)]2 ^х = 1 для средних и ^[2(х)]2 ^х = 2 отдельно для крайних о о

индексов. Полученные выше результаты можно подытожить в виде алгоритма разложения и восстановления сигнала аналогично (4), (5).

ТЕОРЕМА. Пусть имеется одномерный дискретный сигнал S = {5/}, / = 0,1, ..., т, т = 2к, к> 1. Согласно (8), вычисляются значения:

250 + 51 П: 51 — 250

v0 = 0-1, м0 = V 6—----°,

0 4 0 4

52/ —1 + 252/ + 52/ +1 ^ = ^13 52/—2 252/ + 52/ +1

V,- = —--------------;;—, V, .

/ 4 / 4  п т ] = 1,2,...,--------------------------------1,

2

25т + 5т—1 = ^6 _5т—1—25

“ 4 у “ 4

22

Эти значения формируют два новых сигнала К = {V,} и Ж = {м;}, / = 0,1, . , 2т-1, один из которых является огрубленной версией исходного сигнала, а другой содержит детализирующую информацию, необходимую для восстановления исходного сигнала в соответствии с формулами:

т

м ,• т

*2; = --^3’] — и...’т-1’

м0 + м>1

5 = у0 + V, +— г ’ если т — 2.

л/6

Недостающие значения определяются из трехдиагональной системы уравнений:

1

5, +----53 — V, + V, +--т= +--т=,

1 2 3 0 1 л/б ^3

1 1 +1  1 о т

2 52 у-1 + 52 у+1 + 2 52 у + 3 — V + ^+1 + ' 13 ' ’ ] — 1,2’.’У - 2’ 1 '

1 1 1

Т5т-3 + 5т-1 — Vm , + Vm + Мт + ~Т7 Мт .

2 2-1 2 ^3 2-1 У 6 2

Доказательство завершается указанием на наличие строгого диагонального преобладания в первой и последней строках системы уравнений (11).

Формулы (9), (10) и (11) определяют, соответственно, прямое и обратное преобразование одномерного дискретного сигнала на любом уровне разрешения.

Коэффициенты разложения му называем вейвлет-коэффициентами. Упоминание о данном классе вейвлетов в известной литературе отсутствует [7-10].

3.3. Пусть теперь степень восполняющего многочлена равна трем. Нетрудно заметить, что приведенные выше соотношения (3), (8) сохраняют силу и в случае неравномерной сетки. Дальнейшее продвижение в данном направлении существенно опирается на свойство симметрии базисных функций, которое выполняется только для случая равномерной сетки. Случай неравномерной дискретизации относится к так называемым нестационарным схемам, о которых в теории вейвлетов практически ничего не известно [7]. Поэтому далее рассматривается случай эрмитовых сплайнов [6].

Двухмасштабные соотношения для базисных эрмитовых сплайнов 3-й степени можно получить в виде (рис. 3):

1 1 3

Ф3 (/) — 2 Ф3 (2/) + Ф3 (2/ -1) + 2 Ф3(2/ - 2) + 4 ((2/) - у(2/ - 2)),

у(/) —1 у(2/ -1) -1 у(2/) -1 у(2/ - 2) -1 ((2/) - Ф3 (2/ - 2)).

2 8 8 8

Дальнейшее построение, как обычно, сводится к отысканию базиса для дополнения пространства сплайн-разложений на прореженной сетке до пространства сплайнов на густой сетке [12].

В частности, медленная сходимость базиса 5-сплайнов иллюстрируется верхним рядом картинок рис. 4 [7, С. 202]. На нем отображается, как вариационное решение для кривой минимальной энергии постепенно сходится за 1024 итерации. В случае базиса вейвлетов кривая сходится к решению намного бы-

стрее и принимает форму, близкую к конечной, уже через 64 итерации. Эффект от такой замены базиса иллюстрируется нижним рядом картинок на рис. 4.

Рис. 3. Графики функций: а - ф3(/), */293(2/), фз(2/-1), %у(2/); б - у(/), -%^(2/), /у(2/-1),

-Ифз

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

5-сплайны:

Вейвлеты:

«—^ ♦ -я

Число итераций: 0

4

16

64

256

1024

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

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

Библиографический список

1. Проектирование автомобильных дорог: Справочник инженера-дорожника / под ред. Г. А. Федотова. - М. : Транспорт, 1989. - 437 с.

2. Бойков, В.Н. Сплайны в трассировании автомобильных дорог / В.Н. Бойков, Б.М. Шумилов. - Томск : Изд-во ГУ Томский ЦНТИ. - 2001. - 164 с.

3. Система автоматизированного проектирования автомобильных дорог. «ReCAD». Руководства по применению, кн. 1-5. - Томск. - 2001. - 428 с.

4. Анцупов, А.А. Моделирование закруглений автомобильных дорог с использованием кривых Безье 5-й и 6-й степеней / А.А. Анцупов, Б.М. Шумилов, Э.А. Эшаров // Моделирование неравновесных систем: Материалы VIII Всероссийского семинара, 14-16 октября 2005 г. / под ред. В.В. Слабко; отв. за выпуск М.Ю. Сенашова. - Красноярск : ИВМ СО РАН, 2005. - С. 10.

5. Математика и САПР: В 2-х кн. / П. Жармен-Лакур, П.Л. Жорж, Ф. Пистр, П. Безье. - М. : Мир, 1989. - Кн. 2. - 264 с.

6. Завьялов, Ю.С. Методы сплайн-функций / Ю.С. Завьялов, Б.И. Квасов, В.Л. Мирошниченко. - М. : Наука, 1980. - 352 с.

7. Столниц, Э. Вейвлеты в компьютерной графике: [пер. с англ.] / Э. Столниц, Т. ДеРоуз, Д. Салезин. - Ижевск : НИЦ «Регулярная и хаотическая динамика», 2002. - 272 с.

8. Добеши, И. Десять лекций по вейвлетам / И. Добеши,. - М. : РХД, 2001. - 332 с.

9. Воробьев, В.И. Теория и практика вейвлет-преобразования / В.И. Воробьев, В.Г. Грибунин. -СПб : ВУС, 1999. - 290 с.

10. Чуи, Ч. Введение в вейвлеты: [пер. с англ.] / Ч. Чуи. - М. : Мир, 2001. - 412 с.

11. Дьяконов, В.П. Вейвлеты. От теории к практике / В.П. Дьяконов.- М. : СОЛОН-Р. - 448 с.

12. Попова, О. О. Построение системы базисных вейвлетов Эрмита для случая неравномерной сетки / О.О. Попова, Ю.Ю. Ручкина, Б.М. Шумилов // 4-я Всеросс. научно-практ. конф. студентов «Молодежь и современные информационные технологии». - Томск : ТПУ, 2006. -С. 37-38.

B.M. SHUMILOV, E.A. ESHAROV

NON-STATIONARY SPLINE-WAVELETS IN GIS AND CAD OF LINEAR-EXTENDED SPATIAL OBJECTS

The construction of system of basic spline-wavelets, suitable for a case with non-uniform discretization is described. Their application for variation modeling of curves of highways and other linear-extended spatial objects is offered.