Median Filter Exploration
Filed under Technology
Background
One day, I was browsing through some concept arts and stopped at one stunning image. Basically, there’s “depth of field” on that image; however, it’s not the normal depth of field. Instead of blurred objects at far distance, you have “median filtered look” of objects at far distance. It led me to think: “hey, what about using median filter instead of gaussian filter?”
Implementing a trivial median filter has a big disadvantage that is it costs a lot more than gaussian filter. You need to sort the samples you take and look for the middle (median) value of that samples. Let say you take N samples, the fastest sorting algorithm is N log N (Of course, in this case I don’t include bucket/radix sort). Remember, we need to do this in GPU, so a complex algorithm like quick sort/merge sort/heap sort is out of question. You probably ended up with N*N sorting algorithm.
Pseudo Median Filter
As always, I googled to find an answer. I found this “Pseudo Median Filter” that’s faster than Median Filter and tries to mimic the original median filter effect. I found this from a forum in http://www.razyboard.com/system/morethread-cartoon-glsl-shader-pete_bernert-266904-2751605-0.html.
Basically, the algorithm is like this:
| c00 | c01 | c02 |
| c10 | c11 | c12 |
| c20 | c21 | c22 |
Assuming the current pixel is c11, take the c11,c10,c12,c01,c21 colors and then re-calculate c11:
float3 mn = min( min(c10,c12), min(c01,c21) );
c11 = (c11+c10+c12+c01+c21-mx-mn)/3.0;
That yields the following result:
| Pseudo Median Filter – Before | Pseudo Median Filter – After |
|---|---|
 |
 |
To me, it doesn’t look good enough. First, it looks more like a blur than a median filter. What I’m looking for is the “abstraction” of image when I apply median filter. This algorithm is no good; let’s move on.
Fast, Small Radius GPU Median Filter
My next research is to implement the “real” median filter. However, I’m not going to code the median filter; I’ll just google it. I found this page: http://graphics.cs.williams.edu/papers/MedianShaderX6/. I took their 5×5 median filter code, and here’s the result and comparison with gaussian blur.
| Original | What I Want (Photoshop Median w/ Radius = 4) |
|---|---|
 |
 |
| Median Filter | Gaussian Blur |
 |
 |
And Yes! This is close to what I want. There are two defects:
- It’s quite slow. I apply the filter 5 times.
- I probably need bigger kernel size than just 5×5 in order to get more abstraction
Share This
Jan16
