Problem G
Image Processing
Image editing software like Photoshop provide many image effects like blur, sharpen, and edge detection. These effects are commonly implemented through a kernel, a matrix describing a certain image effect. The kernel is applied to an image through convolution: flipping both the rows and columns of the kernel and then multiplying locationally similar entries and summing.
For example, let’s say we have the $4 \times 4$ image $ \begin{bmatrix} a & b & c & d \\ e & f & g & h \\ i & j & k & l \\ m & n & o & p \end{bmatrix} $ and the $2 \times 2$ kernel $ \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}. $
After convolution, the resulting $3 \times 3$ image would be:
\[ \begin{bmatrix} 4a+3b+2e+1f & 4b+3c+2f+1g & 4c+3d+2g+1h \\ 4e+3f+2i+1j & 4f+3g+2j+1k & 4g+3h+2k+1l \\ 4i+3j+2m+1n & 4j+3k+2n+1o & 4k+3l+2o+1p \end{bmatrix} \]A real-world example of this is the blur effect:
|
|
\[ \Rightarrow \frac{1}{9} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \Rightarrow \] |
|
![\includegraphics[width=1.0\textwidth ]{Vd-Orig.png}](/problems/imageprocessing/file/statement/en/img-0001.png)
![\includegraphics[width=1.0\textwidth ]{Vd-Blur2.png}](/problems/imageprocessing/file/statement/en/img-0002.png)
Photo by Michael Plotke cc by-sa 3.0
Input
The first line of the input contains four integers, $H$, the height of the image, $W$, the width of the image, $N$, the height of the kernel, and $M$, the width of the kernel ($1 \leq H \leq 20$, $1 \leq W \leq 20$, $1 \leq N \leq H$, $1 \leq M \leq W$).
Each of the next $H$ lines contains $W$ integers, between $0$ and $100$ inclusive, representing the image.
Each of the next $N$ lines contains $M$ integers, between $0$ and $100$ inclusive, representing the kernel.
Output
Output the resulting image after convolution, consisting of $H-N+1$ lines, each with $W-M+1$ integers.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 2 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 |
26 36 46 66 76 86 106 116 126 |
