Asymptotically optimal algorithms for running max and min filters on random inputs

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, adapti...

Full description

Saved in:
Bibliographic Details
Main Authors: Li, Minming, Liang, Hongyu, Liu, Shengxin, Poon, Chung Keung, Yuan, Hao
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/139417
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-139417
record_format dspace
spelling sg-ntu-dr.10356-1394172020-05-19T07:22:30Z Asymptotically optimal algorithms for running max and min filters on random inputs Li, Minming Liang, Hongyu Liu, Shengxin Poon, Chung Keung Yuan, Hao School of Physical and Mathematical Sciences Engineering::Electrical and electronic engineering Mathematical Morphology Erosion 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. 2020-05-19T07:22:30Z 2020-05-19T07:22:30Z 2018 Journal Article 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 1053-587X https://hdl.handle.net/10356/139417 10.1109/TSP.2018.2830309 2-s2.0-85046336027 13 66 3421 3435 en IEEE Transactions on Signal Processing © 2018 IEEE. All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Engineering::Electrical and electronic engineering
Mathematical Morphology
Erosion
spellingShingle Engineering::Electrical and electronic engineering
Mathematical Morphology
Erosion
Li, Minming
Liang, Hongyu
Liu, Shengxin
Poon, Chung Keung
Yuan, Hao
Asymptotically optimal algorithms for running max and min filters on random inputs
description 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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Li, Minming
Liang, Hongyu
Liu, Shengxin
Poon, Chung Keung
Yuan, Hao
format Article
author Li, Minming
Liang, Hongyu
Liu, Shengxin
Poon, Chung Keung
Yuan, Hao
author_sort Li, Minming
title Asymptotically optimal algorithms for running max and min filters on random inputs
title_short Asymptotically optimal algorithms for running max and min filters on random inputs
title_full Asymptotically optimal algorithms for running max and min filters on random inputs
title_fullStr Asymptotically optimal algorithms for running max and min filters on random inputs
title_full_unstemmed Asymptotically optimal algorithms for running max and min filters on random inputs
title_sort asymptotically optimal algorithms for running max and min filters on random inputs
publishDate 2020
url https://hdl.handle.net/10356/139417
_version_ 1681056182969565184