| Science Forum Index » Image Processing Forum » Determining if a kernel is seperable?... |
|
Page 1 of 1 |
|
| Author |
Message |
| fdm... |
 Posted: Wed Sep 16, 2009 3:14 am |
|
|
|
Guest
|
I am currently working with 2D image interpolation and is experimenting with
BSpline and gaussian kernels. I have read that if a kernel is seperable the
"inner" weights can be determined using the separability property of the
kernel:
x02 - - o12 - - o22
| | |
x01 - - o11 - - o21
| | |
x00 - - x10 - - x20
In this case:
o11 = x10*x01
o21 = x20*x01
o12 = x10*x02
o22 = x20*x02
But how does one determine of a kernel is separable? |
|
|
| Back to top |
|
|
|
| Nicolas Bonneel... |
| Posted: Wed Sep 16, 2009 3:39 am |
|
|
|
Guest
|
fdm a écrit :
[quote:815d954f74]I am currently working with 2D image interpolation and is experimenting
with BSpline and gaussian kernels. I have read that if a kernel is
seperable the "inner" weights can be determined using the separability
property of the kernel:
x02 - - o12 - - o22
| | |
x01 - - o11 - - o21
| | |
x00 - - x10 - - x20
In this case:
o11 = x10*x01
o21 = x20*x01
o12 = x10*x02
o22 = x20*x02
But how does one determine of a kernel is separable?
[/quote:815d954f74]
A (symmetric) separable kernel is such that K = x*transpose(x), with x a
column vector. So, the space spanned by the matrix is generated by a
single vector. The matrix is thus rank 1.
I would guess than reciprocally, any rank 1 matrix represents a
separable kernel....
--
Nicolas Bonneel
http://www-sop.inria.fr/reves/Nicolas.Bonneel/ |
|
|
| Back to top |
|
|
|
| aruzinsky... |
| Posted: Wed Sep 16, 2009 5:28 am |
|
|
|
Guest
|
On Sep 16, 3:14 am, "fdm" <f... at (no spam) gk.com> wrote:
[quote:b00f8c4944]I am currently working with 2D image interpolation and is experimenting with
BSpline and gaussian kernels. I have read that if a kernel is seperable the
"inner" weights can be determined using the separability property of the
kernel:
x02 - - o12 - - o22
| | |
x01 - - o11 - - o21
| | |
x00 - - x10 - - x20
In this case:
o11 = x10*x01
o21 = x20*x01
o12 = x10*x02
o22 = x20*x02
But how does one determine of a kernel is separable?
[/quote:b00f8c4944]
As a practical matter, you want to include cases that are almost
separable so that you can approximate them with separable kernels. In
that case, you should use Singular Value Decomposition (SVD), A UDV. If only one element of the D matrix is nonzero, the matrix is
separable. If the absolute value of one element is much larger than
any of the others which are nonzero, it can be approximated by a
separable matrix. Also, some kernels can be approximated by the sum
of separable kernels using SVD. |
|
|
| Back to top |
|
|
|
| Martin Brown... |
| Posted: Wed Sep 16, 2009 6:45 am |
|
|
|
Guest
|
fdm wrote:
[quote:92dc3d3f38]I am currently working with 2D image interpolation and is experimenting
with BSpline and gaussian kernels. I have read that if a kernel is
seperable the "inner" weights can be determined using the separability
property of the kernel:
x02 - - o12 - - o22
| | |
x01 - - o11 - - o21
| | |
x00 - - x10 - - x20
In this case:
o11 = x10*x01
o21 = x20*x01
o12 = x10*x02
o22 = x20*x02
But how does one determine of a kernel is separable?
[/quote:92dc3d3f38]
For a kernel to be separable every column must be a linear multiple of
every other column, and the same rule applies for every row.
So if a kernel is separable you should be able to sum the rows and
columns to get a pair of vectors which when multiplied together give the
original kernel to within a normalising factor.
Regards,
Martin Brown |
|
|
| Back to top |
|
|
|
| Johann Blaser... |
| Posted: Wed Sep 16, 2009 11:28 am |
|
|
|
Guest
|
thats surely necessary, but not sufficient.
the sobel-kernel is clearly separable, but if i sum the derivative
direction i get zeros.
an easy way to separate a kernel by using a computer is doing a
lu-factorization. the first column of the l-matrix and the first
row of the u-matrix give the two 1d-kernels. by multiplying
the two 1d-kernels and comparing with the original matrix
separability can be checked.
Regards,
Johann
[quote:ed326fc780]But how does one determine of a kernel is separable?
For a kernel to be separable every column must be a linear multiple of
every other column, and the same rule applies for every row.
So if a kernel is separable you should be able to sum the rows and
columns to get a pair of vectors which when multiplied together give the
original kernel to within a normalising factor.
Regards,
Martin Brown[/quote:ed326fc780] |
|
|
| Back to top |
|
|
|
| Nicolas Bonneel... |
| Posted: Wed Sep 16, 2009 1:29 pm |
|
|
|
Guest
|
Johann Blaser a écrit :
[quote:6f035a03ca]thats surely necessary, but not sufficient.
the sobel-kernel is clearly separable, but if i sum the derivative
direction i get zeros.
an easy way to separate a kernel by using a computer is doing a
lu-factorization. the first column of the l-matrix and the first
row of the u-matrix give the two 1d-kernels. by multiplying
the two 1d-kernels and comparing with the original matrix
separability can be checked.
[/quote:6f035a03ca]
Isn't LU supposed to work only on full rank matrices ? Otherwise the
pivot is 0 at some point.. isn't it ? But you can check for the presence
of a 0 in the pivot, and if it happens after the computation of the 1st
row/column, then the matrix is rank 1 and thus separable.
Note that for symmetric matrices, Cholesky is at least 2 faster.
Cheers
--
Nicolas Bonneel
http://www-sop.inria.fr/reves/Nicolas.Bonneel/ |
|
|
| Back to top |
|
|
|
|
