COMPARISON OF ALGORITHMS FOR STANDARD MEDIAN FILTERING

In standard median filtering we search repeatedly for a median from a sample set which changes only slightly between the subsequent searches. We review several well-known methods for solving this running median problem, analyze the (asymptotical) time complexities of the methods, and propose simple variants which are especially suited for small sample sets, a frequent situation. Although we have restricted our discussion to the one-dimensional case, the ideas are easily extended to higher dimensions.