В работе строится вычислительно эффективная реализация алгоритма Брейди расчета быстрого преобразования Хафа (БПХ) на отечественном сопроцессоре СРСА, входящем в состав системы-на-кристалле 1890ВМ9Я “КОМДИВ128-М”. Показывается, что БПХ находит широкое применение в задачах анализа изображений, от зрительных систем беспилотного транспорта до вычислительной рентгеновской томографии. Приводится и анализируется с точки зрения низкоуровневой имплементации классическая рекурсивная реализация БПХ. Впервые рассматривается более эффективный нерекурсивный вариант алгоритма, для которого проводится анализ нагрузки на вычислители и память сопроцессора, а также экспериментальные замеры производительности. Показывается, что теоретически возможная производительность нерекурсивного алгоритма на СРСА составляет 800 Мопс, при этом максимально достижимая на практике производительность составила 470 Мопс, а максимальное полученное экспериментально значение оказалось 406 Мопс. При этом загрузка вычислителей сопроцессора достигла 18%. Таким образом, несмотря на относительно малое число арифметических операций в методе, использование сопроцессора оказывается целесообразным.
Идентификаторы и классификаторы
- eLIBRARY ID
- 46385983
Задачи искусственного интеллекта в области технических зрительных систем отличаются большими объемами однородной информации, которые необходимо обработать для принятия даже самых элементарных решений. При этом зрительные системы эксплуатируются, как правило, в режиме реального времени, что не характерно для большинства иных областей, работающих с “большими данными”. Требования к быстрой обработке больших объемов данных приводят к тому, что классические высокопроизводительные алгоритмы (наряду с популярными нейросетевыми методами) продолжают занимать важное место в анализе зрительной информации. В данной работе мы сосредоточимся на одном весьма известном вычислительно эффективном инструменте анализа изображений, а именно – алгоритме Брейди вычисления быстрого приближенного дискретного преобразования Радона [1], часто называемом также быстрым преобразованием Хафа (БПХ) [2].
Список литературы
- Brady M.L. A fast discrete approximation algorithm for the Radon transform // SIAM Journal on Computing. 1998. V. 27. № 1. P. 91-99.
- Nikolaev D.P., Karpenko S.M., Nikolayev I.P. Hough Transform: Underestimated Tool In The Computer Vision Field // Proceedings of 22nd European Conference on Modelling and Simulation. 2008. P. 238-243. EDN: PGAWGZ
- Hough P.V.C. Machine Analysis of Bubble Chamber Pictures // Conf. Proc. C. 1959. V. 590914. P. 554-558.
- Duda R.O., Hart P.E. Use of the Hough Transformation to Detect Lines and Curves in Pictures // Commun. ACM. 1972. V. 15. № 1. P. 11-15.
- Асватов Е.Н., Ершов Е.И., Николаев Д.И. Робастная ортогональная линейная регрессия для маломерных гистограмм // Сенсорные системы. 2017. Т. 31. № 4. С. 331-342. EDN: ZTUPMD
- Nikolaev D.P., Nikolayev P.P. Linear color segmentation and its implementation // Computer Vision and Image Understanding. 2004. V. 94. № 1. P. 115-139. Special Issue: Colour for Image Indexing and Retrieval. EDN: LIVKFJ
- Kunina I.A., Gladilin S.A., Nikolaev D.P. Blind compensation of radial distortion in a single image using fast Hough transform // Computer Optics. 2016. V. 40. № 3. P. 395-403. EDN: WDNFAB
- A new approach to highway lane detection by using Hough transform technique / Nur Shazwani Aminuddin, Masrullizam Mat Ibrahim, Nursabillilah Mohd Ali et al. // Journal of Information and Communication Technology. 2017. V. 16. № 2. P. 244-260.
- Кунина И.А., Панфилова Е.И., Поволоцкий М. Детектирование пешеходных переходов на изображениях дороги на основе метода динамического выравнивания временных рядов // Труды Института системного анализа Российской Академии наук (ИСА РАН). 2018. Т. 68. № S1. С. 23-31. EDN: VMVBXY
-
Panfilova E.I., Shipitko O.S., Kunina I.A. Fast Hough Transform-Based Road Markings Detection For Autonomous Vehicle // Proc. SPIE 11605, Thirteenth International Conference on Machine Vision (ICMV 2020). 2021. V. 11605. P. 671-680. -
Jahan R., Suman P., Singh D.K. Lane detection using canny edge detection and hough transform on raspberry Pi // International Journal of Advanced Research in Computer Science. 2018. V. 9. № S2. P. 85-89. -
Energy-Efficient Hardware Implementation of Road-Lane Detection Based on Hough Transform with Parallelized Voting Procedure and Local Maximum Algorithm / J. Guan, F. An, X. Zhang et al. // IEICE Transactions on Information and Systems. 2019. V. E102.D. № 6. P. 1171-1182. -
Thongpan Narathip, Rattanasiriwongwut Montean, Ketcham Mahasak. Lane Detection Using Embedded System // International Journal of the Computer, the Internet and Management. 2020. V. 28. № 2. P. 46-51. -
Котов А.А., Коноваленко И.А., Николаев Д.П. Прослеживание объектов в видеопотоке, оптимизированное с помощью быстрого преобразования Хафа // Информационные технологии и вычислительные системы. 2015. № 1. С. 56-68. EDN: UXQJQP -
Бочаров А.Д. Метод линейной регрессии, устойчивый к экстремальным стационарным помехам // Сенсорные системы. 2020. Т. 34. № 1. С. 44-56. EDN: NFUKHF -
Green A.I., Schwartz R., Dodge J., Smith N.A., Etzioni O. // Communications of the ACM. 2020. V. 63. № 12. P. 54-63. -
Tropin D.V., Ilyuhin S.A., Nikolaev D.P., Arlazarov V.V. Approach for Document Detection by Contours and Contrasts. 2020. arXiv:2008.02615 [cs.CV]. EDN: XPOOMT -
Bezmaternykh P.V., Nikolaev D.P. A document skew detection method using fast Hough transform // Proc. SPIE 11433, Twelfth International Conference on Machine Vision (ICMV 2019). 2020. V. 11433. P. 132-137. EDN: XLISLT -
Гайер А.В., Шешкус А.В. Нейросетевая детекция верхней и базовой линий текстовой строки на изображении // XII мультиконференция по проблемам управления (МКПУ-2019). 2019. С. 53-58. EDN: KKECIK -
Slant rectification in Russian passport OCR system using fast Hough transform / E. Limonova, P. Bezmaternykh, D. Nikolaev, V. Arlazarov // Proc. SPIE 10341, Ninth International Conference on Machine Vision (ICMV 2016). 2017. V. 10341. P. 127-131. EDN: XNUQWI -
Martynov S.I., Bezmaternykh P.V. Aztec core symbol detection method based on connected components extraction and contour signature analysis // Proc. SPIE 11433, Twelfth International Conference on Machine Vision (ICMV 2019). 2020. V. 11433. P. 27-34. EDN: HUNIII -
Bulatov K.B., Chukalina M.V., Nikolaev D.P. Fast X-ray sum calculation algorithm for computed tomography // Bulletin of the South Ural State University, Ser.: Mathematical Modelling Programming and Computer Software. 2020. V. 13. № 1. P. 95-106. EDN: KNCATU -
Dolmatova A.V., Chukalina M.V., Nikolaev D.P. Accelerated FBP for Computed Tomography Image Reconstruction // 2020 IEEE International Conference on Image Processing. 2020. P. 3030-3034. EDN: ONKVCW -
Рентгеновский компьютерный томограф - новый инструмент в распознавании / А. С. Ингачева, А. В. Шешкус, Т. С. Чернов и др. // Труды Института системного анализа Российской академии наук (ИСА РАН). 2018. Т. 68. № S1. С. 90-99. EDN: YOQRDN -
Monitored Reconstruction: Computed Tomography as an Anytime Algorithm / K. Bulatov, M. Chukalina, A. Buzmakov et al.// IEEE Access. 2020. V. 8. P. 110759-110774. EDN: UIRXAE -
Vanishing point detection with direct and transposed fast Hough transform inside the neural network / A. Sheshkus, A. Chirvonaya, D. Nikolaev, V. L. Arlazarov // Computer Optics. 2020. V. 44. № 5. P. 737-745. EDN: XFXXIH -
Sheshkus A., Nikolaev D. Houghencoder: Neural Network Architecture for Document Image Semantic Segmentation // 2020 IEEE International Conference on Image Processing. 2020. P. 1946-1950. EDN: QCJJYZ -
Lin Y., Pintea S.L., van Gemert J.C. Deep Hough-Transform Line Priors // Computer Vision - ECCV 2020. 2020. P. 323-340. EDN: XCTQVJ -
Deep Hough Transform for Semantic Line Detection/ Q. Han, K. Zhao, J. Xu, M.-M. Cheng // Computer Vision – ECCV 2020. 2020. P. 249–265. -
Line detection via a lightweight CNN with a Hough Layer / L. Teplyakov, K. Kaymakov, E. Shvets, D. Nikolaev // Proc. SPIE 11605, Thirteenth International Conference on Machine Vision (ICMV 2020). 2021. V. 11605. P. 376-385. -
Методы распознавания и обработки изображений в процессе строительства нефтяных и газовых скважин / С. А. Усилин, В. В. Арлазаров, Д. Н. Путинцев, И. А. Тарханов // Информационные технологии и вычислительные системы. 2020. № 1. С. 12-24. EDN: QKZACI -
Zhao H., Zhang Z. Improving Neural Network Detection Accuracy of Electric Power Bushings in Infrared Images by Hough Transform // Sensors. 2020. V. 20. № 10. P. 1-16. EDN: QBEBOM -
Ershov E.I., Karpenko S.M. Fast Hough Transform and approximation properties of dyadic patterns. 2017. arXiv: 1712.05615 [cs.CV]. -
Ершов Е.И., Терехин А.И., Николаев Д.И. Обобщение быстрого преобразования Хафа для трехмерных изображений // Информационные процессы. 2017. Т. 17. № 4. С. 294-308. EDN: ZXLUCN -
Mehta D.P., Sahni S. Handbook of Data Structures and Applications, Second Edition. Chapman & Hall/CRC, 2018. -
ФГУ ФНЦ НИИСИ РАН. Микросистема интегральная 1890ВМ9Я. Указания по применению, 2016. -
Сударева О.Ю. Эффективная реализация алгоритмов быстрого преобразования Фурье и свертки на микропроцессоре КОМДИВ128-РИО. М.: НИИСИ РАН, 2014. -
Райко Г.О., Мельканович В.С., Павловский Ю.А. Технология программирования многопроцессорной обработки гидроакустических сигналов на вычислительных устройствах семейства "КОМДИВ" // Гидроакустика. 2014. № 20 (2). С. 85-92. EDN: VQFQBP
Выпуск
АНАЛИЗ И ТРАНСФОРМАЦИЯ ПРОГРАММ
КОМПЬЮТЕРНАЯ АЛГЕБРА
АНАЛИЗ ДАННЫХ
ТЕОРИЯ ПРОГРАММИРОВАНИЯ: ФОРМАЛЬНЫЕ МОДЕЛИ И СЕМАНТИКА
Другие статьи выпуска
Непрерывно-временные сети Петри (НВСП), где каждому переходу сети ставится в соответствие временной интервал его срабатывания, используются для моделирования сложных параллельных систем, критичных с точки зрения безопасности. В общем случае, пространство состояний НВСП бесконечно и несчетно и, следовательно, анализ их поведения довольно сложен. ‘Истинно параллельная’ семантика представляет поведение НВСП в виде набора действий, отношение причинной зависимости между которыми моделируется частичным порядком, а отношение параллелизма – отсутствием порядка. Такое представление является более приемлемым для изучения следующих свойств параллельных систем: отсутствие тупиков, ‘справедливость’ (fairness), максимальный параллелизм и т.д. В статье вводятся и исследуются семантики шага (множества параллельных действий) и частичного порядка (множества упорядоченных по причине и параллельных действий) в контексте НВСП, поведение которых определяется слабой временной стратегией (т.е. ход модельного времени не ограничен срабатыванием переходов сети) и устойчиво атомарной техникой сброса часов (т.е. при сбросе часов срабатывание переходов сети рассматривается как атомарное действие).
Предложены шесть методов бинаризации алгоритма стаи ласточек для решения задачи отбора признаков по методу обертки. Эффективность выбранных подмножеств признаков оценивается двумя классификаторами: нечетким классификатором и классификатором на основе k-ближайших соседей. При поиске оптимального подмножества признаков учитывались количество признаков и точность классификации. Разработанные алгоритмы протестированы на наборах данных из репозитория KEEL. Для статистической оценки методов бинаризации использовался двухфакторный дисперсионный анализ Фридмана для связных выборок. Лучшие способности к отбору признаков показал гибридный метод, основанный на методе модифицированных алгебраических операций и введенной нами операции MERGE. Лучшая точность классификации получена с использованием метода V-образной функции трансформации.
Здесь дается описание алгоритмов и программного обеспечения для двух новых методов решения полиномиальных уравнений, основанных на построении выпуклого многоугольника. Первый метод позволяет находить приближенные корни многочлена с помощью многоугольника Адамара. Второй метод позволяет находить ветви алгебраической кривой вблизи ее особой точки и вблизи бесконечности с помощью многоугольника Ньютона и строить эскизы вещественных алгебраических кривых на плоскости. Указаны соответствующие геометрии и алгоритмы компьютерной алгебры, которые позволяют анализировать любые сложные случаи.
За последние годы популярность языка Go значительно возросла. Вместе с тем в настоящее время для языка Go существуют только легковесные статические анализаторы. Мы восполнили этот пробел, адаптировав статический анализатор Svace для поиска ошибок в программах на языке Go. Нами был реализован межпроцедурный и межмодульный статический анализатор имеющий чувствительность к потоку и путям. Для оценки результатов использовалось 10 проектов с открытым исходным кодом. 16 оцениваемых детекторов выдали 6817 предупреждений с 76 срабатываний.
Издательство
- Издательство
- ИЗДАТЕЛЬСТВО НАУКА
- Регион
- Россия, Москва
- Почтовый адрес
- 121099 г. Москва, Шубинский пер., 6, стр. 1
- Юр. адрес
- 121099 г. Москва, Шубинский пер., 6, стр. 1
- ФИО
- Николай Николаевич Федосеенков (Директор)
- E-mail адрес
- info@naukapublishers.ru
- Контактный телефон
- +7 (495) 2767735