СПОСОБ И УСТРОЙСТВО ДЛЯ ГЕНЕРАЛИЗАЦИИ КАРТЫ Российский патент 2023 года по МПК G06T3/40 

ОБЛАСТЬ ТЕХНИКИ

[0001] Заявленное решение относится к области цифрового картографирования, в частности к генерализации картографических изображений.

УРОВЕНЬ ТЕХНИКИ

[0002] В уровне техники традиционно использовался способ ручной генерализации карт, эффективность которого основывалась на опыте и знаниях картографа.

[0003] К недостаткам ручной генерализации можно отнести:

• большие временные затраты на работу картографов,

• значительную разницу в качестве итогового результата в зависимости от уровня мастерства исполнителя (картографа),

• плохую масштабируемость подхода с ростом числа картографических данных,

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

[0004] С развитием научно-технического прогресса, в частности, в области цифровой картографии, стала возможна автоматизация процесса генерализации. Например, автоматизированная генерализация с помощью алгоритмов симплификации геометрий из библиотеки spatialite [1].

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

[0008] Данное техническое решение направлено на устранение недостатков, присущих существующим решениям, известным из уровня техники.

[0009] Заявленное изобретение позволяет решить техническую проблему, заключающуюся в обеспечении формирования карты с высоким качеством генерализации.

[0010] Техническим результатом является повышения качества генерализации карты.

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

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

b) выполняют растеризацию полученной картографической информации;

c) выполняют фильтрацию растрированной картографической информации;

d) выполняют векторизацию отфильтрованной растрированной картографической информации в ходе которой получают восстановленный набор мультиполигонов;

e) формируют генерализированную карту на основе восстановленного набора мультиполигонов.

[0012] В одном из частных примеров реализации заявленный способ дополнительно содержит этап предварительной обработки полученной картографической информации перед выполнением растеризации.

[0013] В другом частном примере реализации этап предварительной обработки картографической информации включает:

• вычисление требуемой глубины цвета,

• вычисление общего ограничивающего прямоугольника для всех слоев, содержащих наборов мультиполигонов,

• определение размера тайла с учетом вычисленной глубины цвета,

• на основе вычисленного общего ограничивающего прямоугольника и размера тайла выполняют разделение обрабатываемой картографической информации на тайлы (тайлинг).

[0014] В другом частном примере реализации глубина цвета вычисляется по формуле:

bits-per-pixel=ceil(log2(N+1)),

где N - количество слоев полученной картографической информации.

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

[0016] В другом частном примере реализации на этапах b)-d) обработка ведется построчно, где каждая строка, представляющая набор из нескольких тайлов, обрабатывает параллельно и независимо от остальных строк.

[0017] В другом частном примере реализации выполнение растеризации полученной картографической информации осуществляется с помощью алгоритма построчного сканирования (алгоритма scanline).

[0018] В другом частном примере реализации этап фильтрации растрированной картографической информации включает:

• применение набора сверточных фильтров к растрированной картографической информации, и/или

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

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

[0020] В другом частном примере реализации этап векторизации отфильтрованной растрированной картографической информации включает:

• нахождение опорных точек на границах смежных объектов,

• построение границ объектов на основании найденных опорных точек,

• построение по меньшей мере одной общей границы между смежными объектами путем объединения общих вершин с одинаковыми координатами,

• восстановление набора мультиполигонов с учетом по меньшей мере одной общей границы объектов.

[0021] Заявленный технический результат достигается также за счет реализации устройства для генерализации карты, содержащего

по меньшей мере один процессор,

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0022] На Фиг. 1 представлена блок-схема компьютерно-реализуемого способа генерализации карты.

[0023] На Фиг. 2 представлена схема реализации компьютерно-реализуемого способа генерализации карты на примере конкретных объектов.

[0024] На Фиг. 3 представлена схема реализации процесса вычисления общего ограничивающего прямоугольника.

[0025] На Фиг. 4 представлена схема реализации процесса тайлинга картографического изображения.

[0026] На Фиг. 5 представлены примеры применения различных параметров фильтрации.

[0027] На Фиг. 6 представлена схема реализации процесса векторизации.

[0028] На Фиг. 7 представлена общая схема вычислительного устройства.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

[0029] Ниже будут описаны понятия и термины, необходимые для понимания настоящего изобретения.

[0030] Картография - это область науки, техники и производства, охватывающая изучение, создание и использование картографических произведений [2].

