On efficient implementations of median filters in theory and in practice

Abstract

The median filter, in its scalar and vector form, is a classic tool for suppressing impulse noise from images. In this paper we present a theoretical algorithm for worst-case optimized scalar median finding and an efficient implementation of the vector median filter (VMF). The former has not better complexity than two existing algorithms, but matches them for some relation between L and r, and is obtained using means which are novel in this context. The latter achievement is a simple practical idea which, for large enough masks, speeds up the standard (naive) implementation of VMF several times. We also presented results of a multi-threaded implementation, run on multicore machines. Filtr medianowy, w postaci skalarnej i wektorowej, jest klasycznym narzędziem usuwania szumu impulsowego z obrazów. W pracy przedstawiamy teoretyczny algorytm skalarnej filtracji medianowej, zoptymalizowany dla najgorszego przypadku, oraz efektywną implementację wektorowego filtru medianowego (VMF). Pierwszy z algorytmów nie osiąga lepszej złożoności niż dwa inne istniejące algorytmy dla tego problemu, ale wyrównuje ich złożoności dla pewnych L i r (odpowiednio: liczba poziomów jasności i promień maski), a środki użyte dla osiągnięcia tego celu stanowią w tym zastosowaniu nowość. Drugi z algorytmów to prosta idea praktyczna przyspieszająca, dla odpowiednio dużych masek, implementację standardową (naiwną) kilkakrotnie. Przedstawiliśmy również wyniki implementacji wielowątkowej, uruchomionej na maszynach wielordzeniowych.