Русская Википедия:Метод Оцу

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Метод Оцу (Шаблон:Lang-en) — это алгоритм вычисления порога бинаризации для полутонового изображения, используемый в области компьютерного распознавания образов и обработки изображений для получения чёрно-белых изображений.

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

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

Метод

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

<math>\sigma^2_w(t)=\omega_1(t)\sigma^2_1(t)+\omega_2(t)\sigma^2_2(t)</math>,

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

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

<math>\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</math>

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

Алгоритм

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

  1. Вычислить гистограмму <math>p(l)</math> изображения и частоту <math>N(l)</math> для каждого уровня интенсивности изображения <math>G</math>.
  2. Вычислить начальные значения для <math>\omega_1(0), \omega_2(0)</math> и <math>\mu_1(0), \mu_2(0).</math>
  3. Для каждого значения <math>t = \overline {1, max(G)}</math> — полутона — горизонтальная ось гистограммы:
    1. Обновляем <math>\omega_1, \omega_2</math> и <math>\mu_1, \mu_2</math>
    2. Вычисляем <math>\sigma^2_b(t)=\omega_1(t)\omega_2(t)\left[\mu_1(t)-\mu_2(t)\right]^2.</math>
    3. Если <math>\sigma^2_b(t)</math> больше, чем имеющееся, то запоминаем <math>\sigma^2_b</math> и значение порога <math>t.</math>
  4. Искомый порог соответствует максимуму <math>\sigma^2_b(t)</math>.
<math> N_T = \sum^{max(G)}_{i=0} {p(i)}</math>,
<math>\omega_1(t) = {{\sum^{t-1}_{i=0} {p(i)}} \over {N_T}} = {\sum^{t-1}_{i=0} {N(i)}},\quad \omega_2(t) = 1 - \omega_1(t)</math>,
<math>\mu_T = {{\sum^{max(G)}_{i=0} {i \cdot p(i)}} \over {N_T}} = {\sum^{max(G)}_{i=0} {i \cdot N(i)}} </math>,
<math>\mu_1(t) = {{\sum^{t-1}_{i=0} {i \cdot p(i)}} \over {N_T \cdot \omega_1(t)}} = {{\sum^{t-1}_{i=0} {i \cdot N(i)}} \over {\omega_1(t)}}, \quad \mu_2(t) = {{\mu_T - \mu_1(t) \cdot \omega_1(t)} \over {\omega_2(t)}}.</math>
Файл:Image processing pre otsus algorithm.jpg
Исходное изображение
Файл:Image processing post otsus algorithm.jpg
Бинаризация с порогом по Оцу

Программная реализация

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

// Количество уровней интенсивности у изображения.
// Стандартно для серого изображения -- это 256. От 0 до 255.
const int INTENSITY_LAYER_NUMBER = 256;

// Возвращает гистограмму по интенсивности изображения от 0 до 255 включительно
void calculateHist(const IMAGE *image, const int size, int* hist) {
    // Иницилизируем гистограмму нулями
    memset(hist, 0, INTENSITY_LAYER_NUMBER * sizeof(*hist));

    // Вычисляем гистограмму
    for (int i = 0; i < size; ++i) {
        ++hist[image[i]];
    }
}

// Посчитать сумму всех интенсивностей
int calculateIntensitySum(const IMAGE *image, const int size) {
    int sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += image[i];
    }

    return sum;
}

// Функция возвращает порог бинаризации для полутонового изображения image с общим числом пикселей size.
// const IMAGE *image содержит интенсивность изображения от 0 до 255 включительно.
// size -- количество пикселей в image.
int otsuThreshold(const IMAGE *image, const int size) {
    int hist[INTENSITY_LAYER_NUMBER];
    calculateHist(image, size, hist);

    // Необходимы для быстрого пересчёта разности дисперсий между классами
    int all_pixel_count = size;
    int all_intensity_sum = calculateIntensitySum(image, size);

    int best_thresh = 0;
    double best_sigma = 0.0;

    int first_class_pixel_count = 0;
    int first_class_intensity_sum = 0;

    // Перебираем границу между классами
    // thresh < INTENSITY_LAYER_NUMBER - 1, т.к. при 255 в ноль уходит знаменатель внутри for
    for (int thresh = 0; thresh < INTENSITY_LAYER_NUMBER - 1; ++thresh) {
        first_class_pixel_count += hist[thresh];
        first_class_intensity_sum += thresh * hist[thresh];

        double first_class_prob = first_class_pixel_count / (double) all_pixel_count;
        double second_class_prob = 1.0 - first_class_prob;

        double first_class_mean = first_class_intensity_sum / (double) first_class_pixel_count;
        double second_class_mean = (all_intensity_sum - first_class_intensity_sum) 
            / (double) (all_pixel_count - first_class_pixel_count);

        double mean_delta = first_class_mean - second_class_mean;

        double sigma = first_class_prob * second_class_prob * mean_delta * mean_delta;

        if (sigma > best_sigma) {
            best_sigma = sigma;
            best_thresh = thresh;
        }
    }

   return best_thresh;
}

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Стиль статьи

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Шаблон:Статья
  2. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Метод_Оцу&oldid=10372949