How do I make a weighted MEDIAN filter in matlab?

Hi everybody... I want to build a weighted median filter, (not an weighted average filter). A proffessor told me that I could use an histogram but I really dont know what he reffers to and he didn't told me anymore about. I really need help with that.

Greetings from Venezuela!

[bym]

the median value would be where the area of the histogram is equal to 50%. Is this an image processing application?

Answer 1

[Jan Rubak]

Hi Eduardo,

[This answer is incorrect. Please see the update in the comment below it.]

A weighted median is probably just another word for a percentile calculation from a data set where the weight parameter is a value between 0 and 100 (with the 50th percentile returning the traditional median value).

If your data set is not too large, then the easiest way to obtain a percentile value is simply to sort it into ascending order and look at the corresponding index in the sorted array. A histogram and a sorted data vector contain basically the same information (one is the derivative of the other flipped on its side).

function Value = GetPercentileValue(DataVector,Percentile)

DataVector = sort(DataVector(:));
idxTarget = 1+(numel(DataVector)-1)*Percentile/100;
idx1 = floor(idxTarget);
idx2 = ceil(idxTarget);
idxFract = idxTarget - idx1;
Value = DataVector(idx1)*(1-idxFract) + DataVector(idx2)*idxFract;

If you're looking to apply this to a one-dimensional DSP problem, then with a bit of bookkeeping, you could maintain a temporally local sorted list of the data which slides along in time, dropping individual values as they pass out of the window while adding the new ones that enter on the other side. If your window size is small enough, it may suit you better to just brute force it by sorting the whole interval from scratch with each new iteration. Depending on your data sizes, this could be vectorized pretty easily by constructing a two-dimensional array where each column contains your entire time-series shifted by one step, and then calling sort(DataArray,2) and using similar logic as above to combine the two appropriate columns in the sorted array.

For a two-dimensional image processing problem, the sliding window approach can be generalized so that each horizontal step you drop a line of pixels out of your list from one side of your window and add a line of new pixels from the other side (and of course a little more care needs to be taken each time you shift down one raster line). If the window size is small, say 5x5 pixels (depending on your image size and available memory), you can create a three-dimensional array with 25 layers, each layer being an appropriately shifted copy of the original image, call sort() along dimension 3 and then combine the appropriate two layers in the result.

In those cases where you want to compute a percentile value from a very large set of data (i.e. large enough that a sort() operation is overkill or not practical due to memory/runtime issues), you'll need to construct a histogram or a cumulative histogram from the data, and then use that to tell you the percentile value. I'm not sure if the Matlab-native hist() function or any of its compatriots allow you to do something like that easily, or if they're mainly just tools for generating plots. I have a personal routine for analyzing multi-gigabyte data files that does something like this, but it's not mature enough yet for me to share it with the File Exchange community at this point, and in any case this doesn't sound like what you probably need.

Hope this helps.

-Jan

[Jan Rubak]

Oops. Years later I encountered the weighted median in some literature, and realized how wrong my answer was for this. What I described above is just a quantile calculation.

Here's a simple function that computes the weighted median of a vector:

function val = WeightedMedian(xVec,wVec)

    validateattributes(xVec,{'numeric'},{'vector'},'WeightedMedian()','x')
    validateattributes(wVec,{'numeric'},{'nonnegative' 'size' szX},'WeightedMedian()',w)

    [xVec,idx] = sort(xVec);
    
    massVec = cumsum(double(wVec(idx)));
    
    val = xVec( find( massVec >= 0.5*massVec(end) ,1,'first') );
    
end

And, with a very minor modification this can also be used to compute a weighted quantile:

function val = WeightedQuantile(xVec,wVec,q)

    validateattributes(xVec,{'numeric'},{'vector'},'WeightedQuantile()','x')
    validateattributes(wVec,{'numeric'},{'nonnegative' 'size' szX},'WeightedQuantile()',w)
    validateattributes(q,{'single' 'double'},{'scalar' '>=' 0 '<=' 1},'WeightedQuantile()',q)

    [xVec,idx] = sort(xVec);
    
    massVec = cumsum(double(wVec(idx)));
    
    val = xVec( find( massVec >= q*massVec(end) ,1,'first') );
    
end

Incidentally, Wikipedia also has an entry now (since 2013) on the weighted median.

[Hudson Romualdo]

Hi Jan Rubak.

Do you remember what literature?

I would like to find something that explain to me the weighted median method like i'm 10 years old. =)

[Jan Rubak]

Hi Hudson,

I don't recall what paper it was, but I'll add an update here if I track it down. I do remember that its main focus was not the weighted median, but rather that it was used as a tool in part of the analysis. They therefore included a brief appendix with the definition which I found clarifying.

The Wikipedia entries on "weighted percentile" and "weighted median" together contain a pretty good mathy explanation, but they spend more time emphasizing the fuzzy vagaries and special cases of the definition rather than illuminating what it actually means. What's worse, I think the figure currently used in the weighted median article is more confusing than illuminating.

Here's an explanation that I hope would satisfy a ten-year-old: Suppose we want to know the median age of the people in your classroom, but weighted by each person's height. First have everyone line up in order from youngest to eldest. Next have each person stand on the head of the person in front of them in line, so they form a single tall human tower. Measure how tall the tower is, and then go to exactly half of that height and see which person is located there. It is their age that is the weighted median.

Out of compassion for the participants' spines, you can perform the equivalent calculation by having them lie down on the ground instead, forming a long straight line with the youngest person at one end and the eldest at the other end. But for some reason I find it more useful to imagine the weighted median as a particular altitude up a vertical tower than as a particular milepost along a horizontal extent.

I think my preference for vertical over horizontal here is because I like to think of histogram analysis in terms of the empirical distribution function (which has the benefit of no resolution tradeoffs due to binning). The definition of the EDF is pretty straight-forward (again, see Wikipedia), and very naturally generalizes to the weighted case. The median value is then the point along the x-axis where the y-value of the EDF crosses 0.5.

Hope this helps!

[Jan Rubak]

P.S. I found the paper. The (brief) appendix with the weighted median definition is on the second last page.

Li & Arce [2004] - A Maximum Likelihood Approach to Least Absolute Deviation Regression