Convolution Kernel Restoration

Solution to the problem from the Research Institute for System Studies of the Russian Academy of Sciences, supported by the Russian Neural Network Association.

Problem Description

Given a grayscale image and the result of a convolution operation with an unknown kernel. The task is to determine the convolution kernel weights.

Constraints

• Convolution window size is known: h × w (odd numbers)
• Convolution was performed in mode='same' - zero padding is added to the image with width (w - 1)/2 on each side and (h - 1)/2 on top/bottom
• Pixel values in the original image and convolution kernel are integers
• The convolution result matches the size of the original image

Implementation Features

No external libraries - uses only built-in Python capabilities

• Custom implementation of Gaussian elimination for solving linear systems
• Custom matrix rank computation for selecting linearly independent equations

Requirements

• Python 3.6+
• No external dependencies

Usage

py main.py

Input Format

1. First line - two numbers m, n - image dimensions.
2. Next m lines with n comma-separated numbers - original image matrix A.
3. Then two odd numbers h, w - convolution kernel dimensions.
4. After that m lines with n comma-separated numbers - convolution result B.

All numbers are integers.
Dimensions satisfy: 3 ≤ m, n ≤ 1000, 3 ≤ h, w ≤ 11, h ≤ m, w ≤ n.

Output Format

h lines, each with w comma-separated integers - convolution kernel weights.

Examples

Example 1

Input:

3,5
9,0,46,57,49
19,23,41,23,88
47,71,92,8,86
3,3
256,1096,1586,2501,1300
1135,1014,1028,2221,1341
1465,2149,1830,936,1860

Output:

6,1,2
15,11,11
-15,12,-10

Example 2

Input:

6,4
68,74,98,40
82,13,45,54
83,51,88,89
91,71,7,40
31,1,96,82
22,97,63,17
3,3
571,757,-167,-745
1203,3152,2777,994
1004,2371,1858,115
1692,2417,2833,1366
1646,3077,2159,-546
1448,2124,1274,1595

Output:

3,-2,-1
14,-5,-4
14,6,15

Algorithm

1. For each position (i,j) in the output matrix, a linear equation is formed based on the h×w window of the input matrix
2. Linearly independent equations are selected (matrix rank check using Gaussian elimination)
3. The system of linear equations is solved using Gaussian elimination with partial pivoting
4. The result is rounded to integers and reshaped into an h×w convolution kernel
5. A 180° rotation (flip along both axes) is applied to obtain the final kernel

Code Structure

• read_ints_csv() - reads comma-separated numbers from a line
• matrix_rank() - computes matrix rank using Gaussian elimination
• solve_linear_system() - solves linear system using Gaussian elimination
• flatten() - converts 2D list to 1D
• reshape() - converts 1D list to 2D matrix
• reverse_2d() - rotates matrix by 180°
• patch_row() - extracts convolution window with padding