Определение радиуса погрешности местоположения - RU2680093C2
Код документа: RU2680093C2
Чертежи
Описание
УРОВЕНЬ ТЕХНИКИ
Оценка местоположения используется мобильными обрабатывающими устройствами для установления местоположения устройства и является функцией, используемой множеством приложений на устройстве. Как правило, методы оценки местоположения могут использовать множество различных источников данных для вычисления местоположения. Системы Wi-Fi позиционирования могут обеспечить информацию о местоположении, когда такие устройства в помещении, использованием доступности точек беспроводного доступа. Точность таких подходов зависит от числа положений, которые являются известными для алгоритма позиционирования. Возможные флуктуации сигнала, которые могут иметь место, однако, могут увеличить погрешности и неточности в пути пользователя. Как правило, радиус погрешности определяется для вычисленного положения, который отражает точность определения. В некоторых приложениях, таких как картографические приложения, радиус погрешности отображается вокруг вычисленного положения.
СУЩНОСТЬ ИЗОБРЕТЕНИЯ
Технология предназначена для определения радиуса погрешности, отражающего обеспечиваемую точность прогнозного (или вычисленного) положения обрабатывающего устройства. Структура данных включает в себя радиус погрешности, соотнесенный с масштабируемой географической областью или "плиткой", содержащей область, в которой прогнозное положение может быть определено. Для любого вычисления прогнозного положения на основе наблюдений радиомаяков, быстрый поиск соответствующей масштабируемой области, включающей в себя новое прогнозное положение, в структуре данных выдает радиус погрешности для нового прогнозного положения.
Структура данных может включать в себя множество первых полей, идентифицирующих масштабируемую географическую область, на основе глобальной проекционной справочной системе, и множество вторых полей, идентифицирующих для каждого из первых полей, радиус погрешности положения, связанный с масштабируемой географической областью и уровнем. Каждый радиус погрешности положения вычисляется так, чтобы быть максимальным радиусом погрешности для, по меньшей мере, порогового процента прогнозных положений в соответствующей масштабируемой географической области.
Это краткое изложение сущности изобретения предусмотрено для введения подборки концепций в упрощенной форме, которые дополнительно описаны ниже в подробном описании. Данное краткое изложение сущности изобретения не предназначено для определения ключевых признаков или существенных признаков заявленного изобретения, а также не предназначено для использования в качестве вспомогательного средства при определении объема заявленного изобретения.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Фигура 1 является блок-схемой, иллюстрирующей мобильные обрабатывающие устройства относительно беспроводных радиомаяков, используемых для вычислений положения.
Фигура 2 является развернутым перспективным видом внутреннего местоположения с множеством беспроводных радиомаяков.
Фигура 3 является блок-схемой, представляющей способ в соответствии с представленной технологией для определения положения и радиуса погрешности.
Фигура 4 является блок диаграммой функционального представления первого обрабатывающего устройства и вычислительного устройства.
Фигура 5 является блок диаграммой функционального представления второго обрабатывающего устройства и вычислительного устройства.
Фигура 6 является блок-схемой, представляющая способ заполнения структуры данных для использования при определении радиуса погрешности в соответствии с представленной технологией.
Фигура 7 является блок-схемой, иллюстрирующей этап с фигуры 3 определения радиуса погрешности.
Фигура 8А является иллюстрацией глобальной проекционной справочной системы с масштабируемыми географическими областями различного уровня.
Фигура 8B является иллюстрацией структуры данных.
Фигура 9A является графиком корреляции между вычисленными прогнозными положениями, основанными на двух наборах данных.
Фигура 9В является иллюстрацией корреляций для множества масштабируемых географических областей в плитке.
Фигура 9С является иллюстрацией функции интегральной функции распределения (CDF) относительно вычисленного радиуса погрешности.
Фигура 10 является блок-схемой вычислительной системы.
Фигура 11 является блок-схемой второй вычислительной системы.
ПОДРОБНОЕ ОПИСАНИЕ
Технология предназначена для определения радиуса погрешности, отражающего точность прогнозного (или вычисленного) положения, обеспечиваемого обрабатывающим устройством. Обеспечивается структура данных, которая включает в себя радиус погрешности, соотнесенный с масштабируемой географической областью или "плиткой", включающей область, в которой прогнозное положение может быть определено. Каждый радиус погрешности в структуре данных был рассчитан так, чтобы его точность превышала пороговый процент коррелированных прогнозных положений. Каждое соответствие радиус погрешности - масштабируемая географическая область является результатом корреляции между погрешностями в прогнозных положениях, определенных для двух наборов данных (обучающего набора данных и тестового набора данных) на основе наблюдений радиомаяков данного местоположения, и по отношению к наземным контрольным данным для местоположения. Устанавливается пороговый процент погрешности для корреляции, и масштабируемые области, соответствующие данному порогу, включаются в структуру данных. Для любого последующего вычисления прогнозного положения на основе сделанных новых наблюдений, быстрый поиск соответствующей масштабируемой области в структуре данных возвращает радиус погрешности для прогнозного положения. Радиус погрешности может быть использован для обеспечения обратной связи с пользователем приложения, учитывающего местоположение, на устройстве обработки. Технология может быть выполнена полностью на мобильном обрабатывающем устройстве, в вычислительной системе, связанной с мобильным устройством через сеть, или разделена между мобильным устройством и подсоединенной к сети вычислительной системой.
В контексте данного описания, прогнозное положение может включать в себя широту, долготу и другую логическую информацию о местоположении, такую как идентификатор помещения, идентификатор магазина и идентификатор этажа в помещении. Фигура 1 иллюстрирует блок-схему множества мобильных обрабатывающих устройств 102, 104, которые используют один или несколько радиомаяков 110а - 110d или другие узлы сотовой связи 120а, 120b для вычисления положения для мобильного устройства. Мобильные обрабатывающие устройства 102, 104 наблюдают или иным образом обнаруживают один или несколько радиомаяков 110, 120 и используют сигналы от этих радиомаяков для вычисления положения. Примерные радиомаяки включают в себя сотовые башни, базовые станции, базовые приемопередающие станции, узлы базовой станции и/или любые другие сетевые элементы, поддерживающие любое количество и тип отпускного режима. Как правило, радиомаяки 110а - 110d представляют Wireless Fidelity (Wi-Fi) радиомаяки, которые имеют известные свойства распространения и сигналы, которые обеспечивают информацию, позволяющую использовать мобильные устройства для вычисления положений в областях, где другие типы сигналов могут не присутствовать, такие как внутреннее пространство зданий и тому подобные. Каждое из мобильных обрабатывающих устройств 102, 104 может хранить свойства для каждого наблюдаемого радиомаяка 110, 120. В некоторых вариантах осуществления примерные свойства включают в себя широту и долготу наблюдающего мобильного вычислительного устройства и время наблюдения. Во внутренних местоположениях, таких как объект, наблюдения могут включать в себя более детальную информацию, такую как местонахождение этажа.
Каждое мобильное вычислительное устройство может само выполнять вычисление положения или может подключиться к провайдеру 125 услуги определения местоположения с помощью сети 50. Каждое мобильное устройство может применить фильтр Калмана (или другие методы) к идентификационной метке радиомаяка (например, набора радиомаяков, наблюдаемых вычислительным устройством) для получения прогнозного положения устройства. Радиус погрешности устройства извлекается из структуры данных, изложенной выше. Радиус погрешности может быть отражен как окружность, имеющая вычисленный радиус погрешности устройства в качестве ее радиуса. В результате, если конкретный радиомаяк детектируется с заданным уровнем достоверности, прогнозное положение устройства может быть обеспечено как находящееся в пределах окружности с центром в вычисленном положении радиомаяка с вычисленным радиусом радиомаяка, как проиллюстрировано позицией 418 фигуры 4.
Провайдер 125 услуги определения местоположения, который может выполнять вычисление местоположения на основе наблюдений мобильного обрабатывающего устройства (102, 104), предыдущих съемок местоположений и других данных, которые собираются и хранятся у провайдера 125 услуги определения местоположения. В некоторых вариантах осуществления, провайдер 125 услуги определения местоположения может собирать данные из множества различных мобильных обрабатывающих устройств, а также запланированных наблюдений радиомаяков относительных известных фактических положений, называемых в данном документе наземными контрольными данными. Мобильные обрабатывающие устройства 102, 104 могут посылать свойства наблюдаемых положений и радиомаяков, наблюдаемых в различных местоположениях с помощью услуги определения местоположения через сеть 50. Провайдер 125 услуги определения местоположения может обслуживать одно или несколько вычислительных устройств, как проиллюстрировано в настоящем документе, для обеспечения услуг определения местоположения для мобильных обрабатывающих устройств через сеть 50.
Вычисленное или прогнозное положение может как включать в себя положение, так и иметь соответствующий радиус погрешности. Радиус погрешности является отражением неопределенности или погрешности, которая может присутствовать в вычислении положения. Иллюстрация радиуса погрешности, отображаемого картографическим приложением с использованием вычисленного положения, изложено на фигуре 4. В общем случае, радиус погрешности представляет область, окружающую вычисленное положение, которая указывает пользователю вычисленного положения относительную точность вычисления.
Наблюдения могут быть использованы в сочетании с услугами глобальной системы позиционирования (GPS) для определения положения. В некоторых случаях данные GPS не доступны. GPS является спутниковой навигационной системой, которая использует более двух дюжин GPS спутников, что вращаются вокруг Земли и передают радиосигналы, которые принимаются и позволяют GPS приемникам определить свое местоположение, скорость и направление. Таким образом, GPS спутники передают сигналы GPS приемникам на земле, а GPS приемники пассивно принимают эти спутниковые сигналы и обрабатывают их (но, как правило, не передают никаких сигналов о себе). Тем не менее, когда мобильное обрабатывающее устройство присутствует внутри объекта-здания, доступ к данным GPS, как правило, трудно получить. Следовательно, использование WiFi или другой информации может принести более точные данные о прогнозном местоположении.
Фигура 2 иллюстрирует развернутый перспективный вид на объект 200, имеющий множество Wi-Fi радиомаяков, расположенных внутри конструкции. Объектом 200 может быть, например, торговый центр, школа, офисное здание, аэропорт или другое здание, где доступ к данным GPS не является легко доступным. Фигура 2 иллюстрирует первый этаж 210 и второй этаж 212 объекта 200. Множество стен 220 разделяют различные комнаты 225 в пределах объекта 200. Радиомаяки 110 расположены по обоим этажам конструкции 200. Обрабатывающее устройство может использовать свойства радиомаяков в пределах объекта 200 для вычисления положения обрабатывающего устройства. Как правило, вычисленные положения выдаются приложениям, которые используют вычисленное положение для предоставления информации пользователю. Несмотря на то, что имеется целый ряд различных типов приложений определения местоположения, картографическое приложение является типичным вариантом использования вычисленного положения.
Локальное позиционирование осуществляется с использованием многих различных свойств. Некоторые используют физические свойства сигнала, в то время как другие используют время, необходимое сигналу для достижения узла назначения. Некоторые общие методы позиционирования включают в себя угол прихода, идентификатор соты, время прихода, временную разность прихода и основывающиеся на мощности методы беспроводного позиционирования. Один общий подход применяет наблюдение информации об интенсивности сигнала в конкретной области. Эта информация формирует базу данных, описывающую идентификационную метку интенсивности сигнала этой области. База данных позже используется для определения местоположения мобильного устройства посредством конкурентного алгоритма сравнения с образцом. Другой подход беспроводного позиционирования на основе мощности использует модель потерь на тракте распространения сигнала для оценки взаимосвязи между уровнем сигнала и расстоянием от передатчиков. Оцененные расстояния от трех или более передатчиков используются для определения конечного положения устройства посредством трилатерации. Любой из указанных выше способов может быть использован в соответствии с представленной технологией.
Фигура 3 является блок-схемой, иллюстрирующей способ в соответствии с представленной технологией для определения радиуса погрешности, связанного с вычисленным или прогнозным положением мобильного обрабатывающего устройства. Способ может быть выполнен полностью или частично на отдельном мобильном обрабатывающем устройстве, либо с осуществлением связи и взаимодействия с услугой 125 определения местоположения. На этапе 310 информацию съемки положений получают для одного или нескольких физических объектов. Информация съемки положений может содержать идентификационные метки радиомаяков для местоположений радиомаяков, которые обнаруживаются в объектах. Радиомаяки, обнаруженные мобильным обрабатывающим устройством 102, 104 в данный момент времени, представляют съемки положений и включают в себя идентификационную метку радиомаяка. Идентификационная метка радиомаяка может также включать в себя другие атрибуты обнаружения, такие как уровень сигнала, дата и время наблюдения и т.д. Объекты не обязательно должны быть внутренними объектами, и могут представлять собой местоположения, где присутствует множество радиомаяков. Один механизм для сбора информации о местах изложен в патентной заявке США с номером US20140057651A1.
Как правило, информация съемки положений может быть собрана путем физической съемки места с помощью мобильного обрабатывающего устройства, определения идентификационной метки радиомаяка для местоположения и создания набора наземных контрольных данных для фактических местоположений, связанных с идентификационной меткой радиомаяка для объекта. Для создания наземных контрольных данных для конкретного объекта, данные наблюдений для объекта связываются с известными положениями для наблюдаемых данных. Наблюдаемые данные могут быть связаны с помощью обследования с использованием информации известного положения (в плане известных широты, долготы и положения этажа), которая соотнесена с идентификационной меткой радиомаяка в данный момент времени. Создаются идентификационные метки известных радиомаяков в каждом из наборов положений на карте.
Наземные контрольные данные и наблюдения используются, как описано ниже, чтобы вычислить прогнозные положения для определения расстояния погрешности между прогнозным положением и известным положением для нескольких наборов данных. Корреляция между прогнозными погрешностями на различных уровнях масштабируемых географических областей используется для оценки точности радиуса погрешности в прогнозных положениях и присвоения радиуса погрешности каждой из конкретного набора масштабируемых географических областей глобальной проекционной справочной системы.
На этапе 320, для любого из наблюдаемых положений, статистика по погрешностям используется для определения радиуса погрешности, достигающего большей, чем пороговая корреляция между вычисленными или прогнозными положениями в масштабируемой географической области. Эти масштабируемые географические области, в которых статистика по погрешностям указывает, что радиус погрешности, по всей вероятности, будет иметь точность, превышающую выбранный порог корреляции, связываются с радиусом погрешности в структуре данных на этапе 330. Следует понимать, что этапы 320 и 330 могут быть выполнены на мобильном обрабатывающем устройстве или провайдером услуги определения местоположения на одном или нескольких обрабатывающих устройствах. Способ определения областей в предварительно определенной масштабируемой географической области обсуждается по отношению к фигуре 6.
После того, как структура данных создается на этапе 330, структура данных может быть сохранена на мобильном обрабатывающем устройстве 102, 104, и/или ее может поддерживать услуга 124 определения местоположения. Это позволяет каждому мобильному обрабатывающему устройству, стремящемуся определить положение и связанный с ним радиус погрешности, быстро извлечь точный радиус погрешности при обращении к структуре данных в режиме реального времени на устройстве.
В любой момент после создания структуры данных на этапе 330, на этапе 340 принимается запрос на определение местоположения. Запрос может быть получен услугой определения местоположения или мобильным обрабатывающим устройством. На этапе 345 наблюдения (идентификационные метки) положений извлекаются для местоположения устройства, отправившего запрос на этапе 340. На этапе 350 прогнозное положение вычисляется исходя из наблюдений положений, сделанных запрашивающим устройством. В соответствии с конкретным алгоритмом, используемым для вычисления по определению местоположения на этапе 350, прогнозное положение рассчитывается для запрашивающего устройства.
После того, как прогнозное положение рассчитано, на этап 360 поиском соответствующей масштабируемой географической области в структуре данных, соответствующей прогнозному местоположению, определяется радиус погрешности, связанный с масштабируемой географической областью. На этапе 370 для определенного прогнозного местоположения, радиус погрешности, связанный с местоположением, выдается на основе масштабируемой географической области.
Фигура 4 иллюстрирует блок-схему мобильного вычислительного устройства 400, которое может содержать одно из мобильных обрабатывающих устройств 102, 104 по фигуре 1 и может включать в себя элементы мобильного устройства так, как проиллюстрировано на фигуре 10, ниже. Вычислительное устройство 400 может включать в себя, например, процессор 412 и пользовательский интерфейс 418. Развернутый вид отображения пользовательского интерфейса 418 проиллюстрирован видом сверху карты 200а объекта, такого как объект 200, с указателем 415 прогнозного положения, отображаемого на карте вместе с радиусом погрешности 417, окружающим указатель 415 прогнозного положения.
Устройство 400 включает в себя память 410, которая может хранить множество наблюдений 411, 422 положения. Хотя только два наблюдения 411 и 422 положения указаны, следует понимать, что множество наблюдений положения будет присутствовать в памяти 410. Каждое наблюдение положения включает в себя идентификационные метки радиомаяков 402 и связанные с ними данные радиомаяка 404. Наблюдения положения могут быть использованы приложением 420 вычисления положения. Приложение 420 вычисления положения может быть использовано для вычисления прогнозного положения исходя из наблюдений 411, 422 положения. Приложение 420 вычисления положения может использовать структуру данных 425 радиус погрешности - масштабируемая область, чтобы присвоить радиус погрешности прогнозному положению, рассчитанному приложением вычисления положения. Приложения 430, учитывающие местоположение, используют прогнозное положение, рассчитанное приложением вычисления положения, для любой из множества различных целей. В одном варианте осуществления (проиллюстрированном на фигуре 4), приложением, учитывающим местоположение, может быть картографическое приложение и отображать прогнозное положение вместе с радиусом погрешности на пользовательском интерфейсе. Следует понимать, что многочисленные другие типы приложений используют прогнозные положения, а технология, обсуждаемая в данном документе, не ограничивается учитывающими местоположение приложениями, которые являются картографическими приложениями.
Фигура 5 иллюстрирует блок-схему функциональных компонент вычислительного устройства 500, которое в одном варианте осуществления может выполнять этапы, показанные на фигуре 3. Вычислительное устройство 500 включает в себя процессор 512 и пользовательский интерфейс 518. Устройство 500 может дополнительно включать в себя память 510, имеющую предусмотренные в ней компоненты, включая наблюдаемые положения 511 и наземные контрольные данные 522. Как было отмечено выше, наземные контрольные данные могут включать в себя, для набора положений в известном положении, заключенном в широте, долготе, и этаже, набор идентификационных меток известных радиомаяков, наблюдаемых в известном положении. Как описано ниже со ссылкой на фигуру 6, эта информация может быть использована в сочетании с наблюдениями положения для определения радиуса погрешности, который соотносится с масштабируемой географической областью. При осуществлении способа по фигуре 6, набор наблюдений 520 положений разделяется на обучающий набор данных 550 и тестовый набор данных 560. Память 510 может дополнительно включать данные 570 масштабируемой географической области, приложение 580корреляции, приложение 575 вычисления радиуса, и может опционально включать в себя приложение 576 вычисления положения и приложения 578, учитывающие местоположение. Одним примером глобальной проекционной справочной системы с использованием масштабируемой географической области является система Bing Maps Tile (http://msdn.microsoft.com/en-us/library/bb259689.aspx). Плитки, используемые здесь, могут содержать данные масштабируемой географической области. Масштабируемая географическая область проиллюстрирована и описана со ссылкой на фигуру 8А. Приложение 576 вычисления положения работает аналогично тому, как показано на фигуре 4. Приложения 578, учитывающие местоположение, могут быть аналогичны тем приложениям, что описаны выше со ссылкой на фигуру 4.
Фигура 6 иллюстрирует способ в соответствии с представленной технологией для выполнения этапа 330 по фигуре 3 определения погрешности, связанной с масштабируемыми географическими областями, которые имеют корреляцию прогнозной погрешности больше, чем заданное пороговое значение, для того чтобы создать структуру данных радиус погрешности - плитка. На этапе 610 собирают данные наблюдений для местоположения. Данные наблюдений будут набором наблюдений, из которых прогнозное положение может быть вычислено. Данные наблюдений отличаются от наземных контрольных данных для местоположения. Это позволяет коррелировать радиус погрешности с масштабируемыми географическими областями на основе прогнозных положений, а не истинных положений, так как истинное положение неизвестно на практике, когда делается запрос в реальном времени для определения положения (как на этапе 340 по фигуре 3).
На этапе 615 данные наблюдений разделяются на обучающий набор данных и тестовый набор данных. Обучающий набор данных включает в себя обучающие наблюдения положения, в то время как тестовый набор данных включает в себя тестовые наблюдения положения. В некоторых вариантах осуществления, обучающий набор данных используется для построения модели местоположения, в то время как тестовый набор данных и модель местоположения используются для создания прогнозных местоположений, которые тестируются на обучающих данных. Вычисления прогнозного местоположения могут быть получены из каждого из обучающего и тестового наборов данных, погрешность между прогнозным положением каждого набора данных и наземными контрольными данными вычисляется, и корреляция между двумя погрешностями используется для определения того, является ли это вычисление достаточно точным, чтобы полагаться на вычисление радиуса погрешности для конкретной масштабируемой географической области.
На этапе 620 модель определения местоположения положения создается с использованием обучающего набора данных. Создание модели определения местоположения является созданием конкретного вычисления, которое будет использоваться для прогнозирования положения исходя из наблюдений положения. Любой из числа различных типов вычислений положения может быть использован, подразумевая использование алгоритма сравнения с образцом, трилатерации или способа, описанного в K. Chintalapudi and V. Padmanabhan, "Indoor Localization Without the Pain," MOBICOM, Association for Computing Machinery, Inc., September 2010 (http://research.microsoft.com/pubs/135721/ez-mobicom.pdf).
На этапе 625 обучающий набор данных оценивается с использованием модели определения местоположения, выбранной на этапе 620, чтобы определить результат погрешности обучающих данных. Оценка на этапе 625 может включать в себя, для набора наблюдений в обучающем наборе данных, определение положений и погрешностей расстояния для положений относительно наземных контрольных данных. На этапе 630 и аналогично этапу 625, тестовый набор данных оценивается с использованием модели определения местоположения для возврата результатов погрешности тестовых данных.
На этапе 635 обучающие погрешности и тестовые погрешности объединяются при помощи географической области (плитки) и на объекте, и на этаже, чтобы получить статистику погрешностей с использованием интегральной функции распределения (CDF) для каждой масштабируемой географической области (т.е. из расчета на плитку) и присваивают результат погрешности каждой масштабируемой географической области на основании прогнозного положения, вычисленного для каждой из них. Масштабируемая область, к которой относится результат погрешности, является, таким образом, основанной на прогнозном положении, а не истинном положении. Фигура 9А является графиком интегральной функции распределения для масштабируемой географической области. Значение по оси Х содержит погрешность расстояния, в то время как значение по оси Y является процентной погрешностью.
Фигура 8А иллюстрирует 3 уровня масштабируемой географической области, пригодных для использования в данном документе. Масштабируемые географические области и система проекций, используемые в этом примере, являются системой Bing Maps Tile. Как проиллюстрировано на фигуре 8А, каждая масштабируемая область или плиточный слой состоит из набора плиточных файлов одинакового размера (256 на 256 пикселей). Каждая из этих плиток выравнивается по фиксированной глобальной сетке в проекции на сферическую сеть Меркатора. Каждая плитка является изображением или картой земли на заданном, фиксированном уровне масштабирования. Таким образом, каждый пиксель в каждой плитке на любом уровне масштабирования представляет собой одно фиксированное местоположение земли. Число плиток в плиточном наборе (и их сохраненный размер) зависит от размера изображаемой области, разрешения источника изображений или карты, и числа уровней масштабирования, созданных для просмотра плиточного набора. Bing Maps использует пронумерованную последовательность уровней масштабирования, как показано на иллюстрации по фигуре 8А. Наименее детальный уровень масштабирования - это уровень 1, который представляет весь земной шар с сеткой 2 на 2 плитки. Общий угол этих четырех плиток находится на 0 градусов долготы и 0 градусов широты. Каждое целочисленное увеличение уровня масштабирования удваивает количество плиток в обоих направлениях север-юг и восток-запад. Уровень масштабирования 2 охватывает весь земной шар с сеткой 4 на 4 плитки, уровень 3 с сеткой 8 на 8 и так далее. Поскольку размер плитки фиксированный, каждое увеличение в уровне масштабирования также уменьшает размер области на земле, представленной одним пикселем в плитке, с коэффициентом 2, обеспечивая увеличение визуальных деталей в плиточном наборе на более высоких уровнях масштабирования.
Присвоение тестовых погрешностей масштабируемым географическим областям может быть выполнено на этапе 640, для каждой плитки число выбранных уровней в проекционной системе (три уровня в этом примере), и на этапе 645 для набора процентилей погрешностей для каждого объекта и этажа создается график точек данных, где для каждой точки данные обучающей погрешности используются как значение X и тестовая погрешность - как значение Y на этапе 650. В одном варианте осуществления, только точки данных, большие заданного размера выборки для обоих из обучающей и тестовой погрешностей - например, 30 выборок - считаются действительными.
Этот график иллюстрирован фигурами 9А и 9В. Фигура 9А является увеличенным видом графика для плитки с 95% погрешностью. Фигура 9В иллюстрирует статистику погрешностей для уровней 18, 19 и 20 системы масштабируемых проекций, относительно объекта, для процентных погрешностей 50%, 67%, 80%, 85%, 90% и 95%. Как проиллюстрировано на фигуре 9А, данные погрешностей как значение X и тестовые погрешности как значение Y, идеальное соотношение между тестовыми погрешностями привело бы к линии точек данных, имеющей наклон, равный 1. Однако, как иллюстрируют фигуры 9А и 9В, точки данных на более низких уровнях (более низком разрешении) и при более низких процентах погрешностей будут подходить к этому распределению. В диаграммах, показанных на фигуре 9В, масштабируемые области (плитки) уровня 19 при 95% погрешности могут быть приемлемыми.
На этапе 655 масштабируемая географическая область выбирается для использования, если обучающая погрешность в тестовой погрешности находятся в пределах определенного расстояния. Например, масштабируемая географическая область является соответствующей требованиям корреляции, если обучающая погрешность и тестовая погрешность достаточно близки, например, в пределах 5 или 10 метров. Выбор происходит от самого высокого уровня разрешения (уровень 20 в примерах) до самого низкого (уровень 18 в примере).
На этапе 660 масштабируемые географические области выбираются для каждого уровня разрешения и каждого объекта, этажа и плитки, плитки, которые коррелируют, выбираются (и те, которые не пропущены), чтобы быть включенными в структуру данных радиуса погрешности. Модель погрешности для объекта состоит из пар ключ-значение <этаж-плитка, 95% погрешность> и 95% погрешностей уровня этажа. Фигура 9С представляет собой график процентной погрешности относительно расстояния погрешности, определенного для конкретной плитки. В этом примере, 95% прогнозных положений будет иметь погрешность меньшую, чем заданное расстояние радиуса.
На этапе 665 масштабируемые географические области соотносятся с расстоянием погрешности в структуре данных, как проиллюстрировано на фигуре 8В. В одном варианте осуществления, структура данных предоставляется на мобильное обрабатывающее устройство для определения радиуса погрешности локально на устройстве в сочетании с картой плиток, используемой в положении, представляющем интерес для мобильного устройства. Этап 665 эквивалентен этапу 330 на фигуре 3.
Следует признать, в приведенном выше примере, что различные параметры могут быть изменены без отхода от предлагаемой здесь технологии. Например, в то время как плитки, имеющие 95% погрешность, используются в предыдущем примере, будут использоваться и другие уровни погрешностей. Фигура 7 иллюстрирует способ для выполнения этапа 360 с фигуры 3 для поиска масштабируемой географической области, соответствующей определенному местоположению, и выдачи соответствующего расстояния погрешности. В примере, показанном на фигуре 7 и в одном варианте осуществления технологии, система позиционирования может использовать масштабируемые географические области для выдачи данных соотнесения для приложения, учитывающего местоположение. В таких случаях, плитка, соответствующая прогнозному положению, будет известна из прогнозного положения. Как проиллюстрировано на фигуре 3, на этапе 350 положение мобильного обрабатывающего устройства прогнозируется путем использования данных съемки и обнаруженных радиомаяков. Далее, на этапе 360, вычисление радиуса погрешности производится, во-первых, на этапе 710, используя прогнозное положение для определения соответствующей плитки, с уровнем разрешения от самого высокого до самого низкого. На этапе 715 первая масштабируемая область, имеющая самый высокий уровень разрешения для конкретной области, выбирается. В примере, показанном на фигуре 8А, уровень 20 - самый высокий уровень разрешения. На этапе 720 делается определение того, будет ли найденная плитка высокого уровня присутствовать в структуре данных радиуса погрешности. Если плитка имеет радиус погрешности95%, то радиус погрешности для этой плитки возвращается на этапе 735; если нет, то на этапе 725делается определение относительно того, доступен ли следующий уровень более низкого разрешения. Если да, то следующий уровень разрешения выбирается на этапе 730 и способ возвращается к этапу 720. Если дополнительные плитки не доступны, структура данных может включать в себя резервный радиус погрешности для объекта, и радиус погрешности, связанный с резервом для объекта, возвращается на 740.
Фигура 10 показывает пример блок-схемы мобильного устройства для осуществления операций по раскрытой технологии. Изображена примерная электронная схема обычного мобильного телефона. Мобильное устройство 1400 включает в себя один или несколько микропроцессоров 1412 и память 1410 (например, энергонезависимая память, такая как ROM и энергозависимую память, такую как RAM), которая хранит считываемый процессором код, который выполняется одним или несколькими процессорами управляющего процессора 1412, реализовывающим функциональные возможности, описанные в данном документе.
Мобильное устройство 1400 может включать в себя, например, процессоры 1412, память 1410, включающую приложения и энергонезависимое запоминающее устройство. Процессор 1412 может осуществлять связь, а также любое количество приложений, в том числе приложения, обсуждаемые в данном документе. Память 1410 может быть любыми типами носителя памяти запоминающих устройств, включающих энергозависимые и энергонезависимые. Операционная система устройства выполняет различные операции мобильного устройства 1400 и может содержать пользовательские интерфейсы для операций, таких как размещение и прием телефонных звонков, текстовых сообщений, проверка голосовой почты и тому подобное. Приложения 1430 могут быть любым набором программ, таких как приложение камеры для фотографий и/или видео, адресной книги, приложения календаря, медиа-плеер, интернет-браузер, игры, приложение будильника или другие приложения сторонних производителей. Энергонезависимая компонента 1440 запоминающего устройства в памяти 1410 содержит данные, такие как веб-кэш, музыка, фотографии, контактные данные, данные планирования и другие файлы.
Процессор 1412 также взаимодействует с схемой РЧ передачи/приема 1406, которая, в свою очередь соединена с антенной 1402, с инфракрасным передающим/приемником 1408, и с датчиком движения/ориентации 1414, таким как акселерометр и магнитометр 1415. Акселерометры были включены в мобильные устройства для того, чтобы такие приложения, как интеллектуальные пользовательские интерфейсы, которые позволяют давать пользователям входящие команды с помощью жестов, внутренний GPS функционал, который вычисляет движение и направление устройства после контакта разорванного с GPS спутником, и для определения ориентации устройства и автоматического переключения дисплея от портрета к пейзажу при вращении телефона. Акселерометр может быть обеспечено, например, микроэлектромеханической системой (MEMS), которая представляет собой миниатюрное механическое устройство (микронных размеров) построенное на полупроводниковом кристалле. Направление ускорения, а также ориентация, вибрация и удар могут быть восприняты. Процессор 1412 дополнительно взаимодействует с звонком/вибратором 1416, пользовательским интерфейсом клавиатуры/экраном 1418, динамиком 1420, микрофоном 1422, камерой 1424, датчиком света 1426 и датчиком температуры 1428. Магнитометры были включены в мобильные устройства для того, чтобы такие приложения, как цифровой компас, который измеряет направление и величину магнитного поля в непосредственной близости от мобильного устройства, отслеживали изменения в магнитном поле и показывали направление магнитного поля для пользователей.
Процессор 1412 управляет передачей и приемом сигналов беспроводной связи. Во время режима передачи, процессор 1412 обеспечивает голосовой сигнал от микрофона 1422, или другой сигнал данных, для схемы передачи/приема 1406. Схема передачи/приема 1406 передает сигнал на удаленную станцию (например, стационарную станцию, оператора, другие сотовые телефоны и т.д.) для связи через антенну 1402. Звонок/вибратор 1416 используется для сигнализации о входящем вызове, текстовом сообщении, напоминании календаря, напоминании будильника, или другом уведомлении пользователю. Во время режима приема, схема передачи/приема 1406 принимает голос или любой другой сигнал данных от удаленной станции через антенну 1402. Принятый голосовой сигнал поступает на динамик 1420, в то время как другие принимаемые сигналы данных также обрабатываются соответствующим образом.
Кроме того, физический соединитель 1488 может быть использован для подключения мобильного устройства 100 к внешнему источнику питания, такому как адаптер переменного тока или базовая станция питания. Физический соединитель 1488 может также быть использован как информационное соединение с вычислительным устройством. Информационное соединение подходит для операций, таких как синхронизация данных мобильных устройств с данными вычисления на другом устройстве. Приемник услуги глобального определения местоположения (GPS) 1465 с использованием спутниковой радионавигации для ретрансляции положения приложений пользователя включен для такой службы.
Фигура 10 показывает пример блок-схемы мобильного устройства для осуществления операций по раскрытой технологии. Устройство по фигуре 10 является более детальной иллюстрацией, например, устройства 102, 104 по фигуре 1. Изображена примерная электронная схема обычного мобильного телефона. Мобильное устройство 1000 включает в себя один или несколько микропроцессоров 1012 и память 1010 (например, энергонезависимая память, такая как ROM и энергозависимую память, такую как RAM), которая хранит считываемый процессором код, который выполняется одним или несколькими процессорами управляющего процессора 1012, реализовывающим функциональные возможности, описанные в данном документе.
Мобильное устройство 1000 может включать в себя, например, процессоры 1012, память 1010, включающую приложения и энергонезависимое запоминающее устройство. Процессор 1012 может осуществлять связь, а также любое количество приложений, в том числе приложения, обсуждаемые в данном документе. Память 1010 может быть любыми типами носителя памяти запоминающих устройств, включающих энергозависимые и энергонезависимые. Операционная система устройства выполняет различные операции мобильного устройства 1000 и может содержать пользовательские интерфейсы для операций, таких как размещение и прием телефонных звонков, текстовых сообщений, проверка голосовой почты и тому подобное. Приложения 1030 могут быть любым набором программ, таких как приложение камеры для фотографий и/или видео, адресной книги, приложения календаря, медиа-плеер, интернет-браузер, игры, приложение будильника или другие приложения сторонних производителей. Энергонезависимая компонента 1440 запоминающего устройства в памяти 1010 содержит данные, такие как веб-кэш, музыка, фотографии, контактные данные, данные планирования и другие файлы.
Процессор 1012 также взаимодействует с схемой РЧ передачи/приема 1006, которая, в свою очередь соединена с антенной 1002, с инфракрасным передающим/приемником 1008, и с датчиком движения/ориентации 1014, таким как акселерометр и магнитометр 1015. Акселерометры были включены в мобильные устройства для того, чтобы такие приложения, как интеллектуальные пользовательские интерфейсы, которые позволяют давать пользователям входящие команды с помощью жестов, внутренний GPS функционал, который вычисляет движение и направление устройства после контакта разорванного с GPS спутником, и для определения ориентации устройства и автоматического переключения дисплея от портрета к пейзажу при вращении телефона. Акселерометр может быть обеспечено, например, микроэлектромеханической системой (MEMS), которая представляет собой миниатюрное механическое устройство (микронных размеров) построенное на полупроводниковом кристалле. Направление ускорения, а также ориентация, вибрация и удар могут быть восприняты. Процессор 1012 дополнительно взаимодействует с звонком/вибратором 1016, пользовательским интерфейсом клавиатуры/экраном 1018, динамиком 1020, микрофоном 1022, камерой 1024, датчиком света 1026 и датчиком температуры 1028. Магнитометры были включены в мобильные устройства для того, чтобы такие приложения, как цифровой компас, который измеряет направление и величину магнитного поля в непосредственной близости от мобильного устройства, отслеживали изменения в магнитном поле и показывали направление магнитного поля для пользователей.
Процессор 1012 управляет передачей и приемом сигналов беспроводной связи. Во время режима передачи, процессор 1012 обеспечивает голосовой сигнал от микрофона 1022, или другой сигнал данных, для схемы передачи/приема 1006. Схема передачи/приема 1006 передает сигнал на удаленную станцию (например, стационарную станцию, оператора, другие сотовые телефоны и т.д.) для связи через антенну 1002. Звонок/вибратор 1016 используется для сигнализации о входящем вызове, текстовом сообщении, напоминании календаря, напоминании будильника, или другом уведомлении пользователю. Во время режима приема, схема передачи/приема 1006 принимает голос или любой другой сигнал данных от удаленной станции через антенну 1002. Принятый голосовой сигнал поступает на динамик 1020, в то время как другие принимаемые сигналы данных также обрабатываются соответствующим образом.
Кроме того, физический соединитель 1088 может быть использован для подключения мобильного устройства 100 к внешнему источнику питания, такому как адаптер переменного тока или базовая станция питания. Физический соединитель 1088 может также быть использован как информационное соединение с вычислительным устройством. Информационное соединение подходит для операций, таких как синхронизация данных мобильных устройств с данными вычисления на другом устройстве. Приемник услуги глобального определения местоположения (GPS) 1065 с использованием спутниковой радионавигации для ретрансляции положения приложений пользователя включен для такой службы.
Фигура 11 иллюстрирует подходящую среду вычислительной системы 900, такую как персональный компьютер, на котором технология может быть реализована. Среда вычислительной системы 900 является только одним примером подходящей вычислительной среды и не предназначена для наложения какого-либо ограничения относительно объема использования или функциональных возможностей технологии. Не следует вычислительной среде 900 интерпретироваться как имеющей какую-либо зависимость или требование, относящееся к любому одному или комбинации компонентов, проиллюстрированных в примерной вычислительной среде 900.
В одном варианте осуществления, система по фигуре 9 или множество их могут быть использованы для обеспечения сервиса определения местоположения 150.
Компоненты компьютера 910 могут включать в себя, но не ограничиваются ими, вычислительный блок 920, системную память 930 и системную шину 921, которая соединяет различные системные компоненты, включая системную память с вычислительным блоком 920. Системная шина 921 может быть любой из нескольких типов структур шин, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, использующую любую из множества архитектур шин. В качестве примера, а не ограничения, такие архитектуры включают в себя шину архитектуры промышленного стандарта (ISA), шину микроканальной архитектуры (MCA), шину расширенной ISA (EISA), шину ассоциации по стандартам видеоэлектроники (VESA) и шину соединения периферийных компонентов (PCI) также известную как шина расширения.
Компьютер 910 обычно включает в себя множество машиночитаемых носителей. Машиночитаемые носители могут быть любыми доступными носителями, к которым может обращаться компьютер 910, и включают в себя как энергозависимые, так и энергонезависимые носители, съемные и несъемные носители. В качестве примера, а не ограничения, машиночитаемые носители могут включать компьютерный носитель данных. Компьютерный носитель данных включает в себя энергозависимые и энергонезависимые, съемные и несъемные носители для хранения данных, такой как машиночитаемые инструкции, структуры данных, программные модули или другие данные. Компьютерный носитель данных включает в себя, но не ограничивается ими, RAM, ROM, EEPROM, флэш-память или другую технологию памяти, CD-ROM, цифровые универсальные диски (DVD) или другой накопитель на оптических дисках, магнитные кассеты, магнитную ленту, накопитель на магнитных дисках или другие магнитные запоминающие устройства, или любой другой носитель, который можно использовать для хранения требуемой информации и к которому может обращаться компьютер 910.
Системная память 930 включает в себя компьютерный носитель данных в виде энергозависимой и/или энергонезависимой памяти, такой как постоянное запоминающее устройство (ROM) 931 и оперативное запоминающее устройство (RAM) 932. Базовая система ввода/вывода 933 (BIOS), содержащая основные процедуры, которые помогают передавать информацию между элементами внутри компьютера 910, такие как во время запуска, обычно хранящаяся в ROM 931. RAM 932 обычно содержит данные и/или программные модули, которые непосредственно доступны и/или в данный момент обрабатываются вычислительным блоком 920. В качестве примера, но не ограничения, фигура 9 иллюстрирует операционную систему 934, программы приложений 935, другие программные модули 936 и программные данные 939.
Компьютер 910 может также включать в себя другие материальные съемные/несъемные, энергозависимые/энергонезависимые компьютерные носители данных. В качестве только примера, фигура 9 иллюстрирует жесткий диск 940, который считывает или записывает на несъемный энергонезависимый магнитный носитель, магнитный диск 951, который считывает или записывает на съемный энергонезависимый магнитный диск 952, и оптический диск 955, который считывает или записывает на съемный, энергонезависимый оптический диск 956, такой как CD-ROM или другие оптические носители. Другие съемные/несъемные, энергозависимые/энергонезависимые компьютерные носители данных, которые могут быть использованы в примерной вычислительной среде включают, но не ограничиваются ими, кассеты с магнитной лентой, карты флэш-памяти, цифровые универсальные диски, цифровые видеоленты, твердотельное RAM, твердотельное ROM и тому подобные. Жесткий диск 941 обычно подсоединен к системной шине 921 через интерфейс несъемной памяти, такой как интерфейс 940, а магнитный диск 951 и оптический диск 955 обычно подсоединены к системной шине 921 интерфейсом съемной памяти, таким как интерфейс 950.
Накопители и их соединения с компьютерным носителем данных, обсужденные выше и проиллюстрированные на фигуре 9, обеспечивают хранение машиночитаемых инструкций, структур данных, программных модулей и других данных для компьютера 910. На фигуре 9, например, жесткий диск 941 проиллюстрирован как хранящий операционную систему 944, программы приложений 945, другие программные модули 946 и программные данные 949. Заметим, что эти компоненты могут быть либо такими же, либо отличаться от операционной системы 934, программ приложений 935, других программных модулей 936 и программных данных 939. Операционная система 944, программы приложений 945, другие программные модули 946 и программные данные 949 обозначены отличающимися ссылочными позициями для иллюстрации того, что, как минимум, они представляют собой разные копии. Пользователь может вводить команды и информацию в компьютер 20 через устройства ввода, такие как клавиатура 962 и координатный манипулятор 961, обычно упоминается как мышь, шаровой манипулятор или сенсорная панель. Другие устройства ввода (не показаны) могут включать в себя микрофон, джойстик, игровую панель, спутниковую антенну, сканер или тому подобное. Эти и другие устройства ввода часто соединяются с блоком 920 обработки через пользовательский входной интерфейс 960, который соединен с системной шиной, но могут быть подсоединены другим интерфейсом и шинной структурой, такими как параллельный порт, игровой порт или универсальная последовательная шина (USB). Монитор 991 или другой тип отображающего устройства также подсоединен к системной шине 921 через интерфейс, такой как видеоинтерфейс 990. В дополнение к монитору компьютеры могут также включать в себя другие периферийные устройства вывода, такие как колонки 999 и принтер 996, которые могут быть соединены через выходной периферийный интерфейс 990.
Компьютер 910 может работать в сетевой среде с использованием логических соединений с одним или более удаленными компьютерами, такими как удаленный компьютер 980. Удаленный компьютер 980 может быть персональным компьютером, сервером, маршрутизатором, сетевым персональным компьютером, одноранговым устройством или другим общим сетевым узлом, и обычно включает в себя многие или все элементы, описанные выше применительно к компьютеру 910, хотя только запоминающее устройство 981 проиллюстрировано на фигуре 9. Логические соединения, изображенные на фигуре 9, включают в себя локальную сеть (LAN) 991 и глобальную сеть (WAN) 993, но могут также включать в себя другие сети. Такие сетевые среды являются обычным явлением в офисах, компьютерных сетях в масштабе предприятий, интранетах и Интернет.
При использовании в сетевой среде LAN, компьютер 910 подсоединен к LAN 991 через сетевой интерфейс или адаптер 990. При использовании в сетевой среде WAN, компьютер 910 обычно включает в себя модем 992 или другие средства для установления связи через WAN 993, такие как Интернет. Модем 992, который может быть внутренним или внешним, может быть подсоединен к системной шине 921, через пользовательский входной интерфейс 960 или другой соответствующий механизм. В сетевой среде программные модули, изображенные относительно компьютера 910, или их части, могут храниться в удаленном устройстве хранения данных. В качестве примера, но не ограничения, фигура 9 иллюстрирует удаленные прикладные программы 985, находящиеся на запоминающем устройстве 981. Следует понимать, что показанные сетевые соединения являются примерными и другие средства установления линии связи между компьютерами могут быть использованы.
Технология работает с многочисленными другими универсальными или специальными средами вычислительных систем или конфигурациями. Примеры хорошо известных вычислительных систем, сред и/или конфигураций, которые могут быть пригодны для использования с технологией, включают, но не ограничены этим, персональные компьютеры, серверные компьютеры, ручные или портативные устройства, многопроцессорные системы, основанные на микропроцессорах системы, телевизионные приставки, программируемую бытовую электронику, сетевые персональные компьютеры, миникомпьютеры, обычные компьютеры, распределенные вычислительные среды, которые включают в себя любые из вышеперечисленных систем или устройств, и т.п.
Технология может быть описано в общем контексте машиновыполняемых команд, таких как программные модули, исполняемые компьютером. Как правило, программные модули включают в себя подпрограммы, программы, объекты, компоненты, структуры данных и т.д., которые выполняют конкретные задачи или реализуют определенные абстрактные типы данных. Технология может также быть реализована в распределенных вычислительных средах, где задачи выполняются удаленными вычислительными устройствами, которые связаны через коммуникационную сеть. В распределенной вычислительной среде программные модули могут быть расположены как на локальных, так и на удаленных компьютерных носителях данных, включая запоминающие устройства.
Хотя изобретение было описано на языке, характерном для структурных признаков и/или методологических действий, следует понимать, что объем изобретения, определяемой прилагаемой формулой изобретения, не обязательно ограничен конкретными признаками или действиями, описанными выше. Напротив, конкретные признаки и действия, описанные выше, раскрыты как примеры форм осуществления формулы изобретения.
Реферат
Изобретение относится к оценке местоположения. Техническим результатом является определение радиуса погрешности, отражающего обеспечиваемую точность прогнозного (или вычисленного) положения обрабатывающего устройства. Обеспечивается структура данных, включающая в себя радиус погрешности, соотнесенный с масштабируемой географической областью или "плиткой", включающей область, в которой вычисленное положение может быть определено. Структура данных может включать в себя множество первых полей, идентифицирующих масштабируемую географическую область, на основе глобальной проекционной справочной системы, и множество вторых полей, идентифицирующих для каждого из первых полей радиус погрешности положения, связанный с масштабируемой географической областью и уровнем. Для любого вычисления прогнозного положения на основе наблюдений радиомаяка, быстрым поиском соответствующей масштабируемой области, включающей в себя новое прогнозное положение, в структуре данных выдается радиус погрешности для нового прогнозного положения. 2 н. и 7 з.п. ф-лы, 14 ил.
