I was curious about median computation here, since we learned that it was O(n^2) bruteforce and O(n) quickselect/median of medians, and found that it can be done in constant time (!?) in this paper, and can take advantage of vectorization.
184praveenb
It's crazy that they got constant time! I haven't read through the paper carefully but it looks like a key component of their technique is using the fact that pixels have a discrete range of possible values (e.g. 0-255) as they discuss in Section IV. Refutation of the Gil-Werman Lower Bound and section V.A Higher Precision on page 3.
I guess that's one way in which the median filter problem is different from the classic "median of an array" problem -- there are many more pixels, but the possible values are generally more limited, allowing for optimized computation.
alexkassil
I love the artistic effect of median filter that results in a flat / cell shading look. Filters have lots of artistic vlaue!
I was curious about median computation here, since we learned that it was O(n^2) bruteforce and O(n) quickselect/median of medians, and found that it can be done in constant time (!?) in this paper, and can take advantage of vectorization.
It's crazy that they got constant time! I haven't read through the paper carefully but it looks like a key component of their technique is using the fact that pixels have a discrete range of possible values (e.g. 0-255) as they discuss in Section IV. Refutation of the Gil-Werman Lower Bound and section V.A Higher Precision on page 3.
I guess that's one way in which the median filter problem is different from the classic "median of an array" problem -- there are many more pixels, but the possible values are generally more limited, allowing for optimized computation.
I love the artistic effect of median filter that results in a flat / cell shading look. Filters have lots of artistic vlaue!