В области компьютерного зрения и обработке изображений , Метод Оцы , названное в честь Нобуюков Оцы (大津展之, Оца Нобуюки ) , используются для выполнения автоматического изображения порогового . [1] В простейшей форме алгоритм возвращает единый порог интенсивности, который разделяет пиксели на два класса: передний план и фон. Этот порог определяется путем минимизации дисперсии интенсивности внутри класса или, что эквивалентно, путем максимизации дисперсии между классами. [2] Метод Оцу представляет собой одномерный дискретный аналог дискриминантного анализа Фишера , связанный с методом оптимизации Дженкса., и эквивалентен глобально оптимальному k-среднему [3], выполненному на гистограмме интенсивности. Расширение многоуровневой пороговой обработки было описано в исходной статье [2], и с тех пор были предложены эффективные в вычислительном отношении реализации. [4] [5]
Метод Оцу
Алгоритм исчерпывающе ищет порог, который минимизирует внутриклассовую дисперсию, определяемую как взвешенная сумма дисперсий двух классов:
Вес а также - вероятности двух классов, разделенных порогом ,а также а также являются дисперсиями этих двух классов.
Вероятность класса вычисляется из бины гистограммы:
Для 2 классов минимизация внутриклассовой дисперсии эквивалентна максимизации межклассовой дисперсии: [2]
который выражается через вероятности классов и класс означает , где класс означает , а также находятся:
Несложно проверить следующие соотношения:
Вероятности классов и средние классы могут быть вычислены итеративно. Эта идея дает эффективный алгоритм.
Алгоритм
- Вычислить гистограмму и вероятности каждого уровня интенсивности
- Настроить начальную а также
- Пройдите через все возможные пороги максимальная интенсивность
- Обновлять а также
- Вычислить
- Желаемый порог соответствует максимальному
Реализация MATLAB или Octave
histogramCounts - это гистограмма из 256 элементов изображения в градациях серого с разными уровнями серого (типично для 8-битных изображений). level - это порог изображения (двойной).
уровень функции = otsu ( histogramCounts ) total = sum ( histogramCounts ); % общее количество пикселей в изображении %% OTSU автоматическое определение порогаверх = 256 ; sumB = 0 ; wB = 0 ; максимум = 0,0 ; sum1 = dot ( 0 : верх - 1 , histogramCounts ); для ii = 1 : верх wF = всего - wB ; если wB > 0 && wF > 0 mF = ( sum1 - sumB ) / wF ; Val = Wb * Wf * (( SUMB / Вб ) - мФ ) * (( SUMB / Вб ) - мФ ); если ( Val > = максимальная ) level = ii ; максимум = val ; конец конец wB = wB + histogramCounts ( ii ); sumB = sumB + ( ii - 1 ) * histogramCounts ( ii ); конецконец
Matlab имеет встроенные функции graythresh()
и multithresh()
в панели инструментов обработки изображений, которые реализованы с помощью метода Оцу и метода Мульти Оцу, соответственно.
Ограничения
Метод Оцу показывает относительно хорошие характеристики, если можно предположить, что гистограмма имеет бимодальное распределение и имеет глубокую и резкую впадину между двумя пиками. Но если площадь объекта мала по сравнению с областью фона, гистограмма больше не демонстрирует бимодальности. [6] И если отклонения интенсивности объекта и фона велики по сравнению со средней разницей, или изображение сильно искажено аддитивным шумом, резкая впадина гистограммы уровней серого ухудшается. Тогда возможно неверный порог, определенный методом Оцу, приводит к ошибке сегментации. (Здесь мы определяем размер объекта как отношение площади объекта ко всей области изображения, а среднюю разницу как разность средних интенсивностей объекта и фона)
Эмпирические результаты показывают, что производительность глобальных методов определения пороговых значений, используемых для сегментации объектов (включая метод Оцу), ограничена небольшим размером объекта, небольшой средней разницей между пикселями переднего и заднего плана, большой дисперсией пикселей, принадлежащих объекту, и пикселей, которые принадлежат ему. к фону, большое количество шума и т. д. [7]
Улучшения
Для устранения ограничений метода Оцу были разработаны различные расширения. Одним из популярных расширений является двухмерный метод Оцу , который лучше справляется с задачей сегментации объектов на зашумленных изображениях. Здесь значение интенсивности данного пикселя сравнивается со средней интенсивностью его ближайшего окружения, чтобы улучшить результаты сегментации. [8]
Для каждого пикселя вычисляется среднее значение уровня серого для окрестности. Пусть уровень серого данного пикселя разделен на дискретные значения и средний уровень серого тоже делятся на одинаковые значения. Затем формируется пара: уровень серого пикселя и среднее значение окрестности.. Каждая пара принадлежит одному извозможные 2-мерные бункеры. Общее количество вхождений (частота),, пары , разделенное на общее количество пикселей в изображении , определяет совместную функцию массы вероятностей на 2-мерной гистограмме:
А метод 2-мерного Оцу разработан на основе 2-мерной гистограммы следующим образом.
Вероятности двух классов можно обозначить как:
Векторы среднего значения интенсивности двух классов и вектор полного среднего могут быть выражены следующим образом:
В большинстве случаев недиагональной вероятностью можно пренебречь, поэтому легко проверить:
Дискретная матрица между классами определяется как
След дискретной матрицы можно выразить как
где
Подобно одномерному методу Оцу, оптимальный порог получается путем максимизации .
Алгоритм
В а также получается итеративно, что аналогично одномерному методу Оцу. Ценности а также изменяются до тех пор, пока мы не получим максимум , это
max , s , t = 0 ; для сс : от 0 до L - 1 сделать для tt : от 0 до L - 1 сделать оценить tr ( S_b ); если tr ( S_b ) > max макс = tr ( S , b ); s = ss ; t = tt ; конец, если конец для конец для return s , t ;
Обратите внимание, что для оценки , мы можем использовать алгоритм быстрого рекурсивного динамического программирования для улучшения временных характеристик. [9] Однако даже при использовании подхода динамического программирования метод 2d Оцу все еще имеет большую временную сложность. Поэтому было проведено много исследований по снижению стоимости вычислений. [10]
Если для построения трех таблиц используются таблицы суммированных площадей, суммируйте , сумма более , и суммировать , то сложность выполнения будет максимальной (O (N_pixels), O (N_bins * N_bins)). Обратите внимание, что если требуется только грубое разрешение с точки зрения порога, N_bins можно уменьшить.
Реализация Matlab
функциональные входы и выходы:
hists - это 2D-гистограмма пары значений оттенков серого и среднего значения для окрестности.
total - количество пар в данном изображении. Оно определяется количеством бинов 2D-гистограммы в каждом направлении.
порог - это полученный порог.
порог функции = otsu_2D ( hists, total ) максимум = 0,0 ; порог = 0 ; helperVec = 0 : 255 ; mu_t0 = сумма ( сумма ( repmat ( helperVec ' , 1 , 256 ) . * hists )); mu_t1 = сумма ( сумма ( repmat ( helperVec , 256 , 1 ) . * hists )); 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 ) = hists ( 1 , 1 ); еще 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 ); конец еще 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 ); конец если ( p_0 ( ii , jj ) == 0 ) продолжить ; конец если ( p_0 ( ii , jj ) == total ) перерыв ; конец 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 ; максимум = тр ; конец конецконецконец
Рекомендации
- ^ М. Сезгин и Б. Санкур (2004). «Обзор методов определения порога изображения и количественная оценка эффективности». Журнал электронного изображения . 13 (1): 146–165. DOI : 10.1117 / 1.1631315 .
- ^ а б в Нобуюки Оцу (1979). «Метод выбора порога по гистограммам серого». IEEE Trans. Sys. Мужчина. Кибер . 9 (1): 62–66. DOI : 10.1109 / TSMC.1979.4310076 .
- ^ Лю, Дунцзю (2009). «Метод Оцу и К-средства». Девятая международная конференция по гибридным интеллектуальным системам IEEE . 1 : 344–349.
- ^ Ляо, Пин-Сун (2001). «Быстрый алгоритм многоуровневого определения порога» (PDF) . J. Inf. Sci. Англ . 17 (5): 713–727. Архивировано из оригинального (PDF) на 24.06.2019.
- ^ Хуан, Дэн-Юань (2009). «Оптимальное многоуровневое определение порога с использованием двухэтапного подхода оптимизации Otsu». Письма о распознавании образов . 30 (3): 275–284. DOI : 10.1016 / j.patrec.2008.10.003 .
- ^ Киттлер, Йозеф и Иллингворт, Джон (1985). «По пороговому выбору с использованием критериев кластеризации». IEEE Transactions по системам, человеку и кибернетике . SMC-15 (5): 652–655. DOI : 10.1109 / tsmc.1985.6313443 .
- ^ Ли, Сан Ук и Чунг, Сок Юн и Пак, Рэ Хонг (1990). «Сравнительное исследование производительности нескольких глобальных пороговых методов сегментации». Компьютерное зрение, графика и обработка изображений . 52 (2): 171–190. DOI : 10.1016 / 0734-189x (90) 90053-X .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Цзяньчжуан, Лю и Вэньцин, Ли и Юпэн, Тянь (1991). «Автоматическая установка пороговых значений для изображений с уровнем серого с использованием двумерного метода Оцу». Схемы и системы, 1991. Труды конференции, Китай., 1991 Международная конференция по : 325–327.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Чжан, Цзюнь и Ху, Цзинлу (2008). «Сегментация изображений на основе метода 2D Оцу с анализом гистограмм». Компьютерные науки и Software Engineering, 2008 Международная конференция по . 6 : 105–108. DOI : 10,1109 / CSSE.2008.206 . ISBN 978-0-7695-3336-0.
- ^ Чжу, Нинбо и Ван, Ганг и Ян, Гаобо и Дай, Веймин (2009). «Быстрый алгоритм определения пороговых значений 2d otsu, основанный на улучшенной гистограмме». Распознавание образов, 2009. CCPR 2009. Китайская конференция по : 1–5.CS1 maint: несколько имен: список авторов ( ссылка )
Внешние ссылки
- Реализация метода пороговой обработки Оцу в виде подключаемого модуля GIMP с использованием Script-Fu (язык на основе схемы )
- Конспект лекций по установлению пороговых значений - охватывает метод Оцу
- Плагин для ImageJ, использующий метод Оцу для определения порога
- Полное объяснение метода Оцу с рабочим примером и реализацией на Java.
- Внедрение метода Оцу в ИТК
- Otsu Thresholding в C # - простая реализация C # с объяснением
- Метод Оцу с использованием MATLAB
- Otsu Thresholding с scikit-изображением в Python