[0031] Картографическое произведение - это произведение, главной частью которого является картографическое изображение [2].

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

[0033] Цифровая картография - это раздел картографии, охватывающий теорию и практику создания и использования цифровой картографической продукции [3].

[0034] Цифровая картографическая продукция - это продукция, получаемая с использованием цифровой картографической информации [3].

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

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

[0037] Цифровая картографическая информация - это картографическая информация, представленная в цифровой форме [3].

[0038] Векторная форма представления (цифровой картографической информации) - способ представления метрической картографической информации в виде последовательности векторов [3].

[0039] Растровая форма представления (цифровой картографической информации) - способ представления цифровой картографической информации в виде матрицы, элементами которой являются коды цветов картографического изображения [3].

[0040] Векторизация цифровой картографической информации - это преобразование цифровой картографической информации из растровой формы представления в векторную [3].

[0041] Геометрии - это специальные геометрические объекты на карте, например, такие как: точки, мультиточки, круги, полилайны, мультиполилайны, полигоны, мультиполигоны.

[0042] Полигон (многоугольник) - это геометрия, представляющая собой замкнутую ломаную линию и ограниченную ею часть плоскости.

[0043] Мультиполигон - это геометрия, состоящая из одного и более полигонов.

[0044] Тайлы (от англ. tiles - плитки) в цифровой картографии - это прямоугольные фрагменты равной величины, созданные отдельно для каждого уровня масштабирования, на которые разбивается картографическое изображение.

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

[0046] Слой - это набор мультиполигонов/пикселей (в зависимости от формы представления данных - векторной или растровой) для однотипных объектов.

[0047] Идентификатор слоя - это битовая последовательность, соответствующая уникальному цвету.

[0048] Масштаб (параметр units-per-pixel) - это параметр, который задает соотношение между единицами измерения расстояния на экваторе и пикселями в растрируемом изображении.

[0049] Глубина цвета (параметр bits-per-pixel) - это параметр, характеризующий минимальное количество бит, требуемых для кодирования набора уникальных слоев.

[0050] Ограничивающий прямоугольник, выровненный по координатным осям (Axis Aligned Bounding Box, AABB) - это прямоугольник, четыре оси которого выровнены относительно системы координат, в которой он находится.

[0051] Bounding Box (ВВох, ограничивающий параллелепипед) - это некая простая фигура (обычно, параллелепипед), ограничивающая форму более сложной геометрической модели.

[0052] На Фиг. 1 представлен компьютерно-реализуемый способ (100) генерализации карты. Выполнение способа (100) осуществляется с помощью по меньшей мере одного процессора. В частном примере реализации выполнение способа (100) осуществляется с помощью устройства для генерализации карты, которое может быть реализовано на базе вычислительного устройства, модифицированного в программно-аппаратной части таким образом, чтобы выполнять функции устройства для генерализации карты. Более подробное описание вычислительного устройства раскрыто далее со ссылкой на Фиг. 7.

[0053] На первом этапе (101) получают картографическую информацию в векторной форме, содержащую по меньшей мере один слой, содержащий набор мультиполигонов для однотипных объектов. Каждый слой имеет идентификатор, соответствующий уникальному цвету, выраженному битовой последовательностью. Получение картографической информации в векторной форме в частном примере реализации может быть реализовано с помощью средства сетевого взаимодействия, подробно раскрытого далее со ссылкой на Фиг. 7. В качестве упомянутых однотипных объектов могут выступать, но не ограничиваться указанными примерами: леса, реки, дома, дороги и т.д.

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

[0055] В частном примере реализации этап предварительной обработки картографической информации может включать следующие подэтапы:

• вычисление требуемой глубины цвета,

• вычисление общего ограничивающего прямоугольника для всех слоев, содержащих наборов мультиполигонов,

• определение размера тайла с учетом вычисленной глубины цвета,

• на основе вычисленного общего ограничивающего прямоугольника и размера тайла выполняют разделение обрабатываемой картографической информации на тайлы (тайлинг).

[0056] Целью подэтапа вычисления глубины цвета (параметр bits-per-pixel) является нахождение минимального количества бит, требуемых для кодирования набора слоев. В частном примере реализации параметр глубины цвета вычисляется по соотношению N+1<=2^∧(bits-per-pixel), где N количество слоев полученной картографической информации, а показатель степени двойки минимальный. Например, если количество слоев равно 7, то параметр bits-per-pixel=3 (минимальная степень 3, а выражение принимает следующий вид: 7<=2^∧3=8). Другими словами, для нахождения глубины нужно вычислить выражение ceil(log2(N+1)).

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

