Introduction¶

The well-known method of median filtering is used both in a wide range of application frameworks and as a standalone filter. Small-window median filters can highly reduce the power of salt & pepper or additive gaussian (AWGN) noise and minimize edge blurring. Large-window filters are also used, for example to estimate the background of images. Currently, the window size should not be an issue as a constant time algorithm and several implementations, including GPU-based codes, have been proposed in recent years. Unfortunately, none of these constant time implementations manage to fully exploit the capabilities of modern GPUs and thus the throughputs of large-window median filters remain far below the peak throughputs allowed by recent GPU models. The statistical and theoretical analysis conducted in this paper demonstrates that a separable approximation of a 2D median filtering is often stronger than its full 2D implementation.

We propose a GPU implementation of 2D separable-median filters, able to output up to 125 billion pixels per second on a recent Volta V100, which significantly outperforms existing implementations like Nvidia’s NPP library or Green’s code, resulting in the fastest median filtering solution to date.

Reminder on median filtering¶

The principle of median filtering is, for each pixel of the input image, to replace its original gray level value by the median value of a set of neighbor pixels. Basicaly, this set of pixels can have various shapes: square, cross, rectangular, … Usualy, an odd-sized square window is used, centered on the pixel to process.

Full 2D median	Separable median

The median operator is non linear and cannot be considered as separable, ie. filtering with a square filtering window cannot be replaced by two consecutive filters, each using a 1D window. However, this technique of separable processing applied to median filtering is well-known for decades and is called the medians of medians. It allows to reduce the computational complexity of the real 2D filter together with achieving higher execution speeds. However, the output images processed in the separable way are not identical as those processed by the real 2D filter, because the median is not separable. In addition, scientists have estimated the output variance of both filter types and proved that the full 2D filter achieves a smaller output variance than the separable version, ie; the denoising power of the full 2D filter is stronger than those of the separable filter. That is probably why the separable median filter has not been widely used until now.

When the separable median filtering outputs higher quality images than the full 2D filter¶

Despite a lower output variance, a statistical study conducted over the 10,000 image of the BOSS database has shown that the separable filter can output better images than the full 2D filter. The main reason is that the separable filter corrupts less than the full 2D filter. Indeed, when processing an image, the median filters alters the gray level of noisy pixels to produce a more likely gray level value. However, it also alters some non noisy pixels,

Examples¶

Below are a few examples of images, taken from the BOSS database, resized, corrupted by salt & pepper noise and processed by both filter types. Some of these examples show configurations where the full filter produces better images than the separable, some others show configurations where the separable outputs better images. PSNR and MSSIM values have been obtained under Matlab R2017b.

Measurements on image #10, 8192x8192 pixels¶

Corrupted by 10 % salt & pepper noise¶

Cover image #10	Corrupted by salt & pepper 10 %
	PSNR= 14.59 dB, MSSIM= 0.071

Filtered by 15x15 full median	Filtered by 15x15 separable median	Filtered by 41x41 full median	Filtered by 41x41 separable median
PSNR= 44.66 dB, MSSIM= 0.995	PSNR= 49.76 dB, MSSIM= 0.996	PSNR= 32.81 dB, MSSIM= 0.971	PSNR= 33.94 dB, MSSIM= 0.973

Corrupted by 25 % salt & pepper noise¶

Cover image #10	Corrupted by salt & pepper 25 %
	PSNR= 10.61 dB, MSSIM= 0.016

Filtered by 15x15 full median	Filtered by 15x15 separable median	Filtered by 41x41 full median	Filtered by 41x41 separable median
PSNR= 40.97 dB, MSSIM= 0.994	PSNR= 47.74 dB, MSSIM= 0.994	PSNR= 32.03 dB, MSSIM= 0.971	PSNR= 32.95 dB, MSSIM= 0.972

Measurements on image #9850, 512x512 pixels¶

Corrupted by 7 % salt & pepper noise¶

Cover image #9850	Corrupted by salt & pepper 7 %
	PSNR= 17.34 dB, MSSIM= 0.182

Filtered by 3x3 full median	Filtered by 3x3 separable median	Filtered by 7x7 full median	Filtered by 7x7 separable median
PSNR= 35.80 dB, MSSIM= 0.968	PSNR= 36.23 dB, MSSIM= 0.970	PSNR= 29.13 dB, MSSIM= 0.865	PSNR= 29.14 dB, MSSIM= 0.866

Corrupted by 25 % salt & pepper noise¶

Cover image #9850	Corrupted by salt & pepper 25 %
	PSNR= 11.82 dB, MSSIM= 0.045

Filtered by 3x3 full median	Filtered by 3x3 separable median	Filtered by 7x7 full median	Filtered by 7x7 separable median
PSNR= 27.06 dB, MSSIM= 0.837	PSNR= 24.74 dB, MSSIM= 0.758	PSNR= 26.56 dB, MSSIM= 0.840	PSNR= 27.52 dB, MSSIM= 0.849