radioelectronicsИзвестия высших учебных заведений России. РадиоэлектроникаJournal of the Russian Universities. Radioelectronics1993-89852658-4794Saint Petersburg Electrotechnical University10.32603/1993-8985-2023-26-2-65-77radioelectronics-737Research ArticleРАДИОЛОКАЦИЯ И РАДИОНАВИГАЦИЯRADAR AND NAVIGATIONАлгоритм обнаружения треков на основе вычисления корреляции следов в аккумуляторе ХафаTrack Detection Algorithm Based on Trace Correlation Using Hough Transformhttps://orcid.org/0000-0003-4469-0501МонаковА. А.MonakovA. A.

Монаков Андрей Алексеевич – доктор технических наук (2000), профессор (2005) кафедры радиотехнических систем. Почетный машиностроитель РФ (2005), почетный работник высшего профессионального образования РФ (2006). Автор более 200 научных работ. Сфера научных интересов – радиолокация протяженных целей; цифровая обработка сигналов; радиолокаторы с синтезированной апертурой; исследование природных сред радиотехническими методами; управление воздушным движением.

190000, Санкт-Петербург, ул. Большая Морская, д. 67 А

Andrey A. Monakov, Dr Sci. (Eng.) (2000), Professor (2005) of the Department of Radio Engineering Systems. Honored Mechanical Engineer of the Russian Federation (2005), Honored Worker of Higher Professional Education of the Russian Federation (2006). The author of more than 200 scientific publications. Area of expertise: extended radar targets; digital signal processing; synthetic aperture radar; remote sensing; air traffic control.

190000, St Petersburg, Bolshaya Morskaya St., 67 A

a_monakov@mail.ruСанкт-Петербургский государственный университет аэрокосмического приборостроенияРоссияSaint-Petersburg State University of Aerospace InstrumentationRussian Federation2023020520232626577Copyright © Монаков А.А., 20232023Монаков А.А.Monakov A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://re.eltech.ru/jour/article/view/737

Введение. Обнаружение треков – одна из основных задач, решаемых системой траекторной обработки (СТО). Известным и эффективным методом обнаружения треков является преобразование Хафа (Hough Transform). Трек считается обнаруженным, если количество отметок, полученных в последовательных обзорах и попавших в одну и ту же область пространства параметров (аккумулятора), превысило порог обнаружения. Однако, как показывает практика, для эффективного применения преобразования Хафа в СТО необходимо достаточно большое время накопления отметок. При малом количестве обзоров, отведенных для обнаружения треков, отметки целей также накапливаются в тех ячейках аккумулятора, где происходят пересечения их следов. Поэтому для обнаружения треков необходима дополнительная обработка, позволяющая выделить кластеры отметок от целей по признаку их геометрической близости. Кроме того, большой объем памяти и вычислительных операций по обслуживанию аккумулятора в значительной мере увеличивают нагрузку вычислителя СТО.Цель работы. Получение простого и устойчивого к ложным обнаружениям алгоритма завязки треков на основе преобразования Хафа без создания в памяти вычислителя аккумулятора.Материалы и методы. В предлагаемом алгоритме построение следов отметок в аккумуляторе с последующим выделением ячеек с максимальным количеством прошедших через них следов заменено на вычисление взаимных корреляций следов и кластеризации отметок по признаку максимального подобия следов.Результаты. Математическое моделирование при выбранных в работе сценарных параметрах подтвердило, что предлагаемый алгоритм правильно обнаружил все существующие в зоне ответственности СТО треки и осуществил безошибочное объединение отметок целей.Заключение. Создан помехоустойчивый алгоритм обнаружения треков, не требующий организации в памяти вычислителя аккумулятора Хафа.

