A fast Two-dimensional median filtering algorithm

所需积分/C币:9 2014-09-09 15:15:51 545KB PDF
收藏 收藏

A fast Two-dimensional median filtering algorithm Thomas S. Huang , A fast Two-dimensional median filtering algorithm, 1979.下载地址:LinJM
HUANG et al.: TWO-DIMENSIONAL MEDIAN FILTERING ALGORITHM 15 Fig. 1. Images before filtering, (a)Girl, original. (b) Girl, with BSC noise.(c)Girl, with Gaussian noise, (d)Airport, original.(e)Air port, with BSC noise. (f)Airport, with Gaussian noise Fig. 2. The six images of Fig. l after 3 X 3 median filtering. 己7c 600 Ai rpor, BSC 300 200 l00 Hi s togram Method 20 120 140 80 indow size ( pels) Fig. 3. Number of comparisons por window plotted against window size. The images filtered were girl with BSC noise and ith Bsc 16 IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-27, NO. 1, FEBRUARY 1979 6c0 Airport, BSc Girl bsc 20|21 14户 Fig 4. Computer time per image plotted against window size. The images filtered were girl with BSC noise and airport with BSC noisc TABLE I NUMBER OF COMPARISONS PER WINDOW(GIRL-IMAGES 1-3 ndo t Method Girl G rI BSC Russia Gaussian 14.614,7 16.37130.691277C123.34 7x7 1899125,07249,2 237,7 Sx 21.e9 25,65 13×1329.4829.46295592.1987.56792.98 TABLE IL COMPUTER TIME IN SECONDS (GIRL-IMAGES 1-3 ir.dow si stog,am Girl Gir? Gir Gi Gauss iar BSC Ga ussian 5×5 3727 65.6833,365,0 9K9 749 76,2 75.9108741053.3 11x1 86·5 3X『3 97.3 HUANG et al. TWO-DIMENSIONAL MEDIAN FILTERING ALGORITHM 17 TABLE III NUMBER OF COMPARISONS PER WINDOW(AIRPORT-IMAGES 4-6 Window Size Hi stog ram QuIcksort Me thod Airport A rport AI r Airport Ai rport Al t BSC Gaussian Gaussi an 45.54 1106 1032 0.47 14.95 55 12426123·28 7x7 l8。10 18.15 239.24 36.83233.03 9x9 21。53 388.35 378.72 25。23 574.01571.0955937 3x1328.95 8c8,0030286 775 TABLE IV COMPUTER TIME IN SECONDS(AIRPORT--IMAGES 4-6) His Method At rport AIrport Ai rport Gauss i an BsC Gaussian 3×350.0 69 156·5 1421 5x3 山4.3 42 7x3 42.3 5×556,4 59。5 378.3 339.1 368.5 76.1 7x7675 67.4 833 6279 x 9 780 96,1 9955 1083.3 8 1·110s0 13x131010 121.8 time per image are measured. The results are listed in'yableshere per window (i.e, per output point) and the computational I-IV. The results for the two images with bsC noise are also n X n=square window size or m X n=rectangular window plotted in Figs. 3 and 4. As we can see, the histogram me thod size much faster than the Quicksort method. according to po= probability of d being zero in one picture these results, for median filtering with an n X n window, the computer time required for the first is approximately o(n), and and for the second o(n ). Some of the nonsquare rectangular d horizontally adjacent pcl gray levcl diffcrcnce of the windows are also used. For an m X n window(moving hori median filtered picture zontally), the computer time required is approximately o(n) d=the average of absolute value of d I. ANALYSIS Proof: From the procedure running mdn in the pidgin We show that for the fast median filtering algorithm, the Algol algorithm, we see that 1) exactly 2n comparisons are average number of comparisons per window is approximately made in the for statement, and 2)number of comparisons and d are related as shown in the following table for the if 2n+|d|+1.5+0.5g statement 18 IEEE TRANSACTIONS ON ACOUSTICS. SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-27, NO. 1. FEBRUARY 1979 d number of comparisons Therefore, c is loosely upper bounded by 2n+Id|+2 and Cn+ t 15. clearly, this algorithm tage of the fact that for typical images the valuc of is small. The value of ld is less than 10 for the images we 2 used. Hence, approximately only(2n+10) comparisons are average. Equation (l)agrees well with the ex perimental resuits reported in Section III Note: This analysis ignores the comparisons made in finding the median of the first window in each line. That, on average, amounts to mdn/q-m)comparisons per window for an q X r image, an mX n filtering window and mdn being the 3 average median of the first windows in each line. This addi- tional number of comparisons can be significant compared to (1) for large number of gray levels and small image size in the assuming d is symmetrically distributed (confirmed in the horizontal direction. This effect can be easily eliminated by experiment for the chosen images), we then have the table applying the proposed algorithm vertically at the end of each line and scanning altemate lines in reverse direction Id average number of comparisons REFERENCES 0 []J.W. Tukey, Exploratory Data Analysis(preliminary ed. ) Read 25 ing, MA: Addison-Wesley, 1971 [2]-, Exploratory Data Analysis. Reading, MA: Addison-Wesley, 3.5 1977 4.5 [3 L.R. Rabiner, M.R. Sambur, and C E Schmidt, "Applications of a nonlinear smoothing algorithm to speech processing, IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-23, pp 552 557,Dec.1975 [4]N. S. Jayant, "Average and median-based smoothing techniques Let c be the average number of comparisons and pi be th for improving digital speech quality in the presence of transmis- probability that!d =i, i-0, 1, '., 255.Then sion errors, ,IEEE Trans. Commun., Vol. COM-24, pp. 1043-1045 Sept. 1976 15] W.K. Pratt, "Median filtering, in Semiannual Report, Image Pro- C=2p+2.5p1+3p2+45p3+……+256.5p255+2n cessing Institutc, Univ. of Southern California, Scpt. 1975, pp 116-123 [6] B. R. Frieden, "A new restoring algorithm for the preferential =0.5po+∑(+15)p;+2 enhancement of edge gradients, >J. Opt. Soc. Amer,, vol. 66 =0 pp.280-283,1976 [7 s.G. Tyan," Fixed points of running medians" (unpublished report), Dep. Elec. EngI. Electrophysics, Polytechnic Inst. of =05po+1.5+∑ip+2 New York, Brooklyn, NY, 1977 i=0 [8]B. Justusson, "Statistical properties of median filters in signal and image processing?",(unpublished report), Math. Inst, Royal =0.5p0+15+|dl+2n. inst, of Technology, Stockholm, Sweden, Dec 1977 [9] A. V. Ahe, 3. E. Hopcroft, and J, D. Ullman, The Design and Analysis of Computer Algorithms. Reading, MA: Addison- Q.E.D Wesley, 1974, p. 101

试读 6P A fast Two-dimensional median filtering algorithm
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    • 分享宗师

    关注 私信 TA的资源
    A fast Two-dimensional median filtering algorithm 9积分/C币 立即下载
    A fast Two-dimensional median filtering algorithm第1页
    A fast Two-dimensional median filtering algorithm第2页


    9积分/C币 立即下载 >