Mean value filter

Hi,
1. I want to know how to deal with marginal data for mean value filter,

the pixels that cannot get full 9 neighboring pixels in general.

2. What is the best algorithm for mean value filter? Where is the
related paper?

3. what book is the best one describing under what conditions mean
value filter is useful? 

Thank you. 

Weng

wtxwtx@gmail.com wrote:
> Hi,
> 1. I want to know how to deal with marginal data for mean value filter,
>
> the pixels that cannot get full 9 neighboring pixels in general.
>

A common practice is to "mirror" pixels into the area surrounding the
actual image data.  Thus if you imagine extending your data array
by placing mirrors at the 4 edges you should see that the top (1st) row
would repeat to the row above it, but the row above that would contain
data from the second row etc.  Of course for a 3 x 3 operation (I
think you meant 8 neighboring pixels) you only need one extra row
or column.

> 2. What is the best algorithm for mean value filter? Where is the
> related paper?
>

A mean filter is just an average.  This looks just like a convolution
where
the coefficients are all the same.  This isn't particularly good as a
filter
so you might want to explore with other values.  Another filter often
used is the median filter which takes the median rather than the mean
of the 3 x 3 (or other size)  group of pixels.  This is often used to
remove
"speckles."

> 3. what book is the best one describing under what conditions mean
> value filter is useful?
>

There are a number of good resources for image processing.  "Video
Demystified" is one of my favorites.  Also for general algorithms I've
used "The Scientist and Engineer's Guide to Digital Signal Processing"
by Steven W Smith, published at one time by Analog Devices.

> Thank you. 
> 
> Weng

Hi Gabor,
Thank you for your response.

1. 'Mirror' operation is interesting.

2. I wrote wrong. The correct name should be median filter, not mean
filter.

3. I have the book, but didn't find the median filter item in it.

4. Do you have an algorithm that is very efficient?

Weng

Weng

wtxwtx@gmail.com wrote:
> Hi Gabor,
> Thank you for your response.
>
> 1. 'Mirror' operation is interesting.
>
> 2. I wrote wrong. The correct name should be median filter, not mean
> filter.
>
> 3. I have the book, but didn't find the median filter item in it.
>
> 4. Do you have an algorithm that is very efficient?
>
> Weng
>
> Weng

This is the most efficient way I could develop for true 3x3 Median

http://www.xilinx.com/xcell/xl23/xl23_16.pdf

5x5 follows same structure but is MUCH larger.

A 'pseudo' median can be done a bit cheaper by taking middle of each
three pixels, and then taking middle of those three...

You can use SRL16s for mirroring horizontally, need blockRAMs for
vertical.

John

Hi John,
I have read the paper and I think it is an excellent paper.

What I want to know is how many products and applications will use it
or have been using it?

Thank you.

Weng

>Weng wrote:
>I have read the paper and I think it is an excellent paper.

Thank you very much, I liked that one too. Nobody has yet shown me a
better way. I was stimulated to work on the median by an article of
Alan Paeth's in "Graphics Gems" (the original, volume 1). He presented
an algorithm that used 20 comparisons, and mentioned that the minimum
bound was 19. I e-mailed him and asked if he had the 19 comparison
graph, but never got a reply, had to work that one out myself. I later
saw (in Knuth's "Searching and Sorting", volume 3 of "The Art of
Computer Programming" (this is a must have for people serious about
algorithms)) that exchange networks are typically diagrammed
differently. Just now you've inspired me to look through Knuth again,
and there is a formula on page 212 (formula (11)) that to implies the
median of 9 can be done with only 16 comparisons. Perhaps this leads to
a better solution, but I doubt it can be pipelined as nicely.

>What I want to know is how many products and applications will use it
>or have been using it?

Median filter is found in any decent image processing library. Beats me
how many others have used it. In 1996, FPGA was the only reasonable
implementation; now with 3+GHz processors common, it can be done
without FPGA, but still cheaper in FPGA I think (hmmm, I don't have a
feel for a DSP performance on this).

 If you want a book describes median applications, try any introductory
