2 ms·
If the window is the length of the data, that becomes O(n log n) -- essentially no better than a sort? For images and other kernel-based filtering, there is a
by jallmann 13y ago
If the window is the length of the data, that becomes O(n log n) -- essentially no better than a sort?
For images and other kernel-based filtering, there is a O(1) median algorithm available: http://nomis80.org/ctmf.html http://nomis80.org/ctmf.html
- sesqu 13y agoThanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters). Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.
- andrewcooke 13y agomaybe i have misunderstood the application - i am talking about "median smoothing" with a "running window". w is typically fixed. but thanks for link to paper - that is new to me.