СПОСОБ И МАШИНА ДЛЯ ГЕНЕРИРОВАНИЯ КАРТОГРАФИЧЕСКИХ ДАННЫХ И СПОСОБ И НАВИГАЦИОННОЕ УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАРШРУТА, ИСПОЛЬЗУЯ КАРТОГРАФИЧЕСКИЕ ДАННЫЕ
METHOD AND MACHINE FOR GENERATION OF MAPPING DATA AND METHOD AND NAVIGATION DEVICE FOR ROUTE DETECTION, USING MAPPING DATA

Область техники, к которой относится изобретение
Изобретение относится к способу и машине для генерирования картографических данных, в частности, картографических данных, которые должны быть использованы в навигационных устройствах, и способу и навигационному устройству для определения маршрута, используя картографические данные. Изобретение имеет конкретное применение в портативных навигационных устройствах (PND).
Уровень техники
Картографические данные для электронных навигационных устройств, таких как персональные навигационные устройства на основе GPS, подобные GO™ компании TomTom International BV, поступают от специальных производителей карт, таких как Tele Atlas NV. Такие устройства также упоминаются как портативные навигационные устройства (PND). Эти картографические данные специально предназначены для использования алгоритмами прокладки маршрута, обычно использующими данные местоположения от GPS-системы. Например, дороги могут быть описаны как линии - т.е. векторы (например, начальная точка, конечная точка, направление для дороги, причем вся дорога составляется из многих сотен таких сегментов, каждый уникально задается параметрами направления начальной точки/конечной точки). Карта тогда является набором таких векторов дороги, данных, ассоциированных с каждым вектором (предел скорости; направление движения и т.д.) плюс точки интереса (POI), плюс названия дорог, плюс другие географические признаки, подобные границам парков, границам рек и т.д., все из которых задаются в виде векторов. Все картографические признаки (например, векторы дороги, POI и т.д.) обычно задаются в координатной системе, которая соответствует или относится к координатной системе GPS, позволяя определять местоположение устройства, определенное при помощи GPS-системы, на относящейся дороге, показанной на карте, и планировать оптимальный маршрут к пункту назначения.
Чтобы составить эту картографическую базу данных, компания Tele Atlas начинает с базовой информации о дорогах из различных источников, таких как карты Ordnance Survey для дорог в Англии. Она также имеет большую выделенную команду транспортных средств, ездящих по дорогам, плюс персонал, проверяющий другие карты и аэрофотоснимки для обновления и проверки ее данных. Эти данные составляют ядро картографической базы данных компании Tele Atlas. Эта картографическая база данных постоянно совершенствуется данными с географической привязкой. Она затем проверяется и публикуется четыре раза в год для производителей устройств, подобных компании TomTom.
Каждый такой сегмент дороги имеет ассоциированный с ним параметр скорости для этого сегмента дороги, который дает указание о скорости, с которой транспортное средство может двигаться по этому сегменту, и является средней скоростью, генерируемой стороной, которая получила картографические данные, которой может быть, например, Tele Atlas. Параметр скорости используется алгоритмами планирования маршрута на PND, на котором обрабатывается карта. Точность такого планирования маршрута, таким образом, зависит от точности параметра скорости. Например, пользователю часто представляется вариант выбора на его PND, чтобы он генерировал самый быстрый маршрут между текущим местоположением устройства и пунктом назначения. Маршрут, вычисленный посредством PND, может действительно не быть самым быстрым маршрутом, если параметры скорости являются неточными.
Известно, что параметры, такие как интенсивность движения транспорта, могут оказывать существенное влияние на профиль скорости сегмента дороги, и такие изменения профиля скорости означают, что самый быстрый маршрут между двумя точками может не оставаться одним и тем же. Неточности в параметре скорости сегмента дороги также могут привести к неточному расчетному времени прибытия (ETA), а также выбору субоптимального самого быстрого маршрута.
Tele Atlas разработала систему, в которой GPS-данные загружаются из PND и используются для предоставления параметров скорости для сегментов картографических данных, целью которых является предоставление параметров скорости, которые показывают действительную скорость на сегменте дороги в заранее определенные моменты времени дня.
Сущность изобретения
Согласно первому аспекту изобретения предоставляется способ обработки данных о скорости для генерирования картографических данных, которые содержат множество доступных для навигации сегментов, представляющих сегменты доступного для навигации маршрута в зоне, покрываемой картой, причем способ содержит этапы, на которых:
i. получают данные о скорости, по меньшей мере, для одного, и как правило каждого сегмента, причем данные о скорости содержат измеренные скорости движения по сегменту в разные моменты времени;
ii. генерируют из данных о скорости для каждого сегмента данные, по меньшей мере, об одном профиле нормальной скорости, содержащем среднюю скорость движения по сегменту для момента времени, повторяющегося еженедельно;
iii. по меньшей мере, для одного заданного момента времени генерируют для некоторых, и как правило всех сегментов, данные, по меньшей мере, об одном профиле анормальной скорости, содержащем ожидаемую скорость движения по сегменту в течение заданного момента времени, причем заданный момент времени является моментом времени, который не происходит еженедельно; и
iv. присваивают сегменту или каждому сегменту картографических данных соответствующий профиль нормальной скорости и профиль анормальной скорости для использования навигационным устройством в алгоритмах прокладки маршрута для определения поездки по всей зоне.
Такой способ является полезным, потому что он способствует гарантированию, что каждый доступный для навигации сегмент в зоне, покрываемой картографическими данными, имеет профиль анормальной скорости, связанный с ним, который может использоваться в течение заданных моментов времени навигационным устройством для получения лучшего указания о потоке движения транспорта по этому сегменту дороги в этот момент времени, чем было бы в случае, если бы использовалась средняя скорость профиля нормальной скорости. Например, заданными моментами времени могут быть национальные праздники, национальные события, такие как день Рождества Христова, национальные спортивные события, например, моменты времени, когда участвует в соревновании национальная спортивная команда, дни национального празднования/траура, и/или моменты времени необычной погоды, такой как сильный дождь или снегопад, туман, чрезмерная жара или другие погодные условия, которые могут влиять на поток движения транспорта. Такая улучшенная оценка скорости для любого данного сегмента дороги в такие заданные моменты времени может действительно увеличивать точность алгоритмов прокладки маршрута для определения поездки по всей зоне, представленной картографическими данными.
Понятно, что термин «момент времени, повторяющийся еженедельно» означает момент времени, который повторяется значительное количество раз, если не все недели, т.е. моменты времени, такие как понедельники, вторники, среды, четверги, пятницы, субботы, воскресенья, рабочие дни, выходные дни и их части, такие как по утрам в понедельник, во вторник с 8 часов до полудня до 9 часов до полудня, части рабочего дня или выходного дня, такие как со вторника по четверг и т.д. Термин также может включать в себя момент времени, который повторяется еженедельно в конкретный период года, например, момент времени, который повторяется по неделям летом, зимой, осенью или весной.
Способ может содержать присвоение каждому сегменту идентификатора, идентифицирующего, когда навигационное устройство должно использовать профиль анормальной скорости для определения маршрута. Идентификация может представлять собой один или более заданных моментов времени и/или одно или более заданных условий, таких как погодные условия.
Способ может содержать идентификацию моментов времени нетипичного характера движения транспорта и генерирование профиля анормальной скорости или каждого профиля анормальной скорости посредством идентификации из данных о скорости измеренной скорости движения по сегментам в один или более из идентифицированных моментов времени в прошлом и определения из идентифицированных данных о скорости одной или более средних скоростей движения по сегменту. Например, идентифицированными моментами времени могут быть прошедшие национальные праздники, такие как официальные выходные дни Великобритании и/или день Рождества Христова, и один из профилей анормальной скорости может быть средними скоростями движения по сегментам в течение прошлых национальных праздников.
Альтернативно, генерирование профиля анормальной скорости или каждого профиля анормальной скорости может содержать скорости движения, определенные посредством увеличения или уменьшения средних скоростей профиля нормальной скорости. Например, заданными моментами времени могут быть моменты времени с суровыми погодными условиями, такими как снег или дождь, и профиль анормальной скорости для моментов времени суровой погоды могут генерироваться пропорциональным снижением средних скоростей профиля нормальной скорости с заранее определенным коэффициентом. В одном варианте осуществления профиль анормальной скорости может быть масштабным коэффициентом, и этап присвоения может содержать присвоение каждому сегменту профиля нормальной скорости и масштабного коэффициента. Использование таких масштабных коэффициентов может быть полезным, так как дополнительное пространство памяти, необходимое для хранения такого масштабного коэффициента, может быть меньше, чем полностью новый профиль скорости, содержащий средние скорости в течение заданного периода времени.
Способ может содержать идентификацию заданных моментов времени из данных о скорости посредством идентификации моментов времени в прошлом, когда измеренные скорости движения не соответствуют заранее определенным порогам для средних скоростей профиля нормальной скорости, и сопоставление этих идентифицированных моментов времени в прошлом с моментами времени в будущем. Таким образом, могут автоматически идентифицироваться заданные моменты времени.
Способ может содержать проверку, происходят ли заданные моменты времени в периоды, происходящие не еженедельно, например, ежемесячно или ежегодно. Может потребоваться так, чтобы способ мог автоматически определять, когда заданные дни будут происходить в будущем.
Заданные моменты времени могут идентифицироваться посредством поиска событий в базе данных событий. База данных событий может приниматься от внешнего источника, такого как метеостанция, организатора событий и т.д.
Способ может содержать сопоставление идентифицированных моментов времени с известными событиями, происходящими в идентифицированный момент времени, например, национальные спортивные события, фестивали или погода, и идентификацию заданных моментов времени, когда должен использоваться профиль анормальной скорости, посредством определения из базы данных событий в будущем, когда произойдут подобные события.
Доступные для навигации сегменты представляют, как правило, сегменты дороги, но также могут представлять сегменты любого другого пути, канала или т.п., доступного для навигации транспортным средством, человеком или т.п. Например, доступный для навигации сегмент может представлять сегмент пути, реки, канала, циклического пути, бечевника, железнодорожной линии или т.п.
Способ может содержать начальный этап захвата GPS-данных. Такой захват GPS-данных может быть посредством загрузки GPS-данных, по меньшей мере, с одного, и как правило множества, портативного навигационного устройства (PND). В таком способе загруженные GPS-данные из PND могут храниться для обработки на этапах способа.
Удобно, что GPS-данные обрабатываются, чтобы генерировать данные о скорости, ассоциированные с одним или более доступными для навигации сегментами. Такой способ, как считается, является полезным, так как он позволяет данным о скорости отражать записанные скорости на доступном для навигации сегменте, а не предполагать, что скорость, с которой происходит движение по сегменту, является пределом скорости, ассоциированным с этим сегментом. По существу, PND, или другие устройства, использующие картографические данные, должны быть способны создавать более точное планирование маршрута.
Данные о скорости могут генерироваться из данных, принимаемых от множества PND или других доступных для навигации устройств. Специалист в данной области техники оценит по достоинству, что базирование на данных от множества устройств вероятно приведет к данным о скорости, которые более точно соотносятся с фактическими условиями на доступном для навигации сегменте.
В некоторых вариантах осуществления обработка может генерировать измеряемый ежедневно профиль скорости для каждого доступного для навигации сегмента (т.е. профиль скорости, который является характерным для дня; в данном случае профиля нормальной скорости, характерный для дня недели). Для заданных дней обработка может генерировать измеряемую ежедневно анормальную среднюю скорость для заданного дня, например, дня, в который происходит нееженедельное событие, такое как день Рождества Христова). Ежедневно может рассматриваться в качестве первого периода времени.
В других вариантах осуществления обработка может иметь целью генерирование профиля измеренной скорости, покрывающего другие периоды времени; т.е. вторые периоды времени, которые могут быть более продолжительными периодами времени, чем первый период времени. Например, в некоторых вариантах осуществления целью обработки может быть генерирование профиля измеряемой по рабочим дням скорости и/или профиля измеряемой по выходным дням скорости. Другие варианты осуществления могут использовать профиль измеряемой один раз скорости для еженедельного периода. Специалист в данной области техники оценит по достоинству, что использование меньших периодов времени (например, ежедневно) покрытия для профиля скорости может делать профиль скорости более представляющим фактический поток движения транспорта. Однако, также будет оценено, что, когда период времени покрытия уменьшается, также увеличивается количество данных, необходимых для генерирования этих профилей измеряемой скорости.
Картографические данные могут содержать данные о первой карте, в которой профиль нормальной скорости связывается с доступными для навигации сегментами, и данные, по меньшей мере, об одной второй карте для использования в заданные моменты времени/дни, в которые профиль анормальной скорости связывается с доступными для навигации сегментами. Способ может содержать посылку данных о первой карте на навигационное устройство по запросу и посылку данных о второй карте или одной из вторых карт, когда картографические данные запрашиваются для заданного момента времени/дня, для которых применима вторая карта. Таким образом, навигационное устройство и/или пользователь могут принять решение, когда условия движения транспорта будут нетипичными для нормальных еженедельных условий движения транспорта, и запросить данные о второй карте, которые гарантируют, что алгоритмы прокладки маршрута навигационного устройства определяют маршрут на основе данных, которые являются лучшим представлением условий движения транспорта. Может быть желательным, чтобы данные о второй карте извлекались с центрального сервера обработки, чтобы снизить количество выгрузок по сравнению со способом, в котором картографические данные продвигаются в навигационное устройство с центрального сервера.
Дополнительно или альтернативно, данные об одной или более вторых карт могут посылаться на навигационное устройство автоматически в заданный момент времени/день, для которого эта вторая карта применима. Таким образом, навигационное устройство автоматически обновляется картографическими данными, которые дают лучшее представление об условиях движения транспорта.
Способ может содержать прием данных о будущих заданных моментах времени и, в ответ на прием данных о будущих заданных моментах времени, ассоциирование профиля анормальной скорости или одного из профилей анормальной скорости с будущими заданными моментами времени. Модифицированные картографические данные могут посылаться на навигационное устройство в заданный момент времени или перед ним. Например, заданный момент времени может быть моментом времени, в который происходит национальное событие, такое как спортивное событие, и данные о второй карте могут содержать анормальные средние скорости для доступных для навигации сегментов карты, которые происходят в течение такого национального события. Таким образом, навигационное устройство может определять, когда использовать профиль анормальной скорости из картографических данных.
Согласно второму аспекту изобретения предоставляется машиносчитываемый носитель данных, содержащий в себе инструкции, которые, когда они считываются машиной, вызывают выполнение машиной способа по первому аспекту изобретения.
Согласно третьему аспекту изобретения предоставляется машина, выполненная с возможностью обработки данных о скорости для генерирования картографических данных, содержащих множество доступных для навигации сегментов, представляющих сегменты доступного для навигации маршрута в зоне, покрываемой картой, причем каждый сегмент выполнен с возможностью имеет данные о скорости, ассоциированные с ним, причем машина содержит процессор, выполненный с возможностью:
i. получать данные о скорости, по меньшей мере, для одного сегмента, причем данные о скорости содержат измеренные скорости движения по сегменту в разные моменты времени;
ii. генерировать из данных о скорости для сегмента или каждого сегмента данные, по меньшей мере, об одном профиле нормальной скорости, содержащем среднюю скорость движения по сегменту для момента времени, повторяющегося еженедельно;
iii. по меньшей мере, для одного заданного момента времени генерировать для сегмента или каждого сегмента данные, по меньшей мере, об одном профиле анормальной скорости, содержащем ожидаемую скорость движения по сегментам в течение заданного момента времени, причем заданный момент времени является моментом времени, который не происходит еженедельно; и
iv. присваивать сегменту или каждому сегменту картографических данных соответствующий профиль нормальной скорости и профиль анормальной скорости для использования навигационным устройством в алгоритмах прокладки маршрута для определения поездки по всей зоне.
Согласно четвертому аспекту изобретения предоставляется машиносчитываемая среда, содержащая в себе инструкции, которые, когда они считываются машиной, вызывают выполнение машинойто, что и машина по четвертому аспекту изобретения.
Согласно пятому аспекту изобретения предоставляются картографические данные, содержащие множество доступных для навигации сегментов, представляющих сегменты доступного для навигации маршрута в зоне, покрываемой картографическими данными, каждый доступный для навигации сегмент имеет данные о скорости, ассоциированные с ним, причем, по меньшей мере, один из доступных для навигации сегментов имеет ассоциированный с ним профиль нормальной скорости, один или более профилей анормальной скорости и идентификацию того, когда навигационное устройство должно использовать профиль анормальной скорости или каждый профиль анормальной скорости в алгоритме прокладки маршрута, а не профиль нормальной скорости.
Согласно шестому аспекту изобретения предоставляется машиносчитываемая среда, содержащая в себе картографические данные пятого аспекта изобретения.
Согласно седьмому аспекту изобретения предоставляется способ определения маршрута по зоне, используя картографические данные, причем картографические данные содержат множество доступных для навигации сегментов, представляющих сегменты доступного для навигации маршрута в зоне, покрываемой картографическими данными, по меньшей мере, один из доступных для навигации сегментов имеет ассоциированный с ним профиль нормальной скорости для повторяющегося еженедельно периода времени, содержащий ожидаемую скорость движения по сегменту в течение повторяющегося периода времени и заданное условие, когда момент времени движения по сегменту существенно отличается от момента времени движения согласно профилю нормальной скорости, причем способ содержит этапы, на которых:
i. принимают запрос на определение доступного для навигации маршрута,
ii. идентифицируют, удовлетворяется ли заданное условие в момент времени движения, и, если условие удовлетворяется, определяют маршрут, используя, по меньшей мере, один другой профиль скорости, в противном случае, определяют маршрут, используя скорость движения по этому сегменту согласно профилю нормальной скорости для еженедельного периода времени, соответствующего моменту времени движения.
Таким образом, способ использует профиль скорости, который может быть подходящим для условий в момент времени движения. Например, заданным условием может быть заданная дата; время и дата; время и/или дата и местоположение; условие движения транспорта или погодные условия.
Другим профилем скорости может быть профиль нормальной скорости для сегмента для еженедельного периода времени, который не соответствует моменту времени движения. Например, если заданным условием является то, что моментом времени движения является национальный праздник, другим профилем скорости, используемым для определения маршрута, может быть профиль нормальной скорости для субботы или воскресенья, а не профиль рабочего дня, который использовался бы обычно.
Картографические данные могут содержать профиль анормальной скорости, содержащий скорость движения по сегментам в момент времени заданного условия, и другим профилем скорости может быть профиль анормальной скорости. Использование специальных профилей скорости для заданного условия может приводить к более точному предсказанию скоростей в течение моментов времени нетипичного характера движения транспорта.
В одном варианте осуществления способ содержит получение данных о зоне влияния и заданном условии, таком как событие, условие движения транспорта или погодное условие, и определение маршрута, используя, по меньшей мере, один из профилей анормальной скорости для сегментов, которые находятся в зоне влияния, и используя, по меньшей мере, один из профилей нормальной скорости для сегментов вне зоны влияния. Таким образом, способ может определить маршрут с учетом событий, которые имеют только местное влияние на скорость движения по сегменту. Например, зоной влияния может быть зона, которая подвергается сильному снегопаду или проливному дождю, или зона, на которую оказывает влияние дорожно-транспортное происшествие.
Поэтому, способ может содержать прием данных об условиях, таких как события, движение транспорта и погода.
В одном варианте осуществления способ может содержать прием данных о местоположении дорожно-транспортного происшествия или другого события и определение зоны влияния посредством идентификации сегментов в пределах заранее определенного расстояния от происшествия или другого события, например, в пределах 50 или 100 км.
В дополнение или альтернативно, способ может содержать определение, удовлетворяется ли заданное условие из календаря. Например, календарь может идентифицировать, когда происходят заданные условия, такие как национальные праздники и фестивали.
Момент времени движения может определяться из момента времени, когда принимается запрос на определение маршрута, или из момента времени, заданного в запросе для определения маршрута.
Согласно восьмому аспекту изобретения предоставляется навигационное устройство, выполненное с возможностью определения маршрута по всей зоне, содержащее память, имеющую хранящиеся в ней картографические данные, содержащие множество доступных для навигации сегментов, представляющих сегменты доступного для навигации маршрута в зоне, покрываемой картографическими данными, по меньшей мере, один из доступных для навигации сегментов имеет ассоциированный с ним профиль нормальной скорости для еженедельно повторяющегося периода времени, содержащий ожидаемую скорость движения по сегменту в течение повторяющегося периода времени и заданное условие, когда момент времени движения по сегменту существенно отличается от момента времени движения согласно соответствующему профилю нормальной скорости, ввод для приема запроса на определение доступного для навигации маршрута, вычислитель маршрута, выполненный с возможностью идентификации, удовлетворяется ли заданное условие в момент времени движения, и, если условие удовлетворяется, определения маршрута, используя, по меньшей мере, один другой профиль скорости, в противном случае, определения маршрута, используя скорость движения по этому сегменту согласно профилю нормальной скорости для еженедельного периода времени, соответствующего моменту времени движения.
Навигационное устройство может содержать приемник для приема данных о текущих условиях, таких как условие движения транспорта и погодные условия и события, в момент времени движения.
Память может иметь хранящийся в ней календарь, идентифицирующий, когда происходят заданные условия, такие как национальные праздники и фестивали.
Согласно девятому аспекту изобретения предоставляется машиносчитываемая среда, содержащая в себе инструкции, которые, когда они считываются процессором навигационного устройства, вызывают выполнение навигационным устройством в соответствии с десятым аспектом изобретения.
В данном документе ссылка делается на данные о скорости, ассоциированные с сегментом дороги. Специалист в данной области техники оценит по достоинству, что каждый сегмент дороги представлен данными в картографических данных, обеспечивающих карту. В некоторых вариантах осуществления такие данные, представляющие сегмент дороги, могут включать в себя идентификатор, который предоставляет ссылку на данные о скорости. Например, ссылка может предоставлять ссылку на сгенерированный профиль скорости. Эта ссылка может предусматриваться в виде справочной таблицы.
В любом из вышеупомянутых аспектов изобретения машиносчитываемая среда может содержать любое из нижеследующего: дискету, компакт-диск (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 показывает блок-схему последовательности операций способа, описывающую то, как ассоциируются сгенерированные из кластеров профили скорости с сегментами дороги, по меньшей мере, одной карты;
фиг.13 показывает блок-схему последовательности операций способа, описывающую то, как генерируются профили анормальной скорости для моментов времени в случае нетипичного характера движения транспорта; и
фиг.14 показывает блок-схему последовательности операций способа, описывающую то, как работает навигационное устройство при использовании профилей анормальной скорости для моментов времени в случае нетипичного характера движения транспорта.
Подробное описание варианта осуществления изобретения
В нижеследующем описании идентичные ссылочные позиции используются для идентификации подобных деталей.
Ниже описываются варианты осуществления настоящего изобретения с конкретной ссылкой на портативное навигационное устройство (PND). Необходимо помнить, однако, что идеи настоящего изобретения не ограничиваются PND, но, вместо этого, универсально применимы к любому типу устройства обработки, которое сконфигурировано для исполнения навигационного программного обеспечения, портативного типа, чтобы обеспечивать функциональную возможность планирования маршрута и навигации. Из этого, поэтому, следует, что в контексте настоящего применения, как предполагается, навигационное устройство включает в себя (без ограничения) любой тип устройства планирования маршрута и навигации, независимо от того, воплощено ли это устройство в виде PND, транспортное средство, такое как автомобиль, или, даже, портативный вычислительный ресурс, например, портативный персональный компьютер (PC), мобильный телефон или персональный цифровой помощник (PDA), исполняющий программное обеспечение планирования маршрута и навигации.
Далее, варианты осуществления настоящего изобретения описываются со ссылкой на сегменты дороги. Необходимо понять, что изобретение также может быть применимо к другим доступным для навигации сегментам, таким как сегменты пути, реки, канала, циклического пути, бечевника, железнодорожной линии или т.п. Для удобства ссылки они обычно упоминаются как сегмент дороги.
Из нижеследующего также очевидно, что идеи настоящего изобретения имеют применение даже в обстоятельствах, когда пользователь не ищет инструкций, как выполнить навигацию из одной точки в другую, но просто желает, чтобы был предоставлен вид данного местоположения. В таких обстоятельствах местоположению «пункта назначения», выбранному пользователем, не нужно иметь соответствующее начальное местоположение, из которого пользователь желает начать навигацию, и, следовательно, ссылки в данном документе на местоположение «пункта назначения» или даже на вид «пункта назначения» не должны интерпретироваться как означающие, что генерирование маршрута является существенным, что должно произойти движение к «пункту назначения», или, даже, что присутствие пункта назначения требует обозначение соответствующего начального местоположения.
С учетом вышеупомянутых условий, глобальная система позиционирования (GPS) на фиг.1 и т.п. используются для многочисленных целей. Как правило, GPS является навигационной системой на базе спутниковых радиостанций, способной определять непрерывную информацию о положении, скорости, времени и, в некоторых случаях, направлении для неограниченного количества пользователей. Ранее известная как NAVSTAR, GPS включает в себя множество спутников, которые двигаются вокруг Земли по очень точным орбитам. Основываясь на этих точных орбитах, GPS-спутники могут ретранслировать свое местоположение, в качестве GPS-данных, любому количеству приемных блоков. Однако понятно, что могут использоваться глобальные системы позиционирования, такие как ГЛОНАСС, европейская система позиционирования Galileo, система позиционирования COMPASS или IRNSS (индийская региональная навигационная спутниковая система).
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 связи включает в себя, но не ограничивается ими, одно или комбинацию из нижеследующих: электрические схемы, электрические проводники, такие как провода и коаксиальные кабели, волоконно-оптические кабели, преобразователи, радиочастотные (РЧ) волны, атмосфера, свободное пространство и т.д. Кроме того, канал 152 связи может включать в себя промежуточные устройства, такие как, например, маршрутизаторы, повторители, буферы, передатчики и приемники.
В одной иллюстративной конструкции, канал 152 связи включает в себя телефонные и компьютерные сети. Кроме того, канал 152 связи может быть способен обеспечивать беспроводную связь, например, инфракрасную связь, радиочастотную связь, такую как микроволновую связь, и т.д. Кроме того, канал 152 связи может обеспечивать спутниковую связь.
Сигналы связи, передаваемые по каналу 152 связи, включают в себя, но не ограничиваются ими, сигналы, которые могут потребоваться или которые могут быть необходимы для данной технологии связи. Например, сигналы могут быть адаптированы для использования в технологии сотовой связи, такой как многостанционный доступ с временным разделением каналов (TDMA), многостанционный доступ с частотным разделением каналов (FDMA), многостанционный доступ с кодовым разделением каналов (CDMA), глобальная система мобильной связи (GSM), общая служба пакетной радиопередачи (GPRS) и т.д. Как цифровые, так и аналоговые сигналы могут передаваться по каналу 152 связи. Этими сигналами могут быть модулированные, зашифрованные и/или сжатые сигналы, как может требоваться для технологии связи.
Сервер 150 включает в себя, в дополнение к другим компонентам, которые могут быть не показаны, процессор 154, соединенный с возможностью работы с памятью 156 и дополнительно соединенный с возможностью работы через проводное или беспроводное соединения 158 с массовым запоминающим устройством 160. Массовое запоминающее устройство 160 содержит в себе хранилище навигационных данных и картографической информации и снова может представлять собой устройство, отдельное от сервера 150, или может быть встроено в сервер 150. Процессор 154 дополнительно соединен с возможностью работы с передатчиком 162 и приемником 164 для передачи и приема информации от навигационного устройства 200 и на него по каналу 152 связи. Посылаемые и принимаемые сигналы могут включать в себя данные, связь и/или другие распространяемые сигналы. Передатчик 162 и приемник 164 могут выбираться или разрабатываться согласно требованию к связи и технологии связи, используемой в коммуникационном дизайне для навигационной системы 200. Кроме того, необходимо отметить, что функции передатчика 162 и приемника 164 могут быть объединены в единственный приемопередатчик.
Как упомянуто выше, навигационное устройство 200 может быть выполнено с возможностью связи с сервером 150 по каналу 152 связи, используя передатчик 166 и приемник 168 для посылки и приема сигналов и/или данных по каналу 152 связи, отмечая, что эти устройства дополнительно могут использоваться для связи с устройствами за исключением сервера 150. Кроме того, передатчик 166 и приемник 168 могут выбираться или разрабатываться согласно требованиям к связи и технологии связи, используемой в коммуникационном дизайне для навигационного устройства 200, и функции передатчика 166 и приемника 168 могут быть объединены в единственном приемопередатчике, как описано выше в отношении фиг.2. Конечно, навигационное устройство 200 содержит другие аппаратные и/или функциональные детали, которые более подробно описаны ниже в данном документе.
Программное обеспечение, хранящееся в памяти 156 сервера, обеспечивает инструкции для процессора 154 и позволяет серверу 150 предоставлять услуги навигационному устройству 200. Одна услуга, предоставляемая сервером 150, включает в себя обработку запросов от навигационного устройства 200 и передачу навигационных данных от массового запоминающего устройства 160 на навигационное устройство 200. Другой услугой, которая может предоставляться сервером 150, включает в себя обработку навигационных данных, используя различные алгоритмы для требуемого применения, и посылку результатов этих вычислений на навигационное устройство 200.
Сервер 150 составляет удаленный источник данных, доступный навигационным устройством 200 через беспроводной канал. Сервер 150 может включать в себя сетевой сервер, расположенный в локальной сети (LAN), глобальной сети (WAN), виртуальной частной сети (VPN) и т.д.
Сервер 150 может включать в себя персональный компьютер, такой как настольный или портативный компьютер, и канал 152 связи может быть кабелем, подсоединенным между персональным компьютером и навигационным устройством 200. Альтернативно, персональный компьютер может быть подсоединен между навигационным устройством 200 и сервером 150 для установления Интернет-соединения между сервером 150 и навигационным устройством 200.
Навигационное устройство 200 может снабжаться информацией от сервера 150 посредством выгрузок информации, которые могут обновляться автоматически, время от времени или при соединении пользователем навигационного устройства 200 с сервером 150 и/или могут быть более динамичными при более постоянном или частом соединении, выполняемым между сервером 150 и навигационным устройством 200 при помощи, например, устройства беспроводного мобильного соединения и соединения TCP/IP. Для многих динамичных вычислений процессор 154 в сервере 150 может использоваться для обработки большой части потребностей обработки, однако, процессор (не показанный на фиг.2) навигационного устройства 200 также может обрабатывать большую часть обработки и вычислений, часто независимо от соединения с сервером 150.
Как показано на фиг.3, необходимо заметить, что блок-схема навигационного устройства 200 не включает все компоненты навигационного устройства, но только представляющие многие примерные компоненты. Навигационное устройство 200 располагается в корпусе (не показан). Навигационное устройство 200 включает в себя схему обработки, содержащую, например, процессор 202, упомянутый выше, причем процессор 202 связан с устройством 204 ввода и устройством отображения, например, экраном 206 отображения. Хотя в данном случае ссылка делается на устройство 204 ввода в единственном числе, специалист в данной области техники должен понимать, что устройство 204 ввода представляет любое количество устройств ввода, включая устройство клавиатуры, устройство речевого ввода, сенсорную панель и/или любое другое известное устройство ввода, используемое для ввода информации. Аналогично, экран 206 отображения может включать в себя любой тип экрана отображения, такой как, например, жидкокристаллический дисплей (LCD).
В одной конструкции, один аспект устройства 204 ввода, сенсорная панель, и экран 206 отображения интегрируются так, чтобы обеспечить интегрированное устройство ввода и отображения, включающее в себя ввод 250 (фиг.4) с сенсорной панели или сенсорного экрана, позволяющее как вводить информацию (посредством непосредственного ввода, выбора меню и т.д.), так отображать информацию посредством экрана с сенсорной панелью, так что пользователю необходимо только прикоснуться к части экрана 206 отображения для выбора одного из множества вариантов выбора отображения или приведения в действие одной из множества виртуальных или «экранных» кнопок. В этом отношении, процессор 202 поддерживает графический пользовательский интерфейс (GUI), который работает совместно с сенсорным экраном.
В навигационном устройстве 200 процессор 202 соединен с возможностью работы с и способен принимать вводимую информацию с устройства 204 ввода посредством соединения 210, и соединен с возможностью работы, по меньшей мере, с одним из экрана 206 отображения и устройства 208 вывода, по соответствующим соединениям 212 вывода, для вывода на него информации. Навигационное устройство 200 может включать в себя устройство 208 вывода, например, устройство звукового вывода (например, громкоговоритель). Так как устройство 208 вывода может создавать звуковую информацию для пользователя навигационного устройства 200, необходимо в равной степени понять, что устройство 204 ввода может включать в себя также микрофон и программное обеспечение для приема команд ввода голосом. Кроме того, навигационное устройство 200 также может включать в себя любое дополнительное устройство 204 ввода и/или любое дополнительное устройство вывода, такие как, например, устройства ввода/вывода звука.
Процессор 202 соединен с возможностью работы с памятью 214 через соединение 216 и дополнительно выполнен с возможностью приема/посылки информации от/на порты 218 ввода/вывода (I/O) через соединение 220, причем порт 218 I/O может соединяться с устройством 222 I/O, внешним для навигационного устройства 200. Внешнее устройство 222 I/O может включать в себя, но не ограничивается внешним устройством прослушивания, таким как наушник, например. Соединение с устройством 222 I/O дополнительно может быть проводным или беспроводным соединение с любым другим внешним устройством, таким как автомобильный стереофонический блок, для громкой связи и/или для операции управления голосом, например, для соединения с наушником или головным телефоном, и/или для соединения с мобильным телефоном, например, причем соединение с мобильным телефоном может использоваться для установления соединения передачи данных между навигационным устройством 200 и Интернетом или любой другой сетью, например, и/или, например, для установления соединения с сервером через Интернет или некоторую другую сеть.
Память 214 навигационного устройства 200 содержит часть энергонезависимой памяти (например, для хранения программного кода) и часть энергозависимой памяти (например, для хранения данных, когда исполняется программный код). Навигационное устройство также содержит порт 228, который осуществляет связь с процессором 202 через соединение 230, позволяя подсоединять к устройству 200 съемную карточку памяти (обычно упоминаемую как карточка). В описываемом варианте осуществления порт выполнен с возможностью подсоединения карточки SD (формат Secure Digital). В других вариантах осуществления порт может допускать подключение других форматов памяти (таких как карточки CompactFlash (CF), MemoryStick™, карточки памяти xD, флэш-накопителей с универсальной последовательной шиной (USB), карточки MMC (MultiMedia), карточки SmartMedia, Microdrive (микродрайв) или т.п.).
Фиг.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 может быть выполнен с возможностью загрузки записи на сервер 152, когда создается канал 152 связи. Это может быть, например, тогда, когда навигационное устройство 200 соединяется с пользовательским компьютером. Снова, в некоторых вариантах осуществления навигационное устройство может быть выполнено с возможностью буферизации GPS привязок в памяти 214 или на карточке, вставленной в порт 228. Если память 214 или карточка, вставленная в порт 228, становятся полными GPS привязками, навигационное устройство может быть выполнено с возможностью удаления самых старых GPS привязок и, по существу, он может рассматриваться как буфер обратного магазинного типа (FIFO).
В описываемом варианте осуществления запись местонахождений содержит одну или более траекторий, причем каждая траектория представляет движение этого навигационного устройства 200 в течение 24-часового периода. Каждые 24 часа предназначены для совпадения с календарным днем, но в других вариантах осуществления нет необходимости, чтобы было так.
Как правило, пользователь навигационного устройства 200 дает свое согласие на то, чтобы запись местонахождений устройств загружалась на сервер 150. Если согласие не дано, тогда запись не загружается на сервер 150. Само навигационное устройство и/или компьютер, к которому подсоединено навигационное устройство, могут быть выполнены с возможностью запроса у пользователя его согласия на такое использование записи местонахождений.
Сервер 150 выполнен с возможностью приема записи местонахождений устройства и хранения ее на массовом запоминающем устройстве 160 для обработки. Таким образом, когда проходит время, массовое запоминающее устройство 160 накапливает множество записей местонахождений навигационного устройства 200, которые имеют загруженные данные.
Как описано выше, массовое запоминающее устройство 160 также содержит в себе картографические данные. Такие картографические данные обеспечивают информацию о местонахождении сегментов дороги, точек интереса и другую такую информацию, которая, как правило, обнаруживается на карте.
В качестве первого процесса, сервер 150 выполнен с возможностью выполнения функции сопоставления карт между картографическими данными и GPS привязками, содержащимися в записях местонахождений, которые были приняты, и такой процесс описывается в связи с фиг.6. Такое сопоставление карт может выполняться в так называемом реальном времени; т.е. когда принимаются записи местонахождений, или может выполняться в более поздний момент времени, после того как записи местонахождений будут вызваны из массового запоминающего устройства 160.
Чтобы увеличить точность сопоставления карт, предварительная обработка записей местонахождений выполняется следующим образом. Каждая GPS-траектория (т.е. 24-часовой период GPS-данных) делится 600 на один или более переходов, причем каждый переход представляет одну поездку навигационного устройства 200, которая потом хранится для последующей обработки.
На каждом переходе отклоняются 602 GPS привязки, отчет которых о точности, принимаемый от навигационного устройства, не является достаточно высоким. Таким образом, в некоторых вариантах осуществления привязка может отклоняться, если отчет о точности указывает, что сигналы от менее чем трех спутников 102 принимались навигационным устройством 200 относительно этой GPS привязки. Далее, выполняется усечение 604 каждого перехода, когда сообщенное время между привязками превышает пороговое значение. Каждый переход, который проходит этот этап предварительной обработки, является прошедшей сопоставление карт.
В данном контексте усеченный переход является переходом, в котором существует заранее определенный период времени между последовательными GPS привязками, который больше заранее определенного времени. По существу, можно сделать вывод, что транспортное средство оставалось неподвижным, и, по существу, необходимо рассматривать, что первый переход закончился, и начался второй переход. Таким образом, усеченный переход становится двумя отдельными переходами.
Однако, перед тем как переход будет разделен, выполняется проверка, изменилось ли положение транспортного средства между последними двумя привязками, так как промежуток свыше заранее определенного времени между GPS привязками также может происходить вследствие потери GPS-сигнала и, при таких обстоятельствах, переход не делится. В описываемом варианте осуществления заранее определенным временем является приблизительно 3 минуты. Однако специалист в данной области техники оценит, что промежутком может быть любое другое подходящее время, такое как приблизительно любое из последующих: 15 секунд, 30 секунд, 1 минута, 90 секунд, 2 минуты, 5 минут, 10 минут или любое время между этими значениями. Как описано ниже в данном документе, если средняя скорость навигационного устройства 200, с которого посылаются GPS привязки, ниже заранее определенного порога, тогда данные в некоторых вариантах осуществления могут отклоняться при последующей обработке. Такой вариант осуществления может быть полезен в том, что он может удалять данные, относящиеся к движению транспорта с частыми остановками, которое имеет место после происшествий, таких как авария или т.п., который может оставлять остальные данные, которые лучше представляют поток движения транспорта установившегося состояния.
Тогда каждый переход берется по очереди, и привязки в этом переходе сопоставляются с картой из картографических данных. Каждая карта содержит множество сегментов дороги, вдоль которых можно двигаться, причем каждый сегмент представлен в карте как прямолинейный вектор.
Программный код, выполняющийся на процессоре 154 сервера 150, обеспечивает обнаружитель совпадений карт, который выполнен с возможностью перешагивания через привязку или каждую привязку в переходе, который обрабатывается, до тех пор, пока он не обнаружит привязку, которая лежит в пределах сегмента или достаточно близко к сегменту, чтобы предположить, что он имел место на этом сегменте (т.е. он находится в пределах порога расстояния сегмента). Этот порог предусматривает меньшую чем 100% точность GPS и эффект сжатия разбиения дороги на набор прямолинейных векторов.
Каждый переход имеет начальную привязку (т.е. первую привязку на переходе), которую труднее ассоциировать с сегментом, чем другие привязки на переходе, так как нет сегментов, которые уже идентифицированы, которые могут быть использованы для ограничения выбора сегментов. Если для этой первой привязки, многочисленные сегменты находятся в пределах порога 606, тогда алгоритм рассматривает следующую GPS привязку (т.е. вторую привязку) на переходе и генерирует набор корней от этих многочисленных сегментов, основываясь на возможном движении как функции расстояния между 2 привязками (т.е. между 1-ой и 2-ой привязками). Если 2-ая привязка не приводит к уникальному потенциальному сегменту для 1-ой привязки, тогда алгоритм перемещается к 3-ей привязке на переходе и снова генерирует и сравнивает возможные маршруты, чтобы попытаться обеспечить уникальный вариант для первой привязки 608. Этот процесс может продолжаться до тех пор, пока не будут обработаны остальные GPS привязки на переходе.
Преимущество такого варианта осуществления заключается в том, что, хотя любая одна первая привязка изолировано может быть около многочисленных сегментов, и эти сегменты изолировано не могут различаться между собой, становится возможным использовать дальнейшее движение (т.е. 2-ую и 3-ью привязки) для определения идентификации сегмента, с которым ассоциируется первая привязка. Таким образом, первый сегмент для перехода определяется обнаружителем совпадений карт.
Если первый сегмент был идентифицирован для перехода, дальнейшие привязки обрабатываются, чтобы идентифицировать дальнейшие сегменты. Конечно, возможно, что следующая привязкаперехода лежит в этом же сегменте, что и первая привязка 612.
Таким образом, последующие привязки перехода обрабатываются 610 для определения, находятся ли они в пределах порога расстояния сегмента, и обнаружитель совпадений карт выполнен с возможностью ассоциирования этого сегмента с каждой из привязок, которые лежат в пределах порога расстояния. Когда обнаружитель совпадений карт обрабатывает привязку, которая находится вне порога расстояния, он выполнен с возможностью генерирования нового набора потенциальных сегментов для этой привязки. Однако теперь возможно добавить дополнительное ограничение, что следующий сегмент является сегментом, который соединен с концом сегмента, который только что был обработан. Эти соседние сегменты получаются обнаружителем совпадений карт из лежащих в основе картографических данных.
Если в любой точке обнаружитель совпадений карт не идентифицирует сегмент для данной привязки, которая является продолжением предыдущего сегмента, или потому что нет сегментов в пределах порога, или нельзя уникально идентифицировать отдельный сегмент, тогда обнаружитель совпадений карт выполнен с возможностью перешагивания через последующие привязки 616, чтобы дополнительно ограничить поездку до тех пор, пока он не сможет идентифицировать сегмент, который является уникальным совпадением. Т.е., если n-ая привязка не может уникально ассоциироваться с сегментом, n+1-ый сегмент используется для дополнительного ограничения идентификации сегмента. Если n+1-ая привязка не создает уникальный сегмент, тогда используется n+2-ая привязка. В некоторых вариантах осуществления этот процесс может выполняться до тех пор, пока не будет идентифицирован уникальный сегмент, или не будут обработаны все GPS привязки на переходе.
Обнаружитель совпадений карт выполнен с возможностью подбора и однозначной идентификации сегментов; в описываемом варианте осуществления он не пытается создать непрерывный маршрут, только подбирает и сопоставляет сегменты с привязками. В других вариантах осуществления может быть желательным попытка генерирования обнаружителем совпадений карт непрерывных маршрутов.
Поэтому, в конце процесса, который обнаружитель совпадений карт выполнен с возможностью выполнять, получается последовательность сегментов дороги, по которым навигационное устройство 200 передвигалось на анализируемом переходе. Потом обнаружитель совпадений карт дополнительно обрабатывает эти сегменты дороги и присваивает из GPS привязок время входа и также время прохождения для этого сегмента. Эти присвоенные времена храняться в массовом запоминающем устройстве 160 для последующей обработки. Вполне может быть так, что множество GPS привязок хранятся для каждого сегмента дороги. Однако независимо от того, сколько GPS привязок ассоциируются с каждым сегментом, время входа, GPS привязки и длина сегмента (которая в данном варианте осуществления храниться в картографических данных) используются для вычисления средней скорости для этого сегмента дороги. Эта средняя скорость затем хранится в массовом запоминающем устройстве 160, ассоциированная с относящимися присвоенными временами и этим сегментом. Информация, относящаяся к скорости потока движения транспорта на сегменте дороги и присвоенная сегменту дороги, может рассматриваться как представляющая собой данные о скорости для этого сегмента дороги.
Сервер 150 дополнительно выполнен с возможностью выполнения усредняющего программного кода на процессоре 154 для обеспечения усреднителя, который обрабатывает присвоенные времена для генерирования из них одного или более средних значений, как описано ниже. Процесс усреднения, используемый в данном варианте осуществления, ниже описывается относительно фиг.7.
На первом этапе процесса 700 усреднитель группирует средние скорости для каждого сегмента дороги на обрабатываемой карте. В группировании для каждого сегмента дороги усреднитель дополнительно выполнен с возможностью группирования средних скоростей в набор заранее определенных периодов 702 времени. Таким образом, средние скорости, которые имеют место в одном и том же периоде времени (например, между 8.00 до полудня и 8.59 до полудня) группируются вместе для дальнейшего анализа. В описываемом варианте осуществления длительность периодов времени составляет один час, но в этом нет необходимости, и специалист в данной области техники оценит из нижеследующего описания, что, когда длительность периода времени уменьшается, разрешение данных увеличивается, но увеличиваются требования к емкости памяти. Другими подходящими периодами времени, по существу, могут быть любые из следующих: 1 минута, 5 минут, 10 минут, 15 минут, 30 минут, 2 часа, 6 часов, 12 часов или любое время между этими значениями времени.
В описываемом варианте осуществления средние скорости хранятся во времени, местном для зоны, покрываемой обрабатываемой картой, а не в централизованном времени. Такой способ удобен, так как он обеспечивает естественную основу для относящихся к движению транспорта вопросов.
Перед тем как средняя скорость, сгенерированная на переходе, будет сгруппирована в заранее определенный период времени, она отбирается с целью повышения качества данных. В данном варианте осуществления средняя скорость добавляется к группе только в течение заранее определенного периода, если средняя скорость попадает в заранее определенный диапазон. В данном варианте осуществления способ исключает скорости, которые превышают максимальный заранее определенный порог (который может составлять приблизительно 180 км/ч), и, дополнительно, способ исключает скорости, которые ниже заранее определенной величины средней скорости для этого сегмента в этом заранее определенном периоде времени (которая может составлять, например, 2 км/ч). Специалист в данной области техники оценит, что скорости, которые значительно ниже средней скорости для этого сегмента при этом времени, могут вполне ассоциироваться с проблемой в потоке движения транспорта для этого сегмента, такой как затор в движении транспорта или т.п. Таким образом, включение данных, относящихся к таким условиям, может понизить общую точность данных при рассмотрении дороги в нормальных условиях. В других вариантах осуществления максимально разрешенная скорость может быть установлена в качестве предела скорости для этого сегмента дороги, но специалист в данной области техники оценит, что такая информация может быть неточной в картографических данных, которые обрабатываются, и также то, что предел скорости для сегмента дороги, фактически, может не давать точное указание об условии движения транспорта.
Если группирование в заранее определенные периоды времени было выполнено, вычисляется средняя скорость для каждого сегмента дороги для каждого заранее определенного периода времени. Например, усредняются все из скоростей в пределах периода времени 8.00 до полудня - 8.59 до полудня для каждого сегмента дороги. Существует несколько вариантов для вычисления средней скорости: использование простого арифметического или гармонического среднего или вычисление медианы. Действительно, в некоторых вариантах осуществления различные весовые коэффициенты могут использоваться для наборов данных согласно более поздним предполагаемым использованием данных.
Таким образом, в описываемом варианте осуществления и для обрабатываемой карты генерируется для каждого сегмента дороги на карте 24 средние скорости: средняя скорость для каждого заранее определенного периода времени длительностью один час. Понятно, что, если используется другая длительность периода времени, тогда будет другое количество средних скоростей. Также понятно, что, фактически, не все сегменты дороги обязательно имеют среднюю скорость, присвоенную им для каждого периода времени, так как проезд по некоторым дорогам может быть нечастый, особенно в «неудобное» время, такое как ранние утренние часы.
Однако перед последующим использованием средних скоростей на сегмент выполняются 706 проверки качества. В данном варианте осуществления эта проверка гарантирует, что использовалось больше заранее определенного количества присвоенных моментов времени для генерирования средней скорости на сегмент. Если это не так, тогда эта средняя скорость на сегмент отклоняется для дополнительной обработки, оставляя промежуток для этого сегмента с одним или более периодами времени. В некоторых вариантах осуществления среднее отклоняется, если имеется менее 5 значений, которые использовались при составлении этого среднего. Другие варианты осуществления, конечно, могут использовать другие значения, такие как 2, 3, 4, 6, 7, 8, 10, 20 или более или любое значение между ними.
Также, выполняется дополнительная проверка качества среднего, и для каждого среднего среднеквадратическое отклонение среднего делится на квадратный корень из количества отсчетов данных, которые использовались при составлении среднего для этого сегмента для этого периода времени. Если результат этого вычисления выходит за заранее определенный порог, тогда это среднее снова отклоняется, оставляя промежуток для этого сегмента для этого периода времени.
Могут быть реализованы другие проверки качества для отклонения средних по любому из следующего: находится ли отклонение в данных за пределами заранее определенного порога; существование более чем заранее определенного количества выбросов сверх заранее определенного порога. Специалист в данной области техники оценит такие статистические методы для гарантирования качества данных.
Набор средних для любого данного сегмента дороги может рассматриваться как профиль измеренной скорости для этого сегмента дороги.
Специалист в данной области техники оценит, что, если профиль измеренной скорости для сегмента дороги имеет несколько отсутствующих значений скорости (т.е. все или, по меньшей мере, большинство заранее определенных периодов времени имеют значение), тогда этот сегмент может обрабатываться, и отсутствующие значения, поэтому, маскируются. Когда количество отсутствующих сегментов увеличивается, тогда снижается качество результирующего кластерного анализа. Таким образом, сколько допустимо отсутствующих периодов времени представляет собой вопрос принятия решения о качестве и должно исследоваться от случая к случаю. Использование только высококачественных полных данных может иметь следствием слишком большой весовой коэффициент для сегментов дороги с высоким покрытием (т.е. с несколькими отсутствующими периодами времени), которые обычно содержат автострады, автомагистрали и другие дороги, по которым движутся многие люди. Слишком низкое требование (т.е. кластеризация сегментов дороги, которые имеют слишком много отсутствующих периодов времени) приводит к нереалистичным кластерам и неточному анализу.
Каждое среднее, которое проходит эти проверки на качество, рассматривается достоверным и одобряется для использования в дальнейшей обработке. На этапе 708 выполняется оценка в отношении полного покрытия средних скоростей на сегмент дороги. Если покрытие достоверными средними достаточно большое, тогда картографические данные направляются для дальнейшей обработки. Однако, если покрытие ниже заранее определенного порога, тогда карта отклоняется от дальнейшего рассмотрения 710. Допустимые карты проходят для формирования кластеров, как описано в отношении фиг.8.
Такое формирование кластеров имеет целью извлечение регулярных профилей скорости для периодов времени, таких как дни, которые повторяются еженедельно, автоматическим или полуавтоматическим образом; как описано ниже, сжатие данных, которое может быть существенным, может достигаться, если предполагается, что дороги подобного класса могут иметь подобный профиль скорости. Например, скорость каждую неделю в 10 часов до полудня утром в воскресенье для первого сегмента дороги может быть подобна скорости в это же время для второго сегмента дороги. Если это подобие для этих сегментов дороги повторяется для других моментов времени, тогда профиль скорости для первого и второго сегментов может рассматриваться представленным одним и тем же профилем скорости второго сегмента. Кластеризация, определенная теперь, имеет целью определение положения таких подобий. Нормализация профилей скорости, как описано ниже, также может позволять использовать профиль скорости для дорог другого класса.
Перед выполнением кластеризации профиль измеренной скорости дополнительно обрабатывается для объединения ночных периодов времени. В данном варианте осуществления усредняются средние скорости между 9 часами после полудня и 5 часами до полудня (т.е. 8 периодов времени), и это ночное среднее используется для каждого из 8 периодов времени. Таким образом, каждый профиль скорости имеет плоский профиль скорости между 9 часами после полудня и 8 часами до полудня, который может называться скоростью свободного потока этого сегмента дороги. Можно предположить, что скорость свободного потока представляет скорость, с которой транспортное средство, обычно автомобиль, движется по дороге, и часто так, что скорость свободного потока отличается от предела скорости для этого сегмента дороги. Скорость свободного потока также может быть приблизительно равна такой же, что и предел скорости для этого сегмента дороги.
На первом этапе 800 и, чтобы ограничить количество кластеров, нормализуются профили измеренной скорости. Такая нормализация может выполняться согласно нескольким критериям. В описываемом варианте осуществления нормализация происходит согласно скорости свободного потока, которая была вычислена для сегмента дороги, с которым ассоциируется среднее. По существу, средняя скорость на сегмент дороги, которая прошла алгоритм кластеризации, имеет значение между 0 и 1. Такой способ может способствовать дополнительному сжатию данных, так как он может сделать результирующий профиль скорости, сгенерированный из кластеров, независимым от типа дороги, и, по существу, становится возможным использовать этот же набор профилей скорости для сегментов дороги, имеющих любой тип дороги.
Использование скоростей свободного потока в течение ночного периода времени может снизить размерность формирования кластеров, так как может быть возможным игнорировать значения скорости ночного времени.
В еще других вариантах осуществления средняя скорость или предел скорости сегмента дороги может использоваться в качестве дополнительного критерия, по сравнению с которым выполнять нормализацию.
Таким образом, дни, показывающие подобный характер движения транспорта, могут быть сгруппированы вместе посредством обработки по алгоритму кластеризации. Если отличается ожидаемый движения транспорта, формирование кластеров должно выполняться независимо. Входным параметром для алгоритма кластеризации является количество требуемых кластеров, и типовой диапазон составляет 10-70 для дня недели. Имеются известные способы приближения к оптимальному количеству кластеров (например, присваивание некоторых мер качества и увеличение/уменьшение количества кластеров в соответствии с их тенденцией), которые могут использоваться для определения, является ли допустимым результат кластеризации.
В одном варианте осуществления алгоритм кластеризации выполняется и предназначается для генерирования примерно 60 кластеров. В других вариантах осуществления алгоритм может быть предназначен для первоначального генерирования большего или меньшего количества кластеров. Результирующие кластеры затем обрабатываются для определения, являются ли сгенерированные кластеры удовлетворительными: являются ли некоторые кластеры слишком подобными (т.е., по существу, одинаковыми)? Имеют ли любые из кластеров отсутствие непрерывности в них? Если есть проблемы с любым из кластеров, тогда алгоритм выполняется снова, при этом целью процесса является генерирование меньшего количества кластеров, чем при первой итерации. Этот итеративный процесс повторяется до тех пор, пока не будет определен удовлетворительный набор кластеров.
В некоторых вариантах осуществления, являются ли кластеры удовлетворительными включает в себя этап определения, содержит в себе или нет любой из сгенерированных из кластеров профилей частоты выше заранее определенного порога. Присутствие таких частот указывает, что сгенерированный из кластеров профиль скорости имеет скорость изменения, которая слишком высокая (т.е. может быть отсутствие непрерывности), и, если используется, может приводить к нестабильности и т.д. в навигационном устройстве 200, использующем эти данные для генерирования маршрута.
Являются ли или нет кластеры удовлетворительными также может включать в себя этап выполнения сравнения между, по меньшей мере, некоторыми, и, как правило, каждым из сгенерированных из кластеров профилей скорости. В одном конкретном варианте осуществления это может выполняться посредством сравнения методом наименьших квадратов.
В одном варианте осуществления кластер выполняется посредством кластерного анализа, но также могут использоваться другие способы построения классов. Простым и эффективным подходом является так называемый алгоритм кластеризации k средних. Этот неиерархический способ обычно начинается с k случайных затравок и перераспределяет члены класса в соответствии с критерием минимальной ошибки, основанным на выбранной метрике. Алгоритм приводит только к локальным минимумам, поэтому, для оптимального решения он должен выполняться много раз. Выполнение с оценками минимальной ошибки дает то, что может быть предпочтительным решением. Центроиды окончательных кластеров образуют предварительно определенные кластеры. В некоторых вариантах осуществления могут использоваться другие методы кластеризации, и они включают в себя иерархическую кластеризацию и нечеткую кластеризацию.
Некоторые варианты осуществления могут добавлять дополнительные кластеры 804. Например, некоторые варианты осуществления могут добавлять плоскую линию в качестве профиля скорости для сегментов дороги, которые не имеют достоверной тенденции, например, вследствие малого охвата данных или из-за относящихся к движению транспорта вопросов.
В качестве конечного этапа 806 при подготовке сгенерированных из кластеров профилей скорости кластеры интерполируются до переменного временного разрешения. В одном варианте осуществления это выполняется с использованием кубических сплайнов, но возможны другие методы, такие как функция экспоненциального приближения. Специалист в данной области техники также оценит по достоинству подобные методы, которые могут быть использованы.
Даже если временное разрешение, используемое в самой процедуре кластерного анализа, является более низким, чем требуется в конечном счете, что может иметь место, чтобы имелось достаточное количество надежной средней скорости в любом одном заранее определенном периоде времени, временное разрешение теперь может модифицироваться. Например, оно может модифицироваться до более высокого разрешения, чтобы удовлетворять требованиям предполагаемого использования. Например, может быть полезным иметь более высокое разрешение, имеющее более непрерывный профиль вместо того, который требуется для обеспечения более плавных маршрутов, которые иначе могут «перескакивать» на временных границах, если временное разрешение слишком низкое. В описываемом варианте осуществления сгенерированные из кластеров профили интерполируются, чтобы они имели разрешение с интервалами приблизительно 5 мин, хотя может использоваться любой другой период. Такой период может быть удобен для последующей обработки, использующей сгенерированный из кластеров профиль скорости.
Фиг.9 показывает типовой выходной результат алгоритма кластеризации для карты, в которой входные значения средней скорости были кластеризованы в 16 независимых сгенерированных из кластеров профилей скорости. Таким образом, для этой карты каждая секция дороги теперь может упоминаться как имеющая один из 16 сгенерированных из кластеров профилей скорости. Если в других вариантах осуществления количество кластеров изменяется, тогда также меняется количество возможных профилей скорости для любого одного сегмента дороги.
Если был определен подходящий набор сгенерированных из кластеров профилей скорости - в данном варианте осуществления было сгенерировано 16 - тогда они ассоциируются с одной или более картами. Как правило, набор профилей скорости будет более точным для карты, с которой они были сгенерированы, так как характер движения транспорта может быть другой на дорогах не на этой карте. Например, если карта покрывает одну страну, тогда может быть, что движение транспорта в другой стране придерживается несколько другим шаблонам.
Однако в других вариантах осуществления профили скорости могут ассоциироваться с множеством карт. В одном примере, может быть подходящим, если карта покрывает часть страны, и/или может быть подходящим использовать карту для многих стран.
Каждый сегмент дороги, который присутствует на обрабатываемой карте, анализируется и может иметь один из сгенерированных из кластеров профилей скорости (как показано на фиг.9), ассоциированный с ним для определения ожидаемой скорости движения по этому сегменту на протяжении недели. Эти профили скорости являются профилями скорости по умолчанию или профилями нормальной скорости, подлежащие использованию навигационным устройством для определения маршрута. Этот процесс описан относительно фиг.12. Начиная с n=1, обрабатывается n-ый сегмент дороги 1200.
Понятно, что, чтобы PND, использующие обрабатываемую карту, могли генерировать точные маршруты, желательно, чтобы каждый сегмент дороги имел профиль скорости, ассоциированный с ним, в котором высокая степень доверия (в качестве первого этапа оценивается, является ли подходящим профиль измеренной скорости). Таким образом, если сделанная ранее оценка качества определила, что профиль измеренной скорости не удовлетворяет критериям качества, тогда используется стратегия альтернатив для замены профиля измеренной скорости данными о скорости, которые, вероятно, оказываются лучшими для прокладки маршрута, назначенного при обработке посредством PND или другого устройства.
Если определено, что профиль измеренной скорости, фактически, является непригодным, тогда, в качестве первого альтернативного положения используется средняя скорость 1000 для обрабатываемого сегмента дороги, которая содержит среднее всех данных о скорости для этого сегмента дороги вместо профиля измеренной скорости. Т.е. данные, собранные для каждого периода времени для каждого дня, усредняются для генерирования единственной скорости. Эта единственная средняя скорость может, должным образом, отображаться на плоский сгенерированный из кластеров профиль скорости (номер 15 на фиг.9).
Затем, необходимо определить, является ли допустимой средняя скорость, сгенерированная из данных, собранных для сегмента. Если среднее проходит эти проверки, тогда среднее используется для этого сегмента дороги.
Снова, специалист в области статистики оценит по достоинству меры, которые могут использоваться для измерения качества среднего. Например, в некоторых вариантах осуществления может требоваться, чтобы среднее было составлено из более, чем заранее определенного количества скоростей, которым может быть, например, приблизительно 10 скоростей. Пороги могут применяться к средним для того, чтобы гарантировать, что они выше минимального значения (которым может быть, например, приблизительно 2 км/ч) и/или ниже максимального значения (которым может быть, например, приблизительно 150 км/ч). Также может использоваться среднеквадратическое отклонение для определения, имеет ли среднее достаточно высокое качество.
Известно, что сегменты дороги могут классифицироваться согласно системе классификации в картографических данных, так что дороги с подобными характеристиками классифицируются в рамках одной и той же классификации. Например, карты, сгенерированные одной стороной, имеют 8 категорий, по которым классифицируются сегменты дороги. В некоторых вариантах осуществления среднее для данного сегмента дороги анализируется для того, чтобы гарантировать, что, по меньшей мере, заранее определенный процент дорог в классификации для этого сегмента дороги обеспечивал скорость, которая использовалась для генерирования среднего. Если этот тест является неуспешным, тогда не только отклоняется среднее, но также может пропускаться процедура заполнения промежутка, описанная ниже.
Если сегмент дороги позволяет поток движения транспорта в двух направлениях, тогда будет набор средних скоростей, ассоциированных с каждым направлением.
Понятно, что, если профиль измеренной скорости был заменен во время стратегии альтернатив, тогда существует практически профиль скорости, который содержит плоскую линию, такую как кластерный профиль скорости номер 15, как показано на фиг.9. Дополнительно понятно, что, так как информация о профиле скорости нормализуется, тогда профиль скорости номер 15 может использоваться для представления любого сегмента дороги, имеющего единственную среднюю скорость, ассоциированную с ним.
Если среднее, сгенерированное из собранных данных от этого сегмента, все же не проходит проверку на качество, тогда используется следующий этап 1002 стратегии альтернатив, и используется так называемый процесс заполнения промежутка, который ниже описывается с помощью фиг.11. В качестве первого этапа каждый сегмент дороги на обрабатываемой карте категорируется как член одной из заранее определенного количества категорий 1100. Специалист в данной области техники оценит по достоинству, что эта категоризация каждого сегмента дороги должна выполняться только один раз, и результирующая категоризация поддерживается для других сегментов дороги, для которых вызывается процесс заполнения промежутка. Другие варианты осуществления, конечно, могут повторно вычислять при каждом вызове или действительно вычисляют категории на лету.
В описываемом варианте осуществления существует 40 таких категорий, описанные вкратце в следующей таблице 1. Эти категории могут изменяться в зависимости от картографических данных, которые обрабатываются, зоны, покрываемой картой, или любого другого относящегося фактора.
Таблица 1
Автомагистраль
0
любая автомагистраль внутри и вне города за исключением кругового движения, подъездной дороги или параллельной дороги
1
круговое движение на автомагистрали внутри и вне города
2
подъездная дорога на автомагистрали внутри и вне города
3
параллельная дорога на автомагистрали внутри и вне города
Международные дороги
4
любая международная дорога вне города за исключением кругового движения или подъездной дороги
5
любая международная дорога внутри города за исключением кругового движения или подъездной дороги
6
круговое движение на международной дороге вне города
7
круговое движение на международной дороге внутри города
8
подъездная дорога на международной дороге вне города
9
подъездная дорога на международной дороге внутри города
Главные дороги
10
любые главные дороги вне города за исключением кругового движения, подъездной дороги или параллельной дороги
11
любые главные дороги внутри города за исключением кругового движения, подъездной дороги или параллельной дороги
12
круговое движение на главных дорогах вне города
13
круговое движение на главных дорогах внутри города
14
подъездная дорога на главных дорогах
15
подъездная дорога на главных дорогах внутри города
16
параллельная дорога на главных дорогах внутри и вне города
Дороги второстепенного значения
17
любые дороги второстепенного значения вне города за исключением кругового движения, подъездной дороги или параллельной дороги
18
любые дороги второстепенного значения внутри города за исключением кругового движения, подъездной дороги или параллельной дороги
19
круговое движение по дорогам второстепенного значения вне города
20
круговое движение на дорогах второстепенного значения внутри города
21
подъездная дорога на дорогах второстепенного значения вне города
22
подъездная дорога на дорогах второстепенного значения внутри города
23
параллельная дорога на дорогах второстепенного значения внутри и вне города
Соединительные дороги
24
любые соединительные дороги вне города за исключением кругового движения или подъездной дороги
25
любые соединительные дороги внутри города за исключением кругового движения или подъездной дороги
26
круговое движение на соединительных дорогах вне города
27
круговое движение на соединительных дорогах внутри города
28
подъездная дорога на соединительных дорогах вне города
29
подъездная дорога на соединительных дорогах внутри города
Важные дороги местного значения
30
любые важные дороги местного значения вне города за исключением кругового движения
31
любые важные дороги местного значения внутри города за исключением кругового движения
32
круговое движение на важных дорогах местного значения вне города
33
круговое движение на важных дорогах местного значения внутри города
Дороги местного значения
34
любые дороги местного значения вне города за исключением кругового движения
35
любые дороги местного значения внутри города за исключением кругового движения
36
круговое движение на дорогах местного значения вне города
37
круговое движение на дорогах местного значения внутри города
Дороги к пункту назначения
38
любые дороги к пункту назначения вне города
39
любые дороги к пункту назначения внутри города
Если каждому сегменту дороги присваивается категория, тогда средняя скорость категории вычисляется для каждой одной из заранее определенных категорий 1102, в данном случае 40 категорий. Среднее категории, которое генерируется, является единственным числом на категорию, и, чтобы достичь этой средней скорости для каждого заранее определенного периода времени, усредняется с использованием любого подходящего метода усреднения, упомянутого в данном документе. Снова, специалист в данной области техники оценит по достоинству, что данный этап может потребоваться только для выполнения один раз, и средняя скорость категории поддерживается для будущих вызовов процесса заполнения промежутка.
Однако в данном варианте осуществления каждая средняя скорость для класса вычисляется в качестве взвешенного по длине гармонического среднего всех элементов, принадлежащих классу, которое определяется по следующей формуле:
,
где:
mean
- V: средняя скорость класса j
i
- l: длина линии i
i
- L: полная длина всех линий, принадлежащих классу j(L=∑l)
i
- V: средняя скорость линии i
Перед тем как эти средние скорости могут использоваться в дальнейшем, они проверяются для того, чтобы удостовериться, что они имеют достаточно высокое качество, так что они обеспечивают надежное представление средней скорости для этой категории дороги. Это может быть не так, если будет очень мало отсчетов в этом заранее определенном периоде времени для этого класса дороги, или если имеется слишком большое расхождение в отсчетах, которые пошли на составление конкретного среднего. Поэтому, выполняются проверки в отношении качества каждого среднего 1104, как описывается ниже.
Если средняя скорость из одной из 40 категорий основывается на меньшем количестве сегментов, чем hit_number_min (которые показаны для данного варианта осуществления в таблице 2 ниже), тогда это среднее заменяется значением из другой категории, как показано в таблице 3 ниже). В описываемом варианте осуществления значение минимального количества достижения определенного уровня равно десяти, но они могут изменяться в других вариантах осуществления.
Если ни quality_factor_abs конкретной категории, ни quality_factor_rel данной категории меньше или равно значениями, показанным в таблице 2, тогда среднее категории скорости заменяется средним назначенной категории замены, как показано в таблице 2. Видно, что quality_factor_rel определяется относительным среднеквадратическим отклонением класса в % от средней скорости, деленной на квадратный корень количества достижений определенного уровня, quality_factor_abs*100/mean_speed.
Поэтому, имеется три коэффициента качества (quality_factor_abs_min, quality_factor_rel_min, hit_number_min), которые успешно проходят проверку, перед тем как может использоваться средняя скорость в любой категории. Если коэффициенты качества не удовлетворяютсяк, тогда средняя скорость заменяется согласно таблице 3.
Значения, показанные в таблице 2, могут значительно меняться в других вариантах осуществления и показаны только в качестве примера. Аналогично, значения для замены, используемые в таблице 3, могут значительно меняться в других вариантах осуществления, в зависимости от зоны, покрываемой картой, стороны, которая сгенерировала картографические данные, и т.д.
Перед тем как может использоваться одно из средних, сгенерированных для категории, проверяется, проходит ли оно некоторые проверки качества. Если оно не проходит эти проверки, тогда процедура заполнения промежутка не подходит для этой категории. Эти проверки качества следующие.
Среднее для классификации должно быть выше минимального порога и ниже максимального порога, которые вычисляются следующим образом, причем min и max являются минимальной и максимальной функциями псевдокода:
,
где mean является средней скоростью соответствующего класса скорости сегмента. Другие величины заданы в таблице 4.
Если скорость, ассоциированная с сегментом, не удовлетворяет этим критериям, тогда эта скорость заменяется ее порогом, основанным на ее средней скорости, если только скорость, ассоциированная с сегментом, не нарушает абсолютные пределы скорости, в этом случае абсолютные пределы скорости будут использоваться в качестве скорости для этого сегмента.
Таблица 4
Параметр
Значение по умолчанию [диапазон значения]
Описание
upper limit
130
Абсолютная разрешенная максимальная скорость для сегмента в км/ч
lower_limit
5
Абсолютная разрешенная минимальная скорость в км/ч для сегмента
Upper_relative_devision
50
Максимальное разрешенное верхнее отклонение скорости для сегмента в процентах от его среднего значения класса
upper_absolute_devision
30
Максимальное разрешенное верхнее абсолютное отклонение скорости в км/ч для сегмента, относящееся к его среднему значению класса
lower_relative_devision
50
Максимальное разрешенное нижнее отклонение скорости для сегмента в процентах от его среднего значения класса
lower_absolute_devision
30
Максимальное разрешенное нижнее абсолютное отклонение скорости в км/ч для сегмента, относящееся к его среднему значению класса
Специалист в данной области техники оценит по достоинству, что вычисления выполняются над скоростями, а не над временными данными.
Таким образом, в конце процесса заполнения промежутка может быть сгенерирована средняя скорость, основанная на сегментах дороги в пределах этой же категории из заранее определенных 40. Однако процесс заполнения промежутка может все же быть неуспешным (т.е. не генерируется среднее, которое успешно проходит проверки качества).
Таким образом, сегменты дороги, которые не имеют данные о скорости, ассоциированные с ними, теперь имеют данные о средней скорости, присвоенные им 1108, которые были сгенерированы процедурой заполнения промежутка (предполагая, что среднее успешно прошло проверки качества).
Если заполнение промежутка было неуспешное, тогда на этапе 1004 скорость, ассоциированная с этим сегментом дороги, устанавливается равной скорости, которая была предоставлена поставщиком картографических данных согласно функциональному классу дороги (FRC). Функциональный класс дороги, например, может содержать приблизительно 8 категорий, хотя он может различаться среди поставщиков картографических данных. Т.е. скорость свободного потока устанавливается на значение согласно FRC, и сгенерированный из кластеров профиль скорости устанавливается в данном варианте осуществления на профиль с номером 15.
Затем профиль скорости (или профиль измеренной скорости или среднее, вставленное заполнением промежутка), ассоциированный с сегментом дороги, теперь отображается на один из сгенерированных из кластеров профилей скорости для генерирования картографических данных, которые могут использоваться навигационными устройствами, такими как PND. Это может выполняться независимо от того, представляет ли собой информация о скорости профиль измеренной скорости или среднее ввиду присутствия плоского сгенерированного из кластеров профиля скорости с номером 15.
На этапе 1210 профиль скорости сравнивается, используя сравнение методом наименьших квадратов, с каждым профилем скорости в наборе сгенерированных из кластеров профилей скорости. После того как будут сделаны эти 16 сравнений, можно определить, какой профиль скорости из набора 16 является самым близким к профилю скорости, ассоциированному с сегментом дороги, и на этапе 1220 ссылка на сгенерированный из кластеров профиль скорости, который, как считается, является самым близким, хранится в картографических данных для этого сегмента дороги. Также хранится в картографических данных относительно этого сегмента дороги скорость свободного потока для этого сегмента дороги, которая была вычислена ранее.
Таким образом, используя ссылку и скорость свободного потока, информация может храниться в картографических данных, которые обеспечивают информацию о средних скоростях для каждого сегмента дороги. Для сегментов с частым движением предоставляемая информация о средней скорости может рассматриваться как содержащая аппроксимацию ежедневного ежечасного среднего между 9 часами до полудня и 5 часами после полудня. Для сегментов с меньшим движением информация о средней скорости может рассматриваться как являющаяся средней скоростью, которая усредняется по всем периодам времени.
Это повторяется 1230 до тех пор, пока каждый из сегментов дороги на карте не будет иметь один из набора 16 сгенерированных из кластеров профилей скорости, ассоциированных с ним.
Перед тем как картографические данные могут быть выпущены для использования, выполняется окончательная проверка, имеют ли достаточное количество сегментов дороги профиль измеренной скорости, ассоциированный с ними (в противоположность среднему, которое было вставлено вместо профиля измеренной скорости). Если эта проверка не проходит, тогда вся карта отклоняется и не выпускается для использования.
В этой окончательной проверке общая длина сегментов дороги вычисляется для каждого функционального класса дороги (FRC). FRC связаны с 40 категориями, перечисленными в таблице 2, как показано в таблице 5 ниже. Длина сегмента дороги в каждом FRC с данными о средней скорости, присвоенными ему, должна быть выше порогового процента общей длины дороги в FRC, как показано в таблице 5.
Таблица 5
Описание FRC (функционального класса дороги)
FRC
Минимальное требуемое покрытие длины [%]
Автомагистрали
0
60
Международные дороги
1
50
Главные дороги
2
40
Дороги второстепенного значения
3
30
Соединительные дороги
4
18
Важные дороги местного значения
5
12
Дороги местного значения
6
2
Дороги к пункту назначения
7
0
Видно, что цифрам минимального покрытия для категорий дороги, которые, как правило, имеют большее влияние на характер прокладки маршрута, даются более высокие процентные требования по сравнению с категориями дороги, которые имеют меньшее влияние. Например, FRC 0 (автомагистрали) должны иметь 60%, так как они имеют более высокое влияние на прокладку маршрута по сравнению, например, с дорогами второстепенного значения, которые, следовательно, имеют требование на покрытие в 30%.
В других вариантах осуществления могут обеспечиваться другие стратегии альтернатив. В одном таком варианте осуществления первой стратегией альтернатив (если профиль измеренной скорости считается неприемлемым) может быть агрегирование этих же заранее определенных периодов времени для каждого дня и добавление к этому периоду для каждого из других дней, и затем результирующий агрегированный профиль скорости используется для каждого дня, а не использование профиля измеренной скорости для каждого отдельного дня. Поэтому, в таком варианте осуществления еженедельный профиль скорости генерируется посредством добавления этих же периодов времени для каждого дня с понедельника по пятницу, и профиль скорости выходных дней генерируется посредством добавления этих же периодов времени для каждой субботы и воскресенья. Понятно, что поток движения транспорта по выходным дням может существенно отличаться от потока движения транспорта по рабочим дням.
Такой агрегированный профиль скорости затем может проверяться, удовлетворяет ли он критериям качества, перед использованием других стратегий альтернатив, если он не является приемлемым. Эти проверки могут выполняться, используя эти же, или, по меньшей мере, подобные, критерии тем, которые используются для оценки профилей измеренной скорости. Если агрегирование данных повысило качество, так что как еженедельные профили скорости, так и профили скорости выходных дней проходят проверку на качество, тогда эти профили скорости используются для этого сегмента дороги.
Профили скорости, вычисленные по вышеописанному способу, задают ожидаемую скорость движения по сегментам для нормальной недели и используются в качестве профилей скорости по умолчанию для определения маршрута навигации. Поэтому, эти профили скорости называются профилями «нормальной» скорости и, как будет оценено по достоинству, были определены посредством обработки данных о скорости, агрегированных вместе от многочисленных периодов времени, которые повторяются каждую неделю.
Однако характер движения транспорта может существенно отличаться от профиля нормальной скорости, если имеется событие, которое не является типичным еженедельным событием, такое как национальный праздник, фестиваль, экстремальная погода или дорожно-транспортное происшествие. Чтобы учитывать необычный характер движения транспорта, вызванный такими событиями, процессор 154 выполнен с возможностью обработки данных о скорости для генерирования профилей анормальной скорости для сегментов, подлежащих использованию в заданные моменты времени, когда происходят эти события.
Это ниже описывается со ссылкой на фиг.13. На этапе 1300 процессор 202 идентифицирует моменты времени в прошлом, в течение которых происходило или ожидалось происхождение нетипичного характера движения транспорта. Это может осуществляться процессором 154, выполняющим поиск по календарю событий (не показан), хранящемуся в памяти 156, моментов времени нееженедельных событий, которые могут иметь влияние на характер движения транспорта.
В ответ на идентификацию моментов времени, в течение которых необычный характер движения транспорта происходил или ожидалось его происхождение, процессор 154 на этапе 1301 определяет один или более профилей анормальной скорости, подлежащих присвоению сегментам.
Профили анормальной скорости могут быть указателями на использование одного из профилей нормальной скорости, обычно используемых для другого периода времени. Например, заданным моментом времени может быть национальный праздник, такой как официальный выходной день Великобритании, и профиль анормальной скорости может быть указателем на профиль нормальной скорости для воскресенья, идентифицирующий, что этот профиль нормальной скорости также должен использоваться для дней (которые не являются воскресеньями), которые являются национальными праздниками.
Процессор 154 может генерировать профиль анормальной скорости посредством извлечения данных о скорости для всех периодов времени, идентифицированных как имеющие нетипичный характер движения транспорта и имеющие общий атрибут, такой как являющийся национальным праздником или моментом времени или днем, по которым были суровые погодные условия, агрегирования этих данных о скорости и генерирования профилей скорости из этих данных о скорости в соответствие с вышеописанным способом со ссылкой на фиг.7-12. Это приводит к последовательности профилей скорости особенно для моментов времени нетипичного характера движения транспорта, такого как национальные праздники или моменты времени суровой погоды.
Процессор 154 также может генерировать профиль анормальной скорости посредством пропорционального повышения или снижения (в большинстве случаях снижения) уже вычисленных профилей нормальной скорости.
Процессор 154 на этапе 1302 присваивает каждый профиль анормальной скорости одному или более сегментам картографических данных и присваивает идентификатор, идентифицирующий, при каких условиях должен использоваться профиль анормальной скорости. Это может определяться из календаря событий для будущих событий или из идентификации характерных условий, когда происходит нетипичный характер движения транспорта, например, условия, идентифицированные как присутствующие, когда в прошлом имел место нетипичный характер движения транспорта.
Созданные картографические данные посылаются на навигационное устройство 200 сервером 150 для использования при определении маршрута по зоне, покрываемой картографическими данными.
Как показано на фиг.14, при приеме через устройство 222 I/O запроса на определение маршрута, процессор 202 навигационного устройства 200 идентифицирует 1400 условия в момент времени движения по маршруту. Например, навигационное устройство 200 содержит календарь событий будущих событий, хранящихся в памяти 214 или на карточке памяти в порту 228 карточки, и принимает обновления в реальном времени по погоде и движению транспорта через антенну/приемник 224, которые также хранятся в памяти. При приеме запроса на определение маршрута процессор 202 выполняет поиск по календарю событий и хранящимся обновлениям реального времени для определения 1401, соответствуют ли условия в момент движения заданному условию идентификатора в картографических данных, которое указывает, когда использовать профиль анормальной скорости, а не профиль нормальной скорости. Если выполняется соответствие, тогда процессор 202 использует профили анормальной скорости для определения маршрута. Если нет, тогда процессор 202 использует профили нормальной скорости для определения маршрута.
В одном варианте осуществления обновления реального времени могут включать в себя местоположение, в котором происходит/будет происходить дорожно-транспортное происшествие или суровое погодное условие. При приеме запроса на определение маршрута процессор 202 использует подход ограничивающего прямоугольника/зоны влияния для определения, для которых сегментов должен использоваться профиль анормальной скорости, и для каких сегментов должен использоваться профиль нормальной скорости. Процессор 202 идентифицирует сегменты в пределах заранее определенного расстояния от происшествия или другого события, например, в пределах 50 или 100 км, и использует анормальный профиль для этих сегментов и использует профиль нормальной скорости для сегментов вне этой (или любой другой зоны влияния). Таким образом, навигационное устройство может учитывать события, которые могут иметь локальное, а не глобальное влияние на движение транспорта.
В другом варианте осуществления процессор 200 навигационного устройства 202 может использовать другой один из других профилей нормальной скорости для скорости движения по сегментам, а не профиль нормальной скорости, соответствующий моменту времени движения, когда идентифицируется заданное условие в момент движения. Таким образом, необязательно, чтобы картографические данные содержали профили анормальной скорости. Такая функциональная возможность может быть подходящей там, где заданным условием является то, что момент времени движения является национальным праздником. Если это условие удовлетворяется, процессор 202 будет использовать профиль скорости субботы или воскресенья, а не профиль скорости для дня, на который приходится национальный праздник. Примером этого является то, когда моментом времени движения является официальный выходной день Великобритании (которым является обычно понедельник) и, в таком случае, процессор 202 (при определении маршрута в Великобритании) может использовать профиль нормальной скорости для воскресенья для определения маршрута, а не профиль нормальной скорости понедельника.
Специалист в данной области техники оценит по достоинству, что устройство, обеспечиваемое для исполнения способа, описанного в данном документе, может содержать аппаратные, программные, аппаратно-программные средства или любую комбинацию двух или более из них.
Специалист в данной области техники оценит по достоинству, что, хотя термин «GPS-данные» использовался для ссылки на данные о положении, полученные от глобальной системы позиционирования GPS, например, описанной в связи с фиг.1, другие данные о положении могут обрабатываться образом, подобным способам, описанным в данном документе. Таким образом, термин «GPS-данные» может быть заменен фразой «данные позиционирования». Такая информация о положении, например, может быть получена из информации о положении, извлеченной при работе мобильного телефона, данных, принимаемых на контрольных постах, данных, полученных от детекторов транспортных средств, вмонтированных в дороги, данных, полученных от системы распознавания номерных знаков, или любых других подходящих данных.