Hierarchical Histogram-based Median Filter for GPUs

Median filtering is a widely used non-linear noise-filtering algorithm, which can efficiently remove salt and pepper noise while it preserves the edges of the objects. Unlike linear filters, which use multiply-and-accumulate operation, median filter sorts the input elements and selects the median of them. This makes it computationally more intensive and less straightforward to implement. This paper describes several algorithms which could be used on parallel architectures and propose a histogram based algorithm which can be efficiently executed on GPUs, resulting in the fastest known algorithm for medium sized filter windows. The paper also presents an optimized sorting network based implementation, which outperforms previous solutions for smaller filter window sizes.