ОСНОВНЫЕ ПРИНЦИПЫ ОТОБРАЖЕНИЯ ИНФОРМАЦИИ НА ЦИФРОВОЙ КАРТЕ ПРИ ИЗМЕНЕНИИ МАСШТАБА

АННОТАЦИЯ

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

Ключевые слова: цифровая карта; кластеризация; тепловая карта; преобразование Хаара.

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

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

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

При отображении точечных объектов на цифровых картах придерживаются определенных соглашений, в частности:

1. Условные знаки объектов имеют габариты;
2. Объекты имеют формуляр, то есть, текст, содержащий некую описательную характеристику объекта. Формуляры объектов имеют габариты и привязаны к условным знакам объектов;
3. Объекты в виде условных знаков всегда присутствуют на цифровой карте, формуляры присутствуют на цифровой карте опционально в зависимости от требований пользователя.

Просмотр как точечных, так и линейных объектов на карте пользователем преследует, как правило, одновременно несколько целей:

• Оценить местоположение отдельного объекта;
• Оценить распределение в пространстве большой группы объектов (в пределе, всего множества объектов).

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

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

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

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

Цель данной статьи – рассмотреть различные способы отображения точечных и линейных объектов при изменении масштаба цифровых карт и выбрать те из них, которые позволяют обеспечить наилучшую «читаемость» карты.

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

1. крупномасштабные карты – карты в масштабах крупнее 1:200 000;
2. среднемасштабные карты – карты в масштабе от 1:200 000 до 1:1 000 000;
3. мелкомасштабные карты – карты в масштабе 1:1 000 000 и мельче.

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

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

Цифровые карты на мелких масштабах. Анализ отображаемой информации позволяет выделить разные типы распределения точечных объектов на карте:

• квазиравномерное (движение воздушных судов онлайн – сайт flightradar24.com, radarbox24.com);
• локализованное (движение морских судов онлайн – shipfinder.co, торговые предприятия на yandex.ru/maps).

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

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

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

Построенная таким образом тепловая карта позволяет оценить области большой и малой плотности точечных объектов.

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

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

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

Рассмотрим основные методы кластеризации, которые можно использовать при отображении точечных объектов на средних и мелких масштабах.

В общем случае кластерный анализ предполагает выполнение следующих действий:

1. Отбор выборки объектов для кластеризации;
2. Определение множества переменных, по которым будут оцениваться объекты в выборке (выявление характеристик) – определение основных свойств объектов, позволяющих объединять их в группы, и минимизация их количества с целью оптимизации процесса кластеризации. Это позволяет в дальнейшем отождествлять объект с вектором его характеристик [3, с.4];
3. Определение метрики – вычисление значений меры сходства между объектами (зависит от исходного пространства и неявных характеристик кластеров). Один из вариантов метрики – расстояние, которое может определяться как среднее, минимальное и максимальное расстояние между объектами кластеров либо формулами Евклидового расстояния, расстояния Чебышева, степенного расстояния и манхэттенского расстояния. Выбор метрики зависит исключительно от эксперта, решающего задачу, и определяется её спецификой. Например, если необходимо присвоить веса определённым объектам, используется квадрат евклидова расстояния, степенное расстояние либо, если необходимо уменьшить влияние выбросов в выборке, используют манхэттенское расстояние;
4. Выбор и применение метода кластерного анализа для создания групп сходных объектов (кластеров).
5. Представление результатов анализа.

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

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

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

По мере принадлежности элементов к кластеру различают кластера:

• Чёткие или непересекающиеся – каждый объект принадлежит одной группе;
• Нечёткие или пересекающиеся – каждый объект относится к каждой группе с некоторой долей вероятности.

В рамках решаемой задачи необходимо исключить методы второй группы, поскольку такой результат затрудняет визуальное восприятие полученной группировки объектов [3, с. 9].

В основном алгоритмы кластеризации делятся на:

• плоские алгоритмы;
• алгоритмы, основанные на теории графов;
• алгоритмы основанные на плотности распределения точек;
• иерархические алгоритмы.

Плоские алгоритмы строят одно разбиение точечных объектов на кластеры. Примером плоского алгоритма является метод k-средних, который построен на принципе создания наиболее удалённых друг от друга заданного числа кластеров. Основные этапы алгоритма:

1. Случайно отобрать точки в количестве, равном заданному количеству кластеров. Они будут являться их центрами масс;
2. Соотнести все объекты к кластерам по принципу близости их центров масс к объекту;
3. Найти новый центр масс группы с учётом нового состава кластера;
4. Если центр масс поменялся, то вернуться к выполнению второго этапа. Иначе – остановить выполнение алгоритма [3, с. 7].

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

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

