СПОСОБ ОБРАБОТКИ ДАННЫХ ПОЗИЦИОНИРОВАНИЯ Российский патент 2013 года по МПК G01C21/32 

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

Изобретение относится к способу обработки данных позиционирования и, в частности, к обработке данных позиционирования для генерирования данных карты, скомпонованных, чтобы быть использованными в навигационных устройствах и, в частности, но не главным образом, в Портативном Навигационном Устройстве (PND). Изобретение также обеспечивает связанное устройство для обеспечения способа.

Предшествующий уровень техники

Данные карты для электронных навигационных устройств, таких как персональные навигационные устройства, основанные на GPS, подобные GO™ от компании TomTom International BV, поступают от специальных поставщиков карт, таких как Tele Atlas NV. Такие устройства также называются Портативными Навигационными Устройствами (устройствами PND). Эти данные карт специально составлены для использования в алгоритмах прокладки маршрута, обычно использующих данные местоположения от системы GPS. Например, дороги могут быть описаны как линии - то есть векторы (например, начальная точка, конечная точка, направление для дороги, причем полная дорога составляется из многих сотен таких сегментов, каждый из которых единственным образом определяется параметрами направления начальной точки/конечной точки). Также карта является набором таких векторов дороги, данных, ассоциированных с каждым вектором (ограничение скорости; направление путешествия и т.д.) плюс точек интереса (точки POI), плюс названия дорог, плюс другие географические признаки, такие как границы парков, речные границы и т.д., все из которых определяются в терминах векторов. Все признаки карты (например, векторы дороги, точки POI и т.д.) обычно определяются в системе координат, которая соответствует или относится к системе координат GPS, позволяя определить позицию устройства, местоположение которой определено с помощью системы GPS, на соответствующей дороге, показанной на карте, и планировать оптимальный маршрут до места назначения.

Чтобы создать эту базу данных карты, Tele Atlas начинает с основной информации дороги из различных источников, таких как Ordnance Survey для дорог в Англии. Она также имеет большую, специализированную группу транспортных средств, которые ездят по дорогам, плюс персонал, проверяющий другие карты и фотографии с воздуха, чтобы обновлять и проверять свои данные. Эти данные составляют ядро базы данных карты Tele Atlas. Эта база данных карты непрерывно увеличивается посредством гео-ссылочных данных. Затем она проверяется, и публикуется четыре раза в год для изготовителей устройств, подобных TomTom.

Каждый такой дорожный сегмент имеет ассоциированные с ним данные о скорости для этого дорожного сегмента, который предоставляет указатель скорости, с которой транспортное средство может ехать вдоль этого сегмента, и он является средней скоростью, сгенерированной стороной, которая вывела данные карты, которой может быть, например, Tele Atlas. Данные о скорости используются алгоритмами планировании маршрута на устройствах PND, на которых обрабатывается карта. Таким образом, точность такого планирования маршрута зависит от точности данных о скорости. Например, пользователю часто предоставляют возможность на его/ее PND, чтобы сделать так, чтобы оно сгенерировало самый быстрый маршрут между текущим местоположением устройства и местом назначения. Маршрут, вычисленный PND, может не быть самым быстрым маршрутом, если данные о скорости неточны.

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

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

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

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

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

ii. генерирование среднего значения категории для каждой категории в пределах классификации;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

генерировать среднее значение категории для каждой категории в пределах классификации;

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

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

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

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

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

В любом из вышеупомянутых аспектов изобретения считываемый машиной носитель может содержать любое из следующего: гибкий диск, CD ROM, DVD ROM/RAM (включая -R/-RW и + R/+RW), жесткий диск, память (включая ключ памяти USB, карточку SD, Memorystick™, компактную флеш-карту или подобное), магнитную ленту, любую другую форму магнитооптического запоминающего устройства, переданный сигнал (включая загрузку из Интернета, передачу FTP и т.д.), провод или любой другой подходящий носитель.

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

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

Фиг. 1 - это схематичная иллюстрация примерной части Глобальной Системы Расположения (GPS), используемой навигационным устройством;

Фиг. 2 - это схематичная диаграмма системы связи для связи между навигационным устройством и сервером;

Фиг. 3 - это схематичная иллюстрация электронных компонентов навигационного устройства согласно Фиг. 2 или любого другого подходящего навигационного устройства;

Фиг. 4 - это схематичная диаграмма компоновки сборки и/или установки навигационного устройства;

Фиг. 5 - это схематичное представление архитектурного стека, используемого навигационным устройством, согласно Фиг. 3;

Фиг. 6 показывает последовательность операций, описывающую вариант осуществления для сопоставления привязок GPS, которые находятся в пределах трассы, с картой;

Фиг. 7 показывает последовательность операций, описывающую вариант осуществления для генерирования среднего значения;

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

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

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

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

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

Подробное описание варианта осуществления изобретения

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

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

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

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

Согласно вышеупомянутым условиям Глобальная Система Определения местоположения (GPS) согласно Фиг. 1 и подобная используется для множества целей. В целом, GPS - это навигационная система, основанная на радиоспутнике, способная определять непрерывную позицию, скорость, время и в некоторых случаях информацию направления для неограниченного числа пользователей. Прежде известная как NAVSTAR, GPS объединяет множество спутников, которые вращаются вокруг земли на чрезвычайно точных орбитах. На основании этих точных орбит спутники GPS могут ретранслировать свое местоположение в качестве данных GPS любому числу принимающих блоков. Однако должно быть понятно, что могут быть использованы такие Глобальные Системы Определения местоположения, как GLOSNASS, европейская система позиционирования Galileo, система позиционирования COMPASS или IRNSS (Индийская региональная навигационная спутниковая система).

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

