TY - JOUR
T1 - Asymptotically Optimal Algorithms for Running Max and Min Filters on Random Inputs
AU - Li, Minming
AU - Liang, Hongyu
AU - Liu, Shengxin
AU - Poon, Chung Keung
AU - Yuan, Hao
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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 one-dimensional (1-D) max (or min) filter, due to the work of [H. Yuan and M. J. Atallah, "Running max/min filters using 1+o(1) comparisons per sample," IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 12, pp. 2544-2548, Dec. 2011], uses 1 + o(1) comparisons per sample in the worst case. As a direct consequence, the d-dimensional max (or min) filter (max and min filters, respectively) can be computed in d + o(1) (2d + o(1), respectively) comparisons per sample. 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 (on i.i.d. inputs) that gets rid of the dependence on d in the dominating term, with respect to n and p, of the (expected) number of comparisons needed. It is also asymptotically optimal (when d is a fixed constant as n → ∞ and p → ∞). We also consider the dynamic version of the problem of d -dimensional max and min filters simultaneously on i.i.d. inputs where we want to maintain the filters after changes in the input array. We design a linear-sized data structure that stores precomputed information for efficient update using O (pd-1 log2 p) expected comparisons per update.
AB - 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 one-dimensional (1-D) max (or min) filter, due to the work of [H. Yuan and M. J. Atallah, "Running max/min filters using 1+o(1) comparisons per sample," IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 12, pp. 2544-2548, Dec. 2011], uses 1 + o(1) comparisons per sample in the worst case. As a direct consequence, the d-dimensional max (or min) filter (max and min filters, respectively) can be computed in d + o(1) (2d + o(1), respectively) comparisons per sample. 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 (on i.i.d. inputs) that gets rid of the dependence on d in the dominating term, with respect to n and p, of the (expected) number of comparisons needed. It is also asymptotically optimal (when d is a fixed constant as n → ∞ and p → ∞). We also consider the dynamic version of the problem of d -dimensional max and min filters simultaneously on i.i.d. inputs where we want to maintain the filters after changes in the input array. We design a linear-sized data structure that stores precomputed information for efficient update using O (pd-1 log2 p) expected comparisons per update.
KW - comparisons per sample
KW - dilation
KW - erosion
KW - Mathematical morphology
KW - running filters
UR - http://www.scopus.com/inward/record.url?scp=85046336027&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85046336027&origin=recordpage
U2 - 10.1109/TSP.2018.2830309
DO - 10.1109/TSP.2018.2830309
M3 - RGC 21 - Publication in refereed journal
VL - 66
SP - 3421
EP - 3435
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
SN - 1053-587X
IS - 13
ER -