[0058] В частном примере реализации информация о количестве слоев содержится в картографической информации, полученной на этапе (101), и может быть извлечена из картографической информации для вычисления глубины цвета. В другом частном примере реализации количество слоев (N) является заранее заданным параметром и зависит от масштаба (параметр units-per-pixel), чем меньше значение параметра units-per-pixel, тем больше слоев необходимо для осуществления процесса генерализации.

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

0 слой (фон): 0b00

1 слой: 0b01

2 слой: 0b10

3 слой: 0b11

[0060] В дальнейшем идентификаторы слоев используются, например:

• на этапе растеризации (102), чтобы отличать разные слои в получаемой картографической информации (изображении);

• на этапе векторизации (104), чтобы восстановить набор мультиполигонов.

[0061] В качестве дополнительного преимущества от использования идентификатора, соответствующего уникальному цвету, можно отметить значительное упрощение нахождения возникающих дефектов на картографическом изображении при осуществлении генерализации за счет визуально различимого цветового отличия между слоями.

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

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

[0064] Процесс вычисления общего ограничивающего прямоугольника для всех слоев, содержащих наборов мультиполигонов, проиллюстрирован на Фиг. 3. На первой схеме представлено несколько наборов мультиполигонов (311), принадлежащих разным слоям (о чем также свидетельствует уникальный цвет каждого слоя).

[0065] Для каждого набора мультиполигонов из каждого отдельного слоя вычисляется (301) ограничивающий прямоугольник, выровненный по координатным осям (ААВВ) на основании параметра масштаба (units-per-pixel). Параметр units-per-pixel задает соотношение между единицами измерения расстояния на экваторе и пикселями в растрируемом картографическом изображении. Например, если полученная картографическая информация в векторной форме измеряется в метрах, то units-per-pixel=100 означает, что в 1 пикселе будет рисоваться данные из квадрата 100x100 метров на экваторе (в силу специфики используемой проекции). В частном примере реализации параметр масштаба (units-per-pixel) содержится в картографической информации, полученной на этапе (101), и может быть извлечен из картографической информации для вычисления (301) ограничивающих прямоугольников. На второй схеме Фиг. 3 проиллюстрированы наборы мультиполигонов из разных слоев, каждый из которых заключен в ограничивающий прямоугольник (312).

[0066] Далее по вычисленному набору ограничивающих прямоугольников (312) строится (302) общий ограничивающий прямоугольник (313), который ограничивает все наборы мультиполигонов из всех слоев. Этот процесс осуществляется с помощью операции расширения (extend).

[0067] Псевдокод операции расширения (extend) можно выразить следующим образом:

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

[0069] Перед разделением на тайлы, необходимо определить размер тайла на основании вычисленной глубины цвета. Размер тайла (параметр tile-size) позволяет разбить обрабатываемую область картографической информации (т.е. картографическое изображение), на прямоугольные фрагменты (тайлы) размера tile-size х tile-size пикселей, причем в каждом из тайлов допускается использование своей палитры цветов размера 2^∧(bits-per-pixel) - 1, что позволяет увеличить количество обрабатываемых слоев и оптимизировать потребляемые вычислительные ресурсы путем значимой экономии используемой памяти. Таким образом, от параметра tile-size зависит количество тайлов, на которое будет разбито картографическое изображение. Параметр tile-size подбирается так, чтобы количество слоев в одном тайле не превышало значения 2^∧(bits-per-pixel) - 1, а количество тайлов было минимальным.

[0070] В частном примере реализации такие параметры, как размер тайла (tile-size) и количество тайлов подбираются с помощью инструментов для автоматического подбора параметров. В качестве таких инструментов могут выступать, но не ограничиваться указанными примерами: GridSearchCV [5], RandomizedSearchCV [6], Hyperopt [7].

[0071] В альтернативном варианте воплощения заявленного решения размер тайла (tile-size) и количество тайлов определяют с помощью автоматического машинного обучения (AutoML). AutoML - это процесс автоматизации выбора алгоритма, создания функций, настройки гиперпараметров, итеративного моделирования и оценки модели.

