Метод Оцу

редактировать

Пример изображения с пороговым значением с использованием алгоритма Оцу

Исходное изображение

В области компьютерного зрения и обработке изображений, Метод Оцы, названное в честь Нобуюков Оцы (大津展之, Оца Нобуюки), используются для выполнения автоматического изображения порогового. В простейшей форме алгоритм возвращает единый порог интенсивности, который разделяет пиксели на два класса: передний план и фон. Этот порог определяется путем минимизации дисперсии интенсивности внутри класса или, что эквивалентно, путем максимизации дисперсии между классами. Метод Оцу является одномерным дискретным аналогом дискриминантного анализа Фишера, связан с методом оптимизации Дженкса и эквивалентен глобально оптимальному k-среднему, выполненному на гистограмме интенсивности. Расширение многоуровневой пороговой обработки было описано в исходной статье, и с тех пор были предложены эффективные в вычислительном отношении реализации.

СОДЕРЖАНИЕ

1 Метод Оцу
- 1.1 Алгоритм
- 1.2 Реализация MATLAB или Octave
2 Ограничения
3 Улучшения
- 3.1 Алгоритм
- 3.2 Реализация Matlab
4 ссылки
5 Внешние ссылки

Метод Оцу

Визуализация метода Оцу

Алгоритм исчерпывающе ищет порог, который минимизирует внутриклассовую дисперсию, определяемую как взвешенная сумма дисперсий двух классов:

{\ displaystyle \ sigma _ {w} ^ {2} (t) = \ omega _ {0} (t) \ sigma _ {0} ^ {2} (t) + \ omega _ {1} (t) \ сигма _ {1} ^ {2} (t)}

\ sigma _ {w} ^ {2} (t) = \ omega _ {0} (t) \ sigma _ {0} ^ {2} (t) + \ omega _ {1} (t) \ sigma _ { 1} ^ {2} (т)

Веса и - вероятности двух классов, разделенных порогом, а и - дисперсии этих двух классов. ${\ displaystyle \ omega _ {0}}$ $\ omega _ {0}$ ${\ displaystyle \ omega _ {1}}$ $\ omega _ {{1}}$ ${\ displaystyle t}$ $т$ ${\ displaystyle \ sigma _ {0} ^ {2}}$ ${\ displaystyle \ sigma _ {0} ^ {2}}$ ${\ displaystyle \ sigma _ {1} ^ {2}}$ ${\ displaystyle \ sigma _ {1} ^ {2}}$

Вероятность класса вычисляется из интервалов гистограммы: ${\ Displaystyle \ omega _ {0,1} (т)}$ $\ omega _ {0,1} (т)$ ${\ displaystyle L}$ $L$

{\ displaystyle {\ begin {align} \ omega _ {0} (t) amp; = \ sum _ {i = 0} ^ {t-1} p (i) \\ [4pt] \ omega _ {1} ( т) amp; = \ сумма _ {я = т} ^ {L-1} р (я) \ конец {выровнено}}}

{\ displaystyle {\ begin {align} \ omega _ {0} (t) amp; = \ sum _ {i = 0} ^ {t-1} p (i) \\ [4pt] \ omega _ {1} ( т) amp; = \ сумма _ {я = т} ^ {L-1} р (я) \ конец {выровнено}}}

Для 2 классов минимизация внутриклассовой дисперсии эквивалентна максимизации межклассовой дисперсии:

{\ displaystyle {\ begin {align} \ sigma _ {b} ^ {2} (t) amp; = \ sigma ^ {2} - \ sigma _ {w} ^ {2} (t) = \ omega _ {0 } (\ mu _ {0} - \ mu _ {T}) ^ {2} + \ omega _ {1} (\ mu _ {1} - \ mu _ {T}) ^ {2} \\ amp; = \ omega _ {0} (t) \ omega _ {1} (t) \ left [\ mu _ {0} (t) - \ mu _ {1} (t) \ right] ^ {2} \ end { выровнено}}}

{\ displaystyle {\ begin {align} \ sigma _ {b} ^ {2} (t) amp; = \ sigma ^ {2} - \ sigma _ {w} ^ {2} (t) = \ omega _ {0 } (\ mu _ {0} - \ mu _ {T}) ^ {2} + \ omega _ {1} (\ mu _ {1} - \ mu _ {T}) ^ {2} \\ amp; = \ omega _ {0} (t) \ omega _ {1} (t) \ left [\ mu _ {0} (t) - \ mu _ {1} (t) \ right] ^ {2} \ end { выровнено}}}

