{"id":1338,"date":"2020-03-13T02:05:41","date_gmt":"2020-03-13T02:05:41","guid":{"rendered":"https:\/\/muthu.co\/?p=1338"},"modified":"2023-12-21T00:36:48","modified_gmt":"2023-12-21T00:36:48","slug":"otsus-method-for-image-thresholding-explained-and-implemented","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/otsus-method-for-image-thresholding-explained-and-implemented\/","title":{"rendered":"Otsu’s method for image thresholding explained and implemented"},"content":{"rendered":"\n

The process of separating the foreground pixels from the background is called thresholding. There are many ways of achieving optimal thresholding and one of the ways is called the Otsu’s method, proposed by Nobuyuki Otsu.<\/a> Otsu’s method[1] is a variance-based technique to find the threshold value where the weighted variance between the foreground and background pixels is the least. The key idea here is to iterate through all the possible values of threshold and measure the spread of background and foreground pixels. Then find the threshold where the spread is least.<\/p>\n\n\n\n

Algorithm<\/h2>\n\n\n\n

The algorithm iteratively searches for the threshold that minimizes the within-class variance, defined as a weighted sum of variances of the two classes (background and foreground). The colors in grayscale are usually between 0-255 (0-1 in case of float). So, If we choose a threshold of 100, then all the pixels with values less than 100 becomes the background and all pixels with values greater than or equal to 100 becomes the foreground of the image.<\/p>\n\n\n\n

The formula for finding the within-class variance at any threshold t<\/em> is given by:<\/p>\n\n\n\n

\\(\\sigma ^2 (t) = \\omega_{bg}(t) \\sigma_{bg} ^2 (t) + \\omega_{fg}(t) \\sigma_{fg} ^2 (t) \\)   \\((1) \\)<\/p>\n\n\n\n

where \\(\\omega_{bg}(t) \\) and \\(\\omega_{fg}(t) \\) represents the probability of number of pixels for each class at threshold t and \\(\\sigma ^2 \\) represents the variance of color values.<\/p>\n\n\n\n

To understand what this probaility means, Let,<\/p>\n\n\n\n

\\(P_{all} \\) be the total count of pixels in an image,
\\(P_{BG}(t) \\) be the count of background pixels at threshold t,
<\/em>\\(P_{FG}(t) \\) be the count of foreground pixels at threshold t<\/em><\/p>\n\n\n\n

So the weights are given by,<\/p>\n\n\n\n

\\(\\omega_{bg}(t) = \\frac{P_{BG}(t)}{ P_{all}} \\)<\/p>\n\n\n\n

\\(\\omega_{fg}(t) = \\frac{P_{FG}(t)}{ P_{all}} \\)<\/p>\n\n\n\n

\\(\\omega_{fg}(t) = \\)<\/p>\n\n\n\n

The variance can be calculated using the below formula:<\/p>\n\n\n\n

\\(\\sigma ^2 (t) = \\frac{ \\sum (x_{i}-\\overline{x} )^{2} }{N-1} \\)<\/p>\n\n\n\n

where,<\/p>\n\n\n\n

\\(x_{i} \\) is the value of pixel at i in the group (bg or fg)
\\(\\overline{x} \\) is the means of pixel values in the group (bg or fg)
\\(N \\) is the number of pixels.<\/p>\n\n\n\n

Now, Let’s understand the formula by finding the within-class variance at one threshold, T=100<\/p>\n\n\n

\n
\"\"<\/a>
Image with pixel color values<\/figcaption><\/figure><\/div>\n\n\n

For the above image, at T=100,  we will get the background and foreground as shown below:<\/p>\n\n\n

\n
\"\"<\/a>
foreground pixels<\/figcaption><\/figure><\/div>\n\n
\n
\"\"<\/a>
background pixels<\/figcaption><\/figure><\/div>\n\n\n

Here,
\\(P_{all} = 16 \\)
\\(P_{BG} = 7 \\)
\\(P_{FG} = 9 \\)<\/p>\n\n\n\n

Our weights will be,<\/p>\n\n\n\n

\\(\\omega_{bg}(t) = \\frac{P_{BG}(t)}{ P_{all}} =  7\/16 = 0.44\\)
\\(\\omega_{fg}(t) = \\frac{P_{FG}(t)}{ P_{all}} =  9\/16 = 0.56\\)<\/p>\n\n\n\n

Now to find the variance, we find the mean first.<\/p>\n\n\n\n

\\(\\overline{x_{bg}} = \\frac{21+22+25+26+27+23+24}{7} = 24\\)
\\(\\overline{x_{fg}} = \\frac{120+120+160+180+190+123+145+165+175}{9} = 153.1\\)<\/p>\n\n\n\n

The variances are given by,<\/p>\n\n\n\n

\\(\\sigma_{bg} ^2 (t=100)= \\frac{(21-24)^2+(22-24)^2…….(24-24)^2}{7} = 4.0\\)
\\(\\sigma_{fg} ^2 (t=100)= \\frac{(120-153.1)^2+(120-153.1)^2…….(175-153.1)^2}{9} = 657.43\\)<\/p>\n\n\n\n

Substituting everything in equation (1) we get,<\/p>\n\n\n\n

\\(\\sigma ^2 (t=100) = 0.44 * 4.0 + 0.56 * 657.43 = 369.9208 \\)<\/p>\n\n\n\n

Similarly, we can find for other values of t also.<\/p>\n\n\n\n

\"\"<\/a><\/td>\"\"<\/a><\/td>\"\"<\/a><\/td><\/tr>
T=22, \\(\\sigma ^2 = 4092.58\\)<\/td>T=23, \\(\\sigma ^2 = 3667.60\\)<\/td>T=25, \\(\\sigma ^2 = 2642.35\\)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\"\"<\/a><\/td>\"\"<\/a><\/td>\"\"<\/a><\/td><\/tr>
T=26, \\(\\sigma ^2 = 2009.93\\)<\/td>T=28, \\(\\sigma ^2 = 371.55\\)<\/strong><\/td>T=124, \\(\\sigma ^2 = 1316.48\\)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

The value of variance remains the same from 28 and 120.<\/p>\n\n\n\n

If you see the above variances, its least at T=28 or more precicely between 28 to 120.<\/p>\n\n\n\n

Thus our Otsu threshold = 28.<\/p>\n\n\n\n

Python Implementation<\/h2>\n\n\n\n
def threshold_otsu_impl(image, nbins=0.1):\n    \n    #validate grayscale\n    if len(image.shape) == 1 or len(image.shape) > 2:\n        print(\"must be a grayscale image.\")\n        return\n    \n    #validate multicolored\n    if np.min(image) == np.max(image):\n        print(\"the image must have multiple colors\")\n        return\n    \n    all_colors = image.flatten()\n    total_weight = len(all_colors)\n    least_variance = -1\n    least_variance_threshold = -1\n    \n    # create an array of all possible threshold values which we want to loop through\n    color_thresholds = np.arange(np.min(image)+nbins, np.max(image)-nbins, nbins)\n    \n    # loop through the thresholds to find the one with the least within class variance\n    for color_threshold in color_thresholds:\n        bg_pixels = all_colors[all_colors < color_threshold]\n        weight_bg = len(bg_pixels) \/ total_weight\n        variance_bg = np.var(bg_pixels)\n\n        fg_pixels = all_colors[all_colors >= color_threshold]\n        weight_fg = len(fg_pixels) \/ total_weight\n        variance_fg = np.var(fg_pixels)\n\n        within_class_variance = weight_fg*variance_fg + weight_bg*variance_bg\n        if least_variance == -1 or least_variance > within_class_variance:\n            least_variance = within_class_variance\n            least_variance_threshold = color_threshold\n        print(\"trace:\", within_class_variance, color_threshold)\n            \n    return least_variance_threshold<\/code><\/pre>\n\n\n\n
The entire notebook is here. Otsu Thresholding implementation<\/a><\/p>\n\n\n\n
Some sample thresholding using the Otsu Method.<\/p>\n\n\n
\n
\"\"<\/a><\/figure><\/div>\n\n
\n
\"\"<\/a><\/figure><\/div>\n\n
\n
\"\"<\/a><\/figure><\/div>\n\n\n
References:<\/p>\n\n\n\n
    \n
  1. “Nobuyuki Otsu (1979), A Threshold Selection Method from Gray-Level Histograms” – https:\/\/ieeexplore.ieee.org\/document\/4310076<\/a><\/li>\n\n\n\n
  2. https:\/\/en.wikipedia.org\/wiki\/Otsu’s_method<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    The process of separating the foreground pixels from the background is called thresholding. There are many ways of achieving optimal thresholding and one of the ways is called the Otsu’s method, proposed by Nobuyuki Otsu. Otsu’s method[1] is a variance-based technique to find the threshold value where the weighted variance between the foreground and background […]<\/p>\n","protected":false},"author":1,"featured_media":1351,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41,38,6,31],"tags":[44,47,54,62],"_links":{"self":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1338"}],"collection":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/comments?post=1338"}],"version-history":[{"count":10,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1338\/revisions"}],"predecessor-version":[{"id":1980,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1338\/revisions\/1980"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media\/1351"}],"wp:attachment":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media?parent=1338"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/categories?post=1338"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/tags?post=1338"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}