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

 

[gabor]

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

 

[JustJohn]

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

 

[JustJohn]

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

 

[JustJohn]

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

 

[JustJohn]

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

 

Hi John,
Could you please let me know how many comparators you need to do one
pixel for 1 clock design?

In the second picture, there are 13 comparators.

Weng

 

Hi John,
I am confused if your are the real author of the paper in Xilinx
website paper: JOHN L. SMITH.

I am not familiar with American people's names. I thought your were
Just John before.

If you are, please accept my respect for you.

That is a really excellent paper and design.

Weng

 

[JustJohn]

Weng writes:

I am confused if your are the real author of the paper in Xilinx
website paper: JOHN L. SMITH.
I am not familiar with American people's names. I thought your were
Just John before.

Yes, I am the John L. Smith who wrote that paper. I use JustJohn here
because there are many John Smiths, and there are several notable other
Johns who regularly contribute to comp.arch.fpga, e.g. the estimable
John_H(andwork), JJ (JohnJakson), John Larkin, and a host of others. I
also use JustJohn to remind me to keep my ego in check.

That is a really excellent paper and design.

Thank you again. Flattery will get you lots of places. It won't get
your homework done, or a patentable circuit...

You see Weng, I'm confused. The questions you ask demonstrate complete
unfamiliarity with the field, indicating you are either a student just
starting out, or perhaps dabbling in something new for fun. But past
posts (I just checked) indicate you want to patent something. If that
is the case, you will have to work to get some knowledge in the field
you want the patent in.

In the second picture, there are 13 comparators.

Yes, and I will be truly impressed if you have something better (or
better than Khaled's circuit), and would love to see it. I don't know
if it would be worth patenting though, probably more trouble than it's
worth, and very difficult to enforce. Still, it amazes me what does get
patented.

Weng, you've been very polite throughout this interchange, and if
English is not your first language, you write it very well. But your
questions are too simple, and you need to start answering them
(researching) for yourself.

Regards,
John

 

Hi John,
Thank you for your response.

Yes, I did get something new about median filter. I am making living as
a senior principle FPGA designer in a small company to do memory
controller system and independently have designed several market
successful products for my company.

My hobby at home is to attack complex algorithms in computer science
and electronics that either is currently implemented by software or the
current algorithms in circuits that can be further improved, updated to
cover more ranges, or get faster speed with less resources.

I have a math background. In math, as you know, there are always many
theorems that expand some previous narrower theorem. I am trying to do
the same things for electronic circuits. One of targets is your paper.
In the paper you really did an excellent job and I learned from the
technique you have used. After reading your paper on June 13, 2005, I
realized that I could and should do better than your paper in a
different circuit. I finished it 2 weeks ago.

I have read several papers after reading your paper and learn there is
a Rank K filter that is similar to median filter and is the Kth largest
data to replace the center data. Further more, there is a Stack filter
further pushing the median filter method far from normal.

In my opinion, developing a new algorithm for electronic algorithm
doesn't need more background knowledge than printing and reading
several papers describing existing best algorithms about the subjects
you are interested. The reason is I will never use it and if I can
develop an algorithm or a circuit, or a method, they can be used by
others. If there is a chance, file a patent. If not, just publish it
for fun.

Due to being not in image industry circle, what I have about median
filter is what I just read from your paper and other several papers. I
will certainly read Khaled Benkrid's paper.

I have been writing some patents now, but not for median filter. What I
have done with median filter is certainly a material for patent. I will
leave the decision whether or not to file a patent 1 year later.
Because I am now occupied by other urgent projects at home.

I appreciate your several responses very much. For example, you gave me
3 examples on how to handle edge pixels that are to be included in my
algorithm without much logic.

Your paper excellence is in the following points:
1. Paper is very concise;
2. Key circuit element is shown very clear;
3. Algorithm is very cleaver.

Thank you.

Weng

If you like, send me email to wtxwtx at gmail dot com by deleting space
char.

 

[Gabor]

Here's an article I've used to generate efficient 3 x 3 median filters:

http://www.cg.tuwien.ac.at/research/publications/1994/Kopp-1994-EMF/TR-186-2-94-18Paper.pdf

(Manfred Kopp and Werner Purgathofer, Technical University of Vienna,
1994)

wtxwtx@gmail.com wrote:

Hi John,
Thank you for your response.

Yes, I did get something new about median filter. I am making living as
a senior principle FPGA designer in a small company to do memory
controller system and independently have designed several market
successful products for my company.

My hobby at home is to attack complex algorithms in computer science
and electronics that either is currently implemented by software or the
current algorithms in circuits that can be further improved, updated to
cover more ranges, or get faster speed with less resources.

I have a math background. In math, as you know, there are always many
theorems that expand some previous narrower theorem. I am trying to do
the same things for electronic circuits. One of targets is your paper.
In the paper you really did an excellent job and I learned from the
technique you have used. After reading your paper on June 13, 2005, I
realized that I could and should do better than your paper in a
different circuit. I finished it 2 weeks ago.

I have read several papers after reading your paper and learn there is
a Rank K filter that is similar to median filter and is the Kth largest
data to replace the center data. Further more, there is a Stack filter
further pushing the median filter method far from normal.

In my opinion, developing a new algorithm for electronic algorithm
doesn't need more background knowledge than printing and reading
several papers describing existing best algorithms about the subjects
you are interested. The reason is I will never use it and if I can
develop an algorithm or a circuit, or a method, they can be used by
others. If there is a chance, file a patent. If not, just publish it
for fun.

Due to being not in image industry circle, what I have about median
filter is what I just read from your paper and other several papers. I
will certainly read Khaled Benkrid's paper.

I have been writing some patents now, but not for median filter. What I
have done with median filter is certainly a material for patent. I will
leave the decision whether or not to file a patent 1 year later.
Because I am now occupied by other urgent projects at home.

I appreciate your several responses very much. For example, you gave me
3 examples on how to handle edge pixels that are to be included in my
algorithm without much logic.

Your paper excellence is in the following points:
1. Paper is very concise;
2. Key circuit element is shown very clear;
3. Algorithm is very cleaver.

Thank you.

Weng

If you like, send me email to wtxwtx at gmail dot com by deleting space
char.

 

Hi Gabor,
Thank you for your response. A good paper. I printed it out.

Weng