Метод Оцу - Otsu's method

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

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

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

Метод Оцу

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

1. Вычислить гистограмму и вероятности каждого уровня интенсивности
2. Настройте начальную и${\ displaystyle \ omega _ {я} (0)}$${\ Displaystyle \ му _ {я} (0)}$
3. Пройдите через все возможные пороги максимальной интенсивности ${\ Displaystyle т = 1, \ ldots}$
   1. Обновление и${\ displaystyle \ omega _ {я}}$${\ Displaystyle \ mu _ {я}}$
   2. Вычислить ${\ Displaystyle \ sigma _ {b} ^ {2} (т)}$
4. Желаемый порог соответствует максимальному ${\ Displaystyle \ 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 > 0 && wF > 0
        mF = (sum1 - sumB) / wF;
        val = wB * wF * ((sumB / wB) - mF) * ((sumB / wB) - mF);
        if ( val >= 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}$${\ displaystyle L}$${\ displaystyle (я, j)}$${\ displaystyle L \ times L}$${\ displaystyle f_ {ij}}$${\ displaystyle (я, j)}$${\ displaystyle N}$

${\ 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} & = \ sum _ {i = 0} ^ {s-1} \ sum _ {j = 0} ^ {t-1} P_ {ij} \ \\ omega _ {1} & = \ sum _ {i = s} ^ {L-1} \ sum _ {j = t} ^ {L-1} P_ {ij} \ end {выровнено}}}$

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

${\ displaystyle {\ begin {align} \ mu _ {0} & = [\ 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} & = [\ 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} & = [\ 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}$

${\ displaystyle \ 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}]}$

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

${\ displaystyle {\ begin {align} & \ operatorname {tr} (S_ {b}) \\ [4pt] = {} & \ 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] = {} & {\ 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 \ mu _ {j} = \ sum _ {i = 0} ^ {s-1} \ sum _ {j = 0} ^ {t-1} jP_ {ij}}$

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

Алгоритм

И получают итерационно , который подобен методу с одномерной OTSU в. Значения и изменяются до тех пор, пока не будет получено максимальное значение , то есть ${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t}$${\ 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) > max
            max = tr(S,b);
            s = ss;
            t = tt;
        end if
    end for
end for
return s,t;

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

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

Реализация Matlab

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

hists - это двумерная гистограмма пары значений оттенков серого и среднего значения для окрестности. ${\ 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 >= maximum )
            threshold = ii;
            maximum = tr;
        end
    end
end
end

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

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

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