Please use this identifier to cite or link to this item:
Title: Asymptotically optimal algorithms for running max and min filters on random inputs
Authors: Li, Minming
Liang, Hongyu
Liu, Shengxin
Poon, Chung Keung
Yuan, Hao
Keywords: Engineering::Electrical and electronic engineering
Issue Date: 2018
Source: Li, M., Liang, H., Liu, S., Poon, C. K., & Yuan, H. (2018). Asymptotically optimal algorithms for running max and min filters on random inputs. IEEE Transactions on Signal Processing, 66(13), 3421-3435. doi:10.1109/tsp.2018.2830309
Journal: IEEE Transactions on Signal Processing
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 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-12 p) expected comparisons per update.
ISSN: 1053-587X
DOI: 10.1109/TSP.2018.2830309
Rights: © 2018 IEEE. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Citations 20

Updated on Mar 2, 2021

Citations 20

Updated on Mar 5, 2021

Page view(s)

Updated on Jun 25, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.