Приложение в твоем смартфоне
Приложение в твоем смартфоне
Приложение в твоем смартфоне
Приложение в твоем смартфоне
18 января 2011 в 17:41

Обнаружение объектов методом Оцу из песочницы

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


Введение


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

Такой характеристикой может быть, например, яркость. Одним из наиболее простых и естественных способов обнаружения объекта (или объектов) является выбор порога по яркости, или пороговая классификация (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 (англ.)
+113
4628
197
orionll 26,5

комментарии (33)

+1
Airog, #
Спасибо, очень интересная статья и алгоритм нужный
0
sdaemon, #
Спасибо! Действительно очень полезно!
+4
kosiakk, #
Здорово.
А работает ли вычитание производных если штрих-код сфотографирован под углом? А для QR-кодов?

Вдобавок хочу дать ссылку на открытый проект ZXing, где ребята из Гугла реализовали чтение множества типов штрих-кодов с фотографий:
code.google.com/p/zxing/
В частности очень популярно их приложение для Android.
0
orionll, #
>> А работает ли вычитание производных если штрих-код сфотографирован под углом?
Как говорят авторы алгоритма, алгоритм хорошо работает в диапазоне наклонов от -30° до +30°. Что довольно неплохо, ИМХО.

>> А для QR-кодов?
Описанный выше алгоритм работает только для 1D штрих-кодов.
Хотя ничто не мешает изменить алгоритм под QR-коды: вместо вычитания сделать сложение производных (в QR-кодах есть и горизонтальные, и вертикальные градиенты).

>> Вдобавок хочу дать ссылку на открытый проект ZXing
Да, отличный проект, знаю такой. У него есть одно важное преимущество: он работает с большим количеством различных типов штрих-кодов (1D и 2D) и сам способен распознавать их тип. Но это же преимущество в то же время приводит и к серьезному недостатку: для каждого отдельного типа штрих-кода распознаваемость намного хуже, чем в алгоритмах, специализированных именно под этот тип штрих-кода. Если я правильно понял, то он вообще никак не локализует штрих-код на картинке. И при больших искажениях, таких как дефокусировка и низкое разрешение, он дает совсем плохие результаты.
0
kosiakk, #
посмотрите исходники — почти для каждого типа есть два класса — быстрый Detector и медленный Decoder.

Для обычных штрих-кодов, например, детектор ищет светлый обрамляющий прямоугольник, и лишь потом пытается прочесть данные.

code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java

мне кажется, такая реализация намного быстрее чем считать гистограмму яркости и т.п. На мобильниках это весьма важно.
0
orionll, #
Хорошо, обязательно посмотрю. Как разберусь, напишу.
0
vgrichina, #
Гистограмма яркости считается за линейное время от количества пикселей, в чем проблема ее посчитать? Остальные шаги требуют еще меньше операций )
0
orionll, #
Да, но линейное время линейному времени рознь. Выигрыш, допустим, в 2-3 раза, может быть существенен. В любом случае надо читать исходный код и сравнивать.
0
vgrichina, #
Сложновато обогнать гистограмму по коефициенту:

  for (int i = 0; i < size; i++)
    hist[image[i] - min]++;


Тут единственная дорогая операция – чтение/запись памяти. Хотя вообще по идее и это не проблема так как гистограмма помещается в кеш.
+1
orionll, #
К сожалению, гистограмма — не единственное тонкое место. Как я упомянул в статье, там сначала идет предобработка: вычитание модулей производных + усредняющий фильтр 31x31. Это занимает большую часть времени работы алгоритма.

Кстати, вопрос в студию: правда ли, что можно реализовать усредняющий фильтр такого размера (31x31) всего за несколько операций на пиксель?
+1
Jabberwok, #
«если взять изображение как разницу горизонтальной и вертикальной производной» а если он повернут? попробуйте покрутить его и для разных углов попробовать. думаю выйдет не очень.
0
orionll, #
Согласен, выйдет не очень. Но тут ничего не поделаешь — пользователю самому придется выравнивать телефон горизонтально. Хотя как я уже сказал выше, допустимый диапазон углов составляет от -30° до +30°, поэтому строгая горизонтальность не нужна. Небольшой наклон допустим.
А вообще все познается в сравнении: если взять, например, то же Яндекс Маркет приложение для Android, то там вообще надо подгонять камеру телефона так, чтобы штрих-код встал четко под прямоугольник. Когда я ехал в трясущейся маршрутке, я просто физически не смог этого сделать.
Или, например, лазерный сканер. Если присмотреться, то можно заметить, как продавщицы в супермаркете частенько поворачивают упаковку товара, чтобы штрих-код распознался системой. А ведь в лазерном сканере качество считывания намного выше, чем в камере телефона.