[0072] В качестве AutoML может быть использован, но не ограничиваться, реализуемый на базе платформы AI Cloud ML Space, сервис AutoML [8]. Указанный сервис позволяет на основе заранее подготовленных датасетов определять оптимальные значения параметров, таких как размер тайла (tile-size) и количество тайлов, при этом под оптимальными значениями параметров понимаются значения параметров, удовлетворяющие следующим условиям:

• в каждом тайле количество слоев должно быть не больше 2^∧(bits-per-pixel) - 1,

• количество тайлов должно быть минимальным.

[0073] Далее на основе вычисленного общего ограничивающего прямоугольника и размера тайла выполняют разделение обрабатываемой картографической информации на тайлы (тайлинг). В частном примере реализации вся дальнейшая обработка производится по-тайлово, что позволяет кодировать большее число слоев не увеличивая глубину цвета. В другом частном примере реализации каждому тайлу присваиваются координаты, определяющие положение тайла в пространстве. На Фиг. 4 представлена схема реализации процесса тайлинга картографического изображения. Проиллюстрированное картографическое изображение разбивается на 9 тайлов (401), причем максимальное количество слоев в каждом из тайлов (401) не превышает 3, с учетом параметра bits-per-pixel=3, т.е. 2²-1=3.

[0074] В мультипроцессорных (многопоточных) средах обработка на этапах (102-104) ведется построчно, где каждая строка (411, 412, 413), представляющая набор из нескольких тайлов обрабатывает параллельно и независимо от остальных строк, что позволяет добиться большей производительности заявленного решения.

[0075] На этапе (102) выполняют растеризацию полученной на этапе (101) картографической информации. В частном примере реализации растеризация может быть осуществлена на основании по меньшей мере таких параметров, как масштаб (units-per-pixel), глубина цвета (bits-per-pixel), количество тайлов и их координаты, причем указанные параметры получены или вычислены на предыдущих этапах.

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

• каждый тайл обрабатывается независимо и параллельно,

• внутри каждого тайла обработка ведется построчно, т.е. строчки пикселей растеризуются последовательно сверху-вниз.

[0077] В результате осуществления этапа (102) получается растрированная картографическая информация, которая в частном варианте реализации может быть представлена в виде аналога RGB-изображения, содержащего связную (в топологическом смысле) и огрубленную геометрию (вследствие масштабирования с параметром units-per-pixel), где каждому цвету соответствует уникальный идентификатор слоя. Необходимо отметить, что разный масштаб (параметр units-per-pixel) позволяет получить геометрию различной детализации, т.е. чем меньше значение параметра units-per-pixel, тем более детализированное изображение получаем. Полученная таким образом растрированная картографическая информация (в частном случае, растрированное картографическое изображение) позволяет производить дальнейшую обработку без отдельной обработки ситуации плохо прилегающих смежных кривых (между объектами с общей границей).

[0078] На Фиг. 2 представлена схема реализации компьютерно-реализуемого способа генерализации карты на примере конкретных объектов. В качестве таких объектов в поле (221) могут выступать, но не ограничиваться ими: синий треугольник, красный пятиугольник с вписанным квадратом, оранжевый квадрат. Объекты представлены в векторной форме и состоят из мультиполигонов. Различные цвета объектов свидетельствуют об их отнесении к разным слоям, поскольку, как отмечалось ранее, цвет является идентификатором слоя.

[0079] После выполнения растеризации (201) объекты преобразуются из векторной формы в растровую форму. В поле (222) проиллюстрирован пример такого преобразования, где вышеуказанные объекты представлены в виде набора пикселей, причем объекты имеют огрубленную геометрию по сравнению с векторной формой представления.

[0080] На этапе (103) выполняют фильтрацию растрированной на этапе (102) картографической информации. Этап (103) фильтрации способствует устранению промежутков между объектами, возникающих, например, при изменении масштаба, а также сглаживанию границ объектов, таким образом повышая качество генерализации карты.

[0081] В одном из частных примеров реализации фильтрации растрированной картографической информации включает:

• применение (202) набора сверточных фильтров к растрированной картографической информации, и/или

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

[0082] Необходимо отметить, что в одном из альтернативных вариантов воплощения заявленного решения в качестве сверточных фильтров применяются фильтры, используемые для морфологических преобразований. В качестве примера, но не ограничиваясь им, фильтры, используемые для морфологических преобразований, основаны на операции дилатация (dilation) и/или эрозия (erosion). Применение (202) набора сверточных фильтров к растрированной картографической информации (в частности, к растрированному картографическому изображению) дополнительно позволяет объединить объекты, между которыми есть промежутки (щели), сгладить границы, тем самым устранив визуальные изъяны на изображении, и как следствие повысить качество генерализации карты.

