A fast method for computing the output of rank order filters within arbitrarily shaped windows

Rank order filters are used in a multitude of image processing tasks. Their application can range from simple preprocessing tasks which aim to reduce/remove noise, to more complex problems where such filters can be used to detect and segment image features. There is, therefore, a need to develop fast algorithms to compute the output of this class of filter. A number of methods for efficiently computing the output of specific rank order filters have been proposed [1]. For example, numerous fast algorithms exist that can be used for calculating the output of the median filter. Fast algorithms for calculating morphological erosions and dilations - which are also a special case of the more general rank order filter - have also been proposed. In this paper we present an extension of a recently introduced method for computing fast morphological operators to the more general case of rank order filters. Using our method, we are able to efficiently compute any rank, using any arbitrarily shaped window, such that it is possible to quickly compute the output of any rank order filter. We demonstrate the usefulness and efficiency of our technique by implementing a fast method for computing a recent generalisation of the morphological Hit-or-Miss Transform which makes it more robust in the presence of noise. We also compare the speed and efficiency of this routine with similar techniques that have been proposed in the literature.