Ricardo M. Sanchez, Paul A. Rodriguez
Department of Electrical Engineering, Ponticia Universidad Catolica del Peru, Lima, Peru
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2012
The median filter is a non-linear filter
used for removal of salt and pepper noise from images. Each pixel of the
image is replaced by the median of its surrounding elements, the median
value is calculated by sorting the data. The complexity of the sorting
algorithms used on the median filters are O(n^2) or O(n), depending on
the kernel size. Those algorithms were formulated for scalar single
processor computers, with few of them successfully adapted and
implemented for computer with a parallel architecture. In this paper we
present a novel sorting algorithm, with O(n) computational complexity
and a highly parallelizable structure, based on the Complementary
Cumulative Distribution Function. Furthermore, a 2D median filter based
on our proposed sorting algorithm can achieve O(1) complexity. We have
implemented our proposed algorithm in two parallel architectures: SIMD
Intel and CUDA, which have a throughput of 12.8 and 35 ~ 57 megapixels
per second respectively
|