Здравствуйте, уважаемые хабрачитатели и хабракритики. Этот пост я хотел бы посвятить такой актуальной на сегодняшний день теме, как обнаружение объектов на изображениях.
В качестве одного из алгоритмов такого обнаружения рассмотрим выбор порога быстрым и эффективным методом Оцу.
Итак, начнем по порядку. Вообще, задача обнаружения объектов заключается в установлении наличия на изображении объекта, обладающего некоторыми определенными характеристиками.
Такой характеристикой может быть, например, яркость. Одним из наиболее простых и естественных способов обнаружения объекта (или объектов) является выбор порога по яркости, или пороговая классификация (thresholding). Смысл такого порога заключается в том, чтобы разделить изображение на светлый объект (foreground) и темный фон (background). Т.е. объект — это совокупность тех пикселей, яркость которых превышает порог (I > T), а фон — совокупность остальных пикселей, яркость которых ниже порога (I < T).
Таким образом, ключевой параметр — это порог T. Как его выбирать?
Существуют десятки методов выбор порога. Быстрым и эффективным методом является метод, придуманный японским ученым Нобуюки Оцу в 1979 году. О нем то и пойдет речь далее.
Пусть имеется 8-битное изображение, для которого требуется вычислить порог T. В случае 24-битной картинки, ее легко перегнать в 8-битную с помощью приведения к серому (grayscale):
I = 0.2125 R + 0.7154 G + 0.0721 B
Метод Оцу (Otsu's Method) использует гистограмму изображения для расчета порога. Напомню, что гистограмма — это набор бинов, каждый из которых характеризует количество попаданий в него элементов выборки. В нашем случае выборка — это пиксели различной яркости, которая может принимать целые значения от 0 до 255.
Пример изображения с объектом:
Гистограмма для такого изображения:
Из гистограммы человек легко видит, что имеется два четко разделяющихся класса. Суть метода Оцу заключается в том, чтобы выставить порог между классами таким образом, чтобы каждый их них был как можно более «плотным». Если выражаться математическим языком, то это сводится к минимизации внутриклассовой дисперсии, которая определяется как взвешенная сумма дисперсий двух классов:
Здесь w1 и w2 — вероятности первого и второго классов соответственно.
В своей работе Оцу показывает, что минимизация внутриклассовой дисперсии эквивалента максимизации межклассовой дисперсии, которая равна:
В этой формуле a1 и a2 — средние арифметические значения для каждого из классов.
Особенность этой формулы заключается в том, что w1(t + 1), w2(t + 1), a1(t + 1), a2(t + 1) легко выражаются через предыдущие значения w1(t), w2(t), a1(t), a2(t) (t — текущий порог). Эта особенность позволила разработать быстрый алгоритм:
Естественно, это лишь общее описание алгоритма. В точной реализации можно сделать массу оптимизаций. Например, проход через гистограмму можно (и нужно) делать не от 1 до 254, а от минимальной до максимальной яркости минус единица. В конце будет приведена реализация на языке C++ с учетом некоторых таких оптимизаций.
Вот такой результат дает реализация вышеописанного алгоритма:
Расчитанный порог:
Хотелось бы также кроме искусственно сгенерированного примера показать и реальное
использование метода.
В моей текущей дипломной работе требуется локализация штрих-кода на изображении:
Перед тем как использовать метод Оцу, нужно сделать предобработку, чтобы как-то учесть особенности структуры одномерного штрих-кода. Если ее не сделать, то метод просто-напросто ничего не даст. Особенность же структуры штрих-кода состоит в том, что он состоит из вертикальных полос, и поэтому имеет большие горизонтальные производные и маленькие вертикальные. Поэтому, если взять изображение как разницу горизонтальной и вертикальной производной, а дальше применить усредняющий фильтр, то получится вот что:
Неплохо, да? Образ штрих-кода четко проглядывается на изображении и выделяется значительно более высокой яркостью по сравнению с окружающими предметами. Вот теперь можно смело применять метод Оцу:
В результате получили правильно локализованный штрих-код.
Ну, как я и обещал, реализация расчета порога методом Оцу на языке C++ с комментариями:
Итак, мы рассмотрели применение метода Оцу для обнаружения объектов на изображениях. Достоинствами этого метода являются:
В качестве одного из алгоритмов такого обнаружения рассмотрим выбор порога быстрым и эффективным методом Оцу.
Введение
Итак, начнем по порядку. Вообще, задача обнаружения объектов заключается в установлении наличия на изображении объекта, обладающего некоторыми определенными характеристиками.
Такой характеристикой может быть, например, яркость. Одним из наиболее простых и естественных способов обнаружения объекта (или объектов) является выбор порога по яркости, или пороговая классификация (thresholding). Смысл такого порога заключается в том, чтобы разделить изображение на светлый объект (foreground) и темный фон (background). Т.е. объект — это совокупность тех пикселей, яркость которых превышает порог (I > T), а фон — совокупность остальных пикселей, яркость которых ниже порога (I < T).
Таким образом, ключевой параметр — это порог T. Как его выбирать?
Существуют десятки методов выбор порога. Быстрым и эффективным методом является метод, придуманный японским ученым Нобуюки Оцу в 1979 году. О нем то и пойдет речь далее.
Метод Оцу
Пусть имеется 8-битное изображение, для которого требуется вычислить порог T. В случае 24-битной картинки, ее легко перегнать в 8-битную с помощью приведения к серому (grayscale):
I = 0.2125 R + 0.7154 G + 0.0721 B
Метод Оцу (Otsu's Method) использует гистограмму изображения для расчета порога. Напомню, что гистограмма — это набор бинов, каждый из которых характеризует количество попаданий в него элементов выборки. В нашем случае выборка — это пиксели различной яркости, которая может принимать целые значения от 0 до 255.
Пример изображения с объектом:
Гистограмма для такого изображения:
Из гистограммы человек легко видит, что имеется два четко разделяющихся класса. Суть метода Оцу заключается в том, чтобы выставить порог между классами таким образом, чтобы каждый их них был как можно более «плотным». Если выражаться математическим языком, то это сводится к минимизации внутриклассовой дисперсии, которая определяется как взвешенная сумма дисперсий двух классов:
Здесь w1 и w2 — вероятности первого и второго классов соответственно.
В своей работе Оцу показывает, что минимизация внутриклассовой дисперсии эквивалента максимизации межклассовой дисперсии, которая равна:
В этой формуле a1 и a2 — средние арифметические значения для каждого из классов.
Особенность этой формулы заключается в том, что w1(t + 1), w2(t + 1), a1(t + 1), a2(t + 1) легко выражаются через предыдущие значения w1(t), w2(t), a1(t), a2(t) (t — текущий порог). Эта особенность позволила разработать быстрый алгоритм:
- Вычисляем гистограмму (один проход через массив пикселей). Дальше нужна только гистограмма; проходов по всему изображению больше не требуется.
- Начиная с порога t = 1, проходим через всю гистограмму, на каждом шаге пересчитывая дисперсию σb(t). Если на каком-то из шагов дисперсия оказалась больше максимума, то обновляем дисперсию и T = t.
- Искомый порог равен T.
Естественно, это лишь общее описание алгоритма. В точной реализации можно сделать массу оптимизаций. Например, проход через гистограмму можно (и нужно) делать не от 1 до 254, а от минимальной до максимальной яркости минус единица. В конце будет приведена реализация на языке C++ с учетом некоторых таких оптимизаций.
Вот такой результат дает реализация вышеописанного алгоритма:
Расчитанный порог:
Реальный пример
Хотелось бы также кроме искусственно сгенерированного примера показать и реальное
использование метода.
В моей текущей дипломной работе требуется локализация штрих-кода на изображении:
Перед тем как использовать метод Оцу, нужно сделать предобработку, чтобы как-то учесть особенности структуры одномерного штрих-кода. Если ее не сделать, то метод просто-напросто ничего не даст. Особенность же структуры штрих-кода состоит в том, что он состоит из вертикальных полос, и поэтому имеет большие горизонтальные производные и маленькие вертикальные. Поэтому, если взять изображение как разницу горизонтальной и вертикальной производной, а дальше применить усредняющий фильтр, то получится вот что:
Неплохо, да? Образ штрих-кода четко проглядывается на изображении и выделяется значительно более высокой яркостью по сравнению с окружающими предметами. Вот теперь можно смело применять метод Оцу:
В результате получили правильно локализованный штрих-код.
Реализация на C++
Ну, как я и обещал, реализация расчета порога методом Оцу на языке C++ с комментариями:
- typedef unsigned char imageInt;
-
- // Определение порога методом Оцу
- int otsuThreshold(imageInt *image, int size)
- {
- // Проверки на NULL и проч. опустим, чтобы сконцетрироваться
- // на работе метода
-
- // Посчитаем минимальную и максимальную яркость всех пикселей
- int min = image[0];
- int max = image[0];
-
- for (int i = 1; i < size; i++)
- {
- int value = image[i];
-
- if (value < min)
- min = value;
-
- if (value > max)
- max = value;
- }
-
- // Гистограмма будет ограничена снизу и сверху значениями min и max,
- // поэтому нет смысла создавать гистограмму размером 256 бинов
- int histSize = max - min + 1;
- int* hist = new int[histSize];
-
- // Заполним гистограмму нулями
- for (int t = 0; t < histSize; t++)
- hist[t] = 0;
-
- // И вычислим высоту бинов
- for (int i = 0; i < size; i++)
- hist[image[i] - min]++;
-
- // Введем два вспомогательных числа:
- int m = 0; // m - сумма высот всех бинов, домноженных на положение их середины
- int n = 0; // n - сумма высот всех бинов
- for (int t = 0; t <= max - min; t++)
- {
- m += t * hist[t];
- n += hist[t];
- }
-
- float maxSigma = -1; // Максимальное значение межклассовой дисперсии
- int threshold = 0; // Порог, соответствующий maxSigma
-
- int alpha1 = 0; // Сумма высот всех бинов для класса 1
- int beta1 = 0; // Сумма высот всех бинов для класса 1, домноженных на положение их середины
-
- // Переменная alpha2 не нужна, т.к. она равна m - alpha1
- // Переменная beta2 не нужна, т.к. она равна n - alpha1
-
- // t пробегается по всем возможным значениям порога
- for (int t = 0; t < max - min; t++)
- {
- alpha1 += t * hist[t];
- beta1 += hist[t];
-
- // Считаем вероятность класса 1.
- float w1 = (float)beta1 / n;
- // Нетрудно догадаться, что w2 тоже не нужна, т.к. она равна 1 - w1
-
- // a = a1 - a2, где a1, a2 - средние арифметические для классов 1 и 2
- float a = (float)alpha1 / beta1 - (float)(m - alpha1) / (n - beta1);
-
- // Наконец, считаем sigma
- float sigma = w1 * (1 - w1) * a * a;
-
- // Если sigma больше текущей максимальной, то обновляем maxSigma и порог
- if (sigma > maxSigma)
- {
- maxSigma = sigma;
- threshold = t;
- }
- }
-
- // Не забудем, что порог отсчитывался от min, а не от нуля
- threshold += min;
-
- // Все, порог посчитан, возвращаем его наверх :)
- return threshold;
- }
* This source code was highlighted with Source Code Highlighter.Заключение
Итак, мы рассмотрели применение метода Оцу для обнаружения объектов на изображениях. Достоинствами этого метода являются:
- Простота реализации.
- Метод хорошо адаптируется к различного рода изображения, выбирая наиболее оптимальный порог.
- Быстрое время выполнения. Требуется O(N) операций, где N — количество пикселей в изображении.
- Метод не имеет никаких параметров, просто берете и применяете его. В MatLab это функция graythresh() без аргументов (Почему я привел пример именно MatLab? Просто этот инструмент — стандарт де-факто для обработки изображений).
- Сама по себе пороговая бинаризация чувствительна к неравномерной яркости изображения. Решением такой проблемы может быть введение локальных порогов, вместо одного глобального.
Источники
- Otsu, N., «A Threshold Selection Method from Gray-Level Histograms,» IEEE Transactions on Systems, Man, and Cybernetics, Vol. 9, No. 1, 1979, pp. 62-66.
- Википедия
- Записки лектора (англ.)
- Сайт людей, которые придумали эффективный алгоритм распознавания штрих-кода UPC (англ.)
