COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### how to make the rolling median more efficient

• Follow

```Just to summarize what I have learned so far:
******************************************************************
efficent code of roll/expanding mean => efficient code of roll/expanding stdev (with small risk of cancellation error mentioned by Derek)
expanding mean is implemented by cumsum function already built-in.
rolling mean is implemented either by filter or cumsum trick.
expanding max is fast enough using simple loop
******************************************************************

Now, two more questions:

******************************************************************
How to efficiently implement the rolling/expanding percentile (special case would be median)
******************************************************************

```
 0

```"andy Lu" <luyi36@gmail.com> wrote in message <hih0ts\$b2a\$1@fred.mathworks.com>...

This is the result of a search on "sliding window" in the file exchange

http://www.mathworks.com/matlabcentral/fileexchange/?term=sliding+window

It should have a number of options for you.
```
 0

```"andy Lu" <luyi36@gmail.com> wrote in message <hih0ts\$b2a\$1@fred.mathworks.com>...

> Now, two more questions:
>
> ******************************************************************
> How to efficiently implement the rolling/expanding percentile (special case would be median)
> ******************************************************************

For rolling percentile, it would look something like this

x=sort(x);

x(round(p*(1:length(x)))); %p is percentile
```
 0

```As Matt has pointed out, one way to perform median filtering is sorting on running window. One of the implementation on 2D is here

This apply as well on 1D array (just provide the appropriate input).

In term of algorithmic, one can do better by inserting/removing elements in a sorted FIFO windowed array. If the data structure is well designed, that task can be carried out in O(log(window size)) complexity. Such complexity is meet by algorithms such as dichotomy search or Downheap of a heap structure.

But I guess for most applications where window size is not too big a brute force sorting is fast enough.

Bruno
```
 0

```"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hih8no\$icd\$1@fred.mathworks.com>...
> "andy Lu" <luyi36@gmail.com> wrote in message <hih0ts\$b2a\$1@fred.mathworks.com>...
>
> > Now, two more questions:
> >
> > ******************************************************************
> > How to efficiently implement the rolling/expanding percentile (special case would be median)
> > ******************************************************************
>
> For rolling percentile, it would look something like this
>
> x=sort(x);
>
> x(round(p*(1:length(x)))); %p is percentile

Thanks Mat.

I have tried following, which is very slow. Did I do something bad?

function r=runmed3(x,p,wind)

[m, n]=size(x);
r = zeros(m-wind+1,n);
pos = round(p*wind);

for c=wind:m
x2 = sort(x(c-wind+1:c, :));
r(c-wind+1,:) = x2(pos,:);
end;

end

tic
x=rand(30000, 30);
runmed3(x,0.5,200);
toc
Elapsed time is 7.845210 seconds.
```
 0

```"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hihfkg\$4er\$1@fred.mathworks.com>...
> As Matt has pointed out, one way to perform median filtering is sorting on running window. One of the implementation on 2D is here
>
>
> This apply as well on 1D array (just provide the appropriate input).
>
> In term of algorithmic, one can do better by inserting/removing elements in a sorted FIFO windowed array. If the data structure is well designed, that task can be carried out in O(log(window size)) complexity. Such complexity is meet by algorithms such as dichotomy search or Downheap of a heap structure.
>
> But I guess for most applications where window size is not too big a brute force sorting is fast enough.
>
> Bruno

Thanks Bruno.

I will try the 2D version.  Your max/min filter is great!
```
 0

5 Replies
315 Views

Similiar Articles:

7/22/2012 1:11:26 PM