PIXELBANKv8.2.1
Menu
Sign In

Separable Filter Optimization

HardFiltering

Implement efficient separable convolution using the separability property.

A 2D filter K is separable if K=hvTK = \mathbf{h} \mathbf{v}^T (outer product of two 1D filters).

Computational advantage:

  • Direct 2D convolution: O(N2⋅k2)O(N^2 \cdot k^2) for k×k kernel
  • Separable: O(N2⋅2k)O(N^2 \cdot 2k) - much faster!

Algorithm:

  1. Check if kernel is separable (rank-1 matrix)
  2. If separable, extract h and v vectors
  3. Convolve image with h horizontally
  4. Convolve result with v vertically

Gaussian, box, and Sobel filters are all separable!

Example:

Input:
image = 5×5 array
kernel = [[1,2,1],[2,4,2],[1,2,1]]  # Separable (Gaussian-like)
Output:
{'result': convolved_image, 'is_separable': True}
Reasoning:

Check separability via SVD: kernel = [[1,2,1],[2,4,2],[1,2,1]] SVD: Only one non-zero singular value → rank 1 → separable!

Extract: h = [1,2,1], v = [1,2,1]

Apply h horizontally, then v vertically. Result same as direct 2D convolution but faster.

Constraints:

  • image: 2D grayscale array
  • kernel: 2D convolution kernel
  • Return: Dict with 'result' and 'is_separable' boolean
  • If separable, use optimized method; otherwise direct convolution
Editor

Test Results

0/0
Run code to see test results.