Волей случая мне повезло принадлежать к интересной породе людей. Мы не прочь встать в выходной пораньше, уехать из города в лес, где на поляне (или опушке) можно обменять небольшую сумму кровных на бумажную карту окрестностей с отмеченными на ней точками. И затем, вооружившись компасом, потратить несколько следующих часов жизни на блуждание по полям, лесам и болотам в поисках этих точек. Чаще в компании, чем в гордом одиночестве.
Со стороны это обычно такие мероприятия выглядят, как толпа бездельников, скитающихся по разным зарослям, уткнувшись в карту, примерно так:
Хотя иногда случается, что иначе (ландшафты разнятся):
Каждая из вожделенных точек называется контрольным пунктом (или просто КП), слегка спрятана от случайных глаз и часто снабжена электронной станцией, которая звонко пикает, когда считывает прикосновение чипа, выданного на старте.
Выглядит КП обычно так (не нашел примера в архивах, фото с Википедии):
Но встречаются и более ламповые варианты:
Карта выглядит плюс-минус следующим образом:
Здесь стоит обратить внимание на три основных момента:
-
карта топографическая — на ней отмечены разные типы ландшафта, дороги и изолинии рельефа
-
место старта и финиша — розовый треугольник
-
контрольные пункты — розовые кружки, у каждого КП есть двузначное число
Называется такое мероприятие — рогейн. А задача участников набрать за отведенное время максимальное количество баллов. Сумма баллов складывается их первых цифр чисел всех найденных КП. То есть участник, нашедший в районе старта три КП: 32, 31 и 74 становится счастливым обладателем 13 баллов в итоговой таблице.
Начинается соревнование сразу после выдачи карты и с самого интересного. Важно что: успеть собрать все КП обычно невозможно физически, поэтому первоочередная задача проложить наиболее оптимальный маршрут, позволяющий получить максимальную сумму баллов. Соревнующиеся, достают нитки, линейки, открывают калькуляторы и уходят с головой в вычисления и споры относительно того, какие КП брать, а какие оставить за бортом.
Выбранный маршрут обычно схематично наносят на карту, обозначая время, до которого надо успеть взять КП, чтобы не начать корректировать свои планы по ходу действа. Вот, например, моя карта с планированием июльского рогейна в окрестностях Галича (мятая, фото постфактум):
Плох тот инженер, которому не приходят мысли об автоматизации любой рутины, пусть даже интересной. Идея научиться рассчитывать идеальный маршрут по фотографии карты догоняла меня долго, но в итоге настигла в этом году. Дальше о решении этой задачи.
Что решаем?
Дано:
-
фотография карты
-
средняя скорость движения
-
ограничение по времени
На выходе:
-
очередность взятия КП и детальный маршрут движения.
Читаем карту
Каждая зона на карте, обозначенная цветом или условными знаками, определяет насколько быстро по ней можно передвигаться.
По полю бежать легко, по дороге или тропе еще легче. В лес лучше по возможности не соваться, в «зеленку» (труднопроходимый лес) лучше не заглядывать вообще. Линии рельефа по возможности пересекать реже. Правил не так много, но карты всегда разные, отсюда интерес.
Чтобы строить маршруты на карте, нужно провести реверс инжиниринг по фотографии и сегментировать карту по скорости передвижения.
Данные для обучения
Я собрал около двух сотен OCAD (.ocd) файлов — это популярный формат редактирования карт для рогейнов или спортивного ориентирования. Готовых изображений карт в сети полно, чего, к сожалению, не скажешь об исходниках.
Далее разметку надо отрендерить в картинку и по символам ISOM (это такой стандарт, как рисовать карты для спортивного ориентирования) собрать маски: каждый тип местности — свой канал в channels.npy (16 классов, примерно как в легенде на изображении выше). Затем можно нарезать картинки и маски на тайлы (у меня 512×512), чтобы получить пары image.jpg + channels.npy. Это собственно и данные для обучения модели сегментации.
Сегментация
Модель — SegFormer MiT-B4 (предобученный на ImageNet). Для каждого пикселя учимся определять один из 16 классов (открытое пространство, зелёнка, дорога, вода, КП и так далее). Обучал примерно 200 эпох на тайлах размером в 512 пикселей с различными аугментациями (повороты, blur, JPEG — имитация реальной фотографии карты в поле перед соревнованием). Функция потерь — CE (угадали класс пикселя) + Dice (не потеряли редкие объекты) + Lovasz (угадали контуры) с весами по редким классам.
Теперь для сегментации достаточно загрузить веса и пробежаться по карте скользящим окном, склеив итоговый результат. На выходе получаем оцифрованную карту скорости передвижения — можно искать самые быстрые маршруты.
Пример выше: чем краснее, тем медленнее.
Находим КП
Контрольные пункты на картах всегда розовые (редко красные) кружки, место старта — треугольник такого же цвета. Нужны их координаты в пределах карты + стоимость КП (первая цифра).
Классический CV
Пыльное университетское прошлое подсовывает классический CV:
-
Выделяем маску (HSV + опционально prior-канал сегментации)
-
Ищем кольца через алгоритм Хафа (Hough), зная примерный диаметр кружка
-
В окне около кольца читаем номер используя OCR
На деле это очень хрупкое решение, потому что реальные фотографии в разных условиях освещения и с разных ракурсов сильно усложняют жизнь Хафу.
Как видно, часть КП теряем, часть определяем с ошибкой.
VLM
На дворе 2026 год — расчехляем VLM (в моем случае qwen3.6-35b-a3b/latest от Yandex Cloud). Просим модель ответить в относительных координатах, где она видит кружки с числами, требуем структурированный ответ. Пример ответа:
{ "controls": [ {"number": 31, "x": 0.22, "y": 0.41, "confidence": 0.92}, {"number": 32, "x": 0.68, "y": 0.35, "confidence": 0.88}, {"number": 33, "x": 0.55, "y": 0.78, "confidence": 0.81} ], "start": {"x": 0.12, "y": 0.18, "confidence": 0.90}}
Для точности движемся тайлами, но все равно точки часто чуть мимо центра.
VLM + refine
Женим два предыдущих подхода: получаем координаты от VLM, а затем уточняем их с помощью классического CV находя в окрестностях окружность около-розорого цвета.
Теперь красота, находим и КП и веса.
Ищем короткий путь
Итак, имеется сетка стоимости перемещения в пространстве. По дороге движемся без штрафа, по лесу замедляемся почти втрое, по зеленке впятеро. По воде плывем совсем медленно. Если в окрестностях точки есть горизонтали рельефа, то увеличиваем штраф — в горку бежать тяжело.
Найти кратчайший по времени, не по расстоянию (!) маршрут можно с помощью классического алогритма A* — идём по сетке и выбираем соседей с минимальным штрафом. Итог — самый быстрый путь с учётом местности.
Как быстрее всего добраться от старта до КП 55:
А до КП 87?
Собираем все вместе
Решаем задачу Orienteering Problem:
выбрать подмножество КП и порядок обхода так, чтобы сумма баллов была максимальна, а суммарное время укладывалось в отведенное для прохождения
Коротко о реализации, это алгоритм перебор подмножеств (DP) в стиле Held–Karp, адаптированный под Orienteering Problem, не классическая задача коммивояжёра (TSP):
-
Как у Held–Karp: состояние «множество посещённых + последний узел», минимальное время до него.
-
В отличие от TSP: не обязаны брать все точки, а в конце максимизируем баллы при лимите времени и возврате на старт.
Весь пайплайн вместе выглядит так:
В результате можно получить отличный персональный маршрут под конкретную физподготовку. Например для средней скорости 1 м/с:
Для 2 м/с:
И для 3 м/с:
Кроме собственно составления маршрутов можно оценивать насколько интересной получилась карта. Например насколько много вариантов прохождения дистанции с плюс-минус одинаковой суммой баллов. Порой весьма занятно рассматривать как проходили гонку лидеры, если организаторы публикуют такие материалы после финиша. Примеры:
Классно, когда вариантов достичь одинаковой суммы много. Причем для разной скорости прохождения дистанции такой разброс вариантов может быть разным, порой интереснее прогуляться восемь часов, нежели пробежать четыре.
Ну и собственно мой маршрут из вступления бездушная машина забраковала, предложив такой:
А посостязаться с алгоритмом в планировании самого удачного в итоге варианта можно только на практике, но это уже совсем другая история.
ссылка на оригинал статьи https://habr.com/ru/articles/1065342/