Как показано на Фиг. 1, система 100 GPS содержит множество спутников 102, обращающихся по орбите вокруг Земли 104. Приемник 106 GPS принимает данные GPS в качестве сигналов 108 данных спутника GPS с расширенным спектром от множества спутников 102. Сигналы 108 данных с расширенным спектром непрерывно передаются от каждого спутника 102, каждые переданные сигналы 108 данных с расширенным спектром содержат поток данных, включающих в себя информацию, идентифицирующую конкретный спутник 102, от которого исходит поток данных. Приемник 106 GPS обычно требует сигналы 108 данных с расширенным спектром по меньшей мере от трех спутников 102, чтобы быть в состоянии вычислять двумерную позицию. Прием четвертого сигнала данных с расширенным спектром позволяет приемнику 106 GPS вычислять, используя известную методику, трехмерную позицию.

На Фиг. 2 навигационное устройство 200 (то есть PND), содержащее или подсоединенное к устройству 106 приемника GPS, способно устанавливать сеанс передачи данных, если требуется, с аппаратным обеспечением сети "мобильной связи" или сети передачи данных с помощью мобильного устройства (не показано), например, мобильного телефона, PDA и/или любого устройства с технологией мобильного телефона, чтобы устанавливать цифровое соединение, например, цифровое соединение с помощью известной технологии Bluetooth. После этого через своего поставщика услуг сети мобильное устройство может устанавливать сетевое соединение (например, через Интернет) с сервером 150. Как таковое, "мобильное" сетевое соединение может быть установлено между навигационным устройством 200 (которое часто может быть мобильным, поскольку оно перемещается одно и/или в транспортном средстве) и сервером 150, чтобы обеспечивать шлюз "в реальном времени" или по меньшей мере "современный" шлюз для информации.

Установление сетевого соединения между мобильным устройством (с помощью поставщика услуг) и другим устройством, таким как сервер 150, используя, например, Интернет, может быть сделано известным способом. В этом отношении может быть использовано любое число соответствующих протоколов линии передачи данных, например, многоуровневый протокол TCP/IP. Кроме того, мобильное устройство может использовать любое число стандартов связи, таких как CDMA2000, GSM, IEEE 802.11 a/b/c/g/n и т.д.

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

Хотя не показано, конечно, навигационное устройство 200 может включать в себя свою собственную технологию мобильного телефона в непосредственно самом навигационном устройстве 200 (например, включая антенну или необязательно используя внутреннюю антенну навигационного устройства 200). Технология мобильного телефона в навигационном устройстве 200 может включать в себя внутренние компоненты и/или может включать в себя вставную карточку (например, карточку Модуля Идентификации Абонента (SIM)), в комплекте, например, с необходимой технологией мобильного телефона и/или антенной. Как таковая, технология мобильного телефона в навигационном устройстве 200 может аналогично устанавливать сетевое соединение между навигационным устройством 200 и сервером 150, например, с помощью Интернета способом, аналогичным таковому любого мобильного устройства.

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

На Фиг. 2 навигационное устройство 200 изображается как находящееся в связи с сервером 150 с помощью общего канала связи 152, который может быть реализован любым из многих различных способов компоновки. Обычно канал 152 связи представляет среду или путь распространения, который соединяет навигационное устройство 200 и сервер 150. Сервер 150 и навигационное устройство 200 могут связываться, когда устанавливается соединение с помощью канала 152 связи между сервером 150 и навигационным устройством 200 (отметим, что такое соединение может быть соединением передачи данных с помощью мобильного устройства, прямым соединением через персональный компьютер с помощью Интернета и т.д.).

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

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

Сигналы связи, переданные через канал 152 связи, включают в себя, но не ограничиваются, сигналы, которые могут потребоваться или могут быть желаемыми для заданной технологии связи. Например, сигналы могут быть адаптированы, чтобы быть использованными в технологии сотовой связи, такой как множественный доступ с временным разделением каналов (TDMA), множественный доступ с частотным разделением каналов (FDMA), множественный доступ с кодовым разделением каналов (CDMA), глобальная система связи с мобильными объектами (GSM), система пакетной радиосвязи общего назначения (GPRS) и т.д. Как цифровые, так и аналоговые сигналы могут быть переданы через канал 152 связи. Эти сигналы могут быть модулированными, зашифрованными и/или сжатыми сигналами, которые могут быть желаемыми для технологии связи.

Сервер 150 включает в себя, в дополнение к другим компонентам, которые могут быть не проиллюстрированы, процессор 154, подсоединенный оперативным способом к памяти 156 и дополнительно подсоединенный оперативным способом с помощью проводного или беспроводного соединения 158 к массовому запоминающему устройству 160. Массовое запоминающее устройство 160 содержит хранилище навигационных данных и информацию карты и снова может быть отдельным устройством от сервера 150 или может быть включено в сервер 150. Процессор 154 дополнительно оперативно подсоединяется к передатчику 162 и приемнику 164 для передачи и приема информации на и от навигационного устройства 200 с помощью канала 152 связи. Посланные и принятые сигналы могут включать в себя данные, связь и/или другие распространенные сигналы. Передатчик 162 и приемник 164 могут быть выбраны или сформированы согласно требованию связи и технологии связи, которые используются в проекте связи для навигационной системы 200. Дополнительно должно быть отмечено, что функции передатчика 162 и приемника 164 могут быть объединены в единственный приемопередатчик.