который выражается в терминах вероятностей классов и средних классов, где класс означает, и являются: ${\ displaystyle \ omega}$ $\омега$ ${\ displaystyle \ mu}$ $\ му$ ${\ displaystyle \ mu _ {0} (т)}$ ${\ displaystyle \ mu _ {0} (т)}$ ${\ Displaystyle \ му _ {1} (т)}$ $\ mu_1 (t)$ ${\ displaystyle \ mu _ {T}}$ ${\ displaystyle \ mu _ {T}}$

{\ displaystyle {\ begin {align} \ mu _ {0} (t) amp; = {\ frac {\ sum _ {i = 0} ^ {t-1} ip (i)} {\ omega _ {0} (t)}} \\ [4pt] \ mu _ {1} (t) amp; = {\ frac {\ sum _ {i = t} ^ {L-1} ip (i)} {\ omega _ {1 } (t)}} \\\ mu _ {T} amp; = \ sum _ {i = 0} ^ {L-1} ip (i) \ end {align}}}

{\ displaystyle {\ begin {align} \ mu _ {0} (t) amp; = {\ frac {\ sum _ {i = 0} ^ {t-1} ip (i)} {\ omega _ {0} (t)}} \\ [4pt] \ mu _ {1} (t) amp; = {\ frac {\ sum _ {i = t} ^ {L-1} ip (i)} {\ omega _ {1 } (t)}} \\\ mu _ {T} amp; = \ sum _ {i = 0} ^ {L-1} ip (i) \ end {align}}}

Несложно проверить следующие соотношения:

{\ displaystyle {\ begin {align} \ omega _ {0} \ mu _ {0} + \ omega _ {1} \ mu _ {1} amp; = \ mu _ {T} \\\ omega _ {0} + \ omega _ {1} amp; = 1 \ end {выровнено}}}

{\ displaystyle {\ begin {align} \ omega _ {0} \ mu _ {0} + \ omega _ {1} \ mu _ {1} amp; = \ mu _ {T} \\\ omega _ {0} + \ omega _ {1} amp; = 1 \ end {выровнено}}}

Вероятности классов и средние классы могут быть вычислены итеративно. Эта идея дает эффективный алгоритм.

Алгоритм

Вычислить гистограмму и вероятности каждого уровня интенсивности
Настройте начальную и ${\ displaystyle \ omega _ {я} (0)}$ $\ omega _ {i} (0)$ ${\ Displaystyle \ му _ {я} (0)}$ $\ mu _ {i} (0)$
Пройдите через все возможные пороги максимальной интенсивности т знак равно 1 , … {\ Displaystyle т = 1, \ ldots}
1. Обновление и ${\ displaystyle \ omega _ {я}}$ $\ omega _ {i}$ ${\ Displaystyle \ mu _ {я}}$ $\ mu _ {я}$
2. Вычислить ${\ Displaystyle \ sigma _ {b} ^ {2} (т)}$ $\ sigma _ {b} ^ {2} (т)$
Желаемый порог соответствует максимальному ${\ Displaystyle \ sigma _ {b} ^ {2} (т)}$ $\ sigma _ {b} ^ {2} (т)$

Реализация MATLAB или Octave

histogramCounts - это гистограмма из 256 элементов изображения в градациях серого с разными уровнями серого (типично для 8-битных изображений). level - это порог изображения (двойной).

function level = otsu(histogramCounts) total = sum(histogramCounts); % total number of pixels in the image %% OTSU automatic thresholding top = 256; sumB = 0; wB = 0; maximum = 0.0; sum1 = dot(0:top-1, histogramCounts); for ii = 1:top wF = total - wB; if wB gt; 0 amp;amp; wF gt; 0 mF = (sum1 - sumB) / wF; val = wB * wF * ((sumB / wB) - mF) * ((sumB / wB) - mF); if ( val gt;= maximum) level = ii; maximum = val; end end wB = wB + histogramCounts(ii); sumB = sumB + (ii-1) * histogramCounts(ii); end end

Matlab имеет встроенные функции graythresh()и multithresh()в панели инструментов обработки изображений, которые реализованы с помощью метода Оцу и метода Мульти Оцу, соответственно.

Ограничения

Метод Оцу хорошо работает, когда гистограмма имеет бимодальное распределение с глубокой и резкой впадиной между двумя пиками. Но если площадь объекта мала по сравнению с областью фона, гистограмма больше не демонстрирует бимодальности. Если дисперсия объекта и интенсивности фона велики по сравнению со средней разницей, или если изображение сильно искажено аддитивным шумом, резкая впадина гистограммы уровней серого ухудшается. Тогда возможно неверный порог, определенный методом Оцу, приводит к ошибке сегментации. (Здесь мы определяем размер объекта как отношение площади объекта ко всей площади изображения, а среднюю разницу как разность средних интенсивностей объекта и фона)

