{"id":3372,"date":"2019-07-15T11:55:36","date_gmt":"2019-07-15T15:55:36","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=3372"},"modified":"2019-11-01T22:46:22","modified_gmt":"2019-11-02T02:46:22","slug":"the-curious-case-of-ordfilt2-performance","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2019\/07\/15\/the-curious-case-of-ordfilt2-performance\/","title":{"rendered":"The curious case of ordfilt2 performance"},"content":{"rendered":"

For today's post, I'd like to welcome guest author Kushagr Gupta, a developer on the Image Processing Toolbox team. -Steve<\/i><\/p>

The Image Processing Toolbox function ordfilt2<\/tt> can be used to perform various types of 2-D statistical filtering, including minimum or maximum filtering and median filtering. A straightforward implementation of this function is expected to scale with $O(r^2)$, where $r$ is the width of the window (assuming a square window). To compute each output pixel, we have to select the $k$-th largest value from the set of $r^2$ input image pixels, which can be done in $O(r^2)$ time with an algorithm such as quick-select.<\/p>

The function ordfilt2<\/tt>, however, does better than that; it scales with $O\\left(r\\right)$complexity. That's because ordfilt2<\/tt> uses a sliding window-based histogram approach to filter the data. When the algorithm moves from one input image pixel to the next, only part of the histogram needs to be updated. (Reference: Huang, T.S., Yang, G.J., and Yang, G.Y., \"A fast two-dimensional median filtering algorithm,\" IEEE transactions on Acoustics, Speech and Signal Processing<\/i>, Vol ASSP 27, No. 1, February 1979.)<\/p>

\"\" <\/p>

As shown in the figure above, r additions and r subtractions need to be carried out for updating the histogram. Computing the output pixel from the histogram doesn't depend on the window size, and so the overall complexity is $O(r)$.<\/p>

We recently received an interesting tech support case related to performance of ordfilt2<\/tt> for uint16 random input data. One of our customers reported the time taken to filter an image with a smaller window size was higher<\/b> than the time taken to process the same image with a relatively larger window size.<\/p>

Was this just a noisy observation? Was this reproducible? Was this a bug in our implementation?<\/p>

We investigated?<\/p>

The customer was generous enough to give us reproduction code. And, the behavior was indeed reproducible! (Many, many times!). What was the explanation?<\/p>

Here are the reproduction steps:<\/p>

Im = im2uint16(rand(1e3));\r\nn = [7 9 11 13 15 21 25 31 35 41 49 51 57 65 73];\r\nt = zeros(length(n),1);\r\nfor<\/span> id=1:length(n)\r\n   t(id) = timeit(@() ordfilt2(Im,ceil(n(id)^2*0.5),...<\/span>\r\n       true(n(id))));\r\nend<\/span>\r\n\r\nplot(n,t)\r\ngrid on<\/span>\r\ntitle('ordfilt2 performance curve (uint16)'<\/span>)\r\nxlabel('window size'<\/span>)\r\nylabel('Time (s)'<\/span>)\r\n<\/pre>\"\" 
A puzzling aspect of this case was that the performance behavior was observed only for random input data and not for real-world images. Here is a comparison:<\/p>
Im1 = im2uint16(imresize(imread('coins.png'<\/span>),[500 500]));\r\nIm2 = im2uint16(rand(500));\r\nn = [11 15 21 27 31 35 41 49 51];\r\ntreal = zeros(length(n),1);\r\ntrand = zeros(length(n),1);\r\nfor<\/span> id=1:length(n)\r\n   treal(id) = timeit(@() ordfilt2(Im1,ceil(n(id)^2*0.5),...<\/span>\r\n       true(n(id))));\r\n   trand(id) = timeit(@() ordfilt2(Im2,ceil(n(id)^2*0.5),...<\/span>\r\n       true(n(id))));\r\nend<\/span>\r\n\r\nplot(n,treal)\r\ngrid on<\/span>\r\nhold on<\/span>\r\nplot(n,trand)\r\nlegend('Real World Image'<\/span>,'Random Image'<\/span>)\r\ntitle('ordfilt2 performance comparison'<\/span>)\r\nxlabel('window size'<\/span>)\r\nylabel('Time (s)'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
We also observed that the the performance behavior was not reproducible for uint8 random images. Instead, the algorithm's performance scaled linearly with the window size, as expected.<\/p>
Im = im2uint8(rand(1e3));\r\nn = [7 9 11 13 15 21 25 31 35 41 49 51 57 65 73];\r\nt = zeros(length(n),1);\r\nfor<\/span> id=1:length(n)\r\n   t(id) = timeit(@() ordfilt2(Im,ceil(n(id)^2*0.5),...<\/span>\r\n       true(n(id))));\r\nend<\/span>\r\n\r\nplot(n,t)\r\ngrid on<\/span>\r\ntitle('ordfilt2 performance curve (uint8)'<\/span>)\r\nxlabel('window size'<\/span>)\r\nylabel('Time (s)'<\/span>)\r\n<\/pre>\"\" 
To understand what was going on, it became essential to dig deeper into the inner workings of the underlying algorithm.<\/p>
As it turns out, while using the sliding window histogram approach, the algorithm also keeps track of the running sum of the histogram so that it does not need to be computed for each pixel in the row. It can be updated accordingly as the window slides by traversing the histogram in the right direction towards the element of interest. This running-sum computation makes the algorithm data dependent. Moreover, the worst case scenario for this data-dependent algorithm happens when the input image contains random data.<\/p>
But why is the behavior prominently present for small window sizes? It can be argued that, as the window size increases, we draw greater number of samples from the underling distribution resulting in smaller variance. As the variance goes down, the code path becomes more predictable and the algorithm obeys linear time complexity. However, when the window size reduces, the data dependency of the algorithm causes the variance to increase (which is a lot more for random input) making the code path less predictable. This causes the behavior reported by the customer of smaller windows taking more time to process as compared to larger windows.<\/p>
After some consideration, we have decided to leave the implementation of ordfilt2<\/tt> as it is. This decision was made based on the fact that the behavior is primarily visible for random input data, which is not usually what customers use ordfilt2<\/tt> for.<\/p>