ISSN 0132-3474

Язык: ru

Статья: ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХАФА С ИСПОЛЬЗОВАНИЕМ СОПРОЦЕССОРА CPCA (2021)

Читать

Читать онлайн

В работе строится вычислительно эффективная реализация алгоритма Брейди расчета быстрого преобразования Хафа (БПХ) на отечественном сопроцессоре СРСА, входящем в состав системы-на-кристалле 1890ВМ9Я “КОМДИВ128-М”. Показывается, что БПХ находит широкое применение в задачах анализа изображений, от зрительных систем беспилотного транспорта до вычислительной рентгеновской томографии. Приводится и анализируется с точки зрения низкоуровневой имплементации классическая рекурсивная реализация БПХ. Впервые рассматривается более эффективный нерекурсивный вариант алгоритма, для которого проводится анализ нагрузки на вычислители и память сопроцессора, а также экспериментальные замеры производительности. Показывается, что теоретически возможная производительность нерекурсивного алгоритма на СРСА составляет 800 Мопс, при этом максимально достижимая на практике производительность составила 470 Мопс, а максимальное полученное экспериментально значение оказалось 406 Мопс. При этом загрузка вычислителей сопроцессора достигла 18%. Таким образом, несмотря на относительно малое число арифметических операций в методе, использование сопроцессора оказывается целесообразным.

Ключевые фразы: ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХАФА С ИСПОЛЬЗОВАНИЕМ СОПРОЦЕССОРА CPCA

Автор (ы): Аникеев Фёдор Александрович, Райко Г. О., Лимонова Елена Евгеньевна, Алиев Михаил Александрович, Николаев Дмитрий Петрович

Журнал: ПРОГРАММИРОВАНИЕ

Идентификаторы и классификаторы

УДК: 004.932.2. Анализ изображения
eLIBRARY ID: 46385983

Для цитирования:

АНИКЕЕВ Ф. А., РАЙКО Г. О., ЛИМОНОВА Е. Е., АЛИЕВ М. А., НИКОЛАЕВ Д. П. ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХАФА С ИСПОЛЬЗОВАНИЕМ СОПРОЦЕССОРА CPCA // ПРОГРАММИРОВАНИЕ. 2021. № 5

Текстовый фрагмент статьи

Моя история просмотров (10)

01. Статья: ИНТЕЛЛЕКТУАЛЬНАЯ НЕЙРОСЕТЕВАЯ МАШИНА С ФУНКЦИЯМИ МЫШЛЕНИЯ

02. Статья: ЯЗЫКОВАЯ ПРОЕКЦИЯ ЭТНОСТЕРЕОТИПИЗАЦИИ СОВЕТОВАНИЯ В РАЗНОСТРУКТУРНЫХ ЯЗЫКАХ

03. Статья: МЕДИАТИЗАЦИЯ СФЕРЫ ЗДОРОВЬЯ ПОД ВЛИЯНИЕМ НОВЫХ МЕДИА: ОСНОВНЫЕ НАПРАВЛЕНИЯ СОЦИОЛОГИЧЕСКОГО ДИСКУРСА

04. Статья: Влияние околообъектовой среды на орбитальные космические аппараты

05. Статья: ГЕНЕТИЧЕСКИЕ ОСОБЕННОСТИ НЕРКИ ONCORHYNCHUS NERKA (WALBAUM, 1792) ОСТРОВНЫХ ПОП УЛЯЦИЙ РОССИЙСКОЙ ЧАСТИ АРЕАЛА

06. Статья: КОНТРОЛЛИНГ И РИСКИ ЕГО ФУНКЦИОНИРОВАНИЯ НА ПРЕДПРИЯТИИ

07. Статья: О ПРЕИМУЩЕСТВЕННОМ РАСПЫЛЕНИИ СПЛАВОВ ПРИ ИОННОЙ БОМБАРДИРОВКЕ

08. Статья: Влияние трансформации военной политики ФРГ на национальную безопасность России

09. Статья: Моделирование и идентификация элемента Пельтье TEC1‑12706 для применения в малообъемных биореакторах искусственного ЖКТ рыб

10. Статья: ПЕРСПЕКТИВЫ РАЗВИТИЯ ИСЛАМСКОЙ ИПОТЕКИ В РОССИИ

Список литературы

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

Выпуск

№ 5 (2021)

Кол-во страниц: 82 страницы

АНАЛИЗ И ТРАНСФОРМАЦИЯ ПРОГРАММ
КОМПЬЮТЕРНАЯ АЛГЕБРА
АНАЛИЗ ДАННЫХ
ТЕОРИЯ ПРОГРАММИРОВАНИЯ: ФОРМАЛЬНЫЕ МОДЕЛИ И СЕМАНТИКА

Другие статьи выпуска

‘ИСТИННО ПАРАЛЛЕЛЬНАЯ' СЕМАНТИКА НЕПРЕРЫВНО-ВРЕМЕННЫХ СЕТЕЙ ПЕТРИ СО СЛАБОЙ ВРЕМЕННОЙ И УСТОЙЧИВО АТОМАРНОЙ ПРОСТРАНСТВЕННОЙ СТРАТЕГИЯМИ (2021)