Так что мой вывод таков: фотографировать штрих-код издалека все равно проще, чем подносить камеру так, чтобы штрих-код четко попадал в зону считывания. Приложений, которые работают по второму принципу полно, а первых, насколько мне известно, пока еще нет.
0
orionll, #
Хм, как выяснилось гугловский ZXing тоже производит локализацию штрих-кода. Осталось только понять, какой алгоритм лучше: описанный в статье или ZXing.
+1
Jabberwok, #
если вы пишете диплом для себя, то уж стоит искать хорошие решения. так аргумент «у остальных так же» не очень. мне удалось подобрать последовательность фильтров, которая неплохо выделяет потенциальные области, где могут быть штрих коды, причем мой метод абсолютно инвариантен к поворотам. потом области надо проверить самому. завтра покажу код если интересно.
+1
orionll, #
Во-первых, суть статьи не в том, чтобы показать, что метод локализации хорош, а в том, чтобы показать действенность метода на реальной задаче. В данном случае, на локализации штрих-кодов.
Во-вторых, «хорошесть» вашего метода не отменяет «хорошесть» описанного мною. Просто ваш может быть немного лучше.
В-третьих, в дипломе я не занимаюсь локализацией, так как локализация уже разработана многими. Вот и вы предлагаете свой метод. Моя задача ограничена именно распознаванием уже локализованного штрих-кода.
В-четвертых, инвариантность относительно поворота в моей работе не нужна, так как дальнейший алгоритм распознавания все равно не работает с наклоненными штрих-кодами (такова плата за низкое разрешение и дефокусировку).
В-пятых, хорошие решения есть, но далеко не все их можно достать в Интернете. Вот вы придумали метод, взяли бы да и опубликовали статью. И я бы в своем дипломе, к примеру, мог бы сослаться на него.
0
orionll, #
Кстати, да, мне интересно, я бы посмотрел код, а еще лучше, краткое его описание.
0
wolfenstein, #
Спасибо, очень интересно. А как насчет инвариантности к освещению? И еще, если можно, этот алгоритм можно применять для любых классов? Или есть какие-то требования?
+1
Jabberwok, #
если освещение изменяется равномерно (либо все темнее, либо все светлее) то результат будет одинаковый. в этом и преимущество.
+1
orionll, #
Если имеется в виду именно средняя яркость всего изображения, то да, от нее ничего не зависит.
А вот если средняя яркость левой половинки картинки меньше, чем правой (неравномерная освещенность фотографии, например), то, к сожалению, метод уже не работает. В таком случае приходится применять всякие ухищрения.
0
orionll, #
>> И еще, если можно, этот алгоритм можно применять для любых классов? Или есть какие-то требования?

Хороший вопрос, в общем-то:) Думаю, можно ответить так: чем лучше классы описываются гауссовым распределением и чем меньше их гистограммы перекрываются, тем надежнее будет метод.
0
wolfenstein, #
я просто занимаюсь обработкой изображений лиц, поэтому интересно. я так понимаю, этот метод можно будет использовать, когда лицо выделяется по яркости на изображении?:)
+2
orionll, #
Я не думаю. Ведь лицо вовсе не обязано быть ярче / темнее фона. А тут именно разделение по яркости.
НЛО прилетело и опубликовало эту надпись здесь
0
orionll, #
Спасибо, исправил
0
lmaxim, #
Из тюнинга — можно пройтись по диагонали при составлении гистограммы — результат примерно как логарифмировать гистограмму, а количество операций меньше.
0
orionll, #
Не совсем понял, поясните, пожалуйста.
0
lmaxim, #
Логарифмирование гистограммы по основанию 2 даст в итоге значения степеней двойки которые для изображения 640*480 будут варьироваться в диапазоне примерно 1-20, 0 естественно отбрасывается при логарифмировании. При вычислении гистограммы по главной диагонали image[i][i] значения тоже будут лежать в данных диапазонах за меньшим числом операций и экспериментально будут очень близки к результату, полученному логарифмированием.
0
orionll, #
А если штрих-код не будет лежать на главной диагонали? Где-нибудь в углу локализован?
0
lmaxim, #
Это подходит для серых изображений, а после вычисления производных и mean-фильтра, если Вы про этот случай, результат будет совсем другой.
0
sigizmund, #
Картинки сдохли ;) а еще и из Эдинбурга :-)
0
orionll, #
Я не знаю почему, но у меня отображаются, даже при Ctrl + F5. Загружал на habreffect.ru.
Кто-нибудь знает, в чем может быть проблема?
+1
GraD_Kh, #
Спасибо, хорошее описание. А если «горбов» неизвестное число? Есть ли обобщение на такой вариант?
+1
orionll, #
На неизвестное число, насколько я знаю, нет. На фиксированное число — есть.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.