(47-1) 09 * << * >> * Русский * English * Содержание * Все выпуски

Разработка алгоритмов цифровой обработки изображений на основе метода Винограда в общем виде и анализ их вычислительной сложности
П.А. Ляхов 1,2, Н.Н. Нагорнов 1, Н.Ф. Семёнова 1, А.Ш. Абдулсалямова 2

1 Северо-Кавказский федеральный университет,
355017, Россия, г. Ставрополь, ул. Пушкина, д. 1;
2 Северо-Кавказский центр математических исследований,
355017, Россия, г. Ставрополь, ул. Пушкина, д. 1

 PDF, 978 kB

DOI: 10.18287/2412-6179-CO-1146

Страницы: 68-78.

Аннотация:
Стремительный рост количественных и качественных характеристик цифровых визуальных данных приводит к необходимости улучшения эксплуатационных показателей современных устройств обработки изображений. В данной работе предложены новые алгоритмы цифровой обработки двумерных изображений на основе метода Винограда в общем виде. Анализ полученных результатов показал, что использование метода Винограда сокращает вычислительную сложность обработки изображений до 84% по сравнению с традиционным прямым методом цифровой фильтрации в зависимости от параметров фильтра и фрагментов изображения, не влияя при этом на качество обработки изображения. Составленные матрицы преобразования метода Винограда и разработанные алгоритмы могут быть использованы в системах обработки изображений для улучшения эксплуатационных характеристик современных микроэлектронных устройств, осуществляющих очистку от шума и сжатие изображений, а также распознавание образов. Перспективным направлением дальнейших исследований является аппаратная реализация разработанных алгоритмов на современных устройствах вычислительной техники, таких как программируемые пользователем вентильные матрицы и интегральные схемы специального назначения, разработка алгоритмов цифровой обработки изображений, используемой в сверточных нейронных сетях, на основе метода Винограда в общем виде для одномерных вейвлет-фильтров с децимацией и для свертки с шагом.

Ключевые слова:
цифровая обработка изображений, цифровая фильтрация, метод Винограда, вычислительная сложность.

Благодарности
Авторы выражают благодарность СКФУ за помощь в рамках проекта поддержки малых научных групп и отдельных ученых. Исследование в параграфе 1 проведено в Северо-Кавказском центре математических исследований в рамках соглашения с Министерством науки и высшего образования Российской Федерации (соглашение № 075-02-2022-892). Исследование в параграфе 2 проведено при поддержке Российского научного фонда (проект № 21-71-00017).

Цитирование:
Ляхов, П.А. Разработка алгоритмов цифровой обработки изображений на основе метода Винограда в общем виде и анализ их вычислительной сложности / П.А. Ляхов, Н.Н. Нагорнов, Н.Ф. Семёнова, А.Ш. Абдулсалямова // Компьютерная оптика. – 2023. – Т. 47, № 1. – С. 68-78. – DOI: 10.18287/2412-6179-CO-1146.

Citation:
Lyakhov PA, Nagornov NN, Semyonova NF, Abdulsalyamova AS. Development of digital image processing algorithms based on the Winograd method in general form and analysis of their computational complexity. Computer Optics 2023; 47(1): 68-78. DOI: 10.18287/2412-6179-CO-1146.

