On the computational complexity of multivariate median filters

Though the noise removal capability of multivariatemedianfilters has been carefully investigated, a comprehensive analysis of their complexity is still missing. In this work, the complexity of the most commonly used multivariatemedianfilters is thoroughly analyzed. For each filter theoretical results are derived and validated against experimental data, proving that computationalcomplexity depends mainly on the approach adopted to sort multivariate samples. Algorithms based on marginal ordering are very fast, whereas the use of an ordering scheme based on the aggregate sum of distances leads to very slow algorithms. An intermediate behavior is observed for filters relying on reduced ordering. A fast algorithm for the implementation of the vector median based on 1-norm is also described which significantly reduces the complexity of this filter