[0083] Пример применения (202) набора сверточных фильтров проиллюстрирован на Фиг. 2 в поле (223), где к объектам, представленным в виде набора пикселей, применены сверточные фильтры.

[0084] В альтернативном варианте воплощения заявленного решения фильтрация (103) растрированной картографической информации дополнительно включает этап получения значений параметров фильтрации, предшествующий вышеуказанным операциям (202, 203). При этом применение набора сверточных фильтров к растрированной картографической информации основано на полученных значениях параметров фильтрации.

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

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

[0087] Метрика 1. Сравнение площади объектов.

[0088] Вычисляем значение площади для изначальных объектов Si и для генерализованных объектов GSj. После этого анализируем отношение

|SUM S_i - SUM GS_j|/SUM S_i → 0%,

где SUM - сумма площадей объектов.

[0089] Отклонение должно стремиться к 0%, т.е. чем меньше отклонение, тем качественнее была выполнена генерализация.

[0090] Метрика 2. Количество полигонов и количество точек.

[0091] Вычисляем количество полигонов MP и кол-во точек Р у изначальных объектов, а также количество полигонов GMP и точек GP у генерализованных объектов.

[0092] Показателем качественной генерализации является тот факт, что GMP<MP, т.е. количество генерализованных объектов всегда меньше или равно изначальным, GP<Р, т.е. количество точек у генерализованных объектов, всегда меньше чем у изначальных объектов.

[0093] В качестве примера, но не ограничиваясь им, изначальную геометрию соотносим с условным 19-ым зумом (англ. zoom - изменение масштаба изображения). При масштабировании геометрии в 13-ом зуме, ориентир для уменьшения количества точек рассчитывается, как ~2^(19-13), т.е. количество точек при указанном изменении масштаба должно уменьшится по сравнению с изначальным значением в 64 раза.

[0094] Метрика 3. Отклонение сопоставленных точек.

[0095] Делаем поиск OP_i(x_i, y_i) изначальных точек для GP_j(x_j, y_j) генерализованных точек в радиусе на максимальную близость по х и у координатам (т.е. решаем задачу поиска ближайшего соседа в заданном радиусе). По сопоставленным точкам (их количество k≤j) вычисляем максимальное отклонение X_k и Y_k по координатам точек.

[0096] Анализируем МАХ и MIN от отклонений, а также медианное и среднее значения. Этот механизм позволят не только делать измерения качества, но и в целом оценивать смещение объектов, что позволяет делать центровку между изначальной и генерализованной геометриями.

[0097] Метрика 4. Отклонение линий.

[0098] У генерализованной геометрии выбираются попарно точки GPj и GPj+1, чтобы получился отрезок, при этом выбор точек последовательно осуществляется по часовой стрелке. К отрезку строится сеть перпендикуляров до пересечения с изначальной геометрией. Перпендикуляры строятся сеткой, может быть выбран вариант равномерной и неравномерной сетки.

[0099] Полученные перпендикуляры являются отклонениями для отрезков в генерализованной геометрии. Для расчетов используется среднее отклонение по перпендикулярам, анализируется МАХ и MIN от отклонений, а также медианное и среднее значения.

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

[0101] В качестве параметров фильтрации могут выступать, но не ограничиваться указанными примерами: форма ядра фильтра, размер фильтра (filter-radius), сила фильтра (object-coef), минимальная допустимая площадь (min-object-area). Примеры применения различных параметров фильтрации наглядно проиллюстрированы на Фиг. 5.

[0102] В качестве формы ядра фильтра могут использоваться различные геометрические формы, однако в предпочтительном варианте воплощения такой формой является круг, поскольку он дает наилучший результат (по результатам А/В-тестирования).

[0103] Параметр размер фильтра (filter-radius) влияет на «округлость» геометрии, чем больше значение параметра filter-radius, тем более «округлая» геометрия получается. Влияние параметра filter-radius на результат фильтрации наглядно проиллюстрирован на Фиг. 5 (элемент 501).

