Эффективный способ привязки местоположения

Эффективный способ привязки местоположения

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- является более эффективным, чем AGORA-C, без существенного негативного влияния на точность,

- не мешает доступным полосам пропускания для широковещательных данных,

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

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

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

- не требует периодического обслуживания.

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

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

(i) сохранения начального положения в списке для поиска маршрута, причем упомянутая начальное положение является одним из:

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

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

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

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

(iv) сохранения последней линии или сегмента в списке путей в упомянутом списке для поиска маршрута, если еще не сохранены.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 4 подробнее показывает блок-схему последовательности операций функции поиска маршрута по кратчайшему пути.

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

Фиг. 6, 7 и 8 графически иллюстрируют различные возможности, возникающие при проверке того, что местоположение корректно покрывается посредством процедуры, проиллюстрированной на фиг. 5.

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

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

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

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

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

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

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

Что касается фиг. 2, дополнительно описывается процесс проверки достоверности "Check_Location", проиллюстрированный в 14 на фиг. 1. Все местоположения, которые не сохраняются в базе данных ранее кодированных местоположений, должны проверяться на предмет достоверности перед дальнейшей обработкой. В качестве первого этапа, на этапе 30 выполняется проверка возможности соединения. Проверка возможности соединения обеспечивает то, что входящее местоположение не разделяется на два или более различных отрезков, которые не соединены. Каждый соединенный участок должен быть обработан отдельно и представляет одно местоположение, которое должно быть кодировано независимо. Эта проверка происходит, если местоположение состоит только из одного соединенного участка.

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

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

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

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

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

Что касается фиг. 3, предоставляется описание этапа 16 Create_LocationReference (Создание привязки местоположения) на фиг. 1. После обработки достоверности, описанной выше, предоставляется достоверная последовательность сегментов, и она должна быть преобразована в привязку местоположения как дерево объектов, заданных в логическом формате данных, как описано ниже.

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

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

Поиск маршрута вычисляет кратчайший путь между начальным сегментом и конечным сегментом. Это вычисление выполняется итеративно, и после инициализации на этапе 50 основной цикл, включающий себя этапы 52, 54, 56, 58, должен вычислять кратчайший путь. Путь по кратчайшему маршруту должен проверяться в каждой итерации на этапе 56 (описано подробнее в дальнейшем со ссылкой на фиг. 5), чтобы устанавливать то, является или нет местоположение по-прежнему частью вычисленного дерева кратчайшего пути. Если местоположение более не покрывается посредством дерева кратчайшего пути, то вычисление маршрута прекращается и возвращает частичный маршрут (часть местоположения, которая покрывается к текущему моменту) на этапе 60, и сегмент, который должен использоваться в качестве промежуточной точки привязки местоположения, чтобы делать поиск маршрута уникальным и допускающим продолжение впоследствии. Этот промежуточный сегмент идентифицируется на этапе 44 на фиг. 3 и возвращается в алгоритм поиска маршрута как новый начальный сегмент, с которого должны осуществляться один или более дополнительных поисков маршрутов.

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

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

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

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

- если промежуточный сегмент идентифицируется.

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

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

Имеются различные специальные возможности для корректной идентификации и привязки промежуточного сегмента в зависимости от характера отклонения, которое возникает при вычислении кратчайшего пути, и они все описываются со ссылкой на фиг. 5, 6, 7 и 8.

Чтобы проверять совпадение кратчайшего пути, определенного к текущему