Как упомянуто выше, навигационное устройство 200 может быть скомпоновано так, чтобы связываться с сервером 150 через канал 152 связи, используя передатчик 166 и приемник 168, чтобы посылать и принимать сигналы и/или данные через канал 152 связи, отметим, что эти устройства могут быть дополнительно использованы для связи с устройствами, кроме сервера 150. Дополнительно передатчик 166 и приемник 168 выбираются или создаются согласно требованиям связи и технологии связи, которые используются в проекте связи для навигационного устройства 200, и функции передатчика 166 и приемника 168 могут быть объединены в единственный приемопередатчик, как описано выше относительно Фиг. 2. Конечно, навигационное устройство 200 содержит другое аппаратное обеспечение и/или функциональные части, которые описаны позже в настоящем описании более подробно.

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

Сервер 150 составляет удаленный источник данных, доступный посредством навигационного устройства 200 с помощью беспроводного канала. Сервер 150 может включать в себя сетевой сервер, расположенный в локальной сети (LAN), глобальной сети (WAN), виртуальной частной сети (VPN) и т.д.

Сервер 150 может включать в себя персональный компьютер, такой как настольный компьютер или ноутбук, и канал 152 связи может быть кабелем, подсоединенным между персональным компьютером и навигационным устройством 200. Альтернативно, персональный компьютер может быть подключен между навигационным устройством 200 и сервером 150, чтобы устанавливать Интернет-соединение между сервером 150 и навигационным устройством 200.

Навигационное устройство 200 может быть обеспечено информацией от сервера 150 с помощью загрузок информации, которые время от времени могут быть автоматически обновлены, или в соответствии с подсоединением навигационного устройства 200 пользователем к серверу 150, и/или могут быть более динамичными в соответствии с более постоянным или частым соединением, сделанным между сервером 150 и навигационным устройством 200 с помощью, например, беспроводного мобильного устройства соединения и соединения TCP/IP. Для многих динамических вычислений процессор 154 в сервере 150 может быть использован, чтобы оперировать большим количеством потребностей обработки, однако процессор (не показан на Фиг. 2) навигационного устройства 200 может также оперировать большим объемом обработки и вычисления, часто независимо от подсоединения к серверу 150.

Ссылаясь на Фиг. 3, должно быть отмечено, что блок-схема навигационного устройства 200 не включает в себя все компоненты навигационного устройства, но является только характерной для многих примерных компонентов. Навигационное устройство 200 располагается в пределах здания (не показано). Навигационное устройство 200 включает в себя схему обработки, содержащую, например, процессор 202, упомянутый выше, причем процессор 202 подсоединяется к устройству 204 ввода и устройству отображения, например экрану 206 дисплея. Хотя в настоящем описании делается ссылка на устройство 204 ввода в единственном числе, специалист в данной области техники должен оценить, что устройство 204 ввода представляет любое число устройств ввода, включая устройство клавиатуры, голосовое устройство ввода, сенсорный экран и/или любое другое известное устройство ввода, используемое для ввода информации. Аналогично экран 206 дисплея может включать в себя любой тип экрана дисплея, такой как, например, дисплей на жидких кристаллах (LCD).

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

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

Процессор 202 оперативно подсоединяется к памяти 214 с помощью соединения 216 и дополнительно адаптируется, чтобы принимать/посылать информацию от/на порты 218 ввода/вывода (в/в, I/O) с помощью соединения 220, в котором порт 218 I/O является подсоединяемым к устройству 222 I/O, внешнему по отношению к навигационному устройству 200. Внешнее устройство 222 I/O может включать в себя, но не ограничиваться ими, внешнее устройство для прослушивания, такое как, например, наушник. Соединение с устройством 222 I/O может дополнительно быть проводным или беспроводным соединением с любым другим внешним устройством, таким как автомобильная стереомагнитола для работы в автоматическом (hands-free) режиме и/или для работы, активизируемой голосом, например, для подсоединения к наушнику или головным телефонам, и/или, например, для подсоединения к мобильному телефону, в котором соединение с помощью мобильного телефона может быть использовано для установления соединения передачи данных между навигационным устройством 200 и Интернетом или, например, любой другой сетью, и/или для установления соединения с сервером с помощью Интернета или, например, некоторой другой сети.

Память 214 навигационного устройства 200 содержит часть энергонезависимой памяти (например, для сохранения программного кода) и часть энергозависимой памяти (например, для сохранения данных, когда выполняется программный код). Навигационное устройство также содержит порт 228, который связывается с процессором 202 с помощью соединения 230, чтобы разрешить добавление сменной карточки памяти (обычно называемой карточкой) к устройству 200. В описываемом варианте осуществления порт выполнен с возможностью разрешить добавление карточки SD (Формат Secure Digital). В других вариантах осуществления порт может разрешать подсоединение памяти других форматов (таким, как карточки Flash (CF), Memory Sticks™, карточки памяти xD, флеш-память USB (универсальная последовательная шина), карточки MMC (Мультимедиа), карточки SmartMedia, Microdrive или подобное).

