СПОСОБ И СИСТЕМА ОПРЕДЕЛЕНИЯ МЕСТОПОЛОЖЕНИЯ ПОЛЬЗОВАТЕЛЯ
METHOD AND SYSTEM FOR DETERMINING THE LOCATION OF THE USER

ОБЛАСТЬ ТЕХНИКИ
[0001] Настоящее техническое решение в общем относится к области обработки цифровых данных, а в частности, способам и системам для целей определения местоположения пользователя в системах визуального позиционирования (англ. Visual Positioning System).
УРОВЕНЬ ТЕХНИКИ
[0002] Разработки в области определения местоположения пользователя с помощью мобильных вычислительных устройств всегда являлись приоритетной областью разработок с учетом стремительного развития сектора потребительской цифровой техники. Наиболее часто используемыми подходами являются программные приложения (например, Яндекс.Карты, Google Maps, Navitel и т.п.), предлагающие различные цифровые карты для позиционирования пользователя с помощью получения его координат ГНСС (Глобальная навигационная спутниковая система), например, с помощью приемников GPS/ГЛОНАСС, массово встраиваемых в мобильные устройства.
[0003] Данные подходы обладают существенным недостатком в части отсутствия возможности анализа и определения местоположения пользователя в условиях реальных объектов окружающего пространства, с помощью их захвата камерой мобильного устройства.
[0004] Для решения данной проблемы могут использоваться известные из уровня техники системы визуального позиционирования, которые позволяют обрабатывать изображения окружающего пространства с помощью камеры мобильного устройства для целей определения местоположения пользователя с учетом его позиции и направления обзора.
[0005] Данные подходы построены на принципе определения локализации камеры мобильного устройства, в частности, существуют структурные методы (см., например, Active Search: Torsten Sattler, Bastian Leibe, Leif Kobbelt, Improving Image-Based Localization by Active Correspondence Search, ECCV 2012, 2012, pp 752-765.) и методы глубокого обучения (PoseNet: A. Kendall, М. Grimes, R. Cipolla, Posenet: A convolutional network for real-time 6-dof camera relocalization, In Proceedings of the IEEE international conference on computer vision, 2015, pp. 2938-2946).
[0006] Структурные методы позволяют достичь достаточно высокий показатель точности, но являются требовательными к вычислительным мощностям, что обуславливает более длительное время для выполнения требуемых вычислений. Методы глубокого обучения напротив, позволяют выполнить требуемые вычисления достаточно быстро, но при этом качество позиционирования данных методов не позволяет получить достаточный показатель точности позиционирования камеры мобильного устройства.
[0007] Задача абсолютной локализации камеры в известном окружении является ключевой задачей в проектах дополненной реальности, а также вспомогательной задачей в системах навигации мобильных роботов (SLAM-задаче). Основные требования к данному подходу следующие:
• стабильно высокая точность,
• минимальные требования к вычислительным ресурсам и системам хранения информации (возможность решать эту задачу непосредственно на мобильных устройствах),
• высокая скорость решения задачи.
[0008] Для обеспечения указанных требований предлагается создание нового подхода, обеспечивающего локализацию камеры мобильного устройства в условиях известного окружения для определения точного и быстрого местоположения пользователя на основании информации, получаемой с камеры мобильного устройства.
СУЩНОСТЬ ИЗОБРЕТЕНИЯ
[0009] Настоящее техническое решение направлено на решение технической проблемы, заключающейся в быстром и точном определении местоположения пользователя в условиях известного окружения с помощью информации, захватываемой с камеры его мобильного устройства.
[0010] Технический результат совпадает с решением технической проблемы и направлен на повышение точности и скорости определения местоположения мобильного устройства пользователя.
[0011] Заявленный результат достигается за счет компьютерно-реализуемого способа определения местоположения пользователя, выполняемого с помощью процессора и содержащего этапы, на которых:
а) получают пользовательский запрос на определение его местоположения, содержащий по меньшей мере одно изображение, полученное с камеры мобильного устройства пользователя, причем изображение содержит по меньшей мере часть одного из объектов окружающего пространства;
b) определяют глобальный дескриптор для упомянутого изображения, содержащегося в пользовательском запросе;
c) на основании полученного глобального дескриптора определяют
область нахождения пользователя с помощью нахождения трехмерной модели окружения, хранящейся в базе данных предварительно сформированных трехмерных моделей окружения, причем каждая трехмерная модель содержит по меньшей мере набор изображений окружения с различных ракурсов, при этом каждое изображение имеет особые точки, для которых рассчитаны двумерные локальные дескрипторы;
по меньшей мере одно схожее изображение в определенной трехмерной модели окружения, причем определение схожего изображения выполняется с помощью алгоритма поиска ближайших соседей;
d) вычисляют особые точки и рассчитывают для них двумерные локальные дескрипторы на изображении пользовательского запроса;
e) осуществляют сравнение локальных дескрипторов, полученных на этапе d), с локальными дескрипторами по меньшей мере одного изображения трехмерной модели окружения, выявленного на этапе с);
f) определяют подмножество особых точек по итогу выполнения сравнения на этапе е), для которых имеется репроекция трехмерных точек на трехмерной модели окружения;
g) определяют трехмерные координаты и поворот камеры мобильного устройства относительно системы координат трехмерной модели окружения на основании выявленных репроекций для подмножества особых точек на этапе f).
[0012] В одном из частных вариантов осуществления способа двумерные локальные дескрипторы определяется с помощью алгоритма масштабно-инвариантной трансформации признаков (SIFT).
[0013] В другом частном варианте осуществления способа для каждой особой точки вычисляются трехмерные координаты.
[0014] В другом частном варианте осуществления способа для каждого изображения, формирующего трехмерную модель окружения, определяется по меньшей мере один глобальный дескриптор.
[0015] В другом частном варианте осуществления способа глобальные дескрипторы определяются с помощью по меньшей мере одной искусственной нейронной сети (ИНС).
[0016] В другом частном варианте осуществления способа на основании глобальных дескрипторов формируется поисковый индекс.
[0017] В другом частном варианте осуществления способа поисковый индекс сохраняется в базе данных в бинарном формате как элемент трехмерной модели окружения.
[0018] В другом частном варианте осуществления способа пользовательский запрос дополнительно содержит данные, получаемые от инерциального измерительного устройства мобильного устройства пользователя.
[0019] В другом частном варианте осуществления способа для трехмерной модели определяются точки соответствия на двумерных изображениях с трехмерными точками модели.
[0020] В другом частном варианте осуществления способа на основании соответствующих точек выделяется набор точек на трехмерной модели для оценки положения камеры мобильного устройства.
[0021] В другом частном варианте осуществления способа дополнительно используются координаты ГНСС мобильного устройства.
[0022] В другом частном варианте осуществления способа каждая трехмерная модель дополнительно содержит координаты ГНСС.
[0023] Заявленное изобретение также осуществляется с помощью системы для определения местоположения пользователя, которая содержит сервер и мобильное устройство пользователя, в которой
мобильное устройство пользователя выполнено с возможностью
- получения по меньшей мере одного изображения с камеры мобильного устройства, причем изображение содержит по меньшей мере часть одного из объектов окружающего пространства;
- формирования пользовательского запроса на определение местоположения, содержащего упомянутое по меньшей мере одно изображение;
сервер выполнен с возможностью
- определения глобального дескриптора для упомянутого изображения, содержащегося в пользовательском запросе;
- на основании полученного глобального дескриптора определения трехмерной модели окружения, хранящейся в базе данных предварительно сформированных трехмерных моделей окружения, причем каждая модель содержит набор изображений окружения с различных ракурсов, при этом каждое изображение имеет особые точки, для которых рассчитаны двумерные локальные дескрипторы;
по меньшей мере одно схожее изображение в найденной трехмерной модели окружения, причем определение изображений выполняется с помощью алгоритма поиска ближайших соседей;
- определения на основании полученного глобального дескриптора изображения пользовательского запроса
- осуществления сравнения локальных дескрипторов с локальными дескрипторами по меньшей мере одного изображения трехмерной модели окружения;
- вычисления особых точек и двумерных локальных дескрипторов для них на изображении пользовательского запроса;
- определения подмножества особых точек по итогу выполненного сравнения локальных дескрипторов, для которых имеется репроекция трехмерных точек на трехмерной модели окружения;
- определения трехмерных координат и поворота камеры мобильного устройства относительно системы координат трехмерной модели окружения на основании выявленных репроекций для подмножества особых точек.
[0024] В одном из частных вариантов реализации системы мобильное устройство пользователя выбирается из группы: смартфон, планшет, портативная игровая приставка, ноутбук, устройство дополненной реальности.
[0025] В одном из частных вариантов реализации системы обмен данными между мобильным устройством пользователя и сервером осуществляется посредством информационной сети Интернет.
[0026] В одном из частных вариантов реализации системы мобильное устройство пользователя при формировании запроса дополнительно учитывает ГНСС координаты устройства.
[0027] В одном из частных вариантов реализации системы поиск моделей трехмерного пространства осуществляется с учетом ГНСС координат мобильного устройства пользователя.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[0028] Фиг. 1 иллюстрирует блок-схему выполнения заявленного способа.
[0029] Фиг. 2А иллюстрирует пример 3D модели окружения в открытом пространстве.
[0030] Фиг. 2Б иллюстрирует пример 3D модели окружения внутри помещения.
[0031] Фиг. 3А иллюстрирует принцип обмена данными между пользователем и сервером.
[0032] Фиг. 3Б иллюстрирует пример сравнения особых точек между изображениями модели окружения и кадром с камеры устройства пользователя.
[0033] Фиг. 4 иллюстрирует общий вид вычислительного устройства для реализации заявленного изобретения.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
[0034] Как представлено на Фиг. 1 заявленный способ (100) определения местоположения пользователя осуществляется с помощью выполнения последовательных этапов. В основу способа положено формирование трехмерных моделей (3D) окружения для целей их использования при последующей локализации позиции пользователей с помощью анализа изображений, фиксируемых с помощью мобильных устройств.
[0035] На Фиг. 2А-Фиг. 2Б представлены примеры созданной 3D модели окружения (20) по группе изображений с различных ракурсов (201)-(203). Построение модели окружения состоит из следующих этапов. С помощью программного обеспечения, обеспечивающего создание трехмерных реконструкций, например, программное обеспечение, созданное на базе фреймворков ARKit, COLMAP, OpenMVG, pytorch, TensorFlow и т.п., создается последовательность изображений, на которых видны все элементы описываемого окружения с разных ракурсов, например, здания, группы зданий, улицы, внутренняя планировка зданий, объекты окружения, архитектурные элементы, мебель, предметы интерьера и т.п. Также программа сохраняет информацию о положении камеры для каждого изображения (эта информация используется для последующей валидации расчетов). В качестве такой информации используется 6-Dof позиция пользователя, в частности, его трехмерное положение и углы поворота в трехмерном пространстве (x, y, z).
[0036] Съемка изображений (201)-(203) ведется по определенной методике: в виде последовательных поворотов камеры в горизонтальной плоскости и последующего перехода к следующей точке съемки. Это повышает точность расчетов.
[0037] Полученная 3D модель (20) представляет собой облако точек, формируемое в ходе упомянутой съемки. На каждом изображении выделяются особые точки (2011)-(2013), для которых определяются двумерные (2D) локальные дескрипторы с помощью алгоритма масштабно-инвариантной трансформации признаков (SIFT). Также, могут применяться такие примеры алгоритмов, как ORB, SURF, LIFT, BRIEF, SuperPoint и др.
[0038] Вычисленные локальные дескрипторы сохраняются в базу данных в заданном формате, например, COLMAP (система формирования структур из движения, англ. structure-from-motion). С помощью COLMAP осуществляется построение облака точек трехмерной модели (20), по которому реализуется возможность расчета репродукции положения двумерных точек (2011)-(2013) в трехмерной системе координат трехмерной модели (20). В качестве особых двумерных точек (2011)-(2013) могут использоваться различные отличимые части объектов окружения, например, части зданий, элементы построек (арки, вывески, колонны, статуи и т.п.) и др.
[0039] Для каждого изображения вычисляются глобальные дескрипторы с использованием модели машинного обучения, например, искусственной нейронной сети NetVLAD, предобученной на датасете Pittsburgh 30k. Глобальный дескриптор представляет собой вектор, отражающий основную информацию, закодированную на изображении.
[0040] По глобальным дескрипторам создается поисковый индекс с помощью одного из применяемых способов, например, FAISS, Nmslib, Falconn и др. Поисковый индекс представляет собой структуру данных, которая содержит информацию об изображениях и используется в системах поиска по изображению. Поисковый индекс сохраняется в бинарном формате как элемент 3D модели окружения (20).
[0041] Далее рассмотрим процесс выполнения способа (100) с отсылкой к Фиг. 3А-3Б. На этапе (101) пользователь (30) с помощью мобильного устройства (300) инициирует запрос на выполнение определения его местоположения, который передается на сервер (302) посредством сети передачи данных (305), например, Интернет. Пользовательский запрос содержит одно или несколько изображений (301), захватываемых с помощью камеры устройства (300). Изображение (301) в общем случае содержит по меньшей мере часть одного из объектов окружающего пространства, например, здание, элемент внутренней отделки, архитектуры и т.п. Изображение (301) также может дополнительно учитывать координаты ГНСС мобильного устройства, получаемые с помощью соответствующего антенного модуля устройства (300) (GPS, ГЛОНАСС, BeiDou и др.). Дополнительно пользовательский запрос может содержать информацию, получаемую с инерциальных датчиков мобильного устройства (300), например, показания гироскопа.
[0042] На этапе (102) на сервере (302) выполняется определение глобального дескриптора для полученного пользовательского изображения (301). Определение глобального дескриптора для изображения (301), которое содержит полностью или частично объект (или его часть) окружения, может осуществляться с помощью упомянутой ранее искусственной нейронной сети NetVlad или любого другого способа, пригодного для выполнения данной функции.
[0043] На этапе (103) на основании полученного глобального дескриптора сервер (302) осуществляет определение предполагаемой области нахождения пользователя (30). Данное определение осуществляется на основании сравнения полученного глобального дескриптора с хранящимися в базе данных (303) предварительно сформированных трехмерных моделей окружения (20).
[0044] Для каждой модели (30) сформирован поисковый индекс на основании глобальных дескрипторов, входящих в них изображений (201)-(203) с различных ракурсов с рассчитанными локальными 2D дескрипторами в соответствующих особых точках (2011)-(2013).
[0045] На этапе (104) при нахождении одной или нескольких подходящих моделей (20) при их анализе на предмет схожести с глобальным дескриптором пользовательского изображения (301), осуществляется поиск одного или нескольких изображений (201)-(203), формирующих упомянутую 3D модель окружения (20), для целей последующего выявления схожих объектов окружения. Алгоритмически выявляется ряд схожих изображений соответствующей 3D модели окружения (20). Определение изображений выполняется с помощью определения меры близости (L2-норма) при помощи метода, основанного на поиске изображений по алгоритму ближайших соседей, например, с помощью метода FAISS (сокр. от англ. Facebook AI Research Similarity Search).
[0046] На этапе (105) осуществляется вычисление особых точек (ЗОН)-(3013) для изображения (301) пользовательского запроса и выполняется расчет для упомянутых точек двумерных локальных дескрипторов с помощью вышеуказанного алгоритма SIFT.
[0047] Далее осуществляется сравнение (этап 106) вычисленных двумерных локальных дескрипторов, полученных на этапе (105), с дескрипторами изображений (201)-(203) трехмерной модели окружения (20). Как показано на Фиг. 3Б, по итогам выполненного сравнения локальных дескрипторов на этапе (107) определяется подмножество двумерных точек на как минимум одном выявленном изображении (201)-(203) модели трехмерного окружения (20).
[0048] На этапе (107) выполняется анализ соответствия дескрипторов изображений (201) для модели окружения (20), хранящейся в базе данных (303), и изображением пользователя (301). На данном этапе осуществляется определение подмножества особых точек, которые содержатся на изображении пользователя (301) по итогу сравнения с изображениями (201)-(203), для которых имеется репроекция трехмерных точек на трехмерной модели окружения (20).Под репрокцией понимается отображение точки в пространстве с различных ракурсов, что позволяет более точно определить схожие изображения, содержащие данные точки (см, например, Zhang. Camera Models and Image Reprojection // ECE661 Computer Vision Homework 6. 2008).
[0049] Поскольку для изображений (201)-(203), формирующих 3D модель окружения (20), заранее рассчитаны 2D-3D соответствия между точками трехмерной модели (20) и их двумерными проекциями (2011)-(2013) на определенном изображении (201)-(203), то с помощью сравнения двумерных дескрипторов становится возможным определение трехмерных координат (репроекций) для особых точек (3011)-(3013) на пользовательском изображении (301).
[0050] На этапе (108) с помощью алгоритма perspective-n-point (сокр. PNP) осуществляется определение положения камеры устройства (300). Алгоритм PNP обеспечивает решение задачи оценки положения калиброванной камеры по набору из п трехмерных точек в трехмерном пространстве и их соответствующих 2D проекциям на изображении. В качестве такого алгоритма может применяться известный из уровня техники алгоритм P3P+RANSAC (X.S. Gao, X.-R. Hou, J. Tang, H.-F. Chang, Complete Solution Classification for the Perspective-Three-Point Problem, IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 25, issue 8, pp 930-943, 2003).
[0051] С помощью алгоритма PNP определяются трехмерные координаты и данные о повороте камеры мобильного устройства (300) относительно системы координат трехмерной модели окружения (20). Указанное определение выполняется на основании выявленных репроекций для подмножества особых точек (3011)-(3013) пользовательского изображения (301). Это позволяет уточнить местоположение пользователя (30) и получить соответствующие данные на сервере (302).
[0052] Под позицией камеры по итогам работы способа (100) понимается [R, t] - поворот и смещение камеры устройства (300) относительно системы координат облака точек, формирующего трехмерную модель (20), где
[R, t] - это скомбинированная матрица, в которой
R=>{α, β, γ} - углы поворота виртуальной камеры относительно осей Ох, Оу, Oz,
t=>{x, у, z} - смещение положения виртуальной камеры, предсказываемое по пользовательскому изображению.
[0053] В качестве одного из примеров использования настоящего решения является размещение AR-контента при наведении камеры устройства (300) на объекты окружающего мира. За счет того, что осуществляется привязка AR-контента в системе координат облака точек на модели окружения (20), то зная позицию камеры и ее поворот устройства (300) через 2D-3D репроекцию можно получить отображение AR-контента на мобильном устройстве (300).
[0054] Дополнительно могут учитываться полученные координаты ГНСС мобильного устройства (300). Благодаря получаемым координатам ГНСС, на этапе (101) появляется возможность уточнения расположения объекта в мировой системе координат. Каждое облако точек, формирующее ЗД модель (20), также обладает привязкой к позициям в мировой системе координат, таким образом становятся известными примерные значения долготы и широты. Используя априорные знания о расположении благодаря ГНСС, на этапе (103) осуществляется выбор модели (20), в которой будет происходить дальнейший поиск по глобальным дескрипторам (104). Модель (20) выбирается на основании поиска кратчайшего расстояние от значений долготы и широты расположения устройства (300) пользователя и долготы/широты самой модели (20). После нахождения кандидатов (104) и получения двумерного сопоставления дескрипторов на шаге (105), позиция ГНСС также используется во время оптимизационного процесса PnP на этапе (108), в ходе которой добавляется ограничение на возможную позицию в пространстве, равное радиусу (несколько метров) от позиции ГНСС устройства (130). Это улучшает сходимость метода, а также уточняет позицию, получая наилучший результат.
[0055] Заявленный способ (100) определения позиции пользователя (30) может использоваться в качестве поправки при применении алгоритма SLAM (от англ. imultaneous localization and mapping-одновременная локализация и построение карты) внутри помещений. Данный метод используется в мобильных автономных средствах для построения карты в неизвестном пространстве или для обновления карты в заранее известном пространстве с одновременным контролем текущего местоположения и пройденного пути.
[0056] В общем виде процесс использования способа (100) внутри помещений с алгоритмом SLAM выглядит следующим образом. Формируются снимки с помощью ARKit/ARCore и отправляются с соответствующими позициями на сервер (302), сохраняя позиции для последующей корректировки. С помощью применения способа (100) к каждому снимку выполняется предсказывание позиции. С учетом полученных от устройства внутри помещения позиций отбрасываются неверно предсказанные позиции, осуществляется выбор лучшей позиции по количеству инлайеров (англ, inliner, точки, удовлетворяющие модели) после этапа PnP и отправляется на устройство внутри помещения, например, устройство (300) пользователя (30).
[0057] Далее выполняется замена текущей позиции устройства пользователя (300) новой, полученной от сервера (302) позицией, учитывая сохраненную позицию и собственное смещение за время ожидания ответа от сервера (302). Это позволяет повысить точность определения позиции устройства (300) пользователя внутри помещений.
[0058] На Фиг. 4 представлен общий вид вычислительного устройства (400). На базе устройства (400) может быть реализовано устройство пользователя (300), сервер (302) и иные непредставленные устройства, которые могут участвовать в общей информационной архитектуре заявленного решения.
[0059] В общем случае, вычислительное устройство (400) содержит объединенные общей шиной информационного обмена один или несколько процессоров (401), средства памяти, такие как ОЗУ (402) и ПЗУ (403), интерфейсы ввода/вывода (404), устройства ввода/вывода (405), и устройство для сетевого взаимодействия (406).
[0060] Процессор (401) (или несколько процессоров, многоядерный процессор) могут выбираться из ассортимента устройств, широко применяемых в текущее время, например, компаний Intel™, AMD™, Apple™, Samsung Exynos™, MediaTEK™, Qualcomm Snapdragon™ и т.п.
[0061] ОЗУ (402) представляет собой оперативную память и предназначено для хранения исполняемых процессором (401) машиночитаемых инструкций для выполнение необходимых операций по логической обработке данных. ОЗУ (402), как правило, содержит исполняемые инструкции операционной системы и соответствующих программных компонент (приложения, программные модули и т.п.).
[0062] ПЗУ (403) представляет собой одно или более устройств постоянного хранения данных, например, жесткий диск (HDD), твердотельный накопитель данных (SSD), флэш-память (EEPROM, NAND и т.п.), оптические носители информации (CD-R/RW, DVD-R/RW, BlueRay Disc, MD) и др.
[0063] Для организации работы компонентов устройства (400) и организации работы внешних подключаемых устройств применяются различные виды интерфейсов В/В (404). Выбор соответствующих интерфейсов зависит от конкретного исполнения вычислительного устройства, которые могут представлять собой, не ограничиваясь: 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 и т.п.
[0064] Для обеспечения взаимодействия пользователя с вычислительным устройством (400) применяются различные средства (405) В/В информации, например, клавиатура, дисплей (монитор), сенсорный дисплей, тач-пад, джойстик, манипулятор мышь, световое перо, стилус, сенсорная панель, трекбол, динамики, микрофон, средства дополненной реальности, оптические сенсоры, планшет, световые индикаторы, проектор, камера, средства биометрической идентификации (сканер сетчатки глаза, сканер отпечатков пальцев, модуль распознавания голоса) и т.п.
[0065] Средство сетевого взаимодействия (406) обеспечивает передачу данных устройством (400) посредством внутренней или внешней вычислительной сети, например, Интранет, Интернет, ЛВС и т.п. В качестве одного или более средств (406) может использоваться, но не ограничиваться: Ethernet карта, GSM модем, GPRS модем, LTE модем, 5G модем, модуль спутниковой связи, NFC модуль, Bluetooth и/или BLE модуль, Wi-Fi модуль и др.
[0066] Дополнительно могут применяться также средства спутниковой навигации в составе устройства (400), например, GPS, ГЛОНАСС, BeiDou, Galileo.
[0067] Представленные материалы технического решения раскрывают предпочтительные примеры реализации и не должны трактоваться как ограничивающие иные, частные примеры его воплощения, не выходящие за пределы испрашиваемой правовой охраны, которые являются очевидными для специалистов соответствующей области техники.