ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Bookmark

Next issue

1
Publication date:
16 March 2021
-->

Algorithm for direction-finding of localized objects of traffic flows on digital satellite images

Date of submission article: 2021-02-24
UDC: 684.511
The article was published in issue no. № 2, 2021 [ pp. 289-294 ]
Abstract:The paper proposes a unique algorithm for determining the direction-finding of localized objects in traffic flows based on ultra-high resolution satellite shooting data and geographical information on the location of MAC sections. The program implementation of the developed algorithm is a component module of the program traffic control system. We provide the input of the module with data on the in-terpolated model of the stage, as well as on the location and size of each localized vehicle on the stage. At the output of the module, the direction of its movement is determined for each vehicle: forward or reverse. The algorithm is based on comparing the position of vehicles and the central interpolated line of the MAC section on digital images of the sections. We have developed a unique algorithm for finding a minimum length segment from a point to a broken line on a plane. We used the algorithm as one stage of the stages of the algorithm for determin-ing the direction of movement of the vehicle at the MAC stage. The approach is based on comparing the relative position of the object and the centerline. Due to the unambiguity of correlation of the rela-tive location of centerline with central point parallel to axes of limiting rectangle of localized vehicle, the direction of motion is determined with high accuracy. Due to this, the direction of motion previous-ly detected by the vehicle is determined with high accuracy. The authors undertook a study of developed algorithms on real satellite data. Analysis of the re-search results showed that the developed algorithm for determining the direction-finding works with high accuracy. The experimental evaluation of the work consists of the formation of a calculated metric for a set of previously extracted local regions. Because the algorithm assigns the vehicle to one of the two directions of traffic, we chose the accuracy of the correct determination of the direction of move-ment as a heuristic metric. It is determined that the error in the direction definition is related to the in-accuracy in determining the coordinates of the centerline of the local road section.
Аннотация:В статье предлагается уникальный алгоритм определения направления движения объектов в транспортном потоке по данным спутниковой съемки сверхвысокого разрешения и географической информации о расположении перегонов улично-дорожной сети. Программная реализация разработанного алгоритма является составным модулем программной системы управления дорожным движением. На вход модуля подаются данные об интерполированной модели перегона, а также о местоположении и размерах каждого локализованного транспортного средства на пере-гоне. На выходе модуля для каждого транспортного средства определяется направление его движения: прямое или обратное. Алгоритм основан на сопоставлении положения транспортных средств и центральной интерполированной линии перегона улично-дорожной сети на цифровых изображениях перегонов. Разработан уникальный алгоритм нахождения отрезка минимальной длины от точки к ломаной линии на плоскости. Алгоритм используется в качестве одного из этапов процедуры определения направления движения объектов транспортного потока на перегоне уличнодорожной сети. Подход основан на сопоставлении относительного положения объекта и осевой линии. Благодаря однозначности соотнесения относительного расположения осевой линии с центральной точкой параллельного осям ограничивающего прямоугольника локализованного транспортного средства направление движения определяется с высокой точностью. Проведены исследования разработанных алгоритмов на реальных спутниковых данных. Анализ их результатов показал, что разработанный алгоритм определения направления движения детектированного объекта транспортного потока работает с высокой точностью. Экспериментальная оценка работы заключается в формировании расчетной метрики для набора ранее извлеченных локальных регионов. В силу того, что алгоритм относит транспортное средство к одному из двух направлений дорожного движения, в качестве метрики эвристическим путем выбрана точность верного определения направления движения. Показано, что погрешность в определении направления связана с неточностью в определении координат осевой линии локального участка дороги.
Authors: V.S. Tormozov (007465@pnu.edu.ru) - Pacific National University (Senior Lecturer), Khabarovsk, Russia, A.L. Zolkin (alzolkin@list.ru) - Povolzhskiy State University of Telecommunications and Informatics (Assistant Professor), Samara, Russia, Ph.D, А.U. Mentsiev (a.mentsiev@chesu.ru) - Chechen State University (Senior Lecturer), Grozny, Russia
Keywords: digital image processing, vehicle, street road network, satellite imagery
Page views: 882
PDF version article

