# What is the time complexity of the original Otsu's method?

I'm trying to give a general comparison of the time complexities of various thresholding algorithms. I have not taken an algorithms course yet, so please forgive any misunderstandings.

Otsu's method is performed on $$N$$ pixels with $$L$$ number of pixel intensities (e.g. an 8 bit greyscale image would have $$L=256$$). The algorithm will choose an intensity $$k$$, and calculate the variance for pixels with intensity less than $$k$$, and for pixels with intensities greater than $$k$$.

Calculating the variance involves finding the mean intensity (summing a total of $$N$$ pixels), then sum the square of the difference between each pixel intensity and the mean mean intensity (again summing a total of $$N$$ pixels). This is performed for all intensities.

Therefore, would I be correct to say that the average time complexity of the algorithm is $$O(LN)$$?

• Can you edit the question to clarify what $L$ represents? Is that the number of possible values for a pixel intensity?
– D.W.
Dec 6, 2020 at 7:19
• @D.W. Done, hope it's clearer now. Dec 6, 2020 at 9:06

The algorithm can certainly be implemented in $$O(LN)$$ time, as you say.
It is not hard to optimize it to run in $$O(N+L^2)$$ time. Simply form a histogram of pixel intensities (count of the number of pixels of each intensity). Then you can compute each variance in $$O(L)$$ time, rather than $$O(N)$$ time.
You can improve it further to run in $$O(N+L)$$ time. Suppose we have computed the sum of values below the threshold and sum of squared values below the threshold; and the same for those above the threshold. That is enough to compute the standard deviations. Then, when we bump up the threshold by one, it is possible to update those four sums in $$O(1)$$ time. As a result, it takes $$O(N)$$ time to build the histogram, then $$O(L)$$ time to compute the score for the first threshold, then $$O(1)$$ time for each subsequent threshold, and there are $$L$$ candidate thresholds, for a total of $$O(N+L)$$ time.
In practice the difference between $$O(N+L^2)$$ vs $$O(N+L)$$ might be unimportant, as for 8-bit images, $$L \le 256$$.