113.113. Convolution Operation

Convolution Operation (2D)

Implement a 2D convolution operation on a given input matrix using a sliding kernel (filter). Convolution is the fundamental operation in Convolutional Neural Networks (CNNs), used to extract features like edges, textures, and patterns from images by applying learned filters across the input.

The 2D convolution formula is:

output_shape = (input_h - filter_h + 1, input_w - filter_w + 1)

for each position (i, j) in the output:

output[i][j] = sum(input[i:i+filter_h, j:j+filter_w] * filter)

where * denotes element-wise multiplication

Your function convolution_operation(input_array, filter_array) should slide the filter over the input (valid convolution with no padding), compute the element-wise product at each position, and sum the results to produce each output element.

Example:

Input: input_array = [[1, 2, 3], filter = [[1, 0],

[4, 5, 6], [0, 1]]

[7, 8, 9]]

Position (0,0): [[1,2],[4,5]] * [[1,0],[0,1]] = 1*1 + 2*0 + 4*0 + 5*1 = 6

Position (0,1): [[2,3],[5,6]] * [[1,0],[0,1]] = 2*1 + 3*0 + 5*0 + 6*1 = 8

Position (1,0): [[4,5],[7,8]] * [[1,0],[0,1]] = 4*1 + 5*0 + 7*0 + 8*1 = 12

Position (1,1): [[5,6],[8,9]] * [[1,0],[0,1]] = 5*1 + 6*0 + 8*0 + 9*1 = 14

Output: [[6, 8], [12, 14]]

In a CNN, the filter weights are learned during training. The convolution operation preserves the spatial relationship between pixels, making it highly effective for image recognition tasks. Different filters detect different features (e.g., horizontal edges, vertical edges, corners).

Constraints: