Fast Median Filter over arbitrary datatypes

Summary

Median filter is one of most common filters in computer vision applications. Many variants of median filter that can be applied to arbitrary datatypes have been proposed throughout the years and a lot of progress is made to make it more efficient. I find all these research very fascinating and was not able to find a good source that aggregates and explains them all. So here it is now! The write up first introduces the baseline median filter (V1) then optimizes it to improve the per pixel median computation (V2) achieve 4.2 times speedup, enable multi threading (V3) gives an even more speedup of 16 times, finally an median filter over the ordinal transform of the image (V4) is discussed which gives 420 times speedup. Finally if the restriction of generalized datatypes is removed algorithm which enable an even greater speedup is discussed. Table of Contents: The main idea behind applying a median filter over a 2D image is to replace each pixel with the median of the values in a window around that pixel. The window can be square or circular. I will be focusing on a square window but it can be easily extended to a circular or hexagonal window by adapting how we add and remove pixels inside our window. I also use a 2D black & white image to avoid verbose code but can be easily modified for general multi channel images by applying the filter on each channel separately. Implementing the simplest possible median filter would be to loop over all pixels of the image and for each pixel we store the values in the surrounding window in a buffer. We then sort the values in the window and take the middle one as the median. If the window size is odd, that’s just the single middle element. If it’s even, we take the average of the two middle elements, for integer types this becomes the floor of that average because of integer division. This is how implementing it looks like: #include <algorithm> #include <vector> template <typename T> void median_filter_v1( const T* input, T* output,...