Blazingly Fast Approximation of Otsu's Multi-threshold Method
Otsu's Method is an algorithm for thresholding a grayscale image into a well-balanced black and white image by analyzing an image's histogram.
It can also be extended to multithresholding, where multiple thresholds can be used to drastically reduce the number of grey shades in an image. Below is an example tractor rendered in only four shades of grey, as calculated by OtsuPyre.
The biggest slowdown with Otsu's Method is that its algorithm must iterate over the entire histogram for each threshold, making its complexity O(LM) where M is the number of thresholds, and L is the range of the intensitly levels (typically 256 for a standard image).
OtsuPyre takes a divide-and-conquer approach to multithresholding by recognizing that manipulating the histogram size will reduce iteration count and achieve higher speeds. OtsuPyre iteratively reduces the histogram to half its size until the histogram length, N, is minimally greater than or equal to M. Then OtsuPyre computes the thresholds on this minimal histogram. This first histograms length is bounded by the number of thresholds: M ≤ N ≤ 2M, and the complexity for this first computation is O(NL).
From there, OtsuPyre will:
- Scale up the computed threshold by a factor of 2
- Use a histogram twice as large as the previous one
- Search larger histogram within error bounds of our previously computed thresholds (error bounds are calculated from the scaling factor in step 1 & 2)
- Return new thresholds
- Repeat steps 1 - 4 until thresholds have been calculated on original histogram.
Step 3 is integral to the speed of OtsuPyre. Assuming we are dealing with a standard image, the histogram and thresholds will both be scaled by 2, and approximate error bounds = 2. Therefore a new threshold search will search a 5x5 area around each threshold, making the complexity for each iterative calculation O(5M).
There are K iterations, which correlate to the original size of the histogram and the number of reductions / compressions taken before it was just small enough to fit the desired thresholds, which leaves the general complexity as O(NM + (8 - K) * 5M)
Searching for M thresholds on a typical image with OtsuPyre will have a maximum complexity of ~ O((2M)M + 8 * 5M), and will require Z iterations. Here are some calculated numbers
- M(number of thresholds): Y(complexity) == Z(iterations)
- 2: O(22 + 7 * 52) == 179
- 3: O(43 + 6 * 53) == 814
- 4: O(44 + 6 * 54) == 4,006
- 5: O(85 + 5 * 55) == 48,393
- 6: O(86 + 5 * 56) == 340,269
- 7: O(87 + 5 * 57) == 2,487,777
- 8: O(88 + 5 * 58) == 18,730,341
- 9: O(169 + 4 * 59) == 68,727,289,236
Now compare to a naive Otsu implementation, which is O(256M)
- 1: 2561 == 256
- 2: 2562 == 65,536
- 3: 2563 == 16,777,216
- 4: 2564 == 4,294,967,296
- 5: 2565 == 1,099,511,627,776
Which can be interpreted to say that Naive Otsu's Method can easily find 3 thresholds, while OtsuPyre can find 8. After those points, both algorithms quickly succumb to the exponential increase in computation time.
Please note that OtsuPyre is an approximation algorithm. Although thresholds found give good separation between grey levels, they do not match thresholds found by a Naive Otsu's implementation.