Mean value filter

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.

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."

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.

Hi Gabor, Thank you for your response.

1. 'Mirror' operation is interesting.

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

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

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

Weng

Weng

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

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

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.

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

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

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

(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.

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).

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

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.

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.

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.

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

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

1994)

snipped-for-privacy@gmail.com wrote:

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

Weng