README for pgmmedian 1.0 Description ----------- pgmmedian is a pbmplus/netpbm program that applies a median filter to an image to reduce noise such as impulse noise. It does not try to characterize the noise to perform a better noise reduction. Installation ------------ Copy C source and man page to your {pbmplus|netpbm}/pgm directory and then modify the Imakefile to include pgmmedian in MAN1, SRCS, OBJS, BINS and add the target line NormalPbmplusProgramTarget(pgmmedian) Then run xmkmf and make. Information about the algorithms -------------------------------- While implementing this median filter, I tried many types of sorts and select k'th value routines to find the median value. I eventually chose to implement it with a histogram sort and a select as the histogram sort is fastest method in many cases especially with larger mask sizes and when the histogram sort is not the fastest, select was nearly the fastest and easier to implement than the other method I created. References for both of these are given in the man page and source code. All regular sorting methods (quicksort, insertion, shell, merge) were too slow. I tried the select k'th from Sedgewick's book and the CACM 489 one and found 489 to be faster. I also tried the algorithm "Median Finding on a 3 x 3 Grid" from Graphics Gems. The histogram sort still beat it and beat the 5x5 version given in the appendix. For combinations of small mask sizes and small maxvals the histogram sort is always fastest, but there is a point where it becomes much slower as the maxval gets larger because you have to compare bins that are farther and farther apart on average. That is why I use a cutoff value to decide between using a histogram sort or select. See the timing tables below to see how poorly a histogram sort can perform for a 3x3 mask with maxval of 64k. I modified the histogram sort to them use a linked list of bins rather than allocating a column of 64k bins. This way you only have to go to the next bin in the linked list, rather than possibly go through 10,000 bins to find the median. The added overhead of having to insert and delete bins from the linked list was a little steep and only saves time over the standard histogram sort when the maxval is 64k. And when the mask size is small, select still beats it, so I decided not to also implement it in the final version. I also designed my own method of finding the median that sorts each column, then merge sorts the columns together to find the median. Then as the mask moves horizontally across the image, you already have the columes sorted. You have to remove the proper elements from the left most column and merge in the sorted values from the right most column. It used a shell sort for the sorting and binary searches to find and replace values from an array of pointers, etc. It's nearly always 5-20% faster than select, but quite a bit more messy to debug when something goes wrong, so I decided to stick with select for those cases where it can beat the histogram sort. This method and the histogram sort were the only methods I used that reused the data from the previous mask. The following timings are from a Sun IPC and Sparc 20. The row of numbers across the top is the result of (maxval/((cols X rows) -1) ). The second row of numbers is the maxval of the image used for that run. select - select from CACM #489 mysort - the sort I devised described above hist - histogram sort hist2 - histogram sort using linked lists Image size of 512x512 Sun Sparc IPC ------------- Mask size of 3x3 ---------------- 8 128 256 512 1024 2048 4096 8192 511 1k 2k 4k 8k 16k 32k 64k Ver14e 13.5 13.8 15.4 16.2 16.7 17.9 19.1 19.7 Ver19m 11.7 12.0 13.5 14.3 14.9 16.1 17.3 18.1 Ver20j 14.2 14.8 16.4 18.3 20.0 24.0 31.0 42.8 Mask size of 5x5 ---------------- 24 85 170 341 682 1365 2730 511 1k 2k 4k 8k 16k 32k 64k Ver14e 21.3 21.8 23.2 24.1 24.7 25.7 26.8 27.6 Ver19m 18.1 18.5 20.0 20.9 21.4 22.7 23.9 24.4 Ver20b 14.0 15.5 18.9 23.9 32.8 51.4 89.6 171.0 Ver20j 32.4 33.0 34.9 36.5 38.4 42.6 49.2 60.7 Mask size of 9x9 ---------------- 80 25 51 102 204 409 819 511 1k 2k 4k 8k 16k 32k 64k Ver14e 45.2 45.6 47.2 48.1 48.6 49.4 50.8 51.4 Ver19m 41.6 42.0 43.4 44.3 44.8 46.1 47.4 47.8 Ver20b 14.0 15.5 18.9 23.9 32.8 51.4 89.6 171.0 Ver20j 32.4 33.0 34.9 36.5 38.4 42.6 49.2 60.7 Mask size of 13x13 ------------------ 168 12 24 48 97 195 390 511 1k 2k 4k 8k 16k 32k 64k Ver14e 81.4 81.5 83.3 84.3 84.5 85.2 86.8 95.2 Ver19m 78.7 79.1 80.4 81.4 82.0 83.4 84.2 84.5 Ver20b 16.9 18.2 21.0 25.8 33.4 49.6 82.4 150.5 Ver20j 44.4 46.1 47.2 48.5 50.4 54.3 60.8 72.0 Mask size of 17x17 ------------------ 288 7 14 28 56 113 227 511 1k 2k 4k 8k 16k 32k 64k Ver14e 129.7 129.9 131.8 132.5 133.0 133.2 134.6 146.7 Ver19m 133.4 133.8 135.1 136.1 136.5 137.9 139.0 138.9 Ver20b 19.8 20.9 23.8 28.1 35.0 49.3 78.8 138.9 Ver20j 55.7 56.1 57.1 58.0 59.6 66.7 72.9 84.0 Mask size of 25x25 ------------------ 624 3 6 13 26 52 105 511 1k 2k 4k 8k 16k 32k 64k Ver14e 269.0 269.9 270.7 272.8 273.2 271.9 273.5 297.6 Ver19m 271.1 271.5 273.0 274.1 274.6 275.7 276.8 276.2 Ver20b 27.3 28.3 30.9 34.6 40.2 52.7 77.7 127.5 Ver20j 65.7 66.4 68.1 69.5 71.3 75.9 82.0 92.5 Mask size of 35x35 ------------------ 1224 3 6 13 26 53 511 1k 2k 4k 8k 16k 32k 64k Ver14e 511.7 512.0 514.1 512.3 514.9 514.1 514.8 559.2 Ver19m 515.7 516.1 517.7 518.5 519.0 520.3 521.5 522.4 Ver20b 34.7 35.6 38.2 41.0 46.1 56.9 77.2 117.9 Ver20j 72.0 72.6 74.2 75.7 77.9 82.3 88.2 98.7 Sun Sparc 20 model 71 --------------------- Mask size of 3x3 ---------------- 8 128 256 512 1024 2048 4096 8192 511 1k 2k 4k 8k 16k 32k 64k select 2.8 2.9 3.3 3.6 3.6 3.9 4.2 4.5 mysort 2.4 2.4 2.7 2.9 2.9 3.2 3.4 3.7 hist 1.7 2.1 2.8 4.0 6.2 10.7 19.7 37.7 hist2 2.5 2.6 3.0 3.2 3.4 4.0 4.8 6.0 Mask size of 5x5 ---------------- 24 85 170 341 682 1365 2730 511 1k 2k 4k 8k 16k 32k 64k select 4.6 4.7 5.0 5.4 5.4 5.7 6.0 6.1 mysort 3.7 3.8 4.1 4.4 4.5 4.7 4.9 5.1 hist 1.9 2.2 2.8 3.9 5.7 9.3 16.6 31.0 hist2 3.7 3.7 4.1 4.3 4.5 5.0 5.7 7.0 Mask size of 9x9 ---------------- 80 25 51 102 204 409 819 511 1k 2k 4k 8k 16k 32k 64k select 10.4 10.5 11.0 11.1 11.3 11.6 11.9 12.1 mysort 8.9 8.9 9.3 9.5 9.5 9.8 10.0 10.2 hist 2.2 2.5 3.1 3.9 5.4 8.4 14.0 25.4 hist2 6.0 6.1 6.4 6.6 6.9 7.4 8.1 9.5 Mask size of 13x13 ------------------ 168 12 24 48 97 195 390 511 1k 2k 4k 8k 16k 32k 64k select 20.0 19.8 20.2 20.8 20.5 20.7 21.2 21.5 mysort 17.1 17.1 17.5 17.7 17.7 18.1 18.2 18.3 hist 2.7 2.9 3.5 4.2 5.5 8.2 13.0 22.4 hist2 8.2 8.3 8.7 9.0 9.1 9.7 10.6 11.8 Mask size of 17x17 ------------------ 288 7 14 28 56 113 227 511 1k 2k 4k 8k 16k 32k 64k select 32.6 32.7 33.2 33.7 33.4 33.7 34.1 34.4 mysort 28.5 28.5 30.0 29.0 29.1 29.3 29.6 29.6 hist 3.4 3.6 4.1 4.7 5.8 8.2 12.8 20.9 hist2 10.3 10.4 12.2 11.0 11.3 11.7 12.5 13.6 Mask size of 25x25 ------------------ 624 3 6 13 26 52 105 511 1k 2k 4k 8k 16k 32k 64k select 69.6 69.7 70.5 70.4 70.8 70.8 70.9 71.2 mysort 60.2 60.2 60.8 60.7 60.7 61.0 61.3 61.4 hist 5.7 5.5 6.0 6.8 7.5 9.6 13.8 20.1 hist2 13.4 13.5 13.7 14.6 14.3 14.8 15.6 16.7 Mask size of 35x35 ------------------ 1224 3 6 13 26 53 511 1k 2k 4k 8k 16k 32k 64k select 137.7 136.6 138.6 137.3 137.9 137.9 138.2 138.5 mysort 230.0 114.9 115.6 115.4 115.7 115.8 116.0 116.1 hist 7.3 7.5 7.9 9.8 9.2 10.7 14.0 19.3 hist2 15.1 15.3 17.5 15.8 19.1 16.4 17.2 18.6 Send all questions/comments/bugs to me at burns@cac.psu.edu. - Mike ---------------------------------------------------------------------------- Mike Burns UNIX Systems Group burns@cac.psu.edu Center for Academic Computing (814) 863-5606 The Pennsylvania State University