close

Вход

Забыли?

вход по аккаунту

?

Патент BY 12943

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.02.28
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 12943
(13) C1
(19)
G 01C 21/00
СПОСОБ, УСТРОЙСТВО И СИСТЕМА
ДЛЯ МОДЕЛИРОВАНИЯ ГРАФА ДОРОЖНОЙ СЕТИ
(21) Номер заявки: a 20080195
(22) 2005.07.22
(85) 2008.02.22
(86) PCT/IB2005/002129, 2005.07.22
(87) WO 2007/010317, 2007.01.25
(43) 2008.08.30
(71) Заявитель: ТЭЛАРГО ИНК. (US)
(72) Авторы: КОРЕС, Андрей; ПАВЛИК,
Богдан; ПЕКАР, Мартин; НОВАК,
Тадей (SI)
(73) Патентообладатель: ТЭЛАРГО ИНК.
(US)
(56) US 6385539 B1, 2002.
BY 4947 C1, 2003.
UA 52943 A, 2003.
SU 1672503 A1, 1991.
BY 12943 C1 2010.02.28
(57)
1. Способ моделирования графа дорожной сети, содержащий этапы, на которых
принимают информационные данные от множества транспортных средств, причем
информационные данные содержат, по меньшей мере, позиционные данные упомянутых
транспортных средств,
вычисляют первое приближение упомянутого графа дорожной сети на основании упомянутых принятых информационных данных, в котором упомянутое вычисление базируется на методах кривых Безье,
профилируют дороги и перекрестки в упомянутом первом приближении, в результате
чего получают граф профилированной дорожной сети и
Фиг. 1
BY 12943 C1 2010.02.28
выполняют проверку упомянутой профилированной дорожной сети.
2. Способ по п. 1, отличающийся тем, что упомянутые принятые информационные
данные содержат, по меньшей мере, одно из: тип транспортного средства, скорость, ускорение транспортного средства и подобное из упомянутого множества транспортных
средств.
3. Способ по п. 1, отличающийся тем, что дополнительно содержит этап, на котором
вычисляют геометрию дорожной сети, топологию и статистику дорожного движения в
автоматическом режиме.
4. Способ по любому из пп. 1-3, отличающийся тем, что содержит этап, на котором
автоматически объединяют упомянутые принятые информационные данные с дополнительной информацией о графе дорожной сети, полученной из других источников.
5. Способ по любому из пп. 1-3, отличающийся тем, что выполняют автоматическое
профилирование графа дорожной сети посредством использования упомянутых принятых
информационных данных.
6. Способ по любому из пп. 1-3, отличающийся тем, что проверку выполняют посредством обследования графа, предпочтительно, с помощью транспортных средств, которые обследуют граф дорожной сети на месте.
7. Способ по любому из пп. 1-3, отличающийся тем, что упомянутый граф дорожной
сети используют для этапа оптимизации в течение проверки упомянутого графа дорожной
сети.
8. Способ по любому из пп. 1-3, отличающийся тем, что упомянутое моделирование
базируют на математических методах для обработки кривых, дуг, многочленов или подобного, выполняемое над упомянутыми данными.
9. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором увеличивают длины кривых Безье до необходимой, заранее определенной длины.
10. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором осуществляют подгонку кривой Безье под упорядоченное множество точек, причем упомянутая кривая соответствует траектории некоторого транспортного средства.
11. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором рассчитывают подобие некоторой пары кривых Безье.
12. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором выполняют обнаружение подобия для отыскания подобных подучастков
некоторой пары кривых Безье.
13. Способ по любому из пп. 1-3, отличающийся тем, что обеспечивают передачу
информации, относящейся к упомянутому графу дорожной сети, на, по меньшей мере, одно транспортное средство из упомянутого множества транспортных средств.
14. Способ по любому из пп. 1-3, отличающийся тем, что содержит этап сжатия упомянутых принятых информационных данных, относящихся к упомянутому множеству
транспортных средств.
15. Способ по п. 14, отличающийся тем, что этап сжатия содержит подгонку кривых
Безье.
16. Способ по любому из пп. 1-3, отличающийся тем, что упомянутые принятые информационные данные представляют траекторию, по меньшей мере, одного транспортного средства из упомянутого множества транспортных средств, где каждая траектория
может быть описана кривыми Безье, причем упомянутый способ дополнительно содержит
этап, на котором усредняют траектории, связанные с упомянутым, по меньшей мере, одним транспортным средством.
17. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этапы, на которых
2
BY 12943 C1 2010.02.28
обнаруживают изменения существующего графа дорожной сети на основании упомянутых принятых информационных данных,
сохраняют упомянутые изменения и
реализуют упомянутые изменения в упомянутом существующем графе дорожной сети.
18. Способ по п. 17, отличающийся тем, что упомянутая реализация базируется на
статистической информации.
19. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором передают информацию, относящуюся к упомянутому графу дорожной
сети, на, по меньшей мере, одно транспортное средство из упомянутого множества транспортных средств.
20. Способ по п. 16, отличающийся тем, что дополнительно содержит этап, на котором выполняют упомянутый этап сжатия упомянутых принятых информационных данных
избирательно в упомянутом моделирующем средстве и/или в упомянутом множестве
транспортных средств.
21. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором сохраняют упомянутые принятые информационные данные.
22. Способ по п. 3, отличающийся тем, что упомянутое вычисление базируют на методах цифрового вычисления для вычисления значений с фиксированной точкой.
23. Способ по любому из пп. 1-3, отличающийся тем, что упомянутые информационные данные содержат данные измерений и дополнительно содержащий этап, на котором
нормализуют упомянутые данные измерений согласно заранее определенным пороговым
значениям.
24. Способ по п. 21, отличающийся тем, что упомянутое сохранение обеспечивают
после выполнения алгоритма сжатия, алгоритма хэширования, алгоритма шифрования
или подобного.
25. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором обнаруживают наличие явления/эффекта многолучевого распространения и в этом случае присваивают упомянутой принятой информации меньший весовой
коэффициент в течение упомянутого этапа вычисления.
26. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно содержит
этап, на котором измеряют размеры и/или пропорции дорог посредством средства обеспечения информации положения в упомянутом множестве транспортных средств.
27. Способ по п. 26, отличающийся тем, что упомянутым средством является приемопередатчик GPS в упомянутом транспортном средстве.
28. Способ по п. 27, отличающийся тем, что приемопередатчик GPS соединен с гироскопом и подобным.
29. Способ по любому из пп. 1-3, отличающийся тем, что подобие кривых Безье используют для определения позиции упомянутого транспортного средства в графе дорожной сети.
30. Машинно-считываемый носитель, содержащий хранящиеся на нем участки программного кода, выполняемые на устройстве на основе процессора, терминальном устройстве, сетевом устройстве, портативном терминале, абонентском электронном
устройстве или терминале с возможностью мобильной связи, для моделирования графа
дорожной сети способом по любому из пп. 1-29.
31. Серверное устройство для моделирования графа дорожной сети, содержащее
компонент для приема информационных данных от множества транспортных средств,
причем упомянутые информационные данные содержат, по меньшей мере, позиционные
данные упомянутых транспортных средств,
компонент для вычисления первого приближения упомянутого графа дорожной сети,
в котором упомянутое вычисление базируется на методах кривых Безье,
3
BY 12943 C1 2010.02.28
компонент для профилирования дорог и перекрестков в упомянутом первом приближении, в результате чего получается граф профилированной дорожной сети, и
компонент для выполнения проверки упомянутой профилированной сети.
32. Сервер по п. 31, отличающийся тем, что содержит
компонент для обнаружения изменений упомянутого графа дорожной сети на основании упомянутой принятой информации,
компонент для сохранения упомянутых изменений и
компонент для включения упомянутых изменений в упомянутый граф дорожной сети.
33. Сервер по п. 31, отличающийся тем, что дополнительно содержит
компонент для анализа упомянутого графа дорожной сети на основании упомянутой
принятой информации и
компонент для сообщения результатов анализа третьей стороне.
34. Сервер по п. 31, отличающийся тем, что дополнительно содержит компонент для
выполнения этапа сжатия упомянутой принятой информации избирательно в упомянутом
компоненте вычисления.
35. Сервер по любому из пп. 31-34, отличающийся тем, что дополнительно содержит
компонент для сохранения, по меньшей мере, упомянутых информационных необработанных данных, принятых от упомянутого множества транспортных средств, атрибутов,
связанных с упомянутыми необработанными данными, графа дорожной сети и подобного.
36. Сервер по любому из пп. 31-34, отличающийся тем, что дополнительно содержит
компонент для обнаружения наличия явления/эффекта многолучевого распространения и, дополнительно,
компонент для присвоения упомянутой принятой информации меньшего весового коэффициента в случае обнаружения эффекта многолучевого распространения.
37. Сервер по любому из пп. 31-34, отличающийся тем, что дополнительно содержит
компонент для измерения размеров дорог посредством средства обеспечения информации
положения в упомянутом множестве транспортных средств.
38. Сервер по любому из пп. 31-34, отличающийся тем, что упомянутая принятая информация представляет траекторию, по меньшей мере, одного транспортного средства из
упомянутого множества транспортных средств, причем каждая траектория описывается
посредством упомянутых математических методов; упомянутый сервер дополнительно
содержит компонент для усреднения траекторий, связанных с упомянутым, по меньшей
мере, одним транспортным средством.
39. Сервер по п. 38, отличающийся тем, что математические методы соответствуют,
по меньшей мере, одному из: кривым Безье, дугам, многочленам или подобному.
40. Система для моделирования графа дорожной сети, содержащая множество серверов по п. 31 и множество транспортных средств обеспечения информационных данных.
Настоящее изобретение относится к области моделирования (или генерации или формирования или адаптации) графа дорожной сети, изображающего единую топографическую структуру (форму, профиль или контур соответственно) дорог, улиц и других
соединений, связанных с дорожным движением. Кроме того, предусмотрены серверное
устройство и система, способные эффективно осуществлять способ моделирования графа.
С учетом более или менее устойчивого увеличения количества транспортных средств в
течение последних двух десятилетий, и особенно в наши дни, в развивающихся и быстро
растущих странах, например Китае, России и Бразилии, также существует необходимость
снабжения водителей точным маршрутом и дорожной навигацией и снабжения организаторов дорожной системы данными, которые помогают им справляться со все более интенсивным движением.
4
BY 12943 C1 2010.02.28
В современном мире существуют некоторые развитые системы, способные решать обе
эти задачи. В развитых государствах в течение последних двух лет были созданы цифровые модели их дорожных систем, которые позволяют водителям ориентироваться в пути.
Эта система известна в настоящее время как автомобильная навигация. Эти системы иногда дополняются системами, обеспечивающими оперативные данные дорожного движения, которые обычно стекаются к оператору дорожной системы и рассылаются на
транспортные средства, оборудованные устройствами навигации, с использованием широковещательной или иной технологии (RDS и т.д.).
Все эти системы требуют утомительной работы по сбору и проверке данных геодезическими средствами (с использованием современных методов, например, GPS). Кроме того,
сбор данных о состоянии дорожного движения требует установки автомобильных устройств распознавания объезда (так называемых петель, микроволновых занавесов, камер и
т.п.) для сообщения о необычных событиях самими водителями и мониторинга с помощью специальных транспортных средств, самолетов или вертолетов. Хотя последние меры почти неизбежны, когда идет речь об оперативных данных, они предоставляют меньше
полезных данных организаторам дорожной системы.
Задачей настоящего изобретения является обеспечение способа, устройства и системы
для моделирования графа дорожной сети, которые позволяют преодолеть недостатки существующей техники.
Средства решения задач настоящего изобретения определены в прилагаемых независимых пунктах формулы изобретения.
Согласно первому аспекту настоящего изобретения, предусмотрен способ моделирования графа дорожной сети, предпочтительно, осуществляемый на, по меньшей мере, одном
сервере моделирования. Способ моделирования может охватывать способ вычисления графа, способ (предпочтительно, автоматического) профилирования графа, способ (предпочтительно, автоматического) обновления и способ проверки графа. Способ содержит, по
меньшей мере, этапы, на которых принимают информацию от совокупности транспортных
средств, причем информационные данные содержат позиционные данные, предпочтительно
данные географического положения совокупности транспортных средств и моделируют
граф дорожной сети в соответствии с принятыми данными. Таким образом, достигается эффективное обновление графа дорожной сети надежным и экономичным способом.
Кроме того, способ вычисления графа может содержать автоматическое вычисление
геометрии (данных позиции), топологии (данных соединения) и статистики (напряженности движения, средних скоростей и т.д.) дорожной сети. Таким образом, можно получить
подробные данные и статистику дорожного движения для использования в системах навигации и в устройстве управления/планирования движения.
Кроме того, способ вычисления графа предусматривает использование измерений от
транспортных средств, включенных в систему (информации), или информации графа сети
из других источников (государственных органов, картографических или дорожностроительных компаний, распознавания аэрофотосъемки или других изображений и т.д.).
В этом случае имеет место, в основном, слияние графов. Таким образом, можно объединять информацию из нескольких источников.
Кроме того, способ профилирования может содержать (предпочтительно, автоматически выполняемые) этапы, на которых обобщают представление дорог и перекрестков и
задают их параметры согласно информации. Таким образом, граф можно завершать и преобразовывать к другим (более абстрактным) представлениям графа.
Кроме того, информационные данные также можно получать, например, у третьей стороны. Это применимо, в особенности, для такой информации, для измерения которой совокупность транспортных средств (кроме транспортных средств проверки) не имеют
оборудования, например, названий улиц или скоростных ограничений. Таким образом,
используется другой источник.
5
BY 12943 C1 2010.02.28
Способ обновления графа, по существу, соответствует способу его профилирования.
Одним основным отличием является извещение о значительных изменениях в графе и
этап вычисления графа на новых подучастках.
Способ проверки может содержать обследование графа, которое также производится
специально оборудованными транспортными средствами проверки, которые объезжают
дорожную сеть и ищут несоответствия с графом дорожной сети, и предоставляют дополнительную информацию о нем. С использованием предварительно обеспеченного графа
дорожной сети можно реализовать этап оптимизации в определенном процессе проверки.
Оптимизация может заключаться в оптимизации маршрутов для транспортных средств
проверки. Таким образом, обеспечивается дополнительное средство перекрестного контроля и проверки графа дорожной сети.
Согласно еще одному варианту осуществления настоящего изобретения, моделирование базируется на математических методах обработки кривых, дуг, многочленов и т.п.,
осуществляемых над данными. Таким образом, моделирование можно реализовать в компьютерной системе с использованием математических методов. Таким образом, например,
разные данные можно обрабатывать одним и тем же способом, таким образом, достигая,
например, воспроизводимых результатов.
Согласно еще одному варианту осуществления настоящего изобретения, моделирование базируется на методах кривых Безье, осуществляемых над данными. Предпочтительно, кривые Безье можно использовать ввиду хороших приближений, достигаемых в
практических вариантах осуществления с использованием этих кривых.
Согласно еще одному варианту осуществления настоящего изобретения, информационные данные могут содержать тип транспортного средства, скорость, ускорение транспортного средства и пр. Предпочтительно, данные могут содержать (вышеупомянутую)
дополнительную информацию, которая позволяет лучше моделировать дорожный граф.
Посредством дополнительных параметров легко исследовать определенное поведение
(движение), например, конкретного автомобиля.
Согласно еще одному варианту осуществления настоящего изобретения, принятые информационные данные представляют траекторию, по меньшей мере, одного транспортного средства из совокупности транспортных средств. Каждая траектория, предпочтительно,
описывается кривыми Безье. Кривые Безье позволяют верно и точно представлять траектории, соответствующие определенному маршруту конкретного транспортного средства.
Согласно предпочтительному варианту осуществления, можно предусмотреть усреднение
траекторий, связанных с, по меньшей мере, одним транспортным средством. Благодаря
усреднению можно добиться точного представления траектории. Главная траектория вычисляется на основании совокупности траекторий, в результате чего получается усовершенствованная модель. Совокупность может происходить от определенного транспортного средства или даже от разных транспортных средств.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрены вычисление первого приближения графа дорожной сети на основании принятых информационных данных, профилирование дорог и перекрестков посредством первого
приближения, в результате чего получается граф профилированной дорожной сети и осуществление проверки профилированной сети. Вышеупомянутые этапы улучшают результирующее представление графа дорожной сети. Первое приближение используется в
качестве первого подхода, и последующие этапы можно итерационно осуществлять в соответствии с замкнутым циклом, т.е. цикл соответствует преимущественной реализации
согласно настоящему изобретению.
Согласно еще одному варианту осуществления настоящего изобретения, вычисление
базируется на методах кривых Безье. Предпочтительно, вычисление может базироваться
на кривых Безье, которые обеспечивают точные и подробные результаты.
6
BY 12943 C1 2010.02.28
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрены обнаружение изменений существующего графа дорожной сети на основании принятых
информационных данных, сохранение изменений и реализация изменений в существующем графе дорожной сети. Таким образом, изменения в существующей дорожной сети регистрируются, и, согласно настоящему изобретению, способ позволяет реализовать эти
изменения на основании, например, уже смоделированного или вычисленного графа.
Согласно еще одному варианту осуществления настоящего изобретения, реализация
базируется на статистической информации. Статистическая информация, в общем случае,
соответствует информации дорожного движения, например, средней скорости движущегося транспортного средства согласно, например, времени недели, времени, необходимого
для переезда из пункта А в пункт В с использованием упомянутого транспортного средства или с использованием другого типа транспортного средства и т.д. Другое состояние дорожного движения можно использовать в качестве статистической информации.
Предполагается даже использование поведения определенного водителя в качестве статистических информационных данных. Например, профессиональный водитель, в частности
водитель такси, будет иначе вести себя в ходе ежедневных поездок, чем обычный водитель, который желает доехать из пункта А в пункт В.
Кроме того предполагается, что статистическая информация обеспечивается в процессе
сбора посредством измеряющих транспортных средств и т.п.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрена передача информации, относящейся к графу сети, на, по меньшей мере, одно транспортное средство совокупности транспортных средств. Таким образом, можно обеспечить
дистанционную навигацию на транспортном средстве. Иными словами, водитель транспортного средства будет принимать данные навигации от сервера, что позволяет дистанционно управлять поездкой. Предпочтительно, фактическая информация, относящаяся к
смоделированному графу дорожной сети, переправляется водителю для обеспечения, например, поведения экономичного вождения. Поскольку граф дорожной сети автоматически и/или периодически адаптируется, водитель транспортного средства всегда будет
получать фактическую информацию, например, о характеристиках дороги.
Согласно еще одному варианту осуществления настоящего изобретения, граф профилированной дорожной сети включает в себя информацию о временах обхода, в отношении
того, когда берется дорога. Предпочтительно, времена можно дополнительно использовать, например, для вопросов навигации. Кроме того, можно реализовать планирование
дороги на основании данных хронирования.
Согласно еще одному варианту осуществления настоящего изобретения, информацию
от совокупности транспортных средств можно сжимать с использованием математических
методов обработки кривых, дуг, многочленов и т.д. Посредством методов сжатия можно
уменьшить объем данных, подлежащий хранению и/или обработке. Согласно предпочтительному варианту осуществления, траектории можно описывать кривыми Безье.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрено
осуществление этапа сжатия информационных данных избирательно в моделирующем средстве и/или в совокупности транспортных средств. Таким образом, сжатие можно реализовать
на стороне транспортного средства, что означает, что серверное средство можно освободить,
т.е. сэкономленную вычислительную мощность можно использовать для других задач.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрено сохранение информационных данных. Таким образом, обеспечивается использование в
будущем определенных данных, представляющих интерес.
Согласно еще одному варианту осуществления настоящего изобретения, вычисление
базируется на методах цифрового вычисления для точного расчета значений с фиксированной точкой. Таким образом, можно обеспечить вычисление на средствах, базирующихся на архитектурах вычислений с фиксированной точкой.
7
BY 12943 C1 2010.02.28
Согласно еще одному варианту осуществления настоящего изобретения, информационные данные содержат данные измерений, и дополнительно предусмотрен этап нормализации данных измерений согласно заранее определенным пороговым значениям.
Благодаря осуществлению этапа нормализации данные представляются согласно заранее
определенным порогам, что улучшает, например, манипуляцию и/или иллюстрацию. Его
также можно применять в средствах, базирующихся на архитектурах вычислений с фиксированной точкой и, таким образом, уменьшать ошибку вычислений.
Согласно еще одному варианту осуществления настоящего изобретения, сохранение
предусмотрено после выполнения алгоритма сжатия, алгоритма хэширования, алгоритма
шифрования и т.п. Таким образом, достигается сохранение защищенных и сжатых данных.
Соответственно каждая регистрационная запись посылается после того, как бортовое
устройство определит всю необходимую информацию.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрено обнаружение наличия явления/эффекта многолучевого распространения, и в этом случае на этапе вычисления принятой информации можно присваивать меньший весовой
коэффициент. Таким образом, гарантируется, что данные, искаженные вследствие эффекта многолучевого распространения, получат меньший весовой коэффициент, например, на
этапах вычисления.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрено измерение размеров дорог посредством средства обеспечения информации положения
в совокупности транспортных средств. Таким образом, обеспечивается определение характеристики оси дороги, соответствующей форме траектории. Кроме того, обеспечивается подробное определение размеров оси дороги, соответствующих ширине улицы (дороги)
и т.д.
Согласно еще одному варианту осуществления настоящего изобретения, сущностью
является приемопередатчик GPS в транспортном средстве. Однако приемопередатчик
способен принимать и/или передавать позиционные данные надлежащим образом оборудованного транспортного средства.
Согласно еще одному варианту осуществления настоящего изобретения, предусмотрено вычисление геометрии, топологии и статистики дорожной сети в автоматическом
режиме. Вычисление автоматически осуществляется посредством, например, периодического алгоритма.
Согласно еще одному варианту осуществления настоящего изобретения, обеспечивается автоматическое профилирование графа дорожной сети с использованием информационных данных.
Согласно еще одному варианту осуществления настоящего изобретения, обеспечивается автоматическое обновление графа дорожной сети с использованием также информационных данных.
Автоматическое профилирование и/или обновление также может базироваться на периодических алгоритмах, которые, например, повторяются на временной основе.
Согласно еще одному аспекту настоящего изобретения, предусмотрен компьютерный
программный продукт, который содержит участки программного кода, хранящиеся на
машинно-считываемом носителе, для осуществления операций способа согласно любому
вышеупомянутому варианту осуществления изобретения, когда компьютерный программный продукт выполняется на устройстве на основе процессора, компьютере, терминале, сетевом устройстве, мобильном терминале или терминале мобильной связи.
Согласно еще одному аспекту настоящего изобретения, предусмотрен компьютерный
программный продукт, содержащий участки программного кода, хранящиеся на машинно-считываемом носителе, для осуществления операций вышеупомянутого способа согласно варианту осуществления настоящего изобретения, когда компьютерный
8
BY 12943 C1 2010.02.28
программный продукт выполняется на устройстве на основе процессора, компьютере,
терминале, сетевом устройстве, мобильном терминале, или терминале мобильной связи.
Согласно еще одному аспекту настоящего изобретения, предусмотрен программный
инструмент. Программный инструмент содержит участки программы для осуществления
операций вышеупомянутых способов, когда программный инструмент реализован в компьютерной программе и/или выполняется.
Согласно еще одному аспекту настоящего изобретения, предусмотрен сигнал компьютерных данных, воплощенный в несущей волне и представляющий команды, которые, при
выполнении процессором, предписывают выполнять операции способа согласно вышеупомянутому варианту осуществления изобретения.
Согласно еще одному аспекту настоящего изобретения, предусмотрено серверное устройство для моделирования графа дорожной сети. Серверное устройство содержит, по
меньшей мере, компонент для приема информационных данных от совокупности транспортных средств, причем информационные данные содержат позиционные данные и компонент для моделирования графа дорожной сети в соответствии с принятыми данными.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для вычисления первого приближения графа дорожной сети; компонент для профилирования дорог и перекрестков посредством первого
приближения, в результате чего получается граф профилированной дорожной сети, и
компонент для осуществления проверки профилированной сети. Все элементы в графе
профилированной сети обновляются, таким образом, на основании данных, происходящих
от совокупности транспортных средств. Это означает, что все элементы принимают дополнительные атрибуты на основании данных транспортного средства. Операцию профилирования можно также обеспечивать периодически, чтобы гарантировать постоянное
обновление сетевых элементов. Дополнительно некоторые атрибуты, которые можно использовать для операции профилирования, можно собирать из других существующих баз
данных, например, баз данных правительства, дорожно-строительных компаний и т.д.
Данные, соответствующие атрибутам, можно вставлять вручную и/или автоматически для
дополнительного использования на этапе профилирования (а также моделирования). Заметим, что всю собранную информацию можно сохранять и далее использовать в любое
время.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для обнаружения изменений графа дорожной сети на основании принятой информации; компонент для оценивания изменений; компонент для
включения изменений в граф дорожной сети.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для анализа графа дорожной сети на основании принятой
информации и компонент для сообщения результатов анализа третьей стороне.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для осуществления этапа сжатия информации избирательно в моделирующем средстве и/или в совокупности транспортных средств.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для сохранения информации.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для обнаружения наличия явления/эффекта многолучевого
распространения и, дополнительно, компонент для присвоения принятой информации
меньшего весового коэффициента.
Согласно еще одному варианту осуществления настоящего изобретения, сервер дополнительно содержит компонент для измерения размеров дорог посредством средства обеспечения информации положения в совокупности транспортных средств.
9
BY 12943 C1 2010.02.28
Согласно еще одному варианту осуществления настоящего изобретения, принятая информация представляет траекторию, по меньшей мере, одного транспортного средства из
совокупности транспортных средств, причем каждая траектория описывается, например,
кривыми Безье, и сервер дополнительно содержит компонент для усреднения траекторий,
связанных с, по меньшей мере, одним транспортным средством.
Согласно еще одному аспекту изобретения, предусмотрена система для моделирования
графа дорожной сети, содержащая совокупность серверных устройств и совокупность
транспортных средств, обеспечивающих информационные данные.
Кроме того, согласно предпочтительному варианту осуществления настоящего изобретения, кривые Безье можно использовать для моделирования графа дорожной сети.
На протяжении подробного описания и прилагаемых чертежей одинаковые или аналогичные компоненты, блоки или устройства обозначены, для простоты, одинаковыми позициями.
Прилагаемые чертежи призваны обеспечивать дополнительные пояснения изобретения
и включены в описание изобретения в качестве его части. Чертежи иллюстрируют варианты осуществления настоящего изобретения и, совместно с описанием, служат для пояснения принципов изобретения. В чертежах:
фиг. 1 - логическая блок-схема, иллюстрирующая принцип способа в соответствии с
настоящим изобретением;
фиг. 2А - последовательность операций в соответствии с настоящим изобретением;
фиг. 2В - логическая блок-схема, демонстрирующая принцип обнаружения изменений в
соответствии с настоящим изобретением;
фиг. 2С - схема оперативного анализа и передачи данных дорожного движения в соответствии с настоящим изобретением;
фиг. 3 - схема, поясняющая принцип действия системы в соответствии с настоящим
изобретением;
фиг. 4 - блок-схема бортового устройства согласно одному варианту осуществления настоящего изобретения;
фиг. 5 - логическая блок-схема, демонстрирующая принцип действия автомата регистрации данных в соответствии с другим вариантом осуществления изобретения;
фиг. 6 - схема, поясняющая принцип усреднения нескольких траекторий, представленных кривыми Безье.
Хотя изобретение описано выше со ссылкой на варианты осуществления согласно прилагаемым чертежам, очевидно, что изобретение не ограничивается ими, но предусматривает ряд модификаций в рамках объема прилагаемой формулы изобретения.
В нижеследующем описании представлена система в соответствии с настоящим изобретением, которая обеспечивает формирование и проверку цифровой, предпочтительно,
векторизованной (или описываемой посредством кривых) модели дорожной сети, эффективное обновление цифровой модели дорожной сети, профилирование (задание атрибутов) цифровой дорожной сети. Для решения вышеупомянутой задачи система использует
сохраненные данные маршрута, полученные от большого количества транспортных
средств, оборудованных приемниками системы позиционирования (GPS, GALILEO и пр.),
передающими свои позиции и другие данные на сервер.
Эти приемники, предпочтительно, оборудованы также беспроводными передатчиками
данных, которые передают сохраненные данные о пройденном маршруте в определенные
моменты времени, более или менее часто, причем, согласно другому варианту, данные от
приемника вручную считываются и затем переносятся в центральное хранилище.
Объем данных, которые точно описывают маршруты, очень велик. Поэтому необходимо особое сжатие либо до передачи данных в центральный пункт (для снижения стоимости связи), или до их сохранения. Все данные могут храниться на удаленном сервере или
их совокупности, и особые программные инструменты можно использовать для объеди-
10
BY 12943 C1 2010.02.28
нения всех имеющихся данных из нужного набора данных, соответствующих анализируемой географической области.
На фиг. 1 схематически показан принцип настоящего изобретения на основании схемы
информационных потоков. Последовательность операций в соответствии с изобретением
можно начинать любыми средствами. Операция начала может обеспечиваться автоматически, посредством пользовательского ввода и т.п. Предполагается, что последовательность операций активируется или начинается, соответственно, в случае приема или
определения новых данных.
На следующем этапе работы 100 обеспечивается прием данных, причем прием данных
может представлять собой непрерывный или периодически повторяющийся процесс. Эта
операция соответствует получению данных, которое будет описано ниже. На следующем
этапе работы моделируется 150 граф дорожной сети. Все вычисления и операции моделирования могут базироваться на кривых Безье, как описано ниже. По окончании всех этапов моделирования и вычисления способ может подойти к концу и может возобновиться,
что соответствует новой операции согласно фиг. 1.
Также предполагается, что на этапе моделирования 150 можно принимать дополнительную информацию от других средств в системе. Это означает, что новыми итерациями
и т.п. можно управлять посредством внешних процессов или операций или даже посредством, например, пользовательского ввода. При приеме дополнительных параметров, соответствующих информации от совокупности транспортных средств, этап моделирования
150 может возобновляться, пока не будет достигнут желаемый результат.
Согласно фиг. 2А-2С, система может действовать следующим образом. В общем случае
существуют три основных процесса. Первый процесс, показанный на фиг. 2А, представляет
собой начальное вычисление, которое дает первый результат для графа дорожной сети.
Второй процесс, показанный на фиг. 2В, может повторяться периодически, например,
раз в месяц. Это снабжает систему регулярным обновлением изменений в системе дорожной сети. Изменения могут соответствовать либо изменениям размера (геометрии и/или
топологии) дорожной сети, либо ее статистики (атрибутов). Другие изменения, используемые для обновления, можно реализовать в рамках объема настоящего изобретения.
В третьем процессе, показанном на фиг. 2С, осуществляется непрерывный анализ текущего состояния дорожного движения. При обнаружении конкретной ситуации (с высокой статистической вероятностью) система сообщает о ней соответствующему
получателю (в центр управления движением, полиции и т.д.).
На фиг. 2А представлен процесс, представляющий начальное вычисление графа дорожной сети. На первом этапе работы осуществляется сбор данных 200. Это означает, что
совокупность надлежащим образом оборудованных транспортных средств доставляет/передает информацию положения, например, на центральный сервер. Предполагается, что
передача может осуществляться периодически или даже вручную. Это означает, что полученные данные, находящиеся в данный момент в хранилище транспортного средства,
нужно каким-то образом передавать, например, на центральный сервер или провайдеру.
На следующем этапе работы, 210, может производиться вычисление первого приближения
дорожной сети, в которой приближение соответствует начальному графу дорожной сети.
Согласно первому набору информации положения, можно осуществлять первое вычисление приближения графа. Это первое приближение соответствует предварительному представлению дорожной сети и, конечно, подлежит исправлению и ревизии. Затем
осуществляется профилирование 310 дорог и/или перекрестков. На этом этапе можно добавлять некоторые параметры, например, направление дороги и/или тип перекрестка, а
также другие атрибуты, как средняя скорость, время (необходимое для прохождения определенного соединения или расстояния соответственно) и т.п., которые можно проверять
согласно этапу 215. На этапе 215 проверки можно осуществлять первую проверку первого
приближения, после чего граф можно постоянно развивать и/или расширять. Основное
11
BY 12943 C1 2010.02.28
различие между этапами 215 и 225 состоит в том, что этап 215 предпочтительно осуществлять на графе в целом, тогда как этап 225 осуществляется только на определенных выявленных/определенных изменениях.
На фиг. 2В представлен принцип обновления и актуализации первого приближения.
Этап сбора данных аналогичен вышеупомянутому этапу согласно фиг. 2А. Надлежащим
образом оборудованные транспортные средства постоянно доставляют данные информации положения и прочие данные. Эти данные также могут содержать информацию о типе
транспортного средства, водителе и т.д. На следующем этапе 220 можно производить
сравнение между существующими данными, включенными в существующий граф, и
вновь принятыми данными. В результате может передаваться список изменений или даже
новых дорог и т.д., т.е. способ позволяет актуализировать первое приближение. Этап актуализации описан со ссылкой на этап работы 225 на фиг. 2В, и изменения могут содержать изменения в структурах графа, например, упразднение существующих дорог или
добавление новых или даже его атрибутов (например, скорости, времени, правил дорожного движения и т.д.).
Заметим, что ввод на этапе 220 (фиг. 2В) может быть результатом последовательности
операций в соответствии с фиг. 2А (или какого-либо другого графа) или, в будущем, выходом последовательности согласно фиг. 2В и, дополнительно, фиг. 2С.
На фиг. 2С показана последовательность операций согласно настоящему изобретению,
в которой обеспечивается оперативный анализ состояний дорожного движения и сообщаются его результаты. Вышеупомянутый сбор данных 200 осуществляется постоянно, и
система в соответствии с настоящим изобретением способна анализировать существующие данные дорожного движения. Этот анализ 230 может базироваться на теории вероятностей, т.е. можно осуществлять операцию вероятностного и/или прогностического
мониторинга движения. Согласно настоящему изобретению, результаты анализа 230 можно дополнительно сообщать третьей стороне. Третья сторона может соответствовать центральному пункту мониторинга движения или даже транспортному средству, или
водителю соответственно. В рамках объема настоящего изобретения существует большое
количество допустимых конфигураций.
Перейдем к подробному рассмотрению задачи получения или сбора данных. Устройство, расположенное на транспортном средстве (бортовое устройство) из совокупности
транспортных средств, может обеспечивать его позицию с использованием, например,
сигнала GPS (это также может быть другая аналогичная система, например, Galileo) и
возможно некоторых устройств счисления пути (например, гироскопа) ежесекундно, поскольку это обычно наименьший интервал времени, который могут поддерживать приемники GPS. Если измерения связаны прямыми линиями, они очень хорошо описывают
форму дороги. Проблема состоит в объеме этих данных. Вот почему необходимо сжатие.
Сжатие данных обеспечивает ряд преимуществ: сокращение объема данных, передаваемых на центральный сервер, сокращение размера базы данных, сокращение времени (последующей) обработки.
Также предусмотрено, что форма дороги описывается очень точно, т.е. ошибка не превышает ширины дороги или в общем случае геометрии дороги. Поэтому необходимо правильно и, по существу, без потерь сжимать данные формы.
С этой целью для описания формы дороги можно использовать кривые Безье третьего
порядка. Кривые Безье обеспечивают очень гибкое и геометрически простое представление. Эти кривые могут описывать формы U и S, точки возврата и петли. Можно использовать и другие кривые, например, кривые Безье более высоких порядков, дуги, многочлены
и т.д., другой возможный признак состоит в описании также других информационных
данных, а не только формы траектории. Помимо скорости транспортного средства, можно
обеспечивать и делать доступными обороты двигателя, и т.д.
12
BY 12943 C1 2010.02.28
В общем случае термин "траектория" относится к описанию путешествия/поездки или
перемещения транспортного средства в определенных условиях. Это означает, согласно
тривиальному описанию, что движение некоторого автомобиля можно представить линией (кривой), причем каждая точка линии описывает фактическое географическое положение (может быть включена также высота) транспортного средства. Предполагается также,
что каждая точка траектории связана с фактическими скоростью, ускорением транспортного средства и т.п., что предпочтительно для дальнейшего вычисления или моделирования.
Задание интервала времени между двумя регистрационными записями.
Интервал времени между двумя регистрационными записями в значительной степени
зависит от формы дороги. Термин "регистрационная запись" относится к сохранению определенной информации от совокупности транспортных средств. Бортовое устройство
может регистрировать несколько позиционных данных до отправки их на сервер. Позиционные данные соответствуют маршруту (траектории) перемещения транспортного средства. Данные можно отправлять спонтанно без сохранения или, как упомянуто выше,
позиционные данные можно накапливать (главная задача компонента 415), а затем отправлять.
В общем случае длинный участок магистрали можно хорошо аппроксимировать одной
кривой; с другой стороны, извилистая горная дорога имеет лишь короткий участок, который можно описать одной кривой. Интервал времени обычно длиннее на главных дорогах. Задача состоит в том, чтобы получить описание дороги (пути или траектории
транспортного средства) с минимальным количеством элементов, а также с минимальной
ошибкой.
Поэтому может понадобиться эвристическое приближение. Бортовое устройство имеет
буфер, содержащий ряд последовательных измерений. Длина буфера равна длине наибольшего интервала времени между последовательными регистрационными записями (если измерения имеют достоверные позиции, т.е. если бортовое устройство не находится в
туннеле или гараже без гироскопа). Предпочтительно, можно задавать наименьший разрешенный интервал времени. Таким образом, можно получить нижнюю и верхнюю границы качества сжатия согласно изобретению.
Кроме того, поскольку не все данные измерений доступны (буфер слишком мал), можно использовать эвристический подход для определения подходящего представления траектории определенного транспортного средства.
Основная идея состоит в том, что измерения в буфере аппроксимируются кривой (например, кривой Безье) с заранее определенной периодичностью, например, ежесекундно.
Если уже осуществленное приближение является достаточно хорошим, можно опустить
некоторые измерения для экономии ресурсов для расчета приближения в будущем. Если
приближение превышает заранее заданный порог ошибки, процесс нужно остановить и
зарегистрировать (сохранить) существующую кривую с измерением на ее конце, и очистить буфер. Таким образом, можно гарантировать малую ошибку (ниже заранее определенного порога) (не связанную с ошибкой GPS!) в описании дороги. Существуют и другие
условия, инициирующие регистрацию данных текущих измерений.
Согласно настоящему изобретению, можно регистрировать измерения, имеющие большую вторую производную скорости, предпочтительно, превышающую опорное значение.
В этих точках ускорение изменяется наиболее резко. При постоянном ускорении форма
дороги изменяется постепенно. Легче описать форму дороги между точками максимума
второй производной скорости.
Согласно настоящему изобретению, можно задавать порог для второй производной. В
случае превышения этого порога в определенном измерении кривую до этого измерения
(совместно с ним) можно зарегистрировать. Таким образом, согласно настоящему изобретению, достигается минимальное количество элементов в описании дороги.
13
BY 12943 C1 2010.02.28
Текущие (или последние удовлетворительные) кривая и измерение регистрируются, если выявляется ненормальное поведение сигнала GPS, например, явление многолучевого
распространения или потеря сигнала (например, при въезде в туннель). Таким образом,
можно избежать ошибок или ложных измерений. Явление или эффект многолучевого распространения, соответственно, означает, что сигналы GPS от спутников испытывают отражение или помеху со стороны других сигналов, в результате чего в передачу данных
или сигнала может вкрадываться ошибка. В этом случае приемник определяет текущую
позицию с ошибкой.
Вышеупомянутая основная идея применима и к другим величинам (например, скорости), а не только к форме дороги. Измерения этой величины ежесекундно аппроксимируются, и, если приближение не достаточно хорошо, процесс аппроксимации можно
остановить, и затем последнее удовлетворительное приближение можно зарегистрировать. При измерении скалярных величин (чисел) предполагается использовать, например,
многочлены вместо кривых.
Экспериментальные наблюдения показывают, что вышеупомянутое приближение позволяет регистрировать данные каждые 30-40 секунд (в среднем) для описания формы дорог с точностью до нескольких метров. Согласно настоящему изобретению, наблюдения
аппроксимируются посредством кубических кривых Безье. В противном случае интервалы времени могут существенно отличаться. В общем случае, чем выше порядок кривой,
тем больше интервал времени между регистрационными записями (промежуток времени
между двумя последовательными позициями регистрационных записей).
Эффект или явление многолучевого распространения.
Одна из важнейших проблем, возникающих при попытке точного описания формы дороги, представляет собой явление многолучевого распространения. Если оно длится короткий период времени, его можно обнаружить на основании: различия между
направлением, сообщаемым приемником GPS, и направлением, вычисленным из координат GPS, и увеличенной расчетной ошибкой координат.
В случае обнаружения этого явления измерениям, полученным в этих условиях, присваивается меньший весовой коэффициент, чем другим измерениям, когда измерения аппроксимируются согласно настоящему изобретению. Поэтому более точные измерения
оказывают большее влияние на форму кривой.
Предполагается, что измерения (и кривые) регистрируются или сохраняются до того,
как происходит это явление. Причина в том, что измерения (и кривые) до явления не повреждены. Если явление не превышает максимальный интервал времени, предпочтительно ничего не регистрировать, пока явление не закончится. Однако верные кривые или
приближения опираются, в основном, на верные измерения. В случае выявления эффекта
многолучевого распространения предполагается, что измерения, произведенные в этот период (во время эффекта многолучевого распространения), отбрасываются. Такой же подход применяется просто в случае увеличения расчетной ошибки.
Применение фильтра Калмана к устройствам GPS.
Другая трудность связана с тем, что известный в технике фильтр Калмана, входящий в
состав приемника GPS, работает не очень хорошо при низкой скорости приемника GPS.
Поэтому сообщаемое местоположение GPS дрейфует, когда транспортное средство стоит
на месте. Это может создавать серьезную проблему в городах с большим количеством дорожных пробок.
Решение этой проблемы состоит в том, чтобы ничего не регистрировать при низкой
скорости транспортного средства (например, ниже 3 км/ч). Согласно настоящему изобретению, измерение (с кривой) можно регистрировать, как только обнаруживается, что
транспортное средство остановилось, и сразу же после начала движения. Измерения, произведенные при низкой скорости, можно отбрасывать, и дальнейшие этапы аппроксимации можно блокировать, и просто соединять прямой линией (линией) последовательные
14
BY 12943 C1 2010.02.28
регистрационные записи (непосредственно до остановки транспортного средства и сразу
после начала его движения).
Обе вышеописанные проблемы решаются, если бортовое устройство имеет устройство
счисления пути (гироскоп), но это увеличивает стоимость бортового устройства.
Еще одна проблема связана с граничными условиями; обработкой начала и конца работы, временными сбоями и т.д.
Согласно возможному варианту осуществления настоящего изобретения, можно предусмотреть следующую реализацию Соответственно, ежесекундно измеряются следующие
величины:
координаты GPS - позиция (P(t)),
оценка горизонтальной ошибки (сигма), вычисленная приемником GPS,
вектор скорости, вычисленный приемником GPS (WGS84 азимут, скорость (узлы)),
вектор скорости, вычисленный из координат GPS ((P(t + 1)-P(t-1))/2),
ускорение (из азимута GPS),
ускорение (из координат GPS),
производная ускорения (из азимута GPS),
производная ускорения (из координат GPS),
информация о достоверности данных (см. следующий список):
0 нет азимута, нет координат,
1 нет азимута, есть координаты,
2 есть азимут, нет координат,
3 есть азимут, есть координаты.
Вышеприведенный список приведен исключительно в порядке примера, и настоящее
изобретение им не ограничивается.
Также необходимо знать, была ли позиция вычислена приемником GPS или устройством счисления пути. Дополнительно, в рамках объема настоящего изобретения, можно
измерять и другие величины.
Если вектор скорости, вычисленный приемником GPS (Vs), и вектор скорости, вычисленный из координат GPS (Vk), сильно отличаются, и оценка ошибки (сигма) возрастает,
очень вероятной причиной может быть явление многолучевого распространения.
Ряд этих измерений сохраняется в буфере. Длина этого буфера (Max) представляет собой максимальный интервал времени для аппроксимированной кривой. Минимальный
интервал времени (min) можно задавать для каждой кривой. Однако интервал обеспечивает нижнюю границу качества сжатия и позволяет не регистрировать последнее измерение
в буфере. Кроме того, измерение, которое было произведено за min секунд до текущего
измерения, можно регистрировать. В случае регистрации измерения, которое было произведено за r(<min) секунд до текущего, то буфер не полностью очищается - последние r измерений могут оставаться в буфере. При использовании циклического буфера не
требуется сдвигать эти r измерения в начало буфера. Таким образом, реализация, согласно
одному варианту осуществления настоящего изобретения, предусматривает сохранение
начальной и текущей позиций в буфере.
Иногда предусматривается регистрация данных измерения до текущего измерения.
Иногда для обнаружения определенного явления необходимо производить несколько последовательных измерений. Например, пять последовательных измерений можно использовать для вычисления производной ускорения в среднем (третьем) измерении. В данную
секунду вычисляется производная за две секунды до этого. Если эта производная достаточно велика, измерение (с кривой) две секунды назад можно регистрировать в соответствии с настоящим изобретением. Затем буфер очищается, только последние 3(= r)
измерения остаются в буфере. Блок не обязан производить какую-либо аппроксимацию в
течение нескольких секунд, пока min измерения находятся в буфере. После этого продол-
15
BY 12943 C1 2010.02.28
жается обычная процедура. Производная функция сглаживается с использованием ортогональных многочленов на 5 последовательных измерениях.
Можно использовать дополнительный буфер, в котором хранятся последние min аппроксимированные кривые, если, например, необходимо регистрировать кривую несколько секунд назад.
В общем случае существует несколько граничных условий. Первое измерение (с достоверной позицией) нужно регистрировать. То же справедливо для последней позиции, после выключения двигателя. Последнюю позицию вне туннеля (с достоверной позицией
GPS) нужно регистрировать. Также предусмотрено задание порога u, указывающего,
сколько секунд подряд позиция GPS должна быть недостоверной, чтобы пометить ее как
начало туннеля. Это делается для того, чтобы можно было отбрасывать очень короткие
туннели или ошибки, шумы в приемниках GPS. После того, как измерение зарегистрировано как начало туннеля, первое измерение с достоверной позицией GPS в качестве конца
туннеля должно быть зарегистрировано. Если бортовое устройство не содержит устройство счисления пути, эти две регистрационные записи соединяются прямой линией. Интервал времени между двумя регистрационными записями может превышать Max только в
этом случае. Если бортовое устройство имеет устройство счисления пути (гироскоп), процедура регистрации данных в туннеле производится как обычно.
В следующем разделе описан выбор этапа регистрации данных (регистрационной записи) в соответствии с одним вариантом осуществления настоящего изобретения. Например,
в данное время t измеряются следующие три величины (значения): A(t) = величина производной ускорения (скаляр), V(t) = разность векторов скорости |Vs-Vk| (скалярное представление), S(t) = сигма, расчетная ошибка (скалярное значение).
Если A(t) превышает заранее определенный порог, то измерение является элементом
(предметом) регистрации. Если взвешенная сумма V(t) и S(t) превышает другой порог
(вследствие возможного возникновения эффекта многолучевого распространения), то:
если (t-1) > min, то нужно регистрировать предыдущее измерение (чтобы не повредить
текущее приближение кривой), иначе
если t < Max, то t-e измерение не следует регистрировать (поскольку эффект многолучевого распространения может вскоре закончиться и, таким образом, возможны правильные конечные измерения и приближения кривой).
Если нужно найти и зарегистрировать измерение с большой производной и малыми
оценками многолучевого распространения и ошибки. Могут существовать два граничных
значения: минимальное время до новой регистрационной записи (min), максимальное
время до новой регистрационной записи (Max).
На фиг. 5 представлен автомат в соответствии с настоящим изобретением. Например:
(L обозначает регистрацию 530, m, 510 это ежесекундное измерение).
Это автомат (согласно фиг. 5), который имеет временное состояние:
Lmmmmmmmmmmmmmmmmmmm… = L + c⋅m
Автомат осуществляет основной Цикл:
L + c⋅m
If количество текущих измерений с больше min и меньше Max
then
if триггер задан равным t, t > min, t < Max, (c-t) < min, измерение t в последовательности
регистрируется, и последовательность очищается до L + (c-t)⋅m
else
L + (c + l)⋅m
goto Цикл
Триггер (520) может состоять из нескольких частей:
А) если вторая производная скорости больше предписанного порога, это означает, что
измерение в t1: = c-2 является кандидатом для регистрации;
16
BY 12943 C1 2010.02.28
B) если явление многолучевого распространения вероятно происходит в t2: = c-1 (различие между направлениями велико, и расчетная ошибка увеличилась), то
1. если m(t2-1) не имела многолучевого распространения и (t2-1) > min, то m(t2-1) является кандидатом для регистрации, иначе (в противном случае)
2. если t2 < Max, m(t2) не следует регистрировать;
C) если вычисленная кривая в с недостаточно хорошо аппроксимирует измерения, и
кривая в t3: = c-1 делает это хорошо, то m(t3) является кандидатом для регистрации;
D) если измеряются другие скалярные величины (например, скорость) и приближение
измерений не достаточно хорошо, то m(t4) совместно с кривой и аппроксимирующей
функцией этой величины следует регистрировать, t4: = c-1. Затем выбирается минимальный tm кандидатов для регистрации (t1, t2, t3, t4). Новой регистрационной записью является m(tm) с соответствующей кривой и, возможно, аппроксимирующими функциями
других величин.
При попытке аппроксимировать кривую измерения позиций они взвешиваются весовым коэффициентом, который убывает с ростом вероятности многолучевого распространения. Если аппроксимация осуществляется посредством арифметических операций с
фиксированной точкой, нужно производить некоторые особые измерения.
Предусмотрены также некоторые другие граничные условия: регистрируется первая
достоверная позиция после начала; регистрируется последняя достоверная позиция (при
выключении автомобиля); регистрируется последнее измерение до туннеля (до того, как
позиции GPS становятся недостоверными); регистрируется первое измерение после туннеля.
Кривые Безье.
Ниже приведено краткое введение в кубические кривые Безье, где обеспечены преимущественные адаптации в соответствии с настоящим изобретением.
Эти кривые, в общем случае, задаются 4 контрольными точками с P0 по P3. Кривая лежит в выпуклой оболочке контрольных точек. Кривая начинается в первой контрольной
точке и заканчивается в последней. Начальное направление кривой равно направлению
между первыми двумя точками и конечное направление равно направлению между последними двумя точками.
Кривые Безье численно задаются многочленами Бернштайна над контрольными точками Pk.
N
N!
t k (1 − t )N −k ; 0 ≤ t ≤ 1 описывает кривую, параметризованную t.
B(t ) = ∑ pk
k!(N − k )!
k =0
Кривые можно разбивать посредством алгоритма де Кастелье (не показан).
Еще один вопрос состоит в аппроксимации кривыми Безье в соответствии с принятыми
или предоставленными измерениями. Если мобильные блоки (или устройства) имеют
блок цифровой обработки сигнала с фиксированной точкой, можно использовать только
арифметические операции с фиксированной точкой, поэтому ошибку вычислений, обусловленную вычислением с фиксированной точкой, нужно минимизировать или устранять. Первое усовершенствование в соответствии с настоящим изобретением состоит в
использовании алгоритмов CORDIC (цифровой расчет координат) для вычисления норм
векторов (или кривых) и т.д.
Второе усовершенствование в соответствии с настоящим изобретением состоит в выборе ограничивающего прямоугольника (неплотный) измерений их нормализации согласно размеру ограничивающего прямоугольника и диапазону чисел (арифметические
операции с фиксированной точкой).
Согласно уровню техники предусмотрена только регулировка длины тангенциальных
(контрольных) векторов кривой (между первой и второй парами контрольных точек), но
также необходимо изменять направление.
17
BY 12943 C1 2010.02.28
Ниже показано, как можно добиться большей гибкости формы аппроксимирующей
кривой в соответствии с изобретением.
Приведем следующие определения:
V1 = V0 + α1t1 + β1t1p ,
V2 = V3 + α 2 t 2 + β 2 t p2 ,
где Vi - контрольные точки кривой и ti - контрольные (тангенциальные) векторы на концах
кривой, t pj перпендикулярен tj, αj обозначает поправочный коэффициент для длины контрольного вектора и βj обозначает поправочный коэффициент для направления. Решение
относительно значений βj аналогично решению относительно αj, которое описано в уровне техники.
Процедура аппроксимации может циклически повторяться, и цикл может содержать
два этапа: регулировку длины и регулировку направления контрольных векторов.
Согласно настоящему изобретению, предусмотрено измерение расстояний посредством
сигналов или информации GPS соответственно. Можно измерять длину маршрута с помощью системы GPS. При наличии измерений, которые производятся ежесекундно (некоторые могут быть пропущены), предполагается суммировать расстояния между всеми
последовательными парами и получить очень точную оценку фактической длины. При
низкой скорости (например, ниже 3 км/ч) измерения можно отбрасывать согласно одному
варианту осуществления настоящего изобретения.
Сохранение данных.
Все данные и информация, используемые в настоящем изобретении и поступающие от
совокупности транспортных средств, можно сохранять в центральном пункте (сервере) и
впоследствии анализировать на паре каскадов, например, для достижения желаемого результата. Эти введенные данные предпочтительно называть необработанными данными.
Необработанные данные могут включать в себя, по меньшей мере, одно из: позиции, скорости, азимута (направления), времени получения данных, но также могут включать в себя: описание кривой (траектории), описание функции других величин (скорости и т.д.),
оценку горизонтальной точности позиции, принятой приемником позиции, количество
спутников (GPS) с хорошим сигналом, данные от других датчиков транспортного средства
(температуру, вес) и т.д. Необработанные данные можно сохранять так, чтобы движение
(путь или траектория) транспортного средства хранилось в виде отдельного набора данных, однако идентификатор транспортного средства может быть зашифрован (хэширован)
или даже отсутствовать для обеспечения конфиденциальности.
Данные транспортного средства могут содержать два атрибута, дополнительно помогающие идентифицировать данные маршрута: тип транспортного средства (пассажирский
автомобиль, фургон, грузовик, автобус, мотоцикл, строительная машина, трактор,…), назначение транспортного средства (пассажирский, полицейский, строительный, такси, муниципальный автобус, военный, сельскохозяйственный,…).
Вышеупомянутые два атрибута могут помогать дифференцировать дорожную сеть общего пользования и дороги, используемые специальными транспортными средствами (например, тракторами), и дороги, используемые конкретной службой с расширенными или
ограниченными правами (полицией, военными, такси и т.д.).
Вычисление дорожной сети.
Сначала необработанные данные анализируются для обеспечения векторов (кривых),
представляющих дороги и организованных в ориентированный граф (как в общеизвестной
в математике теории графов). Этот процесс нуждается в небольшом количестве очень
точных измерений (согласно традиционному подходу в практической геодезии) или
большом количестве менее точных измерений, которые дают высокую точность после усреднения. Согласно настоящему изобретению, сосредоточимся на втором случае.
18
BY 12943 C1 2010.02.28
Ребрами графа являются улицы, и вершинами графа являются соединения нескольких
дорог. Геометрически ближайшие вершины представляют перекрестки. Таким образом, в
нижеследующем описании все операции будут получены из стандартной теории графов.
Результирующим графом является базовый граф дорожной сети. Проще говоря, в результате анализа необработанные данные от большого количества транспортных средств,
прошедших по одному и тому же пути, преобразуются в один вектор (кривую), представляющий дорогу, по которой осуществляется движение. Этот процесс вовсе не тривиален.
Заметим, что данные могут не полностью соответствовать правилам дорожного движения,
поскольку некоторые водители могут нарушать их.
Конечной целью является создание двухмерной карты. Можно также включать информацию о высоте над уровнем моря, если измерения достаточно точны. Необходимо правильно вычислять два свойства дорожной сети: геометрию, т.е. точные позиции осей
дорог; топологию, т.е. истинные соединения между дорогами.
Геометрия, в основном, вычисляется путем усреднения траекторий транспортных
средств, движущихся по одной и той же дороге. Топология, в основном, вычисляется путем определения, какие траектории соединяют какие дороги. Существует несколько стратегий вычисления дорожной карты. Описано два основных приближения: локальная и
глобальная версии. Можно определить расстояние между выборочными точками дорог
согласно обоим из них.
Локальная версия сосредоточена более локально (в отношении расстояния). Она продвигается локально на предписанное расстояние между выборочными точками. Она сосредотачивается на плотности результирующего графа. Это вычисление карты базируется
на двух этапах: вычислении участков дороги и вычислении перекрестков дорог.
Основной операцией является вычисление единой кривой между двумя выборочными
точками, соответствующей усреднению измерений. Согласно экспериментальным тестам,
было выбрано расстояние 100 м между двумя выборочными точками. Согласно настоящему изобретению, предпочтительно описывать участки дороги между двумя выборочными точками как прямую линию, если расстояние между точками составляет около 20 м.
Таким образом, возникающая ошибка является незначительной, и участок дороги представляется надлежащим образом.
Согласно настоящему изобретению, кривые Безье можно использовать для представления траекторий транспортных средств и выведенных из них усредненных траекторий в
виде графа, в силу их численной устойчивости и геометрической гибкости и четкости.
Усреднение кривых Безье.
Эта процедура является частью настоящего изобретения и используется для вычисления геометрии дорог, но может использоваться и в других целях. Согласно рассмотренному выше, обеспечивается совокупность траекторий, обеспечиваемых совокупностью
измеряющих транспортных средств. Каждая траектория каждого транспортного средства
описывается последовательными кривыми Безье в соответствии с настоящим изобретением. Эти кривые обычно имеют разную длину. Для получения точной геометрии оси дороги или подучастка дороги, соответственно, можно предусмотреть этап усреднения всех
имеющихся траекторий согласно настоящему изобретению. Усредненные кривые должны
быть достаточно короткими для достаточно точного описания всех деталей дорожной сети. Соответственно используются усредненные кривые Безье длиной менее 100 м.
В следующем разделе описан этап усреднения множества траекторий, описываемых
кривыми Безье в соответствии с настоящим изобретением. Задача состоит в усреднении
нескольких траекторий. Сначала можно выбрать начальную и конечную точки для каждого усреднения. Начальную и конечную точки, между которыми усредняются траектории,
можно также задать как линию, перпендикулярную траекториям согласно настоящему
изобретению.
19
BY 12943 C1 2010.02.28
Предполагается, что среднюю траекторию между начальной и конечной точками (линию) можно достаточно хорошо описать кривой Безье согласно изобретению.
До усреднения данные кривые в точках, ближайших к выбранным начальной и конечной точкам (или линиям), можно разбивать. Таким образом, получается результат, соответствующий подучасткам траекторий, которые весьма подобны.
Существует несколько путей осуществления усреднения согласно изобретению:
1. Если все подучастки между начальной и конечной точками описываются единичными кривыми, предпочтительно просто усреднять контрольные точки подучастков. В противном случае можно выбрать другой способ усреднения, который описан ниже.
2. Усреднение:
Начальные и конечные координаты этих подучастков.
Скорости (длины контрольных векторов) в этих начальных и конечных координатах.
Длины подучастков.
Различия во времени каждого подучастка между начальными и конечными координатами. Таким образом, обеспечивается достаточно данных для прогнозирования траектории (см. следующий раздел).
3. Аппроксимация измеренных позиций новой кривой Безье (координаты - точки на исходных кривых) в этом подучастке (см. раздел о сжатии данных). При недостаточном количестве измеренных позиций предпочтительно произвольно добавлять точки на кривых.
Заметим, что неиспользование позиций может привести к большой ошибке. Использование позиций, которые очень близки к начальной или конечной точке каждого подучастка,
может быть неблагоприятным, поскольку ошибка в этих позициях оказывает большее
влияние на форму кривой, таким образом, иногда могут появляться маленькие петли.
Прогнозирование и определение траектории.
В случае, когда траектории не описываются кривыми Безье, но измерения достаточно
близки, траекторию можно прогнозировать и описывать, выбирая кривую Безье следующим образом.
Без сжатия, данные от транспортных средств состоят из позиций, направлений (азимутов) и скоростей в этих позициях и времени и расстояния между последовательными позициями. Для вычисления дорожной карты необходимо иметь информацию о том, какова
была траектория между этими позициями. Если зарегистрированное расстояние совпадает
с длиной предложенной кривой, ее можно считать удовлетворительной.
Согласно следующим значениям: начальной и конечной точкам траектории, вектору
скорости в начале и конце, расстоянию, времени, необходимому для прохождения этого
пути, можно обеспечить этап прогнозирования траектории между этими точками.
Согласно настоящему изобретению, траекторию можно прогнозировать или вычислять
посредством кривой Безье 3-й степени. Начальная и конечная точки фиксированы и являются первой и последней контрольными точками, которые используются в методах кривых Безье. Затем можно определить позицию посередине между двумя контрольными
точками. Вторая контрольная точка получается из первой путем прибавления вектора скорости, и третья контрольная точка получается из последней путем вычитания вектора скорости. Затем нормализованные векторы скорости умножаются на соответствующий
коэффициент (например, скорость [м/с]⋅время[c]/3) для первого приближения этих точек.
Затем можно вычислить длину кривой и, при необходимости, отрегулировать (см. следующий раздел).
Регулировка длины кривой Безье.
Полезно задавать приближение кривой с помощью правильных направлений. Длина
предусмотрена как дополнительный фактор, если осталось только две степени свободы длина начального и конечного векторов. Эта процедура изменяет оба вектора равномерно,
поскольку скорости обычно не изменяются очень резко. Если кривая короче фактических
данных, предпочтительно удлинить векторы скорости (контрольные); а если она длиннее,
20
BY 12943 C1 2010.02.28
предпочтительно укоротить векторы и повторить процесс. Когда фактическая и необходимая длины достаточно близки, последовательность операций можно остановить. Тем не
менее регулировка обеспечивается в итерационном режиме, что позволяет получить желаемый результат после определенного количества операций.
Вычисление участков дороги.
Это этап, на котором можно вычислять участки дороги между перекрестками дорог.
Этот этап сосредотачивается на геометрии дорожной сети. Согласно изобретению, начальную точку выбирают произвольно, и последовательность операций продолжается посредством вышеописанной базовой операции вдоль измерений, пока измерения
разделяются. Это сигнал для перекрестка. Предполагается также продолжать участок назад для получения полного участка между перекрестками.
Вычисление перекрестка дорог.
Вычисление перекрестков дорог является отдельным этапом, поскольку геометрия и
топология дорожной сети наиболее сложны на перекрестках. Этот этап базируется на топологии. Измерения (регистрационные записи или части кривых) приписываются соответствующим участкам дороги. Все измерения, ведущие от одного участка дороги к
другому, собираются. Они подобны потоку из одной трубы в другую. Вышеописанная базовая операция применяется к собранным измерениям. Предпочтительно только соединять два существующих участка с вновь вычисленным "поточным" участком. То же самое
осуществляется для всех комбинаций из двух участков дороги, которые соединены измерениями.
Такую же процедуру можно повторять на результирующем графе или осуществлять на
нескольких графах из разных источников (государственных учреждений, дорожностроительных компаний и т.д.), а не только опирающихся на измерения из нашей системы.
Глобальное вычисление.
Глобальная версия в большей степени ориентирована на геометрическую точность. Она
требует длинных путей (по меньшей мере, 500 м) в измерениях. Она также позволяет дополнять частичный граф.
Вычисление участка дороги.
Сначала выбираются начальная и конечная точки участка дороги. Затем все измерения,
идущие от начальной точки к конечной и имеющие примерно одинаковую длину, собираются. Вышеописанная базовая операция применяется к собранным данным. Малую
часть (100-500 м) участка в конечных точках можно отбросить во избежание менее точных результатов.
Присоединение участка дороги к существующему графу.
Когда участок дороги уже вычислен, его можно присоединить к существующему графу. Можно присоединять только подучастки, которые не включены в существующий
граф.
Вычисление графа.
Кроме того, нужно повторять первые два этапа, пока не будут использованы все измерения. Первоначально обеспечивается старт с пустым графом, и конечным результатом
является граф части дорожной сети, которая в достаточной степени покрыта измерениями.
Экспериментальные результаты.
Экспериментальные наблюдения показывают высокую точность способа в соответствии с настоящим изобретением. Конечно, точность зависит от количества произведенных
измерений.
Ошибки в топологии вычисленного графа составляют несколько процентов. Ошибки, в
основном, возникают при наличии параллельных дорог, расстояние между которыми составляет меньше удвоенной величины ошибки GPS (обычно 30 метров), и на сложных перекрестках. Причиной тому являются неточность системы GPS и слишком длинный,
фиксированный интервал времени между регистрационными записями. Предполагается,
21
BY 12943 C1 2010.02.28
что процент ошибки можно снизить, применяя способ к сжатым измерениям (динамическому интервалу времени между регистрационными записями с аппроксимированной
кривой) и используя гироскоп в бортовом устройстве. Кроме того, скорости и времена
ожидания совершенно точны.
Профилирование сети.
Кроме того, основной этап работы в соответствии с настоящим изобретением может
состоять в идентификации и профилировании перекрестков. Несколько вершин базового
графа дорожной сети, которые соединены и близки друг к другу, можно объединить в более сложную структуру перекрестка. Базовый граф дорожной сети используется совместно с необработанными данными для анализа перекрестков с целью задания следующих (и,
возможно, других двух) свойств перекрестка: правил дорожного движения (какие дороги
входят в перекресток, какие выходят из него и какие соединяются; имеются ли светофоры;
какие дороги имеют преимущество и т.д.), картины движения (какие дороги являются
главными в перекрестке, каково предполагаемое время пересечения перекрестка), типа
перекрестка (тип креста или звезды, круг, съезды (например, с магистрали) и т.д.), сколько
полос идет в конкретном направлении и т.д. Данные во второй линии можно использовать
для того, чтобы отличать главные дороги от второстепенных, чтобы не отвлекать водителя
при ориентировании в области, где слишком много второстепенных дорог.
Данные вновь сохраняются как граф с дополнительными вспомогательными структурами данных (матрицами и т.д.).
Этих данных, в основном, достаточно для ориентации водителя.
Кроме того, предусмотрено профилирование дорог, см. также фиг. 2А-2С. При большом количестве транспортных средств, движущихся по одним и тем же дорогам, доступен
большой объем статистических данных, например средняя скорость, средняя скорость на
определенное время суток и т.д. Эти данные используются для профилирования соединения (дороги), для присвоения каждому соединению следующих атрибутов: направления
улиц/дорог (одностороннее, двустороннее движение), расстояния, средней скорости или
среднего времени прохождения соединения (в зависимости от часа недели и т.п.), достоверности статистических данных (для проверки, достаточно ли данных, чтобы сказать
что-то существенное о движении по конкретному соединению/дороге), средней напряженности движения (относительной, касающейся других дорог), типа дороги (магистраль,
улица, местная дорога, количество полос и т.д.), времени ее использования (в последний
раз) и некоторых других.
Это делается с использованием графа дорожной сети и необработанных данных. Процесс был подробно описан выше со ссылкой на фиг. 2А-2С и в описании.
Предполагаемое преимущество состоит в том, что (благодаря кривым и аппроксимированной скорости) можно обеспечить скорость в каждой точке траектории (пути) транспортного средства. Это позволяет точно указывать скорости транспортных средств при
пересечении поперечного сечения дороги. Другие величины (значения) можно аппроксимировать аналогично вышеупомянутому примеру, касающемуся скорости, согласно настоящему изобретению.
В общем случае, операцию профилирования можно осуществлять с использованием
уже сохраненных данных дорожного движения в любое время и на любом графе (сгенерированном вручную или даже из других источников).
Если можно наблюдать, когда использовались дороги, можно находить дороги, которые не были использованы (оборудованными) транспортными средствами в течение долгого времени. Весьма вероятно, что такие дороги больше не используются, и их можно
(обычно после некоторой проверки) удалить из базы данных дорожной карты. Это очень
эффективный способ обнаружения вспомогательных дорог (используемых для строительства магистрали или на других стройках) или других дорог, надобность в которых отпала
(см. раздел об обновлении сети).
22
BY 12943 C1 2010.02.28
Результатом является цифровая система дорожной сети, которая верна с геометрической и топологической точек зрения. Она содержит статистические данные, позволяющие
осуществлять очень точное отыскивание быстрейшего пути на основе прошлого опыта
всех транспортных средств, задействованных в схеме. Однако эти данные нужно проверять вручную (с помощью специально оборудованных транспортных средств проверки) во
избежание предложения водителям запрещенных поворотов.
Проверка.
Цифровую систему дорожной сети из предыдущего раздела должны обходить транспортные средства проверки, снабженные специальным оборудованием, для проверки, что
база данных (дорожный граф) соответствует фактической дорожной системе. Поскольку
дорожная система уже оцифрована, можно предлагать водителю точный маршрут, обеспечивающий кратчайшее расстояние. Оптимизацию можно осуществлять с использованием одного из общеизвестных принципов оптимизации маршрута (например, алгоритма
китайского почтальона, известного из теории графов).
Конечно, некоторую корректировку можно производить вручную, до того, как специально оборудованные транспортные средства начнут проверку. Это позволяет дополнительно сократить необходимые затраты. Дополнительная экономия достигается, если эти
транспортные средства посылать только на те дороги и перекрестки, которые были вычислены на основании слишком бедных или недостаточно точных данных. Это особенно
полезно при обнаружении изменений в графе дорожной сети.
Это представляет большое преимущество над другими системами, где отсутствует дорожная система (или, по меньшей мере, какое-либо топологическое "упорядочение") до
проверки. При всяком несоответствии между фактической и цифровой системами дорожной сети водитель должен ввести эти данные в особое оборудование, которое затем предлагает новый маршрут. Изменения могут быть постоянными или временными (которые
меньше влияют на цифровую систему дорожной сети). Этот процесс делает проверку более быстрой и экономичной.
Проверка фактически добавляет или удаляет некоторые улицы (ребра графа) и изменяет соединения, т.е. его топологию. Дороги, по которым, возможно, никогда не ездили
транспортные средства, не обязательно добавлять вручную. При необходимости, транспортные средства проверки пару раз проезжают по дороге для внесения ее в систему.
Очень важный аспект состоит в том, что транспортные средства должны проверять высоту и ширину туннелей или других препятствий, поскольку такие данные очень трудно
получить иным способом. Результатом является цифровая система дорожной сети, которую можно использовать для навигации.
Эти транспортные средства могут быть оборудованы датчиками вибрации для определения качества дороги или другими датчиками, которые могут быть не связаны напрямую
с дорожной сетью, но собирают другую полезную информацию, например, покрытие мобильной сети и т.п.
Обновление графа дорожной сети.
Поскольку бортовые устройства передают данные непрерывно, описанный процесс может повторяться несколько раз в соответствии с этапом обновления. Это делается для того,
чтобы иметь возможность очень быстро обнаруживать новые участки или изменения в дорожной сети и очень быстро проверять те же самые участки посредством вышеописанного
процесса. Поскольку вновь обработанные, необработанные данные, скорее всего, исключают одни и те же улицы и поскольку некоторые из них признаются неверными в процессе
проверки, предполагается обращать на них внимание и помечать их соответственно, чтобы
в процессе обновления избегать отправки персонала проверки без необходимости.
В общем случае, операцию обновления можно осуществлять с использованием данных
дорожного движения в любое время и на любом графе (сгенерированном вручную или
даже из других источников).
23
BY 12943 C1 2010.02.28
Необработанные данные, передаваемые бортовыми устройствами, используются в нескольких целях. Необработанные данные о траектории транспортного средства описываются кривыми. Для каждого участка траектории соответствующие участки дороги и
перекрестки отыскиваются в базе данных. Если их нет в базе данных, этот участок траектории помечается и сохраняется для обновления дорожной сети.
На вышеупомянутом этапе рассматривается вопрос подобия кривых. Он предусмотрен
для отыскания подобных подучастков кривых, чтобы можно было определять, когда определенное транспортное средство находилось на определенной дороге или части дороги
соответственно. Участки, находящиеся вне графа, сохраняются и соответственно помечаются. В начале вычисления для обновления геометрию, топологию и профилирование
можно осуществлять согласно участкам, согласно настоящему изобретению. В этом состоит усовершенствование методов, отвечающих уровню техники, которые предусматривают только обнаружение изменений без каких-либо дополнительных этапов обработки.
Таким образом, подход подобия кривых можно использовать в других целях, например,
в системах электронного толлинга, поскольку он позволяет точно определить, где именно
находится транспортное средство, или, в целом, для распознавания формы.
Главный сервер сравнивает принятые данные с сохраненной информацией дорожного
движения для участков дороги. Если эта информация значительно отличается, это причина для предупреждения. Обычно это указывает наличие дорожной пробки. Если несколько
транспортных средств передают сходную информацию об аномальном движении на конкретном участке дороги, предупреждение даже более уместно. Эта операция осуществляется за пару минут. Данные также используются для последующей обработки. Первый
этап состоит в обновлении информации статистики дорожного движения, касающейся
участков дороги и перекрестков. Участки дороги, соответствующие новым данным, отыскиваются в базе данных, и их информация обновляется.
Участки дороги также имеют информацию о временах проезда. В ходе регулярной проверки (например, ежемесячной) отыскиваются дороги, которые больше не используются и
которые можно удалить из базы данных (после некоторой проверки). С другой стороны,
участки траекторий, не имеющие соответствующих дорог в базе данных, используются
для вычисления новых участков дороги, которые затем добавляются в базу данных.
Подобие кривых Безье.
Для сравнения, например, двух кривых их нужно сначала выровнять. Это выравнивание может включать в себя параллельные переносы, повороты и масштабирование. Подобие между кривыми вычисляется на основании расстояний (евклидовых или других)
между соответствующими парами контрольных точек в соответствии с настоящим изобретением. Это вычисление может представлять собой суммирование, усреднение, нахождение минимума, максимума и т.д. Оно зависит от характера задачи.
Действительно, подобные композиции контрольных точек дают подобные кривые. Обратное не всегда справедливо - можно построить подобные кривые с сильно отличающимися композициями контрольных точек. Задача состоит в параметризации. Это можно
проиллюстрировать на примере прямой линии. Две средние контрольные точки линии
можно поместить где угодно на линии, и кривая будет иметь одну и ту же форму, только
параметризация будет отличаться.
Если рассматривать только форму кривой, а не параметризацию, можно перепараметризовать кривые до расчета подобия. Перепараметризацию можно производить, выбирая
точки на кривых и затем аппроксимируя их другой кривой (см. раздел об аппроксимации
упорядоченного множества точек кривой Безье). Эта кривая должна иметь, в основном, ту
же форму, что и исходная.
Отыскание подобного подучастка на паре кривых.
Эта процедура предусмотрена для вычисления дорожной карты и обновления статистики дорожного движения. Длинная кривая может описывать траекторию транспортного
24
BY 12943 C1 2010.02.28
средства. Дороги так же описываются, как кривые. Предполагается определять, когда
транспортное средство находилось на той или иной дороге, какая часть его траектории
соответствует какой дороге.
Сначала дадим определение подобия кривых. Для сравнения кривых можно использовать.
Абсолютный критерий. В этом случае следует задать минимальную длину сравниваемых подучастков кривых. Короткие отрезки кривых всегда могут быть подобными, поскольку их контрольные точки располагаются близко друг к другу. Также можно задать
некоторые критерии об угле между кривыми (например, между векторами, соединяющими начальную и конечную точки).
Относительный критерий.
Кривые можно выравнивать в начале. Сначала выбирается подкривая второй кривой,
концевые точки которой наиболее близки к концевым точкам первой кривой. Затем рекурсивно повторяется следующая процедура согласно настоящему изобретению.
Если кривые подобны, они регистрируются как подобные части. В противном случае
первая кривая разбивается (посередине), и вторая кривая разбивается максимально близко
к точке разбиения первой кривой. Обе пары подкривых сравниваются.
В конце сообщается о парах подобных подкривых.
Описанная система, согласно варианту осуществления настоящего изобретения, является очень эффективным средством для генерации и профилирования цифровой модели
дорожной сети. Такого рода данные очень полезны в эпоху массовых перемещений. Вместо строительства специальной инфраструктуры для решения задачи анализа дорожного
движения предложенная система использует сравнительно недорогое оборудование для
транспортных средств, которое используется для других полезных целей (навигации, обмена сообщениями, управления флотом в целом), общественную сеть беспроводной передачи данных (GSM/UMTS, CDMA) и особую компьютерную систему для анализа
большого объема данных. Такого рода принцип наиболее полезен для развивающихся
стран, где быстро развивается дорожная система и недостает опытных организаторов для
выполнения сложных операций по построению цифровой модели или, в противном случае, дорожной сети. Существует много вариантов использования этой системы.
Бортовые устройства способны помогать водителю осуществлять навигацию, если они
имеют пользовательский интерфейс, обычно клавиатуру и экран. Запрос на навигацию
можно посылать на сервер, который также располагает текущей информацией, сервер передает результаты обратно на OBU, который представляет результаты и направляет водителя.
Наиболее ценными данными являются непрерывно обновляемые данные цифровой модели дорожной сети совместно со статистикой дорожного движения, которые помогают
навигационным компаниям обновлять свои продукты маршрутизации гораздо быстрее.
Это справедливо для стран, уже имеющих карты дорог (Европа, США), и особенно для
стран, имеющих бедные цифровые модели дорожных сетей (Россия, Китай, Индия).
Профилированная модель дорожной сети помогает специалистам по планированию дорожной инфраструктуры повышать пропускную способность там, где это даст наибольший эффект. Модель включает в себя данные потока дорожного движения не только в
целом, но и на конкретное время суток, день недели и т.д.
Обычно задается вопрос: сколько времени нужно, чтобы проехать из пункта А в пункт
В? Каждый путь, каждую траекторию можно описать в виде упорядоченного множества
измерений, кривой. Их можно помечать идентификатором траектории. Затем все измерения (кривые), которые находятся вблизи пункта А и пункта В, собираются. Если измерение (кривая) в первом множестве имеет такой же идентификатор траектории, как
измерение (кривая) во втором множестве, то траектория между этими двумя измерениями
(кривыми) выделяется. Все такие выделенные подучастки траектории представляют поток
дорожного движения из пункта А в пункт В. Их можно дальше анализировать.
25
BY 12943 C1 2010.02.28
Поскольку данные маршрутизации базируются на статистических данных (которые обновляются ежедневно), это совершенная платформа для приложений оптимизации, например: оптимизации множественной загрузки, множественной доставки, своевременной
доставки, оптимизации изменения прибытия, оптимизации для общественной транспортной сети.
В случае, когда граф дорожной сети содержит детали хронирования, определяющие
время, необходимое для прохождения соединений (участков дороги) графа, предполагается вычислять самый быстрый маршрут на основе временных деталей. Временные детали
могут характеризовать движение в зависимости от дня недели или, в общем случае, например, времени суток. Например, если пользователь введет начальное время, способ в
соответствии с настоящим изобретением определит самый быстрый маршрут и предоставит пользователю результирующее время прохождения пути и т.п. Также предусмотрено,
что пользователь может вводить желаемое время прибытия с тем, чтобы алгоритм определял и выдавал начальное время и т.д. Этого можно добиться следующим образом: каждое
соединение графа должно иметь присоединенную информацию о том, сколько времени
требуется для его прохождения согласно деталям хронирования. При поиске самого быстрого маршрута посещаемые элементы должны включать в себя также детали хронирования.
Такую систему можно легко модифицировать для работы в качестве системы электронного толлинга. Основное преимущество состоит в том, что, если использовать всю
информацию, не нужна будет полная карта дорожной сети. Траектории измеряются как
кривые, и вероятность идентификации правильной дороги с использованием кривой гораздо больше, чем с использованием просто одного измерения координат GPS.
Если сравнивать форму кривых, определить фактическое местоположение транспортного средства можно гораздо легче и точнее.
На фиг. 3 показан принцип работы системы согласно варианту осуществления настоящего изобретения. Совокупность транспортных средств репрезентативно обозначена двумя автомобилями, которые оборудованы подходящими бортовыми устройствами.
Устройства способны, например, принимать сигналы GPS и определять географическую
информацию каждого транспортного средства соответственно. Согласно этому варианту
осуществления, но без ограничения, можно использовать спутник GPS 300. Спутник 300
передает на каждое бортовое устройство измеряющих транспортных средств сигнал позиции. Бортовое устройство может сохранять все позиционные данные или, альтернативно,
оно может периодически передавать данные на центральный сервер 301 в определенном
положении 302. Сервер 301 надлежащим образом оборудован антенной 303 и, конечно,
средством приема сигналов от совокупности измеряющих транспортных средств. Вся
принятая информация может храниться на сервере или, например, на другом подходящем
средстве хранения. Способ в соответствии с настоящим изобретением может осуществляться на сервере 301, который, согласно этому варианту осуществления, выступает также
в роли рабочей (вычисляющей) станции. Дополнительно, сервер базы данных также можно реализовать для поддержки сервера 301 для сохранения большого объема принятых
позиционных данных.
Траектории обоих транспортных средств, в этом случае, обозначаются как Дорога А и
Дорога В, причем эти дороги показывают два перекрестка (Перекресток А). Посредством
принятой информации сервер может сохранять все траектории от каждого транспортного
средства соответственно. Кроме того, согласно настоящему изобретению, все траектории
от одного или нескольких транспортных средств, движущихся (едущих) по аналогичной
дороге, можно усреднять для получения точных моделей дороги.
Область 380 демонстрирует, в порядке примера, часть дороги, которой присвоены некоторые размеры, например, длина L и ширина W. Согласно настоящему изобретению,
все участки дороги, входящие в граф дорожной сети, можно охарактеризовать их пара-
26
BY 12943 C1 2010.02.28
метрами, например: шириной, длиной, направлением, высотой и т.д. Дополнительно можно вставлять другие параметры, например: среднюю скорость, категорию дороги и пр.
Среднюю скорость можно определять согласно, например, времени суток или дню. Дополнительно параметры могут содержать статистическую информацию, например, статистику дорожного движения. Статистика может обеспечиваться, например, третьими
сторонами и может содержать информацию о дорожных пробках или даже статистику дорожного движения, например, количество автомобилей или оценочные значения и т.д.
На фиг. 4 показан вариант осуществления бортового устройства, которое можно установить на измеряющем транспортном средстве. Бортовое устройство содержит ЦП 400,
который способен управлять всеми операциями устройства. ЦП 400 может соединять между собой все остальные модули или компоненты, соответственно, в бортовом устройстве
согласно фиг. 4. Бортовое устройство содержит: сменный носитель 425 информации, приемник 405 сигнала позиции, дополнительный модуль счисления 410, интерфейс связи 420
и модуль 415 внутренней памяти.
Модуль связи 420 можно адаптировать для связи с центральным сервером посредством
определенного канала данных. Предполагается использовать разные технологии связи, как
GSM, CDMA, UMTS, TETRA, General Radio Interface и т.п.
На фиг. 6 показан принцип усреднения нескольких траекторий, представленных кривыми Безье, с образованием усредненной кривой. Каждая траектория А, В и С описана посредством приближения кривой Безье на основании информации 60 позиционных данных.
На фиг. 6 представлен только принцип вычисления согласно изобретению. Фактически
траектории каждого транспортного средства почти идентичны реальной форме обследуемой дороги или улицы, но, для ясности, показано значительное различие между траекториями.
В общем случае, каждую траекторию каждого транспортного средства можно описать
последовательными кривыми Безье. Эти кривые обычно имеют разные длины. Для получения геометрии оси дороги необходимо обеспечить этап усреднения траекторий, соответствующих совокупности измеряющих транспортных средств.
Это означает, что форма кривых зависит от позиционных данных, принятых от совокупности транспортных средств. В этом варианте осуществления показаны только три
траектории, но можно осуществлять способ в соответствии с настоящим изобретением на
совокупности транспортных средств.
Позиционные данные 60 могут включать в себя данные географического положения
(координаты) измеряющих транспортных средств, причем координаты используются для
описания кривых Безье. Математические вычисления кривых Безье подробно описаны
выше в подразделе "Кривые Безье".
В этом варианте осуществления позиционные данные обеспечиваются на временной
основе, это означает, что через каждые ∆t позиционные данные, так или иначе, передаются от совокупности транспортных средств. Согласно настоящему изобретению, хронирование может изменяться и не быть фиксированным. Таким образом, предполагается
выбирать большое значение времени, если маршрут не имеет кривых, и в областях, где
дорога имеет большое количество кривых или перекрестков, время можно соответственно
адаптировать. Это значит, что уменьшение значения приводит к более точным измерениям формы траектории.
После этого траектории А, В и С можно использовать для вычисления усредненной
кривой 65, которая соответствует существующей физической форме дороги. Согласно
изобретению, предполагается усреднять большое количество траекторий (кривых Безье)
для получения желаемого результата. Алгоритм в соответствии с настоящим изобретением позволяет эффективно усреднять кривые Безье и является преимущественным и экономичным с точки зрения объема вычислений.
27
BY 12943 C1 2010.02.28
Таким образом, настоящее изобретение обеспечивает автоматическое вычисление графа дорожной сети, входные данные которого обычно представляют собой измерения от
многих транспортных средств (включенных в современную систему), но некоторые методы можно осуществлять на некоторых других измерениях или также на существующих
графах дорожной сети.
Кроме того, изобретение обеспечивает автоматическое профилирование сети, входные
данные которого представляют собой граф и необработанные данные. Граф получается,
как указано в вышеприведенном описании (вычисленный согласно описанному выше, полученный от кого-то и т.д.), и необработанные данные обычно представляют собой измерение от транспортных средств в системе, отвечающей настоящему изобретению, но их
также можно получать откуда-нибудь еще (например, названия дорог, скоростные ограничения от государственных органов). Согласно другому аспекту, процедура, в основном,
состоит во вставке (и записи) необработанных данных (некоторых из их параметров) в
граф. Форма кривой является предполагаемым аспектом для идентификации соответствующей дороги и участков траектории.
Кроме того, автоматическое обновление, в основном, соответствует вышеописанному,
причем распознавание участков траекторий, которые не соответствуют никаким участкам
дороги (и наоборот - участков дороги, по которым в последнее время не проехало ни одно
транспортное средство), представляет особую важность. При сборе достаточного их количества можно вычислить новые части графа дорожной сети. Один аспект состоит в том,
что это можно делать на любом графе, и это означает, что можно производить обновление
(а также профилирование) на существующих дорожных графах, например, для Европы,
США, Японии и т.д.
Наконец, предусмотрен способ проверки, который охватывает окончательное утверждение данных. Преимущество состоит в том, что настоящее изобретение имеет приближение (вычисленный граф) и может оптимизировать маршруты для транспортных средств
проверки, что означает существенную экономию.
Кроме того, предусмотрен способ нахождения самого быстрого маршрута в графе дорожной сети. Нахождение базируется на деталях хронирования, которые составляют часть
элементов графа дорожной сети. Однако пользователь надлежащим образом оборудованного транспортного средства может использовать информацию, обеспечиваемую графом
сети, согласно настоящему изобретению, для определения (нахождения) самого быстрого
по времени маршрута. Например, если пользователь хочет попасть по определенному адресу в данное время, способ в соответствии с настоящим изобретением позволяет определить и вычислить самый быстрый маршрут. Определение базируется на информации,
включенной в граф дорожной сети, который профилирован также с использованием деталей хронирования.
Кроме того, предусмотрен способ инспектирования потока дорожного движения, зарегистрированного посредством информационных данных, который применим, например,
для планирования дорожной инфраструктуры. Таким образом, непрерывно адаптируемый
граф дорожной сети доставляет информацию о состоянии дорожного движения, и его
можно использовать для определения переполненных подучастков дороги и/или перекрестков и пр.
Хотя изобретение описано выше со ссылкой на варианты осуществления согласно прилагаемым чертежам, очевидно, что изобретение не ограничивается ими, но предусматривает ряд модификаций в рамках объема прилагаемой формулы изобретения.
28
BY 12943 C1 2010.02.28
Фиг. 2A
Фиг. 2B
Фиг. 3
29
Фиг. 2C
BY 12943 C1 2010.02.28
Фиг. 4
Фиг. 5
Фиг. 6
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
30
Документ
Категория
Без категории
Просмотров
0
Размер файла
371 Кб
Теги
12943, патент
1/--страниц
Пожаловаться на содержимое документа