(47-1) 09 * << * >> * Russian * English * Content * All Issues

Development of digital image processing algorithms based on the Winograd method in general form and analysis of their computational complexity
P.A. Lyakhov 1,2, N.N. Nagornov 1, N.F. Semyonova 1, A.S. Abdulsalyamova 1,2

1 North-Caucasus Federal University, 355017, Stavropol, Russia, Pushkin street, 1;
2 North-Caucasus Center for Mathematical Research, 355017, Stavropol, Russia, Pushkin street, 1

 PDF, 978 kB

DOI: 10.18287/2412-6179-CO-1146

Pages: 68-78.

Full text of article: Russian language.

Abstract:
The fast increase of the amount of quantitative and qualitative characteristics of digital visual data calls for the improvement of the performance of modern image processing devices. This article proposes new algorithms for 2D digital image processing based on the Winograd method in a general form. An analysis of the obtained results showed that the use of the Winograd method reduces the computational complexity of image processing by up to 84% compared to the traditional direct digital filtering method depending on the filter parameters and image fragments, while not affecting the quality of image processing. The resulting Winograd method transformation matrices and the algorithms developed can be used in image processing systems to improve the performance of the modern microelectronic devices that carry out image denoising, compression, and pattern recognition. Research directions that show promise for further research include hardware implementation on a field-programmable gate array and application-specific integrated circuit, development of algorithms for digital image processing based on the Winograd method in a general form for a 1D wavelet filter bank and for stride convolution used in convolutional neural networks.

Keywords:
digital image processing, digital filtering, Winograd method, computational complexity.

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.

Acknowledgements:
The authors thank the North-Caucasus Federal University for the award of funding in the contest of competitive projects of scientific groups and individual scientists of North-Caucasus Federal University. The research in section 1 was supported by the North-Caucasus Center for Mathematical Research under agreement with the Ministry of Science and Higher Education of the Russian Federation (Agreement No. 075-02-2022-892). The research in section 2 was supported by the Russian Science Foundation (Project No. 21-71-00017).

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
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20