[0104] Значение параметра object-coef влияет на «агрессивность» фильтра, значения object-coef<1 сжимает геометрию, значения object-coef>1 растягивает геометрию. Влияние параметра object-coef на результат фильтрации наглядно проиллюстрирован на Фиг. 5 (элемент 502).

[0105] Параметр минимальной допустимой площади (min-object-area) характеризует минимально допустимую площадь в пикселях по меньшей мере одного объекта из слоя. Такой подход позволяет вычислить площадь растрированных объектов в пикселях и удалить те объекты, площадь которых меньше параметра минимальной допустимой площади (min-object-area). Влияние параметра min-object-area на результат фильтрации наглядно проиллюстрирован на Фиг. 5 (элемент 503).

[0106] Параметр min-object-area связан с параметром масштаба (units-per-pixel), который задает соотношение между единицами измерения расстояния на экваторе (метрами) и пикселями в растрированном изображении. Таким образом, связь между параметрами min-object-area и units-per-pixel задает связь между площадью в метрах и площадью в пикселях.

[0107] Пример применения (203) фильтрации по площади проиллюстрирован на Фиг. 2 в поле (224), где в процессе сравнения площади объектов в пикселях с пороговым значением (т.е. параметром минимальной допустимой площади) удален объект - оранжевый квадрат, площадь которого оказалась меньше значения параметра min-object-area.

[0108] В альтернативном варианте воплощения заявленного решения этап применения набора сверточных фильтров осуществляется прямо на этапе (102) растеризации. Симметричность ядра фильтра ([10], [11]) дает возможность применять фильтр построчно, а не попиксельно, по аналогии с оптимизациями для фильтра Гаусса [12], что позволяет получить более оптимальный доступ к памяти и, как следствие, более высокую производительность.

[0109] На этапе (104) выполняют векторизацию отфильтрованной на этапе (103) растрированной картографической информации.

[0110] В одном из частных примеров реализации этап векторизации (104) отфильтрованной растрированной картографической информации включает:

• нахождение опорных точек на границах смежных объектов,

• построение границ объектов на основании найденных опорных точек,

• построение по меньшей мере одной общей границы между смежными объектами путем объединения общих вершин с одинаковыми координатами,

• восстановление набора мультиполигонов с учетом по меньшей мере одной общей границы объектов.

[0111] Реализация этапов процесса векторизации проиллюстрирована на Фиг. 6.

[0112] В процессе векторизации (104) осуществляют поиск опорных точек на границах смежных объектов. В качестве опорных точек выступают пиксели на растрированном картографическом изображении, которые обладают определенным свойством, а именно соседи у таких пикселей разного цвета, т.е. принадлежат к разным слоям. На этапе нахождения опорных точек осуществляют поиск координат таких пикселей, соседи которых имеют 3 или более различных идентификаторов слоев (цветов). Отдельно обрабатываются граничные случаи, например, точки в углах изображения (0, 0), (0, h), (w, 0), (w, h). Цвет фона (т.е. пиксели, не занятые объектами) выступает в качестве отдельного идентификатора (идентификатор фонового слоя) и учитывается при поиске опорных точек. Цель этапа - найти опорные точки на стыках объектов, принадлежащих разным слоям (учитывая фоновый слой без объектов), которые в дальнейшем используются для построения графа допустимых отрезков, который служит для построения границ объектов.

[0113] Найденные опорные точки впоследствии позволяют построить общую границу между отдельными смежными объектами используя общие вершины с одинаковыми координатами. Построение общей границы позволяет оптимизировать процесс векторизации за счет переиспользования общих границ при преобразовании отфильтрованной растрированной картографической информации в векторную форму представления (т.е. при преобразовании из наборов пикселей в мультиполигоны). Обращаясь к Фиг. 6, например, при векторизации «желтого» объекта, характеризующегося набором желтых пикселей, строим границу «желтого» объекта, и если часть границы общая с другим объектом («красным» объектом, характеризующимся набором красных пикселей), то используем значения опорных точек общей границы для построения границы «красного» объекта. Аналогично, для построения границы «зеленого» объекта используем значения опорных точек общей границы между «красным» и «зеленым» объектами.

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

