I am looking for imformation about how to quickly w/low processing reduce
noise in a image.  I seen a couple of examples of other ways off
http://en.wikipedia.org/wiki/Median_filter (at the bottom of the page) but I
can't understand the formula.

Currently I am taking the image down to a byte array and doing a standard
"median" filter against the image where you take the current pixel and
compare against the surrounding pixels to get the "median" value. i.e.

for(y = 1; y < height - 1; y++)
    for(x=1; x < width - 1; x++)
    {
        ArrayList Red = new arraylist(), green....... blue.......
        for(yy = y-1; yy < y+1; yy++)
            for(xx = x - 1; xx < x+; xx++)
                Add to red, green, blue

        // sort red, green, blue
        Red.sort();
        gree....
        blue....

        // each array's total size is 9 bytes which means the median is the
4th value of each array after the sort
        redmedian = red[4]
        blue......
        gree......
    }


This is working like a champ and given the desired results but at a hugh
cost to processing and time to process.  Im running off a dual core machine
and its running around 50% proc and taking around 500ms to complete this.

On Thu, 11 Dec 2008 18:00:30 -0800, anonymous <spam@myplaceinspace.com> 
wrote:

Short of someone writing a comprehensive article reiterating exactly the 
information found in the articles you're already aware of, I'm not clear 
on what kind of help you're looking for here.

Well, without knowing the size of the image being processed, it's 
impossible to know whether 500ms is a reasonable time or not.

That said, your posted algorithm is essentially a brute-force median 
calculation, so it's not very surprising it's slow.  The algorithms 
referenced by the Wikipedia article themselves compare their performance 
against a previous optimization.  So, if you had even implemented that 
previous optimization, you'd be ahead of the game.

I think you've got a couple of choices: either take the time to read and 
understand the articles about the various algorithms that can be used for 
the processing (you already have the references...it's just a matter of 
studying them); or you can use a third-party library to do the image 
filtering (I don't have information off the top of my head, but I'm sure 
there are a wide variety of options along those lines).

On the latter point, Google shows quite a number of options, with this 
search:
http://www.google.com/search?q=gnu+median+filter+c%23
Also, the second link on the Wikipedia article takes you to a page that 
has a link to a C implementation of the algorithm.  It's great if you can 
understand the algorithm, but from a practical point of view if you just 
port the C code, that would probably be enough for your purposes.

Maybe you'll catch someone in a rare moment when they've got a lot of time 
on their hands and can invest the time and effort in writing an article 
explaining the algorithms to you.  But, I wouldn't count on it if I were 
you.  :)

Pete

You don't show how you are retrieving / setting the pixels and that is where
you are most likely to incur your penalty.

Google for something like
    c# fast bitmap pixel access

This shouldn't be the case, as the OP stated he's reduced the image
down to a byte array, and access to a byte array (whether rectangular
or jagged) should be pretty quick.

The slow down might just be the sort step.  A mean or Gaussian
convolution should be faster than median filtering.  Maybe try
implementing one of those?  If it's still slow, then you can be
reasonably sure it's not an algorithmic problem, and profiling it to
find where the actual bottleneck is would be a good opportunity to
learn about performance counters.

~Dathan

But how? :-)


I agree.  I think the OP should first do nothing in the loop.  Then add the
read pixel code, then the code to read surrounding pixels, then the code to
select the median, then the code to write the pixel.  Should be pretty
obvious then where the bottleneck is.

The slow down w/out a doubt is with the sorting and the alg being used to
process the current pixel and 8 surrounding pixels.

Reading/Writing bytes as Dathan stated is working like a champ and I can
compare frames (320X240 24bit) at 30fps without increasing processing time
or processor utilization.  Problem now is that the images are coming from a
camera and as such has noise.  This noise is causing issues with comparison.
Using the described alg the comparison works perfectly but this has cost me
hughly on time and processing.

Anywho.... thanks for your input.


Show quoteHide quote

What about using mean average instead of a median?  That way you don't need
a list or a sort

for xx
    for yy
        red += data[xx,yy];
        green += data[xx,yy]
        blue += data[xx,yy];

red = red / 9;
green = green / 9;
blue = blue / 9;

PS, you would need to read from one array and write to another, otherwise
you will be using averaged pixels to average against.

A median filter is quite often superior to a linear filter.  It
wouldn't hurt to try a mean or gaussian filter, but you might be best
off optimizing the median filter.

On Dec 15, 12:50 pm, JS <jnospams...@gmail.com> wrote:
A couple things to think about:
You know you're always looking at a group of 9 pixels.  So instead of
instantiating three ArrayList's per pixel (and eventually having to
garbage collect them), instantiate byte[] red = new byte[9]; and the
same for green and blue outside the outermost loop.  That alone should
save you a huge amount of time on garbage collection.  You'll also
save on array accesses, as access to an Array should be faster than
access to an ArrayList.

If that doesn't do the trick, you might try implementing your own Sort
() method.  In some cases for smaller result sets, it's actually
faster (due to overhead, recursion, etc.) to use a bubble sort than a
quicksort (which is what the MSDN documentation states that Array.Sort
() and ArrayList.Sort() use).

~Dathan

On Mon, 15 Dec 2008 14:53:54 -0800, Dathan <dat***@gmail.com> wrote:

It's unlikely that garbage collection is consuming a major part of the 
time of the algorithm.  Your advice to avoid repeated reallocations is 
good and should be followed, but it won't result in a significant change 
in the cost of the algorithm (i.e. the OP is currently using an algorithm 
that has to sort the data, which is what's dominating the cost, and the 
only way to fix that is to use a better algorithm).

There is no point at all in messing around with optimizing the OP's median 
filter algorithm.  There are already optimal, published algorithms, and as 
I pointed out in my first reply to this thread, one even comes with C code 
(which can easily be translated to C#).

It's true that there are _other_ things one might do, such as choosing a 
mean filter instead of median.  I.e. change the problem so it's easier.

But if what one wants is the median filter specifically, then just use the 
published optimal solution.

Pete

Thanks Dathan,

I will check out the other possible filtering methods.  I have isolated the
slow down as you stated down to the sort routines.


Show quoteHide quote

Private, Public, ... ?
Case insensitive generic list search ?
MVP pattern and application/user settings in WinForm
How to stop a working thread
Confused about conversion
new to socket programming; did i miss anything?
MT Data Retrieval Question
Anybody trying WPF?
console applications
Splash screen loading slow on Vista?