Algorithm Difference between Median_Filter And Median Inside Rank Filter?

[ashishdonvir]

In Median_Filter  Available as plugin filter if i select kernel size 9 it takes around 11 seconds to perform the filter for my grayscal image of size 1580x1050. On other hand if select  Median from the menu Process -> Filters -> Median and set Radius 9 it takes around 2.5 five seconds only to perform the filter for the same image. I know that Median is one of the rank filters of imageJ. What is the difference between Median in rank Filters And Median_Filter As Plugin? i Know that In Median_Filter it applies 9x9 median for each pixel. But i need     know about Median of rank filter. I tried to see code but could not understand exactly what it does. What is difference between kernel value and Radius Value? It would be great help if Any one explain the logic of Median of rank filter?  

[Michael Schmid]

Hi Ashish (did I guess the name correctly form your mail address?),

the built-in RankFilters are highly optimized:
- Multithreading, where each thread looks for the next line waiting for being processed (for the median, processing time depends on the image data).
- Using a rather small work array for the original pixels, so if nicely fits into the CPU cache.
- Padding the work array so that no checks for out-of-image coordinates are required when reading pixels values.
- When reading the pixels, they are already pre-sorted into two bins, for those larger and smaller than a guessed value.  The guess is the median of the previous pixel.  As the median changes only slowly from pixel to pixel, this leaves fewer pixel values (roughly half of the work).  If the median happens to be equal to the guess, it is found immediately because less than half of the pixels land in the lower and upper bin.

For Hoare's find algorithm, which is finally used to find the n-th value in a bin, you have to consult the literature (simply search the Web for it).
--

What is the median filter you compare with? Is it the one from
  ij-plugins.sourceforge.net/plugins/toolkit.html  ?

If you need an extremely fast version, faster than that in the RankFilters, and if you don't care so much about accuracy, you may also try the 'FastFilters' plugin.  It is also multithreaded, but it uses a rough approximation: the median is first calculated for lines, then for columns of the line medians.

--
'Kernel', 'structuring element' or 'support size' is the area where pixels are taken from.  So, in the RankFilters, the 'kernel' is a circle with radius r.  To see what it looks like, use Process>Filters>Show Circular Masks.

<strictly speaking, these three terms have slightly different meaning, but in practice I don't care - I am a user of image processing, not a theorist>


Hope this helps,

Michael
________________________________________________________________
On Oct 17, 2013, at 08:41, ashishdonvir wrote:

> In Median_Filter  Available as plugin filter if i select kernel size 9 it
> takes around 11 seconds to perform the filter for my grayscal image of size
> 1580x1050. On other hand if select  Median from the menu Process -> Filters
> -> Median and set Radius 9 it takes around 2.5 five seconds only to perform
> the filter for the same image. I know that Median is one of the rank filters
> of imageJ. What is the difference between Median in rank Filters And
> Median_Filter As Plugin? i Know that In Median_Filter it applies 9x9 median
> for each pixel. But i need     know about Median of rank filter. I tried to
> see code but could not understand exactly what it does. What is difference
> between kernel value and Radius Value? It would be great help if Any one
> explain the logic of Median of rank filter?

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[ashishdonvir]

yes i am ashish. Thanks for your reply.

Now can you please simplify Median of RankFilter for me as i have to implement it on my own way. And accuracy does matter for me as i am suppose to use this for medical imaging. And Median of Rank Filter gives me better result.

I am comparing Rank Filter with this http://svg.dmi.unict.it/iplab/imagej/Plugins/Forensics/Median_filter2/Median_Filter.html

my own implementation is same as above take the same time. Now plese take a moment and simplify median of RankFilter for me. I mean if we don't use multithreding what would be the logic of Median. I have my image of type unsigned short.

Thank you in advance..

[Michael Schmid]

Hi Ashish,

it is still unclear to me what you need -- could you specify exactly what you want?

(1) A median filter as fast as the built-in one, but with a different structuring element (e.g. not using a circular but a rectangular area)?
(2) A simplified version as a starting point for something in addition to calculating the median?  If so, what do you want to do?
(3) An explanation how to efficiently compute the median for a set of numbers?  ("Hoare's find algorithm", also named "quickselect"; search for it on the web).

You might also have a look at the source code of the RankFilters in ImageJ 1.37.  There, the RankFilters are still simpler, with less optimization and no multithreading (still using Hoare's find algorithm).  You can get it at http://rsb.info.nih.gov/ij/download/src/

Michael
________________________________________________________________
On Oct 19, 2013, at 19:09, ashishdonvir wrote:

> yes i am ashish. Thanks for your reply.
>
> Now can you please simplify Median of RankFilter for me as i have to
> implement it on my own way. And accuracy does matter for me as i am suppose
> to use this for medical imaging. And Median of Rank Filter gives me better
> result.
>
> I am comparing Rank Filter with this
> http://svg.dmi.unict.it/iplab/imagej/Plugins/Forensics/Median_filter2/Median_Filter.html
>
> my own implementation is same as above take the same time. Now plese take a
> moment and simplify median of RankFilter for me. I mean if we don't use
> multithreding what would be the logic of Median. I have my image of type
> unsigned short.
>
> Thank you in advance..

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[m_azodi]

Hi Michael,

If I am right, we do have three different Median Filters here:
1) RankFilters plugin
2) FastFilters plugin (less accuracy but fastest one)
3) Median_filter plugin
I am wondering if all of the mentioned plugins could perform median filter on 24 or 32-bit images?
Apart from them, do you suggest any other median filter algorithm (outside of the concept of imageJ framework) which would perform fast on processing 24 or 32-bit images? If yes, then please leave me the implementation link.

Thanks in advance.

[Michael Schmid]

Hi,

when referring to 'RankFilters', this usually means the built-in filters of ImageJ, such as mean, median, minimum, maximum in Process>Filters.  Many built-in filters are actually plugins.

Fast Filters (external plugin): In contrast to the built-in RankFilters, it does not take a (roughly) circular area where the pixels are read from ('support' or 'kernel' area) but a square area. For the median, it actually does not calculate the median inside this square area, but it first calculates the median for the lines, then for the columns of the median-filtered lines. This is a bit faster than the median over the square area would be, but it does not always give the same result. Nevertheless, it is almost as good as a 'true' median.

The built-in Process>Filters>Median (RankFilters) and the Fast Filters internally use 32-bit float data. Other image types are converted to 32 bits.

Some other external filters cannot handle float data, e.g. the fast median http://ij-plugins.sourceforge.net/plugins/filters/ works only on 8-bit and 16-bit data (but it is faster than the built-in version).

I don't know which external Median_filter plugin is the one you are interested in? In any case, you can simply try whether it works for your data.


Michael
________________________________________________________________
On May 8, 2014, at 23:55, m_azodi wrote:

> Hi Michael,
>
> If I am right, we do have three different Median Filters here:
> 1) RankFilters plugin
> 2) FastFilters plugin (less accuracy but fastest one)
> 3) Median_filter plugin
> I am wondering if all of the mentioned plugins could perform median filter
> on 24 or 32-bit images?
> Apart from them, do you suggest any other median filter algorithm (outside
> of the concept of imageJ framework) which would perform fast on processing
> 24 or 32-bit images? If yes, then please leave me the implementation link.
>
> Thanks in advance.

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html