• Алгоритм выделения связных компонент, в котором эксперт устанавливает определённую величину, с которой сравниваются веса ребер графа. Все ребра, имеющие больший вес, чем установленное значение, удаляются из графа. Таким образом, соединенными остаются только близлежащие друг к другу вершины. Поэтому основной задачей является верный подбор значения для сравнения весов. Если он подобран правильно, то граф распадётся на несколько кластеров и задача считается решенной. В рассматриваемой задаче подбор значения для каждого масштаба затрудняет её решение [4];
• Алгоритм минимального покрывающего дерева основан на построении на графе минимального покрывающего дерева с последующим удалением ребер с наибольшим весом. [4]. Данный метод не оптимален в рамках рассматриваемой ситуации, поскольку он имеет довольно большую вычислительную мощность – O(n²log n) [6, с. 35];

В качестве примером алгоритма, основанного на плотности распределения точек, рассмотрим метод DBSCAN (англ. Density-based spatial clustering of applications with noise, DBSCAN). Основные этапы построения кластеров:

1. Определить роль каждого объекта. Всего ролей три: если вокруг объекта много объектов, то он может считаться основным объектом кластера; если вокруг объекта мало объектов, но в окрестности есть основной объект, то он считается пограничным; иначе объект является шумовыми;
2. Отбрасываются все шумовые объекты;
3. Соединяются все основные объекты, которые находятся в окрестностях определённого радиуса друг от друга;
4. С основными объектами соотносятся все ближайшие пограничные объекты, образуя с соединениями искомые кластеры [2].

Данные методы могут подойти для отображения карт как на средних, так и на мелких масштабах. «Шумовые» точечные объекты, которые отбрасываются в процессе кластеризации, будут отображаться как одиночные объекты, не попавшие ни в один кластер. Средняя вычислительная сложность алгоритма О(n log n), в худшем случае – O(n²).

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

• Агломеративные методы, для которых на начальном этапе предполагают, что каждый объект является группой. В процессе кластеризации эти группы объединяются между собой. Если довести процесс кластеризации до конца, в таком случае будет получена одна группа, содержащая все исходные объекты. Эти методы удобны при изменении требований, связанных с изменением количества кластеров, поскольку кластеризацию не нужно проводить заново (в случае уменьшения числа кластеров следует проложить кластеризацию с текущего состояния, в случае увеличения – вернуться к этапу кластеризации с необходимым числом групп);
• Дивизионные методы, для которых на начальном этапе предполагают, что все исходные объекты образуют единый кластер, который в процессе кластеризации делится на меньшие группы. Если довести процесс кластеризации до конца, в таком случае будет получены кластеры, каждый из которых состоит из одного элемента исходной выборки [2].

Представляется, что при изменениях масштаба одними из предпочтительных методов кластеризации точечных объектов являются как раз иерархические агломеративные алгоритмы. Они не требуют пересчёта, позволяют использовать результаты предыдущего разбиения при переходе от одного масштаба к другому, вычислительная сложность алгоритмов данной группы равна O(n²).

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

• выбирается линейка базовых масштабов, для которых заранее рассчитываются наборы генерализованных данных;
• автоматическая генерализации линейных объектов непосредственно во время отображения цифровой карты [5, c. 37].

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

Исходя из требования быстродействия наиболее подходящими являются алгоритмы автоматической генерализации, имеющие сложность O(n). Этому требованию удовлетворяют иерархические (кратномасштабные) методы сжатия, в частности метод преобразования Хаара.

Обычно преобразование Хаара используется для сжатия входных сигналов и компрессии изображений с плавными переходами. Идея преобразования заключается в следующем. Для одномерного дискретного входного сигнала каждой паре соседних элементов ставится в соответствие два числа – полусумма и полуразность элементов. Массив полусумм всех элементов исходного сигнала является огрубленной версией входного сигнала, а массив полуразностей содержит детальную информацию, необходимую для восстановления исходного сигнала. Как правило, для реальных данных соседние значения элементов отличаются несущественно. Соответственно, значения полуразностей находятся в достаточно узком диапазоне значений и могут быть представлены компактно при программной реализации алгоритма сжатия [1, с. 25].

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

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

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

1. Берлянт А.М., Мусин О.Р., Собчук Т.В. Картографическая генерализация и теория фракталов. – М.: Наука, 1998. – 136 с.;
2. Кантор В.В. Знакомство с методами кластеризации [видеозапись лекции Кантора В.В.] // Coursera. Поиск структуры в данных. Режим доступа URL: www.coursera.org/lecture/unsupervised-learning/znakomstvo-s-mietodami-klastierizatsii-V5Mhp (дата обращения16.02.2020);
3. Котов А., Красильников Н. Кластеризация данных // Электронный ресурс. Режим доступа URL: https://logic.pdmi.ras.ru/~yura/internet/02ia-seminar-note.pdf (дата обращения: 10.02.2020);
4. Обзор алгоритмов кластеризации данных // Электронные данные. Режим доступа URL: https://habr.com/ru/post/101338/ (дата обращения 22.02.2020);
5. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике: Пер. с англ. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002.  – 272 с.;
6. Jain A., Murty M., Flynn P. Data Clustering: A Review. // ACM Computing Surveys. 1999. Vol. 31, no. 3.