Способ определения местоположения из кодированных данных, представляющих его

Способ определения местоположения из кодированных данных, представляющих его

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Настоящее изобретение относится к способу определения местоположения, представленного посредством данных, кодированных согласно одному или более заранее определенных форматов, а более конкретно, относится к способу для точного определения местоположения в рамках цифровой карты, к примеру, создаваемой и продаваемой компаниями Tele Atlas B.V и Navteq Inc., таким способом, который не зависит от конкретной цифровой карты, используемой во время процесса декодирования, и при этом является идентичным первоначально кодированному местоположению. В этом отношении, способ может считаться независимым от карты, но способ, которым осуществляется декодирование, в отличие от определения декодированных данных в местоположение, неизбежно зависит от заранее определенного выбранного формата.

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

Уровень техники

В дополнительной поданной в один день с данной заявке заявителя, озаглавленной "Efficient Location Referencing Method", описывается технология для формирования машиночитаемого представления местоположения таким способом, который не только считается оптимизированным относительно полной длины в байтах, но и который также считается независимым от карты.

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

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

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

Одним конкретным атрибутом, зачастую предоставленным в цифровых картах, является таблица привязок местоположений канала сообщений о дорожном движении (TMC). TMC - это технология для доставки информации о дорожном движении и поездке пользователям транспортных средств, а более конкретно, в навигационные системы (портативные или интегрированные), присутствующие в этих транспортных средствах и которые включают в себя некоторую форму цифровой карты. TMC-сообщение состоит из кода события (который не обязательно должен быть конкретным для дорожного движения, хотя они наиболее распространены) и кода местоположения, зачастую состоящего из упорядоченного списка привязок местоположений, посредством которых местоположение события дорожного движения может быть определено в цифровой карте и тем самым представлено графически на экране навигационной системы. Определенному числу заранее заданных узлов в большинстве предлагаемых на рынке цифровых карт назначается точка привязки TMC-местоположения, которая определяется с привязкой на ограниченную таблицу местоположений. Таблица местоположений состоит из 2¹⁶ (65536) привязок местоположений, соответствующих аналогичному числу физических или реальных местоположений, обычно пересечений дорог, также идентифицируемых на цифровой карте.

Хотя TMC-сообщения являются очень эффективными в том, что они могут иметь небольшую длину в 37 битов, и, следовательно, не потреблять значительную часть доступной полосы пропускания для широковещательных данных, только фиксированное число привязок местоположений доступно, и, следовательно, типично только автомагистрали и главные шоссе (или их пересечения) в каждой стране, предлагающей TMC, могут быть указаны в привязках. Имеются различные другие недостатки TMC-привязок местоположений. Например, TMC-таблицы местоположений:

- зачастую поддерживаются через орган государственной власти или национальное правительство,

- часто меняются между циклами обновления, которые являются традиционно весьма длинными,

- не существуют или доступны только коммерчески на некоторых рынках.

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

Одной попыткой преодолевать некоторые из ограничений TMC-привязок местоположений или конкретных для карты привязок является проект динамической привязки местоположения, также известный как AGORA-C (в процессе стандартизации согласно ISO 17572-1, 2 и 3). Хотя полное описание подхода к привязке местоположения AGORA-C выходит за рамки данной заявки, фундаментальные основы подхода заключаются в том, что привязка местоположения может полностью указываться посредством набора точек местоположения, указываемых посредством пар координат широты и долготы и упорядоченных в списке, причем каждая точка удовлетворяет различным правилам, но, наиболее важно, является последовательной с точки зрения привязываемого местоположения и предыдущей точки в списке, т.е. последовательные точки формируют взаимосвязь "следующая точка". Как и в других системах привязки местоположения, каждая точка содержит определенное число атрибутов, которые помогают в лучшем задании этой точки, но конкретным для AGORA-C способом является идентификация каждой точки как одной из точки местоположения, точки пересечения, точки маршрутизации или некоторой комбинации вышеозначенных трех точек. Каждая точка вдоль местоположения, в котором изменяется характерный признак участка дороги, представляется посредством точки пересечения, тем самым местоположения, которые являются путями по дорожной сети и которые проходят через пересечения без изменений характерного признака участка дороги, не должны привязываться посредством точки пересечения. Например, если местоположение включает в себя часть автомагистрали, которая включает в себя перекрестки, которые не являются релевантными относительно местоположения, то нет необходимости включать точки пересечения для таких перекрестков. Одним из предшествующих этапов способа кодирования AGORA-C является определение всех прошедших точек пересечения между первой и последней точкой пересечения вдоль местоположения, в котором происходит изменение характерного признака участка дороги.

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