Эмпирические результаты показывают, что производительность глобальных методов определения пороговых значений, используемых для сегментации объектов (включая метод Оцу), ограничена небольшим размером объекта, небольшой средней разницей между пикселями переднего и заднего плана, большой дисперсией пикселей, принадлежащих объекту, и пикселей, которые принадлежат ему. к фону, большое количество шума и т. д.

Улучшения

Для устранения ограничений метода Оцу были разработаны различные расширения. Одним из популярных расширений является двухмерный метод Оцу, который лучше справляется с задачей сегментации объектов на зашумленных изображениях. Здесь значение интенсивности данного пикселя сравнивается со средней интенсивностью его ближайшего окружения, чтобы улучшить результаты сегментации.

Для каждого пикселя вычисляется среднее значение уровня серого для окрестности. Пусть уровень серого данного пикселя разделен на дискретные значения, а средний уровень серого также разделен на те же значения. Затем формируется пара: уровень серого пикселя и среднее значение окрестности. Каждая пара принадлежит одному из возможных двумерных интервалов. Общее количество вхождений (частота) пары, деленное на общее количество пикселей в изображении, определяет функцию совместной вероятностной массы на 2-мерной гистограмме: ${\ displaystyle L}$ $L$ ${\ displaystyle L}$ $L$ ${\ displaystyle (я, j)}$ $(я, j)$ ${\ displaystyle L \ times L}$ $L \ раз L$ ${\ displaystyle f_ {ij}}$ $f_ {ij}$ ${\ displaystyle (я, j)}$ $(я, j)$ ${\ displaystyle N}$ $N$

{\ displaystyle P_ {ij} = {\ frac {f_ {ij}} {N}}, \ qquad \ sum _ {i = 0} ^ {L-1} \ sum _ {j = 0} ^ {L- 1} P_ {ij} = 1}

{\ displaystyle P_ {ij} = {\ frac {f_ {ij}} {N}}, \ qquad \ sum _ {i = 0} ^ {L-1} \ sum _ {j = 0} ^ {L- 1} P_ {ij} = 1}

А метод 2-мерного Оцу разработан на основе 2-мерной гистограммы следующим образом.

Вероятности двух классов можно обозначить как:

{\ displaystyle {\ begin {align} \ omega _ {0} amp; = \ sum _ {i = 0} ^ {s-1} \ sum _ {j = 0} ^ {t-1} P_ {ij} \ \\ omega _ {1} amp; = \ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L-1} P_ {ij} \ end {выровнено}}}

{\ displaystyle {\ begin {align} \ omega _ {0} amp; = \ sum _ {i = 0} ^ {s-1} \ sum _ {j = 0} ^ {t-1} P_ {ij} \ \\ omega _ {1} amp; = \ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L-1} P_ {ij} \ end {выровнено}}}

Векторы среднего значения интенсивности двух классов и вектор полного среднего могут быть выражены следующим образом:

{\ displaystyle {\ begin {align} \ mu _ {0} amp; = [\ mu _ {0i}, \ mu _ {0j}] ^ {T} = \ left [\ sum _ {i = 0} ^ { s-1} \ sum _ {j = 0} ^ {t-1} i {\ frac {P_ {ij}} {\ omega _ {0}}}, \ sum _ {i = 0} ^ {s- 1} \ sum _ {j = 0} ^ {t-1} j {\ frac {P_ {ij}} {\ omega _ {0}}} \ right] ^ {T} \\\ mu _ {1} amp; = [\ mu _ {1i}, \ mu _ {1j}] ^ {T} = \ left [\ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L -1} i {\ frac {P_ {ij}} {\ omega _ {1}}}, \ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L-1 } j {\ frac {P_ {ij}} {\ omega _ {1}}} \ right] ^ {T} \\\ mu _ {T} amp; = [\ mu _ {Ti}, \ mu _ {Tj }] ^ {T} = \ left [\ sum _ {i = 0} ^ {L-1} \ sum _ {j = 0} ^ {L-1} iP_ {ij}, \ sum _ {i = 0 } ^ {L-1} \ sum _ {j = 0} ^ {L-1} jP_ {ij} \ right] ^ {T} \ end {align}}}