Авторы: Зубарев Алексей Юрьевич

Непрерывно-временные сети Петри (НВСП), где каждому переходу сети ставится в соответствие временной интервал его срабатывания, используются для моделирования сложных параллельных систем, критичных с точки зрения безопасности. В общем случае, пространство состояний НВСП бесконечно и несчетно и, следовательно, анализ их поведения довольно сложен. ‘Истинно параллельная’ семантика представляет поведение НВСП в виде набора действий, отношение причинной зависимости между которыми моделируется частичным порядком, а отношение параллелизма – отсутствием порядка. Такое представление является более приемлемым для изучения следующих свойств параллельных систем: отсутствие тупиков, ‘справедливость’ (fairness), максимальный параллелизм и т.д. В статье вводятся и исследуются семантики шага (множества параллельных действий) и частичного порядка (множества упорядоченных по причине и параллельных действий) в контексте НВСП, поведение которых определяется слабой временной стратегией (т.е. ход модельного времени не ограничен срабатыванием переходов сети) и устойчиво атомарной техникой сброса часов (т.е. при сбросе часов срабатывание переходов сети рассматривается как атомарное действие).

Сохранить в закладках

МЕТОДЫ БИНАРИЗАЦИИ АЛГОРИТМА СТАИ ЛАСТОЧЕК ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОТБОРА ПРИЗНАКОВ (2021)

Авторы: Слезкин Артем Олегович, Ходашинский Илья Александрович, Шелупанов Александр Александрович

Предложены шесть методов бинаризации алгоритма стаи ласточек для решения задачи отбора признаков по методу обертки. Эффективность выбранных подмножеств признаков оценивается двумя классификаторами: нечетким классификатором и классификатором на основе k-ближайших соседей. При поиске оптимального подмножества признаков учитывались количество признаков и точность классификации. Разработанные алгоритмы протестированы на наборах данных из репозитория KEEL. Для статистической оценки методов бинаризации использовался двухфакторный дисперсионный анализ Фридмана для связных выборок. Лучшие способности к отбору признаков показал гибридный метод, основанный на методе модифицированных алгебраических операций и введенной нами операции MERGE. Лучшая точность классификации получена с использованием метода V-образной функции трансформации.

Сохранить в закладках

АЛГОРИТМЫ И ПРОГРАММЫ ВЫЧИСЛЕНИЯ КОРНЕЙ МНОГОЧЛЕНА ОТ ОДНОЙ ИЛИ ДВУХ НЕИЗВЕСТНЫХ (2021)

Авторы: Батхин Александр Борисович, Брюно Александр Дмитриевич

Здесь дается описание алгоритмов и программного обеспечения для двух новых методов решения полиномиальных уравнений, основанных на построении выпуклого многоугольника. Первый метод позволяет находить приближенные корни многочлена с помощью многоугольника Адамара. Второй метод позволяет находить ветви алгебраической кривой вблизи ее особой точки и вблизи бесконечности с помощью многоугольника Ньютона и строить эскизы вещественных алгебраических кривых на плоскости. Указаны соответствующие геометрии и алгоритмы компьютерной алгебры, которые позволяют анализировать любые сложные случаи.

Сохранить в закладках

МЕЖПРОЦЕДУРНЫЙ СТАТИЧЕСКИЙ АНАЛИЗ ДЛЯ ПОИСКА ОШИБОК В ПРОГРАММАХ НА ЯЗЫКЕ GO (2021)

Авторы: Болотников И. В., Бородин Алексей Евгеньевич

За последние годы популярность языка Go значительно возросла. Вместе с тем в настоящее время для языка Go существуют только легковесные статические анализаторы. Мы восполнили этот пробел, адаптировав статический анализатор Svace для поиска ошибок в программах на языке Go. Нами был реализован межпроцедурный и межмодульный статический анализатор имеющий чувствительность к потоку и путям. Для оценки результатов использовалось 10 проектов с открытым исходным кодом. 16 оцениваемых детекторов выдали 6817 предупреждений с 76 срабатываний.

Сохранить в закладках

Издательство

Издательство: ИЗДАТЕЛЬСТВО НАУКА
Регион: Россия, Москва
Почтовый адрес: 121099 г. Москва, Шубинский пер., 6, стр. 1
Юр. адрес: 121099 г. Москва, Шубинский пер., 6, стр. 1
ФИО: Николай Николаевич Федосеенков (Директор)
E-mail адрес: info@naukapublishers.ru
Контактный телефон: +7 (495) 2767735
Сайт: https://naukapublishers.ru

Все права на тексты и товарные знаки принадлежат их законным владельцам. Подробнее...

Сайт https://scinetwork.ru (далее – сайт) работает по принципу агрегатора – собирает и структурирует информацию из публичных источников в сети Интернет, то есть передает полнотекстовую информацию о товарных знаках в том виде, в котором она содержится в открытом доступе.

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

Все права на товарные знаки принадлежат их законным владельцам!

Сайт носит исключительно информационный характер, и предоставляемые им сведения являются открытыми публичными данными.

Администрация сайта не несет ответственность за какие бы то ни было убытки, возникающие в результате доступа и использования сайта.

Спасибо, понятно.