Хотя этот подход к привязке является всеобъемлющий в том, что можно точно и повторяемо кодировать и декодировать любое местоположение, существующее в рамках системы географической информации, считается, что система является чрезмерной и, возможно, избыточной в определенных аспектах, и возможна более эффективная система кодирования и декодирования. Например, хотя способ привязки является независимым от задач предварительной компиляции и является независимым от карты, средний размер сообщения AGORA-C намного превышает 30 байтов в расчете на привязку местоположения. С точки зрения устройств, которые могут в большинстве случаев декодировать привязки местоположения, таких как персональные навигационные устройства, PDA, мобильные устройства или встроенные в автомобиль интегрированные навигационные системы, требуется, чтобы принимаемое сообщение являлось максимально коротким, чтобы иметь возможность предоставлять быстрое декодирование и окончательное определение местоположения, представленное посредством этого.

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

Сущность изобретения

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

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

(ii) выполнения поиска маршрута в рамках упомянутой второй цифровой карты между:

- по меньшей мере, одним из упомянутого, по меньшей мере, одного узла-кандидата и соответствующей(им) линией-кандидатом или сегментом-кандидатом, исходящей(им) из него или инцидентной(ым) ему, и

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

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

(iii) повторения этапа (ii) для каждой последовательной пары точек привязки местоположения вплоть до и включая конечную точку привязки местоположения, обнаруживаемую в списке.

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

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

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

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

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

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

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

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

Дополнительно предпочтительно, способ включает в себя дополнительные этапы:

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

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

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

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

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

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

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

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

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

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

Краткое описание чертежей

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

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

Фиг. 6-11 предоставляют схематические представления второй цифровой карты, включающей в себя узлы и сегменты, и, в частности, фиг. 6 иллюстрирует сеть по фиг. 2, но представленную посредством узлов и сегментов, обнаруживаемых во второй цифровой карте, фиг. 7 иллюстрирует узлы-кандидаты, идентифицированные в рамках второй цифровой карты, фиг. 8 иллюстрирует линии-кандидаты, идентифицированные в рамках второй цифровой карты, и фиг. 9 иллюстрирует наиболее вероятные линии-кандидаты, посредством которых местоположение полностью привязывается. Фиг. 10 показывает кратчайший путь, алгоритмически определенный между наиболее вероятными линиями, и фиг. 11 показывает местоположение как определенное,

Фиг. 12-20 предоставляют различные схематические иллюстрации, применимые в контексте логических и физических форматов данных, описанных ниже, и в частности, фиг. 12 показывает требуемое последовательное соединение точек привязки местоположения (LRP), фиг. 13 иллюстрирует, как азимут вычисляется для одной LRP относительно следующей LRP, фиг. 14 показывает, как азимуты могут варьироваться, фиг. 15 демонстрирует, как атрибут "расстояние до следующей точки" определяется для LRP, фиг. 16 иллюстрирует использование смещений, фиг. 17 показывает способ, которым для LRP предоставляются атрибуты, фиг. 18/19 иллюстрируют узлы, которые должны исключаться в ходе кодирования привязки местоположения, и фиг. 20 иллюстрирует, как значения азимута для LRP попадают в 1 из 32 дискретных секторов круга.

Подробное описание изобретения

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

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

