Работа каскада Хаара в OpenCV в картинках: теория и практика
В прошлой статье мы подробно описали алгоритм распознавания номеров (ссылка), который заключается в получении текстового представления на заранее подготовленном изображении, содержащем рамку с номером + небольшие отступы для удобства распознавания. Мы лишь вскользь упомянули, что для выделения областей, где содержатся номера, использовался метод Виолы-Джонса. Данный метод уже описывался на хабре (ссылка, ссылка, ссылка, ссылка). Сегодня мы проиллюстрируем наглядно то, как он работает и коснёмся ранее необсужденных аспектов + в качестве бонуса будет показано, как подготовить вырезанные картинки с номерами на платформе iOS для последующего получения уже текстового представления номера.
Метод Виолы-ДжонсаОбычно у каждого метода есть основа, то, без чего этот метод не мог бы существовать в принципе, а уже над этой основой строится вся остальная часть. В методе Виолы-Джонса эту основу составляют примитивы Хаара, представляющие собой разбивку заданной прямоугольной области на наборы разнотипных прямоугольных подобластей: 
В оригинальной версии алгоритма Виолы-Джонса использовались только примитивы без поворотов, а для вычисления значения признака сумма яркостей пикселей одной подобласти вычиталась из суммы яркостей другой подобласти [1]. В развитии метода были предложены примитивы с наклоном на 45 градусов и несимметричных конфигураций. Также вместо вычисления обычной разности, было предложено приписывать каждой подобласти определенный вес и значения признака вычислять как взвешенную сумму пикселей разнотипных областей [2]: 
Почему в основу метода легли примитивы Хаара? Основной причиной являлась попытка уйти от пиксельного представления с сохранением скорости вычисления признака. Из значений пары пикселей сложно вынести какую-либо осмысленную информацию для классификации, в то время как из двух признаков Хаара строится, например, первый каскад системы по распознаванию лиц, который имеет вполне осмысленную интерпретацию [1]: 
Сложность вычисления признака так же как и получения значения пикселя остается O (1): значение каждой подобласти можно вычислить скомбинировав 4 значения интегрального представления (Summed Area Table — SAT), которое в свою очередь можно построить заранее один раз для всего изображения за O (n), где n — число пикселей в изображении, используя формулу [2]:
Это позволило создать быстрый алгоритм поиска объектов, который пользуется успехом уже больше десятилетия. Но вернемся к нашим признакам. Для определения принадлежности к классу в каждом каскаде, находиться сумма значений слабых классификаторов этого каскада. Каждый слабый классификатор выдает два значения в зависимости от того больше или меньше заданного порога значение признака, принадлежащего этому классификатору. В конце сумма значений слабых классификаторов сравнивается с порогом каскада и выносится решения найден объект или нет данным каскадом. Ну хватит теории, перейдем к практике! Мы уже давали ссылку на XML нашего классификатора автомобильных номеров, который можно найти в мастере проекта opencv (ссылка). Посмотрим на его первый каскад:
По сути все эти признаки в какой-то степени являются самыми обыкновенными детекторами границ. На основе этого базиса строится решение о том распознал ли каскад объект на изображении или нет.Второй по важности момент в методе Виола-Джонса — это использование каскадной модели или вырожденного дерева принятия решений: в каждом узле дерева с помощью каскада принимается решение может ли на изображении содержатся объект или нет. Если объект не содержится, то алгоритм заканчивает свою работу, если он может содержатся, то мы переходим к следующему узлу. Обучение построено таким образом, чтобы на начальных уровнях с наименьшими затратами отбрасывать большую часть окон, в которых не может содержаться объект. В случае распознавания лиц — первый уровень содержит всего 2 слабых классификатора, в случае распознавания автомобильных номеров — 6 (при учете, что последние содержат до 15ти). Ну и для наглядности как происходит распознавание номера по уровням:
Более насыщенный тон показывает вес окна относительно уровня. Отрисовка была сделана на основе модифицированного кода проекта opencv из ветки 2.4 (добавлена поуровневая статистика).
Реализация распознавания на платформе iOS
С добавлением opencv в проект обычно не возникает проблем, тем более что существует готовый фреймворк под iOS, поддерживающий все существующие архитектуры (в том числе и симулятор). Функция для нахождения объектов используется та же, что и в проекте под Android (ссылка): detectMultiScale класса cv: CascadeClassifier, осталось только подготовить данные для подачи на вход. Допустим у нас имеется UIImage на котором нужно отыскать все номера. Для каскада нам нужно сделать несколько вещей: во-первых, ужать изображение до 800 px по большей стороне (чем больше изображение, тем нужно рассмотреть больше масштабов, также от размера изображения зависит количество окон, которые нужно просмотреть при поиске), во-вторых, сделать из него черно-белый аналог (метод оперирует только с яркостью, по идее этот этап можно пропустить, opencv это умеет делать за нас, но сделаем это заодно, раз и так производим манипуляции с изображением), в-третьих, получить бинарные данные для передачи opencv. Все эти три вещи можно сделать за один мах, отрисовав в контекст нашу картинку с правильными параметрами, вот так:
+ (unsigned char *)planar8RawDataFromImage:(UIImage *)image
size:(CGSize)size
{
const NSUInteger kBitsPerPixel = 8;
CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceGray ();
NSUInteger elementsCount = (NSUInteger)size.width * (NSUInteger)size.height;
unsigned char *rawData = (unsigned char *)calloc (elementsCount, 1);
NSUInteger bytesPerRow = (NSUInteger)size.width;
CGContextRef context = CGBitmapContextCreate (rawData,
size.width,
size.height,
kBitsPerPixel,
bytesPerRow,
colorSpace,
kCGImageAlphaNone);
CGColorSpaceRelease (colorSpace);
UIGraphicsPushContext (context);
CGContextTranslateCTM (context, 0.0f, size.height);
CGContextScaleCTM (context, 1.0f, -1.0f);
[image drawInRect: CGRectMake (0.0f, 0.0f, size.width, size.height)];
UIGraphicsPopContext ();
CGContextRelease (context);
return rawData;
}
Теперь можно смело создавать из этого буфера cv: Mat и передавать в функцию по распознаванию. Далее, пересчитываем положение найденных объектов по отношению к оригинальному изображению и вырезаем:
CGSize imageSize = image.size;
@autoreleasepool {
for (std: vector
Список литературы P. Viola and M. Jones. Robust real-time face detection. IJCV 57(2), 2004 Lienhart R., Kuranov E., Pisarevsky V.: Empirical analysis of detection cascades of boosted classifiers for rapid object detection. In: PRS 2003, pp. 297–304 (2003)