image processing textbook. On my shelf I have Pratt "Digital Image
Processing", and Gonzales/Wintz "Digital Image Processing".

Regards,
John (a median kind of guy)

Hi John,
Thank you for your advice to look at the Knuth's volume 3. I have the
book and will look at the paget 212.

Do you use 'mirror' algorithm to handle the side image pixels?

Does 'mirror' algorithm do the following way:
Original frame of image:
row0, row1, ... row 1023

Mirrored frame of image:
row1, row0, row1, ... row1023, row 1022

Same things are done with column.

Weng

>Weng wrote:
>Do you use 'mirror' algorithm to handle the side image pixels?

I don't currently have median in anything shipping at the moment, if I
did, product documentation would say.

>Mirrored frame of image:
>row1, row0, row1, ... row1023, row 1022

You've got it! Easy right?

Other common options are:
1) Duplication:
row0, row0, row1, ... row1023, row 1023

2) Extension:
(2*row0-row1), row0, row1, ... row1023, (2*row 1023-row1022)

Extra credit if you design it to handle all three.

umm Weng, this may be getting a bit far from comp.arch.fpga and
comp.lang.verilog,
You might try posting to sci.image.processing, they're nice folks over
there too.
Regards,
John

Hi John,
Thank you for your inputs.

I am wondering if there is a median value filter algorithm to deal with
1 pixel for 1 clock. That is, one pixel is in and one pixel is out in
real time. Is there any advantage if the algorithm is found?

The article and the algorithm you mentioned from Xilinx design paper
uses 3 clock to handle 1 pixel.

Weng

Weng wrote:
>I am wondering if there is a median value filter algorithm to deal with
>1 pixel for 1 clock. That is, one pixel is in and one pixel is out in
>real time.
(Sigh)
Yes there is. The graphs in the note are part of what is needed to do
this. What was not shown in the note was the required line delay
buffers (see below). The note was intended to demonstrate how the
XC4000 carry logic could be used for more than simply adding and
subtracting, carry logic is also handy for sorting networks.

>Is there any advantage if the algorithm is found?
Advantage compared to what? And the algorithm is not missing. Weng, as
you do more designs, you will see that there are always trade-offs.
There is another clever implementation (possibly better for ASIC) that
takes a bit-serial approach, and can be modified for arbitrary rank.
This was worked out by Khaled Benkrid in a back issue of SPIE 'Journal
of Electronic Imaging' (I don't have the issue handy, you'll have to
look that up yourself). Another median implementation might use a
single comparator, some RAM, and 19  clock cycles (or 13 with partial
result re-use).

>The article and the algorithm you mentioned from Xilinx design paper
>uses 3 clock to handle 1 pixel.

No, wrong, look again. The graphs only represent the flow of data, and
both graphs in the note may be implemented to produce one output pixel
per clock (remember, lots of trade-offs are possible). Preceding the
graphs, you need to implement two line delay buffers. Source video
feeds the input of your first line delay. The output of the first line
delay feeds the input of the second line delay. Source video and the
two line delay buffer outputs feed into the pipelined version of the
sorting network. Add muxes to handle special cases for first and last
line output. This is video, so here's a picture. I haven't included the
muxes, but this is what feeds the sorting network. I've labeled the
pixels to correspond to fig. 3 in the xcell note.

(use fixed width font):
Video In --+-------------------->P1, P4, P7
           |  +------------+
           +->| Line Delay |--+->P2, P5, P8
              +------------+  |
           +------------------+
           |  +------------+
           +->| Line Delay |---->P3, P6, P9
              +------------+

Now Weng, I can't give you everything, you are going to have to figure
out for yourself how to do the line delays, and where to put and how to
wire the muxes. The exercise will do you good.

Regards, and good luck,
John