Метод Оцу
Метод Оцу (англ. Otsu's method) — это алгоритм вычисления порога бинаризации для полутонового изображения, используемый в области компьютерного распознавания образов и обработки изображений для получения чёрно-белых изображений.
Алгоритм позволяет разделить пиксели двух классов («полезные» и «фоновые»), рассчитывая такой порог, чтобы внутриклассовая дисперсия была минимальной[1]. Метод Оцу также имеет улучшенную версию для поддержки нескольких уровней изображения[2], который получил название мульти-Оцу метод.
В различных русскоязычных источниках можно встретить различные способы написания фамилии автора, Нобуюки Отсу (англ.), например, можно встретить Метод Отса и Метод Отсу.
Метод
Метод Оцу ищет порог, уменьшающий дисперсию внутри класса, которая определяется как взвешенная сумма дисперсий двух классов:
- [math]\displaystyle{ \sigma^2_w(t)=\omega_1(t)\sigma^2_1(t)+\omega_2(t)\sigma^2_2(t) }[/math],
где веса [math]\displaystyle{ \omega_i }[/math] — это вероятности двух классов, разделённых порогом t,
[math]\displaystyle{ \sigma^2_i }[/math] — дисперсия этих классов.
Оцу показал, что минимизация дисперсии внутри класса равносильна максимизации дисперсии между классами:[1]
- [math]\displaystyle{ \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]\displaystyle{ \omega_i }[/math] и среднего арифметического класса [math]\displaystyle{ \mu_i }[/math], которое, в свою очередь, может обновляться итеративно. Эта идея привела к эффективному алгоритму.
Алгоритм
Пусть дано полутоновое изображение [math]\displaystyle{ G(i,j), i=\overline {1, Height}, j=\overline {1, Width}. }[/math] Счётчик повторений [math]\displaystyle{ k=0. }[/math]
- Вычислить гистограмму [math]\displaystyle{ p(l) }[/math] изображения и частоту [math]\displaystyle{ N(l) }[/math] для каждого уровня интенсивности изображения [math]\displaystyle{ G }[/math].
- Вычислить начальные значения для [math]\displaystyle{ \omega_1(0), \omega_2(0) }[/math] и [math]\displaystyle{ \mu_1(0), \mu_2(0). }[/math]
- Для каждого значения [math]\displaystyle{ t = \overline {1, max(G)} }[/math] — полутона — горизонтальная ось гистограммы:
- Обновляем [math]\displaystyle{ \omega_1, \omega_2 }[/math] и [math]\displaystyle{ \mu_1, \mu_2 }[/math]
- Вычисляем [math]\displaystyle{ \sigma^2_b(t)=\omega_1(t)\omega_2(t)\left[\mu_1(t)-\mu_2(t)\right]^2. }[/math]
- Если [math]\displaystyle{ \sigma^2_b(t) }[/math] больше, чем имеющееся, то запоминаем [math]\displaystyle{ \sigma^2_b }[/math] и значение порога [math]\displaystyle{ t. }[/math]
- Искомый порог соответствует максимуму [math]\displaystyle{ \sigma^2_b(t) }[/math].
- [math]\displaystyle{ N_T = \sum^{max(G)}_{i=0} {p(i)} }[/math],
- [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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]
![]() |
![]() |
Программная реализация
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,0 1,1 N. Otsu. A threshold selection method from gray-level histograms (англ.) // IEEE Trans. Sys., Man., Cyber. : journal. — 1979. — Vol. 9. — P. 62—66.
- ↑ Ping-Sung Liao and Tse-Sheng Chen and Pau-Choo Chung. A Fast Algorithm for Multilevel Thresholding (неопр.) // J. Inf. Sci. Eng.. — 2001. — Т. 17. — С. 713—727.
Ссылки
- Lecture notes on thresholding — covers the Otsu method.
Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. |