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...
Saved in:
Main Authors: | , , , , |
---|---|
Other Authors: | |
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 |