Some convergence properties of median filters

A median filter is a nonlinear digital filter which consists of a window of length that moves over a signal of finite length. For each input sample, the corresponding output point is the median of all samples in the window centered on that input sample. Any finite length, -level, signal that ends with constant regions of length will converge to an invariant signal in a finite number of passes of this median filter. Such an invariant signal is called a root. The concept of a root signal has proved to be crucial in understanding the properties of the median filter, root signals are to median filters what passband signals are to linear signals. In this paper, two results concerning the rate at which a signal is filtered to a root are developed. For a window of width 3, we derive a recursive formula to count the number of binary signals of length that converge to a root in exactly passes of a median filter. Also, we show that, given a window of width , any signal of length will converge to a root in at most passes of the filter.