{\ displaystyle {\ begin {align} \ mu _ {0} amp; = [\ mu _ {0i}, \ mu _ {0j}] ^ {T} = \ left [\ sum _ {i = 0} ^ { s-1} \ sum _ {j = 0} ^ {t-1} i {\ frac {P_ {ij}} {\ omega _ {0}}}, \ sum _ {i = 0} ^ {s- 1} \ sum _ {j = 0} ^ {t-1} j {\ frac {P_ {ij}} {\ omega _ {0}}} \ right] ^ {T} \\\ mu _ {1} amp; = [\ mu _ {1i}, \ mu _ {1j}] ^ {T} = \ left [\ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L -1} i {\ frac {P_ {ij}} {\ omega _ {1}}}, \ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L-1 } j {\ frac {P_ {ij}} {\ omega _ {1}}} \ right] ^ {T} \\\ mu _ {T} amp; = [\ mu _ {Ti}, \ mu _ {Tj }] ^ {T} = \ left [\ sum _ {i = 0} ^ {L-1} \ sum _ {j = 0} ^ {L-1} iP_ {ij}, \ sum _ {i = 0 } ^ {L-1} \ sum _ {j = 0} ^ {L-1} jP_ {ij} \ right] ^ {T} \ end {align}}}

В большинстве случаев недиагональной вероятностью можно пренебречь, поэтому легко проверить:

{\ displaystyle \ omega _ {0} + \ omega _ {1} \ cong 1}

\ omega _ {0} + \ omega _ {1} \ cong 1

{\ displaystyle \ omega _ {0} \ mu _ {0} + \ omega _ {1} \ mu _ {1} \ cong \ mu _ {T}}

\ omega _ {0} \ mu _ {0} + \ omega _ {1} \ mu _ {1} \ cong \ mu _ {T}

Дискретная матрица между классами определяется как

{\ displaystyle S_ {b} = \ sum _ {k = 0} ^ {1} \ omega _ {k} [(\ mu _ {k} - \ mu _ {T}) (\ mu _ {k} - \ mu _ {T}) ^ {T}]}

S_ {b} = \ sum _ {k = 0} ^ {1} \ omega _ {k} [(\ mu _ {k} - \ mu _ {T}) (\ mu _ {k} - \ mu _ {T}) ^ {T}]

След дискретной матрицы можно выразить как

{\ displaystyle {\ begin {align} amp; \ operatorname {tr} (S_ {b}) \\ [4pt] = {} amp; \ omega _ {0} [(\ mu _ {0i} - \ mu _ {Ti }) ^ {2} + (\ mu _ {0j} - \ mu _ {Tj}) ^ {2}] + \ omega _ {1} [(\ mu _ {1i} - \ mu _ {Ti}) ^ {2} + (\ mu _ {1j} - \ mu _ {Tj}) ^ {2}] \\ [4pt] = {} amp; {\ frac {(\ mu _ {Ti} \ omega _ {0 } - \ mu _ {i}) ^ {2} + (\ mu _ {Tj} \ omega _ {0} - \ mu _ {j}) ^ {2}} {\ omega _ {0} (1- \ omega _ {0})}} \ конец {выровнено}}}

{\ displaystyle {\ begin {align} amp; \ operatorname {tr} (S_ {b}) \\ [4pt] = {} amp; \ omega _ {0} [(\ mu _ {0i} - \ mu _ {Ti }) ^ {2} + (\ mu _ {0j} - \ mu _ {Tj}) ^ {2}] + \ omega _ {1} [(\ mu _ {1i} - \ mu _ {Ti}) ^ {2} + (\ mu _ {1j} - \ mu _ {Tj}) ^ {2}] \\ [4pt] = {} amp; {\ frac {(\ mu _ {Ti} \ omega _ {0 } - \ mu _ {i}) ^ {2} + (\ mu _ {Tj} \ omega _ {0} - \ mu _ {j}) ^ {2}} {\ omega _ {0} (1- \ omega _ {0})}} \ конец {выровнено}}}

куда

{\ Displaystyle \ му _ {я} = \ сумма _ {я = 0} ^ {s-1} \ сумма _ {j = 0} ^ {t-1} iP_ {ij}}

{\ Displaystyle \ му _ {я} = \ сумма _ {я = 0} ^ {s-1} \ сумма _ {j = 0} ^ {t-1} iP_ {ij}}

{\ displaystyle \ mu _ {j} = \ sum _ {i = 0} ^ {s-1} \ sum _ {j = 0} ^ {t-1} jP_ {ij}}

{\ displaystyle \ mu _ {j} = \ sum _ {i = 0} ^ {s-1} \ sum _ {j = 0} ^ {t-1} jP_ {ij}}

