WikiDer > Метод отсуса - Википедия

Otsus method - Wikipedia
Пример изображения с пороговым значением с использованием алгоритма Оцу
Исходное изображение

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

Метод Оцу

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

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

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

Вероятность класса вычисляется из бины гистограммы:

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

который выражается через вероятности классов и класс означает , где класс означает , и находятся:

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

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

Алгоритм

  1. Вычислить гистограмму и вероятности каждого уровня интенсивности
  2. Настроить начальную и
  3. Пройдите через все возможные пороги максимальная интенсивность
    1. Обновлять и
    2. Вычислить
  4. Желаемый порог соответствует максимальному

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

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

функцияуровень =оцу(histogramCounts)общий = сумма(histogramCounts); % общее количество пикселей в изображении %% OTSU автоматическое определение порогаверх = 256;SumB = 0;wB = 0;максимум = 0.0;сумма1 = точка(0:верх-1, histogramCounts);за ii = 1:верх    wF = общий - wB;    если wB > 0 && wF > 0        мФ = (сумма1 - SumB) / wF;        вал = wB * wF * ((SumB / wB) - мФ) * ((SumB / wB) - мФ);        если ( вал >= максимум )            уровень = ii;            максимум = вал;        конец    конец    wB = wB + histogramCounts(ii);    SumB = SumB + (ii-1) * histogramCounts(ii);конецконец

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

Ограничения

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

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

Улучшения

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

Для каждого пикселя вычисляется среднее значение уровня серого для окрестности. Пусть уровень серого данного пикселя разделен на дискретные значения и средний уровень серого тоже делятся на одинаковые значения. Затем формируется пара: уровень серого пикселя и среднее значение окрестности . Каждая пара принадлежит одному из возможные двухмерные бункеры. Общее количество вхождений (частота), , пары , разделенное на общее количество пикселей в изображении , определяет совместную функцию масс вероятности в 2-мерной гистограмме:

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

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

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

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

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

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

куда

Подобно одномерному методу Оцу, оптимальный порог получается путем максимизации .

Алгоритм

В и получается итеративно, что аналогично одномерному методу Оцу. Ценности и изменяются до тех пор, пока мы не получим максимум , то есть

Максимум,s,т = 0;за SS: 0 к L-1 делать    за tt: 0 к L-1 делать        оценивать tr (S_b);        если tr (S_b) > Максимум            Максимум = tr(S,б);            s = SS;            т = тт;        конец если    конец законец завозвращаться s,т;

Обратите внимание, что для оценки , мы можем использовать алгоритм быстрого рекурсивного динамического программирования для улучшения временных характеристик.[9] Однако даже при использовании подхода динамического программирования метод 2d Оцу все еще имеет большую временную сложность. Таким образом, было проведено много исследований по снижению стоимости вычислений.[10]

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

Реализация Matlab

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

шипение это 2D-гистограмма пары значений оттенков серого и среднего значения для окрестности.

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

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

функцияпорог =otsu_2D(шистс, всего)максимум = 0.0;порог = 0;helperVec = 0:255;mu_t0 = сумма(сумма(повторять(helperVec',1,256).*шипение));mu_t1 = сумма(сумма(перематывать(helperVec,256,1).*шипение));p_0 = нули(256);mu_i = p_0;mu_j = p_0;за ii = 1:256    за jj = 1:256        если jj == 1            если ii == 1                p_0(1,1) = шипение(1,1);            еще                p_0 (ii, 1) = p_0(ii-1,1) + шипение(ii,1);                mu_i(ii,1) = mu_i(ii-1,1)+(ii-1)*шипение(ii,1);                mu_j(ii,1) = mu_j(ii-1,1);            конец        еще            p_0(ii,jj) = p_0(ii,jj-1)+p_0(ii-1,jj)-p_0(ii-1,jj-1)+шипение(ii,jj);            mu_i(ii,jj) = mu_i(ii,jj-1)+mu_i(ii-1,jj)-mu_i(ii-1,jj-1)+(ii-1)*шипение(ii,jj);            mu_j(ii,jj) = mu_j(ii,jj-1)+mu_j(ii-1,jj)-mu_j(ii-1,jj-1)+(jj-1)*шипение(ii,jj);        конец        если (p_0 (ii, jj) == 0)            Продолжить;        конец        если (p_0 (ii, jj) == общий)            перемена;        конец        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)));        если ( tr >= максимум )            порог = ii;            максимум = tr;        конец    конецконецконец

Рекомендации

  1. ^ М. Сезгин, Б. Санкур (2004). «Обзор методов определения порога изображения и количественная оценка эффективности». Журнал электронного изображения. 13 (1): 146–165. Дои:10.1117/1.1631315.
  2. ^ а б c Нобуюки Оцу (1979). «Метод выбора порога по гистограммам серого». IEEE Trans. Sys. Мужчина. Кибер. 9 (1): 62–66. Дои:10.1109 / TSMC.1979.4310076.
  3. ^ Лю, Дунцзю (2009). «Метод Оцу и К-средства». Девятая международная конференция по гибридным интеллектуальным системам IEEE. 1: 344–349.
  4. ^ Ляо, Пинг-Сун (2001). «Быстрый алгоритм многоуровневого определения порога» (PDF). J. Inf. Sci. Англ.. 17 (5): 713–727.
  5. ^ Хуан, Дэн-Юань (2009). «Оптимальное многоуровневое определение порога с использованием двухэтапного подхода оптимизации Otsu». Письма с распознаванием образов. 30 (3): 275–284. Дои:10.1016 / j.patrec.2008.10.003.
  6. ^ Киттлер, Йозеф и Иллингворт, Джон (1985). «По пороговому выбору с использованием критериев кластеризации». IEEE Transactions по системам, человеку и кибернетике. SMC-15 (5): 652–655. Дои:10.1109 / tsmc.1985.6313443.
  7. ^ Ли, Сан Ук и Чунг, Сок Юн и Пак, Рэ Хонг (1990). «Сравнительное исследование производительности нескольких глобальных пороговых методов сегментации». Компьютерное зрение, графика и обработка изображений. 52 (2): 171–190. Дои:10.1016 / 0734-189х (90) 90053-х.CS1 maint: несколько имен: список авторов (связь)
  8. ^ Цзяньчжуан, Лю и Вэньцин, Ли и Юпэн, Тянь (1991). «Автоматическая установка пороговых значений для изображений с уровнем серого с использованием двухмерного метода Оцу». Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on: 325–327.CS1 maint: несколько имен: список авторов (связь)
  9. ^ Чжан, Цзюнь и Ху, Цзинлу (2008). «Сегментация изображений на основе метода 2D Оцу с анализом гистограмм». Компьютерные науки и разработка программного обеспечения, Международная конференция 2008 г.. 6: 105–108. Дои:10.1109 / CSSE.2008.206. ISBN 978-0-7695-3336-0.
  10. ^ Чжу, Нинбо и Ван, Ганг и Ян, Гаобо и Дай, Веймин (2009). «Быстрый алгоритм определения пороговых значений 2d otsu, основанный на улучшенной гистограмме». Распознавание образов, 2009. CCPR 2009. Китайская конференция по: 1–5.CS1 maint: несколько имен: список авторов (связь)

внешняя ссылка