informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-867Research ArticleОБРАБОТКА СИГНАЛОВ, ИЗОБРАЖЕНИЙ, РЕЧИ, ТЕКСТА И РАСПОЗНАВАНИЕ ОБРАЗОВSIGNAL, IMAGE, SPEECH, TEXT PROCESSING AND PATTERN RECOGNITIONАлгоритм быстрого вычисления локальных гистограмм изображения на видеокартеАlgorithm of fast computation of local image histograms on video card1ТроцкийФ. С.TrotskiPh. S.

младший научный сотрудник

Junior Researcher

trotskiphilipp@gmail.comЗалесскийБ. А.ZaleskyB. A.

доктор физикоматематических наук, заведующий лабораторией обработки и распознавания изображений

Dr. Sc. (Phys.-Math.), Head of the Laboratory of Image Processing and Recognition

zalesky@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук Беларуси, МинскThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk2019260320191614957Copyright © Троцкий Ф.С., Залесский Б.А., 20192019Троцкий Ф.С., Залесский Б.А.Trotski P.S., Zalesky B.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/867

Рассматривается алгоритм параллельного вычисления гистограмм различных типов, в том числе яркости и ориентированного градиента, предназначенный для выполнения на видеокартах, которые поддерживают массивные параллельные вычисления. В настоящее время локальные гистограммы используются для решения задач обработки и распознавания изображений, однако их применение ограничено из-за большого времени вычисления для всех пикселов изображения. Одна из основных трудностей, возникающих при вычислении этих векторных признаков, – большое число конфликтов одновременного доступа к ячейкам видеопамяти, в которые записываются одинаковые значения характеристики. В предложенном алгоритме существенно уменьшено число конфликтов одновременного доступа, что позволило значительно уменьшить время его выполнения. Так, например, девятимерные векторы локальных гистограмм ориентированного градиента для всех 256×256 окон изображения размера HD вычисляются на видеокарте GPU NVIDIA GeForce GTX 1060 за 1,9 мс, в то время как на процессоре Intel Core i7-6700 c частотой 3,4 ГГц – за 151 мс.

An algorithm of parallel computation of image histograms of different types, including brightness and oriented gradient ones, on video cards of various types is presented. Now local histograms are used for solution of some tasks of image processing and recognition, but their application is restricted due to the long computational time. One of the difficulties appearing during parallel computations of this vector feature is the large number of conflicts of simultaneous access to video memory sells. In the developed version, the number of conflicts of simultaneous access are many times reduced. It accelerated the computations. For instance, 9D vectors of histograms of oriented gradient for all 256×256 windows of a HD image are calculated on the GPU NVIDIA GeForce GTX 1060 within 1,9 msec, whereas the same computations made by the CPU Intel Core i7-6700 take 151 msec.

