Median filter
category: general [glöplog]
Do you know what exactly does Photoshop median filter? I understand median for greyscale images perfectly... but what about color images? Does median it is the median of every channel by separate? Or what?
it works on brightness. though it's not a simple kernel convolution as far as i know. v of each pixel is saturated to an average range of its neighbors.
which means pixels that are similar to their neighbors are untouched.
median filters are usually used for removing noise artifacts..
going through proximity window of 8 neighbours of the pixel (or wider) and choose for the pixel in the new buffer the value of the median of all the 9 pixels. it wont blur edges as much as.. well.. blur filter.. but will get rid of the pixel granulation..
thats the median filter i know, maybe photoshop's one is different.. O_o can't check now i installed gimp 2 last time i had to reinstall stuff.
going through proximity window of 8 neighbours of the pixel (or wider) and choose for the pixel in the new buffer the value of the median of all the 9 pixels. it wont blur edges as much as.. well.. blur filter.. but will get rid of the pixel granulation..
thats the median filter i know, maybe photoshop's one is different.. O_o can't check now i installed gimp 2 last time i had to reinstall stuff.
ps: and now think again and say what's the median when we're dealing with 3-tuplets as values. :)
uh.. thats what i get for only reading half the message before replying. i should be in bed.. do ignore me. -_-
...so this is where you start prepping test images?
shouldn't be hard to do :)
shouldn't be hard to do :)
it's also handy to get rid of jpeg artifacts or upscale a pic really big, median filter it and scale it down and you can 'cheat' doing some anti-aliasing on the fly that way..
You know, median is really great witn video, to separate a static background from moving objects. This is what I want to use it for.
you can do the median separately for each channel (which may be what ps does) but since the sort is the slow part you probably want to sort according to, e.g., overall intensity.
for small kernels (3x3, 4x4, etc.) there are well-known routines for doing the median w/ a minimal # of comparisons. you can also try randomized median where expected time to find the middle element is small (but the cost of the rand()s might make this not worthwhile for small kernels)
for small kernels (3x3, 4x4, etc.) there are well-known routines for doing the median w/ a minimal # of comparisons. you can also try randomized median where expected time to find the middle element is small (but the cost of the rand()s might make this not worthwhile for small kernels)
Well, doing the median for every channel might work (I've not tried it yet), but it may generate undesired colors. What I want is not space median but time median, so I have N frames and I want to know for every pixel wich color is the median of all the frames. This way, in a static video, I can delete moving objects and left only the background. Median is commonly used for this purpose. I don't care about speed. Maybe there are other methods for this thing... I'm just thinking about it. It is easy to explain, I just want to pick the most common color from a time sequence of colors. The problem is that due noise in video inputs, we may have not two equal colors (by pigeonhole, you can't be sure of having 2 equal colors by pixel with less than 2^24+1 frames). So, how to choose a good one? Median looks to work good enough, but maybe there are other good solutions like searching for the highest density of pixel values inside a sphere in an rgb 3d space... or something similar using an octree to make it faster or whatever...
use a median with a radius of number of frames in your clip. here's the algorithm step by step for your (where V(x,y,t) is the color at x,y and t):
1) find the mean of V(x,y,t) over t. You will just get the average frame of the video namely m1(x,y)
2) weigh each pixel using m1(x,y) and find a weighed average m2(x,y) which will be your background.
the important part is finding the weight W(x,y,t) for m2 of course. once you obtain it m2 will be sum(W(x,y,t) * V(x,y,t)) over t. i can easily propose several methods for this.
- you can first mark each pixel at V(x,y,t) as near to m1(x,y) or not by comparing colors. near means:
|V(x,y,t) - m(x,y)| < threshold
in rgb space. length of a color is sqrt(r*r+b*b+g*g).
marking pixels near of far will give you a binary data W'(x,y,t). normalize it over t (divide each x,y pair with the number of marked pixels) to obtain W(x,y,t) and therefore m2(x,y). we simply averaged the frames again by using only the pixels that are near m1(x,y) discarding object components hopefully.
- the problem with the above approach is the object will possibly cast shadows on the background. to overcome this problem, etiher find m1 in terms of hue, or make the comparison above in hs domain discarding v. OR compare the color vector by their angles only:
V(x,y,t) . m(x,y) / |V(x,y,t)| . |m(x,y)| > threshold
in rgb domain. you compare the cosine of the angle of two rgb vectors to a threshold which is much like a comparison in hs domain. once you've compared again, find the binary W' then W and then m2.
- another approach could be using a gaussian W with m2 mean (a literal median filter). this won't deviate m1 from m2 much though.
by far i assumed the camera movements won't change the background much. if you have a bricked wall tile for example, 1 or 2 pixel shift won't change the color intensity much. if the panning is so much that you can't assume such a property, either try synchronization with block correlation (which would probably suck since you don't see all the blocks of the background) or use wavelet decomposition for identifying moving objects first an then not weighing them - weight them according to their motion factors found with wavelet transform.
1) find the mean of V(x,y,t) over t. You will just get the average frame of the video namely m1(x,y)
2) weigh each pixel using m1(x,y) and find a weighed average m2(x,y) which will be your background.
the important part is finding the weight W(x,y,t) for m2 of course. once you obtain it m2 will be sum(W(x,y,t) * V(x,y,t)) over t. i can easily propose several methods for this.
- you can first mark each pixel at V(x,y,t) as near to m1(x,y) or not by comparing colors. near means:
|V(x,y,t) - m(x,y)| < threshold
in rgb space. length of a color is sqrt(r*r+b*b+g*g).
marking pixels near of far will give you a binary data W'(x,y,t). normalize it over t (divide each x,y pair with the number of marked pixels) to obtain W(x,y,t) and therefore m2(x,y). we simply averaged the frames again by using only the pixels that are near m1(x,y) discarding object components hopefully.
- the problem with the above approach is the object will possibly cast shadows on the background. to overcome this problem, etiher find m1 in terms of hue, or make the comparison above in hs domain discarding v. OR compare the color vector by their angles only:
V(x,y,t) . m(x,y) / |V(x,y,t)| . |m(x,y)| > threshold
in rgb domain. you compare the cosine of the angle of two rgb vectors to a threshold which is much like a comparison in hs domain. once you've compared again, find the binary W' then W and then m2.
- another approach could be using a gaussian W with m2 mean (a literal median filter). this won't deviate m1 from m2 much though.
by far i assumed the camera movements won't change the background much. if you have a bricked wall tile for example, 1 or 2 pixel shift won't change the color intensity much. if the panning is so much that you can't assume such a property, either try synchronization with block correlation (which would probably suck since you don't see all the blocks of the background) or use wavelet decomposition for identifying moving objects first an then not weighing them - weight them according to their motion factors found with wavelet transform.
Quote:
a gaussian W with m2 mean
i mean "a gaussian W with m1 mean".
Why do you have ps's avatar? You know that's ilegal, right?
it's ps's avatar + a watermark on it. try extracting it ;)
anes: looks more like you forgot to set transparency
Oh... I see now. Sorry...
huh? when looking at the description from anes i got kinda confused..
i always thought a pure median filter was taking the pixel neighbourhood, sorting them (mostly in order of luminance or palette order) and then taking the center as output. this works great against "outliers" i.e. salt and pepper noise.
i never tried the photoshop median filter but it seems from this description it only uses "linear" operations and no sorting?
separating movement and background from video with a "median" sounds great btw!! mostly block-search stuff is used for this (MPEG video). this median sounds like a simple alternative?
i always thought a pure median filter was taking the pixel neighbourhood, sorting them (mostly in order of luminance or palette order) and then taking the center as output. this works great against "outliers" i.e. salt and pepper noise.
i never tried the photoshop median filter but it seems from this description it only uses "linear" operations and no sorting?
separating movement and background from video with a "median" sounds great btw!! mostly block-search stuff is used for this (MPEG video). this median sounds like a simple alternative?
earx: Can you elaborate on that "separation of foreground/background using median filtering" concept ?
earx: i've proposed a method to apply "photoshop median" for seperating static background from static shot video clip. for images it has the advantage of keeping pixels that are not the median of their neighbors but also not noise either.
for frame collusion this doesn't matter since all samples are lost. neither this nor the general median method in literature is the best way to accomplish the same task anyway. in fact it pretty much depends on your data set (speed and occurence of moving objects, shadows, daylight change etc). (for a single clip, i would rather extract the background by selecting partial regions by hand at certain frames.)
for frame collusion this doesn't matter since all samples are lost. neither this nor the general median method in literature is the best way to accomplish the same task anyway. in fact it pretty much depends on your data set (speed and occurence of moving objects, shadows, daylight change etc). (for a single clip, i would rather extract the background by selecting partial regions by hand at certain frames.)
btw what i call "photoshop median" could be a plug-in also. simple median should distort non-outlier peaks in the image. i'll try it today.