Фиг. 3 дополнительно иллюстрирует оперативное соединение между процессором 202 и антенной/приемником 224 с помощью соединения 226, в котором антенна/приемник 224 может быть, например, антенной/приемником GPS и также будет функционировать в качестве приемника 106 GPS согласно Фиг. 1. Должно быть понятно, что антенна и приемник, обозначенные ссылочной позицией 224, схематично объединяются для иллюстрации, но эти антенна и приемник могут быть раздельно расположенными компонентами, и что антенна может быть, например, патч-антенной GPS или спиральной антенной.

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

В дополнение портативное или карманное навигационное устройство 200 согласно Фиг. 3 может подсоединяться или "устанавливаться" известным способом на транспортное средство такое, как, например, велосипед, мотоцикл, автомобиль или лодка. Затем такое навигационное устройство 200 удаляется от установленного местоположения для портативного или карманного навигационного использования. Действительно, в других вариантах осуществления устройство 200 может быть скомпоновано так, чтобы быть карманным, чтобы позволять осуществлять навигацию пользователя.

Ссылаясь на Фиг. 4, навигационное устройство 200 может быть блоком, который включает в себя интегрированное устройство 206 ввода и отображения и другие компоненты согласно Фиг. 2 (включая, но не ограничиваясь, внутренний приемник 224 GPS, процессор 202, источник питания (не показан), системы памяти 214 и т.д.).

Навигационное устройство 200 может устанавливаться на кронштейне 252, который непосредственно может быть прикреплен к приборной панели/окну/т.д. транспортного средства, используя присоску 254. Этот кронштейн 252 является одним примером установочной станции, на которую может быть установлено навигационное устройство 200. Навигационное устройство 200 может быть установлено или, иначе, подсоединено к кронштейну 252 установочной станции посредством, например, подсоединения навигационного устройства 200 к кронштейну 252 с помощью защелки. Кроме того, навигационное устройство 200 может быть вращающимся по отношению к кронштейну 252. Чтобы освободить соединение между навигационным устройством 200 и установочной станцией, например, может быть нажата кнопка (не показана) на навигационном устройстве 200. Другие одинаково подходящие размещения для подсоединения и отсоединения навигационного устройства 200 для установочной станции известны специалистам в данной области техники.

На Фиг. 5 процессор 202 и память 214 взаимодействуют, чтобы поддерживать BIOS 282 (базовую систему ввода/вывода), которая функционирует в качестве интерфейса между функциональными компонентами аппаратного обеспечения 280 навигационного устройства 200 и программного обеспечения, выполняемого устройством. Затем процессор 202 загружает операционную систему 284 из памяти 214, которая обеспечивает среду, в которой может работать прикладное программное обеспечение 286 (реализуя некоторое или все описанное планирование маршрута и навигационные функциональные возможности). Прикладное программное обеспечение 286 обеспечивает оперативную среду, включающую в себя графический интерфейс пользователя (GUI), который поддерживает основные функции навигационного устройства, например, просмотр карты, планирование маршрута, навигационные функции и любые другие функции, ассоциированные с ним. В этом отношении часть прикладного программного обеспечения 286 содержит модуль 288 генерирования вида.

В описываемом варианте осуществления процессор 202 навигационного устройства программируется для приема данных GPS, принятых антенной 224, и время от времени для сохранения этих данных GPS вместе с отметкой времени, когда данные GPS были приняты, в памяти 214, чтобы создавать запись местоположения навигационного устройства. Каждая запись данных, сохраненных таким образом, понимается как привязка GPS; то есть она является привязкой местоположения навигационного устройства, которая содержит запись широты, долготы, отметки времени и точности.

В одном варианте осуществления данные по существу сохраняются на периодической основе, которая имеет место, например, каждые 5 секунд. Специалист в данной области техники оценит, что возможны другие периоды и что есть баланс между разрешением данных и объемом памяти; то есть, поскольку разрешение данных увеличивается посредством взятия большего количества выборок, требуется больше памяти, чтобы сохранить данные. Однако в других вариантах осуществления разрешение может быть по существу каждые: 1 секунду, 10 секунд, 15 секунд, 20 секунд, 30 секунд, 45 секунд, 1 минуту, 2.5 минуты (или действительно любой период между этими периодами). Таким образом, в памяти устройства создается запись местонахождения устройства 200 в моменты времени.

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

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

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

Дополнительно процессор 202 скомпонован время от времени выгружать запись местонахождения устройства 200 (то есть данные GPS и отметки времени) на сервер 150. В некоторых вариантах осуществления, в которых навигационное устройство 200 имеет регулярный или по меньшей мере обычным образом предоставленный канал 152 связи, подсоединяющий его к серверу 150, выгрузка данных имеет место на периодической основе, которая может происходить, например, раз в каждые 24 часа. Специалист в данной области техники оценит, что другие периоды возможны и могут быть по существу любыми из следующих периодов: 15 минут, 30 минут, ежечасно, каждые 2 часа, каждые 5 часов, каждые 12 часов, каждые 2 дня, еженедельно или любым временем между этими. Действительно, в таких вариантах осуществления процессор 202 может быть скомпонован так, чтобы выгружать запись местонахождения по существу в реальном времени, хотя это может неизбежно означать, что данные на самом деле время от времени передаются с относительно коротким периодом между передачами и также могут более корректно пониматься как в псевдореальном времени. В таких вариантах осуществления в псевдореальном времени навигационное устройство может быть скомпоновано так, чтобы буферизовать привязки GPS в памяти 214 и/или на карточке, вставленной в порт 228, и передавать их, когда сохранилось заранее определенное число. Это заранее определенное число может быть порядка 20, 36, 100, 200 или любым промежуточным числом. Специалист в данной области техники оценит, что заранее определенное число, в частности, управляется объемом памяти 214/карточки в порте 228.

