A quick study of the overall jitter algorithm shows that most of the execution time is spent into pixel sorts and median filters. A detailed study of several methods to reduce the number of operations needed for these two specific steps has been done. The fast sorting problem has received a great deal of attention, and there are too many good methods to try to introduce them here. It is probably enough to know that the quicksort version used in the jitter implementation (pixel_qsort) is always at least twice faster as the local qsort() function found in the local standard C libraries on all tested Unix flavours.
Searching an array to find the median value is usually done by sorting out the array and then returning the central value. However, it is intuitive that more work is actually done than really needed. Instead of ending up with a sorted array, it should be possible to limit the amount of permutations needed to bring the median value in the center of the array with all values below being smaller than the median, and all values above being greater. Some permutation schemes are known for most used cases (3, 5, 7, 9, 25 values), but unfortunately there is no generic formula giving the best permutation scheme for any given number of values.
Figures11, 12 and 13 show the permutation networks needed to get the median value out in the minimal time. A permutation of two elements a and bis here defined as:
pix_swap(a,b)
begin
if a>b then swap(a,b)
else do nothing.
end
In these figures, a is always the above element, b the bottom one. Example: the permutations needed for 3 values (p0,p1,p2) are:
pix_swap(p0,p1) pix_swap(p1,p2) pix_swap(p0,p1)
In the more generic case of N elements in input, from which the median needs to be found, several algorithms have been reviewed. A complete survey of all methods, their results, an implementation for each algorithm in ANSI C and other pointers can be found from the following web site:
Fast median filtering: an ANSI C implementation
