Decompose 2D filter kernel into 1D kernels

Question

I'm trying to separate a 2D matrix into two vectors such that their outer products equal the original matrix.

Using SVD:

import cv2
import numpy as np

def createDoG(sigma, sigmaRatio=0.5):
    size = int(np.ceil(sigma*3))*2+1
    kernel1_2D = np.outer(cv2.getGaussianKernel(size, sigma), cv2.getGaussianKernel(size, sigma))
    kernel2_2D = np.outer(cv2.getGaussianKernel(size, sigma*sigmaRatio), cv2.getGaussianKernel(size, sigma*sigmaRatio))
    return kernel1_2D - kernel2_2D

def decompose(kernel):
    U, S, V = np.linalg.svd(kernel)
    h1 = U[:,0] * np.sqrt(S[0])
    h2 = V[0] * np.sqrt(S[0])
    return h1,h2

kernel_DoG = createDoG(1)
h1,h2 = decompose(kernel_DoG)
print("kernel_DoG == h1*h2':", np.isclose(kernel_DoG, np.outer(h1, h2)).all()) #prints False

Why can't I decompose this matrix? What class of matrices are separable(into two vectors)?

The application is for decomposing a kernel so I can apply two-pass 1D convolution for speed-up. I also tried this answer in python with no luck.

Answer 1

Why can't I decompose this matrix?

Because it is not separable. The DoG, and many other kernels, are not separable.

What class of matrices are separable (into two vectors)?

The kernels where all rows are scaled versions of the other rows are separable. That is, each row i must be of the form

r[i][j] = a[i] * b[j]

where b is the “model row”, and a[i] is the scaling for each row. This looks kind of obvious, since the multiplication above is what you get when you convolve the column kernel a with the row kernel b (and is the outer product that the code in the question uses).

To know if a 2D kernel is separable, compute its rank: the rank must be 1. This indicates that all rows are scaled versions of each other.

For reference, here are two different MATLAB solutions to the kernel decomposition in an arbitrary number of dimensions:

• my solution, using SVD
• DJ Kroon’s solution, using least squares