Метод Оцу

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

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

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

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

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

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

,

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

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

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

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

Пусть дано монохромное изображение Счетчик повторений

  1. Вычислить гистограмму изображения и частоту для каждого уровня интенсивности изображения .
  2. Вычислить начальные значения для и
  3. Для каждого значения — полутона — горизонтальная ось гистограммы:
    1. Обновляем и
    2. Вычисляем
    3. Если больше, чем имеющееся, то запоминаем и значение порога
  4. Искомый порог соответствует максимуму .
,
,
,
Исходное изображение
Бинаризация с порогом по Оцу

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

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 * .7152 + 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.

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