Подобно одномерному методу Оцу, оптимальный порог получается путем максимизации. ${\ displaystyle (s, t)}$ $(с, т)$ ${\ displaystyle \ operatorname {tr} (S_ {b})}$ ${\ displaystyle \ operatorname {tr} (S_ {b})}$

Алгоритм

И получают итерационно, который подобен методу с одномерной OTSU в. Значения и изменяются до тех пор, пока не будет получено максимальное значение, то есть ${\ displaystyle s}$ $s$ ${\ displaystyle t}$ $т$ ${\ displaystyle s}$ $s$ ${\ displaystyle t}$ $т$ ${\ displaystyle \ operatorname {tr} (S_ {b})}$ ${\ displaystyle \ operatorname {tr} (S_ {b})}$

max,s,t = 0; for ss: 0 to L-1 do for tt: 0 to L-1 do evaluate tr(S_b); if tr(S_b) gt; max max = tr(S,b); s = ss; t = tt; end if end for end for return s,t;

Обратите внимание, что для оценки мы можем использовать алгоритм быстрого рекурсивного динамического программирования, чтобы улучшить временные характеристики. Однако даже при использовании подхода динамического программирования метод 2d Оцу все еще имеет большую временную сложность. Поэтому было проведено много исследований по снижению стоимости вычислений. ${\ displaystyle \ operatorname {tr} (S_ {b})}$ ${\ displaystyle \ operatorname {tr} (S_ {b})}$

Если таблицы с суммированными областями используются для построения 3 таблиц, суммирования, суммирования и суммирования, то сложность выполнения составляет максимум (O (N_pixels), O (N_bins * N_bins)). Обратите внимание, что если требуется только грубое разрешение с точки зрения порога, N_bins можно уменьшить. ${\ displaystyle P_ {ij}}$ $P_ {ij}$ ${\ displaystyle i * P_ {ij}}$ ${\ displaystyle i * P_ {ij}}$ ${\ displaystyle j * P_ {ij}}$ ${\ displaystyle j * P_ {ij}}$

См. Также: Таблица суммированных площадей

Реализация Matlab

функциональные входы и выходы:

hists - это двумерная гистограмма пары значений оттенков серого и среднего значения для окрестности. ${\ displaystyle 256 \ times 256}$ ${\ displaystyle 256 \ times 256}$

total - количество пар в данном изображении. Оно определяется количеством бинов 2D-гистограммы в каждом направлении.

порог - это полученный порог.

function threshold = otsu_2D(hists, total) maximum = 0.0; threshold = 0; helperVec = 0:255; mu_t0 = sum(sum(repmat(helperVec',1,256).*hists)); mu_t1 = sum(sum(repmat(helperVec,256,1).*hists)); p_0 = zeros(256); mu_i = p_0; mu_j = p_0; for ii = 1:256 for jj = 1:256 if jj == 1 if ii == 1 p_0(1,1) = hists(1,1); else p_0(ii,1) = p_0(ii-1,1) + hists(ii,1); mu_i(ii,1) = mu_i(ii-1,1)+(ii-1)*hists(ii,1); mu_j(ii,1) = mu_j(ii-1,1); end else p_0(ii,jj) = p_0(ii,jj-1)+p_0(ii-1,jj)-p_0(ii-1,jj-1)+hists(ii,jj); mu_i(ii,jj) = mu_i(ii,jj-1)+mu_i(ii-1,jj)-mu_i(ii-1,jj-1)+(ii-1)*hists(ii,jj); mu_j(ii,jj) = mu_j(ii,jj-1)+mu_j(ii-1,jj)-mu_j(ii-1,jj-1)+(jj-1)*hists(ii,jj); end if (p_0(ii,jj) == 0) continue; end if (p_0(ii,jj) == total) break; end tr = ((mu_i(ii,jj)-p_0(ii,jj)*mu_t0)^2 + (mu_j(ii,jj)-p_0(ii,jj)*mu_t1)^2)/(p_0(ii,jj)*(1-p_0(ii,jj))); if ( tr gt;= maximum) threshold = ii; maximum = tr; end end end end

использованная литература

внешние ссылки

Реализация метода пороговой обработки Оцу в виде подключаемого модуля GIMP с использованием Script-Fu (язык на основе схемы )
Конспект лекций по установлению пороговых значений - охватывает метод Оцу
Плагин для ImageJ, использующий метод Оцу для определения порога
Полное объяснение метода Оцу с рабочим примером и реализацией Java
Внедрение метода Оцу в ИТК
Otsu Thresholding в C # - простая реализация C # с объяснением
Метод Оцу с использованием MATLAB
Otsu Thresholding с scikit-изображением в Python