# Otsu's method

An example image thresholded using Otsu's algorithm
Original image

In computer vision and image processing, Otsu's method is used to automatically perform clustering-based image thresholding,[1] or, the reduction of a graylevel image to a binary image. The algorithm assumes that the image contains two classes of pixels following bi-modal histogram (foreground pixels and background pixels), it then calculates the optimum threshold separating the two classes so that their combined spread (intra-class variance) is minimal.[2] The extension of the original method to multi-level thresholding is referred to as the Multi Otsu method.[3] Otsu's method is named after Nobuyuki Otsu (大津展之 Ōtsu Nobuyuki?).

## Method

In Otsu's method we exhaustively search for the threshold that minimizes the intra-class variance (the variance within the class), defined as a weighted sum of variances of the two classes:

$\sigma^2_w(t)=\omega_1(t)\sigma^2_1(t)+\omega_2(t)\sigma^2_2(t)$

Weights $\omega_i$ are the probabilities of the two classes separated by a threshold $t$ and $\sigma^2_ i$ variances of these classes.

Otsu shows that minimizing the intra-class variance is the same as maximizing inter-class variance:[2]

$\sigma^2_b(t)=\sigma^2-\sigma^2_w(t)=\omega_1(t)\omega_2(t)\left[\mu_1(t)-\mu_2(t)\right]^2$

which is expressed in terms of class probabilities $\omega_i$ and class means $\mu_i$.

The class probability $\omega_1(t)$ is computed from the histogram as $t$:

$\omega_1(t)=\Sigma_0^t p(i)$

while the class mean $\mu_1(t)$ is:

$\mu_1(t)=\left[\Sigma_0^t p(i)\,x(i)\right]/\omega_1$

where $x(i)$ is the value at the center of the $i$th histogram bin. Similarly, you can compute $\omega_2(t)$ and $\mu_2$ on the right-hand side of the histogram for bins greater than $t$.

The class probabilities and class means can be computed iteratively. This idea yields an effective algorithm.

### Algorithm

1. Compute histogram and probabilities of each intensity level
2. Set up initial $\omega_i(0)$ and $\mu_i(0)$
3. Step through all possible thresholds $t = 1 \ldots$ maximum intensity
1. Update $\omega_i$ and $\mu_i$
2. Compute $\sigma^2_b(t)$
4. Desired threshold corresponds to the maximum $\sigma^2_b(t)$
5. You can compute two maxima (and two corresponding thresholds). $\sigma^2_{b1}(t)$ is the greater max and $\sigma^2_{b2}(t)$ is the greater or equal maximum
6. Desired threshold = $\frac{\text{threshold}_1 + \text{threshold}_2 }{2}$

### JavaScript implementation

NB: The input argument total is the number of pixels in the given image. The input argument histogram is a 256-element histogram of a grayscale image different gray-levels (typical for 8-bit images). This function outputs the threshold for the image.

function otsu(histogram, total) {
var sum = 0;
for (var i = 1; i < 256; ++i)
sum += i * histogram[i];
var sumB = 0;
var wB = 0;
var wF = 0;
var mB;
var mF;
var max = 0.0;
var between = 0.0;
var threshold1 = 0.0;
var threshold2 = 0.0;
for (var i = 0; i < 256; ++i) {
wB += histogram[i];
if (wB == 0)
continue;
wF = total - wB;
if (wF == 0)
break;
sumB += i * histogram[i];
mB = sumB / wB;
mF = (sum - sumB) / wF;
between = wB * wF * Math.pow(mB - mF, 2);
if ( between >= max ) {
threshold1 = i;
if ( between > max ) {
threshold2 = i;
}
max = between;
}
}
return ( threshold1 + threshold2 ) / 2.0;
}


## References

1. ^ M. Sezgin and B. Sankur (2004). "Survey over image thresholding techniques and quantitative performance evaluation". Journal of Electronic Imaging 13 (1): 146–165. doi:10.1117/1.1631315.
2. ^ a b Nobuyuki Otsu (1979). "A threshold selection method from gray-level histograms". IEEE Trans. Sys., Man., Cyber. 9 (1): 62–66. doi:10.1109/TSMC.1979.4310076.
3. ^ Ping-Sung Liao and Tse-Sheng Chen and Pau-Choo Chung (2001). "A Fast Algorithm for Multilevel Thresholding". J. Inf. Sci. Eng. 17 (5): 713–727.