[0115] Пример выполнения векторизации (204) проиллюстрирован на Фиг. 2 в поле (225), где объекты, представленные в виде набора пикселей (в растровой форме представления), подвергшиеся фильтрации (202, 203) преобразуются в объекты, представленные в виде восстановленного набора мультиполигонов (в векторной форме представления). На Фиг. 2 наглядно продемонстрирована разница между исходными объектами, состоящими из мультиполигонов (поле (221)) и преобразованными объектами, состоящими из восстановленных мультиполигонов (поле (225)). Объекты претерпели следующие изменения: синий треугольник теперь имеет закругленные (сглаженные в результате фильтрации) углы; красный пятиугольник также имеет закругленные (сглаженные в результате фильтрации) углы, кроме того, вписанный в него квадрат в ходе фильтрации изменил форму на окружность; оранжевый квадрат был удален в ходе осуществления фильтрации по площади.

[0116] На этапе (105) формируют генерализированную карту на основе восстановленного набора мультиполигонов, полученного на этапе (104) векторизации.

[0117] В частном примере реализации вместе с генерализованной картой дополнительно формируется информация о значениях параметров, используемых на этапах (102-104), например, но не ограничиваюсь, в качестве метаданных [13]. Эта информация может быть использована для анализа и дальнейшего усовершенствования способа генерализации карты.

[0118] На Фиг. 7 представлен общий вид вычислительного устройства (700), на базе которого может быть реализовано устройство для генерализации карты, обеспечивающее реализацию способа генерализации карты.

[0119] В общем случае вычислительное устройство (700) содержит объединенные общей шиной информационного обмена один или несколько процессоров (701), средства памяти, такие как ОЗУ (702) и ПЗУ (703), интерфейсы ввода/вывода (704), устройства ввода/вывода (705), и средство для сетевого взаимодействия (706).

[0120] Процессор (701) (или несколько процессоров, многоядерный процессор) могут выбираться из ассортимента устройств, широко применяемых в текущее время, например, компаний Intel™, AMD™, Apple™, Samsung Exynos™, MediaTEK™, Qualcomm Snapdragon™ и т.п. В качестве процессора (701) может также применяться графический процессор, например, Nvidia, AMD, Graphcore и пр.

[0121] ОЗУ (702) представляет собой оперативную память и предназначено для хранения исполняемых процессором (701) машиночитаемых инструкций для выполнение необходимых операций по логической обработке данных. ОЗУ (702), как правило, содержит исполняемые инструкции операционной системы и соответствующих программных компонент (приложения, программные модули и т.п.).

[0122] ПЗУ (703) представляет собой одно или более устройств постоянного хранения данных, например, жесткий диск (HDD), твердотельный накопитель данных (SSD), флэш-память (EEPROM, NAND и т.п.), оптические носители информации (CD-R/RW, DVD-R/RW, Blu-Ray Disc, MD) и др.

[0123] Для организации работы компонентов устройства (700) и организации работы внешних подключаемых устройств применяются различные виды интерфейсов В/В (704). Выбор соответствующих интерфейсов зависит от конкретного исполнения вычислительного устройства, которые могут представлять собой, не ограничиваясь: PCI, AGP, PS/2, IrDa, FireWire, LPT, COM, SATA, IDE, Lightning, USB (2.0, 3.0, 3.1, micro, mini, type C), TRS/Audio jack (2.5, 3.5, 6.35), HDMI, DVI, VGA, Display Port, RJ45, RS232 и т.п.

[0124] Для обеспечения взаимодействия пользователя с вычислительным устройством (700) применяются различные устройства (705) В/В информации, например, клавиатура, дисплей (монитор), сенсорный дисплей, тач-пад, джойстик, манипулятор мышь, световое перо, стилус, сенсорная панель, трекбол, динамики, микрофон, средства дополненной реальности, оптические сенсоры, планшет, световые индикаторы, проектор, камера, средства биометрической идентификации (сканер сетчатки глаза, сканер отпечатков пальцев, модуль распознавания голоса) и т.п.

[0125] Средство сетевого взаимодействия (706) обеспечивает передачу данных устройством (700) посредством внутренней или внешней вычислительной сети, например, Интранет, Интернет, ЛВС и т.п. В качестве одного или более средств (706) может использоваться, но не ограничиваться: Ethernet карта, GSM модем, GPRS модем, LTE модем, 5G модем, модуль спутниковой связи, NFC модуль, Bluetooth и/или BLE модуль, Wi-Fi модуль и др.

[0126] Дополнительно в составе устройства (700) могут также применяться средства спутниковой навигации, например, GPS, ГЛОНАСС, BeiDou, Galileo.

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

[0128] Источники информации:

