I'm wondering if the 2D laplacian kernel
0 1 0
1 -4 1
0 1 0
is also a separable kernel. How can I find that out?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ If it were $\begin{bmatrix}a & b & c\end{bmatrix} * \begin{bmatrix}d \\ e \\ f\end{bmatrix}$, then the upper-left corner would be $ad = 0$, so either $a$ or $d$ would have to be zero, so... $\endgroup$– user856Apr 15, 2012 at 19:18
-
$\begingroup$ you're right. Post it as an answer and I'll accept it. Although I was searching for a "standard way" to verify if the kernel is separable or not $\endgroup$– paulAlApr 15, 2012 at 19:20
-
$\begingroup$ I've posted an answer about a general way to do this for arbitrary kernels, though I don't know if it's "standard" in any sense. $\endgroup$– user856Apr 15, 2012 at 19:39
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
A kernel $h$ is separable if and only if all its rows are multiples of each other. Then you can pick one, call it $f$, make a column of the multiplicative factors, call it $g$, and find that $h = f*g$.
You can't do this for the 2D Laplacian kernel, because $[0,1,0]$ is not a multiple of $[1,-4,1]$.
$\begingroup$
$\endgroup$
You cannot separate this kernel and make 2 consecutive convolutions to get the same result. But you can make 2nd derivative convolutions (horizontal and vertical) with [1 -2 1] and [1; -2; 1] kernels and then sum their results.
In case of separable convolution you use associative property of convolution, in case of sum of two convolutions you use distributive property.
I think sum of convolutions is another way to effectively compute convolution kernel.
$\begingroup$
$\endgroup$
In general, you need to verify the rank of the kernel (considered as a matrix). If rank is one, than (by SVD decomposition) you can find two vectors whose outer product is the kernel. In this case, the rank of the laplacian is 2, hence it is not separable.
$\begingroup$
$\endgroup$
The given definitions there, are somewhat wrong. That's only proof it can't be subdivided into two 1D matrixes.
0 -1 -1 -1 0
-1 3 2 3 -1
-1 2 1 2 -1
-1 3 2 3 -1
0 -1 -1 -1 0
Obviously fits the definition of Rahul's iff definition and would not be separable. However it's properly the combination of:
1, 1, 1
1, 1, 1
1, 1, 1
and
0 -1 0
-1 5 -1
0 -1 0
So that matrix could actually be done in:
[1,1,1],
[1,
1,
1,]
[ 0 -1 0
-1 5 -1
0 -1 0 ]
15 operations rather than 25. Because it's separable, but doesn't meet the traditional definition. Though, the Laplace is still not.
