No icon

Asymptotically Optimal Algorithms for Running Max and Min Filters on Random Inputs

Asymptotically Optimal Algorithms for Running Max and Min Filters on Random Inputs

ABSTRACT :

Given a d-dimensional array of size nd and an integer p, the running max (or min) filter is the set of maximum (or minimum) elements within a d-dimensional sliding window of edge length p inside the array. This problem is useful in many signal processing applications such as pattern analysis, adaptive signal processing and morphological analysis.

The current best algorithm for computing the 1D max (or min) filter, due to Yuan and Atallah [IEEE Trans. Pattern Anal. Mach. Intell., 2011], uses 1+o(1) comparisons per sample in the worst case. As a direct consequence, the d-dimensional max (or min) filter can be computed in d+o(1) comparisons per sample, and the d-dimensional max and min filters can be computed simultaneously using 2d+o(1) comparisons per sample. Both bounds are the best known results for the corresponding problems, on both worst-case inputs and independently and identically distributed (i.i.d.) inputs.

In this paper, we first present an algorithm for computing d- dimensional max and min filters simultaneously on i.i.d. inputs that uses 1:5+o(1) expected comparisons per sample. This is the first algorithm for d-dimensional max and min filters (on i.i.d. inputs) that gets rid of the dependence on d in the dominating term, with respect to the input length n and the window length p, of the (expected) number of comparisons needed. It is also asymptotically optimal (when d is a fixed constant as n ! 1 and p ! 1). For the 1D case, our algorithm improves the previous best upper bound of 2 + o(1) to 1:5 + o(1). This result also matches the lower bound derived by Cormen, Leiserson, Rivest and Stein [Introduction to Algorithms, 2009]. As a by-product of our algorithm, we can also compute the d-dimensional max (or min) filter on i.i.d. inputs using 1 + o(1) expected comparisons per sample, which matches the bound for the 1D case.

We also consider the dynamic version of the problem of d- dimensional max and min filters simultaneously on i.i.d. inputs, motivated by the situation where we want to maintain the running filters after some changes in the input (d-dimensional) array. The most straightforward method is to recompute the whole running filters upon an update on the input using the algorithm in the static case. This incurs at least 1:5nd expected comparisons per update. In this paper, we design a linear-sized data structure that stores pre-computed information for efficient update using O(pd

Comment As:

Comment (0)