In computer vision and image processing, Otsu's method is used to automatically perform
histogram shape-based image thresholding, 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 (e.g. foreground and background)
then calculates the optimum threshold separating those two classes so that their combined spread (intra-class variance) is minimal.

Let the pixels of given picture be represented in L gray levels [1,2,…L]. The number of pixels with level i is denoted by ni and the total number of pixels by  N = n1 + n2 + …+ nL.
In order to simplify the discussion, the gray-level histogram is normalized and regarded as a probability distribution:

Now suppose that we dichotomize the pixel into two classes C0 and C1 (background and objects) by a threshold at level k: C0 denotes pixels with levels [0, … k] and C1 denotes pixels with levels [k+1, … ,L]. Then the probabilities of class occurrence and the class mean levels, respectively, are given by



The optimal threshold k* is


where

Reference:

 

  1. Nobuyuki Otsu, A threshold selection method from gray-level histograms, IEEE, January 1979
  2. https://en.wikipedia.org/wiki/Otsu's_method

 

void OtsuBinarization(Image* input_image, Image* output_image)
{
	int max_x = input_image->get_width();
	int max_y = input_image->get_height();
	const int L = 256;
	float hist[L] = { 0.0F };

	//calculate grayscale histogram
	for (int x = 0; x < max_x; ++x)
		for (int y = 0; y < max_y; ++y)
		{
			Pixel cur;
			cur = input_image->get_pixel(x, y);
			int graylevel = max(0.0, min(255.0, 0.299*cur.R + 0.587*cur.G + 0.114*cur.B));
			hist[graylevel] += 1;
		}

	int N = max_x*max_y;

	//normalize histogram
	for (int i = 0; i < L; ++i)
		hist[i] /= N;


		float ut = 0;
		for (int i = 0; i < L; ++i)
			ut += i*hist[i];

		int max_k = 0;
		int max_sigma_k_ = 0;
		for (int k = 0; k < L; ++k)
		{
			float wk = 0;
				for (int i = 0; i <= k; ++i)
					wk += hist[i];
				float uk = 0;
				for (int i = 0; i <= k; ++i)
					uk += i*hist[i];

			float sigma_k = 0;
			if (wk != 0 && wk != 1)
				sigma_k = ((ut*wk - uk)*(ut*wk - uk)) / (wk*(1 - wk));

			if (sigma_k > max_sigma_k_)
			{
				max_k = k;
				max_sigma_k_ = sigma_k;
			}
		}

	for (int x = 0; x < max_x; ++x)
		for (int y = 0; y < max_y; ++y)
		{
			Pixel cur;
			cur = input_image->get_pixel(x,y);
			int graylevel = max(0.0, min(255.0, 0.299*cur.R + 0.587*cur.G + 0.114*cur.B));
			if (graylevel < max_k)
				output_image->set_pixel(x,y, RGB(0, 0, 0));
			else
				output_image->set_pixel(x,y, RGB(255, 255, 255));
		}
}

Comments  

+1 #1 Jose 2009-01-29 23:39
Nice article
I search on internet for Otsu method and I found many article but this is much
value from other articles. Great job. Thanks
Quote
+1 #2 Anonymous 2009-03-30 00:39
There is something missing when normalizing the histogram, and after that as
well.
Quote
+1 #3 llaskov 2010-05-21 14:45
(wk !=0 && wk!=1) is not a very good idea when wk is a float variable.
Quote
+1 #4 tony 2012-04-03 07:00
faster way
If you remove the two inner loops which recalculate wk and uk the algorithm
becomes O(N) instead O(N log N), where N is the number of bins in the histogram.
Quote

Add comment


Security code
Refresh

Joomla SEF URLs by Artio