Алгоритм Otsu

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

История

Алгоритм был разработан Нобуюки Оцу (Nobuyuki Otsu) и впервые опубликован в 1979 году в статье «A Threshold Selection Method from Gray-Level Histograms» в журнале IEEE Transactions on Systems, Man, and Cybernetics. До появления этого метода порог бинаризации часто задавался вручную или с помощью эвристических правил, что было трудоёмко и не гарантировало оптимальности. Алгоритм Оцу стал первым широко распространённым автоматическим методом, не требующим вмешательства оператора. Он быстро завоевал популярность в задачах компьютерного зрения, медицинской визуализации, анализа документов и промышленного контроля качества благодаря своей простоте, эффективности и отсутствию необходимости в обучающих данных.

Принцип работы

Алгоритм Оцу работает с гистограммой яркости изображения, которая представляет собой распределение количества пикселей по каждому уровню серого (от 0 до 255 для 8-битного изображения). Основная идея заключается в том, чтобы найти порог t, который разделяет гистограмму на два класса: C0 (пиксели с яркостью меньше или равной t) и C1 (пиксели с яркостью больше t).

Математическая основа

Алгоритм вычисляет следующие статистики для каждого возможного порога t от 0 до 255:

1. Вероятность класса:

• ω0(t) = Σ p(i) для i от 0 до t — доля пикселей, принадлежащих классу C0.
• ω1(t) = Σ p(i) для i от t+1 до 255 — доля пикселей, принадлежащих классу C1.
• Здесь p(i) — вероятность уровня яркости i (количество пикселей с яркостью i, делённое на общее количество пикселей).

1. Средняя яркость класса:

• μ0(t) = (Σ i * p(i)) / ω0(t) для i от 0 до t.
• μ1(t) = (Σ i * p(i)) / ω1(t) для i от t+1 до 255.

1. Общая средняя яркость изображения: μT = Σ i * p(i) для i от 0 до 255.

1. Внутриклассовая дисперсия (мера разброса яркостей внутри каждого класса):

• σ²W(t) = ω0(t) σ²0(t) + ω1(t) σ²1(t), где σ²0(t) и σ²1(t) — дисперсии яркостей внутри классов C0 и C1 соответственно.

1. Межклассовая дисперсия (мера различия между средними яркостями классов):

• σ²B(t) = ω0(t) ω1(t) (μ0(t) - μ1(t))².

Алгоритм Оцу находит порог t, который максимизирует межклассовую дисперсию σ²B(t) или, что эквивалентно, минимизирует внутриклассовую дисперсию σ²W(t). Максимизация межклассовой дисперсии означает, что средние яркости двух классов максимально разнесены, что обеспечивает наилучшее разделение.

Вычислительная сложность

Наивная реализация алгоритма требует вычисления статистик для каждого из 256 возможных порогов, что даёт сложность O(N * L), где N — количество пикселей, а L — количество уровней серого (обычно 256). Однако существуют эффективные рекуррентные формулы, позволяющие вычислять ω0(t), μ0(t) и σ²B(t) за один проход по гистограмме, что снижает сложность до O(N + L). В современных реализациях алгоритм выполняется практически мгновенно для изображений размером до нескольких мегапикселей.

Применение

Алгоритм Оцу широко используется в различных областях обработки изображений и компьютерного зрения:

Бинаризация изображений

Основное применение — преобразование полутонового изображения в бинарное (чёрно-белое). Это необходимо для задач:

• Распознавание текста (OCR): выделение символов на сканированных документах или фотографиях.
• Анализ медицинских снимков: сегментация клеток, тканей или патологий на рентгенограммах, МРТ и КТ.
• Промышленный контроль: обнаружение дефектов, трещин или посторонних объектов на поверхности изделий.
• Обработка спутниковых снимков: выделение водных объектов, дорог или растительности.

Предварительная обработка

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

• Выделение контуров: бинарное изображение, полученное с помощью метода Оцу, упрощает поиск границ объектов.
• Сегментация изображений: служит быстрым и простым способом грубой сегментации на два класса.
• Улучшение качества изображения: может применяться для коррекции освещения или контраста.

Ограничения и модификации

Несмотря на свою популярность, алгоритм Оцу имеет ограничения:

• Предположение о бимодальности: алгоритм работает наилучшим образом, когда гистограмма изображения имеет два чётко разделённых пика (бимодальное распределение). Если гистограмма унимодальна (один пик) или мультимодальна (много пиков), результат может быть неудовлетворительным.
• Чувствительность к шуму: шум и неравномерное освещение могут исказить гистограмму и привести к неправильному выбору порога.
• Неравномерные размеры классов: если один из классов (например, фон) значительно больше другого (объект), алгоритм может сместить порог в сторону большего класса.

Для преодоления этих ограничений были разработаны модификации, такие как:

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

Пример работы

Рассмотрим полутоновое изображение размером 100x100 пикселей. Гистограмма яркости имеет два пика: один около 50 (тёмные пиксели — объект) и другой около 200 (светлые пиксели — фон). Алгоритм Оцу перебирает все возможные пороги от 0 до 255 и вычисляет межклассовую дисперсию. Максимальное значение σ²B(t) будет достигнуто при пороге, который наилучшим образом разделяет эти два пика, например, при t = 120. Все пиксели с яркостью ≤ 120 становятся чёрными (0), а с яркостью > 120 — белыми (255). В результате получается бинарное изображение, где объект чётко отделён от фона.

Критика

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

Источники

1. Otsu, N. (1979). A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics, 9(1), 62-66.
2. Gonzalez, R. C., & Woods, R. E. (2018). Digital Image Processing (4th ed.). Pearson.
3. Sezgin, M., & Sankur, B. (2004). Survey over image thresholding techniques and quantitative performance evaluation. Journal of Electronic Imaging, 13(1), 146-168.