References:
  1. Gonzalez RC, Woods RE. Digital image processing. Pearson Education Limited; 2018.
  2. Rossinelli D, Fourestey G, Schmidt F, Busse B, Kurtcuoglu V. High-throughput lossy-to-lossless 3d image compression. IEEE Trans Med Imaging 2021; 40(2): 607-620. DOI: 10.1109/TMI.2020.3033456.
  3. Smistad E, Østvik A, Pedersen A. High performance neural network inference, streaming, and visualization of medical images using FAST. IEEE Access 2019; 7: 136310-136321. DOI: 10.1109/ACCESS.2019.2942441.
  4. Avenido HGD, Crisostomo RV. Image reconstruction from a large number of projections in proton and 12C ions computed tomography using sequential and parallel ART algorithms. Procedia Comput Sci 2022; 197: 126-134. DOI: 10.1016/J.PROCS.2021.12.126.
  5. Mittal S, Vibhu. A survey of accelerator architectures for 3D convolution neural networks. J Syst Archit 2021; 115: 102041. DOI: 10.1016/J.SYSARC.2021.102041.
  6. Chervyakov NI, Lyakhov PA, Nagornov NN, Valueva MV, Valuev GV. Hardware implementation of a convolutional neural network using calculations in the residue number system. Computer Optics 2019; 43(5): 857-868. DOI: 10.18287/2412-6179-2019-43-5-857-868.
  7. Le NT, Wang J-W, Le DH, Wang C-C, Nguyen TN. Fingerprint enhancement based on tensor of wavelet subbands for classification. IEEE Access 2020; 8: 6602-6615. DOI: 10.1109/ACCESS.2020.2964035.
  8. Winograd S. Arithmetic complexity of computations. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics; 1980. ISBN: 0-89871-163-0.
  9. Lavin A, Gray S. Fast algorithms for convolutional neural networks. 2016 IEEE Conf on Computer Vision and Pattern Recognition (CVPR) 2016: 4013-4021. DOI: 10.1109/CVPR.2016.435.
  10. Yepez J, Ko SB. Stride 2 1-D, 2-D, and 3-D Winograd for convolutional neural networks. IEEE Trans Very Large Scale Integr Syst 2020; 28(4): 853-863. DOI: 10.1109/TVLSI.2019.2961602.
  11. Mehrabian A, Miscuglio M, Alkabani Y, Sorger VJ, El-Ghazawi T. A Winograd-based integrated photonics accelerator for convolutional neural networks. IEEE J Sel Top Quantum Electron 2020; 26(1): 6100312. DOI: 10.1109/JSTQE.2019.2957443.
  12. Shen J, Huang Y, Wen M, Zhang C. Toward an efficient deep pipelined template-based architecture for accelerating the entire 2-D and 3-D CNNs on FPGA. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 2020; 39(7): 1442-1455. DOI: 10.1109/TCAD.2019.2912894.
  13. Wang X, Wang C, Cao J, Gong L, Zhou X. WinoNN: Optimizing FPGA-based convolutional neural network accelerators using sparse Winograd algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 2020; 39(11): 4290-4302. DOI: 10.1109/TCAD.2020.3012323.
  14. Wu D, Fan X, Cao W, Wang L. SWM: A high-performance Sparse-Winograd matrix multiplication CNN accelerator. IEEE Trans Very Large Scale Integr Syst 2021; 29(5): 936-949. DOI: 10.1109/TVLSI.2021.3060041.
  15. Valueva M, Lyakhov P, Valuev G, Nagornov N. Digital filter architecture with calculations in the residue number system by Winograd method F (2×2, 2×2). IEEE Access 2021; 9: 143331-143340. DOI: 10.1109/ACCESS.2021.3121520.
  16. Waring EFRS. VII. Problems concerning interpolations. Philos Trans R Soc 1779; 69: 59-67. DOI: 10.1098/RSTL.1779.0008.
  17. Horn RA, Johnson CR. Topics in matrix analysis. Cambridge: Cambridge University Press; 1991. ISBN: 978-0-521-30587-7.
  18. Valueva MV, Lyakhov PA, Nagornov NN, Valuev GV. High-performance digital image filtering architectures in the residue number system based on the Winograd method. Computer Optics 2022; 46(5): 752-762. DOI: 10.18287/2412-6179-CO-933.
  19. Zimmerman, R. Binary adder architectures for cell-based VLSI and their synthesis. A dissertation thesis for the degree of Doctor of technical sciences. Konstanz Hartung-Gorre; 1998. Diss ETH No 12480.
  20. Kogge PM, Stone HS. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans Comput 1973; C-22(8): 786-793. DOI: 10.1109/TC.1973.5009159.
  21. Parhami B. Computer arithmetic: Algorithms and hardware designs. Oxford University Press; 2010.
  22. Lyakhov P, Valueva M, Valuev G, Nagornov N. High-performance digital filtering on truncated multiply-accumulate units in the residue number system. IEEE Access 2020; 8: 209181-209190. DOI: 10.1109/ACCESS.2020.3038496.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20