Implement efficient separable convolution using the separability property.
A 2D filter K is separable if K=hvT (outer product of two 1D filters).
Computational advantage:
Direct 2D convolution: O(N2⋅k2) for k×k kernel
Separable: O(N2⋅2k) - much faster!
Algorithm:
Check if kernel is separable (rank-1 matrix)
If separable, extract h and v vectors
Convolve image with h horizontally
Convolve result with v vertically
Output: return {'result': ..., 'is_separable': ...} where result has the same size as the image (pixels outside the image are treated as 0), with every value rounded to 4 decimal places. Treat the kernel as separable when its second singular value is negligible (<10−10) relative to its first.
Gaussian, box, and Sobel filters are all separable!
Inputs:image is a 5×5 grayscale grid of zeros with a single 1 at the centre (row 2, column 2) — an impulse. kernel is a 3×3 grid of weights.
Separability: every row of the kernel is a multiple of [1,2,1] (rows are 1×, 2×, 1× it), so the matrix has rank 1 and factors as K=hvT with h=v=[1,2,1]. Hence is_separable is True.
Horizontal pass: filtering each row with [1,2,1] leaves every row zero except the middle one, which becomes [0,1,2,1,0].
Vertical pass: filtering each column with [1,2,1] spreads column 2's value 2 into 2,4,2 down rows 1–3, and columns 1 and 3 into 1,2,1.
Output: the kernel itself, centred on the impulse, with zeros on the border — pixels outside the image count as 0. Notice this equals direct 2D convolution, but costs 2k=6 multiplies per pixel instead of k2=9.
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
A 2D filter is separable when it can be decomposed into the outer product of two 1D filters: K=\mathbf{h}\mathbf{v}T, where h is a horizontal filter and v is a vertical filter. Mathematically, this means every element in the 2D kernel can be expressed as K[i,j]=h[i]⋅v[j]. This property is fundamental to linear algebra—a matrix has rank 1 if and only if it can be expressed as an outer product of two vectors.
The computational advantage is substantial. Instead of applying a k×k kernel directly to an N×N image (requiring O(N2⋅k2) operations), you can apply two sequential 1D convolutions: first horizontally with h, then vertically with v, totaling O(N2⋅2k) operations. For large kernels, this represents a dramatic speedup. Many common filters used in image processing—Gaussian blur, box filters, and Sobel edge detection operators—are naturally separable, making this optimization widely applicable in practice.
Rank-1 Matrix Detection
To determine if a kernel is separable, you must check if it has rank 1. A matrix has rank 1 if and only if all rows are scalar multiples of each other (or equivalently, all columns are scalar multiples of each other). Computationally, you can use Singular Value Decomposition (SVD): if only one singular value is non-zero (within numerical tolerance), the matrix is rank 1. Alternatively, you can check if the determinant of any 2×2 submatrix is zero, or use row reduction to verify that only one row is linearly independent.
Algorithm/Approach
The general solution follows this pattern:
Rank verification: Determine if the kernel is separable by checking its rank
Vector extraction: If separable, decompose the kernel into h and v
Sequential convolution: Apply 1D convolutions in sequence rather than 2D
Optimization: Leverage the separability to reduce computation
The key insight is that matrix decomposition (typically via SVD) gives you the optimal 1D filters directly. For a rank-1 matrix, K=UΣVT simplifies to K=(\mathbf{u}\sqrt{\sigma})(\sqrt{\sigma}\mathbf{v}T), where u and v are the first columns of U and V, and σ is the single non-zero singular value.
Step-by-Step Strategy
Step 1: Validate Separability
Compute the SVD of the kernel matrix
Count non-zero singular values (accounting for numerical precision)
If exactly one singular value is significantly non-zero, the kernel is separable
Step 2: Extract 1D Filters
From SVD: h=U[:,0]⋅σ0 and v=V[:,0]⋅σ0
Alternatively, normalize: h=U[:,0] and v=V[:,0]⋅σ0
Verify reconstruction: h\mathbf{v}T≈K
Step 3: Apply Sequential Convolution
Convolve the image with h along the horizontal axis (each row)
Convolve the intermediate result with v along the vertical axis (each column)
This produces the same result as direct 2D convolution but more efficiently
Step 4: Handle Edge Cases
Check for numerical precision when determining rank (use a threshold like 10−10)
Ensure output dimensions match expected convolution output
Common Pitfalls
Rank tolerance: Using exact zero to check for rank-1 fails due to floating-point errors. Always use a relative or absolute threshold when comparing singular values.
Normalization ambiguity: The decomposition K=\mathbf{h}\mathbf{v}T is not unique—you can scale h by α and v by 1/α. Ensure your verification accounts for this.
Convolution order: The order matters for non-commutative operations. Verify that horizontal-then-vertical produces the same result as direct 2D convolution.
Boundary handling: 1D convolutions at image edges may behave differently than 2D convolutions depending on padding strategy. Use consistent padding (zero-padding, reflection, etc.).
Numerical stability: For ill-conditioned kernels, SVD may introduce numerical errors. Check reconstruction error explicitly.
Time & Space Complexity
Aspect
Direct 2D
Separable
Time Complexity
O(N² · k²)
O(N² · 2k)
Space (kernel)
O(k²)
O(2k)
Space (intermediate)
O(N²)
O(N²) for intermediate result
SVD decomposition
—
O(min(k², k³)) one-time cost
For a 512×512 image with a 7×7 kernel: direct convolution requires ~12.8M operations, while separable requires only ~3.6M operations—a 3.5× speedup. The SVD decomposition cost is negligible since it's computed once on the small kernel matrix.