No icon

Efficient Scalable Median Filtering Using Histogram-Based Operations

Efficient Scalable Median Filtering Using Histogram-Based Operations


Median filtering is a smoothing technique for noise removal in images. While there are various implementations of median filtering for a single-core CPU, there are few implementations for accelerators and multi-core systems. Many parallel implementations of median filtering use a sorting algorithm for rearranging the values within a filtering window and taking the median of the sorted value. While using sorting algorithms allows for simple parallel implementations, the cost of the sorting becomes prohibitive as the filtering windows grows. This makes such algorithms, sequential and parallel alike, inefficient. In this work we introduce the first software parallel median filtering that is non-sorting based. The new algorithm uses efficient histogram based operations. These reduce the computational requirements of the new algorithm while also accessing the image fewer times. We show an implementation of our algorithm for both the CPU and NVIDIA’s CUDA supported GPU. The new algorithm is compared with several other leading CPU and GPU implementations. The CPU implementation has near perfect linear scaling with a 3.7X speedup on a quad-core system. Our GPU implementation is several orders of magnitude faster than the other GPU implementations for mid-size median filters. For small kernels, 3 _ 3 and 5 _ 5, comparison based approaches are preferable as fewer operations are required. Lastly, the new algorithm is open-source and can be found in the OpenCV library.

Existing System:

Median filtering requires a single parameter, k, which represents the size of the filtering windows (sometimes referred to as the kernel). Median filtering works as follows, for each pixel in the image, a k_k window is placed around that pixel and the median value of theses pixels is taken as the output value. Hence, the name median filtering. How that median value is found is algorithm dependent. One popular method for finding the median value is to sort all the k2 values and then simply take the value at the middle of the outputted array the sorting algorithm is dictated by several factors: the data itself, the storage requirements, amount of data movement required by the algorithm, and the parallel scalability of the algorithm.


Proposed System:

Our new algorithm papers extends the work of Perreault and Hebert and presents to the best of our knowledge the first software parallel algorithm for median filtering that uses histogram based operations and accesses each pixel O(1) times. The main contribution of this paper is to show how to partition the work required by the median filtering to a many-core system. This algorithm is appropriate both for a standard multi-core CPU system and for modern day GPU systems.

Comment As:

Comment (0)