On the computational complexity of multivariate median filters

Though the noise removal capability of multivariate median filters has been carefully investigated, a comprehensive analysis of their complexity is st ill missing. In this work, the complexity of the most commonly used multiva riate median filters is thoroughly analyzed. For each filter theoretical re sults are derived and validated against experimental data, proving that com putational complexity depends mainly on the approach adopted to sort multiv ariate samples. Algorithms based on marginal ordering are very fast, wherea s the use of an ordering scheme based on the aggregate sum of distances lea ds to very slow algorithms. An intermediate behavior is observed for filter s relying on reduced ordering. A fast algorithm for the implementation of t he vector median based on 1-norm is also described which significantly redu ces the complexity of this filter. (C) 1998 Elsevier Science B.V. All right s reserved.