СПОСОБ КАРТОГРАФИЧЕСКОГО ОТОБРАЖЕНИЯ ДВУХМЕРНЫХ РАСПРЕДЕЛЕНИЙ, ЗАДАННЫХ В ЦИФРОВОЙ ФОРМЕ
METHOD FOR CARTOGRAPHIC DISPLAY OF TWO-DIMENSIONAL DISTRIBUTIONS GIVEN IN DIGITAL FORM

Изобретение относится к области геодезии и картографии, в частности к картографическому моделированию при структурно-тектонических, геофизических, геохимических и т.п. исследованиях, при поисково-разведочных работах, инженерно-геологических изысканиях и т.д.
Известен оптический способ построения карт плотности распределения заданных графическим способом элементов (пятен, точек и линий) на исследуемой площади, включающий преобразование изображений дискретных графических распределений в непрерывную полутоновую форму с дальнейшим их представлением в форме изолиний эксинденсит (авторское свидетельство SU №365562, 1970 [1]). Однако данный способ не предусматривает обработку данных, заданных в цифровой форме.
Известен также способ картографического отображения двумерных распределений, заданных в цифровой форме, включающий преобразование изображений дискретных графических распределений в непрерывную полутоновую форму с дальнейшим их представлением в форме изолиний - эксинденсит, в котором с целью повышения точности при оптическом моделировании кодируют цифровые значения признака в заданной точке планшета оптическими символами - разновеликими пятнами с оптической плотностью, пропорциональной величине признака (авторское свидетельство SU №640113, 1978 [2]), что обеспечивает отображение двумерных распределений, заданных в цифровой форме.
Однако в большинстве случаев картографического отображения необходимо построение трехмерной модели рельефа, заданной в аналитическом виде при отображении результатов экологического состояния регионов (патент RU №2079891, заявка №92007530 от 23.11.1992 [3]), результатов ситуационного мониторинга объектов хозяйственной деятельности, например морских газонефтяных месторождений и терминалов, включая подводные исследования с отображением рельефа местности, что известными способами не обеспечивается.
Известен также способ построения трехмерной модели рельефа в виде кусочных сплайн-функций двух переменных. Исходной информацией служит типографская карта местности. Способ реализуется посредством геопространственной информационной системы (ГИС) (Берлянт A.M. Картография. - М.: Аспект Пресс, 2002. - 336 с. [4]). Эффективность аналитической обработки данных в геопространственных информационных системах в значительной степени зависит от возможностей, обеспечиваемых цифровой моделью рельефа (ЦМР), определяемой как совокупности высотных отметок, взятых в узлах некоторой регулярной или нерегулярной сети точек с заданными координатами [4]. В автоматизированных системах ЦМР служит основой получения прямой и косвенной информации о рельефе местности. Например, получение информации о морфометрических данных, включая вычисление углов наклона и экспозиции склонов; анализ видимости/невидимости; построение трехмерных изображений; профилей поперечного сечения; оценку формы склонов через кривизну их поперечного и продольного сечения; вычисление положительных и отрицательных объемов; генерацию линий сети тальвегов и водоразделов, образующих каркасную сеть рельефа, его структурных линий и иных особых точек рельефа: локальных минимумов (впадин) и локальных максимумов (вершин), седловин, бровок, линий обрывов и иных нарушений «гладкости» поверхности и т.д.
Источниками исходных данных для создания ЦМР, например, суши служат топографические карты, аэрофотоснимки, космические снимки, данные альтиметрических измерений, морские навигационные карты, данные промерных гидрографических работ. При этом принята следующая технология построения ЦМР (Суворов С.Г., Дворецкий Е.М., Коваленко С.А. Методика создания цифровых моделей рельефа повышенной точности // Информация и космос. №1, 2005 - с.52-54 [5]). Вся доступная информация оцифровывается. Полученные от разнообразных источников данные сводятся в единый набор координат точек и высот в них. Этот набор триангулируется (обычно методом Делоне). Процедура триангуляции дает систему непересекающихся треугольников, покрывающих рассматриваемую область поверхности земли (TIN-модель). В результате чего рельеф представляется многогранной (элементарная грань - треугольник) поверхностью с высотными отметками (отметками глубин) в узлах треугольной сети. Каждая грань этой поверхности описывается либо линейной функцией (полиэдральная модель), либо полиномиальной поверхностью, коэффициенты которой определяются по значениям в вершинах граней-треугольников. Эта технология в различных вариантах реализована во всех применяемых на практике ГИС.
При этом цель построения ЦМР - получение адекватной прямой и косвенной информации о рельефе в автоматизированных системах - не достигается. Источником всех недостатков этой технологии является этап триангуляции. При этом рельеф представляется в виде непрерывной функции, но с разрывами уже в соответствующей функции первого дифференциала на ребрах триангуляции (т.е. негладкая функция). Это противоречит модели рельефа, которая принята при построении топографических или навигационных карт, где поверхность рельефа представляется гладкой функцией. Кроме того, истинное назначение триангуляции - это задать порядок (сеть) по степени близости и взаимному расположению на множестве точек в плоскости, следовательно, при этом не учитывается взаимоотношение высот (глубин) между точками, что приводит к искажению пространственного направления и смещению в местоположении структурных линий рельефа. К основным видам структурных линий рельефа относятся гребневые и килевые линии, линии выпуклого и вогнутого перегибов. Под гребневыми линиями, или водоразделами, понимают линии плановой корреляции точек с максимальными высотами. Килевые линии (тальвеги, русла) соединяют точки с минимальными высотами. Кроме того, результат триангуляции резко и непредсказуемо изменится при изменении исходного набора точек, т.е. при удалении, добавлении точки (точек) или при изменении координат в исходном массиве точек. Это свойство триангуляции не позволяет «управлять» (редактировать) построением локальной формы рельефа. Кроме того, если ЦМР при этом построена с использованием триангуляции, то результаты вычислений дифференциалов рельефа различных порядков не являются достоверными. Можно констатировать, что в этой области геоинформатики существует проблемная ситуация, выражающаяся в том, что технология построения ЦМР с использованием процедуры триангуляции не позволяет достичь требуемой цели. Разрешение сложившейся проблемной ситуации можно путем применения таких средств построения ЦМР, которые не используют процедуру триангуляции и которые приводят к построению всюду гладкой поверхности, что и реализовано в известном техническом решении (патент RU №2415381 С1, 27.08.2011 [6]).
В известном способе картографического отображения двухмерных распределений, заданных в цифровой форме, включающим преобразование изображений дискретных графических распределений в непрерывную полутоновую форму с дальнейшим их представлением в форме изолиний - эксинденсит, в котором при оптическом моделировании кодируют цифровые значения признака в заданной точке планшета оптическими символами - разновеликими пятнами с оптической плотностью, пропорциональной величине признака, построение рельефа местности, в отличие от аналогов [1-5], построение рельефа местности выполняют путем интерполяции точек высот (глубин) в виде двумерных нерегулярных рациональных фундаментальных сплайнов, путем построения двумерной сплайн-функции, определяемой как тензорное произведение одномерных сплайнов [6].
Известный способ [6] включает интерполяцию точек высот (глубин) методами двумерных сплайн-функций, а конкретно в виде двумерных нерегулярных рациональных фундаментальных сплайнов (NURBS) (Голованов Н.Н. Геометрическое моделирование. - М.: Физматлит, 2002. - 472 с.[7]). Преимуществом данного способа является выполнение интерполяции точек высот в виде двумерных рациональных двумерных сплайн-функций NURBS, что позволяют построить гладкую поверхность для любой формы рельефа, даже для обрывов с отрицательным углом наклона. Во-вторых, поверхность рельефа задается аналитической зависимостью, т.е. конечным набором параметров фиксированного набора функций (полиномиальных сплайнов). Аналитическая форма задания рельефа, т.е. в виде суперпозиции аналитических функций от двух переменных, позволяет использовать весь аппарат дифференциальной геометрии для описания морфометрических свойств рельефа, например вычисления значения функции (высоту, глубину) или ее дифференциала (уклон) в любой точке (точках) области задания функции. В-третьих, NURBS обеспечивают возможность локального редактирования формы поверхности. Кроме того, для одной и той же области земли объем массива данных ЦМР при использовании NUBRS будет как минимум на порядок меньше, чем при традиционном точечном представлении. Применение NURBS повышает эффективность автоматизированных геопространственных систем за счет уменьшения времени обработки и требуемого объема памяти. Применение NURBS в вычислительной технике уже давно свершившийся факт - в графических пакетах всех операционных систем встроены алгоритмы обработки и визуализации NURBS, например в графических пакетах низкого уровня: DirectX и OpenGL для Windows. Однако при построении ЦМР возникают препятствия, связанные с эффектом возникновения в некоторых ситуациях нарушения монотонности в изменении поверхности - локальное появление ложных осцилляций. В известном способе это препятствие устраняется либо путем добавления новых точек в массив для интерполяции, либо путем использования методов изогеометрической аппроксимации сплайнами (Квасов Б.И. Методы изогеометрической аппроксимации сплайнами. - М. - Ижевск: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2006. - 416 с. [8]). В первом случае разрешение проблемы связано с повышением значимости работы эксперта в итерационной процедуре построения NURBS, во втором с существенным усложнением математических алгоритмов технологии.
В известном способе реализована технология построения ЦМР на основе NURBS в виде итерационной экспертной автоматизированной процедуры. В качестве языка программирования использован язык MatLab. В этой системе качество построения ЦМР определяется путем экспертного сравнения положения изолиний, вычисленных по NURBS, с положением соответствующих изогипс (изобат) на исходной карте.
В конкретной реализации известного способа источником информации о рельефе служат растровые карты.
В общем случае при аппроксимации профиля рельефа одномерными сплайнами задают значения двух первых производных в конечных точках разреза. Однако такая информация неизвестна, и получить ее на практике нельзя. Поэтому в качестве базового сплайна для аппроксимации профиля рельефа по разрезу использован простейший кубический сплайн с нулевыми граничными производными. Согласование первых двух дифференциалов ЦРМ для смежных прямоугольных участков карты обеспечивается перекрытием областей задания смежных NURBS.
Технология построения ЦМР в аналитическом виде на основе NURBS позволяет исключить этап триангуляции и тем самым исключить недостатки существующих технологий.
Однако при составлении ЦМР в обеспечение проведения геологических и сейсмических подводных исследований необходимо выполнять более подробную детализацию рельефа морского дна для выбора мест установки донной измерительной аппаратуры.
Отсутствие дифференцируемости у фрактальных функций приводит к необходимости использовать специфический аппарат для их представления. К такому аппарату можно отнести два вида инструментальной техники: системы итерирующих функций (Iterated Function Systems - IFS) и вейвлеты. Эти инструменты позволяют представить фрактальную функцию в виде предфрактала только как среднее (средне взвешенное значение) на дискретном множестве ячеек (точек), обычно регулярном. Площадь ячеек соответствует некоторому масштабу, кратному степени двойки. Для IFS вообще отсутствуют какие-либо принципиальные ограничения на значения масштаба. Для вейвлетов возможны все масштабы, меньшие некоторого максимального, определяемого только плотностью исходных данных.
Методы представления рельефа с помощью IFS и вейвлетов позволяют осуществить (Sahr K., White D., Kimerling A. Geodesic Discrete Global Grid Systems // Cartography and Geographic Information Science, Vol. 30, No. 2, 2003, pp.121-134. White. D. Global Grids From Recursive Diamond Subdivisions of The Surface of an Octahedron or Icosahedron. // Environmental Monitoring and Assessment, 4(1), 2000, pp.93-103. Bartholdi. J., Goldsman P. Continuous Indexing of Hierarchical Subdivisions of the Globe. // Int. J. Geographical Information Science, 15(6), 2001, pp.489-522. Goodchild M.F., Yang S. A Hierarchical Data Structure for Global Geographic Information Systems. // Computer Vision and Geographic Image Processing, 54(1), 1992, pp.31-44. Matos P. SMOS L1 Processor Discrete Global Grids Document - DEIMOS, Engenharia, 2003. - 64 pp. Lessig C. Orthogonal and Symmetric Haar Wavelets on the Sphere - University of Toronto, 2007. - 169 pp. Peter Schroder and Wim Sweldens. Spherical wavelets: Efficiently representing functions on the sphere. Computer Graphics Proceedings (SIGGRAPH 95), 1995, pages 161-172):
- двоичную генерализацию поверхности, заданную на регулярной сетке точек;
- имитацию увеличения масштаба разрешения исходной информации;
- выявление резких перепадов значений функции;
- вычисление фрактальных параметров функции;
- фильтрацию "шума".
При этом могут быть реализованы следующие операции:
- восстановления рельефа по дискретным измерениям;
- решения обратной задачи IFS;
- нахождения оптимальных непрерывных и дискретных семейств вейвлетов для представления рельефа.
Данные операции могут быть реализованы на методах описания рельефа с помощью функций Морса, графов Кронрода-Риба и комплексов Морса-Смейла, что обеспечит возможность:
- топологического кодирования форм рельефа;
- картографической генерализации;
- распознавания геоморфологических объектов;
- формальной классификации геоморфологических объектов;
- замощения поверхности рельефа семейством параметризованных (полиномиальных) функций, заданных на клетках Морса-Смейла;
- иерархически оценивать степень сходства двух карт рельефа, представляющих одну область, в одном или разных масштабах;
- оценки достоверности выделенных форм рельефа с учетом погрешности и мощности исходной информации;
- оценки степени достаточности набора точечных измерений для восстановления рельефа с заданной подробностью.
Задачей предлагаемого технического решения является расширение функциональных возможностей с одновременным повышением достоверности способа картографического отображения двумерных распределений, заданных в цифровой форме на основе алгоритмов восстановления рельефа по дискретным измерениям с использованием топологических карт; формирования графа Кронрода-Риба для кусочно-линейной поверхности; формирования комплексов Морса-Смейла для кусочно-линейной поверхности; упрощения кусочно-линейной поверхности с использованием полученной для нее структур графа Кронрода-Риба и комплексов Морса-Смейла; оценки фрактальных параметров рельефа на основе заданных структур графа Кронрода-Риба и комплексов Морса-Смейла.
Поставленная задача решается за счет того, что в способе картографического отображения двухмерных распределений, заданных в цифровой форме, включающем преобразование изображений дискретных графических распределений в непрерывную полутоновую форму с дальнейшим их представлением в форме изолиний - эксинденсит, в котором при оптическом моделировании кодируют цифровые значения признака в заданной точке планшета оптическими символами - разновеликими пятнами с оптической плотностью, пропорциональной величине признака, построение рельефа местности выполняют путем интерполяции точек высот и/или глубин в виде двумерных нерегулярных рациональных фундаментальных сплайнов, путем построения двумерной сплайн-функции, определяемой как тензорное произведение одномерных сплайнов, в котором, в отличие от прототипа, при построении рельефа местности определяют итерирующие функции и вейвлеты для представления фрактального рельефа, путем формирования для кусочно-линейной поверхности графа Кронрода-Риба и комплексов Морса-Смейла, при этом выполняют упрощения кусочно-линейной поверхности с использованием полученной для нее структур графа Кронрода-Риба и комплексов Морса-Смейла; оценку фрактальных параметров рельефа на основе заданных структур графа Кронрода-Риба и комплексов Морса-Смейла.
Сущность реализации предлагаемого способа поясняется чертежами.
Фиг.1. Иллюстрация последовательности первых шести предфракталов, в процедуре построения фрактальной линии («ковер Серпинского») с индексом ветвления, равным или большим трем для внутренних точек (удаляемые треугольники обозначены белым цветом).
Фиг.2. Графический результат рекурсивного применения матричных выражений.
Фиг.3. Иллюстрация определения расстояния между точкой х и подмножеством В, а также расстояния от подмножества В, и от В до А.
Фиг.4. Графическая иллюстрация действия IFS. Позициями обозначены: исходное изображение 1, три последующие итерации 2, 3, 4 соответственно.
Фиг.5. Начальные шаги генерации фрактальной поверхности с помощью IFS. Последовательности генерации 5, 6, 7, 8.
Фиг.6. Аппроксимация IFS предфрактала 9 другим предфракталом 10.
Фиг.7. Частотно-временная диаграмма для преобразования Фурье (фиг.7а) и масштабно-временная диаграмма для вейвлет-преобразования (фиг.7б). Частота 11, амплитуда 12, масштаб 13.
Фиг.8. Схема двумерной вейвлет-декомпозиции. Фиг.8а - Цепочка вычислений, фиг.8б - масштабное соответствие уровней декомпозиции. Исходные данные 14, первый уровень 15 декомпозиции, второй уровень 16 декомпозиции, третий уровень 17 декомпозиции.
Фиг.9. Примеры имитации рельефа фракталами.
Фиг.10. Поведение функции f(x, y) вблизи критической точки с координатами (0,0). Минимум - а, седло - с, максимум - d.
Фиг.11. График поверхности вблизи точки с координатами (0,0) для вырожденной критической точки типа «обезьяньего седла».
Фиг.12. Граф Кронрода-Риба. Фиг.12а, б - контурное изображение функции, для которой построен граф Кронрода-Риба, фиг.12в - граф Кронрода-Риба, фиг.12г - вложение графа Конрода-Риба в плоскость контурного рисунка функции: максимумы - точки I, J, G, минимумы - точки D, А, В, L, седла - точки Н, F, Е, С, K.
Фиг.13. Иллюстрация перехода от гладкой поверхности к симплициальному комплексу. Гладкая поверхность 18, симплициальный комплекс 19.
Фиг.14. Симплексы малой размерности.
Новые отличительные признаки заявляемого способа, заключающиеся в том, что при построении рельефа местности определяют итерирующие функции и вейвлеты для представления фрактального рельефа, путем формирования для кусочно-линейной поверхности графа Кронрода-Риба и комплексов Морса-Смейла, при этом выполняют упрощения кусочно-линейной поверхности с использованием полученной для нее структур графа Кронрода-Риба и комплексов Морса-Смейла; оценку фрактальных параметров рельефа на основе заданных структур графа Кронрода-Риба и комплексов Морса-Смейла, основаны на следующих постулатах.
Первый постулат (непрерывности) - рельеф Земли представляет собой непрерывную поверхность.
Второй постулат (топологический) - рельеф Земли представляет собой замкнутую двумерную поверхность в трехмерном пространстве, топологически эквивалентную двумерной сфере.
Эти два очевидных постулата определяют достаточно общие геометрические свойства рельефа. Для конструктивного математического описания необходимо иметь некий способ арифметизации геометрических объектов. Поэтому необходимо ввести вспомогательный постулат, использующий некоторую числовую систему, согласованную по своим свойствам с первыми двумя постулатами. В качестве такой числовой системы выберем наиболее привычную систему вещественных чисел, тогда постулат арифметизации поверхности рельефа можно записать в следующем виде.
<mrow><mrow><mo>{</mo><mrow><mrow><mo>(</mo><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub><msub><mrow><mtext>,x</mtext></mrow><mtext>2</mtext></msub><msub><mrow><mtext>,x</mtext></mrow><mtext>3</mtext></msub></mrow><mo>)</mo></mrow><mo>∈</mo><msup><mtext>R</mtext><mtext>3</mtext></msup><mrow><mo>|</mo><mrow><msup><mrow><mrow><mo>|</mo><mrow><msubsup><mtext>x</mtext><mtext>1</mtext><mtext>2</mtext></msubsup><mo>+</mo><msubsup><mtext>x</mtext><mtext>2</mtext><mtext>1</mtext></msubsup><mo>+</mo><msubsup><mtext>x</mtext><mtext>3</mtext><mtext>2</mtext></msubsup></mrow><mo>|</mo></mrow></mrow><mrow><mtext>1/2</mtext></mrow></msup><mo>−</mo><mtext>R</mtext><mo><</mo><msub><mtext>h</mtext><mtext>0</mtext></msub></mrow></mrow></mrow><mo>}</mo></mrow></mrow>
2
+
+
0
+
0
1
2
3
Третий постулат (арифметизации): рельеф это топологическое пространство с евклидовой метрикой
гомеоморфное двумерной сфере (S), где R - множество вещественных чисел, R∈R, R - положительные вещественные числа, h∈R - наибольшее возможное отклонение от R, 2h/R<<1. Для определенности положим, что вещественные координаты точки (x, x, x) соответствуют декартовой прямоугольной правой системе координат с начальной точкой в центре сферы.
Последний постулат позволяет перейти от чисто геометрического представления рельефа к его представлению в виде точечного множества.
Кроме того, предположим, что рельеф не имеет "отвесных и уклонов с отрицательными углами". Это условие выразим в виде следующего постулата.
Четвертый постулат (технический): всякий луч, выходящий из центра Земли, пересекает поверхность рельефа в единственной точке.
Множество математических поверхностей s, удовлетворяющих приведенным постулатам, обозначим символом Ξ (Ξ={s} или s∈Ξ). Заметим, что используя повороты вокруг центра, некоторые поверхности s из множества Ξ можно совместить поточечно. Кроме того, не будем различать поверхности, тождественные с точностью до масштабного множителя. Такие подмножества поверхностей образуют классы эквивалентности.
Поэтому в качестве Ξ будем рассматривать множество, состоящее только из представителей классов эквивалентности s.
Так, определенное множество математических поверхностей Ξ чрезвычайно обширно. По определению в него включены все непрерывные поверхности. Все непрерывные поверхности делятся на два непересекающихся класса: класс дифференцируемых - гладких (обозначим это множество символом
) и класс всюду не дифференцируемых - негладких ({'s}) поверхностей
В картографии и геоинформатике без аргументации неявно предполагается, что рельеф Земли - гладкая функция. Действительно, картографическое изображение рельефа оперирует гладкими линиями изобат и изогипс, что возможно только для гладких функций. Пятый постулат для картографического отображения рельеф: картографический рельеф Земли представляется гладкой поверхностью.
В работе (Мандельброт Б. Фрактальная геометрия природы. - М.: Институт компьютерных исследований, 2002. - 655 с.) приведено подробное обоснование утверждения того, что рельеф Земли представляет собой фрактальную поверхность.
Т
T
T
T
Фракталы можно рассматривать как множества точек, вложенные в пространство. Например, множество точек, образующих линию в обычном евклидовом пространстве, имеет топологическую размерность D=1 и размерность Хаусдорфа-Безиковича D=1. Евклидова размерность пространства равна Е=3. Так как для линии D=D, то линия, согласно определению Мандельброта, не фрактальна, что подтверждает разумность определения. Аналогично множество точек, образующих поверхность в пространстве с Е=3, имеет топологическую размерность D=2 и D=2. Мы видим, что и обычная поверхность не фрактальна независимо от того, насколько она сложна. Наконец, шар, или полная сфера, имеет D=3 и D=3.
d
+
d
Центральное место в определении размерности Хаусдорфа-Безиковича и, следовательно, фрактальной размерности D занимает понятие расстояния между точками в пространстве. В общем случае при δ→0 мера M=∑h(δ) равна нулю или бесконечности в зависимости от выбора d - размерности меры. Размерность Хаусдорфа-Безиковича D∈R множества ℑ есть критическая размерность, при которой мера M изменяет свое значение с нуля на бесконечность:
<mrow><msub><mi>M</mi><mi>d</mi></msub><mo>=</mo><mstyle displaystyle="true"><mo>∑</mo><mrow><mi>γ</mi><mrow><mo>(</mo><mi>d</mi><mo>)</mo></mrow><msup><mi>δ</mi><mi>d</mi></msup><mo>=</mo><mi>γ</mi><mrow><mo>(</mo><mi>d</mi><mo>)</mo></mrow><mi>N</mi><mrow><mo>(</mo><mi>δ</mi><mo>)</mo></mrow><msup><mi>δ</mi><mi>d</mi></msup><munder><mo>→</mo><mrow><mi>δ</mi><mo>→</mo><mn>0</mn></mrow></munder><mrow><mo>{</mo><mrow><mtable><mtr><mtd><mrow><mn>0,</mn><mi>d</mi><mo>></mo><mi>D</mi></mrow></mtd></mtr><mtr><mtd><mrow><mi>∞</mi><mo>,</mo><mi>d</mi><mo><</mo><mi>D</mi></mrow></mtd></mtr></mtable><mo>.</mo><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></mrow></mrow></mstyle></mrow>
d
d
Значение M при d=D часто конечно, но может быть равно нулю или бесконечности. Важно учесть, при каком значении d величина M изменяется скачком. Заметим, что в приведенном выше определении размерность Хаусдорфа-Безиковича фигурирует как локальное свойство, так как она характеризует свойства множества точек при бесконечно малом диаметре, или размере δ пробной функции, используемой для покрытия множества. Следовательно, фрактальная размерность D может быть также локальной характеристикой множества.
В соответствии с (1) для фрактальной поверхности логарифм нормированного спектра мощности возвышений как функция логарифма длины волны шероховатостей λ должен быть линейной функцией.
Неформальная интерпретация фракталов состоит в том, что граница фрактального объекта выглядит одинаково, в каком бы масштабе их не наблюдать. Это проявление свойства масштабной инвариантности.
T
T
T
Фракталы можно рассматривать как множества точек, вложенные в пространство. Например, множество точек, образующих линию в обычном евклидовом пространстве, имеет топологическую размерность D=1 и размерность Хаусдорфа-Безиковича D=1. Евклидова размерность пространства равна Е=3. Так как для линии D=D, то линия, согласно определению Мандельброта (Мандельброт Б. Фрактальная геометрия природы. - М.: Институт компьютерных исследований, 2002. - 655 с.), не фрактальна, что подтверждает разумность определения. Аналогично множество точек, образующих поверхность в пространстве с Е=3, имеет топологическую размерность D=2 и D=2.
T
Мы видим, что и обычная поверхность не фрактальна независимо от того, насколько она сложна. Наконец, шар, или полная сфера, имеет D=3 и D=3.
d
+
d
Центральное место в определении размерности Хаусдорфа-Безиковича и, следовательно, фрактальной размерности D занимает понятие расстояния между точками в пространстве. В общем случае при δ→0 мера M=∑h(δ) равна нулю или бесконечности в зависимости от выбора d - размерности меры. Размерность Хаусдорфа-Безиковича D∈R множества ℑ есть критическая размерность, при которой мера M изменяет свое значение с нуля на бесконечность.
d
Значение M при d=D часто конечно, но может быть равно нулю или бесконечности.
d
Важно учесть, при каком значении d величина M изменяется скачком. Заметим, что в приведенном выше определении размерность Хаусдорфа-Безиковича фигурирует как локальное свойство, так как она характеризует свойства множества точек при бесконечно малом диаметре, или размере δ пробной функции, используемой для покрытия множества. Следовательно, фрактальная размерность D может быть также локальной характеристикой множества. В действительности здесь существует несколько нюансов, заслуживающих рассмотрения. В частности, определение размерности Хаусдорфа-Безиковича позволяет покрывать множество "шарами" не обязательно одного и того же размера при условии, что диаметры всех шаров меньше δ. В этом случае d - мера есть нижняя грань, т.е. минимальное значение, получаемое при всех возможных покрытиях.
Тогда шестой постулат для рельефа Земли (апостериорный постулат физического рельефа): физический рельеф Земли адекватно представляется всюду недифференцируемой поверхностью - фракталом.
<mrow><mtext>Ξ</mtext><mo>=</mo><mrow><mo>{</mo><mover accent="true"><mi>s</mi><mo>˜</mo></mover><mo>}</mo></mrow></mrow>
Таким образом, физическая поверхность рельефа Земли является математическим объектом из множества Ξ={'s}, тогда как картографическое представление рельефа относится к гладким функциям
.
0
Важнейшим следствием является то, что любое сечение фрактальной поверхности будет также являться фрактальной линией. Для решения прикладных задач, важно отметить существенное различие между "вертикальными" сечениями поверхности 's и "горизонтальными". Линия пересечения 's с плоскостью, проходящей через центр 's ("вертикальное" сечение), всегда является фрактальной замкнутой одномерной простой линией. Такая линия топологически эквивалентна окружности. Другое дело "горизонтальное" сечение. Это сечение образует множество точек пересечения 's некоторой сферой с центром, соответствующим 's и с радиусом R+h, где |h|<h.
Множество точек такого пересечения тоже является фракталом, но этот фрактал имеет значительно более сложное устройство. Очевидно, что такое сечение может состоять из многих "замкнутых" связных изолированных между собой кусков - "береговых линий островов". Но не это главное отличие от "вертикального" сечения. "Горизонтальное" сечение приводит к линиям, значительно более сложно устроенным с топологической точки зрения. Каждый связный кусок "горизонтального" сечения топологически не эквивалентен окружности. Дело в том, что вблизи всякой точки пересечения фрактальной поверхности 's с секущей сферой число точек пересечения бесконечно. Поэтому вблизи каждой точки пересечения могут возникать "расщепления" простой линии. Таким образом, "горизонтальные" сечения 's дают некоторое множество несвязных линий, имеющих индекс ветвления, равный или больший трем. Поэтому фрактальную линию графически изобразить нельзя. Однако графически фрактал можно косвенно представить в виде некоторой бесконечной итерационной процедуры. На каждом шаге этой процедуры можно изобразить промежуточное состояние в построении фрактала. Такое промежуточное состояние называется предфракталом. Процедура построения линии, имеющей для внутренних точек индекс ветвления, равный или больший трем, поясняется примером построения линии С (называемой треугольный "ковер Серпинского") с индексом ветвления, равным или большим трем для внутренних точек, которая строится следующим образом: в равностороннем треугольнике со стороной, равной единице, проводятся средние линии, и из него выбрасываются внутренние точки треугольника, ограниченного средними линиями. Оставшееся множество состоит из треугольников первого ранга. С каждым из треугольников первого ранга проделывается та же операция: в нем проводятся средние линии и выбрасываются внутренние точки ограниченного ими треугольника. Подобным же образом поступают с каждым из девяти получившихся треугольников второго ранга и приходят к 27 треугольникам третьего ранга. Поступая так же и далее, для каждого натурального числа n получают множество, состоящее из 3" треугольников n-го ранга (фиг.1).
Оставшееся после выполнения всех этих операций множество С есть континуум. В общем случае, "горизонтальное" сечение всюду недифференцируемой поверхности представляет собой тонкую сеть с ячейками различного размера. Заметим, что "ковер Серпинского" обладает уникальным свойством: любая линия, вложимая в евклидову плоскость, вложима и в "ковер Серпинского". Данное свойство позволяет рассматривать "ковер Серпинского" в качестве универсальной линии на плоскости (Болтянский В.Г., Ефремович В.А. Наглядная топология. - М.: Наука, 1983. - 160 с.).
<mrow><mtext>L</mtext><mo>=</mo><mstyle displaystyle="true"><mrow><msubsup><mo>∫</mo><mtext>a</mtext><mtext>b</mtext></msubsup><mrow><msqrt><mrow><mtext>1</mtext><mo>+</mo><msup><mi>ƒ</mi><mrow><mtext>'2</mtext></mrow></msup><mrow><mo>(</mo><mtext>x</mtext><mo>)</mo></mrow><mtext>dx</mtext></mrow></msqrt></mrow></mrow></mstyle></mrow>
Одним из следствий фрактальности линии "вертикального" сечения 's, то есть отсутствия производной в любой ее точке, является ее неспрямляемость - неприменимость понятия длины для нее. Действительно, длина L гладкой плоской кривой (спрямляемой), заданной уравнением y=ƒ{x), определяется интегралом от производной:
, но для фрактальной кривой производная не определена, следовательно, не определена и длина. Очевидно, что понятие длины не определено и для более сложно устроенной линии "горизонтального" сечения 's.
Аналогичное утверждение справедливо относительно площади поверхности для односвязной области или всей 's - площадь для фрактальных поверхностей не определена. Действительно, для кусочно-гладких функций поверхностей с кусочно гладким краем (или без края) площадь поверхности обычно определяют с помощью следующей конструкции. Поверхность разбивают на мелкие части с кусочно-гладкими границами: в каждой части выбирают точку, в которой существует касательная плоскость, и ортогонально проектируют рассматриваемую часть на касательную плоскость поверхности в выбранной точке; площадь полученных плоских проекций суммируют; наконец, переходят к пределу при все более мелких разбиениях (таких, что наибольший из диаметров частей разбиения стремится к нулю). На указанном классе поверхностей этот предел всегда существует, и если поверхность задана параметрически кусочно гладкой функцией z=ƒ(x, y) над областью D на плоскости {х, у), то площадь S выражается двойным интегралом
<mrow><mtext>S</mtext><mo>=</mo><mstyle displaystyle="true"><mrow><munder><mo>∬</mo><mtext>D</mtext></munder><mrow><msqrt><mrow><mtext>1</mtext><mo>+</mo><msup><mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mtext>d</mtext><mi>ƒ</mi></mrow><mrow><mtext>dx</mtext></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mtext>2</mtext></msup><mo>+</mo><msup><mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mtext>d</mtext><mi>ƒ</mi></mrow><mrow><mtext>dy</mtext></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mtext>2</mtext></msup></mrow></msqrt><mtext>dxdy</mtext><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>2</mtext><mo>)</mo></mrow></mrow></mrow></mstyle></mrow>
Однако по определению поверхность 's всюду не дифференцируема, поэтому интеграл для площади не существует.
В первом приближении можно понимать фрактал как геометрическую фигуру, которая обладает свойством самоподобия, т.е. составленную из нескольких частей, каждая их которых подобна всей фигуре целиком. Небольшая часть фрактала содержит информацию о всем фрактале. Фракталы подобны самим себе, они похожи сами на себя на всех в любом масштабе - под каким бы увеличением не смотреть на фрактальные объекты, они будут все такими же фрагментированными и изломанными. Это свойство самоподобия приводит к тому, что для описания фрактальных мер и соотношений с необходимостью нужно использовать параметр масштаба рассмотрения фрактала. Степенная зависимость от масштаба вида (1) справедлива для:
- меры одномерного и двумерного фракталов;
- средних значений максимальных отклонений от прямой соединяющие две точки фрактала;
- соотношения периметра замкнутой фрактальной кривой и площади, ею охватываемой;
- распределение замкнутых областей при "горизонтальном" сечении 's по площади.
Свойство фрактальности проявляется в картографии в различных аспектах. Главный аспект состоит в том, что для отображения рельефа применяют длинную линейку масштабов карт. На каждом масштабе предполагается (неявно), что рельеф - гладкая поверхность. Это следует из того, что изогипсы (изобаты) - гладкие кривые. Однако рельеф одного и того же участка на картах разного масштаба различен в деталях. Причем с увеличением масштаба нет сходимости в положении изогипс (изобат), что и свидетельствует об отсутствии сходимости к некоторой гладкой поверхности. Именно это обстоятельство объясняет необходимость наличия процедуры картографической генерализации в технологии построения карт различного масштаба. Процедура генерализации осуществляется экспертным путем. В геоинформатике отсутствуют приемлемые автоматизированные алгоритмы картографической генерализации. Свойство фрактальности проявляется в математической зависимости (степенная функция) хода кривой пересеченности и используется для описания изрезанности поверхности рельефа. Алгоритм построения кривой пересеченности заключается в следующем. На карте некоторого масштаба берется произвольно, но равномерно распределенные по площади пары точек, отстоящих друг от друга на расстояние r. Определяется разность высот h каждой пары точек, и находится среднее арифметическое абсолютных величин этих разностей. Затем расстояние удваивается, утраивается и т.д.; на карте вновь выбираются пары точек, замеряются разности высот и находят средние значения, соответствующие увеличенному расстоянию между точками. Эти средние значения наносятся на график, на котором по оси абсцисс откладывается расстояние между точками, а по оси ординат - средние значения разностей высот. Кривая, вблизи которой укладываются точки на графике, является кривой пересеченности h=ƒ(r). Аппроксимируют эту зависимость степенной функцией, которая свойственна фрактальным поверхностям.
Наиболее прозрачно свойство недифференцируемости рельефа проявляется в оценках длины береговых линий по картам различного масштаба. Графическое изображение береговых линий на картах различного масштаба является по сути предфракталами различного уровня детализации, отображающими "горизонтальное" сечение 's, соответствующее нулевому уровню моря. При измерении береговой линии в постоянно укрупняющемся масштабе в рассмотрение попадают все более мелкие изгибы, и каждая новая деталь увеличивает общую длину берега. В случае фрактальности рельефа наблюдаемая длина должна возрастать неограниченно. Выполненные оценки длины береговой линии для различных участков побережья показали, что оценки длин растут с увеличением масштаба по степенному закону вида (1). В то же время график для гладкой кривой должен стремиться к постоянному значению.
К настоящему времени установлено, что фрактальными объектами являются длины рек, структура и границы водосборов и овражно-балочных сетей, распределения островов по площади (Мельник М.А. Фрактальный анализ морфологически однородных участков рек (на примере Томской области) // Материалы XIII научного совещания географов Сибири и Дальнего Востока. Иркутск: Изд-во ИГ СОРАН, 2007. Т.1. С.165-167. Tarboton D.G. Fractal river networks, Horton's laws and Tokunaga cyclicity // Journal of Hydrology. 187. (1996). 105-117. (new2/10.1.1.80.2625.pdf). Иванов А.В., Короновский А.А., Минюхин И.Н., Яшков И.А. Определение фрактальной размерности овражно-балочной сети города Саратова // Известия вузов. Прикладная нелинейная динамика. 2006. т.14. №2. с 64-73. Dodds P.S., Rothman D.H. SCALING, UNIVERSALITY, AND GEOMORPHOLOGY // Annu. Rev. Earth Planet. Sci. 2000. 28: 571-610 (new2/AnnRev.28.1.571.pdf). Turcotte D.L. Self-organized complexity in geomorphology: Observations and models // Geomorphology 91 (2007) 302-310).
2
Отсутствие дифференцируемости у фрактальных функций приводит к необходимости использовать специфический аппарат для их представления. К такому аппарату можно отнести: системы итерирующих функций (Iterated Function Systems - IFS) и вейвлеты. Эти математические инструменты позволяют представить фрактальную функцию в виде предфрактала только как среднее (средневзвешенное значение) на дискретном множестве ячеек (точек), обычно регулярном. Площадь ячеек соответствует некоторому масштабу, кратному степени двойки. Для IFS вообще отсутствуют какие-либо принципиальные ограничения на значения масштаба. Для вейвлетов возможны все масштабы, меньшие некоторого максимального, определяемого только плотностью исходных данных. Основной принцип IFS - представить самоподобный фрактал как композицию множества "мельчайших" копий самого себя. Рельеф может представляться и более сложными фрактальными конструкциями, чем самоподобный фрактал (Gagnon J., Lovejoy S., Schertzer D. Multifractal earth topography // Nonlin. Processes Geophys., 13, 2006, 541-570). IFS представляет собой относительно громоздкую теоретико-множественную конструкцию, поэтому ограничимся только общим схематическим описанием. Дадим пример общего выражения IFS для плоскости R:
<mrow><mtext>W</mtext><mrow><mo>(</mo><mtext>x</mtext><mo>)</mo></mrow><mo>=</mo><msub><mtext>w</mtext><mtext>i</mtext></msub><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>a</mtext><mtext>i</mtext></msub></mrow></mtd><mtd><mrow><msub><mtext>b</mtext><mtext>i</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>c</mtext><mtext>i</mtext></msub></mrow></mtd><mtd><mrow><msub><mtext>d</mtext><mtext>i</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>+</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>e</mtext><mtext>i</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>ƒ</mi><mtext>i</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>=</mo><msub><mtext>A</mtext><mtext>i</mtext></msub><mtext>x</mtext><mo>+</mo><msub><mtext>t</mtext><mtext>i</mtext></msub><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>3</mtext><mo>)</mo></mrow></mrow>
Отсюда, форма IFS для треугольного ковра Серпинского будет:
<mrow><msub><mtext>w</mtext><mtext>i</mtext></msub><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mtext>0</mtext><mtext>.5</mtext></mrow></mtd><mtd><mtext>0</mtext></mtd></mtr><mtr><mtd><mtext>0</mtext></mtd><mtd><mrow><mtext>0</mtext><mtext>.5</mtext></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>+</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mtext>1</mtext></mtd></mtr><mtr><mtd><mtext>1</mtext></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mtext>,</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>4</mtext><mo>)</mo></mrow></mrow>
<mrow><msub><mtext>w</mtext><mtext>i</mtext></msub><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mtext>0</mtext><mtext>.5</mtext></mrow></mtd><mtd><mtext>0</mtext></mtd></mtr><mtr><mtd><mtext>0</mtext></mtd><mtd><mrow><mtext>0</mtext><mtext>.5</mtext></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>+</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mtext>1</mtext></mtd></mtr><mtr><mtd><mrow><mtext>50</mtext></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mtext>,</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>5</mtext><mo>)</mo></mrow></mrow>
<mrow><msub><mtext>w</mtext><mtext>i</mtext></msub><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mtext>0</mtext><mtext>.5</mtext></mrow></mtd><mtd><mtext>0</mtext></mtd></mtr><mtr><mtd><mtext>0</mtext></mtd><mtd><mrow><mtext>0</mtext><mtext>.5</mtext></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mtext>x</mtext><mtext>2</mtext></msub></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>+</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mtext>50</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext>50</mtext></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>6</mtext><mo>)</mo></mrow></mrow>
Графический результат рекурсивного применения этих матричных выражений представлен на фиг.2.
Метрическим пространством (X, d) называется множество Х, на котором определена вещественная функция расстояния d:Х×Х→R со следующими свойствами:
d(a, b)≥0 для всех а, b∈Х;
d(a, b)=0, если и только если a=b для всех a, b∈Х;
d(a, b)=d(b, а) для всех а, b∈Х;
d(a, с)≤d(a, b)+d(b, с) для всех а, b, с∈Х.
n
Такие функции называются метрикой. Это значит, что метрическое пространство - это комбинация из двух элементов: множества точек из X∈R и расстояний между двумя точками множества d(a, b).
Пусть (X, d) полное метрическое пространство. Обозначим через ℜ(X) пространство, точками которого являются непустые компактные подмножества Х.
Расстоянием между точкой и подмножеством определяется как
d(x, B)=min{d{x, y):y∈B},
где В∈ℜ(X), х∈Х. Это определение иллюстрируется фиг.3.
Расстояние между двумя подмножествами определяется как d(A, В)=max{d(x, B):x∈A}.
Здесь метрика не симметрична, как показано на рис.1.8, d(A, В)≠d(B, A}. Для преодоления проблемы несимметричности этой метрики вводят метрику Хаусдорфа. Метрика Хаусдорфа на ℜ(X) определяется как
<mrow><mtext>h</mtext><mrow><mo>(</mo><mrow><mtext>A</mtext><mtext>,B</mtext></mrow><mo>)</mo></mrow><mo>=</mo><mtext>max</mtext><mrow><mo>(</mo><mrow><mtext>d</mtext><mrow><mo>(</mo><mrow><mtext>AB</mtext></mrow><mo>)</mo></mrow><mtext>,d</mtext><mrow><mo>(</mo><mrow><mtext>B</mtext><mtext>,A</mtext></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mtext> </mtext><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>7</mtext><mo>)</mo></mrow></mrow>
Метрика Хаусдорфа позволяет определить сходимость IFS путем вычисления расстояния между точками отображений для каждой итерации. Приведем еще несколько необходимых определений, гарантирующих сжимаемость отображений:
<mrow><mtext>W</mtext><mrow><mo>(</mo><mtext>S</mtext><mo>)</mo></mrow><mo>=</mo><mstyle displaystyle="true"><msubsup><mo>∪</mo><mrow><mtext>i</mtext><mo>=</mo><mtext>1</mtext></mrow><mtext>n</mtext></msubsup><mrow><msub><mtext>w</mtext><mtext>i</mtext></msub><mrow><mo>(</mo><mtext>S</mtext><mo>)</mo></mrow></mrow></mstyle></mrow>
.
Преобразование W:Х→Х на метрическом пространстве (X, d) называется сжимающим отображением (или сжатием), если существует такое число s, 0<s<1, что
d(W(x), W(y))≤s·d(x, y}, ∀x, y∈Х.
Число s называется коэффициентом сжатия.
<mrow><mtext>W:X</mtext><mo>→</mo><mtext>X|W</mtext><mo>=</mo><msubsup><mo>∪</mo><mrow><mtext>i</mtext><mo>=</mo><mtext>1</mtext></mrow><mtext>n</mtext></msubsup><msub><mtext>w</mtext><mtext>i</mtext></msub></mrow>
ƒ
Основные результаты теории сжимающих отображений связаны с неподвижными точками таких отображений. Пусть Х полное метрическое пространство и
, сжимающее отображение. Тогда существует единственная точка x∈Х, такая, что для любой точки x∈Х
<mrow><msub><mtext>x</mtext><mi>ƒ</mi></msub><mo>=</mo><mtext>W</mtext><mrow><mo>(</mo><mrow><msub><mtext>x</mtext><mi>ƒ</mi></msub></mrow><mo>)</mo></mrow><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∪</mo><mrow><mtext>i</mtext><mo>=</mo><mtext>1</mtext></mrow><mtext>n</mtext></munderover><mrow><msub><mtext>w</mtext><mtext>i</mtext></msub><mrow><mo>(</mo><mrow><msub><mtext>x</mtext><mi>ƒ</mi></msub></mrow><mo>)</mo></mrow></mrow></mstyle><mo>=</mo><munder><mrow><mtext>lim</mtext></mrow><mrow><mtext>n</mtext><mo>→</mo><mi>∞</mi></mrow></munder><msup><mtext>W</mtext><mrow><mo>∘</mo><mtext>n</mtext></mrow></msup><mrow><mo>(</mo><mtext>x</mtext><mo>)</mo></mrow><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>8</mtext><mo>)</mo></mrow></mrow>
ƒ
Точка х называется неподвижной точкой или аттрактором отображения W.
n
Это определение подразумевает, что любое сжимающее отображение, примененное к любому множеству инициализации, всегда приведет к фиксированному конечному множеству. Система итерирующих отображений описывает множество сжимающих функций, которые действуют на множестве (в пространстве R), чтобы получить другое множество в том же пространстве или пространстве меньшей размерности. Общая запись IFS есть
<mrow><mtext>W</mtext><mrow><mo>(</mo><mo>⋅</mo><mo>)</mo></mrow><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∪</mo><mrow><mtext>i</mtext><mo>=</mo><mtext>1</mtext></mrow><mtext>n</mtext></munderover><mrow><msub><mtext>w</mtext><mtext>i</mtext></msub><mrow><mo>(</mo><mo>⋅</mo><mo>)</mo></mrow></mrow></mstyle><mtext>,</mtext><mtext> </mtext><mrow><mo>(</mo><mtext>9</mtext><mo>)</mo></mrow></mrow>
n
n
n
i
i
где (·) соответствует параметру пространства R, w - соответствует каждому отдельному сжимающему отображению {w:R→R|i=1,…,n}. Графически это можно рассматривать как показано на фиг.4. На фиг.5 и 6 представлены иллюстрации действия IFS на поверхности.
Вейвлеты как математическое средство для иерархического представления функций позволяют описать произвольную функцию в терминах грубого усредненного приближения и деталей различного масштаба.
Даже для схематичного формального описания двумерного вейвлет-преобразования требуется ввести огромное число определений. Необходимости этого нет, так как в настоящее время существует большой объем литературы по вейвлетам, например (Малла С. Вейвлеты в обработке сигналов. - М.: Мир, 2005. - 671 с. Блаттер К. Вейвлет-анализ. Основы теории. - М.: Техносфера, 2004. - 280 с. Добеши И. Десять лекций по вейвлетам. - Ижевск, НИЦ "Регулярная и хаотичекая динамика", 2001. - 464 с. Чуй Ч. Введение в вейвлеты. - М.: Мир, 2001. - 412 с.). Приведем лишь неформальное обоснование дискретных вейвлетов. Классическим инструментом анализа данных служит анализ Фурье, который можно использовать для того, чтобы обратить данные наблюдений в точке в форму, более удобную для анализа частот. Однако при использовании методов Фурье возникает одно затруднение: каждый коэффициент Фурье содержит полную информацию о поведении ряда лишь на одной частоте и никакой информации о его поведении на других частотах. Кроме того, методы Фурье трудно адаптировать ко многим ситуациям, имеющим практическое значение. Например, большинство встречающихся на практике временных рядов является конечными и апериодическими, в то время как дискретное преобразование Фурье можно применять только для периодических функций. Недостатки методов Фурье и необходимость обеспечить иерархическое представление функций, которое называется кратномасштабным анализом, послужили причиной разработки методов, в основе которых исследуемая функция представляется набором коэффициентов, каждый из которых несет ограниченную информацию и о положении, и о частоте функции (фиг.7).
Несмотря на существование широкого многообразия методов иерархического представления функций разработанная теория вейвлетов содержит арсенал чрезвычайно полезных средств, позволяющих осуществить иерархическое разложение функций эффективным и одновременно теоретически обоснованным способом. Если говорить в общем, то вейвлет-представление функций состоит из общего грубого приближения и уточняющих коэффициентов, позволяющих работать с функцией при различных масштабах.
Двумерные дискретные вейвлеты представляют собой семейство из четырех тензорных произведений (HH, HL, LH, LL) двух фильтров с некоторыми специальными свойствами: низкочастотного L и высокочастотного Н, параметризованных масштабными и сдвиговыми коэффициентами. Эти два фильтра являются одномерными дискретными вейвлетами. Исходными данными для двумерной вейвлет-декомпозиции служат скалярные функции, заданные на регулярной сетке точек (матрицы).
Процесс двумерной вейвлет-декомпозиции осуществляется по схеме, представленной на фиг.8.
Вейвлеты широко применяются для представления рельефа, заданного на регулярной сетке точек, в различных масштабах (Keitt Т.Н., Urban D.L. Scale-Specific Inference Using Wavelets // Ecology, 86(9), 2005, pp.2497-2504. Marchuk A.G., Simonov K.V. Detecting possible impact craters on Earth's surface using the DEM data proscessing. // Bull. Nov. Comp. Center, Math. Model. in Geoph., 10 (2005), 59-66. Swai C.J., Kirby J.F. An effective elastic thickness map of Australia from wavelet transforms of gravity and topography using Forsyth's method // GEOPHYSICAL RESEARCH LETTERS, VOL. 33 2006 78-82. Audet P. Directional wavelet analysis on the sphere: Application to gravity and topography of the terrestrial planets // JOURNAL OF GEOPHYSICAL RESEARCH, VOL. 116, 2011, 111-127. Tassara A., Swain С., Hackney R., Kirby J. Elastic thickness structure of South America estimated using wavelets and satellite-derived gravity data // Earth and Planetary Science Letters 253 (2007) 17-36). С помощью вейвлетов производят выявление резких перепадов в значениях функции, оценивают фрактальные параметры. Именно связь между коэффициентами вейвлет-разложения фрактальными параметрами является основой применения вейвлет-преобразования при описании фрактальных функций (Berkner K. F Wavelet-based Solution to the Inverse Problem for Fractal Interpolation Functions // Fractal in Engineering '97, Springer-Verlag, 1997. - 123-135 pp. Struzik Z.R., Dooijes E.H., Groen F.C.A. The solution of the inverse fractal problem with the help of wavelet decomposition. In M M Novak, editor. Fractals reviews in the natural and applied sciences, pages 332-343. Chapman and Hall, February 1995). В настоящее время, практическое применение фрактального представления рельефа лежит в сфере имитации. Разработано большое число алгоритмов, имитирующих рельеф фрактальными поверхностями (Franceschetti G., Riccio D. Scattering, Natural Surfaces and Fractals - Academic Press is an imprint of Elsevier, 2007. - 307 pp.). На фиг.9 представлены два примера имитации фрактального рельефа.
Представление рельефа в виде фрактальной функции приводит к практической невозможности полного (во всех деталях и подробностях) описать и отобразить реальный рельеф каким-либо способом. Фрактальность рельефа проявляется в том, что поверхность рельефа представляет собой совокупность различных пространственных форм (неровностей) бесконечного набора пространственных масштабов. Однако в этом многообразии форм рельефа прослеживается закономерность в виде подобия изменчивости на различных масштабах.
Главная особенность картирования рельефа состоит в том, что рельеф на картах всегда представляется в виде гладкой функции. Наличие гладких изолиний на картах (изогипс, изобат) - свидетельство гладкости поверхности рельефа. В картографии фрактальность рельефа проявляется косвенно, через картографическую генерализацию. Традиционно рельеф представляется в виде карт различного масштаба. На картах большого масштаба отображаются более мелкие формы рельефа. Переход к меньшему масштабу требует применения законов картографической генерализации - сглаживания, утрирования, исключения форм рельефа малых размеров.
Различные формы рельефа в различных масштабах изучает наука геоморфология. В геоморфологии принято различные по размерам формы рельефа делить на порядки. В настоящее время выделяют до 12 порядков земной поверхности (Симонов Ю.Г., Болысов С.И. Методы геоморфологических исследований: Методология. - М.: Аспект Пресс, 2002. - 191 с.).
7
2
6
2
5
2
Например, к первой категории относятся континентальные выступы и океанические впадины (площадь форм 10 км), ко второй категории - части первых размером 10 км, к третьей - части элементов рельефа второй категории с размерами порядка 10 км. Деление проводится дальше, и каждая последующая категория занимает площадь, на порядок величин меньшую по сравнению с предыдущей. Здесь важно отметить то, что объектам каждой категории соответствуют свои пространственные масштабы карты в масштабах, которых эти объекты можно наблюдать. В других масштабах эти объекты не наблюдаемы. Кроме того, подобным по форме объектам из различных категорий дают разные имена, например холм, сопка, возвышенность, гора, горная область, хребет.
Эти особенности геоморфологической классификации накладывали отпечаток на применение математики в геоморфологических исследованиях. Практически для каждой именной формы рельефа разрабатывались свои способы и методы математического описания. В предлагаемом техническом решении использован более абстрактный математический аппарат - топология, в части элементов теории дифференциальной и алгебраической (комбинаторной) топологии. Применение этого аппарата позволяет единообразно математически описывать все формы рельефа независимо от масштабов и конкретных форм для отображения на карте или дисплее.
Алгебраическая топология обеспечивает связь между геометрией и алгеброй, между непрерывным и дискретным описанием рельефа, описанием структурных особенностей рельефа: точек минимумов, максимумов, линий сети тальвегов и водоразделов. Дифференциальная топология обеспечивает теоретическую основу, для выявления и согласования глобальных свойств поверхности рельефа с набором его локальных структурных особенностей. Все это позволяет осуществить реализацию конструктивных алгоритмов для ЭВМ.
Кроме того, аппарат дифференциальной и алгебраической топологии дает возможность приближенно восстановить поверхность по набору точечных данных, сравнивать степень близости двух представлений поверхности рельефа фиксированной области, как для одного масштаба, так и для различных масштабов. Получить логически аргументированный способ упрощения рельефа, как для целей генерализации, так и для удаления шума измерений.
1
n
1
n
1
n
Возможность приближенного представления фрактальной поверхности с помощью гладкой функций гарантирует теорема Вейерштрасса (Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления, т.3 - М.: Физматлит, 2001. - 662 с.), которая утверждает, что непрерывную функцию (подчеркнем, что достаточно только непрерывности, требования гладкости функции отсутствуют вообще) нескольких переменных ƒ(х,…,x) на замкнутом ограниченном множестве Q можно равномерно приблизить последовательностью полиномов: для любого ε>0 существует такой многочлен Р(х,…,x), что максимум его отклонения от ƒ(х,…,x) на Q не превосходит данного ε:
<mrow><munder><mrow><mtext>max</mtext></mrow><mtext>Q</mtext></munder><mtext>|</mtext><mi>ƒ</mi><mrow><mo>(</mo><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub><mtext>, </mtext><mo>…</mo><msub><mrow><mtext>, x</mtext></mrow><mtext>n</mtext></msub></mrow><mo>)</mo></mrow><mo>−</mo><mtext>P</mtext><mrow><mo>(</mo><mrow><msub><mtext>x</mtext><mtext>1</mtext></msub><mtext>, </mtext><mo>…</mo><msub><mrow><mtext>, x</mtext></mrow><mtext>n</mtext></msub></mrow><mo>)</mo></mrow><mtext>|</mtext><mo><</mo><mtext>ε</mtext><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mrow><mtext>2</mtext><mtext>.1</mtext></mrow><mo>)</mo></mrow></mrow>
Существует обобщение теоремы Вейерштрасса - теорема Стоуна (Stone M.N. The Generalized Weierstrass Approximation Theorem // Mach. Mag. 1948. Vol. 21. P.167-183, 237-254), в которой доказывается, что плотно не только множество многочленов от координатных функций, но вообще кольцо многочленов от любого набора функций, разделяющих точки. Следовательно, например, плотно множество тригонометрических многочленов.
Среди многообразия возможных гладких поверхностей следует выделить класс поверхностей, который будет представлять все остальные гладкие функции. В качестве такого класса целесообразно использовать класс функций Морса. Можно считать, что поверхности, принадлежащие классу функций Морса, наиболее "просто" устроены с математической точки зрения. Дело в том, что функции Морса имеют минимально возможный набор типов критических точек, а именно: точки локальных максимумов, минимумов и простые седловые точки.
2
Обычно рассматривают двумерные функции, заданные на плоскости. В нашем случае поверхность рельефа задается на сфере S. Это многообразие замкнуто и ограничено, поэтому компактно. Гладкие функции, заданные на произвольном многообразии, исследует теория Морса (Милнор Дж. Теория Морса. - М.: Издательство ЛКИ, 2011. - 184 с.). Эта математическая теория исследует отношение между топологией многообразия М (для нас М - сфера) и критическими точками скалярной функции ƒ:М→R, определенной на многообразии М.
1
n
Рассмотрим гладкую функцию ƒ:М→R на гладком многообразии М, и пусть х,…,x - гладкие регулярные координаты в окрестности точки p∈М. Точка p называется критической для функции ƒ, если дифференциал
<mrow><mtext>d</mtext><mi>ƒ</mi><mo>=</mo><mstyle displaystyle="true"><mo>∑</mo><mrow><mfrac><mrow><mtext>d</mtext><mi>ƒ</mi></mrow><mrow><msub><mrow><mtext>dx</mtext></mrow><mtext>i</mtext></msub></mrow></mfrac><msub><mrow><mtext>dx</mtext></mrow><mtext>i</mtext></msub><mtext> </mtext><mrow><mo>(</mo><mrow><mtext>10</mtext></mrow><mo>)</mo></mrow></mrow></mstyle></mrow>
обращается в ноль в точке р. Это эквивалентно условию обращения в ноль всех частных производных функции в данной точке. Критическая точка называется невырожденной, если второй дифференциал
<mrow><msup><mtext>d</mtext><mtext>2</mtext></msup><mi>ƒ</mi><mo>=</mo><mstyle displaystyle="true"><mo>∑</mo><mrow><mfrac><mrow><msup><mtext>d</mtext><mtext>2</mtext></msup><mi>ƒ</mi></mrow><mrow><msub><mrow><mtext>dx</mtext></mrow><mtext>i</mtext></msub><msub><mrow><mtext>dx</mtext></mrow><mtext>j</mtext></msub></mrow></mfrac><msub><mrow><mtext>dx</mtext></mrow><mtext>i</mtext></msub><msub><mrow><mtext>dx</mtext></mrow><mtext>j</mtext></msub><mtext> </mtext><mrow><mo>(</mo><mrow><mtext>11</mtext></mrow><mo>)</mo></mrow></mrow></mstyle></mrow>
невырожден в этой точке. Это эквивалентно условию, что матрица вторых частных производных имеет определитель, отличный от нуля. Согласно известной лемме Морса в окрестности каждой невырожденной критической точки всегда можно выбрать такие локальные координаты, в которых функция запишется в виде квадратичной формы:
<mrow><mi>ƒ</mi><mrow><mo>(</mo><mtext>p</mtext><mo>)</mo></mrow><mo>=</mo><mo>−</mo><msubsup><mtext>x</mtext><mtext>1</mtext><mtext>2</mtext></msubsup><mo>−</mo><msubsup><mtext>x</mtext><mtext>2</mtext><mtext>2</mtext></msubsup><mo>−</mo><mo>…</mo><mo>−</mo><msubsup><mtext>x</mtext><mtext>λ</mtext><mtext>2</mtext></msubsup><mo>+</mo><msubsup><mtext>x</mtext><mtext>λ</mtext><mtext>2</mtext></msubsup><mo>+</mo><mo>…</mo><mo>+</mo><msubsup><mtext>x</mtext><mtext>n</mtext><mtext>2</mtext></msubsup><mtext>.</mtext><mtext> </mtext><mrow><mo>(</mo><mrow><mtext>12</mtext></mrow><mo>)</mo></mrow></mrow>
Для каждой невырожденной критической точки число λ определено однозначно и называется ее индексом.
2
2
Гладкая функция ƒ:М→R является функцией Морса, если все ее критические точки невырождены. Замечательным фактом в теории критических точек является то, что для функций Морса на S известна полная классификация критических точек и геометрия в их окрестности. Оказывается, что вблизи критической точки p∈S всегда существует возможность выбора таких локальных координат х и у, что функцию вблизи этой точки можно записать в виде
<mrow><mi>ƒ</mi><mrow><mo>(</mo><mrow><mtext>x</mtext><mtext>,y</mtext></mrow><mo>)</mo></mrow><mo>=</mo><mo>±</mo><msup><mtext>x</mtext><mtext>2</mtext></msup><mo>±</mo><msup><mtext>y</mtext><mtext>2</mtext></msup><mtext>,</mtext><mtext> </mtext><mrow><mo>(</mo><mrow><mtext>13</mtext></mrow><mo>)</mo></mrow></mrow>
и все эти критические точки изолированы (лемма Морса).
На фиг.10 представлены графики поверхностей для всех четырех возможных критических точек вблизи точки с координатами (0,0).
Если гладкая функция на сфере не является функцией Морса, то она может иметь не только невырожденные критические точки типа (13), но и вырожденные типы критических точек, отличных от (13), например вырожденную критическую точку типа "обезьяньего седла", представленного на фиг.11.
Однако каждая ограниченная гладкая функция ƒ:М→R может быть равномерно аппроксимирована гладкой функцией g, не имеющей вырожденных критических точек. Более того, g можно выбрать так, чтобы i-ые производные g на компактном множестве К равномерно приближали соответствующие производные ƒ при i≤k. Функции Морса всюду плотны в пространстве всех гладких функций на гладком многообразии. Другими словами, любую гладкую функцию сколь угодно малым шевелением можно превратить в функцию Морса. При этом сложные вырожденные критические точки рассыпаются в объединение некоторого числа морсовских, т.е. невырожденных, особенностей. Это объясняется тем, что невырожденные критические точки типа (13) устойчивы относительно малых "шевелений" графиков (фиг.10), тогда как вырожденные критические точки при малых "шевелениях" соответствующих графиков либо исчезают, либо переходят в поверхность с некоторым набором невырожденных критических точек типа (13).
Большое значение имеет понятие индекса i(p) функции ƒ в критической точке p∈М, который определяется как число минусов в соответствующем уравнении (13). Критическая точка индекса 0, 1 или 2 называется минимумом седлом и максимумом, соответственно.
∞
Таким образом, всегда возможно любую гладкую функцию на сфере представить в виде функции Морса. Другими словами, всякой поверхности рельефа, представленной на карте, можно однозначно сопоставить некоторую функцию Морса. Далее, ради простоты изложения, будем считать, что рассматриваемые функции Морса принадлежат к классу - С дифференцируемых функций. Программно-математический аппарат, для реализации способа, включает математический аппарат описания структурных свойств гладких функций на основе алгебраической топологии.
Алгебраическая топология предоставляет набор инструментов, которые позволяют улавливать и описывать форму поверхности, определять, в чем поверхности совпадают или отличаются. Кроме того, в алгебраической топологии существуют классические инструменты, такие как теория Морса, гомотопий и гомологии, которые подходят для решения ряда вопросов, связанных с формой поверхности.
1
1
2
2
2
1
2
1
Цель алгебраической топологии предоставит средства для решения типичной задачи: распознавания (различения) объектов, принадлежащих категории G (в нашем случае гладких поверхностей). Алгебраическая топология, с помощью функтора F:G→G заменяет эту задачу аналогичной задачей распознавания объектов, принадлежащих категории G. Смысл замены состоит в том, что эта задача в категории G может оказаться легче. Следует отметить, что при переходе от категории G к категории G часть информации об объектах категории G, как правило, теряется. Однако функторы алгебраической топологии обеспечивают "хорошие" свойства такой замены, а именно: используемые параметры относительно легко вычислимы на ЭВМ; существуют простые способы выяснения различности или изоморфности объектов; при переходе от объекта Х к объекту F(X) не теряется много информации.
2
При этом функции двух переменных рассматриваются как раз не как функции двух переменных х и у, а как функции, заданные в точках двумерной области - S.
Алгебраическая топология обнаруживает резкое расщепление свойств функций двух переменных. Одни из них оказываются близки к свойствам функций одного переменного. Другие свойства функций двух переменных, наоборот, резко «двумерны». Кроме того, оказывается, что есть и понятия, которые зависят как от «одномерных», так и от «двумерных» свойств функций.
«Одномерные» свойства функции двух переменных описываются с помощью графа Кронрода-Риба, а свойства более высокой размерности с помощью комплексов Морса-Смейла.
Теория Морса (Милнор Дж. Теория Морса. - М.: Издательство ЛКИ, 2011. - 184 с.) устанавливает основы для описания множества критических точек гладкой функции, заданной на многообразии. Используя теорию Морса, можно определить способ описания формы поверхности, основанный на эволюции поверхности изолиний уровней, отображающей функцию. Этот способ, заключающийся в сопоставлении уровней критических точек на поверхности, как правило, рассматривается как один из самых простых способов описания геометрии поверхности. С каждой функцией оказывается связанным некоторый одномерный континуум, ее одномерное дерево. Изучение ряда свойств самой функции сводится к изучению свойств соответствующей функции на одномерном дереве. Разделение свойств функции двух переменных на «одномерные» и «двумерные» представляется факт принципиальный. С этой точки зрения введение одномерного дерева как раз существенно: с его помощью особенно четко выделяются одномерные свойства двумерной функции.
-1
2
2
-1
2
В дальнейшем через ƒ(r) будем обозначать полный прообраз значения r скалярной функции ƒ, заданной на S(ƒ:S→R). Через а будем обозначать регулярные значения функции, т.е. такие значения, в прообразе которых нет ни одной критической точки. В этом случае ƒ(а) всегда является гладким подмногообразием в S в силу известной теоремы о неявной функции. Обозначим через с критические значения функции, т.е. такие значения, в прообразе которых есть хотя бы одна критическая точка.
2
-1
Пусть ƒ - функция Морса на компактном гладком многообразии S. Рассмотрим произвольную поверхность уровня ƒ(a) и ее компоненты связности, которые назовем слоями. В результате многообразие разбивается в объединение слоев, получается слоение с особенностями. Подчеркнем, что каждый слой связен по определению. Объявляя каждый слой одной точкой и вводя естественную фактор-топологию в пространстве слоев Г, получаем некоторое фактор-пространство. Его можно рассматривать как базу этого слоения. Для функции Морса пространство Г является графом.
2
Граф Г называется графом Кронрода-Риба (Кронрод А.С. О функциях двух переменных // УМН, 5:1(35) (1950), 24-134. Reeb G. Sur les points singuliers d'une forme de pfaff compl'etement int'egrable ou d'une fonction num'erique. Comptes Rendus de L'Acad'emie ses S'eances, Paris, 222:847-849, 1946) для функции Морса ƒ на многообразии S. Вершиной графа Кронрода-Риба назовем точку, отвечающую особому слою функции ƒ, т.е. связной компоненте уровня, содержащей критическую точку функции. Вершину графа Кронрода-Риба назовем концевой, если она является концом ровно одного ребра графа. Все остальные вершины назовем внутренними.
Концевые вершины графа Кронрода-Риба взаимно-однозначно отвечают локальным минимумам и максимумам функции. Внутренние вершины графа Кронрода-Риба взаимнооднозначно отвечают особым слоям функции, содержащим седловые критические точки (фиг.12).
Для простоты изображения двумерных поверхностей, везде далее в этом разделе предполагается, что изображаемые функции ведут себя как - r вдали от начала координат, продолжая их вблизи точки ∞ так, чтобы она была точкой локального минимума.
Если заранее известно, что изучаемая поверхность является ориентируемой или неориентируемой, то граф Кронрода-Риба произвольной простой функции на ней позволяет восстановить топологию поверхности. Графы Кронрода-Риба рассматриваются с точностью до изоморфизма ориентированных графов. Две функции Морса на ориентируемой поверхности послойно эквивалентны тогда и только тогда, когда их графы Кронрода-Риба изоморфны.
Обобщенный механизм построения графа Кронрода-Риба сводится к следующему. Пусть на многообразии задана функция Морса. Две критические точки соединяются ребром на графе Кронрода-Риба тогда и только тогда, когда существует монотонный гладкий путь на многообразии, который соединяет эти точки и не пересекает критических слоев (кроме своих концов). Под монотонным путем понимается путь, вдоль которого данная функция возрастает. Два седла соединяются двумя ребрами на графе Кронрода-Риба тогда и только тогда, когда существуют два монотонных гладких пути на многообразии, которые соединяют эти седла и не пересекают критических слоев (кроме своих концов), причем, эти пути невозможно соединить постоянным путем на многообразии (то есть внутренние точки путей принадлежат разным слоям).
Таким образом, одномерное дерево функции Морса состоит из множества концевых точек плюс не более чем счетное число простых дуг, попарно пересекающихся не более чем в одной точке, являющейся притом точкой ветвления.
Следует отметить, что для вырожденной функции Морса (наличие вырожденной критической точки) сколь угодно малым шевелением функции Морса можно добиться, чтобы на каждом критическом уровне с (т.е. на множестве точек p, для которых ƒ(p)=с) лежала ровно одна критическая точка. Другими словами, критические точки, попавшие на один уровень, можно развести на близкие уровни. Функции Морса, имеющие ровно по одной критической точке на каждом критическом уровне, называются простыми. Для невырожденной функции Морса граф Кронрода-Риба является деревом, имеющим Т тройных точек ветвления, K=Т+2 концевых точек и Р=2T+1 ребро, соединяющие K+Т=2Т+2 вершины графа (Arnol V.I. Smooth functions statistics // Abdus Salam International Centre for Theoretical Physics, ICTR. 2006. IC/2006/012. 9pp.). Заметим, что не всякий конечный (или бесконечный) граф будет графом Кронрода-Риба для некоторой собственной гладкой функции с изолированными критическими точками на поверхности (Шарко В.В. Гладкие функции на некомпактных поверхностях. // Збiрник праць Iн-ту математики НАН Украïни 2006, т.3, №3, 443-473). Существует условие, которое гарантирует, что граф будет графом Кронрода-Риба.
ν
Пусть ν - вершина графа Г. Граф Г=Г - ν получается из графа Г в результате удаления вершины ν и всех инцидентных ей ребер. Вершина v называется разбивающей, если граф Г - несвязное множество. Обозначим через Ω - множество вершин порядка 1 в графе Г.
Граф Г удовлетворяет условию (W), если:
a) Г - связное множество;
ν
<mrow><msubsup><mtext>Г</mtext><mtext>ν</mtext><mtext>i</mtext></msubsup></mrow>
<mrow><msubsup><mtext>Г</mtext><mtext>ν</mtext><mtext>i</mtext></msubsup><mstyle displaystyle="true"><mo>∩</mo><mrow><mtext>Ω</mtext><mo>≠</mo><mo>∅</mo></mrow></mstyle></mrow>
b) Для каждой разбивающей вершины ν из Г, такой, что если среди компонент связности графа Г присутствуют конечные графы
, то
;
c) Если граф Г - конечен, то Ω состоит не менее из двух вершин.
Пусть Г - граф с условием (W). Тогда на Г существует возрастающая (убывающая) функция. Каждый граф с условием (W) есть граф Кронрода-Риба гладкой функции с изолированными особенностями, заданной на поверхности.
Пусть граф Г удовлетворяет условию (W), и на нем задана функция высоты g, тогда существует ориентированная поверхность М и гладкая функция ƒ с изолированными особенностями на ней, являющейся функцией высоты, у которой граф Кронрода-Риба изоморфен Г.
Граф Кронрода-Риба любой собственной гладкой функции с изолированными особенностями, заданной на поверхности (компактной или некомпактной), удовлетворяет условию (W).
Для того чтобы граф был графом Кронрода-Риба гладкой функцию ƒ с изолированными особенностями на некоторой поверхности необходимо и достаточно, чтобы он удовлетворял условию (W).
Графы Кронрода-Риба позволяют рассчитать число возможных топологически различных функций Морса на сфере (Nicolaescu L.I. Counting Morse functions on the 2-sphere // Compositio Math. 144 (2008) 1081-1106), установить топологическую эквивалентность двух функций Морса, определяет эту поверхность однозначно с точностью до диффеоморфизма.
Для функции Морса, топология множества уровней связана с критическими точками и полем градиента функции. Эта связь обеспечивает возможность для формального описания поверхности в алгебраической форме. В отличие от других методов топологии, основанных, например, на деревьях Кронрода-Риба, использование комплекса Морса-Смейла обеспечивает описание двумерных и многомерных свойств поверхности, что позволяет получить представление локальной топологии гладких функций и произвести сегментацию поверхности на регионы с "однородным" полем градиента. Другими словами, геометрия гладкой поверхности отображается в простые геометрические образы (симплициальные комплексы, фиг.13), анализ которых позволяет описать структурные особенности исходной поверхности, различной размерности: нуль-, одно- и двумерные. Эти структурные особенности легко интерпретируются в геоморфологических терминах, например нульмерным объектам соответствуют вершины (пики) и впадины (ямы), одномерным - линии сети тальвегов, водоразделов, двумерным - монотонные склоны. Этим обеспечивается связь геометрических свойств через структурные особенности с геоморфологической семантикой.
В последнее время теория Морса была распространена до кусочно-линейных функций (Gyulassy A.G. Combinatorial Construction of Morse-Smale Complexes. Dissertation Submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy. University of California. 2008). Такое расширение на кусочно-линейные функции и дискретные сетки позволяет использовать теорию Морса для решения практических задач с реальными наборами данных.
Критические точки функции Морса - это те точки на двумерной поверхности, где функция стационарна. Чтобы в полной мере описать функцию Морса, мы должны выделить ее структурные особенности. Для этого нужно определить векторное поле, называемое градиентом.
2
2
Градиент функции Морса - векторное поле на S. Проинтегрируем это векторное поле, для того чтобы осуществить декомпозицию S на регионы с однородными потоками.
<mrow><mfrac><mtext>d</mtext><mrow><mtext>ds</mtext></mrow></mfrac><mtext>l</mtext><mrow><mo>(</mo><mtext>t</mtext><mo>)</mo></mrow><mo>=</mo><mtext>d</mtext><mi>ƒ</mi><mrow><mo>(</mo><mrow><mtext>l</mtext><mrow><mo>(</mo><mtext>t</mtext><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow>
Кривая l(t) называется интегральной линией ƒ, если -
для всех t∈R.
Другими словами интегральная линия есть путь, для которого касательный вектор параллелен градиенту в каждой точке пути.
2
Интегральные линии представляют поток вдоль градиента между критическими точками. В любой точке, где градиент не равен нулю, интегральную линию, проходящую через эту точку, можно найти, проследив вперед и в обратном направлении вдоль векторного поля градиента. Интегральной линии открытые 1-многообразия, а так как Sкомпактно, ограничения на обоих концах существуют. Следующее определение определяет верхний и нижний предел точек интегральной линии.
<mrow><munder><mrow><mtext>lim</mtext></mrow><mrow><mtext>s</mtext><mo>→</mo><mo>−</mo><mi>∞</mi></mrow></munder><mtext>l</mtext><mrow><mo>(</mo><mtext>t</mtext><mo>)</mo></mrow></mrow>
Предел
называется источником интегральной линии l(t) и обозначается org(l).
<mrow><munder><mrow><mtext>lim</mtext></mrow><mrow><mtext>s</mtext><mo>→</mo><mo>+</mo><mi>∞</mi></mrow></munder><mtext>l</mtext><mrow><mo>(</mo><mtext>t</mtext><mo>)</mo></mrow></mrow>
Предел
называется приемником интегральной линии l(t) и обозначается dest(l).
Интегральные линии на гладких функциях обладают следующими свойствами:
1) две интегральные линии либо пересекаются, либо же совпадают;
2
2) интегральные линии покрывают все S,
3) источники и приемники интегральных линий являются критическими точками ƒ.
2
2
Интегральные линии монотонны и, следовательно, org(l) ≠ dest(l). Эти свойства обеспечивают условие, что каждая точка S имеет ровно одну интегральную линию, проходящую через нее. Все точки на S могут быть классифицированы как источники или приемники.
Перечисленные свойства следуют из стандартного дифференциального исчисления.
Интегральные линии, которые соединяют максимум и седло, или минимум и седло, называются линиями сепаратрис. В геоморфологии линии сепаратрис, которые соединяют минимумы и седла, обычно называют оврагами, или линиями долин, а те, которые соединяют седла и максимумы, называются линиями хребтов.
2
2
2
2
Устойчивые / неустойчивые многообразия. Пусть p будет некоторой критической точкой функции ƒ:S→R. Неустойчивое многообразие для точки p - есть множество точек, принадлежащих интегральной линии, для которой источником является p, U(p)={p}U{x∈S|x∈im(l),org(l)=p}. Устойчивым многообразием для точки р есть множество точек, принадлежащих интегральной линии, для которой приемником является p, S(p)={p}U{x∈S|x∈im(l), dest(l)=p}. Здесь im(l} есть отображение кривой l∈S.
Устойчивое многообразие S(p) критической точки р с индексом i=i{p) есть открытая клетка размерности dim(S{p))=i.
Заметим, что неустойчивые многообразия функции ƒ являются устойчивыми многообразиями функции - ƒ, так как d(-ƒ)=-dƒ. Таким образом, два типа многообразий имеют одни и те же структурные свойства. Поэтому неустойчивые многообразия функции ƒ есть так же открытые клетки, но с размерностью dim(U(p))=2-i, где i - индекс критической точки.
Функция Морса называется функцией Морса-Смейла, если устойчивые и неустойчивые многообразия пересекаются только трансверсально. В двух измерениях, это означает, что устойчивые и неустойчивые 1-многообразия пересекаются под углами, близкими к прямым. Их точка пересечения обязательно является седлом, их пересечение в регулярной точке противоречило бы свойству 1) для интегральных линий.
2
Связные компоненты U(p)∩s(q) для всех критических точек p, q∈S называются клетками Морса-Смейла. Речь идет о клетках измерения 0, 1 и 2, в качестве вершин, дуг и регионов соответственно.
Набор клеток Морса-Смейла образует комплекс Морса-Смейла. Одномерный остов комплекса Морса-Смейла состоит из критических точек и линий сепаратрис. Этот остов называется критической сетью.
2
Так как U(p)∩S(p)={р}, и если р≠q, то U(р)∩s(q) есть множество регулярных точек r∈S, которые лежат на интегральных линиях l с org(l)=p и dest(l)=q. Вполне возможно, что пересечения устойчивых и неустойчивых многообразий состоит более чем из одного компонента.
В результате пересечения устойчивых и неустойчивых многообразий отображенных каждая вершина комплекса Морса-Смейла является критической точкой, каждая дуга составляет половину от стабильного или нестабильного 1-многообразия седла, и каждый регион является одним из компонентов пересечения стабильного 2-многообразия максимума, а нестабильный 2-многообразия минимума.
Отметим, что каждая ячейка комплекса Морса-Смейла имеет простую геометрию - практически монотонная функция, хорошо аппроксимируемая полиномиальным уравнением.
0
k
k
Ячейки комплекса Морса-Смейла триангулируются для перехода к симплициальным комплексам - комбинаторной основе алгебраической топологии (Понтрягин Л.С. Основы комбинаторной топологии. - М.: Наука, 1976. - 136 с.). Если дан линейно независимый набор из k+1-ой точки {е,…,e}∈R, то выпуклая оболочка, построенная на этих точках, называется k-ым симплексом. Точки из множества точек называются вершинами. На фиг.14 приведены все симплексы малой размерности для 0≤k≤3.
Предлагаемый способ осуществляется следующим образом.
Способ картографического отображения двухмерных распределений, заданных в цифровой форме, включает преобразование изображений дискретных графических распределений в непрерывную полутоновую форму с дальнейшим их представлением в форме изолиний - эксинденсит. При оптическом моделировании кодируют цифровые значения признака в заданной точке планшета оптическими символами - разновеликими пятнами с оптической плотностью, пропорциональной величине признака. Построение рельефа местности выполняют путем интерполяции точек высот и/или глубин в виде двумерных нерегулярных рациональных фундаментальных сплайнов, путем построения двумерной сплайн-функции, определяемой как тензорное произведение одномерных сплайнов.
При построении рельефа местности определяют итерирующие функции и вейвлеты для представления фрактального рельефа, путем формирования для кусочно-линейной поверхности графа Кронрода-Риба и комплексов Морса-Смейла, при этом выполняют упрощения кусочно-линейной поверхности с использованием полученной для нее структур графа Кронрода-Риба и комплексов Морса-Смейла; оценку фрактальных параметров рельефа на основе заданных структур графа Кронрода-Риба и комплексов Морса-Смейла.
Представления рельефа с помощью IFS и вейвлетов позволяют осуществить:
двоичную генерализацию поверхности, заданную на регулярной сетке точек;
имитацию увеличения масштаба разрешения исходной информации;
выявление резких перепадов значений функции;
вычисление фрактальных параметров функции;
фильтрацию "шума".
Основные алгоритмы программно-математического обеспечения позволяют:
восстановить рельеф по дискретным измерениям;
решить обратную задачу IFS;
выбрать оптимальные непрерывные и дискретные семейства вейвлетов для представления рельефа.
Методы описания рельефа с помощью функций Морса, графов Кронрода-Риба и комплексов Морса-Смейла обеспечивают возможность:
топологического кодирования форм рельефа;
картографической генерализации;
распознавания геоморфологических объектов;
формальной классификации геоморфологических объектов;
замощения поверхности рельефа семейством параметризованных (полиномиальных) функций, заданных на клетках Морса-Смейла;
иерархически оценивать степень сходства двух карт рельефа, представляющих одну область, в одном или разных масштабах;
оценки достоверности выделенных форм рельефа с учетом погрешности и мощности исходной информации;
оценки степени достаточности набора точечных измерений для восстановления рельефа с заданной подробностью.
Для осуществления перечисленных возможностей разработан следующий перечень основных алгоритмов:
восстановления рельефа по дискретным измерениям с использованием топологических;
формирования графа Кронрода-Риба для кусочно-линейной поверхности;
формирования комплексов Морса-Смейла для кусочно-линейной поверхности;
упрощения кусочно-линейной поверхности с использованием полученных для нее структур графа Кронрода-Риба и комплексов Морса-Смейла;
оценку фрактальных параметров рельефа на основе заданных структур графа Кронрода-Риба и комплексов Морса-Смейла.
Выбранные формулировки постулатов описывают самую простейшую структуру поверхности, однако это не является ограничением. Вполне возможно перейти к более сложным конструкциям, например разрешить существование "пещер", "тоннелей" и т.п. Аппарат топологии остается вполне адекватным и в этом случае, только необходимо применять более сложную технику алгебраической топологии - теорию гомологии.
Предлагаемый способ реализуется на элементной базе микропроцессорной техники, видеоплоттеров и видеопланшетов, информационно соединенных с измерительной аппаратурой параметров рельефа морского дна и т.д.
Например, блок управления выполнен на основе микропроцессоров семейства AVR фирмы АТМЕС со специальным программным обеспечением, позволяющим осуществлять ввод/вывод информации и преобразование сигналов от нескольких навигационных датчиков (приборов), например эхолота, который представляет собой многолучевой эхолот типа «R2Sonic 2022» с центральным лучом 1 градус, высокочастотного профилографа, который представляет собой профилограф с линейно-частотной модуляцией типа «Chirp», гидролокаторов бокового обзора, которые представляют собой батиметрический гидролокатор типа «Benthos C3D» с шириной полосы обзора 1,2 км, а блок преобразования картографической информации выполнен на основе микропроцессора DSP - процессора, работающего под управлением встраиваемой операционной системы «UCLinux».
Микропроцессор на основе DSP-процессора является устройством, обеспечивающим программную и аппаратную интеграцию отдельных блоков, входящих в состав аппаратных средств. Микропроцессор позволяет выполнять операции над 32-разрядными числами в формате с плавающей запятой, что обеспечивает точность вычислений, достаточную для решения большинства задач управления и преобразования данных. Тактовая частота процессора составляет 400 МГц. Помимо процессора в состав блока преобразования картографической информации входят микросхемы памяти SDRAM, микросхемы памяти flash, микросхемы интерфейсов ввода-вывода. Такое построение системы позволяет решать в реальном времени сложные вычислительные задачи, большой объем оперативной памяти системы позволяет осуществлять реализацию ресурсоемких алгоритмов.
Источники информации
1. Авторское свидетельство SU №365562, 1970.
2. Авторское свидетельство SU №640113, 1978.
3. Патент RU №2079891.
4. Берлянт A.M. Картография. - М.: Аспект Пресс, 2002. - 336 с.
5. Суворов С.Г., Дворецкий Е.М., Коваленко С.А. Методика создания цифровых моделей рельефа повышенной точности // Информация и космос. №1, 2005. - С.52-54.
6. Патент №2415381.
7. Голованов Н.Н. Геометрическое моделирование. - М.: Физматлит, 2002. - 472 с.
8. Квасов Б.И. Методы изогеометрической аппроксимации сплайнами. - М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2006. - 416 с.