Метод Оцу

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод Оцу (англ. Otsu's method) — это алгоритм вычисления порога бинаризации для полутонового изображения, используемый в области компьютерного распознавания образов и обработки изображений.

Алгоритм позволяет разделить пиксели двух классов («полезные» и «фоновые»), рассчитывая такой порог, чтобы внутриклассовая дисперсия была минимальной[1]. Метод Оцу также имеет улучшенную версию для поддержки нескольких уровней изображения[2], который получил название мульти-Оцу метод.

В различных русскоязычных источниках можно встретить различные способы написания фамилии автора, так, например, можно встретить Метод Отса и Метод Отсу.

Метод[править | править вики-текст]

Метод Оцу ищет порог, уменьшающий дисперсию внутри класса, которая определяется как взвешенная сумма дисперсий двух классов:

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

где веса \omega_i — это вероятности двух классов, разделенных порогом t,
\sigma^2_i — дисперсия этих классов.

Оцу показал, что минимизация дисперсии внутри класса равносильна максимизации дисперсии между классами:[1]

\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

которая выражается в терминах вероятности \omega_i и среднего арифметического класса \mu_i, которое, в свою очередь, может обновляться итеративно. Эта идея привела к эффективному алгоритму.

Алгоритм[править | править вики-текст]

Пусть дано монохромное изображение G(i,j), i=\overline {1, Height}, j=\overline {1, Width}. Счетчик повторений k=0.

  1. Вычислить гистограмму p(l) изображения и частоту N(l) для каждого уровня интенсивности изображения G.
  2. Вычислить начальные значения для \omega_1(0), \omega_2(0) и \mu_1(0), \mu_2(0).
  3. Для каждого значения t = \overline {1, max(G)} — полутона — горизонтальная ось гистограммы:
    1. Обновляем \omega_1, \omega_2 и \mu_1, \mu_2
    2. Вычисляем \sigma^2_b(t)=\omega_1(t)\omega_2(t)\left[\mu_1(t)-\mu_2(t)\right]^2.
    3. Если \sigma^2_b(t) больше, чем имеющееся, то запоминаем \sigma^2_b и значение порога t.
  4. Искомый порог соответствует максимуму \sigma^2_b(t).

\omega_1(t) = {{\sum^{t}_{i=0} {p(i)}} \over {\sum^{max(G)}_{i=0} {p(i)}}} = N(t), \omega_2(t) = 1 - \omega_1(t), \mu_1(t) = {{\sum^{t}_{i=0} {i \cdot p(i)}} \over {\omega_1(t)}}, \mu_2(t) = 1 - \mu_1(t).

Исходное изображение
Бинаризация с порогом по Оцу

Программная реализация[править | править вики-текст]

JavaScript[править | править вики-текст]

В данной функции аргумент pixelsNumber является общим числом пикселей изображения, а аргумент histogram — гистограмма 8-битового полутонового изображения, представленная в виде одномерного массива, в котором номер элемента кодирует номер полутона, а значение поля — количество пикселей с этим полутоном.

function otsu(histogram, pixelsNumber) {
	var sum = 0
	  , sumB = 0
	  , wB = 0
	  , wF = 0
      , mB
	  , mF
	  , max = 0
	  , between
	  , threshold = 0;
	for (var i = 0; i < 256; ++i) {
      wB += histogram[i];
      if (wB == 0)
        continue;
      wF = pixelsNumber - 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) {
        max = between;
        threshold = i;
      }
    }
    return threshold;
}

// To test: open any image in browser and run code in console
var im = document.getElementsByTagName('img')[0]
  , cnv = document.createElement('canvas')
  , ctx = cnv.getContext('2d');
cnv.width = im.width;
cnv.height = im.height;
ctx.drawImage(im, 0, 0);
var imData = ctx.getImageData(0, 0, cnv.width, cnv.height)
  , histogram = Array(256)
  , i
  , red
  , green
  , blue
  , gray;
for (i = 0; i < 256; ++i)
	histogram[i] = 0;
for (i = 0; i < imData.data.length; i += 4) {
  red = imData.data[i];
  blue = imData.data[i + 1];
  green = imData.data[i + 2];
  // alpha = imData.data[i + 3];
  // https://en.wikipedia.org/wiki/Grayscale
  gray = red * .2126 + green * .07152 + blue * .0722;
  histogram[Math.round(gray)] += 1;
}
var threshold = otsu(histogram, imData.data.length / 4);
console.log("threshold = %s", threshold);
for (i = 0; i < imData.data.length; i += 4) {
  imData.data[i] = imData.data[i + 1] = imData.data[i + 2] =
    imData.data[i] >= threshold ? 255 : 0;
  // opacity 255 = 100%
  imData.data[i + 3] = 255;
}
ctx.putImageData(imData, 0, 0);
document.body.appendChild(cnv);
console.log("finished");

Результат запуска этого кода в консоли можно увидеть тут.

Реализация на языке C[править | править вики-текст]

#include <stdlib.h> /* Для функций malloc и free*/

/* Функция возвращает порог бинаризации для полутонового изображения image с общим числом пикселей size */
int otsuThreshold(const IMAGE *image, const int size)
{
   int min=image[0], max=image[0];
   int i, temp, temp1;
   int *hist;
   int histSize;

   int alpha, beta, threshold=0;
   double sigma, maxSigma=-1;
   double w1,a;

/**** Построение гистограммы ****/
/* Узнаем наибольший и наименьший полутон */
   for(i=1;i<size;i++)
   {
      temp=image[i];
      if(temp<min)   min = temp;
      if(temp>max)   max = temp;
   }

   histSize=max-min+1;
   if((hist=(int*) malloc(sizeof(int)*histSize))==NULL) return -1;

   for(i=0;i<histSize;i++)
      hist[i]=0;

/* Считаем сколько каких полутонов */
   for(i=0;i<size;i++)
      hist[image[i]-min]++;

/**** Гистограмма построена ****/

   temp=temp1=0;
   alpha=beta=0;
/* Для расчета математического ожидания первого класса */
   for(i=0;i<=(max-min);i++)
   {
      temp += i*hist[i];
      temp1 += hist[i];
   }

/* Основной цикл поиска порога
Пробегаемся по всем полутонам для поиска такого, при котором внутриклассовая дисперсия минимальна */
   for(i=0;i<(max-min);i++)
   {
      alpha+= i*hist[i];
      beta+=hist[i];

      w1 = (double)beta / temp1;
      a = (double)alpha / beta - (double)(temp - alpha) / (temp1 - beta);
      sigma=w1*(1-w1)*a*a;
    
      if(sigma>maxSigma)
      {
         maxSigma=sigma;
         threshold=i;
      }
   }
   free(hist);
   return threshold + min;
}

Примечания[править | править вики-текст]

  1. 1 2 N. Otsu (1979). «A threshold selection method from gray-level histograms». IEEE Trans. Sys., Man., Cyber. 9: 62-66.
  2. Ping-Sung Liao and Tse-Sheng Chen and Pau-Choo Chung (2001). «A Fast Algorithm for Multilevel Thresholding». J. Inf. Sci. Eng. 17: 713-727.

Ссылки[править | править вики-текст]