Mathematical Complexity of Running Filters on Semi-Groups and Related Problems

This paper proves that the mathematical complexity of running filters on semi-groups is C(p)=3-(6/(p+1)) operations per sample, where p is the filter window. On other algebraic structures, the mathematical complexity of the filtering can be lower. Two such cases are investigated: the running filtering on max/min lattice and on additions group. They correspond to max/min and moving average filters. It is shown that the algorithms developed for semi-groups are of interest in such cases, too. Thus, the fastest deterministic algorithm for max/min filtering known so far is based on an algorithm for running filtering on semi-groups. First, an optimized version is proposed in this paper. Then, further improvement for data-dependent max/min algorithms is proposed. Finally, the case of moving average and exponential smoothing is investigated. Their implementation by using the algorithms for semi-groups is of lower complexity than the classical recursive implementation for the particular case of small size windows (p=3 and p=4).