Ссылаясь сначала на фиг. 2-5, первая цифровая карта (кодера) показана на фиг. 2 и состоит из 15 узлов и 23 линий (двухсторонние линии подсчитываются два раза). Узлы пронумерованы от (1) до (15). Необходимые атрибуты линий показаны около каждой линии с использованием формата: <FRC>,<FOW>,<длина в метрах>. FRC - это сокращение для "функционального класса дороги", и FOW - это сокращение для "формы пути", оба из которых описываются более подробно в нижеприведенном приложении. Острия стрелок указывают возможное направление движения для каждой линии.

Местоположение, которое должно быть кодировано, показано на фиг. 3 с помощью полужирных линий. Местоположение начинается в узле (3) и проходит по узлам (5), (7), (10), (11), (13), (14) и завершается в узле (15). Его общая длина на карте кодера составляет 685 метров. Упорядоченный список линий и карта, которая должна использоваться в ходе кодирования, выступают в качестве входных данных для кодера.

Кодирование

На первом этапе процесса кодирования местоположение сначала проверяется на предмет достоверности. Поскольку местоположение является соединенным и по нему может двигаться автомобиль, и все функциональные классы дорог вдоль местоположения находятся между 0 и 7, это местоположение считается достоверным. Хотя в процесс кодирования можно включать проверку относительно того, активированы или нет ограничения на поворотах в рамках картографических данных, этот этап для краткости здесь опускается.

Второй этап кодера заключается в том, чтобы проверять начальный и конечный узел местоположения как являющиеся реальными узлами согласно конкретным заранее определенным правилам для форматов данных. Конечный узел (15) имеет только одну входящую линию, и, следовательно, является достоверным. Начальный узел (3) также имеет две инцидентных линии, но здесь это одна исходящая и одна входящая линия. Следовательно, данный узел не является достоверным, и кодер выполняет поиск реального узла вне местоположения. Кодер должен обнаруживать, что узел (1) является реальным узлом, и он также уникально продляет местоположение. Узел (1) выбирается как новый начальный узел для привязки местоположения, и будет положительное смещение в 150 метров. Общая длина пути привязки местоположения приводит к 835 метрам.

Третий этап кодера заключается в том, чтобы переходить к тому, чтобы вычислять кратчайший путь между начальной линией (линией между узлами (1) и (3)) и конечной линией (линией между узлами (14) и (15)) местоположения. Результирующий кратчайший путь выделяется на фиг. 4 с помощью полужирных линий. Кратчайший путь имеет длину в 725 метров.

Следующий (4-й) этап процесса кодирования теперь состоит в том, чтобы проверять то, покрывается или нет местоположение посредством вычисленного кратчайшего пути. Он определяет то, что это не так, и имеется отклонение после узла (10).

Согласно принципам, указанным в находящейся одновременно на рассмотрении и поданной в один день с данной заявке заявителя, кодер должен определять линию от узла (10) к (11) как новую промежуточную точку привязки местоположения. Узел (10) является реальным узлом, поскольку он не может быть пропущен во время поиска маршрута, и кратчайший путь к этой линии полностью покрывает соответствующую часть местоположения. Длина местоположения, покрываемого после этого первого вычисления кратчайшего пути, составляет 561 метр.

Следующий этап кодирования подготавливает вычисление маршрута, чтобы определять кратчайший путь для оставшейся части местоположения (от узла (10) через (11), (13) и (14) к (15)). Вычисление кратчайшего пути, следовательно, начинается в линии от (10) к (11) и завершается в линии от (14) к (15).

Кодер возвращается к вышеприведенному этапу 3 и определяет кратчайший путь (длина: 274 метра) между (10) и (15), и вышеприведенный этап 4 возвращает то, что местоположение теперь полностью покрывается посредством вычисленных кратчайших путей.

