Optimal algorithms for max/min filtering

This paper proposes an approach for the derivation of optimal algorithms for max/min filtering. The transfer matrix for the input-output description of max/min filters is introduced. In connection with the filter realization problem, the decomposition of transfer matrices is analyzed. The decomposition is based on two properties, namely chaining and weak superposition. Matrix decomposition is further used to derive flow-charts for max/min computation. Optimization criteria with respect to the computational complexity (comparisons/sample) of the derived algorithms are defined. Two examples are presented. For certain window sizes, the derived algorithms perform in less than log₂n comparisons per sample