Font size:       Font:

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

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

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

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

В ряде научных работ рассматривались различные подходы к задаче детектирования и классификации объектов транспортных потоков по данным съемки сверхвысокого разрешения [2, 3]. В таких работах цифровое изображение кандидата объекта маркируется как один из заранее заданных классов. Причем во множестве классов для маркировки в работе создается класс, не относимый к объектам [4, 5]. Так, процедура классификации объединяется с про-цедурой детектирования: кандидат, отнесен-ный к одному из существующих классов объектов, маркируется как детектированный. В то же время для отнесения детектированного объекта к одному из потоков на участке дорожного пути необходима локализация объекта одному из перегонов рассматриваемой УДС. В ситуации, когда транспортное движение на участке дороги двустороннее, также требуется определить принадлежность транспортного средства к одному из направлений движения. Разработан алгоритм, базирующийся на данных о месторасположении ранее детектированного объекта относительно осевой линии интерполированной модели дороги [6]. Выполняется идентификация части дорожного полотна, в границах которой находится наибольшая геометрическая площадь детектированного объекта – параллельного осям минимально ограничивающего прямоугольника (Bounding Box, BB) [7, 8]. При рассмотрении интерполированной цифровой модели перегона определяется, с какой стороны относительно ломаной осевой линии участка УДС находится большая часть детектированного транспортного средства (см. рисунок).

Направление дорожного движения на перегоне обозначается индексом, определяемым исходя из выражения  где iТС – индекс направления движения рассматриваемого транспортного средства на участке УДС; x – абсцисса центральной точки BB транспортного средства; x0 – абсцисса точки пересечения отрезка, проведенного от рассмат-риваемой точки к ломаной осевой линии участка УДС. Индекс может быть определен только для тех участков УДС, на которых движение двустороннее.

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

Этап 1. Вычисление координат центральной точки BB транспортного средства:

, где xBB, yBB – координаты BB транспортного средства; wBB, hBB – ширина и высота BB транспортного средства.

Этап 2. Нахождение координат точки пересечения отрезка, проведенного от центральной точки ВВ (этап 1) к ломаной осевой линии дороги, с одной из прямых, проведенных от отрезков ломаной рассматриваемого перегона. На изображении заданы точка PBB(x, y) и ломаная линия, образованная последовательностью точек A = {A1, A2, …, An}, Ak (xk, yk}, y = 1, n, где n – общее количество точек на ломаной. Для получения координат точки пересечения необходимо найти такой перпендикуляр с наименьшей длиной среди всех перпендикуляров от точки PBB к прямой, проведенной из множества всех отрезков ломаной. Разработанный уникальный алгоритм нахождения отрезка минимальной длины PBBPmin от точки PBB к ломаной линии A на плоскости состоит из следующих шагов.

1. Формируется список L = {P1, P2, …, Pn-1} точек пересечения отрезка от точки PBB к прямым каждого из отрезков ломаной на плоскости. Изначально список L не содержит точек.

2. Для каждого отрезка AkAk+1 : Ak(xk, yk}, Ak+1(xk+1, yk+1}, k = 1, n – 1, выполняется расчет координат точки Pk на прямую, проведенную из отрезка AkAk+1 к ломаной [9]:

где PBB(x, y) – центральная точка BB транспорт-ного средства. При этом точка Pk может не принадлежать отрезку AkAk+1.

3. Включение точки Pk(xpk, ypk) в список возможных точек L: L = L È Pk. Точка Pk (xpk, ypk) принадлежит отрезку AkAk+1, если выполнено

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

,

где Pmin(xpmin, ypmin) – точка пересечения отрезка от PBB к ломаной линии с наименьшей длиной, min – функция поиска минимума; n – количество точек в ломаной; Pk(xpk, ypk) – точка основания k-го перпендикуляра; PBB(x, y) – точка построения отрезков к ломаной.

Результатом работы алгоритма являются найденная точка отрезка от PBB(x, y) к ломаной линии с наименьшей длиной Pmin(xpmin, ypmin), а также сам отрезок PminS.