В других вариантах осуществления, которые не имеют обычным образом предоставленного канала 152 связи, процессор 202 может быть скомпонован, чтобы выгружать запись на сервер 152, когда создается канал 152 связи. Это может иметь место, например, когда навигационное устройство 200 подсоединяется к компьютеру пользователя. Снова в таких вариантах осуществления навигационное устройство может быть скомпоновано, чтобы буферизировать привязки GPS в памяти 214 или на карточке, вставленной в порт 228. Если память 214 или карточка, вставленная в порт 228, становится заполненной привязками GPS, навигационное устройство может быть скомпоновано, чтобы удалять самые старые привязки GPS, и также оно может пониматься как буфер "первым пришел, первым обслужен" (FIFO).

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

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

Сервер 150 компонуется для приема записи местонахождений устройства и сохранения ее в массовом запоминающем устройстве 160 для обработки. Таким образом, когда проходит время, массовое запоминающее устройство 160 накапливает множество записей местонахождения навигационных устройств 200, которые выгрузили данные.

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

В качестве первого процесса сервер 150 компонуется, чтобы выполнять функцию сопоставления карт между данными карты и привязками GPS, которые содержатся в записях местонахождений, которые были приняты, и такой процесс описывается со ссылками на Фиг. 6. Такое сопоставление карт может быть выполнено так называемым способом реального времени; то есть когда записи местонахождения принимаются или может быть выполнено спустя некоторое время после того, как записи местонахождения были выбраны из массового запоминающего устройства 160.

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

В пределах каждой поездки привязки GPS, чьи отчеты точности, принятые от навигационного устройства, недостаточно высоки, отвергаются 602. Таким образом, в некоторых вариантах осуществления привязка может быть отклонена, если запись точности указывает, что сигналы от менее чем трех спутников 102 были приняты навигационным устройством 200 относительно этой привязки GPS. Дополнительно каждая поездка прерывается 604, когда сообщенное время между привязками становится выше порогового значения. Каждая поездка, которая проходит эту стадию предварительной обработки, передается, чтобы быть сопоставленной с картой.

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

Однако до того, как поездка разделится, выполняется проверка относительно того, изменилась ли позиция транспортного средства между последними двумя привязками, поскольку промежуток больше заранее определенного времени между привязками GPS может также быть результатом потери сигнала GPS, и при таких обстоятельствах поездка не разделяется. В описываемом варианте осуществления заранее определенное время составляет примерно 3 минуты. Однако специалист в данной области техники оценит, что промежуток может быть любым другим подходящим временем, таким как, например, любое из следующего: 15 секунд, 30 секунд, 1 минута, 90 секунд, 2 минуты, 5 минут, 10 минут или любое время между ними. Как рассмотрено в дальнейшем, если средняя скорость навигационного устройства 200, от которого посылаются привязки GPS, находится ниже заранее определенного порога, то данные в некоторых вариантах осуществления могут быть отклонены при более поздней обработке. Такой вариант осуществления может быть полезным, поскольку он может удалять данные, касающиеся так называемого трафика в режиме старт-стоп, который имеет место после инцидентов, таких как авария или подобное, которые могут оставлять оставшиеся данные более характерными для потока трафика установившегося режима.

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

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

Каждая поездка имеет начальную привязку (то есть первую привязку в пределах поездки), которая является более трудной для ассоциирования с сегментом, чем другие привязки в пределах поездки, поскольку не существует сегментов, которые уже были идентифицированы, которые могут быть использованы для ограничения выбора сегментов. Если для этой первой привязки множественные сегменты находятся в пределах порога 606, то алгоритм переключается на следующую привязку GPS (то есть 2-ю привязку) в пределах поездки и генерирует набор корней из этих множественных сегментов на основании возможного перемещения в качестве функции расстояния между 2 привязками (то есть между 1-й и 2-й привязками). Если 2-я привязка не приводит к единственному сегменту кандидата для 1-й привязки, то алгоритм переходит к 3-й привязке в пределах поездки и снова генерирует и сравнивает возможные маршруты, чтобы попытаться обеспечить единственного кандидата для первой привязки 608. Этот процесс может продолжаться до тех пор, пока оставшиеся привязки GPS в пределах поездки не будут обработаны.

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

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

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

Если в какой-нибудь точке устройство сопоставления карты не в состоянии идентифицировать сегмент для данной привязки, которая следует за предыдущим сегментом, или потому что не существует сегментов в пределах порога, или оно не может однозначно определить единственный сегмент, то устройство сопоставления карты компонуется так, чтобы обходить последующие привязки 616, чтобы дополнительно ограничивать рейс до тех пор, пока оно не сможет идентифицировать сегмент, который является единственным совпадением. Таким образом, если n-я привязка не может единственным способом ассоциироваться с сегментом, сегмент n+1 используется для дополнительного ограничения идентификационной информации сегмента. Если привязка n+1 не дает получить единственный сегмент, то используется привязка n+2. В некоторых вариантах осуществления этот процесс может осуществляться до тех пор, пока не будет идентифицирован единственный сегмент или не будут обработаны все привязки GPS с поездкой.

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

