On efficient implementations of median filters in theory and in practice

• Autorzy: Stoliński S. , Grabowski S. , Bieniecki W.

Warianty tytułu

PL

O efektywnych implementacjach filtrów medianowych w teorii i praktyce

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

image processing; median filters; data structures

PL

przetwarzanie obrazu; filtry medianowe; struktury danych

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 3/1
• Strony: 1021--1032
• Opis fizyczny: Bibliogr. 18 poz., tab.

Twórcy

autor

Stoliński S.

• Computer Engineering Department, Technical University of Łódź

autor

Grabowski S.

• Computer Engineering Department, Technical University of Łódź

autor

Bieniecki W.

• Computer Engineering Department, Technical University of Łódź

Bibliografia

• [1] Astola J., Haavisto P., Neuvo Y., Vector median fliers. Proceedings of the IEEE, vol. 78, no. 4, 1990, 678-89.
• [2] Blum M, Flyod R. W., Pratt V., Rivest R., Tarjan R., Time Bounds for Selection. J. Comput. Syst. Sei., vol. 7, no. 4, 1973, 448-61.
• [3] Dor D., Zwick U., Selecting the Median. SODA 1995, 28-37.
• [4] van Emde Boas P., Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space. Inf. Process. Lett., vol. 6, no. 3, 1977, 80-82.
• [5] Frederickson G.N., Johnson D.B., Generalized Selection and Ranking. (Preliminary Version). STOC 1980, 420-28.
• [6] Gagie Т., Puglisi S.J., Turpin A., Range Quantile Queries: Another Virtue of Wavelet Trees. The Computing Research Repository (CoRR), CoRR abs/0902.0133, v5 (May 21, 2009), available at http://arxiv.org/abs/0903.4726.
• [7] Gil J., Werman M., Computing 2-D Min, Median, and Max Filters. IEEE Trans. Pattern Anal. Machine Intell, vol. 15, no. 5, 1993, 504-507.
• [8] Grabowski S., Bieniecki W., A two-pass median-like filter for impulse noise removal in multichannel images. III Konferencja „Komputerowe Systemy Rozpoznawania" KOSYR 2003 (3r Conf. on Computer Recognition Systems), Miłków k/Karpacza, 2003, 195-200.
• [9] Harter R., comp.programming forum, 2004, available at http://coding.derkeiler.com/Archive/General/comp .programming/2004-10/0289 .html.
• [10] Harter R., comp.programming forum, 2004, available at http://coding.derkeiler.com/Archive/General/comp.programming/2004-10/0664.html.
• [11] Huang Т., Yang G. L, Tang, G. Y: A Fast Two-Dimensional Median Filtering Algorithm. IEEE Trans. Acoust, Speech, Signal Processing, vol. 27, no. 1, 1979, 13-18.
• [12] Navarro G., Mäkinen V., Compressed full-text indexes. ACM Comput. Surv., 39(1), 2007.
• [13] Perreault, S., Hebert, P., Median Filtering in Constant Time. IEEE Trans. Image Processing, vol. 16, no. 9, 2007, 2389-2394.
• [14] Regazzoni C. S., Teschioni A., A New Approach to Vector Median Filtering Based on Space Filling Curves. IEEE Transactions on Image Processing, vol. 6, no. 7, 1997, 1025-1037.
• [15] Smółka В., Chydziński A., Fast detection and impulsive noise removal in color images. Real-Ti-me Imaging, vol. 11, no. 5-6, 2005, 389-02.
• [16] Smółka В., Szczepański M., Plataniotis K.N., Venetsanopoulos A.N., New technique of impulse noise suppression in color images. II Konferencja „Komputerowe Systemy Rozpoznawania" KOSYR 2001 (2nd Conf. on Computer Recognition Systems), Miłków k/Karpacza, 2001, 225-232.
• [17] Trahanias P.E., Venetsanapoulos A., Vector directional filters: A new class of multichannel image processing filters. IEEE Transactions on Image Processing, vol. 2, no. 4, 1993, 528-534.
• [18] Weiss В., Fast Median and Bilateral Filtering. ACM Transactions on Graphics (TOG), vol. 25, no. 3, 2006, 519-526.