Мультимасштабные базы геоданных для электронных карт1
Мультимасштабные карты, становясь стандартом де-факто в ГИС-среде, требуют соответствующей разработки методик проектирования и наполнения мультимасштабных баз данных. При этом различные подходы (сети Петри, квадротомические модели) могут быть использованы в работе с векторными и растровыми данными, цифровыми моделями
Т.Е. Самсонов (МГУ им. М.В. Ломоносова)
Актуальная на данный момент концепция практической картографии может быть сформулирована как database-driven cartography, т. е. «картография, движимая базами данных» [1]. В это определение заложены следующие ключевые положения:
— карта является результатом обработки и визуализации данных, организованных и структурированных в виде базы географических данных (БГД);
— картографический результат во многом зависит от БГД, структуры и качества ее содержимого;
— электронная карта, как правило, является не только графическим представлением информации, каждый ее слой связан с источником данных — классом пространственных объектов в БГД (точечным, линейным, полигональным, растровым, сетевым).
Таким образом, в концепции геоинформационного картографирования [2] выделяется практический оттенок, указывающий на тесную взаимосвязь карты и базы данных: карта не только создается на основе БД, но и методика ее создания зависит от особенностей БД как источника данных. С другой стороны, БД должна быть подготовлена так, чтобы наилучшим образом соответствовать решаемой картографической задаче. Очевидно, что среди основных составляющих работы специалиста-картографа должны быть подготовка базы данных, ее проектирование и наполнение.
Интерактивность среды просмотра, будь то простое приложение в окне Web-браузера или полнофункциональная настольная ГИС, подразумевает возможность пользовательской навигации. При этом часто возникает необходимость не только перемещаться по карте, но и переходить с одного уровня исследования на другой, что соответствует разным масштабам изображения.
Обеспечить масштабирование одним набором базовых данных затруднительно. Алгоритмы автоматической генерализации пока что не удовлетворяют требованиям ни по качеству и географической достоверности результатов, ни по затратам времени на выполнение [3], поэтому в интерактивной среде неприемлемы. В то же время масштабный ряд карты может включать один-два десятка уровней с диапазоном значений, например, от 1:10 000 до 1:10 000 000 (в частности, карта мира на популярном геосервисе Google Maps). Необходимо каким-то образом обеспечить иерархию масштабов карты данными соответствующей структуры и точности.
Достаточно простое с концептуальной точки зрения решение этой проблемы состоит в создании мультимасштабной базы геоданных (МБГД) [4, 5]. БГД — это объектно-ориентированная модель данных, позволяющая описывать поведение объектов [6]. МБГД состоит из наборов данных различной детализации (пространственной и семантической), формирующих так называемые лоды, или уровни детализации (от англ. LoD — Level of Detail). Каждый лод оптимизирован для отображения в определенном диапазоне масштабов, т. е. для него существуют опорный масштаб, к которому приведены (генерализованы) данные, и некая масштабная окрестность2, в пределах которой можно использовать данные без ущерба для читаемости карты, скорости ее отображения, эстетичности и т. д.
В случае использования МБГД работа с данными происходит в два этапа [7].
1. Предварительная обработка исходных данных и формирование лодов. На этом этапе проводятся сложные операции генерализации, занимающие значительное время и, вероятно, требующие ручной коррекции результатов автоматической обработки. В распоряжении картографа могут быть, например, цифровые данные четырех масштабов, из которых необходимо сформировать масштабный ряд из десяти уровней (таблица).
Таблица. Пример использования цифровых данных при создании мультимасштабной карты
Стоит заметить, что БД электронных версий топографических карт слишком подробны для экранного просмотра в оригинальном масштабе (1:200 000, 1:1 000 000 и т. п.). Как правило, масштаб можно смело укрупнять в полтора-два раза (что примерно соответствует масштабам 1:150 000 и 1:750 000), чтобы обеспечить нормальное восприятие информации. Связано это с низкой разрешающей способностью экрана и его ограничениями по цветопередаче. Следовательно, для отображения в оригинальном масштабе (если есть такая принципиальная необходимость) требуется генерализация данных. При формировании лода еще меньшей детализации генерализация может проводиться с привлечением данных более мелкого масштаба. В таблице такой случай соответствует3 лоду 2.
2. Обработка данных «на лету» во время визуализации. На этом этапе проводятся несложные операции, как правило, ограничивающиеся запросами к БД в целях отбора объектов. При этом объектам различных типов может быть присвоена одинаковая символика (условное обозначение), и визуально они будут относиться к одному типу. Таким образом, при отображении объектов также имеет место картографическая генерализация.
Теоретически, необходимо стремиться к уменьшению числа уровней детализации и выполнению большинства задач на втором этапе. «Обрастание» базы данных лодами чревато возникновением необходимости ее каскадного обновления. Появление или изменение хотя бы одного объекта требует обновления всех лодов для поддержания целостности БД. При этом недостаточно актуализировать сам объект — необходимо проанализировать его географическое окружение, применить правила топологии. Если объект относится к новому типу, возможно, потребуется вмешательство в саму структуру БД.
Для поддержки подобных операций необходимо хранить иерархические связи между объектами [5]. По сути, такие связи могут отражать историю генерализации (что из чего получено), если несколько лодов последовательно сформированы на основе одного исходного масштаба. В общем случае (лоды получены независимо друг от друга) такая связь будет указывать на соответствие или пространственное соподчинение объектов. Например, связи «дом — дом» или «дом — квартал» (рис. 1).
Рис. 1. Иерархические связи между представлениями объектов в разных масштабах: «дом — дом» (а); «дом — квартал» (б)
Прежде чем рассматривать хранение связей в базе данных, необходимо детальнее проникнуть в их природу. Начать же следует с особенностей самой карты, которые и определяют принципы формирования БД.
До этого момента наши рассуждения опирались на понятия масштабного ряда и ряда лодов. Эти ряды дискретны и состоят из фиксированного набора уровней. Тем не менее, подобное ограничение не свойственно самой карте. В общем случае среда просмотра должна поддерживать непрерывное изменение масштаба.
Электронные карты, с точки зрения визуализации данных, можно разделить на динамические и кэшированные [8]. В первом случае при навигации происходят обращение к базе данных и перерисовка изображения с учетом нового охвата. При использовании технологии кэширования мозаика (кэш) растровых фрагментов (тайлов), на которые разбита вся область карты, рассчитывается заранее, поэтому работа с ней протекает существенно быстрее (рис. 2). Однако визуализация в произвольном масштабе невозможна или приводит к простому масштабированию тайлов ближайшего уровня (растягиванием или сжатием).
Рис. 2. Принцип работы кэшированной (а) и динамической (б) карт при изменении области просмотра (масштабирование и панорамирование)
В связи с этим возникают следующие вопросы: как соотносятся произвольные масштабы изображения и лоды, на которые они должны опираться; при каком масштабе должно происходить переключение уровней детализации; как теоретически обеспечить интерактивную генерализацию данных в произвольный масштаб на основе существующих лодов; какую роль в свете рассматриваемой проблемы играет структура базы данных (связи между объектами в разных лодах) и как необходимо организовать в таком случае хранение связей?
Элегантная модель МБГД [9], дающая ключ к решению этих вопросов, опирается на теорию сетей Петри. Сеть Петри N = (S,T,F) состоит из трех элементов [10]:
— множество мест S = {s1,...,sn};
— множество переходов T = {t1,...,tn}, таких, что
— отношение инцидентности
, устанавливающее каждому переходу t в соответствие входное и выходное мультимножество мест.
Моделирование в сетях Петри осуществляется на событийном уровне. Определяется, какие действия происходят в системе, какие состояния предшествовали этим действиям, какие состояния примет система после выполнения действия. Реализация событийной модели в сетях Петри описывает поведение системы. Пример сети Петри приведен на рис. 3.
Рис. 3. Пример сети Петри: S — место; T — переход
С точки зрения PN-модели4, уровень детализации (лод) можно рассматривать как некое состояние системы — место; событие масштаба5, при котором происходит смена лодов и, соответственно, генерализация данных, — как переход, а связи между соответствующими сущностями в базе данных (до и после перехода) реализуют отношение инцидентности. Подобная модель в виде графа представлена на рис. 4, а соответствующий ей картографический сюжет — на рис. 5.
Рис. 4. PN-модель генерализации объектов в мультимасштабной базе геоданных
В базе данных каждому пространственному объекту соответствует единица представления (representation instance). Один объект может иметь множество единиц представления в нескольких лодах. Единицы представления одного объекта могут различаться по типу пространственной локализации (полигональная, линейная, точечная) и по содержанию пространственной и атрибутивной информации (геометрическая подробность, состав атрибутов и т. д.).
Рис. 5. Процесс генерализации в МБГД. На первых трех этапах происходит упрощение и объединение (слияние) объектов. На последнем этапе качественные характеристики обобщаются,качественные характеристики обобщаются, вводится новая категория объектов
Как только меняется одна из этих характеристик, возникает новая единица представления. Например, локализация реки при переходе на новый уровень детализации может смениться с полигональной на линейную. Причиной, инициирующей это событие, будет невозможность восприятия человеком полигонального объекта в более мелком масштабе из-за визуального слияния границ.
В частном случае единица представления, взятая из одного лода базы данных, может использоваться на нескольких уровнях детализации карты. Масштабный диапазон, в пределах которого она актуальна, можно определить как жизненный цикл единицы представления [9]. Таким объектом может быть, например, квартал простой геометрической формы, не требующий генерализации в двух-трех соседних масштабах (№ 7 на рис. 5).
По аналогии и масштабный диапазон, в пределах которого объект присутствует в БД, определяется как жизненный цикл объекта [9]. Он является объединением жизненных циклов единиц представления. Как только объект поглощается единицей представления более высокого порядка (например, дома объединяются в кварталы), его жизненный цикл заканчивается.
Хранение масштабных событий в МБГД позволяет проследить историю генерализации объектов. Более того, оно поддерживает непрерывность их жизненного цикла. На основе содержания масштабного события, включающего собственно сам масштаб и средства генерализации, а также связи между объектами и переходом, можно реализовать состояние системы на произвольный между лодами масштаб.
Таким образом, PN-модель является последовательным развитием стандартной иерархической модели МБГД, которая строго привязана к уровням детализации. Преимуществами PN-модели являются:
— непрерывность: запрос к базе данных может быть осуществлен в любом масштабе;
— исключение дублирования данных в лодах: в пределах жизненного цикла хранится одна единица представления (для самого крупного масштаба);
— простота обновления МБГД, которая обеспечивается отсутствием в ней дубликатов и хранением истории генерализации.
Представление моделей рельефа и геополей в МБГД
Как правило, данные о поверхностях в БГД представлены в виде цифровых моделей. Среди различных типов ЦМР на практике чаще всего используют модели на прямоугольной сетке (GRID) и триангуляционные (TIN). В БГД им соответствуют специальные структуры данных, отличные от структур векторных классов объектов. Это связано с иной (континуальной) природой поверхностей. Очевидно, требуется рассмотреть методику наполнения МБГД мультимасштабными цифровыми моделями (МЦМР).
Основной характеристикой ЦМР является ее разрешение6. Для сеточных моделей оно определяется размером ячейки на местности, для триангуляционных — минимальным расстоянием между узлами в области наибольшей плотности данных. Разрешение модели непосредственно связано с масштабом визуализации и масштабом анализа (степенью локализации показателя) [11]. Излишняя подробность модели не лучшим образом сказывается на времени отображения карты. Оптимизация разрешения позволяет:
— максимизировать скорость визуализации;
— обеспечить наглядность пластического изображения;
— обосновать достоверность вычисленных по модели аналитических показателей, величина которых, как известно, зависит от масштаба исследования [12].
Таким образом, при подготовке лода ЦМР требуется привести модель к необходимому разрешению.
Регулярная структура цифровых моделей упрощает задачу генерализации «на лету». В отличие от векторных данных, алгоритмы интерактивного отбора узлов и ребер моделей поверхностей хорошо разработаны и активно применяются в средах виртуального моделирования, компьютерных играх и т. д. [13]. Практика показывает, что в МБГД, как правило, присутствуют три-пять лодов, а промежуточные по детализации уровни генерируются «на лету» [14].
Также как и для векторных данных, для ЦМР существуют два типа мультимасштабного представления [14]:
— метрическое (лод БГД). Иерархическая организация лодов представляет собой пирамиду, которая может быть создана как для прямоугольно-сеточной модели, так и для триангуляционной (рис. 6). На каждом новом уровне разрешение модели становится более грубым, число узлов сокращается в соответствии с масштабом;
— визуальное (лод изображения). В трехмерной среде используется понятие ракурсно-зависимого лода (view-dependent LoD). Детализация изображения интерактивно меняется в зависимости от удаленности участка поверхности от точки обзора [15]. В формировании такого лода могут участвовать несколько метрических представлений.
Рис. 6. Иерархическое представление ЦМР в виде пирамиды: модель на прямоугольной сетке (а); триангуляционная модель (б)
Эффективным средством оптимизации хранения МЦМР является создание на ее основе квадротомической модели. Суть метода заключается в последовательном делении массива на четыре квадрата и нахождении неоднородных квадратов, включающих пикселы с разным значением [16]. Однородные квадраты остаются без изменения, а неоднородные снова делятся на четыре до тех пор, пока не останется неоднородных значений (вплоть до квадрата размером 1х1 пиксел). Подобное упорядочение сопоставимо с дискретно приспособленным разрешением, при котором фиксируется каждая стадия изменения разрешения и, следовательно, детальность описания объектов [16]. Полученные квадраты последовательно кодируются, а результаты деления могут быть графически представлены в виде так называемого дерева квадрантов (рис. 7).
Рис. 7. Квадротомическая модель рельефа на основе сеточной ЦМР: модель (а), дерево квадрантов (б) [14]
В случае классифицированных растров однородность понимается как совпадение значений. Однако рельефу несвойственно иметь константное значение высоты в сколь угодно малой окрестности. Поэтому можно установить некий допуск, например, максимальное отклонение значений в квадрате от среднего по квадрату. Если оно не превышает пороговой величины, квадрат считается однородным, его дальнейшее деление прекращается.
Очевидно, что при этом происходит генерализация цифровой модели. Руководствуясь требуемым масштабным рядом и регулируя допуск однородности, можно построить эффективную квадротомическую модель рельефа (рис. 8).
Рис. 8. Квадротомическое представление ЦМР [17]
Основной стратегией организации цифровых моделей является разбиение территории на небольшие фрагменты, которыми можно эффективно управлять [14]. Стандартная иерархическая схема состоит из нескольких уровней: регион — тайл — блок — строка — колонка. При управлении мультимасштабными моделями подобная структура оказывается полезной с точки зрения обновления данных. Оно может осуществляться в рамках только тех иерархических блоков модели, которые захватываются областью изменившихся значений. Для них будет проводиться интерполяция обновленных данных. При этом с некоторого уровня модель можно и не обновлять, если крупномасштабные (локальные) изменения в ней не заметны.
Выводы
Мультимасштабное интерактивное картографирование является актуальной задачей. Многие его подзадачи, например интерактивная генерализация данных, пока не имеют удовлетворительного решения и требуют дальнейших исследований. Мультимасштабные карты, становясь стандартом де-факто в ГИС-среде, требуют соответствующей разработки методик проектирования и наполнения мультимасштабных баз данных. При этом различные подходы (сети Петри, квадротомические модели) могут быть использованы в работе с векторными и растровыми данными, цифровыми моделями.
Автор выражает благодарность проф. А.М. Берлянту и проф. И.К. Лурье за научное руководство при подготовке статьи.
Список литературы
1. Cartographic Design Process: Artistic Interpretation With the Geodatabase / An ESRI White Paper, July 2004. — http://www.esri.com/library/whitepapers/pdfs/cartographic-design.pdf .
2. Берлянт А.М. Геоинформационное картографирование. — М.: Астрея, 1997. — 64 с.
3. Wang Y. H., Chen J., Jian J. Multi-Scale Conceptual Model for GIS Geographical Features // Journal of China University of Mining & Technology. — 2003. — Vol. 32(4). — P. 376–382.
4. Buttenfield B. Research Initiative 3: Multiple Representations // Closing Report / National Center for Geographic Information and Analysis. — Buffalo, 1993.
5. Jones C.B., Kidner D.B., Luo L.Q. et al. Database design for a Multi-scale spatial information system // Int. Journal of GIS. — 1996. — Vol. 10(8). — P. 901–920.
6. Мамедов Э.Э. База геоданных // ArcReview. — 2001. — № 4 (19). — C. 3–5.
7. Cecconi A., Weibel L., Barrault M. Improving Automated Generalisation for On-Demand Web Mapping by Multiscale Databases // Symposium on Geospatial Thory, Processing and Applications. — Ottawa, 2002. — http://www.isprs.org/commission4/proceedings02/pdfpapers/138.pdf .
8. Самсонов Т.Е. Картографический дизайн, ориентированный на Интернет: проектирование и оформление карт для Web-сервисов // ArcReview. — 2009. — № 1. — C. 14–15.
9. Yin Z.C. A Multi-Scale GIS Database Model Based On Petri Net // ISPRS Workshop on
Service and Application of Spatial Data Infrastructure, XXXVI (4/W6). — Hangzhou, 2005. — P. 271–275.
10. Питерсон Дж. Теория сетей Петри и моделирование систем / Пер. с англ. — М.: Мир, 1984. — 264 с.
11. Wood J. Scale-based Cha-racterization of Digital Elevation Models // Innovations in GIS (3): CRC Press, 1996. — P. 163–175.
12. Gallant J.C. Hutchinson M.F. Scale Dependence in Terrain Analysis // Mathematics and Computers in Simulation. — 1997. — Vol. 43, № 3. — P. 313–321.
13. Duchaineau M. et al. ROAMing terrain: real-time optimally adapting meshes / In: Roni Yagel and Roni Yagel (Eds.) // Proceedings of the 8th Conference on Visualization 1997. — Phoenix (AZ), 1997. — P. 81–88.
14. Li Z., Zhu Q., Gold C. Digital Terrain Modeling: Principles and Methodology. — Boca Raton, London, New York, Washington: CRC Press, 2004. — 323 p.
15. Lindstrom P. et al. Real-time continuous level of detail rendering of height fields / In: Rushmeier H. (Ed.) // Proceedings of SIGGRAPH 96. — New Orleans (LA), 1996. — P. 109–118.
16. Лурье И.К. Геоинформационное картографирование. Методы геоинформатики и цифровой обработки космических снимков: Учебник для вузов. — М.: КДУ, 2008. — 424 с.
17. Cheng G. Hierarchy Representation of Virtual Terrain Environment and Research into the Real Time Shading Technology: Ph.D. thesis / Zhengzhou Institute for Mapping and Surveying. — Zhengzhou, 2000. — 133 p.
1Исследование выполнено в соответствии с Программой поддержки ведущей научной школы 171.2008.5 и грантом РФФИ 08-05-00126-а. 2 Эта окрестность может быть названа «пределом применимости» [7] (от англ. Limit of Applicability). 3 В статье [7] предлагается использовать так называемый морфинг — геометрическое осреднение двух вариантов одного объекта различной подробности. Например, взяв представления одного и того же объекта из лодов 1:5000 и 1:10 000 можно их осреднением получить представление для масштаба 1:7500. 4 От англ. Petri Net — сеть Петри. 5 От англ. scale event; речь идет о событии, происходящем при наличии определенного масштаба. 6 Безусловно, существует много других важных характеристик, таких как перепад высот, средняя величина углов наклона и т. д. Однако они уже производны и вычисляются по модели. Фундаментальной характеристикой является именно разрешение.
RSS
Реклама
Актуальная на данный момент концепция практической картографии может быть сформулирована как database-driven cartography, т. е. «картография, движимая базами данных» [1]. В это определение заложены следующие ключевые положения:
