Computing 2-Dimensional Min, Median and Max Filters

Fast algorithms to compute min, median, max or any other order statistic filter transforms are described and lower bounds for their computation are shown. The algorithms take constant time per pixel to compute min or max filters and polylog time per pixel, in the size of the filter, to compute the median filter. 1 Introduction Order filters are widely used as an effective tool for reducing certain types of noise and periodic interference patterns in signals and images without severely degrading the signal [3]. One of the more useful properties of the median filter is that it many situations it doesn't blur edges and monotone changes in the signal but it cleans up sporadic noise. The min and max filters are the primitive operations for all of the so called morphological filters [4, 6]. In this paper we describe fast algorithms to compute min, median, max or any other order statistic filter transforms and show lower bounds for their computation. Let A[1::n; 1::n] be a two dimensional ar..