изображениялокальные гистограммыалгоритмпараллельная версияCUDAimageslocal histogramsalgorithmparallel versionCUDAReferencesGonzalez, R. Цифровая обработка изображений / R. Gonsalez, R. Woods. – М. : Техносфера, 2005. – 1070 c.Gonzalez R., Woods R. Cifrovaya obrabotka izobrazhenij [Digital Image Processing]. Moscow, Tehnosfera, 2005, 1070 p.Dalal, N. Histograms of oriented gradients for human detection / N. Dalal, B. Triggs // Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR’2005). – San Diego, 2005. – Vol. 1. – P. 886–893.Dalal N., Triggs B. Histograms of oriented gradients for human detection. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’2005). San Diego, 2005,Rotation invariant histogram of oriented gradients / M. Cheon [et al.] // Intern. J. of Fuzzy Logic and Intelligent Systems. – 2011. – Vol. 11, no. 4. – P. 293–298.vol. 1, pp. 886–893.Marimon, D. Orientation histogram-based matching for region tracking / D. Marimon, T. Ebrahimi // Eighth Intern. Workshop on Image Analysis for Multimedia Interactive Services (WIAMIS’07). – Santorini, Greece, 2007. – P. 8.Cheon M., Lee W., Hyun C.-H., Park M. Rotation invariant histogram of oriented gradients. International Journal of Fuzzy Logic and Intelligent Systems, 2011, vol. 11, no. 4, pp. 293–298.Ragb, H. Histogram of oriented phase and gradient (HOPG) descriptor for improved pedestrian detection / H. Ragb, V. Asari // IS&T Intern. Conf. on Electronic Imaging: Video Surveillance and Transportation Imaging Applications. – San Francisco, 2016.Marimon D., Ebrahimi T. Orientation histogram-based matching for region tracking. Eighth International Workshop on Image Analysis for Multimedia Interactive Services (WIAMIS’07). Santorini, Greece, 2007, p. 8.Ragb, H. Histogram of oriented phase (HOP): a new descriptor based on phase congruency / H. Ragb, V. Asari // Proc. SPIE 9869, Mobile Multimedia/Image Processing, Security, and Applications. – Bellingham, 2016. – Vol. 98690.Ragb H., Asari V. Histogram of oriented phase and gradient (HOPG) descriptor for improved pedestrian detection. IS&T International Conference on Electronic Imaging: Video Surveillance and Transportation Imaging Applications. San Francisco, 2016.Facial expression recognition based on facial components detection and HOG features / J. Chen [et al.] // Scientific Cooperations Intern. Workshops on Electrical and Computer Engineering Subfields, 22–23 Aug. 2014, Istanbul, Turkey. – Istanbul, 2014. – P. 64–69.Ragb H., Asari V. Histogram of oriented phase (HOP): a new descriptor based on phase congruency. Proceedings SPIE 9869, Mobile Multimedia/Image Processing, Security, and Applications. Bellingham, 2016,Harris, M. Using Shared Memory in CUDA C/C++ [Electronic recource] / M. Harris. – Mode of access: https://devblogs.nvidia.com/using-shared-memory-cuda-cc. – Date of access: 26.09.2018.vol. 98690. DOI: 10.1117/12.2225159Залесский, Б. А. Параллельная версия детектора экстремальных особых точек / Б. А. Залесский, Ф. С. Троцкий // Информатика. – 2018. – Т. 15, № 2. – С. 55–63.Chen J., Chen Z., Chi Z., Fu H. Facial expression recognition based on facial components detection and HOG features. Scientific Cooperations International Workshops on Electrical and Computer Engineering Subfields, 22–23 August 2014, Istanbul, Turkey. Istanbul, 2014, рр. 64–69.Булашев, С. В. Статистика для трейдеров / С. В. Булашев. – М. : Компания Спутник+, 2003. – 245 с.Harris M. Using Shared Memory in CUDA C/C++. Available at: https://devblogs.nvidia.com/usingshared-memory-cuda-cc (accessed 26.09.2018).Сандерс, Д. Технология CUDA в примерах: введение в программирование графических процессоров : пер. с англ. А. А. Слинкина / Д. Сандерс, Э. Кэндрот. – М. : ДМК Пресс, 2013. – 234 c.Zalesky B. A., Trotski Ph. S. Parallelnaya versiya detektora ekstremalnyih osobyih tochek [Parallel version of detector of extremal key points]. Informatika [Informatics], 2018, vol. 15, no. 2, pp. 55–63 (in Russian).Bulashev S. V. Statistika dlya treyderov. Statistics for traders. Moscow, Kompanija Sputnik+, 2003, 245 p. (in Russian).Bulashev S. V. Statistika dlya treyderov. Statistics for traders. Moscow, Kompanija Sputnik+, 2003, 245 p. (in Russian).Sanders D., Kendrot E. CUDA by Example: An Introduction to General-Purpose GPU Programming. Boston, Addison-Wesley Professional, 2010, 320 p.Sanders D., Kendrot E. CUDA by Example: An Introduction to General-Purpose GPU Programming. Boston, Addison-Wesley Professional, 2010, 320 p.

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