20

What makes a convolution kernel separable? How would I be able to tell what those separable parts were in order to do two 1D convolutions instead of a 2D convolution>

Thanks

2 Answers 2

19

If the 2D filter kernel has a rank of 1 then it is separable. You can test this in e.g. Matlab or Octave:

octave-3.2.3:1>     sobel = [-1 0 1 ; -2 0 2 ; -1 0 1];
octave-3.2.3:2>     rank(sobel)
ans =  1
octave-3.2.3:3> 

See also: http://blogs.mathworks.com/steve/2006/11/28/separable-convolution-part-2/ - this covers using SVD (Singular Value Decomposition) to extract the two 1D kernels from a separable 2D kernel.

See also this question on DSP.stackexchange.com: Fast/efficient way to decompose separable integer 2D filter coefficients

1
  • 1
    SVD is the way to go here. Separable (ie. rank 1) kernels are very specific, and SVD allows you to approximate your kernel by a (small) sum of separable ones. May 4, 2011 at 21:19
4

you can also split the matrix into symmetric and skew parts and separate each part, which can be effective for larger 2d convolutions.

2
  • can you give example to clarify?
    – mrgloom
    Feb 11, 2015 at 15:52
  • 1
    If you can arrange your 2d matrix as the vector product x.y' +u.v' etc you can do a set of 1d convolutions of the rows and columns in stead of the 2d convolution, needing only 4N multiply/adds rather than N^2. If the u.v' has a smaller size then the reduction is greater. This usually assumes you have prior knowledge of the matrix's structure to ease the separation. It will also depend on your compute engine - a GPU may favour another structure. Feb 11, 2015 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.