Maximum 2D Filter in C++

Hi all,

I am looking for an efficient implementation of the 2D maximum filter in 
C++. I tried to write one using the Blitz library, but my code's speed 
is far slower than the matlab code. I am new to the field and I'm not 
sure if it is my algorithm that is suboptimal, or if matlab has special 
optimization I can't achieve. In any case I am looking for either a C++ 
code for maximum filtering, or advice on algorithm and implementation.
My image is 512 x 512 and the filter is 11 x 11.

Thanks,
RS

RS wrote:
> I am looking for an efficient implementation of the 2D maximum filter in
> C++.
> [...]
> My image is 512 x 512 and the filter is 11 x 11.

How are you currently doing it? Are you actually trying to find the
maximum over an 11x11 area for each pixel? This would require 121
comparisons for each pixel. Note that a comparison is actually an
expensive operation compared to an addition: A sequence of additions
can easily be pipelined by the CPU whereas comparisons require a change
of the control flow which is not as easily pipelined.

Here are some ideas:

The maximum operation is a separable operation. That is, if you wish to
find the maximum over a set of pixels this is the same as splitting the
set into disjoint subsets, then finding the maximum over each subset
and then finding the maximum over the maxima.

In other words: What you can do is compute an intermediate image as
follows: Go over the image row-wise and find the maxima over 11
consecutive pixels in a row. Then go over the intermediate image
column-wise and find the maxima over 11 consecutive pixels in a column.
This results in only 22 comparisons per pixel.

Note that you do not need to do a full maximum search at each pixel. If
you remember the position of the last maximum found you only need to
update the maximum if either the current pixel is above the maximum or
if the position is more than 11 pixels away.

Hope this helps,

Marcus

Speedy wrote:
> RS wrote:
>> I am looking for an efficient implementation of the 2D maximum filter in
>> C++.
>> [...]
>> My image is 512 x 512 and the filter is 11 x 11.
> 
> How are you currently doing it? Are you actually trying to find the
> maximum over an 11x11 area for each pixel? This would require 121
> comparisons for each pixel. Note that a comparison is actually an
> expensive operation compared to an addition: A sequence of additions
> can easily be pipelined by the CPU whereas comparisons require a change
> of the control flow which is not as easily pipelined.
> 


Thanks for your response. I am actually using the max (of a matrix) 
function of the Blitz library. I am pretty sure they are efficient in 
that. But I'll try to do that manually.

Thanks again,
RS

"RS" <rsina_no.ssppaamm@comcast.net> wrote in message 
news:1_CdnY3VXeAs0qXYnZ2dnUVZ_qGdnZ2d@comcast.com...
> I am looking for an efficient implementation of the 2D maximum filter in 
> C++. I tried to write one using the Blitz library, but my code's speed is 
> far slower than the matlab code.

If you are in the Windows environment ...

How are you getting the pixel to start with? You have to load the image  (I 
assume a bitmap file format) and then get at each pixel.

You could use the GetPixel API call, but this is NOTORIOUSLY s-l-o-w, whihc 
perhaps you did not realize. The fast way (any environment) is to get a 
pointer to the start of the image data (after the image header), and 
increment the pointer along each line.

-- 
regards,
Stewart DIBBS
========================================
Image Acquisition and Advanced Image Processing
PiXCL 6.1 is very affordable and available now !
www.pixcl.com   Gatineau, Quebec, CANADA
========================================