IMPROVING GIL-WERMAN ALGORITHM FOR RUNNING MIN AND MAX FILTERS

The current best bound on the number of comparison operations needed t o compute the running maximum or minimum over a p-element sliding data window is approximately three comparisons per output sample [1], [2], [3], [4]. This bound is probabilistic for the algorithms in [2], [3], [4] and is derived for their complexities on the average for independ ent, identically distributed (i.i.d.) input signals (uniformly i.i.d., in the case of the algorithm in [2]). The worst-case complexities of these algorithms are O(p). The worst-case complexity C-1 = 3 - 4/p com parisons per output sample for 1D signals is achieved in the Gil-Werma n algorithm [1]. In this correspondence we propose a modification of t he Gil-Werman algorithm with the same worst-case complexity but with a lower average complexity. A theoretical analysis shows that using the proposed modification the complexities of sliding Max or Min 1D and 2 D filters over i.i.d. signals are reduced to C-1 = 2.5 - 3.5/p + 1/p(2 ) and C-2 = 5 - 7/p + 2/p(2) comparisons per output sample on the aver age, respectively. Simulations confirm the theoretical results. Moreov er, experiments show that even for highly correlated data, namely, for real images the behavior of the algorithm remains the same as for i.i .d. signals.