Fast 2D Convolutions Algorithms Lecture
Nowadays, digital images and video are everywhere. Image Processing revolutionizes very many domains, notably:
-Digital Media (video/image/movie) Content Production and Broadcasting, Social Media Analytics,
-Medical/Biological/Dental Imaging and Diagnosis,
-Big Visual Data Analytics,
-Internet and Communications (media broadcasting, streaming).
-Scientific Imaging of any sort, e.g., Remote Sensing, Environment Sensing.
Photoshop and many other image processing tools are ubiquitous.
Furthermore, Image Processing is typically the first step that enables diverse applications, in unison with Computer Vision and Machine Learning:
-Autonomous Systems (cars, drones, vessels) Perception,
-Robotics Perception and Control,
-Intelligent Human-Machine Interaction,
-Anthropocentric (human-centered)Computing,
-Smart Cities/Buildings and Assisted living.
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.
Therefore, 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^4) and O(N^6) respectively their fast execution is a must.
This lecture will overview 2D linear and cyclic convolution. Then it will present their fast execution through FFTs, resulting in algorithms having computational complexity of the order O(N^2log2N). Optimal Winograd 2D convolution algorithms will be presented having theoretically minimal number of computations. Parallel block-based 2D convolution/calculation methods will be overviewed. The use of 2D convolutions in Convolutional Neural Networks will be presented.