Forums > MaxMSP

Coder for median~?


Jun 07 2007 | 3:51 pm

I noticed there isn’t an object to do median filtering in MSP.
Median-filtering is more expensive as an envelope follower because it
requires sorting, but it’s really nice in that it’s not affected by
sudden spikes in the way that average~ might. (and is really useful as
an adaptive threshold for envelope detection)

Would anyone be interested in implementing a C++ version of a
signal-rate median filter using quicksort or some other type algorithm?
I definitely don’t have the C/C++ chops to knock this one out, but it
seems like it could be particularly useful.

thanks,
Peter McCulloch

http://www.petermcculloch.com

Jun 07 2007 | 5:31 pm

On 07 Jun 2007, at 17:51, Peter McCulloch wrote:

> I noticed there isn’t an object to do median filtering in MSP.
> Median-filtering is more expensive as an envelope follower because
> it requires sorting, but it’s really nice in that it’s not affected
> by sudden spikes in the way that average~ might. (and is really
> useful as an adaptive threshold for envelope detection)
>
> Would anyone be interested in implementing a C++ version of a
> signal-rate median filter using quicksort or some other type
> algorithm? I definitely don’t have the C/C++ chops to knock this
> one out, but it seems like it could be particularly useful.

hi,
if you want something like a "running" median, you don’t need a
sorting algorithm.
once the history array is initialized correctly, you just throw out
the oldest sample value, fit in the new value where it belongs (and
move all values in between) and return the middle value of the array,
the median value.

that’s how it’s done in supercollider’s Median UGen. i have
implemented this code in an msp object (sorry, i couln’t find a
maxmsp only solution ;-) ) for a project, but ended up not using it.
so, it is not heavily tested, seems to work alright, though.
contact me off list, if you are interested.
volker.

Sep 26 2016 | 2:10 pm

Suuuper old bump here, but has anyone gotten a median filter going in gen-land?

Like (the younger version of Peter) I’m looking to use some median filtering for envelope/onset detection.

There’s Roald’s MSP version here, but it’s a lot of objects for just a 5 sample window:
https://cycling74.com/forums/topic/audiorate-median-filter/

Sep 26 2016 | 10:22 pm

try this– sort algorithm is very inefficient, but gets rid of spikes (it’s got an analysis window of 71 samples — maybe if it’s just 15 or so it will be tolerable, as the complexity is n squared)
You can change from 71 to something else by altering some params in the gen patch

edit: better actually attach patch:


-- Pasted Max Patch, click to expand. --

Sep 26 2016 | 11:14 pm

Check out Graham’s insert sort for gen~
https://cycling74.com/forums/topic/insert-sort-of-a-buffer-in-gen-codebox/

He mentioned the samples can be sorted on the GPU using cell-based operators. If so, it wouldn’t be too much trouble to sort "grayscale" amplitudes using this approach: https://www.shadertoy.com/view/4dcGDf while reading the sorted buffer with gen~.

http://dafx13.nuim.ie/papers/06.dafx2013_submission_46.pdf (section 2)

http://sonification.de/handbook/download/TheSonificationHandbook-HermannHuntNeuhoff-2011.pdf (section 8.2)

Sep 27 2016 | 4:18 am

@Floating Point
That works gang-busters, but damn is it expensive! Like 50-60% on my (shitty) desktop machine.
It has to be around 40+ samples before you start seeing meaningful reduction in the spikes (in the example anyways).

@Metamax
Ah, didn’t see that before or when searching. I guess one can arrive at the median by any sorting algorithm, and indeed curious about using the GPU for that part of the process.

I’ve been looking at this thesis here: (As suggested by @AlexHarker in this thread (https://cycling74.com/forums/topic/onset-detection/)
https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/3809/BROSSIERAutomaticAnnotation2006.pdf

Specifically section 2.4, which has lots of juicing info, though I haven’t chased down all the references, especially since I no longer have access to journals and such.

Sep 27 2016 | 9:09 am

fwiw, here is a gen~ implementation of supercollider’s median filter


-- Pasted Max Patch, click to expand. --

Sep 27 2016 | 12:00 pm

Ooh that’s nice. Not too expensive either.

Just a quick experiment, but I managed to cobble something *very* usable using the signal path proposed in that thesis I linked.
Specifically figure 2.5:
Audio -> (DC-removal) -> (lowpass filter) -> (moving median) -> (moving mean) -> (thresholding) -> (peak picking)

Actually looking at it now, I’ve done the mean/median backwards, but I couldn’t get a version working well with them the other way around. I guess I am also implementing it in a typical volume differential way, so I don’t know if that’s supposed to be different.

Lots of room for improvement here, specifically with using a dynamic thresholding as described by the thesis as well. (Right now going from dead silence to the tiniest sound produces a wild differential)

— Pasted Max Patch, click to expand. —
Oct 01 2016 | 4:48 am

this works quite nicely indeed – an interesting idea to use the noise removal capabilities of a median filter to actually detect transients. still a bit expensive though.
I don’t think you’re following what’s described in the thesis, but who cares if it works?

Oct 01 2016 | 4:59 am

Definitely not ‘by the book’ there, but as an initial test it provided promising results.

What I like the most about it is that it provides super clean/tight spikes in the differential, rather than the envelope-shaped decreases you get from subtracting two envelope followers.

Other than that, I wouldn’t know where to implement a median filter (in the scale of 2-50samps) to create a dynamic thresholding across multiple onsets.

Oct 03 2016 | 6:19 am

This is very useful. Thanks guys!

Viewing 11 posts - 1 through 11 (of 11 total)

Forums > MaxMSP