On efficient implementations of median filters in theory and in practice

Stoliński, S.; Grabowski, S.; Bieniecki, W.

Artykuł - szczegóły

Tytuł artykułu

On efficient implementations of median filters in theory and in practice

Autorzy

Stoliński S. , Grabowski S. , Bieniecki W.

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

Warianty tytułu

O efektywnych implementacjach filtrów medianowych w teorii i praktyce

Języki publikacji

Abstrakty

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.

Słowa kluczowe

image processing median filters data structures

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.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-AGH1-0022-0024