Otsu's method

From Wikipedia, the free encyclopedia
Jump to: navigation, search
An example image thresholded using Otsu's algorithm
Original image

In computer vision and image processing, Otsu's method, named after Nobuyuki Otsu (大津展之 Ōtsu Nobuyuki?), 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, or equivalently (because the sum of pairwise squared distances is constant), so that their inter-class variance is maximal.[2] Consequently, Otsu's method is roughly a one-dimensional, discrete analog of Fisher's Discriminant Analysis.

The extension of the original method to multi-level thresholding is referred to as the Multi Otsu method.[3]

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 are 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.

The Otsu method produces a threshold on the 0:1 scale. This threshold applies to the dynamic range of pixel intensities present in the image. For example, were the image to only contain pixel intensities in the range of 155 to 255, an Otsu threshold of 0.75 would map to a grayscale threshold value of 230 (not 191 as it would if the image contained pixels in the full range of 0-255). Common photographic images will tend to contain a full range of pixel intensities, making it a mute point, but other applications could be sensitive to the distinction.[4]

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 * (mB - mF) * (mB - mF);
        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. 
  4. ^ "Q&A Forum". Stack Overflow. 

External links[edit]