Метод пространственного анализа топологии автотранспортной сети

Размещено на http://www.allbest.ru/

Метод пространственного анализа топологии автотранспортной сети

Введение

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

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

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

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

В работе предлагается метод автоматического построения специальной математической модели улично-дорожной сети (УДС) на основе имеющихся данных на электронной карте города (используются геометрические параметры слоя «проезжие части») [2]. Для применения данного метода необходимым условием является наличие детализированный векторной электронной карты города, содержащей слои с различными типами объектов (рис. 1).

1.Модель улично-дорожной сети

В рамках проектирования и реализации интеллектуальной транспортной системы г. Самары разработана специальная математическая модель улично-дорожной сети с использованием геоинформационных технологий [3]. Такая модель УДС (рис. 2) служит информационной основой подсистем интеллектуальной транспортной системы, которые решают широкий спектр задач, связанных с организацией дорожного движения, таких как задачи управления и распределения транспортных потоков, оптимизация грузоперевозок, экспертная дислокация дорожных знаков и светофоров и др. Основой модели УДС являются объекты трех базовых типов: участки, узлы и дуги. Участок - это область проезжей части, характеризующаяся атрибутами, постоянными в любой точке объекта. Участки делятся на перегоны, перекрестки, железнодорожные переезды и пешеходные переходы.

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

2.Метод автоматизированного построения модели УДС

автоматизация сеть интеллектуальный транспортный

Под автоматизированным построением модели УДС понимается процесс, состоящий из следующих этапов.

1. Автоматическое построение осевых (срединных) линий проезжих частей.

2. Автоматический поиск перекрестков (мест пересечения осевых).

3. Автоматическое разбиение слоя «Проезжая часть» на участки дорожной сети согласно предложенной модели УДС (построение слоя «Участок»).

4. Автоматическое построение графа транспортной сети (слои «Узел» и «Дуга») с привязкой к слою «Участок».

5. Ручная коррекция модели транспортной сети.

6. Автоматическое заполнение атрибутивных полей слоев «Участок», «Узел», «Дуга».

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

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

Наибольшую алгоритмическую сложность представляет процесс построения слоя «Участок» [2], заключающийся в анализе слоя «проезжие части» и итерационном выделении из этого слоя объектов (полигонов), подходящих под определенный паттерн.

На 4-м этапе происходит построение орграфа транспортной сети и формирование логики взаимоотношений объектов модели УДС, т.е. топологии.

3.Алгоритм анализа топологии на основе метода трассировки

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

Метод трассировки применяется в основном при моделировании освещения изображений в трехмерной графике. В геоинформационных системах (ГИС) метод трассировки лучей используется для векторизации растровых изображений. Обобщенно метод трассировки лучей может применяться для анализа «окружающей обстановки» относительно определенной точки с целью извлечения пространственной информации. Под пространственной информацией понимается расположение границ областей с определенными (искомыми) характеристиками относительно центра исследования. Алгоритм, реализующий данный метод, находит условно локальную область с постоянными характеристиками, отличными от характеристик других областей. Метод основан на трассировке пространства вокруг центра при помощи лучей, заданных функциями определенного вида и условиями финитности лучей (рис. 3).

4.Алгоритм метода заключается в следующем

автоматизация сеть интеллектуальный транспортный

Шаг 1. Выбирается центр. Центр может быть выбран исходя из условий задачи (например, центр масс однородного полигона). В этом случае решается задача поиска области трассировки. В других случаях может решаться обратная задача. В рассматриваемом случае в качестве центра выбираются ключевые точки. В каждой точке определенной области строится область трассировки. Этот процесс продолжается до тех пор, пока область не будет удовлетворять заданным критериям. Пусть центр будет в точке O с координатами (X0,Y0) для двумерной плоскости.

Шаг 2. Из центра строятся расходящиеся лучи, отстоящие друг от друга на угол Ai,i+1. Лучи нумеруются от 1 до N, где N - число лучей. Каждому лучу соответствует некоторая функция fi - зависимость одной координаты от другой, которая может быть представлена в полярных, декартовых или других координатах. На рис. 3 показан простейший пример с лучами, которым соответствует линейная функция вида y=kx+b. Стоит отметить, что функция fi может иметь не только аналитический, но и произвольный (например, алгоритмический) вид. Каждый луч строится из центра по закону fi и прерывается при наступлении некоторого условия финитности Fi. Функция Fi - некоторая предикатная функция, равная 0 на всей длине луча и равная 1 в точке его прерывания. Функция Fi, например, может играть роль определителя границ других областей или удаленности от центра. Угол Ai,i+1 определяет количество лучей для трассировки, следовательно, точность построения. Точность построения характеризуется относительной ошибкой , равной отношению площади пересечения трассированной области Str, представленной полигоном из периферийных вершин лучей, с реальной однородной областью S к площади этой реальной однородной области .

