Changes between Version 9 and Version 10 of libpipi/research/filters Tweet

Timestamp:

08/22/2008 12:19:07 AM (16 years ago)

Author:

Sam Hocevar

Comment:

--

libpipi/research/filters

@@ -27 +27 @@
 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 applying a 5×0 filter and a 0×5 filter instead of a 5×5 filter, so there is no real point in studying this specific optimisation.
 
-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.
+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²) where r is the filter radius and n = (2r+1)². Improving on the sorting 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.
 
 The third way to optimise a median filter is by accounting for the size of neighbourhood changes in raster scan order: usually only a few values are removed from and added to the list of neighbours. This becomes promising with large kernel sizes, and efficient algorithms exist that handle this case in 1D at least ![2].
 
-Methods for O(1) median filters have recently been discovered [3]. However, they rely on histograms, which only works well when the input data consists of 8-bit integers. Since libpipi does most of its computations using 32-bit floats, such techniques are of limited usefulness.
+Methods for O(r) or O(log(r)) median filters have been commonly used so far. Even an O(1) method has recently been discovered [3]. However, they all seem to rely on histograms, which only works well when the input data consists of 8-bit integers. Since libpipi does most of its computations using 32-bit floats, such techniques are of limited usefulness.
 
 === References ===