Способ создания картографических данных

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

 

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

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

Уровень техники изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В любом из вышеуказанных аспектов изобретения машиночитаемый носитель может содержать любой из следующих: гибкий диск, 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-данные, любому числу приемных устройств. Однако будет понятно, что могут использоваться системы глобального позиционирования, такие как GLONASS, Европейская система позиционирования Galileo, система позиционирования COMPASS или IRNASS (Индийская региональная навигационная спутниковая система).

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

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

Обращаясь к фиг.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 может также включать в себя любое дополнительное устройство ввода и/или любое дополнительное устройство вывода, такие как, например, устройства звукового ввода/вывода.

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

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

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

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

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

Обращаясь к фиг.4, навигационное устройство 200 может быть устройством, которое включает в себя интегрированное устройство 206 ввода и отображения и другие компоненты на фиг.2 (включающие в себя, но не ограничивающиеся этим, внутренний GPS-приемник 224, процессор 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 может быть выполнен с возможностью выгрузки записи на сервер 150, когда канал 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:00 воскресным утром для первого сегмента дороги может быть подобна скорости в то же время на втором сегменте дороги. Если эта схожесть для таких сегментов дороги повторяется для других моментов времени, тогда скоростной профиль для первого и второго сегментов может рассматриваться как представленный одним и тем же скоростным профилем второго сегмента. Кластеризация, как теперь определено, имеет целью находить такие сходства. Нормализация скоростных профилей, как обсуждается ниже, может также допускать использование скоростного профиля для дорог другого класса.

Прежде чем выполняется кластеризация, измеренный скоростной профиль дополнительно обрабатывается для того, чтобы объединять ночные периоды времени. В этом варианте осуществления средние скорости между 21:00 и 05:00 (т.е. 8-часовые периоды времени) усредняются, и это среднее значение ночного времени используется для каждого из 8-часовых периодов; т.е. измеренный скоростной профиль модифицируется, чтобы заменять его часть модифицированными значениями для средних скоростей для одного или более предварительно определенных периодов времени, которые содержат использование среднего значения средних скоростей, которые должны быть заменены, в качестве модифицированного значения для каждого из предварительно определенных периодов времени. Таким образом, каждый скоростной профиль имеет ровный скоростной профиль между 21:00 и 08:00, что может быть названо скоростью свободного потока этого сегмента дороги. Можно предположить, что скорость свободного потока представляет скорость, с которой транспортное средство, как правило, автомобиль, движется по дороге, и часто это является случаем, когда скорость свободного потока отличается от ограничения скорости для этого сегмента дороги. Скорость свободного потока может также быть приблизительно такой же, что и ограничение скорости для этого сегмента дороги.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В описываемом варианте осуществления существуют 40 таких категорий, как обозначено в следующей таблице 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	любые дороги до пункта назначения в пределах города
Таблица 1

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

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

При этом

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

- l_i: длина линии i

- L: общая длина всех линий, принадлежащих классу j ()

- 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.

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

Номер категории скорости	Номер категории скорости замены
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
Таблица 3

Значения, показанные в таблице 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.

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

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

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

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

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

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

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

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

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

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

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

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

Описание FRC (функционального класса дороги)	FRC	Минимальный требуемый охват расстояния (%)
Автострады	0	60
Международные дороги	1	50
Главные дороги	2	40
Второстепенные дороги	3	30
Соединяющие дороги	4	18
Важные местные дороги	5	12
Местные дороги	6	2
Дороги до пункта назначения	7	0
Таблица 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10. Машиночитаемый носитель, содержащий инструкции, которые, когда выполняются машиной, побуждают машину:
i. выполнять способ по любому из пп.1-8,
ii. функционировать как машина по п.9.