Otsu's method

From Wikipedia, the free encyclopedia
  (Redirected from Otsu's Method)
Jump to: navigation, search
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 to be thresholded contains two classes of pixels or bi-modal histogram (e.g. foreground and background) then calculates the optimum threshold separating those 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[edit]

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 ith 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[edit]

  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[edit]

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[edit]

  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. 

External links[edit]