Шаг 3. Записывается N пар значений (i, l), где i - номер луча, а l - его длина. Эти значения представляют количественную характеристику окружающего пространства, сформированного по заданным критериям около определенной точки.

Шаг 4. Для наглядности удобно представить пары значений в виде графика, где по оси абсцисс показаны номера лучей, а по оси ординат - их длины (рис. 4). Отметим, что результатом применения данного метода могут быть не только пары (i, l), но и пары (i, l'), где l' - относительная длина луча, равная отношению длины луча к максимально возможному значению либо к максимальной длине луча в конкретном построении. Максимально возможная длина луча lmax - это значение, ограничивающее построение луча в случае ненаступления другого условия его финитности.

Рассмотрим применение описанного метода трассировки к задаче выделения перекрестков на проезжих частях УДС.

Наличие правильно построенных осевых линий объектов слоя «Проезжая часть» обязательно для работы алгоритма автоматизированного построения модели УДС. В случае отсутствия слоя «Осевые улицы» его необходимо построить. Для этого нужно провести линеаризацию каждого объекта слоя «Проезжая часть» при помощи, например, алгоритма триангуляции [5]. Затем необходимо совместить конечные точки получившихся полилиний, расположенных на смежных линиях проезжих частей, так, чтобы в пределах одной улицы осевая линия была непрерывна.

При применении метода трассировки на карте строятся лучи, исходящие из какой-либо ключевой точки и имеющие определенную длину. Каждый луч прерывается при пересечении границы объекта «Проезжая часть». За количественную характеристику окружающего точку пространства можно принять вектор пар значений (i,li), где i - номер луча, а li - его длина.

Ключевая точка (например, центр перекрестка) принимается за центр полярных координат. Проведем из центра лучи, равноотстоящие друг от друга на угол . Исходящий от центра луч прервется на границе объекта слоя «Проезжая часть» (на обочине) или достигнет максимально установленной длины lmax (рис. 5). Условие финитности будет задавать предикатная функция F(x,y), где (x,y) координата точки строящегося луча. F(x,y) = 0, если точка с координатами (x,y) принадлежит объекту слоя «Проезжая часть», т.е. находится в границах полигона. F(x,y) = 1, если точка не находится на объекте «Проезжая часть».

В случае применения метода трассировки пространства для слоя «Проезжая часть» график длин лучей представляет собой совокупность двух или более всплесков, характеризующих лучи проезжей части (рис. 6). Число пиков (локальных максимумов) M и вид графика (паттерн) определяет тип участка:

- 2 пика - линейный участок;

- 3 пика - Т-образный перекресток;

- 4 пика - Х-образный перекресток и т.д.

Расстояние между максимумами определяет характер участка. При M=2, если , то имеется линейный участок с поворотом. - коэффициент люфта, некоторое малое число, определяющее допустимое отклонение от прямой осевой линии линейного участка, зависящее от числа N.

5.Построение геомоделей участков улично-дорожной сети на карте города

автоматизация сеть интеллектуальный транспортный

Задача выделения из проезжей части одного объекта слоя «Участок» сводится к преобразованию полученного графика (рис. 7 а) на основе соответствующего паттерна в график, определяющий границы объекта «Участок» (рис. 7 б). Зададим каждому лучу, построенному из ключевой точки, фиксированную длину, полученную из преобразованного графика. Соединив периферийные точки расходящихся лучей, получим объект слоя «Участок».

Построение участка типа «Перекресток». Необходимо провести трассировку пространства, окружающего центр перекрестка (точка пересечения осевых), и преобразовать полученный вектор длин лучей в вектор, характеризующий перекресток. Для преобразования результирующего графика в объект-перекресток нет необходимости искать отсекающую кривую. Достаточно найти точки xi, xj (рис. 7 б). Отобразив эти точки на карту и соединив их прямыми, получим линии отсечения объекта-перекрестка (рис. 8). Точки находятся путем отсечения графика по горизонтали линией y = k*lmin, где lmin - значение ближайшего минимума графика, а k - некоторый коэффициент, найденный эмпирически.

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

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

Построение участка типа «Железнодорожный переезд». Железнодорожный переезд - это участок, находящийся на пересечении железной дороги и проезжей части УДС. Расстояние от границ участка до железнодорожных путей регламентировано ГОСТом. Для создания участка типа «Железнодорожный переезд» проводится трассировка пространства из места пересечения ж/д путей и проезжей части. Преобразования сводятся к получению графика, соответствующего буферной зоне около переезда.

Построение участка типа «Тупик». Для построения тупиков УДС необходимо исследовать срединные линии проезжих частей на смежность со срединными линиями других объектов слоя «Проезжая часть». Из граничных точек, несмежных срединных линий производится трассировка пространства и выделение участка «Тупик».

Построение объектов типа «Узел». Узлы строятся на основе слоя «Участок» (рис. 2 б). Таким образом, на этапе построения узлов УДС слой «Участок» должен быть полностью заполнен. Графическое представление узла - эллипс, расположенный на границе смежных участков в точке движения и возможного изменения направления транспортного потока. Двум смежным участкам могут соответствовать один или два узла. В рассматриваемых электронных картах отсутствует информация по организации дорожного движения на УДС, в частности, для улиц, имеющих одностороннее движения, нет данных о разрешенном направлении движения транспортных потоков. В связи с этим соединение двух участков проводится двумя узлами, что дает возможность решать разнообразные задачи, связанные с управлением транспортными потоками, без изменения основной структуры модели УДС. Для нахождения точек установки узлов необходимо для каждой пары смежных участков найти линии смежности. Точки установки узлов соответствуют ј и ѕ длины линии смежности, т.е. находятся в середине каждой из двух полос движения. При наличии слоя «Улицы» может быть определена принадлежность узла к конкретной улице.

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

Построение дуг, имеющих радиус искривления. Криволинейные дуги представляют собой полилинии с более чем двумя вершинами. Дуги на линейных участках типа «Поворот» соответствуют границам буферной зоны около срединной линии участка. Ширина буферной зоны равна половине ширины участка. Криволинейные дуги, описывающие изменение направления движения на перекрестках или развороты, представляют собой линейную интерполяцию окружности, соответствующей дуге (рис. 2 б).

Заключение

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

Предложенный метод автоматического построения математической модели УДС позволил построить геоинформационную объектную модель улично-дорожной и транспортной сетей г. Самары, значительно сократив время, необходимое для заполнения базы данных относительно более чем 500 000 участков УДС. Это позволило решать задачи обеспечения подсистем интеллектуальной транспортной системы города необходимыми знаниями, касающимися пространственно-координированной информации, сократив необходимость ручного ввода данных. Масштабы транспортных сетей современных городов, наличие большого количества анализируемой информации обусловливают актуальность и экономическую эффективность данной разработки.

Библиографический список

автоматизация сеть интеллектуальный транспортный

1.Dell'Acqua F., Gamba P., Iodice A., Lisini G., Riccio D., Ruello G. Simulation and Analysis of Fine Resolution SAR Images in Urban Areas, 2nd GRSS/ISPRS Joint Workshop on “Data Fusion and Remote Sensing over Urban Areas”, URBAN 2003. P. 133-136.

2.Михеева Т.И. Построение математических моделей объектов улично-дорожной сети города с использованием геоинформационных технологий // Информационные технологии. 2006. №1. С. 69-75.

3.Михеева Т.И., Демьяненко Р.В., Большаков А.С. Обобщенный метод проектирования модели улично-дорожной сети / Математика. Компьютер. Образование: Тез. докл. ХIII международ. конф. М. - Ижевск: МГУ, НИЦ «Регулярная и хаотическая динамика», ¬ 2006. С. 78.

4.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. 960 с.

5.Михеева Т.И., Петряшина Ю.В. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек / Перспективные информационные технологии в научных исследованиях, проектировании и обучении (ПИТ-2006). Труды науч.-техн. конф. с междунар. участ. Т.2. Самара, 2006. С. 48 54.

Размещено на Allbest.ru