Hide

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:

\includegraphics[width=1.0\textwidth ]{Vd-Orig.png}

\[ \Rightarrow \frac{1}{9} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \Rightarrow \]

\includegraphics[width=1.0\textwidth ]{Vd-Blur2.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

Please log in to submit a solution to this problem

Log in