A higher resolution is required to access the IDE
- 196
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
Statement
Goal
Convolution is a method for extracting features from an input image which can be used for training a Deep Neural Network to classify input image. It produces an output matrix where each element is a weighted sum of neighbouring input elements using a kernel (weight matrix).Given an input image of size r × c pixels (each pixel represented by an integer) and a kernel of size m × n, print the (r-m+1) × (c-n+1) output pixels after the convolution.
To calculate the output pixel values, place the top left corner of kernel of size m × n on the input image matrix starting from the top left corner and then shift it one step right as long as it fits in the input image matrix. Then start again on the next row down.
At each location, calculate the sum of the weights multiplied by the pixel values at the overlapped cells.
Example how convolution works
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
w11 w12
w21 w22
In this case we have 9 possible placements of the kernel matrix.
Top left corner at
Weighted Sum = a11 * w11 + a12 * w12 + a21 * w21 + a22 * w22
Top left corner at
Weighted Sum = a12 * w11 + a13 * w12 + a22 * w21 + a23 * w22
Top left corner at
Weighted Sum = a13 * w11 + a14 * w12 + a23 * w21 + a24 * w22
Top left corner at
Weighted Sum = a21 * w11 + a22 * w12 + a31 * w21 + a32 * w22
Top left corner at
Weighted Sum = a22 * w11 + a23 * w12 + a32 * w21 + a33 * w22
So on...
For an animated visualization please refer to this link: tinyurl.com/nk0vnyel
Resources for more information:
https://d2l.ai/chapter_convolutional-neural-networks/conv-layer.html
https://developers.google.com/machine-learning/practica/image-classification/convolutional-neural-networks
Input
Line 1: The height (r) and width (c) of input image matrix separated by space.
Next r lines: c pixel values separated by spaces.
Line r+2: The height (m) and width (n) of the kernel matrix separated by space.
Next m lines: n weights separated by spaces.
Next r lines: c pixel values separated by spaces.
Line r+2: The height (m) and width (n) of the kernel matrix separated by space.
Next m lines: n weights separated by spaces.
Output
Print the output image matrix after the convolution.
Constraints
Kernel matrix is a square matrix.
m ≤ r and n ≤ c
m ≤ r and n ≤ c
Example
Input
3 3 100 200 100 200 100 200 50 100 50 2 2 -1 1 1 -1
Output
200 -200 -150 150
A higher resolution is required to access the IDE