Sparse Valid Conv2D From Scratch
NVIDIA● MediumFULLTIMEOAProblem statement
Implement two-dimensional valid cross-correlation from scratch over one integer image and one integer kernel. At each output position [row][col], sum image[row + dr][col + dc] * kernel[dr][dc] over every kernel cell. Return all valid output positions in a rectangular matrix.
Use the common ML convention: do not reverse the kernel. There is one channel, unit stride, no padding and no dilation. The output has imageRows - kernelRows + 1 rows and imageCols - kernelCols + 1 columns. An optimized implementation can precompute nonzero kernel taps and avoid copying every image patch.
Function
conv2D(image: int[][], kernel: int[][]) → int[][]Examples
Example 1
image = [[1,2,3],[4,5,6],[7,8,9]]kernel = [[1,0],[0,-1]]return = [[-4,-4],[-4,-4]]The asymmetric diagonal weights distinguish kernel orientation.
Example 2
image = [[2,-1],[-3,4]]kernel = [[2]]return = [[4,-2],[-6,8]]A one-cell filter scales every pixel, preserving the matrix shape.
Example 3
image = [[1,2,3],[4,5,6]]kernel = [[0,0,0],[0,0,0]]return = [[0]]A full-size all-zero filter produces one zero.
Constraints
- The image is rectangular, with 1 to 30 rows and 1 to 30 columns.
- The rectangular kernel has at least one row and column, and fits within the image in both dimensions.
- Each image and kernel entry is an integer in
[-100,100]. - Every result fits in a signed 32-bit integer.