The naive approach is to collect all the pixels from the surrounding area, sort them, and return the middle, median, value. Especially with web-based techniques this becomes computationally a very heavy operation, so I’ve used a couple of optimizations to boost up the performance.
First is that, when analyzing the image, only small changes to the sample are made. For the update e.g. taking one pixel step, it’s enough to remove the pixels from the left edge and add the new ones at right edge. This reduces the number of calculations in a general case from NxN to 2N:
The second optimization comes to the way of sorting the pixel data. Since the color data has discrete, integer values from a limited 0…255 range, I’ve chosen a histogram to do the sorting with, compare this to like for instance counting sort. And because the changes in data are small, I keep track of the position of the median.
The median’s position is updated on how data changes. There’s a couple of simple rules to follow:
If the added value is smaller than current median, the median should take a step downwards or to the previous bin.
Likewise if a removed value is smaller, the median should take a step upwards.
If the added or removed value is larger, it doesn’t affect the median position at all. Remember that at each step there are as many removed as added values.
In a general case the changes in median’s position remained small, even plus-minus zero in most cases. To map a rgb-coordinate from the 3D-color space to a histogram range of course has some disadvantages: several distinctly different colors might ‘hit’ the same histogram bin. To avoid these data collisions and also to have an even distribution in the histogram bins, I’ve first equalized the rgb-channels. And remember this is a greedy algorithm adaption, in cases when median is read from a bin with several entries, the average of these colors is returned.
Of course, if we can sort an array and pick a median, why not try picking up as well the k:th item in order. In the demo you can also set the value to pick to k:th element. If that is set to zero, the result is as picking the minimum, and with 1.0 like the maximum.