The running maximum-minimum (max-min) filter computes the maxima and minima over running windows of size w. This filter has numerous applications in signal processing and time series analysis. We present an easy-to-implement online algorithm requiring no more than 3 comparisons per element, in the worst case. Comparatively, no algorithm is known to compute the running maximum (or minimum) filter in 1.5 comparisons per element, in the worst case. Our algorithm has reduced latency and memory usage.
@cite_2 proposed a fast algorithm based on anchors. They do not improve on the number of comparisons per element. For window sizes ranging from 10 to 30 and data values ranging from 0 to 255, their implementation has a running time lower than their implementation by as much as 30 implementation by as much as 15 than 15, but is outperformed similarly for smaller window sizes, and both are comparable for a window size equals to 15. The Droogenbroeck-Buckley filter pseudocode alone requires a full page compared to a few lines for algorithm. Their experiments did not consider window sizes beyond @math nor arbitrary floating point data values.
@cite_2
2047293099
Several efficient algorithms for computing erosions and openings have been proposed recently. They improve on van Herk's algorithm in terms of number of comparisons for large structuring elements. In this paper we introduce a theoretical framework of anchors that aims at a better understanding of the process involved in the computation of erosions and openings. It is shown that the knowledge of opening anchors of a signal f is sufficient to perform both the erosion and the opening of f. Then we propose an algorithm for one-dimensional erosions and openings which exploits opening anchors. This algorithm improves on the fastest algorithms available in literature by approximately 30 in terms of computation speed, for a range of structuring element sizes and image contents.