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$).
展开▼
机译：本文证明了在半组上运行过滤器的数学复杂度是每个样本$ C（p）= 3-（6 /（p + 1））$个操作，其中$ p $是过滤器窗口。在其他代数结构上，滤波的数学复杂度可能较低。研究了两个这样的情况：在最大/最小晶格上和在加法组上的运行过滤。它们对应于最大/最小和移动平均滤波器。结果表明，在这种情况下，为半群开发的算法也很有趣。因此，迄今为止已知的用于最大/最小过滤的最快的确定性算法是基于在半组上运行过滤的算法。首先，提出了一种优化版本。然后，提出了对数据相关的最大/最小算法的进一步改进。最后，研究了移动平均和指数平滑的情况。对于小窗口（$ p = 3 $和$ p = 4 $）的特殊情况，使用半组算法实现的复杂度要比经典递归实现低。
展开▼