По позиции транспортного средства относительно осевой линии интерполированной модели перегона будет определено направление движения транспортного средства на перегоне.

Этап 3. Идентификация направления дорожного движения объекта как индекса iТС исходя из соотношения координат ранее полученной точки Pmin основания перпендикуляра и центральной точки транспортного средства.

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

Экспериментальная оценка работы заключается в формировании расчетной метрики для набора ранее извлеченных локальных регионов [5]. В силу того, что алгоритм относит транспортное средство к одному из двух (максимум) направлений дорожного движения, Результаты оценки работы алгоритма определения направления движения ТС

The algorithm evaluation findings for determining the machine direction

Показатель	Номер исследуемой области
	1	2	3	4	5	6	7
Общее количество транспортных средств	231	14	28	3	11	15	29
Количество транспортных средств, для которых было верно определено направление 	225	13	26	3	11	15	28
Количество транспортных средств, для которых направ-ление движения было определено неверно	6	1	2	0	0	0	1
Точность алгоритма определения направления движения, %	97,4	92,9	92,9	100	100	100	96,6

в качестве метрики эвристическим путем выбрана точность верного определения направления движения [10, 11], рассчитываемая по формуле , где P – точность определения; TP – количество транспортных средств, для которых было верно определено направление движения; FP – количество транспортных средств, для которых направление движения было определено неверно [11]. В таблице представлены результаты экспериментальной оценки работы алгоритма для различных областей дневных спутниковых снимков.

Заключение

Таким образом, был разработан алгоритм определения направления дорожного движе-ния, вдоль которого движется транспортное средство, по местоположению детектированного транспортного средства. Проведенные исследования показали, что разработанный алгоритм определения направления движения детектированного транспортного средства работает в среднем с точностью 97,1 %. Погрешность в определении направления связана с неточностью в определении координат осевой линии локального участка дороги. Разработан уникальный алгоритм нахождения отрезка минимальной длины от точки к ломаной линии на плоскости. Подход основан на сопоставлении относительного положения объекта и осевой линии. Благодаря сопоставлению положений с высокой точностью определяется направление движения ранее детектированного транспортного средства.

Работа выполнена при поддержке Минобрнауки РФ, дополнительное соглашение № 075-02-2020-1529/1 от 21.04.2020.

Литература

1.    Тормозов В.С. Подсчет и распознание автомобилей на спутниковых снимках // Ученые заметки ТОГУ. 2017. Т. 8. № 3. С. 126–134. URL: https://www.elibrary.ru/download/elibrary_30458787_63143288.pdf (дата обращения: 19.01.2021).

2.    Abraham L., Sasikumar M. Vehicle detection and classification from high resolution satellite images. ISPRS Annals, 2014, vol. 2, no. 1, pp. 1–8. DOI: 10.5194/isprsannals-II-1-1-2014.

3.    Gill N.K., Sharma A. Vehicle detection from satellite images in digital image processing. IJCIR, 2017, vol. 13, no. 5, pp. 697–705.

4.    Larsen S.Q., Salberg A.B., Eikvil L., Trier D. Operational Traffic Monitoring Using Very High Resolution Satellite Imagery. 2012. URL: https://www.nr.no/en/nrpublication?query=/file/1338295684/Larsen_EARSeL-2012_pres.pdf (дата обращения: 19.01.2021).

5.    Тормозов В.С., Василенко К.А., Золкин А.Л. Настройка и обучение многослойного персептрона для задачи выделения дорожного покрытия на космических снимках города // Программные продукты и системы. 2020. Т. 33. № 2. С. 343–348. DOI: 10.15827/0236-235X.130.343-348.

6.    Haklay M., Weber P. Openstreetmap: User-generated street maps. IEEE Pervasive Computing, 2008, vol. 7, no. 4, pp. 12–18. DOI: 10.1109/MPRV.2008.80.

7.    Jun Y.N., Tay Y.H. Image-based Vehicle Classification System. 2012. URL: https://arxiv.org/abs/1204.2114 (дата обращения: 19.01.2021).

