LECTURE 0 :
14th December 2019 11:00 EET
Fast 1D/2D convolution algorithms for machine learning and computer vision
2D convolutions play an extremely important role in machine learning, as they form the first layers of Convolutional Neural Networks (CNNs). They are also very important for computer vision (template matching through correlation, correlation trackers) and in image processing (image filtering/denoising/restoration). 3D convolutions are very important for machine learning (video analysis through CNNs) and for video filtering/denoising/restoration. 1D convolutions are extensively used in digital signal processing (filtering/denoising) and analysis (also through CNNs)
Therefore, 1D/2D/3D convolution algorithms are very important both for machine learning and for signal/image/video processing and analysis. As their computational complexity is of the order O(N^2), O(N^4) and O(N^6) respectively their fast execution is a must.
This lecture will overview linear and cyclic convolution. Then it will present their fast execution through FFTs, resulting in algorithms having computational complexity of the order O(Nlog2N), O(N^2log2N) for 1D and 2D convolutions respectively. Finally, optimal Winograd 1D and 2D convolution algorithms will be presented having theoretically minimal number of computations.
LECTURER
Prof. Ioannis Pitas (IEEE fellow, IEEE Distinguished Lecturer, EURASIP fellow) received the Diploma and PhD degree in Electrical Engineering, both from the Aristotle University of Thessaloniki, Greece. Since 1994, he has been a Professor at the Department of Informatics of the same University. He served as a Visiting Professor at several Universities.
His current interests are in the areas of image/video processing, machine learning, computer vision, intelligent digital media, human centered interfaces, affective computing, 3D imaging and biomedical imaging. He has published over 1138 papers, contributed in 50 books in his areas of interest and edited or (co-)authored another 11 books. He has also been member of the program committee of many scientific conferences and workshops. In the past he served as Associate Editor or co-Editor of 9 international journals and General or Technical Chair of 4 international conferences. He participated in 70 R&D projects, primarily funded by the European Union and is/was principal investigator/researcher in 42 such projects. He has 30000+ citations to his work and h-index 81+ (Google Scholar).
Prof. Pitas leads the big European H2020 R&D project MULTIDRONE: https://multidrone.eu/. He is chair of the Autonomous Systems initiative https://ieeeasi.signalprocessingsociety.org.
SAMPLE LECTURE MATERIAL.
LECTURE 1 RECORDING
Fast 1D/2D convolution algorithms for machine learning and computer vision
RELATED LITERATURE
[1] Y. LeCun, Y. Bengio, and G. Hinton, \Deep learning," nature, vol. 521, no. 7553, p. 436, 2015.
[2] A. V. Oppenheim, Discrete-time signal processing. Pearson Education India, 1999.
[3] J. F. Henriques, R. Caseiro, P. Martins, and J. Batista, \High-speed tracking with kernelized correlation _lters," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 3, pp. 583{596, 2015.
[4] O. Zachariadis, V. Mygdalis, I. Mademlis, N. Nikolaidis, and I. Pitas, 2d visual tracking for Sports uav cinematography applications," in Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP), 2017.19
[5] S. Winograd, Arithmetic complexity of computations, vol. 33. Siam, 1980.
[6] J. H. McClellan and C. M. Rader, \Number theory in digital signal processing," 1979.
[7] H. J. Nussbaumer, Fast Fourier transform and convolution algorithms. Springer Science & Business Media, 1981.
[8] I. Pitas, Computational complexity study of multidimensional digital signal processing algorithms. Aristotle University of Thessaloniki, Greece, 1985.
[9] I. Pitas and M. Strintzis, \Multidimensional cyclic convolution algorithms with minimal multiplicative complexity," IEEE transactions on acoustics, speech, and signal processing, vol. 35, no. 3, pp. 384-390, 1987.
[10] S. Chetlur, C. Woolley, P. Vandermersch, J. Cohen, J. Tran, B. Catanzaro, and E. Shelhamer, \cudnn: E_cient primitives for deep learning," arXiv preprint arXiv:1410.0759, 2014.
[11] A. Lavin and S. Gray, \Fast algorithms for convolutional neural networks," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4013{4021, 2016.
[12] D. Budden, A. Matveev, S. Santurkar, S. R. Chaudhuri, and N. Shavit, Deep tensor convolution on multicores," arXiv preprint arXiv:1611.06565, 2016.
[13] Z. Jia, A. Zlateski, F. Durand, and K. Li, \Optimizing n-dimensional, winograd-based convolution for manycore cpus," in Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 109{123, ACM, 2018.
[14] I. Pitas, Digital image processing algorithms and applications. John Wiley & Sons, 2000.
[15] D. B. Kirk andW. H.Wen-Mei, Programming massively parallel processors: a hands-on approach. Morgan kaufmann, 2016.
[16] V. Sze, Y.-H. Chen, T.-J. Yang, and J. S. Emer, \E_cient processing of deep neural networks: A tutorial and survey," Proceedings of the IEEE, vol. 105, no. 12, pp. 2295{2329, 2017.
[17] V. Strassen, \Gaussian elimination is not optimal," Numerische mathematik, vol. 13, no. 4, pp. 354-356, 1969.
[18] J. Cong and B. Xiao, \Minimizing computation in convolutional neural networks," in international conference on arti_cial neural networks, pp. 281- 290, Springer, 2014.
[19] I. Pitas and M. Strintzis, \Algorithms and structures for convolutions over galois _elds," in 9-me Colloque sur le traitement du signal et des images, FRA, 1983, GRETSI, Groupe d'Etudes du Traitement du Signal et des Images, 1983.
[20] R. Twogood, M. Ekstrom, and S. Mitra, \Optimal sectioning procedure for the implementation of 2-d digital _lters," IEEE Transactions on Circuits and Systems, vol. 25, no. 5, pp. 260-269, 1978.
[21] R. Agarwal and J. Cooley, \New algorithms for digital convolution," IEEE
Transactions on Acoustics, Speech, and Signal Processing, vol. 25, no. 5, pp. 392{410, 1977.
[22] N. I. Mademlis, V. Mygdalis and I.Pitas, \Challenges in autonomous uav cinematography: An overview," IEEE International Conference on Multimedia and Expo (ICME), pp. 392-410, 1977.
[23] P. Ribenboim, Classical theory of algebraic numbers. Springer Science & Business Media, 2013.