НОВОСТИ Несколько фактов о каскадных классификаторах, которые редко всерьез рассматриваются в научных статьях

[Bonnie]

Привет Хабр! Сегодня снова поговорим про распознавание. А именно, про такую простую модель распознавателя как каскадный классификатор. Именно каскад используется в популярном методе Виолы и Джонса, про который уже так много раз писали на Хабре (например,

You must be registered for see links

,

You must be registered for see links

и

You must be registered for see links

). Грусть в том, что несмотря на обилие статей, всерьез каскадные классификаторы никто не изучал. И не только на Хабре, но и научном сообществе. Хотя каскадный классификатор кажется простым, там достаточно много подводных камней и интересных особенностей. Поэтому мы спешим поделиться с вами своими знаниями. Так что, если интересно, добро пожаловать под кат.

Каскадный классификатор – очень простая модель. Он состоит из нескольких последовательных уровней, каждый из которых представим в виде бинарного классификатора. Исследуемый прецедент подается на вход первому уровню и далее «путешествует» уровень за уровнем. Если на очередном уровне классификатор признает прецедент отрицательным, то он уже не анализируется оставшимися классификаторами каскада. Такая простая модель стала популярна после публикации метода Виолы и Джонса [1], где, как заявляется, она использовалась для обеспечения высокой производительности. Но только ли для этого? Так ли просто каскадный классификатор? Давайте разбираться!

Сегодняшнюю статью на Хабре мы построим в новом для нас формате. Мы выберем несколько утверждений, которые детально раскроем и даже где-то даже опровергнем. Итак, давайте приступим!

Каскадный классификатор в методе Виолы и Джонса используется просто для ускорения работы детектора объектов


В оригинальной статье [1] на самой первой странице есть такая фраза:

The third major contribution of this paper is a method for combining successively more complex classifiers in a cascade structure which dramatically increases the speed of the detector by focussing attention on promising regions of the image.​

Действительно, оригинальный метод Виолы и Джонса предназначен для поиска объектов на изображении. Причем задача детектирования решается методом скользящего окна с помощью бинарного классификатора, который прикладывается в каждой точке исследуемого изображения в разных масштабах. Несбалансированность исследуемых данных на этапе детекции («пустых» регионов без искомого объекта на каждом исследуемом изображении в миллионы и даже в миллиарды раз больше, чем регионов с объектами) побудило к использованию каскада – механизму, который позволяет быстро отсекать «пустые» регионы.

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

1. Позволяет легко обучить классификатор, естественным образом избегая проблемы «бесконечной» обучающей выборки;
2. Обеспечивает быстрое отсечение «пустых» регионов при детекции объектов, за счет чего достигается высокая производительность в среднем.

Что же, давайте продолжим изучать классический каскад и обратимся к вопросу производительности.

С учетом вышесказанного каскадный классификатор — инструмент для ускорения


Вернемся еще раз к вопросу о предназначении каскада, но теперь с другой стороны. Если посмотреть на каскадный классификатор математически, то видно, что каскад представляет собой конъюнктивную форму сильных классификаторов (каждый из которых представим в виде линейной композиции признаков):

где

— индикаторная функция.

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

Таким образом, применение каскадного классификатора, в дополнение к повышению производительности, обеспечивает также большую выразительную силу, чем одиночный линейный классификатор, в условиях ограниченного числа признаков.

Каскадный классификатор обеспечивает стабильно высокую производительность и может спокойно использоваться в системах распознавания в режиме реального времени


Как мы выше рассказали, каскадная схема позволяет добиться высокой производительности за счет быстрого отсеивания «пустых» регионов, поскольку их количество на несколько порядков превышает количество регионов, содержащих объект. Время обработки «пустого» региона отличается от времени обработки региона с объектом в несколько раз (пропорционально длине каскада – количеству уровней каскада).

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

Таким образом, время работы каскадного классификатора на разных картинках может существенно отличаться. Отсюда, при выполнении серьезных замеров производительности классификаторов следует делать замеры времени работы в среднем и в худшем случаях. И всегда быть готовым к таким временным «непостоянностям» при использовании каскадных классификаторов.

В своей практике мы уже сталкивались с серьезными проблемами из-за существенного расхождения времени работы каскада в среднем и худшем случаях. В рамках проекта по автоматизации платных автодорог мы решали задачу распознавания типа автомобиля, где в качестве одной из основных подзадач стояла проблема подсчета колесных пар. Конечно, для детекции колес на отдельных кадрах мы использовали метод Виолы и Джонса. За счет большой вариативности колес (см. рисунок ниже) обученный каскад был достаточно длинным (20 уровней). Мы живьем наблюдали неприятные проблемы, связанные с разным временем обработки каждого кадра, что всерьез мешало нам строить систему распознавания в режиме реального времени.

Тогда мы развили идею классического каскадного классификатора до полноценного решающего дерева, разработав уникальную технологию обучения такого решающего дерева (помним, что необходимо было предложить алгоритм, который позволил бы нам избежать проблемы, связанные с «бесконечной» обучающей выборкой). Детали этого алгоритма можно найти в нашей научной работе [3]. Здесь же сообщим лишь несколько фактов:

1. Самый длинный путь в обученном дереве состоит из 6 сильных классификаторов (схема обученного древовидного классификатора представлена на рисунке ниже).
2. Обученный древовидный классификатор обеспечивал лучшее качество работы по сравнению с обученным ранее каскадом. Это закономерно и следует из того, что выразительная сила древовидного каскада (который представляет собой конъюнктивно-дизъюнктивной формы) выше выразительной силы каскада (конъюнктивной формы).
3. Обученный древовидный классификатор серьезно обходил каскад в худшем случае, практически не проигрывая при этом в среднем.

В таблице ниже представлены численные сравнения каскадного и древовидного классификаторов.

Чувствительность	Специфичность	Время в среднем, мкс	Время в худшем, мкс
Каскадный классификатор	93,55%	99,98%	58159	67432
Древовидный классификатор	94,02%	99,99%	58717	63552

Таким образом, если вы действительно хотите использовать каскадные классификаторы в системах распознавания в режиме реального времени, то помните всегда про особенности, связанные со скоростью работы в среднем и худшем случаях.

Технологии обучения каскадного классификатора настолько очевидны, что нечего на них всерьез заморачиваться


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

1. Определитесь со значениями доли ложного распознавания (
   
   ) для всего каскада.
2. Определитесь со значениями доли верного распознавания (
   
   ) и доли ложного распознавания (
   
   ) для каждого уровня распознавания.
3. Определитесь с валидационной выборкой, чтобы честно оценивать качественные показатели финального классификатора.
4. Обучайте каждый новый уровень каскада (который, напомним, обучается на всех имеющихся положительных примерах, а также на ложноположительных ошибках текущего каскада) так, чтобы его показатели
   
   и
   
   были не хуже заданных, то есть
   
   и
   
   . Кстати, процесс обеспечения этих показателей сам по себе тоже вызывает немаленький интерес.
5. Добавьте только что обученный уровень к каскаду и оцените его качественные показатели на валидационной выборке. Если доля ложных распознаваний меньше целевого показателя
   
   , то заканчиваем обучение. Иначе – переходим на шаг 4 для обучения нового уровня каскада.

Если в результате описанного выше алгоритма обучено

уровней каскада, то можно оценить среднюю сложность долю верного распознавания каскада следующим образом:

где

– сложность

-го уровня каскада,

– вероятность вычисления

-го уровня каскада, а

– доля верных распознаваний

-го уровня каскада.

Как вы видите, в представленном алгоритме обучения никак не участвует сложность каскада, поэтому назвать его эффективным по производительности, конечно, нельзя. При этом мы точно знаем, что ученые во всем мире твердо убеждены в важности алгоритмов обучения эффективных каскадов, в качестве подтверждения приведем здесь цитату из статьи Пола Виолы и Майкла Джонса [4]:

The overall training process involves two types of tradeoffs. In most cases classifiers with more features will achieve higher detection rates and lower false positive rates. At the same time classifiers with more features require more time to compute. In principle one could define an optimization framework in which
– the number of classifier stages,
– the number of features,

, of each stage,
– the threshold of each stage
are traded off in order to minimize the expected number of features

given a target for

and

. Unfortunately finding this optimum is a tremendously difficult problem.​

Интересно, что наш обзор актуальной литературы, сделанный в 2016 году, показал, что на тот момент еще не существовало эффективных алгоритмов обучения каскадных классификаторов. Кстати, именно тогда мы в Smart Engines решали эту задачу. Мы изучили следующий функционал, который зависит от ошибок детектирования первого рода (

), ошибок детектирования второго рода (

) и средней сложности (

):

Выбор параметров

,

и

, задают относительную стоимость ошибок первого и второго рода, а также сложности получаемого детектора. Далее в процессе обучения каскадного классификатора использовался жадный алгоритм перебора параметров на каждом уровне с целью получения каскадов, максимизирующих выбранный функционал. Детальное описание разработанного алгоритма выходит за рамки данной статьи, но мы всегда готовы поделиться им с тобой, наш читатель, путем предоставления библиографической ссылки [5].

Заключение


Подводя итог всему сказанному со своей стороны, на примере модели каскадного классификатора, мы хотим сделать следующие выводы:

1. Редко удается встретить научную работу, в которой досконально описаны все необходимые детали.
2. Очень полезно перечитывать научные статьи, всерьез задумываясь о работе свойствах и ограничениях представленных в них моделей, даже если на первый взгляд кажется, что в статье все «разжевано».
3. Всегда найдется место научному достойному исследованию, даже если исследуемая модель была предложена 20 лет назад.

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

Спасибо.

Список используемых источников

1. Paul Viola Michael J. Jones. Robust real-time object detection // International journal of computer vision. – 2001.
2. Bourdev L., Brandt J. Robust object detection via soft cascade //2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). – IEEE, 2005. – Т. 2. – С. 236-243.
3. Minkina A. et al. Generalization of the Viola-Jones method as a decision tree of strong classifiers for real-time object recognition in video stream //Seventh International Conference on Machine Vision (ICMV 2014). – International Society for Optics and Photonics, 2015. – Vol. 9445. – P. 944517.
4. Paul Viola Michael J. Jones. Robust real-time face detection // International journal of computer vision. – 2004. – Vol. 57. – No. 2. – P. 137-154.
5. Поляков И. В. и др. Построение оптимальных каскадов Виолы-Джонса при помощи «жадных» алгоритмов перебора управляющих параметров с промежуточным контролем по валидационной выборке // Сенсорные системы. – 2016. – Т. 30. – №. 3. – С. 241-248.