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
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
you can also split the matrix into symmetric and skew parts and separate each part, which can be effective for larger 2d convolutions.
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