Поэтому в конце процесса, в который устройство сопоставления карты выполнено с возможностью выполнять, получают последовательность дорожных сегментов, вдоль которых навигационное устройство 200 перемещалось в течение проанализированной поездки. Затем устройство сопоставления карты дополнительно обрабатывает эти дорожные сегменты и назначает, исходя из привязок GPS, время входа и также транзитное перевозки для этого сегмента. Эти назначенные времена сохраняются в массовом запоминающем устройстве 160 для более поздней обработки. Может быть так, что множество привязок GPS сохраняются для каждого дорожного сегмента. Однако независимо от того, сколько привязок GPS ассоциируется с каждым сегментом, время входа, привязки GPS и длина сегмента (которая в этом варианте осуществления сохраняется в данных карты) используются для вычисления средней скорости для этого сегмента дороги. Затем эта средняя скорость сохраняется в массовом запоминающем устройстве 160, ассоциированном с соответствующими назначенными временами и этим сегментом. Информация, касающаяся скорости потока трафика на дорожном сегменте и назначенная дорожному сегменту, может пониматься как данные о скорости для этого дорожного сегмента.

Сервер 150 дополнительно компонуется, чтобы выполнять программный код усреднения на процессоре 154, чтобы обеспечивать схему усреднения, которая обрабатывает назначенные времена, чтобы сгенерировать одно или более средних значений из них, как описано ниже. Процесс усреднения, используемый в этом варианте осуществления, описывается со ссылками на Фиг. 7.

На первом этапе процесса 700 схема усреднения группирует средние скорости для каждого дорожного сегмента на обрабатываемой карте. В пределах группировки для каждого дорожного сегмента схема усреднения дополнительно компонуется, чтобы группировать средние скорости в набор заранее определенных периодов 702 времени. Таким образом, средние скорости, которые имеют место в пределах одного и того же периода времени (например, между 8.00 утра и 8.59 утра) группируются для дополнительного анализа. В описываемом варианте осуществления периоды времени - это продолжительность в течение часа, но это необязательно, и специалист в данной области техники оценит из последующего описания, что, поскольку длина периода времени уменьшается, разрешение данных увеличивается, но увеличиваются требования к запоминающему устройству. Другие подходящие периоды времени могут быть по существу любым из следующего: 1 минута, 5 минут, 10 минут, 15 минут, 30 минут, 2 часа, 6 часов, 12 часов или любое время между этими временами.

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

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

После того как была выполнена группировка в заранее определенные периоды времени, средняя скорость вычисляется для каждого дорожного сегмента в течение каждого заранее определенного периода времени. Например, все скорости в пределах периода времени с 8.00 утра до 8.59 утра для каждого сегмента дороги усредняются. Есть несколько возможностей для вычисления средней скорости: использование простого арифметического или гармонического анализа или вычисление срединного значения выборки. Действительно, в некоторых вариантах осуществления различные веса могут быть использованы для наборов данных согласно намеченному позже использованию данных.

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

Однако, прежде чем будут использоваться дополнительные средние скорости для каждого сегмента, выполняется 706 проверка качества. В этом варианте осуществления эта проверка гарантирует, что более чем заранее определенное число назначенных времен было использовано для генерирования средней скорости для каждого сегмента. Если дело обстоит не так, то эта средняя скорость для каждого сегмента отбрасывается для дополнительной обработки оставшегося промежутка для этого сегмента в одном или более периодах времени. В некоторых вариантах осуществления среднее значение отбрасывается, если есть менее чем 5 значений, которые были взяты, чтобы составить это среднее значение. Конечно, другие варианты осуществления могут использовать отличные значения, такие как 2, 3, 4, 6, 7, 8, 10, 20 или более, или любое значение между этими.

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

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

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

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

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

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

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

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

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

В дополнительных вариантах осуществления средняя скорость или ограничение скорости дорожного сегмента может использоваться в качестве дополнительного критерия для выполнения нормализации.

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

В одном варианте осуществления алгоритм кластеризации выполняется и компонуется так, чтобы сгенерировать приблизительно 60 кластеров. В других вариантах осуществления алгоритм может быть скомпонован, чтобы сгенерировать больше или меньше кластеров первоначально. Затем получающиеся в результате кластеры обрабатываются, чтобы определять, являются ли сгенерированные кластеры удовлетворительными: действительно ли некоторые из кластеров слишком аналогичны (то есть по существу одинаковыми)? Имеет ли любой из кластеров разрывы в нем? Если существуют проблемы с любым из кластеров, то алгоритм запускается снова с процессом, стремящимся сгенерировать меньше кластеров, чем первая итерация. Этот итерационный процесс повторяется до тех пор, пока не будет определен удовлетворительный набор кластеров.

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

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

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

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

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

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

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

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

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

Каждый дорожный сегмент, который представлен на обрабатываемой карте, анализируется и может иметь один из скоростных кластерно-сгенерированных профилей (как показано на Фиг. 9), ассоциированных с ним, и этот процесс описывается со ссылками на Фиг. 12. Начиная с n=1, обрабатывается 1200 n-й дорожный сегмент.

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

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

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

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