[1] SpatiaLite - spatial extensions for SQLite. https://www.gaia-gis.it/gaia-sins/spatialite-manual-2.3.1.html

[2] ГОСТ 21667-76 Картография. Термины и определения

[3] ГОСТ 28441-99 Картография цифровая. Термины и определения

[4] Берлянт А.М. КАРТОГРАФИЧЕСКАЯ ГЕНЕРАЛИЗАЦИЯ // Большая российская энциклопедия. Том 13. Москва, 2009, стр. 237

[5] Sklearn.mode_lselection.GridSearchCV - scikit-learn 1.2.0 documentation. https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.GridSearchCV.html

[6] Sklearn.mode_lselection.RandomizedSearchCV - scikit-learn 1.2.0 documentation. https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.RandomizedSearchCV.html

[7] Hyperopt Documentation, https://hyperopt.github.io/hyperopt/

[8] AutoML - документация AI Cloud ML Space. Руководство пользователя. https://docs.sbercloud.ru/aicloud/mlspace/concepts/automl.html

[9] Scanline rendering. https://en.wikipedia.org/wiki/Scanline_rendering

[10] Separable filter. https://en.wikipedia.org/wiki/Separable_filter

[11] John Chapman. Optimizing Convolutions. https://john-chapman.github.io/2019/03/29/convolution.html

[12] Матричные фильтры обработки изображений, https://habr.com/ru/post/142818/

[13] ГОСТ Р 52573-2006. Географическая информация. Метаданные

Изобретение относится к способу и устройству генерализации карты. Технический результат заключается в повышении качества генерализации карты. Способ содержит этапы, на которых: a) получают картографическую информацию в векторной форме, содержащую по меньшей мере один слой, содержащий набор мультиполигонов для однотипных объектов; b) выполняют растеризацию полученной картографической информации; c) выполняют фильтрацию растрированной картографической информации; d) выполняют векторизацию отфильтрованной растрированной картографической информации, причем в процессе векторизации осуществляют: нахождение опорных точек на границах смежных объектов, построение границ объектов на основании найденных опорных точек, построение по меньшей мере одной общей границы между смежными объектами путем объединения общих вершин с одинаковыми координатами, восстановление набора мультиполигонов с учетом по меньшей мере одной общей границы объектов; e) формируют генерализированную карту на основе восстановленного набора мультиполигонов. 2 н. и 8 з.п. ф-лы, 7 ил.

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

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

b) выполняют растеризацию полученной картографической информации;

c) выполняют фильтрацию растрированной картографической информации;

d) выполняют векторизацию отфильтрованной растрированной картографической информации, причем в процессе векторизации осуществляют:

• нахождение опорных точек на границах смежных объектов,

• построение границ объектов на основании найденных опорных точек,

• построение по меньшей мере одной общей границы между смежными объектами путем объединения общих вершин с одинаковыми координатами,

• восстановление набора мультиполигонов с учетом по меньшей мере одной общей границы объектов;

e) формируют генерализированную карту на основе восстановленного набора мультиполигонов.

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

3. Способ по п. 2, характеризующий тем, что этап предварительной обработки картографической информации включает:

• вычисление требуемой глубины цвета,

• вычисление общего ограничивающего прямоугольника для всех слоев, содержащих наборов мультиполигонов,

• определение размера тайла с учетом вычисленной глубины цвета,

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

4. Способ по п. 3, характеризующий тем, что глубина цвета вычисляется по формуле:

bits-per-pixel=ceil(log2(N+1)),

где N - количество слоев полученной картографической информации.

5. Способ по п. 4, характеризующий тем, что каждый слой имеет идентификатор, соответствующий уникальному цвету, выраженному битовой последовательностью, при этом значение битовой последовательности зависит от вычисленной глубины цвета.

6. Способ по п. 3, характеризующий тем, что на этапах b)-d) обработка ведется построчно, где каждая строка, представляющая набор из нескольких тайлов, обрабатывает параллельно и независимо от остальных строк.

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

8. Способ по п. 1, характеризующий тем, что этап фильтрации растрированной картографической информации включает:

• применение набора сверточных фильтров к растрированной картографической информации, и/или

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

9. Способ по п. 8, характеризующий тем, что в качестве сверточных фильтров применяются фильтры, используемые для морфологических преобразований.

10. Устройство для генерализации карты, содержащее:

по меньшей мере один процессор,

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