Introduction. Track detection is one of the main tasks to be solved in trajectory processing. This task can be efficiently solved using the Hough Transform. A track is considered detected if the number of position measurements received in a number of consecutive radar scans and falling into the same cell of the parameter space (accumulator) has exceeded the detection threshold. However, the effective practical application of the Hough transform requires a sufficiently long time of measurement. Under a small number of scans given for track detection, measurements are also accumulated in those accumulator cells where their traces intersect. Therefore, in order to detect true tracks, additional processing is required to distinguish measurement clusters from different targets based on their geometric proximity. In addition, a large amount of memory and computational operations for the accumulator maintenance significantly increase the computation load of the trajectory processor.Aim. To design a simple and false-detection resilient algorithm for detecting tracks without the Hough accumulator in the processor memory.Materials and methods. In the proposed algorithm, the construction of measurement traces in the Hough accumulator followed by selection of cells with the largest number of traces passed through them is replaced by computation of the cross correlations of the traces and clustering of measurements based on the maximum similarity of their traces.Results. Mathematical simulation with the scenario parameters selected in the paper confirmed the accuracy of the proposed algorithm in detecting all tracks existing in the radar field of view and its efficiency in conducting error free association of target position measurements.Conclusion. A false-detection resilient algorithm for track detection was created based on the Hough transform. The algorithm does not require the Hough accumulator in the processor memory.