Снова специалист в области статистики техники оценит измерения, которые могут быть использованы для измерения качества среднего значения. Например, в некоторых вариантах осуществления может быть потребовано, чтобы среднее значение составлялось из более чем заранее определенного числа скоростей, которое может быть равно, например, примерно 10 скоростям. Пороги могут быть применены к средним значениям, чтобы гарантировать, что они находятся выше минимального значения (которое, например, может составлять примерно 2 км/ч) и/или ниже максимального значения (которое, например, может составлять примерно 150 км/ч). Среднеквадратическое отклонение также может быть использовано для определения, имеет ли среднее значение достаточно высокое качество.

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

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

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

Если среднее значение, сгенерированное из собранных данных от этого сегмента, все еще дает сбой при проверке качества, то используется следующий этап 1002 стратегии возврата, и используется так называемый процесс заполнения промежутков, который описывается со ссылками на Фиг. 11. В качестве первого этапа каждый дорожный сегмент на обрабатываемой карте классифицируется в качестве члена одной из заранее определенного числа категорий 1100. Специалист в данной области техники оценит, что эта классификация каждого дорожного сегмента должна быть выполнена только один раз, и вызывают получающуюся в результате классификацию, поддерживаемую для дополнительных дорожных сегментов, для которых запускается процесс заполнения промежутков. Конечно, другие варианты осуществления могут повторно вычислять при каждом вызове или действительно вычислять категории "на лету".

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

Таблица 1 Автострады 0 Любая автострада внутри или вне города, кроме окольной дороги, подъездной дороги или параллельной дороги 1 Окольная дорога на автостраде внутри или вне города 2 Подъездная дорога на автостраде внутри или вне города 3 Параллельная дорога на автостраде внутри или вне города Международные дороги 4 Любая международная дорога вне города, кроме окольной   дороги или подъездной дороги 5 Любая международная дорога внутри города, кроме окольной дороги или подъездной дороги 6 Окольная дорога на международной дороге вне города 7 Окольная дорога на международной дороге внутри города 8 Подъездная дорога на международной дороге вне города 9 Подъездная дорога на международной дороге внутри города Главные дороги 10 Любые главные дороги вне города, кроме окольной дороги, подъездной дороги или параллельной дороги 11 Любые главные дороги внутри города, кроме окольной дороги, подъездной дороги или параллельной дороги 12 Окольная дорога на главных дорогах вне города 13 Окольная дорога на главных дорогах внутри города 14 Подъездная дорога на главных дорогах 15 Подъездная дорога на главных дорогах внутри города 16 Параллельная дорога на главных дорогах внутри и вне города Дороги второстепенного значения 17 Любые дороги второстепенного значения вне города, кроме окольной дороги, подъездной дороги или параллельной дороги 18 Любые дороги второстепенного значения внутри города, кроме окольной дороги, подъездной дороги или параллельной дороги 19 Окольная дорога на дорогах второстепенного значения вне города 20 Окольная дорога на дорогах второстепенного значения внутри города 21 Подъездная дорога на дорогах второстепенного значения вне города 22 Подъездная дорога на дорогах второстепенного значения внутри города 23 Параллельная дорога на дорогах второстепенного значения внутри и вне города Дороги сообщения 24 Любые дороги сообщения вне города, кроме окольной дороги или подъездной дороги 25 Любые дороги сообщения внутри города, кроме окольной дороги или подъездной дороги 26 Окольная дорога на дорогах сообщения вне города 27 Окольная дорога на дорогах сообщения внутри города 28 Подъездная дорога на дорогах сообщения вне города 29 Подъездная дорога на дорогах сообщения внутри города Важные дороги местного значения 30 Любые важные дороги местного значения вне города, кроме окольной дороги 31 Любые важные дороги местного значения внутри города, кроме окольной дороги 32 Окольная дорога на важных дорогах местного значения вне города 33 Окольная дорога на важных дорогах местного значения внутри города Дороги местного значения 34 Любые дороги местного значения вне города, кроме окольной дороги 35 Любые дороги местного значения внутри города, кроме окольной дороги 36 Окольная дорога на дорогах местного значения вне города 37 Окольная дорога на дорогах местного значения внутри города Дороги места назначения 38 Любые дороги места назначения вне города 39 Любые дороги места назначения внутри города

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

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

V_mean=L/Σ l_i/V_i,

принимая во внимание, что

V_mean - средняя скорость класса j;

l_i - длина линии I;

L абсолютная длина всех линий, принадлежащих классу j (L=Σ l_i);

V_i - средняя скорость линии i.

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

Если средняя скорость из одной из этих 40 категорий основана на меньшем количестве сегментов, чем hit_number_min (которое показано для этого варианта осуществления в таблице 2 ниже), то это среднее значение заменяется значением из другой категории, как показано в таблице 3 ниже). В описываемом варианте осуществления значение для минимального числа обращения равно десяти, но оно может изменяться в других вариантах осуществления.

Если ни quality_factor_abs конкретной категории, ни quality_factor_rel этой категории не меньше или равно значениям, показанным в таблице 2, то среднее значение категории скорости заменяется средним значением назначенной категории замены, как показано в таблице 2. Следует заметить, что quality_factor_rel_min задается относительным среднеквадратическим отклонением класса в % средней скорости, поделенной на квадратный корень числа попаданий, quality_factor_abs*100/mean_speed.

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