8.    Hinz S. Detection of vehicles and vehicle queues for road monitoring using high resolution aerial images. Proc. IX World Multiconf. on SCI, 2005, vol. 8, pp. 1–4.

9.    Тормозов В.С. Метод детектирования и классификации транспортных средств на спутниковых снимках сверхвысокого разрешения // Промышленные АСУ и контроллеры. 2019. № 6. С. 18–24. DOI: 10.25791/asu.06.2019.678.

10. Виноградова Е.П., Головин Е.Н. Метрики качества алгоритмов машинного обучения в задачах классификации // Научная сессия ГУАП. 2017. С. 202–206.

11. Zhu W., Zeng N., Wang N. Sensitivity, specificity, accuracy, associated confidence interval and ROC analysis with practical SAS implementations. NESUG Proc.: Health Care and Life Sciences, 2010. URL: http://www.cpdm.ufpr.br/documentos/ROC.pdf (дата обращения: 19.01.2021).

12. Powers D.M.W. Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation. Journal of Machine Learning Technologies, 2011, vol. 2, no. 1, pp. 37–63.

References

  1. Tormozov V.S. Vehicle count and recognition on satellite images. Uchenye Zametki TOGU, 2017,
    vol. 8, no. 3, pp. 126–134. Available at: https://www.elibrary.ru/download/elibrary_30458787_63143288.pdf (accessed January 19, 2021) (in Russ.).
  2. Abraham L., Sasikumar M. Vehicle detection and classification from high resolution satellite images. ISPRS Annals, 2014, vol. 2, no. 1, pp. 1–8. DOI: 10.5194/isprsannals-II-1-1-2014.
  3. Gill N.K., Sharma A. Vehicle detection from satellite images in digital image processing. IJCIR, 2017, vol. 13, no. 5, pp. 697–705.
  4. Larsen S.K., Salberg A.B., Eikvil L., Trier D. Operational Traffic Monitoring Using Very High Resolution Satellite Images. 2012. Availale at: https://www.nr.no/en/nrpublication?query=/file/1338295684/Larsen_EARSeL-2012_pres.pdf (accessed January 19, 2021)
  5. Tormozov V.S., Vasilenko K.A., Zolkin A.L. Setting up and training a multilayer perceptron for the problem of highlighting the road surface in the city space images. Software and Systems, 2020, vol. 33, no. 2, pp. 343–348. DOI: 10.15827/0236-235X.130.343-348 (in Russ.).
  6. Haklay M., Weber P. Openstreetmap: User-generated street maps. IEEE Pervasive Computing, 2008, vol. 7, no. 4, pp. 12–18. DOI: 10.1109/MPRV.2008.80.
  7. Jun Y.N., Tay Y.H. Image-based Vehicle Classification System. 2012. Available at: https://arxiv.org/
    abs/1204.2114 (accessed January 19, 2021).
  8. Hinz S. Detection of vehicles and vehicle queues for road monitoring using high resolution aerial images. Proc. IX World Multiconf. on SCI, 2005, vol. 8, pp. 1–4.
  9. Tormozov V.S. Method of detecting and classifying vehicles on ultra-high resolution satellite images. Industrial Automatic Control Systems and Controllers, 2019, no. 6, pp. 18–24 (in Russ.).
  10. Vinogradova E.P., Golovin E.N. Metrics of quality of machine training algorithms in classification problems. The Scientific Conf. of SUAI. Proc. the Session, 2017, pp. 202–206 (in Russ.).
  11. Zhu W., Zeng N., Wang N. Sensitivity, specificity, accuracy, associated confidence interval and ROC analysis with practical SAS implementations. NESUG Proc.: Health Care and Life Sciences, 2010. Available at: http://www.cpdm.ufpr.br/documentos/ROC.pdf (accessed January 19, 2021).
  12. Powers D.M.W. Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation. Journal of Machine Learning Technologies, 2011, vol. 2, no. 1, pp. 37–63.

Permanent link:
http://swsys.ru/index.php?page=article&id=4817&lang=en
Print version
The article was published in issue no. № 2, 2021 [ pp. 289-294 ]

Perhaps, you might be interested in the following articles of similar topics: