Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
how to make the rolling median more efficient

Subject: how to make the rolling median more efficient

From: andy Lu

Date: 12 Jan, 2010 05:22:04

Message: 1 of 6

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)
******************************************************************
also how about rolling max??

Thanks in advance for your advice!

Subject: how to make the rolling median more efficient

From: Matt J

Date: 12 Jan, 2010 07:20:04

Message: 2 of 6

"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.

Subject: how to make the rolling median more efficient

From: Matt J

Date: 12 Jan, 2010 07:35:20

Message: 3 of 6

"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

Subject: how to make the rolling median more efficient

From: Bruno Luong

Date: 12 Jan, 2010 09:33:04

Message: 4 of 6

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

http://www.mathworks.com/matlabcentral/newsreader/view_thread/251787

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

Subject: how to make the rolling median more efficient

From: andy Lu

Date: 12 Jan, 2010 15:49:04

Message: 5 of 6

"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.

Subject: how to make the rolling median more efficient

From: andy Lu

Date: 12 Jan, 2010 15:52:02

Message: 6 of 6

"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
>
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/251787
>
> 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!

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us