I just run over the a strange matlab phenomenon and I am quite
interested if this is a bug or a feature :)
so, when filtering an image with some 2D kernel (eg Gaussian) the Matlab
"imfilter" function tries to separate the 2D kernel into two 1D kernels
for speedup. But this is only done if the kernel AND the image are
two-dimensional. This actually means that when filtering and RGB (3
layered) image with a 2D kernel then no kernel separation is applied.
when filtering a grayscale image only, separation is applied.
Is there a reason or is this just a bug (in fact if eg using a 30x30
kernel, the separation yield a speedup factor of about 10).
roli
ps: if important, i am using matlab 7.2.0.232 (R2006a)
Bug or feature? Depends on your perspective, I guess.
Ship an unoptimized function foobar in release N. (For example, the
original imfilter did not do automatic separability determination at all.)
Optimize foobar for some cases in a later release.
Now, is the fact that foobar can be optimized more than it is now a bug?
From my point of view, I'd prefer to call it an enhancement request. :-)
Anyway, thanks for pointing this out. It fits in with other performance
improvements that we want to make to imfilter, some of which have been
discussed recently in this newsgroup.
--
Steve Eddins
http://blogs.mathworks.com/steve
> Anyway, thanks for pointing this out. It fits in with other performance
> improvements that we want to make to imfilter, some of which have been
> discussed recently in this newsgroup.
ok, thanks for your answer, i am satisfied
regards, roli
By the way, upgrade to R2006b. I just lost half a day playing around
with the debugger examining my variables in MATLAB only to find out I
was wasting my time on a bug. The bug is that a uint8 variable
displays as -1 in the Workspace if it's really 255. Try this and
you'll see what I mean
wrongDisplay = uint8(255)
It will show in the command line as 255 but in the Workspace as -1.
However if you double-click on it in the Workspace it will bring up the
ArrayEditor and correctly show it there as 255. And we all know how
often we deal with 255 when dealing with images. This bug was fixed in
R2006b.
Regards,
ImageAnalyst
============================================================
Yes, that's right. Filtering an M-by-N image with a P-by-Q kernel
requires about MNPQ multiplies and adds, assuming we don't use FFTs. If
you filter first with a P-by-1 kernel and then with a 1-by-Q kernel,
that's about MNP + MNQ mults and adds, or MN(P+Q).
If the kernel is 7-by-7, that's 3.5x fewer operations.
>Does the number of multiplications and additions come down if done with
>two 1D kernels rather than doing it in one shot using 2D convolution?
>I am just wondering if that might be the reason.
>Please let me know.
Well, have you tried to calculate this yourself? It should take only a
few minutes.
For a simplified example, assume that the image and filter kernel are
square (generalizing this to rectangles is pretty obvious). Suppose the
image is NxN pixels and the filter kernel is MxM pixels.
Doing a single convolution operation at one image pixel location
requires MxM multiply-add operation. So processing the whole image
costs N*N * M*M multiply-adds.
If the 2D filter kernel can be decomposed into the product of two 1D
filters, they will be 1xM and Mx1. Convolving one image pixel with one
filter costs M multiply-adds, so filtering the entire image with one
filter costs N*N * M of these operations. But there are two filters
which need to be applied in succession, so the total cost is
N*N * M*2 multiply-adds.
Now compare the two total costs. The two 1D filters cost 2/M times as
much as the 2D filter.
This is a no advantage for a 2x2 kernel, a small advantage for a 3x3 or
4x4 kernel, and a really big speedup for a 128x128 kernel.
Unfortunately, most larger 2D filters used in image processing are radially
symmetric, and most radially symmetric filters are not separable, so you
can't use this optimization on them. But 2D Gaussians *are* separable
(into two 1D Gaussians) and radially symmetric, so there's an advantage
to using a Gaussian filter when you can.
Dave
With Regards,
Abhishek S
If you have MATLAB, take a look at the code for the filter function. It
uses the singular value decomposition. There's similar code in the
imfilter function, which is in the Image Processing Toolbox.