Pull to refresh

Обнаружение объектов методом Оцу

Image processing *
Sandbox
Здравствуйте, уважаемые хабрачитатели и хабракритики. Этот пост я хотел бы посвятить такой актуальной на сегодняшний день теме, как обнаружение объектов на изображениях.
В качестве одного из алгоритмов такого обнаружения рассмотрим выбор порога быстрым и эффективным методом Оцу.


Введение


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

Такой характеристикой может быть, например, яркость. Одним из наиболее простых и естественных способов обнаружения объекта (или объектов) является выбор порога по яркости, или пороговая классификация (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. Вычисляем гистограмму (один проход через массив пикселей). Дальше нужна только гистограмма; проходов по всему изображению больше не требуется.
  2. Начиная с порога t = 1, проходим через всю гистограмму, на каждом шаге пересчитывая дисперсию σb(t). Если на каком-то из шагов дисперсия оказалась больше максимума, то обновляем дисперсию и T = t.
  3. Искомый порог равен T.

Естественно, это лишь общее описание алгоритма. В точной реализации можно сделать массу оптимизаций. Например, проход через гистограмму можно (и нужно) делать не от 1 до 254, а от минимальной до максимальной яркости минус единица. В конце будет приведена реализация на языке C++ с учетом некоторых таких оптимизаций.

Вот такой результат дает реализация вышеописанного алгоритма:


Расчитанный порог:


Реальный пример


Хотелось бы также кроме искусственно сгенерированного примера показать и реальное
использование метода.

В моей текущей дипломной работе требуется локализация штрих-кода на изображении:


Перед тем как использовать метод Оцу, нужно сделать предобработку, чтобы как-то учесть особенности структуры одномерного штрих-кода. Если ее не сделать, то метод просто-напросто ничего не даст. Особенность же структуры штрих-кода состоит в том, что он состоит из вертикальных полос, и поэтому имеет большие горизонтальные производные и маленькие вертикальные. Поэтому, если взять изображение как разницу горизонтальной и вертикальной производной, а дальше применить усредняющий фильтр, то получится вот что:


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


В результате получили правильно локализованный штрих-код.

Реализация на C++


Ну, как я и обещал, реализация расчета порога методом Оцу на языке C++ с комментариями:
  1. typedef unsigned char imageInt;
  2.  
  3. // Определение порога методом Оцу
  4. int otsuThreshold(imageInt *image, int size)
  5. {
  6.   // Проверки на NULL и проч. опустим, чтобы сконцетрироваться
  7.   // на работе метода
  8.  
  9.   // Посчитаем минимальную и максимальную яркость всех пикселей
  10.   int min = image[0];
  11.   int max = image[0];
  12.  
  13.   for (int i = 1; i < size; i++)
  14.   {
  15.     int value = image[i];
  16.  
  17.     if (value < min)
  18.       min = value;
  19.  
  20.     if (value > max)
  21.       max = value;
  22.   }
  23.  
  24.   // Гистограмма будет ограничена снизу и сверху значениями min и max,
  25.   // поэтому нет смысла создавать гистограмму размером 256 бинов
  26.   int histSize = max - min + 1;
  27.   int* hist = new int[histSize];
  28.  
  29.   // Заполним гистограмму нулями
  30.   for (int t = 0; t < histSize; t++)
  31.     hist[t] = 0;
  32.  
  33.   // И вычислим высоту бинов
  34.   for (int i = 0; i < size; i++)
  35.     hist[image[i] - min]++;
  36.  
  37.   // Введем два вспомогательных числа:
  38.   int m = 0; // m - сумма высот всех бинов, домноженных на положение их середины
  39.   int n = 0; // n - сумма высот всех бинов
  40.   for (int t = 0; t <= max - min; t++)
  41.   {
  42.     m += t * hist[t];
  43.     n += hist[t];
  44.   }
  45.  
  46.   float maxSigma = -1; // Максимальное значение межклассовой дисперсии
  47.   int threshold = 0; // Порог, соответствующий maxSigma
  48.  
  49.   int alpha1 = 0; // Сумма высот всех бинов для класса 1
  50.   int beta1 = 0; // Сумма высот всех бинов для класса 1, домноженных на положение их середины
  51.  
  52.   // Переменная alpha2 не нужна, т.к. она равна m - alpha1
  53.   // Переменная beta2 не нужна, т.к. она равна n - alpha1
  54.  
  55.   // t пробегается по всем возможным значениям порога
  56.   for (int t = 0; t < max - min; t++)
  57.   {
  58.     alpha1 += t * hist[t];
  59.     beta1 += hist[t];
  60.  
  61.     // Считаем вероятность класса 1.
  62.     float w1 = (float)beta1 / n;
  63.     // Нетрудно догадаться, что w2 тоже не нужна, т.к. она равна 1 - w1
  64.  
  65.     // a = a1 - a2, где a1, a2 - средние арифметические для классов 1 и 2
  66.     float a = (float)alpha1 / beta1 - (float)(m - alpha1) / (n - beta1);
  67.     
  68.     // Наконец, считаем sigma
  69.     float sigma = w1 * (1 - w1) * a * a;
  70.  
  71.     // Если sigma больше текущей максимальной, то обновляем maxSigma и порог
  72.     if (sigma > maxSigma)
  73.     {
  74.       maxSigma = sigma;
  75.       threshold = t;
  76.     }
  77.   }
  78.  
  79.   // Не забудем, что порог отсчитывался от min, а не от нуля
  80.   threshold += min;
  81.  
  82.   // Все, порог посчитан, возвращаем его наверх :)
  83.   return threshold;
  84. }
* This source code was highlighted with Source Code Highlighter.


Заключение


Итак, мы рассмотрели применение метода Оцу для обнаружения объектов на изображениях. Достоинствами этого метода являются:
  1. Простота реализации.
  2. Метод хорошо адаптируется к различного рода изображения, выбирая наиболее оптимальный порог.
  3. Быстрое время выполнения. Требуется O(N) операций, где N — количество пикселей в изображении.
  4. Метод не имеет никаких параметров, просто берете и применяете его. В MatLab это функция graythresh() без аргументов (Почему я привел пример именно MatLab? Просто этот инструмент — стандарт де-факто для обработки изображений).
Недостатки:
  1. Сама по себе пороговая бинаризация чувствительна к неравномерной яркости изображения. Решением такой проблемы может быть введение локальных порогов, вместо одного глобального.

Источники

  1. 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.
  2. Википедия
  3. Записки лектора (англ.)
  4. Сайт людей, которые придумали эффективный алгоритм распознавания штрих-кода UPC (англ.)
Tags: image processingotsubarcode
Hubs: Image processing
Total votes 121: ↑117 and ↓4 +113
Comments 33
Comments Comments 33

Popular right now