В качестве следующего этапа, путь привязки местоположения будет состоять из двух кратчайших путей, и далее формируется упорядоченный список точек привязки местоположения. Фиг. 5 показывает полужирным линии, которые выбираются для точек привязки местоположения. Первая точка привязки местоположения указывает на линию от узла (1) к (3) и указывает начало пути привязки местоположения, вторая точка привязки местоположения указывает на линию от узла (10) к (11), и эта линия требуется для того, чтобы не допускать отклонения от местоположения. Последняя точка привязки местоположения указывает на линию от узла (14) к (15) и указывает конец базового опорного пути.

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

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

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

Ссылаясь также на фиг. 1, на которой показана краткая блок-схема 100 последовательности операций способа для процесса согласно одному варианту осуществления изобретения, первый этап 102 в процессе заключается в том, чтобы декодировать входящие или передаваемые в беспроводном режиме (обычно в случае мобильного устройства) двоичные данные (или XML либо другое машиночитаемое представление), являющиеся результатом предшествующего процесса кодирования и структурированные согласно физическому формату данных. Декодирование этих двоичных данных не является существенным элементом изобретения, которое применяется к определению местоположения из списка точек привязки местоположения - декодирование двоичных данных является просто средством идентификации требуемых точек привязки местоположения.

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

Информация, извлеченная из примера двоичных данных, показана в таблицах 1, 2 и 3 (и дополнительно содержится на фиг. 1 на этапах 106, 108 и 110, соответственно).

Таблица 1Декодированные координаты
Индекс LRP	Долгота	Широта
1	6,12682°	49,60850°
2	6,12838°	49,60397°
3	6,12817°	49,60304°

Таблица 2Декодированная информация LRP
Индекс LRP	FRC	FOW	Азимут	LFRCNP	DNP
1	FRC3	MULTIPLE_CARRIAGEWAY	135,00°-146,25°	FRC3	527,4-586,0 м
2	FRC3	SINGLE_CARRIAGEWAY	225,00°-236,25°	FRC5	234,4-293,0 м
3	FRC5	SINGLE_CARRIAGEWAY	281,25°-292,50°	-	0 м

Таблица 3Декодированная информация смещения
Смещение	Значение
Положительное смещение	117,2-175,8 м
Отрицательное смещение	Нет доступного смещения

Этой информации достаточно для того, чтобы определить местоположение на карте декодера, показанной на фиг. 6. Эта карта состоит из 17 узлов и 26 линий (двухсторонние линии подсчитываются два раза). Чтобы не допускать путаницы, все узлы, указываемые на карте декодера, предваряются "X".

Эта карта отличается от карты кодера (см. фиг. 2) несколькими аспектами. Некоторые значения длины являются различными (например, линия от узла X(3) к X(5)), некоторые значения функционального класса дороги изменены (например, линия от узла X(3) к X(5)), и имеется еще два узла X(16) и X(17), а также дополнительные линии, соединяющие эти новые узлы. Задача декодера заключается в том, чтобы определить местоположение в этой другой карте.

После проверки достоверности данных и предоставления списка декодированных точек привязки местоположения (LRP) и их атрибутов, как указано на этапе 112 на фиг. 1, декодер затем начинает обрабатывать каждую LRP в списке на этапе 114, чтобы сначала определять узлы-кандидаты для каждой LRP. Результат этой обработки, которую достаточно просто осуществлять посредством использования LRP-координат и идентификации ближайшего узла(лов), обнаруживаемых на цифровой карте декодера 118 (как указано, в общем, на 116), состоит в том, чтобы предоставлять список узлов-кандидатов для каждой LRP. Узлы карты, удаленные от LRP более чем на заранее определенное пороговое значение, могут исключаться, как показано на 120. Фиг. 7 показывает узлы-кандидаты (полужирный круг), которые размещаются рядом, посредством координат точек привязки местоположения. Для точки 1 и 2 привязки местоположения (в вышеприведенных таблицах 1 и 2), в этом примере, существует только один узел-кандидат, но для последней точки привязки местоположения возможны два узла-кандидата X(16) и X(17).

Так же, в качестве части обработки LRP и их атрибутов, линии-кандидаты для каждой точки привязки местоположения также идентифицируются. Полужирные линии