Changes between Version 5 and Version 6 of libpipi/research/filters
- Timestamp:
- 08/21/2008 01:38:22 PM (16 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
libpipi/research/filters
v5 v6 28 28 There are several ways to optimise a median filter. 29 29 30 Random links for now: 30 The first idea is an approximation, based upon the assumption that the median of subset medians is close to the median of the whole set. It can already be simulated by doing `--median 5x0 --median 0x5` in `pipi`, so there is no real point in studying this specific optimisation. 31 32 The second idea is to optimise the median selection. The most naive method is to bubble-sort the neighbourhood values and select the middle point, which has complexity O(n²). Improving on the sort algorithm by using eg. heapsort or quicksort, reduces the complexity to O(n.log2(n)). But since we’re only interested in the median and not in ordering the rest of the data, we can use an efficient median selection algorithm. This operation can be done in fewer than 3n tests ![1] but the practical implementation is extremely complex. 33 34 === Links === 35 31 36 * [http://coding.derkeiler.com/Archive/General/comp.programming/2004-10/0289.html Sliding median filter] 32 37 * [http://iris.usc.edu/Vision-Notes/bibliography/twod268.html A shitload of papers about median filtering and its derivatives] 38 39 === References === 40 41 * ![1] Uri Zwick, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.2770 Selecting the median], In Proceedings of the 6rd Annual ACM-SIAM Symposium on Discrete Algorithms (1995) 33 42 34 43 = Dilate / erode = … … 54 63 }}} 55 64 56 === References ===65 === Links === 57 66 58 67 * [http://ostermiller.org/dilate_and_erode.html Efficiently Implementing Dilate and Erode Image Functions]