Таблица 2 Параметр Значение по умолчанию [диапазон значения] Описания quality_factor_abs_min 3 Коэффициент качества для отклонения данных: s/sqrt(n) (среднеквадратическое отклонение абсолютной     скорости класса в км/ч, поделенное на квадратный корень числа попаданий) quality_factor_rel_min 5 Коэффициент качества для замены класса скорости: s/sqrt(n) (относительное среднеквадратическое отклонение класса в % от средней скорости, поделенной на квадратный корень числа попаданий, quality_factor_abs*100/mean_speed) hit_number_min 10 Минимальное число всех требуемых попаданий для класса скорости

Таблица 3 Номер категории скорости Номер категории скорости замены 1 0 2 0 3 0 4 10 5 4 6 4 7 5 8 4 9 5 10 11 11 10 12 10 13 11 14 10 15 11 16 10 17 18 18 17 19 17 20 18 21 17 22 18 23 17 24 25 25 24 26 24 27 25 28 24 29 25 30 31 31 30 32 30 33 31 34 35 35 34 36 34 37 35 38 39 39 38

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

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

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

Min_speed_threshold=max[max(mean-lower_relative_devision*mean/100, mean-lower_absolute_devision), lower_limit],

Max_speed_threshold=min[min (mean+upper_relative_devision*mean/100, mean+upper_absolute_devision), upper_limit],

где mean - это маршрутная (средняя) скорость соответствующего класса скорости сегмента. Другие количества определяются в таблице 4.

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

Таблица 4 Параметр Значение по умолчанию [диапазон значения] Описания upper_limit 130 Абсолютная максимально допустимая скорость для сегмента в км/ч lower_limit 5 Абсолютная минимально допустимая скорость для сегмента в км/ч upper_relative_devision 50 Максимально допустимое верхнее отклонение абсолютной скорости для сегмента в процентах среднего своего класса upper_absolute_devision 30 Максимально допустимое верхнее отклонение абсолютной скорости в км/ч для сегмента, связанного со средним своего класса lower_relative_devision 50 Минимально допустимое нижнее отклонение абсолютной скорости для сегмента в процентах среднего своего класса lower_absolute_devision 30 Минимально допустимое нижнее отклонение абсолютной скорости в км/ч для сегмента, связанного со средним своего класса

Специалист в данной области техники оценит, что вычисления выполняются в отношении скоростей, а не в соответствии с данными времени.

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

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

Если заполнение промежутков дает сбой, на этапе 1004, скорость, ассоциированная с этим дорожным сегментом, устанавливается, чтобы быть скоростью, которая была обеспечена поставщиком данных карты, согласно Функциональному Дорожному Классу (FRC). Функциональный дорожный класс может, например, содержать примерно 8 категорий, хотя это может отличаться между поставщиками данных карты. Таким образом, скорость свободного потока устанавливается равным значению согласно FRC, и скоростной кластерно-сгенерированный профиль, устанавливается в этом варианте осуществления равным профилю № 15.

Затем скоростной профиль (измеренный скоростной профиль или среднее значение, вставленное посредством заполнения промежутков), ассоциированное с дорожным сегментом, теперь отображается в один из скоростных кластерно-сгенерированных профилей для генерирования данных карты, которые могут быть использованы навигационными устройствами, такими как устройства PND. Это может быть выполнено независимо от того, является ли информация скорости измеренным скоростным профилем или средним значением ввиду наличия плоского скоростного кластерно-сгенерированного профиля №15.

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

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

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

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

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

Таблица 5 Описание FRC (Функционального Дорожного Класса) FRC Минимальная требуемая зона охвата длины [%] Автострады 0 60 Международные дороги 1 50 Главные дороги 2 40

Дороги второстепенного значения 3 30 Дороги сообщения 4 18 Важные дороги местного значения 5 12 Дороги местного значения 6 2 Дороги местного значения 7 0

Следует заметить, что числам минимальной зоны охвата для дорожных категорий, которые в целом оказывают больше влияния на поведение маршрутизации, дается более высокое требование в процентах по сравнению с дорожными категориями, которые оказывают более низкое влияние. Например, FRC 0 (Автострады) обязаны иметь 60%, так как они оказывают более высокое влияние на маршрутизацию, по сравнению, например, с дорогами второстепенного значения, которые, следовательно, имеют требование для 30%-ной зоны охвата.

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

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

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

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

Изобретение относится к области приборостроения и может найти применение в системах дистанционной обработки позиционной информации. Технический результат - расширение функциональных возможностей. Для этого способ и система обработки данных позиционирования содержат: классифицирование данных о скорости, ассоциированных, по меньшей мере, с некоторыми сегментами навигации, содержащие данные о скорости, ассоциированные с наблюдаемым объектом, множественную категорию классификации, по которым данные о скорости могут быть классифицированы согласно параметру сегмента с возможностью навигации, с которым ассоциированы данные о скорости; этап и средства для генерирования среднего значения категории для каждой категории в пределах классификации; этап и средства для оценки, по меньшей мере, некоторых сегментов с возможностью навигации объекта в пределах данных карты для определения, существуют ли данные о скорости, ассоциированные с объектом; и если не существует данных о скорости, ассоциированных с сегментом с возможностью навигации, используют средние значения категории согласно параметру обрабатываемого сегмента с возможностью навигации объекта. 3 н. и 7 з.п. ф-лы, 12 ил., 5 табл.

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

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

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

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

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

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

7. Способ по любому из пп.4-6, в котором кластерно-сгенерированные скоростные профили нормализуют согласно параметру.

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

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

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