траекторная обработкаобнаружение трековпреобразование Хафаtrajectory processingtrack detectionHough transformReferencesКоновалов А. А. Основы траекторной обработки радиолокационной информации. Ч. 1. СПб.: Изд-во СПбГЭТУ "ЛЭТИ", 2013. 164 с.Konovalov A. A. Osnovy traektornoi obrabotki radiolocatzionnoi informatzii [Foundations of the Trajectory Surveillance of Radar Targets]. Part. 1. St Petersburg, ETU Publishing House, 2013, 164 p. (In Russ.)Киселев В. Ю., Монаков А. А. Оценка качества алгоритмов траекторной обработки в радиолокационных системах управления воздушным движением: обнаружение треков // Радиотехника. 2016. Т. 80, № 3. С. 28–36.Kiselev V. Yu., Monakov A. A. Assessment of Trajectory Processing Algorithms in Air Traffic Control Radar Systems: Track Detection. J. Radioengineering. 2016, vol. 80, no. 3, pp. 28–36.Pat. US 3069654. Methods and means for recognizing complex patterns / P. V. C. Hough. Publ.18.12.1962.Hough P. V. C. Methods and Means for Recognizing Complex Patterns. Pat. US 3069654. Publ. 18.12.1962.Duda R. O., Hart P. E. Use of the Hough transform to detect lines and curves in pictures // Communication of the ACM. 1972. Vol. 15, № 1. P. 11–15. doi:10.1145/361237.361242Duda R. O., Hart P. E. Use of the Hough Transform to Detect Lines and Curves in Pictures. Communication of the ACM. 1972, vol. 15, no. 1, pp. 11–15. doi:10.1145/361237.361242Illingworth J., Kittler J. A survey of the Hough transform // Computer Vision. Graphics and Image Processing. 1988. Vol. 44, № 1. P. 87–116. doi:10.1016/0734-189x(88)90071-0Illingworth J., Kittler J. A Survey of the Hough Transform. Computer Vision. Graphics and Image Processing. 1988, vol. 44, no. 1, pp. 87–116. doi:10.1016/0734-189x(88)90071-0Mukhopadhyay P., Chaudhuri B. B. A survey of Hough Transform // Pattern Recognition. 2015. Vol. 48, № 3. P. 993–1010. doi:10.1016/j.patcog.2014.08.027Mukhopadhyay P., Chaudhuri B. B. A Survey of Hough Transform. Pattern Recognition. 2015, vol. 48, no. 3, pp. 993–1010. doi:10.1016/j.patcog.2014.08.027Carlson B. D., Evans E. D., Wilson S. L. Search radar detection and track with the Hough transform. Part I: System concept // IEEE Trans. on Aerospace and Electronic Systems. 1994. Vol. 30, № 1. P. 102–108. doi:10.1109/7.250410Carlson B. D., Evans E. D., Wilson S. L. Search Radar Detection and Track with the Hough Transform, Part I: System Concept. IEEE Trans. on Aerospace and Electronic Systems. 1994, vol. 30, no. 1, pp. 102–108. doi:10.1109/7.250410Yankowich S. W., Farooq M. A Hough transform based multisensor, multitarget track initiation technique // Proc. of the 36th IEEE Conf. on Decision and Control. 1997. Vol. 5. P. 5018–5023. doi:10.1109/cdc.1997.649856Yankowich S. W., Farooq M. A Hough Transform Based Multisensor, Multitarget Track Initiation Technique. Proc. of the 36th IEEE Conf. on Decision and Control. 1997, vol. 5, pp. 5018–5023. doi:10.1109/cdc.1997.649856Alexiev K. Implementation of Hough transform as track detector // Proc. of the Third Intern. Conf. on Information Fusion, Paris, France, 10–13 July 2000. IEEE, 2000. Vol. 2. doi:10.1109/ific.2000.859896Alexiev K. Implementation of Hough Transform as Track Detector. Proc. of the Third Intern. Conf. on Information Fusion, Paris, France, 10-13 July 2000. IEEE, 2000, vol. 2. doi:10.1109/ific.2000.859896An effective Hough transform based track initiation / S. Jin, Y. Liang, P. He, G. Pan, Q. Pan, Y. Cheng // Intern. Conf. on Machine Learning and Cybernetics, Dalian, China, 13–16 Aug. 2006. IEEE, 2006. P. 3196–3200. doi:10.1109/icmlc.2006.258425Jin S., Liang Y., He P., Pan G., Pan Q., Cheng Y. An Effective Hough Transform Based Track Initiation. Intern. Conf. on Machine Learning and Cybernetics, Dalian, China, 13–16 Aug. 2006. IEEE, 2006. P. 3196–3200. doi:10.1109/icmlc.2006.258425Ворошилина Е. П., Ворошилин Е. П., Тисленко В. И. Алгоритмы завязки траекторий подвижных объектов // Докл. ТУСУР. 2009. Т. 20, № 2. С. 48–52.Voroshilina E. P., Voroshilin E. P., Tislenko V. I. Track initiation methods for moving targets. Proc. of TUSUR University. 2009, vol. 20, no. 2, pp. 48–52. (In Russ.)Семенов А. Н. Обнаружение радиолокационных целей с помощью преобразования Хафа // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2014. № 12. C. 619–632. doi:10.7463/1214.0738733Semenov A. N. Radar Target Detection by Means of the Hough Transform. Science and Education. MGTU Electron J. 2014, no. 12, pp. 619–632. doi:10.7463/1214.0738733 (In Russ.)Multiple hypothesis tracking using Hough transform track detector / E. Semerdjiev, K. Alexiev, E. Djerassi, P. Konstantinova // Information & Security: An Intern. J. 1999. Vol. 2. P. 113–121. doi:10.11610/isij.0210Semerdjiev E., Alexiev K., Djerassi E., Konstantinova P. Multiple Hypothesis Tracking Using Hough Transform Track Detector. Information & Security: An Intern. J. 1999, vol. 2, pp. 113–121. doi:10.11610/isij.0210Alexiev K. M., Bojilov L. V. A Hough transform track initiation algorithm for multiple passive sensors // Proc. of the 3rd Intern. Conf. on Information Fusion, Paris, France, 10–13 July 2000. IEEE, 2000. Vol. 1. doi:10.1109/ific.2000.862662Alexiev K. M., Bojilov L. V. A Hough Transform Track Initiation Algorithm for Multiple Passive Sensors. Proc. of the 3rd Intern. Conf. on Information Fusion, Paris, France, 10–13 July 2000. IEEE, 2000, vol. 1. doi:10.1109/ific.2000.862662Multitarget track initiation using а modified Hough transform / T. Lo, J. Litva, H. Leung, A. W. Bridgewater // AGARD, Pointing and Tracking Systems. England: Technivision Services, 1994. P. 25-1–25-8.Lo Т., Litva J., Leung Н., Bridgewater А. W. Multitarget Track Initiation Using a Modified Hough Transform. AGARD, Pointing and Tracking Systems. England, Technivision Services, 1994, pp. 25-1–25-8.Cooperative track initiation for distributed radar network based on target track information / H. Liu, H. W. Liu, X. Dan, S. Zhou, J. Liu // IET Radar Sonar Navig. 2016. Vol. 10, № 4. P. 735–741. doi:10.1049/iet-rsn.2015.0312Liu H., Liu H. W., Dan X., Zhou S., Liu J. Cooperative Track Initiation for Distributed Radar Network Based on Target Track Information. IET Radar Sonar Navig. 2016, vol. 10, no. 4, pp. 735–741. doi:10.1049/ietrsn.2015.0312Spratling А. А neural implementation of the Hough transform and the advantages of explaining away // Image and Vision Computing. 2016. Vol. 52. P. 15–24. doi:10.1016/j.imavis.2016.05.001Spratling А. А Neural Implementation of the Hough Transform and the Advantages of Explaining Away. Image and Vision Computing. 2016, vol. 52, рр. 15–24. doi:10.1016/j.imavis.2016.05.001Carlson B. D., Evans E. D., Wilson S. L. Search radar detection and track with the Hough transform. Part II: Detection Statistics // IEEE Trans. on Aerospace and Electronic Systems. 1994. Vol. 30, no. 1. P. 109–115. doi:10.1109/7.250411Carlson B. D., Evans E. D., Wilson S. L. Search Radar Detection and Track with the Hough Transform, Part II: Detection Statistics. IEEE Trans. on Aerospace and Electronic Systems. 1994, vol. 30, no. 1, p. 109–115. doi:10.1109/7.250411Монаков А. А. Обнаружитель движущейся цели для оптического приемника на основе алгоритма Хафа // XIX Междунар. науч.-техн. конф. "Радиолокация, навигация, связь". 2013. Т. 3. С. 1434–1443.Monakov A. A. Detector of a Moving Optic Target Based on the Hough Transform. Proc. of XIX Intern. Conf. "Radar, Navigation and Communication". 2013, vol. 3. pp. 1434–1443. (In Russ.)Монаков А. А. Обнаружитель движущейся цели для радиолокационного приемника на основе алгоритма Хафа // XX Междунар. науч.-техн. конф. "Радиолокация, навигация, связь". 2014. Т. 3. С. 1584–1594.Monakov A. A. Detector of a Moving Radar Target Based on the Hough Transform. Proc. of XX Intern. Conf. "Radar, Navigation and Communication". 2014, vol. 3, pp. 1584–1594. (In Russ.)Carlson B. D., Evans E. D., Wilson S. L. Search radar detection and track with the Hough transform, Part III: Detection performance with binary integration // IEEE Trans. on Aerospace and Electronic Systems. 1994. Vol. 30, no. 1. P. 116–125. doi:10.1109/7.250412Carlson B. D., Evans E. D., Wilson S. L. Search Radar Detection and Track with the Hough Transform, Part III: Detection Performance with Binary Integration. IEEE Trans. on Aerospace and Electronic Systems. 1994, vol. 30, no. 1, p. 116–125. doi:10.1109/7.250412Prior knowledge-based statistical estimation of linear false tracks in uniform distributed clutter / F. Wang, W. Lu, C. Shi, J. Zhou // IET Radar Sonar & Navigation. 2021. Vol. 15, № 10. P. 1237–1246. doi:10.1049/rsn2.12107Wang F., Lu W., Shi C., Zhou J. Prior KnowledgeBased Statistical Estimation of Linear False Tracks in Uniform Distributed Clutter. IET Radar Sonar & Navigation. 2021, vol. 15, no. 10, pp. 1237–1246. doi:10.1049/rsn2.12107Imiya A., Hada T., Tatara K. The Hough Transform without the Accumulators // Structural, Syntactic, and Statistical Pattern Recognition. Lecture Notes in Computer Science. 2002. Vol. 2396. P. 823–832. doi:10.1007/3-540-70659-3_87Imiya A., Hada T., Tatara K. The Hough Transform without the Accumulators. Structural, Syntactic, and Statistical Pattern Recognition. Lecture Notes in Computer Science. 2002, vol. 2396, pp. 823–832. doi:10.1007/3-540-70659-3_87A robust and accumulator-free ellipse Hough transform / X. Yu, H. W. Leong, C. Xu, Q. Tian // Proc. of the 12th ACM Intern. Conf. on Multimedia. New York, USA, 10–16 Oct. 2004. P. 256–259. doi:10.1145/1027527.1027585Yu X., Leong H. W., Xu C., Tian Q. A Robust and Accumulator-Free Ellipse Hough Transform. Proc. of the 12th ACM Intern. Conf. on Multimedia. New York, USA, 10–16 Oct. 2004, pp. 256–259. doi:10.1145/1027527.1027585Kurniawan R., Fuadi Z., Adriman R. Accumulator-free Hough Transform for Sequence Collinear Points // Aceh Intern. J. of Science and Technology. 2021. P. 74–83. doi:10.13170/aijst.10.2.20894Kurniawan R., Fuadi Z., Adriman R. Accumulator-free Hough Transform for Sequence Collinear Points. Aceh Intern. J. of Science and Technology. 2021, pp. 74–83. doi:10.13170/aijst.10.2.20894

The authors declare that there are no conflicts of interest present.