Алгоритмическое развитие Виола-Джонсовских детекторов для решения прикладных задач распознавания изображений тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Усилин Сергей Александрович

• Усилин Сергей Александрович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Усилин Сергей Александрович

Введение

1 Метод Виолы и Джонса детектирования объектов на изображении

1.1 Понятие цифрового изображения

1.2 Задача поиска объектов и основы статистического обучения

1.2.1 Задача построения классификатора

1.2.2 Бустинг в задачах классификации.....................................................................22f

1.2.3 Оценка качества работы детекторов

1.3 Оригинальный методы Виолы и Джонса

1.3.1 Прямоугольные признаки Хаара

1.3.2 Обучение классификаторов с помощью АёаВооБ1

1.3.3 Каскадная структура классификаторов

1.3.4 Результаты практического тестирования метода

1.4 Анализ существующих модификаций метода Виолы и Джонса

1.4.1 Модификации в части пространства признаков

1.4.2 Модификации в части обучающего алгоритма

1.4.3 Модификации в части каскадной структуры классификатора

1.5 Применение метода Виолы и Джонса в индустриальных распознающих системах

1.6 Конкретизация цели и задачи исследования

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

2.1 Карта направленных границ

2.2 Контурные признаки Хаара

2.3 Численный эксперимент и результаты

2.3.1 Распознавание образов колес

2.3.2 Распознавание номера кредитной карты

2.4 Выводы по второму разделу

3 Высокоуровневая структура классификатора Виолы и Джонса в виде решающего дерева сильных классификаторов

3.1 Решающее дерево сильных классификаторов

3.2 Метрика сравнения классификаторов

3.3 Численный эксперимент и результаты

3.3.1 Распознавание образов колес

3.3.2 Распознавание логотипа платежной системы VISA

3.4 Выводы по третьему разделу

4 Способ ускорения процедуры поиска объектов в видеопотоке путем адаптивного выбора распознающих классификаторов

4.1 Задача об n-руком бандите

4.2 Постановка задачи адаптивного выбора распознающих классификаторов

4.3 Алгоритм адаптивного выбора распознающих классификаторов

4.4 Численный эксперимент и результаты

4.5 Выводы по четвертому разделу

5 Проектирование и реализация программного комплекса детектирования объектов методом Виолы и Джонса

5.1 Существующие программные решения детектирования объектов методом Виолы и Джонса

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

5.3 Разработка программного комплекса objed

5.3.1 Выбор средств разработки

5.3.2 Архитектура программного комплекса objed

5.4 Использование программного комплекса objed в индустриальных распознающих системах

5.5 Выводы по пятому разделу

Заключение

Список сокращений и условных обозначений

Список литературы

Список публикаций автора

Приложение А Модуль обучения программного комплекса objed

Приложение Б Алгоритм AdaBoost

Приложение В Охранные документы на результаты интеллектуальной деятельности

Введение диссертации (часть автореферата) на тему «Алгоритмическое развитие Виола-Джонсовских детекторов для решения прикладных задач распознавания изображений»

Введение

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

Содержательная постановка задачи обучения машин распознаванию образов появилась в конце 50-х годов и заключалась в построении способа обучения машин решать классификационные задачи так же, как это делают живые существа. В это же появились первые нейросетевые модели распознавания, в частности перцептрон Розенблатта [1]. К концу 60-х годов уже были разработаны различные подходы для решения задач распознавания в рамках статистических и персептронных моделей. Большой вклад в развитие теории распознавания внесли советские (в последующем российские) ученые и научные школы. Здесь необходимо, прежде всего, отметить школы: Айвазяна С.А. - ЦЭМИ АН СССР (Айвазян С.А., Бухштабер В.М., Енюков И.С. и др.), Айзермана М.А. - ИАТ АН СССР (Айзерман М.А., Раверманн Э.М., Розоноэр Л.И. и др.), Бонгарда М.М. - ИППИ АН СССР (Бонгард М.М., Вайнцвайг М.Н., Максимов В.В. и др.), Вапника В.Н. - ИАТ АН СССР (Вапник В.Н., Червоненкис А.Я., Стефанюк А.Р. и др.), Журавлева Ю.И. - ВЦ АН СССР (Журавлев Ю.И., Рудаков К.В., Воронцов К.В. и др.), Загоруйко Н.Г. - Институт математики СО АН СССР, Новосибирский ГУ (Загоруйко Н.Г., Елкина В.Н., Лбов Г. С. и др.), Ковалевского В.А. - Институт кибернетики АН УССР, Киев (Ковалевский В.А., Винцюк Т.К., Шлезингер М.И. и др.), Сойфера В.А. - СГАУ (Сойфер В.А., Сергеев В.В., Храмов А.Г. и др.), Якубовича В.А. - Ленинградский ГУ (Якубович В.А., Тимофеев A.B., Шмидт A.A. и др.).

В результате такого активного развития теории распознавания образов было разработано множество алгоритмов построения классификаторов. Дальнейшее развитие этого направления, особенно при решении сложных практических задач, привело к разработке нового типа классификаторов, использующих для построения решающих правил композицию («коллектив») алгоритмов. Здесь необходимо выделить результаты, полученные учёными из научной школы Ю.И. Журавлева (см., например, [2,3]). Позднее аналогичные исследования появились и в других странах. Так, например, в 90-е годы Йоавом Фройндом и Робертом Шапиром в работах был предложен достаточно эффективный итеративный алгоритм построения «сильного» распознавателя путем объединения нескольких «слабых», названный авторами AdaBoost (adaptive boosting) [4-6]. Алгоритм представляет собой процедуру пошагового объединения «слабых» классификаторов в «сильные», при этом на каждой итерации особое внимание обращается на неверно классифицированные прецеденты предыдущих этапов. Благодаря своей простоте и эффективности AdaBoost быстро набрал популярность и начал активно применяться для решения различных задач распознавания.

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

Для случая, когда локализация объектов определяется с помощью обрамляющего прямоугольника, на протяжении многих лет применяют метод сканирующего (скользящего) окна (англ. sliding window, scan window) [7-11].

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

Революционный прорыв в области детектирования объектов был сделан американскими учеными Полом Виолой и Майклом Джонсом в 2001 году, предложившими алгоритм поиска лица на изображениях, обеспечивающий обработку до 15 кадров VGA разрешения в секунду [7,8]. Суть предложенного алгоритма заключается в объединении в единую конструкцию четырех подходов: использование вычислительно легковесных и обладающих хорошей обобщающей способностью признаков Хаара, обучение классификаторов с помощью бустинга, обеспечение высокой производительности за счет использования каскада классификаторов, а также применение метода скользящего окна для определения локализации объектов. Несмотря на то, что данный метод изначально разрабатывался для поиска лиц, он оказался применим для детекции широкого класса объектов, обладающих жесткой геометрией. В результате алгоритм Виолы и Джонса стал классическим подходом для решения задач локализации объектов на изображении [12-25].

На сегодняшний день степень разработанности метода Виолы и Джонса достаточно высока. Исследователями по всему миру предложено множество модификаций оригинального алгоритма и отдельных его частей. В частности, Лиенхард и Майдт предложили расширить оригинальное пространство прямоугольных признаков Хаара за счет повернутых на 45° в паре с быстрым

способом подсчета таких признаков [26]. Позже Мессом и Барзак дополнили концепцию наклонных признаков Хаара, предложив подход к вычислению признаков под произвольными углами [27]. В 2010 развитие яркостных признаков Хаара достигло своего пика за счет работы [28], в которой исследователи из института в Гилфорде (Мин-Три Фам и Ян Гао) вместе с коллегами из Университета в Сингапуре (Виет-Дунг Хуан и Тат-Джен Чам) предложили алгоритм построения полигональных признаков Хаара. Помимо расширения допустимой формы признаков в настоящее время предложен ряд модификаций относительно самой природы вычисляемых признаков. Так, Далал и Триггс предложили использовать гистограммы направленных градиентов [10] для построения классификаторов, устойчивых к яркостным изменениям, исследователи из Microsoft (Жан, Сан и Танг) объединили концепцию HoG и признаков Хаара [29], а Пиотр Доллар с коллегами из Калифорнийского института предложил использовать мультиспектральное представление изображения для одновременного вычисления признаков разной природы [30,31].

Немало работ посвящено модификациям метода Виолы и Джонса в части алгоритма обучения сильных классификаторов. Большое количество работ посвящено различным вариантам аппроксимации функционала качества композиции непрерывно дифференцируемыми оценками сверху [32-38]. Отдельное внимание стоит обратить на алгоритм LogitBoost [35], сформулированный Фридманом, Хасти и Тибширани, который представляет собой адаптацию подхода логистической регрессии к идее бустинга. В результате этого построенный классификатор обладает набором интересных особенностей: обученный таким образом классификатор оказывается оптимальным с точки зрения байесовской классификации, позволяет строить более устойчивые к шуму классификаторы, возникает возможность получать численные оценки вероятности принадлежности исследуемых объектов к найденным классам.

В дополнение к новым методам обучения сильных классификаторов, учеными были предложены альтернативные способы построения каскадов. Одна из первых модификаций была предложена учеными из Microsoft (Сяо, Чжу, Чжан)

и заключалась в использовании ответов классификации ранних уровней каскада в качестве специального признака на очередном уровне [39]. В результате получается своего рода «связанный каскад», который в англоязычной литературе встречается в виде термина chain cascade [39] или nesting-structure cascade [40]. Позднее, в 2005 Боурдев и Брандт представили модель так называемого «легкого каскада» (англ. soft cascade), которая структурно похожа на сильный классификатор, обученный с помощью бустинга, однако способна отклонять отрицательные области после вычисления очередного слабого классификатора. В 2007 году Пол Виола и Ча Жанг в работе [41] развили идею такого каскада, добавив алгоритм подбора промежуточных порогов.

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

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

Таким образом, алгоритмическое развитие метода Виолы и Джонса, устраняющее указанные недостатки, является высоко востребованным, а тема исследований диссертационной работы - актуальной. Метод Виолы и Джонса активно применяется в области робототехники [42,43], разработки в которой входят в перечень приоритетных направлений развития науки, технологий и техники Российской Федерации, утвержденный Указом Президента РФ № 899 от 07.07.2011 года. Исследования по теме диссертации поддержаны Российским фондом фундаментальных исследований как в части инициативных научно-исследовательских проектов, так и в области междисциплинарных исследований. Основные результаты диссертации были получены в процессе выполнения работ по следующим научным грантам РФФИ:

- 17-29-03161_офи_м Каскадные алгоритмы локализации и прослеживания протяженных объектов на мобильных устройствах;

- 17-29-03297_офи_м Исследование возможности создания энергоэффективных аппаратных устройств для мобильных устройств комплексов идентификации и верификации личности в составе систем технического зрения наземных робототехнических комплексов;

- 16-29-09508_офи_м Алгоритмическое развитие Виола-Джонсовских детекторов в задачах идентификации объектов в потоках гетерогенных данных;

- 13-01-12106_офи_м Методы обучения и дообучения для систем видеоклассификации сложноструктурированных объектов в неконтролируемых условиях;

- 13-07-00870_А Алгоритмы трекинга и детекции ригидных трёхмерных объектов.

Объектом исследования является метод Виолы и Джонса поиска объектов на изображении.

Предметом исследования является алгоритмическое развитие Виола-Джонсовских детекторов для решения прикладных задач распознавания изображений.

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

Для ее достижения требуется решить следующие задачи:

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

2. Разработать семейство вычислительно эффективных признаков, обеспечивающих высокий уровень обобщения объектов и устойчивых к различным параметрам освещенности, применимых для использования в индустриальных распознающих системах.

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

4. Разработаны математическая модель и алгоритм адаптивного выбора распознающего классификатора Виолы и Джонса в задаче многоклассовой детекции объектов в видеопоследовательности.

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

Научная новизна выносимых на защиту результатов состоит в следующем:

- в рамках диссертационной работы формулируется и решается задача адаптации метода Виолы и Джонса к использованию в индустриальных условиях, требующая разработки новых моделей и подходов;

- представлено новое семейство признаков, устойчивых к различным параметрам освещенности и учитывающих геометрические особенности объектов за счет использования в качестве исходных данных карты направленных границ;

- предложена новая модель высокоуровневого классификатора в виде решающего дерева, обеспечивающая несколько выходов с положительным исходом, а также представлен алгоритм его обучения и дообучения в случае расширения выборки прецедентов;

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

Теоретическая и практическая значимость работы. Диссертационная работа имеет как теоретическую, так и практическую значимость.

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

Практическая значимость работы подтверждается использованием полученных результатов в следующих индустриальных системах распознавания. Результаты диссертационной работы внедрены в систему классификации автомобилей по геометрическим характеристикам АКТС-4 (эксплуатируется на 200 полосах пунктов взимания платы автомагистралей России М1 «Беларусь», М4 «Дон» и Западного Скоростного Диаметра Санкт-Петербурга), программные продукты распознавания документов Smart IDReader и Smart PassportReader (интегрированы в информационные решения крупнейших российских банков, страховых компаний и организаций различных государственных структур), а также в интеллектуальную систему автономного вождения C-Pilot (система содействия водителю, предназначена для установки на коммерческий транспорт).

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

- Международной IEEE конференции «Image Processing» (ICIP'2010), Гонконг, 2010;

- Международной конференции «The 7th International Conference on Machine Vision» (ICMV'2014), Милан, Италия, 2014;

- Международной конференции «The 9th International Conference on Machine Vision» (ICMV'2016), Ницца, Франция, 2016;

- Международной конференции «The 10th International Conference on Machine Vision» (ICMV'2017), Вена, Австрия, 2017;

- Междисциплинарной школе-конференции Института проблем передачи информации им. А. А. Харкевича Российской академии наук (ИППИ РАН) «Информационные технологии и системы» (ИТиС) в 2015, 2014 и 2012 годах;

- Открытом германо-российском семинаре «8th Open German-Russian Workshop «Pattern Recognition and Image Understanding», г. Нижний Новгород, 2011.

- Научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» в 2010, 2012 и 2013 годах.

- Открытом германо-российском семинаре «8th Open German-Russian Workshop «Pattern Recognition and Image Understanding», г. Нижний Новгород, 2011.

- Научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» в 2010, 2012 и 2013 годах.

Помимо научных конференций результаты диссертационной работы были обсуждены на международном научно-исследовательском семинаре Национального комитета при Президиуме РАН по распознаванию образов и анализу изображений «Анализ и понимание изображений (Математические, когнитивные и прикладные проблемы анализа изображений и сигналов)», заседания которого на базе Федерального исследовательского центра «Информатика и управление» Российской академии наук.

Публикации. Основные научные результаты диссертации изложены в 23 публикациях, в том числе: пять статей в изданиях, рекомендованных ВАК РФ, три публикации в изданиях, входящих в международные базы цитирования Scopus и Web of Science, патент на изобретение, два патента на полезную модель, а также три свидетельства на программу для электронных вычислительных машин (ЭВМ).

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

Структура и объем диссертации. Диссертация состоит из введения, пяти основных разделов, заключения, списка используемых по тексту работы сокращений и условных обозначений, списка использованной литературы, список публикаций автора по теме диссертации, а также трех приложений. Общий объем работы составляет 149 страниц (с учетом всех приложений), содержит 36 рисунков и 10 таблиц. Список литературы представлен 128 наименованиями.

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

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

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

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

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

Приложение А настоящей диссертации содержит описание модуля обучения классификаторов программного комплекса objed, приведена краткая документация по настройке и запуску отдельных утилит.

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

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

1 Метод Виолы и Джонса детектирования объектов на изображении

Метод Виолы и Джонса [7,8] представляет собой подход для решения задачи поиска объектов на изображении. Несмотря на то, что алгоритм, предложенный Полом Виолой и Майклом Джонсом в 2001 году, изначально разрабатывался для поиска лиц на изображениях в режиме реального времени, в настоящее время его различные модификации активно применяются в задачах поиска на изображениях пешеходов [19-22], транспортных средств [22-24], дорожных знаков [14,25] и множества других объектов с условно-фиксированной проекцией [12,13]. Здесь под словом «модификация» подразумевается тот факт, что при изменении постановки задачи приходится вносить изменения и в сам метод Виолы и Джонса (например, изменить пространство признаков или метод обучения). Такая популярность обусловлена тем фактом, что алгоритм показывает отличные результаты и высокую стабильность к геометрическим искажениям и яркостным изменениям.

Прежде, чем приступить к описанию самого метода, введем понятие цифрового изображения [44-48] и рассмотрим базовые основы задачи поиска объектов.

1.1 Понятие цифрового изображения

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

Определение 1. Под изображением будем понимать действительнозначную функцию f(y,x), определенную на некотором подмножестве пространства М2. Значение функции f(y,x) называется интенсивностью или яркостью, реже уровнем серого.

Определение 2. Изображение f(y,x) будем называть цифровым изображением, если величины у и х принимают конечное число дискретных значений.

В силу того, что величины у и х принимают конечное число дискретных значений, цифровое изображение можно представить в виде матрицы из М строк и N столбцов, где (у, х) задают координаты, а /(у, х) - значение элемента матрицы. В дальнейшем для большего удобства будем использовать целочисленные значения у = {0,1,2,..., М — 1} и х = {0,1,2,..., N — 1}, принимая за начало координат левый верхний угол изображения, где (у, х) = (0,0), ось у направлена вниз, а ось х - вправо. Область действительной координатной плоскости, охватываемая координатами изображения, называется пространственной областью, а у и х - пространственными переменными или пространственными координатами.

Список литературы диссертационного исследования кандидат наук Усилин Сергей Александрович, 2018 год

Список литературы

1. Rosenblatt, F. The Perceptron: A Perceiving and Recognizing Automaton / F. Rosenblatt // Cornell Aeronaut. — 1957. — Report 85-60-1.

2. Журавлев, Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации / Ю.И. Журавлев // Проблемы кибернетики. — 1978. — Т. 33. С. 5-68.

3. Журавлев, Ю.И. Избранные научные труды / Ю.И. Журавлев. — М.: Магистр, 1998. — 420 с.

4. Freund, Y. Experiments with a New Boosting Algorithm / Y. Freund, R.E. Schapire // International Conference on Machine Learning. — 1996. — P. 148-156.

5. Freund, Y. A Decision-theoretic Generalization of On-line Learning and an Application to Boosting / Y. Freund, R.E. Schapire // Comput. Learn. theory. — 1997. — Vol. 55. — № 1. — P. 119-139.

6. Freund, Y. Boosting a Weak Learning Algorithm by Majority / Y. Freund // Inf. Comput. — 1995. — Vol. 121. — № 2. — P. 256-285.

7. Viola, P. Robust Real-time Object Detection / P. Viola, M. Jones // International Journal of Computer Vision. — 2001.

8. Viola, P. Rapid object detection using a boosted cascade of simple features / P. Viola, M. Jones // Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2001). — 2001. — Vol. 1. — P. 511-518.

9. Rowley, H.A. Human Face Detection in Visual Scenes / H.A. Rowley, S. Baluja, T. Kanade // Adv. Neural Inf. Process. Syst. — 1995. — № 11 — P. 875-881.

10. Dalal, N. Histograms of Oriented Gradients for Human Detection / N. Dalal, W. Triggs // IEEE Computer Society Conference on Computer Vision and Pattern Recognition CVPR'05. — 2005. — Vol. 1. — № 3. — P. 886-893.

11. Chum, O. An Exemplar Model for Learning Object Classes / O. Chum, A. Zisserman // IEEE Conference on Computer Vision and Pattern Recognition. — 2007. — P. 1 -8.

12. Усилин, С.А. Распознавание гильоширных элементов: определение страниц паспорта РФ / С.А. Усилин и др. // Труды Института системного анализа РАН. Обработка информационных и графических ресурсов. — 2013. — Т. 63. — № 3. — С. 106-110.

13. Усилин, С.А. Локализация, ориентация и идентификация документов с фиксированной геометрией на изображении / С.А. Усилин, Д.П. Николаев, В.В, Постников // Труды Института системного анализа РАН. Обработка информационных и графических ресурсов / под ред. В.Л. Арлазарова. — М.: КРАСАНД, 2010. — Т. 58. — С. 248-261.

14. Chen, S. Boosted road sign detection and recognition / S. Chen, J. Hsieh // 2008 Int. Conf. Mach. Learn. Cybern. — 2008. — № July. — P. 3823-3826.

15. Dollar, P. Pedestrian detection: A benchmark / P. Dollar et al. // 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, CVPR Workshops 2009. — 2009. — P. 304-311.

16. Broggi, A. Vehicle detection for autonomous parking using a Soft-Cascade AdaBoost classifier / A. Broggi et al. // IEEE Intelligent Vehicles Symposium. — 2014. — P. 912-917.

17. Paisitkriangkrai, S. Fast pedestrian detection using a cascade of boosted covariance features / S. Paisitkriangkrai, C. Shen, J. Zhang // IEEE Trans. Circuits Syst. Video Technol. — 2008. —Vol. 18, — № 8. — P. 1140-1151.

18. Lin, C. Boosted Vehicle Detection Using Local and Global Features / C. Lin et al. // J. Signal Inf. Process. — 2013. — Vol. 4. — № 3. — P. 243-252.

19. Viola, P. Detecting pedestrians using patterns of motion and appearance / P. Viola, M. Jones, D. Snow // Int. J. Comput. Vis. 2005. — Vol. 63. — № 2. — P. 153-161.

20. Zhu, Q. Fast Human Detection Using a Cascade of Histograms of Oriented Gradients / Q. Zhu et al. // IEEE Conference on Computer Vision and Pattern Recognition. — 2006. — Vol. 2. — P. 1491-1498.

21. Jones, M. Pedestrian detection using boosted features over many frames / M. Jones, D. Snow // 2008 19th International Conference on Pattern Recognition. — 2008. — P. 1-4.

22. Moutarde, F. Real-time visual detection of vehicles and pedestrians with new efficient adaBoost features / F. Moutarde, B. Stanciulescu, A. Breheret // 2008 IEEE International Conference on Intelligent RObots Systems (IROS 2008). — 2008.

23. Lee, D.C. Boosted Classifier for Car Detection / D.C. Lee, T. Kanade. — 2007.

24. Sivaraman, S. A general active-learning framework for on-road vehicle recognition and tracking / S. Sivaraman, M.M. Trivedi // IEEE Trans. Intell. Transp. Syst. — 2010. — Vol. 11. — № 2. — P. 267-276.

25. Escalera, S. Fast greyscale road sign model matching and recognition / S. Escalera, P. Radeva // Recent Adv. Artif. Intell. Res. Dev. — 2004. — P. 69-76.

26. Lienhart, R. An extended set of Haar-like features for rapid object detection / R. Lienhart, J. Maydt // Image Processing. 2002. Proceedings. 2002 International Conference on. — 2002. — Vol. 1. — P. I-900-I-903 vol.1.

27. Messom, C. Fast and Efficient Rotated Haar-like Features using Rotated Integral Images / C. Messom, A. Barczak. — 2017.

28. Pham, M.T. Fast polygonal integration and its application in extending haar-like features to improve object detection / M.T. Pham et al. // 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. — 2010. — P. 942-949.

29. Zhang, W. Cat head detection - How to effectively exploit shape and texture features / W. Zhang, J. Sun, X. Tang // Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics). —2008. — Vol. 5305 LNCS. — № PART 4. — P. 802-816.

30. Dollar, P. Integral Channel Features / P. Dollar et al. // BMVC 2009 London Engl. — 2009. — P. 1-11.

31. Dollar, P. The Fastest Pedestrian Detector in the West / P. Dollar, S. Belongie, P. Perona // Procedings Br. Mach. Vis. Conf. 2010. — 2010. — P. 68.1-68.11.

32. Воронцов, К.В. Машинное обучение (курс лекций) [Электронный ресурс] / К.В. Воронцов. — Режим доступа: http://www.machinelearning.ru/ (дата обращения: 01.09.2015).

33. Мерков, А. Распознавание образов. Введение в методы статистического обучения / А. Мерков. — М. : Едиториал УРСС, 2011. — 256 с.

34. Мерков, А. Распознавание образов. Построение и обучение вероятностных моделей / А. Мерков. — М. : Ленанд, 2014. — 240 c.

35. Friedman, J. Additive logistic regression: A statistical view of boosting / J. Friedman, T. Hastie, R. Tibshirani // Annals of Statistics. — 2000. — Vol. 28. — № 2. — P. 337-407.

36. Domingo, C. MadaBoost: A Modification of AdaBoost / C. Domingo, O. Watanabe // Conference on Computational Learning Theory (COLT). — 2000. — P. 180-189.

37. Huang, C.H.C. Vector boosting for rotation invariant multi-view face detection / C.H.C. Huang et al. // Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. — 2005. — Vol. 1. — P. 446-453.

38. Li, S.Z. FloatBoost learning and statistical face detection / S.Z. Li, Z.Q. Zhang // IEEE Trans. Pattern Anal. Mach. Intell. — 2004. — Vol. 26. — № 9. — P. 11121123.

39. Xiao, R. Boosting Chain Learning for Object Detection / R. Xiao, L. Zhu, H.-J. Zhang // ICCV '03: Proceedings of the Ninth IEEE International Conference on Computer Vision. — 2003. — P. 709.

40. Wu, Bo. Fast rotation invariant multi-view face detection based on real AdaBoost / Bo Wu et al. // In Sixth IEEE International Conference on Automatic Face and Gesture Recognition. — 2004. — P. 79-84.

41. Zhang, C. Multiple-instance pruning for learning efficient cascade detectors / C. Zhang, P. Viola // Adv. Neural Inf. Process. — 2008. — P. 1-8.

42. Lee, S. Recent Progress in Robotics: Viable Robotic Service to Human / S. Lee. — Springer Science & Business Media, 2008. — 410 p.

43. Robotics: Joint Conference on Robotics, LARS 2014, SBR 2014, Robocontrol 2014, Sao Carlos, Brazil, October 18-23, 2014. Revised Selected Papers (Communications in Computer and Information Science). — Springer, 2015.

44. Гонсалес, Р. Цифровая обработка изображений. Издание 3-е, исправленное и дополненное / Р. Гонсалес, Р. Вудс. — М. : Техносфера, 2012. — 1104 с.

45. Претт, У. Цифровая обработка изображений: Пер. с англ. Кн. 1 / У. Претт. — М. : Мир, 1982. — 312 с.

46. Красильников, Н.Н. Цифровая обработка 2D- и 3D-изображений: учеб. пособие / Н.Н. Красильников. — 2011. — 608 с.

47. Яне, Б. Цифровая обработка изображений / Б. Яне. — М. : Техносфера, 2007. — 584 с.

48. Гашников, М.В. Методы компьютерной обработки изображений. 2-е изд. / М.Б. Гашников и др. / под ред. Сойфера В.А. — М. : ФИЗМАТЛИТ, 2003. — 784 с.

49. Everingham, M. The pascal visual object classes (VOC) challenge / M. Everingham // Int. J. Comput. Vis. — 2010. — Vol. 88. — № 2. — P. 303-338.

50. Вапник, В.Н. Теория распознавания образов (статистические проблемы обучения) / В.Н. Вапник, А.Я. Червоненкис. — М. : Наука, 1974. — 416 с.

51. Вапник, В.Н. О методе упорядоченной минимизации риска / В.Н. Вапник, А.Я. Червоненкис // Автоматика и телемеханика. — 1994. — № 8. — C. 21-31. — № 9. — С. 29-40.

52. Вапник, В.Н. Восстановление зависимостей по эмпирическим данным / В.Н. Вапник. — М. : Наука, 1979. — 449 с.

53. What you wanted to know about AUC [Электронный ресурс]. — Режим доступа: http://fastml.com/what-you-wanted-to-know-about-auc/ (дата обращения: 01.09.2015).

54. Davis, J. The Relationship Between Precision-Recall and ROC Curves / J. Davis, M. Goadrich // Proceedings of the 23rd International Conference on Machine learning — ICML'06. — 2006. — P. 233-240.

55. Papageorgiou, C.P. A general framework for object detection / C.P. Papageorgiou, M. Oren, T. Poggio // Sixth Int. Conf. Comput. Vis. IEEE Cat No98CH36271. — 1998. — Vol. 6. — № January. — P. 555-562.

56. Crow, F.C. Summed-area tables for texture mapping / F.C. Crow // ACM SIGGRAPH Computer Graphics. — 1984. — Vol. 18. — № 3. — P. 207-212.

57. Iba, W. Induction of One-Level Decision Trees / W. Iba, P. Langley // ML92: Proceedings of the Ninth International Conference on Machine Learning, Aberdeen, Scotland, 1-3 July 1992. — 1992. — P. 233-240.

58. Roth, D. A SNoW-based face detector / D. Roth, M. Yang, N. Ahuja // Adv. Neural Inf. Process. Syst. — 2000. — Vol. 12. — P. 855-861.

59. Schneiderman, H. A statistical method for 3D object detection applied to faces and cars / H. Schneiderman, T. Kanade // IEEE Conference on Computer Vision and Pattern Recognition. — 2000. — Vol. 1. — P. 746-751.

60. Sung, K.K. Example-based learning for view-based human face detection / K.K. Sung, T. Poggio // IEEE Trans. Pattern Anal. Mach. Intell. — 1998. — Vol. 20. — № 1. — P. 39-51.

61. Rowley, H.A. Neural network-based face detection / H.A. Rowley, S. Baluja, T. Kanade // IEEE Trans. Pattern Anal. Mach. Intell. — 1998. — Vol. 20. — № 1. — P. 23-38.

62. Huang, C.-C. An Extended Set of Haar-like Features for Bird Detection Based on AdaBoost / C.-C. Huang, C.-Y. Tsai, H.-C. Yang // Signal Processing, Image Processing and Pattern Recognition SE - 17 / ed. Kim T. et al. — Springer Berlin Heidelberg, 2011. — Vol. 260. — P. 160-169.

63. Francke, H. Real-Time Hand Gesture Detection and Recognition Using Boosted Classifiers and Active Learning / H. Francke, J. Ruiz-del-solar, R. Verschae // Lect. Notes Comput. Sci. — 2007. — Vol. 4872. — P. 533-547.

64. Ojala, T. A comparative study of texture measures with classification based on feature distributions / T. Ojala, M. Pietikainen, D. Harwood // Pattern Recognit. — 1996. — Vol. 29. — № 1. —P. 51-59.

65. Yang, Z. Demographic Classification with Local Binary Patterns / Z. Yang, H. Ai // Proceedings of the 2007 International Conference on Advances in Biometrics. — Berlin, Heidelberg: Springer-Verlag, 2007. — P. 464-473.

66. Оператор Local Binary Patterns в задаче классификации текстур [Электронный ресурс]. Режим доступа: http://habrahabr.ru/post/153109/ (дата обращения: 01.09.2015).

67. Ojala, T. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns / T. Ojala, M. Pietikainen, T. Maenpaa // IEEE Trans. Pattern Anal. Mach. Intell. — 2002. — Vol. 24. — № 7. — P. 971-987.

68. Chang-yeon, J. Face Detection using LBP features / J. Chang-yeon // Stanford.Edu.

— 2008. — P. 1-4.

69. HOG (Histogram of Oriented Gradients) with Matlab Implementation [Электронный ресурс]. Режим доступа: http://farshbafdoustar.blogspot.com.tr/2011/09/hog-with-matlab-implementation.html (дата обращения: 01.09.2015).

70. Schapire, R.E. Improved Boosting Algorithms Using Confidence-Based Predictions / R.E. Schapire, Y. Singer // Mach. Learn. — 1999. — Vol. 37. — № 3. — P. 297336.

71. Freund, Y. An adaptive version of the boost by majority algorithm / Y. Freund // Mach. Learn. — 2001. — Vol. 43. — № 3. — P. 293-318.

72. Demiriz, A. Linear programming boosting via column generation / A. Demiriz, K.P. Bennett, J. Shawe-Taylor // Mach. Learn. — 2002. — Vol. 46. — № 1-3. — P. 225254.

73. OpenCV [Электронный ресурс]. — Режим доступа: http://opencv.org/ (дата обращения: 01.09.2015).

74. Ruan, C. Real Adaboost feature selection for Face Recognition / C. Ruan, Q. Ruan, X. Li // International Conference on Signal Processing Proceedings, ICSP. — 2010.

— P. 1402-1405.

75. Duan, S. The LogitBoost Based on Joint Feature for Face Detection / S. Duan, X. Wang, W. Wan // Image and Graphics (ICIG), 2013 Seventh International Conference on. — 2013. — P. 483-488.

76. Demirkir, C. Multi pose face detection and pose estimation using Multi-class LogitBoost algorithm / C. Demirkir, B. Sankur // Signal Process. Commun. Appl. Conf. (SIU), 2010 IEEE 18th. — 2010.

77. Gualdi, G. Multi-stage sampling with boosting cascades for pedestrian detection in images and videos / G. Gualdi, A. Prati, R. Cucchiara // Lecture Notes in Computer

Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2010. — Vol. 6316 LNCS. — № PART 6. — P. 196209.

78. Bourdev, L. Robust Object Detection via Soft Cascade / L. Bourdev, J. Brandt // Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). — Washington, DC, USA: IEEE Computer Society, 2005. — Vol. 2. — P. 236-243.

79. Li, S.Z. Statistical learning of multi-view face detection / S.Z. Li et al. // Proc. European Conf. on Computer Vision. — 2002. — P. 67-81.

80. Жукова, П.Н. О профилактике правонарушений и безопасности дорожного движения / П.Н. Жукова, В.А. Насонова // Проблемы правоохранительной деятельности. — Белгород: Белгородский юридический институт Министерства внутренних дел Российской Федерации им. И.Д. Путилина, 2014. — № 1. — C. 34-36.

81. Арлазаров, В.Л. Алгоритмы распознавания и технологии ввода текстов в ЭВМ / В.Л. Арлазаров, О.А. Славин // Информационные технологии и вычислительные системы. — 1996. — Т. 1. — № 6. С. 48-54.

82. Арлазаров, В.В. Cognitive Forms система массового ввода структурированных документов / В.В. Арлазаров, В.В. Постников, Д.Л. Шоломов // Управление информационными потоками. Сборник трудов Института системного анализа РАН. — М.: Едиториал УРСС, 2002. —С. 35-46.

83. Шепелев, К.В. Применение методов распознавания образов при модернизации существующих систем видеонаблюдения в системах безопасности / К.В. Шепелев // Современный мир опыт, проблемы и перспективы развития. — Ставрополь: Центр научного знания "Логос," 2016. — № 2. — С. 9-12.

84. Zafeiriou, S. A survey on face detection in the wild: Past, present and future / S. Zafeiriou, C. Zhang, Z. Zhang // Comput. Vis. Image Underst. — 2015. — Vol. 138. — P. 1-24.

85. Zhang, C. Boosting-Based Face Detection and Adaptation / C. Zhang, Z. Zhang. — 2010. — 140 p.

86. Comaschi, F. RASW: A run-time adaptive sliding window to improve Viola-Jones object detection / F. Comaschi et al. // 2013 7th International Conference on Distributed Smart Cameras, ICDSC 2013. — 2013.

87. Canny, J. A Computational Approach to Edge Detection / J. Canny // IEEE Trans. Pattern Anal. Mach. Intell. — 1986. — Vol. 8. — № 6. — P. 679-698.

88. Rokach, L. Data mining with decision trees: theory and applications / L. Rokach, O. Maimom // Data Mining and Knowledge Discovery. — 2007. — 242 p.

89. Норушис, А. Построение логических (древообразных) классификаторов методами нисходящего поиска (обзор) / А. Норушис // Статистические проблемы управления. — Вильнюс, 1990. — Т. 93. — С. 131-158.

90. POWERS, D.M.W. Evaluation: From Precision, Recall and F-Measure To Roc, Informedness, Markedness & Correlation / D.M.W. POWERS // J. Mach. Learn. Technol. — 2011. — Vol. 2. — № 1. — P. 37-63.

91. Thompson, W.R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples / W.R. Thompson // Biometrika. — 1933. — Vol. 25. — № 3-4. — P. 285-294.

92. Jones, M. Fast Multi-view Face Detection / M. Jones, P. Viola // Mitsubishi Electr. Res. Lab TR2000396. — 2003. — № July.

93. Lienhart, R. A detector tree of boosted classifiers for real-time object detection and tracking / R. Lienhart, L. Liang, A. Kuranov // Proceedings - IEEE International Conference on Multimedia and Expo. — 2003. — Vol. 2. — P. II277-II280.

94. Herbert, R. Some Aspects of the Sequential Design of Experiments / R. Herbert // Bull. Am. Math. Soc. — 1952. — Vol. 58. — № 5. — P. 527-535.

95. Саттон, Р.С. Обучение с подкреплением / Р.С. Саттон, Э.Г. Барто. — М.: БИНОМ. Лаборатория знаний, 2012. — 399 с.

96. Gittins, J.C. Bandit processes and dynamic allocation indices / J.C. Gittins // Statistics (Ber). — 1979. — Vol. 41. — № 2. — P. 148-177.

97. Thathachar, M.A.L. A New Approach to the Design of Reinforcement Schemes for Learning Automata / M.A.L. Thathachar, P.S. Sastry // IEEE Trans. Syst. Man Cybern. — 1985. — Vol. SMC-15. — № 1. — P. 168-175.

98. Tokic, M. Value-difference based exploration: Adaptive control between epsilon-greedy and softmax / M. Tokic, G. Palm // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2011. — Vol. 7006 LNAI. — P. 335-346.

99. Watkins, C.J.C.H. Learning from Delayed Rewards / C.J.C.H. Watkins. — Cambridge University, 1989.

100. Luce, R.D. Individual choice behavior / R.D. Luce // Individ. Choice Behav. — 1959.

101. Гришилов А.А. Математические методы построения прогнозов / А.А. Гришилов, В.А. Стакун, А.А. Стакун. — М.: Радио и связь, 1997. — 112 с.

102. Nikolaev, D.P. Diamond recognition algorithm using two-channel x-ray radiographic separator / D.P. Nikolaev et al. // Proc. SPIE 9445, Seventh Int. Conf. Mach. Vis. (ICMV 2014). — № 944507.

103. Жуковский, А.Е. Синтез обучающей выборки на основе реальных данных в задачах распознавания изображений / А.Е. Жуковский и др. // Информационные технологии и системы (ИТиС'12): сборник трудов конференции. — М., 2012. — С. 377-382.

104. Ilin, D. Creating training datasets for OCR in mobile device video stream / D. Ilin, V. Krivtsov // Proceedings 29th European Conference on Modelling and Simulation. — 2015.

105. Арлазаров, В.В. Формирование множества графических образов символов в задачах обучения классификатора символов / В.В. Арлазаров, Н. Решетняк, О.А. Славин // Труды Института системного анализа РАН. Обработка информационных и графических ресурсов. — 2014. — Т. 64. — № 4. — С. 7379.

106. OpenCV: Cascade Classifier Training [Электронный ресурс]. — Режим доступа: http: //docs. opencv.org/2.4/doc/user_guide/ug_traincascade. html (дата обращения: 01.09.2017).

107. Bradski, G. Learning OpenCV 3. Computer Vision in C++ with the OpenCV Library / G. Bradski, A. Kaehler. — O'Reilly Media, 2016. — 1024 p.

108. Howse, J. OpenCV Blueprints. / J. Howse et al. — Packt Publishing, 2015. 366 p.

109. Computer Vision System Toolbox [Электронный ресурс]. — Режим доступа: https://www.mathworks.com/help/vision/ (дата обращения: 01.09.2017).

110. Visual Studio Community [Электронный ресурс]. — Режим доступа: https://www.visualstudio.com/ru/vs/community/ (дата обращения: 01.09.2017).

111. CMake [Электронный ресурс]. Режим доступа: https://cmake.org/ (дата обращения: 01.09.2017).

112. Страуструп, Б. Язык программирования С++ / Б. Страуструп. — БИНОМ, 2015. — 1136 с.

113. JTC1/SC22/WG21 - The C++ Standards Committee - ISOCPP [Электронный ресурс]. Режим доступа: http://www.open-std.org/jtc1/sc22/wg21/ (дата обращения: 01.09.2017).

114. Шлее, М. Qt 5.3 Профессиональное программирование на C++ / М. Шлее. — СПб.: БХВ-Петербург, 2015. — 928 с.

115. Саммерфилд, М. Qt. Профессиональное программирование. Разработка кроссплатформенных приложений на С++ / М. Саммерфилд. — СПб.: Символ-Плюс, 2011. — 560 с.

116. Гербер, Р. Оптимизация ПО. Сборник рецептов / Р. Гербер и др. — СПб.: Питер, 2010. — 352 c.

117. A C++ library for interacting with JSON [Электронный ресурс]. — Режим доступа: https://github.com/open-source-parsers/jsoncpp (дата обращения: 01.09.2017).

118. Гамма, Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования / Э. Гамма и др. — СПб.: Питер, 2007. — 366 с.

119. Khanipov, T. Vision-based industrial automatic vehicle classifier / T. Khanipov et al. // Proceedings of SPIE vol. 9445 (ICMV-2014). — 2015. — P. 9445-9445-5.

120. Коптелов, И. Макет автоматического классификатора транспортных средств / И. Коптелов и др. // Информационные технологии и системы (ИТиС'14): сборник трудов конференции. — 2014. — С. 350-256.

121. Григорьев, А.С. Архитектура системы детекции и классификации автомобилей средствами технического зрения в естественных условиях / А.С. Григорьев и др. // Сенсорные системы. — 2017. —Т. 31. — № 1. — С. 72-84.

122. Когнитив Автороботы - Cognitive Technologies - Разработка беспилотных транспортных средств [Электронный ресурс]. — Режим доступа: http://cognitivepilot.com/ (дата обращения: 01.09.2017).

123. Прун, В.Е. Разработка мультисенсорного комплекса компьютерного (технического) зрения на базе грузового автомобиля КАМАЗ / В.Е. Прун, В.В. Постников, А.В. Панченко // БЕСПИЛОТНЫЕ ТРАНСПОРТНЫЕ СРЕДСТВА: ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ сборник материалов 94 международной научно-технической конференции Ассоциации автомобильных инженеров. — Нижний Новгород: Нижегородский государственный технический университет им. Р.Е. Алексеева, 2016. — С. 246-248.

124. Распознавание Паспорта РФ на мобильном телефоне [Электронный ресурс]. Режим доступа: https://habrahabr.ru/company/smartengines/blog/252703/ (дата обращения: 01.09.2017).

125. Smart IDReader [Электронный ресурс]. Режим доступа: http://smartidreader.ru/ (дата обращения: 01.09.2017).

126. RUDevices [Электронный ресурс]. Режим доступа: http://rudevices.ru/ (дата обращения: 01.09.2017).

127. Полевой, Д.П. Задача контроля качества при создании и развитии систем оптического распознавания печатного текста / Д.П. Полевой, О.С. Самойлов // Технологии программирования и хранения данных. — 2009. — Т. 45. — C. 251-259.

128. Kim, K. Computer Vision Final Project: Viola-Jones & Morphology-based Face Detector [Электронный ресурс] / K. Kim. — 2005. — Режим доступа: http: //www.cc. gatech.edu/~kihwan23/imageCV/Final2005/FinalProj ect_KH.htm (дата обращения: 01.09.2015).

Список публикаций автора

Публикации в изданиях, входящих в Перечень ВАК РФ

1. Усилин, С.А. Использование метода преследования для повышения быстродействия алгоритма многоклассовой детекции объектов в видеопотоке каскадами Виолы-Джонса / С.А. Усилин // Труды Института системного анализа Российской академии наук (ИСА РАН). — М.: Поли Принт Сервис, 2017. — Т. 67.

— №1. — С. 75-82.

2. Поляков, И.В. Построение оптимальных каскадов Виолы-Джонса при помощи «жадных» алгоритмов перебора управляющих параметров с промежуточным контролем по валидационной выборке / И.В. Поляков, Е.Г. Кузнецов, С.А. Усилин, Д.П. Николаев // Сенсорные системы. — М.: Наука, 2016.

— Т. 30. — №3. — С. 241-248.

3. Усилин, С.А. Распознавание гильоширных элементов: определение страниц паспорта РФ / С.А. Усилин, Д.П. Николаев, Д.Л. Шоломов, В.В. Арлазаров // Труды Института системного анализа РАН. Обработка информационных и графических ресурсов. — М.: URSS, 2013. — Т. 63. — № 3. — С. 106-110.

4. Усилин, С.А. Локализация, ориентация и идентификация документов с фиксированной геометрией на изображении / С.А. Усилин, Д.П. Николаев, В.В. Постников // Труды Института системного анализа РАН. Обработка информационных и графических ресурсов. — М.: URSS, 2010. — Т. 58. — С. 248261.

5. Гладилин, С.А. Построение устойчивых признаков детекции и классификации объектов, не обладающих характерными яркостными контрастами / С.А. Усилин, Д.П. Николаев, А.А. Котов, С.А. Гладилин // Информационные технологии и вычислительные системы. — М.: ФИЦ ИУ РАН, 2014. — Т. 1. — С. 61-72.

Публикации в трудах профильных конференций

6. Fedorenko, F. Real-time object-to-features vectorisation via Siamese neural networks / F. Fedorenko, S. Usilin // Proceedings of the Ninth International Conference on Machine Vision (ICMV 2016). — SPIE, 2017. — Vol. 10341. — 103411R. (SCOPUS)

7. Minkina, A. Generalization of the Viola-Jones method as a Decision Tree of Strong Classifiers for Real-time Object Recognition in Video Stream / A. Minkina, D. Nikolaev, S. Usilin, V. Kozyrev // Proceedings of the Seventh International Conference on Machine Vision (ICMV 2014). — SPIE, 2015. — Vol. 9445. — 944517. (SCOPUS)

8. Usilin, S. Visual Appearance Based Document Image Classification / S. Usilin, D. Nikolaev, V. Postnikov, G. Schaefer // Proceedings of the 17th IEEE International Conference on Image Processing (ICIP 2010). — IEEE, 2010. — P. 2133-2136. (SCOPUS, WoS)

9. Кузнецова, Е.Г. Модификация слабых классификаторов машины Виолы-Джонса для мультиспектральных изображений / Е.Г. Кузнецова, С.А. Усилин, А. Г. Минкина, Д.П. Николаев // Информационные технологии и системы (ИТиС'15): сборник трудов конференции. — М.: ИППИ, 2015. — С. 329-337.

10. Минкина, А.Г. Обобщение метода Виолы и Джонса в виде решающего дерева сильных классификаторов для распознавания объектов в видеопотоке в режиме реального времени / А.Г. Минкина, А.С. Григорьев, С.А. Усилин, Д.В. Полевой, Д.П. Николаев // Информационные технологии и системы (ИТиС'14): сборник трудов конференции. — М.: ИППИ, 2014. — С. 158-163.

11. Григорьев, А.С. Ускорение поиска объектов в видеопотоке методом Виолы-Джонса путем адаптивного выбора распознающих каскадов / А.С. Григорьев, С.А. Усилин, Н.Д. Петрович // Труды 55-й научной конференции МФТИ. — Москва-Долгопрудный-Жуковский : МФТИ, 2012. — С. 11-12.

12. Жуковский, А.Е. Синтез обучающей выборки на основе реальных данных в задачах распознавания изображений / А.Е. Жуковский, Н.А. Тарасова, С.А. Усилин, Д.П. Николаев // Информационные технологии и системы (ИТиС'12): сборник трудов конференции. — М.: ИППИ, 2012. — С. 377-382.

13. Котов, А.А. Построение устойчивых признаков для алгоритма Виолы и Джонса в задаче классификации транспортных средств / А.А. Котов, С.А. Усилин, Д.П. Николаев // Информационные технологии и системы (ИТиС'12): сборник трудов конференции. — М.: ИППИ, 2012. — С. 383-388.

14. Usilin, S. Guilloche Elements Recognition Applied to Passport Page Processing / S. Usilin, D. Nikolaev, D. Sholomov // Proceedings of the 8th Open German-Russian Workshop «Pattern Recognition and Image Understanding» 0GRW-8-2011. — Nizhny Novgorod : Lobachevsky State University of Nizhny Novgorod, 2011. — P. 303306.

15. Жуковский, А.Е. Применение активного обучения к методу Виола-Джонса поиска объектов на изображении / А.Е. Жуковский, Д.П. Николаев, С.А. Усилин // Информационные технологии и системы (ИТиС'11): сборник трудов конференции. — М.: ИППИ, 2011. — С. 234-240.

16. Усилин, С.А. Поиск объектов в видеопотоке при известных кинематике и геометрической модели сцены / С.А. Усилин, Д.П. Николаев, В.В. Постников // Труды 53-й научной конференции МФТИ. — Москва-Долгопрудный-Жуковский : МФТИ, 2010. — С. 67-69.

17. Усилин, С.А. Идентификация изображений документов методами, предназначенными для поиска лиц / С.А. Усилин, Д.П. Николаев, В.В. Постников // Информационные технологии и системы (ИТиС'10): сборник трудов конференции. — М.: ИППИ, 2010. — С. 132-137.

Патенты, свидетельства о регистрации программ для ЭВМ

18. Автономное автоматизированное рабочее место контроля паспортных документов : Патент на полезную модель № 166152 Российская Федерация / В.В. Арлазаров, А.П. Гладков, Д.П. Николаев, С.А. Усилин ; патентообладатель Общество с ограниченной ответственностью «СМАРТ ЭНДЖИНС СЕРВИС». — № 2016122432; заявл. 07.06.2016 ; опубл. 26.10.2016.

19. Автоматизированное рабочее место контроля паспортных документов : Патент на полезную модель № 166038 Российская Федерация / В.В. Арлазаров,

А.П. Гладков, Д.П. Николаев, С.А. Усилин ; патентообладатель Общество с ограниченной ответственностью «СМАРТ ЭНДЖИНС СЕРВИС». — № 2016106183; заявл. 25.02.2016 ; опубл. 24.10.2016.

20. Программа для распознавания идентификационных карт личности «Smart IDReader» : свидетельство о государственной регистрации программы для ЭВМ № 2016616961 / В.В. Арлазаров, Д.П. Николаев, С.А. Усилин, К.Б. Булатов, Т.С. Чернов, Д.Г. Слугин, Д.А. Ильин, П.В. Безматерных, А.А. Муковозов, Е.Е. Лимонова. — № 2016612014 ; заявл. 10.03.2016 ; опубл. 22.06.2016.

21. Библиотека для распознавания в видеопотоке паспорта гражданина Российской Федерации «Smart PassportReader» : свидетельство о государственной регистрации программы для ЭВМ № 2015616071 / В.В. Арлазаров, К.Б. Булатов, Д.А. Ильин, А.В. Куроптев, Д.П. Николаев, Д.В. Полевой, С.А. Усилин, И.А. Фараджев, Т.С. Чернов. — № 2015612880 ; заявл. 10.04.2015 ; опубл. 29.05.2015.

22. Программа для распознавания и детектирования автомобилей, с учетом их ракурса и направления движения : свидетельство о государственной регистрации программы для ЭВМ № 2015610891 / Д.В. Полевой, С.А. Усилин, П.В. Безматерных. — № 2014662041 ; заявл. 26.11.2014 ; опубл. 20.01.2015.

23. Способ автоматической классификации транспортных средств : Пат. 2486597 C1 Российская Федерация / Д.П. Николаев, В.В. Постников, Т.М. Ханипов, С.А. Усилин, А.С. Григорьев ; патентообладатель Общество с ограниченной ответственностью «Техно-траффик». — № 2012105146/11 ; заявл. 09.02.2012 ; опубл. 27.06.2013, Бюл. № 18. — 15 с.

127

Приложение А Модуль обучения программного комплекса objed

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

Инструментарий оЬ^её является открытым программным обеспечением, исходный код о^её доступен по адресу: МрБ: //github.com/usilinsergey/obi её.

В данном приложении представлено краткое описание основных составляющих инструментарий оЬ]её.

Содержание

А.1. Инструмент разметки набора изображений и анализа результатов детектирования objedmarker.......................................................................................128

А.2. Инструмент подготовки обучающего набора изображений objedcutcli........130

А.3. Инструмент обучения классификатора objedtraincli.......................................131

А.4. Инструмент визуального контроля работы классификатора objedcheck......135

А.5. Инструмент анализа качества работы классификатора objedruncli...............136

А.1. Инструмент разметки набора изображений и анализа результатов детектирования objedmarker

Инструмент разметки набора изображений и анализа результатов детектирования оЬдеёшагкег представляет собой программу с графическим пользовательским интерфейсом, выполняющую две основные задачи:

- разметка набора изображений на предмет наличия объекта (в русскоязычной литературе данная процедура часто упоминается как «изготовление идеала» [127]);

- сравнение результатов детектирования с «идеальными» (то есть, созданными вручную оператором).

Пользовательский интерфейс программы оЬ^еёшагкег представлен на рисунке А.1. Главное окно разделено на две основные области: слева находится область панелей инструментов, справа - область просмотра изображения и разметки.

Рисунок А.1

— Внешний вид программы оЬдеёшагкег

Открытие набора изображений выполняется с помощью команды меню File ^ Open Dataset... (Ctrl+O). При открытии указывается директория изображений (Directory), а также имя размечаемых данных (Ideal Markup). Опционально можно указать имя результата детектирования (Run Markup) для сравнения результата детектирования с «идеальными» значениями.

С помощью диалогового окна Option Size Properties следует указать характерные размеры размечаемых объектов (базовый размер задает соотношение сторон размечаемого объекта, минимальный и максимальный размеры - границы размечаемых объектов). Программа objedmarker при снятии флажка Base Object Size возможна разметка объектов с произвольным соотношением сторон. Цвет размечаемых объектов указывается с помощью диалогового окна Editor Properties.

Процесс разметки каждого изображения состоит из следующих двух шагов:

Шаг 1. С помощью левой кнопки мыши (устанавливает границы нового объекта) и клавиш W и S (используются при нажатой кнопке мыши и позволяют увеличивать или уменьшать размер нового объекта) выполняется разметка всех видимых объектов. Удаление случайного объекта выполняется с помощью правой кнопки мыши. Перемещение и изменение размера выполняется также с помощью кнопки мыши).

Шаг 2. Если на изображении все присутствующие объекты размечены и нет никаких сомнительных элементов (например, присутствует объект наполовину видимый, слишком маленький, размытый и т.п.), то такое изображение считается размеченным полностью и с помощью клавиши Space помечается «звездочкой». В противном случае изображение считается размеченным частично и не помечается «звездочкой».

Навигация между изображениями выполняется с помощью клавиш A и D. Сохранение результатов разметки выполняется автоматически в директорию <директория изображений>/<имя размечаемых данных>. Для повышения визуального качества изображения присутствует возможность контрастирования с помощью панели Adjust Image.

При сравнении результата детектирования с «идеальной разметкой» необходимо с помощью панели Compare Markup указать порог взаимного перекрытия объектов (от 0.0 до 1.0). Далее, с помощью комбинаций клавиш Shift+D и Shift+A можно перемещаться к следующему и предыдущем отличию соответственно. С помощью левой кнопки мыши можно добавить результат детектирования в «идеал» (полезно при условии непреднамеренного пропуска объекта при создании «идеальной» разметки).

А.2. Инструмент подготовки обучающего набора изображений objedcutcli

Инструмент подготовки обучающего набора изображений objedcutcli представляет собой программу с интерфейсом командной строки и предназначен для подготовки обучающих наборов изображений на основе размеченного набора изображений.

При запуске программы objedcutcli необходимо передать в качестве аргумента путь к конфигурационному файлу в формате INI. Чтобы сгенерировать шаблон конфигурационного файла запустите программу следующим образом:

objedcutcli -g [config_path]

Ниже представлено краткое описание основных элементов конфигурационного файла.

Mode. Задает режим функционирования программы objedcutcli. В режиме cutting происходит подготовка обучающего набора данных. В режиме statistics выполняется подсчет статистической информации по размеченному изображению:

- общее количество изображений в размеченном наборе;

- количество изображений, размеченных полностью;

- количество размеченных объектов;

- характерные размеры размеченных объектов;

MarkupName. Задает имя размечаемых данных (должно совпадать со значением Ideal Markup, указанным при разметке).

LeftMargin, RightMargin, TopMargin, BottomMargin. Указывают насколько необходимо расширить изображение размеченного объекта при вырезании слева, справа, сверху, снизу соответственно. Данные величины задаются в долях от ширины (высоты).

PositiveDataset, NegativeDataset. Указывают директории для сохранения положительной и отрицательной обучающих выборок. Если данные параметры не указаны, то соответствующая обучающая выборка не будет сгенерирована.

OutputFormat. Указывают формат сохранения обучающей выборки. Поддерживается TIFF и JPEG.

MinObjectWidth, MaxObjectWidth, MinObjectHeight, MaxObjectHeight. Указывают минимальные и максимальные размеры вырезываемых объектов.

DatasetList. Содержит список размеченных наборов данных. Указывается путь к директориям с изображениями, внутри которых должны быть соответствующие директории с разметкой.

А.3. Инструмент обучения классификатора objedtraincli

Инструмент обучения классификатора objedtraincli представляет собой программу с интерфейсом командной строки и предназначен для обучения бинарных классификаторов типа Виолы и Джонса, описанных в данной работе.

При запуске программы objedtraincli необходимо передать в качестве аргумента путь к конфигурационному файлу в формате INI. Чтобы сгенерировать шаблон конфигурационного файла запустите программу следующим образом:

objedtraincli -g [config_path]

Ниже представлено краткое описание основных элементов конфигурационного файла.

ClassifierType. Задает высокоуровневую структуру классификатора. Возможно обучение каскадного классификатора (cascadeClassifier) и древовидного классификатора (treeClassifier) в соответствии с методом, описанным в разделе 3.

ОазэШегРаШ. Указывает путь и имя файла, в который будет сохранен классификатор. Если по указанному пути уже существует классификатор, то он будет «дообучен».

ОаээШег'^^Ь, ОазэШегН^М. Задает физические размеры в пикселях обучаемого классификатора. Размеры должны быть нечетные.

М1п1шиш8еа1е, Мах1шиш8еа1е, 81ер8еа1е. Задает параметры масштабирования, при которых будет обучаться классификатор, то есть при обучении будут использоваться все размеры начиная с С/аяя^е^^ге • М1П1шиш5са/е до С/аяя^е^ге • Мах1шиш5са/е с множителем

NegativeCount. Задает количество отрицательных примеров, которые должны быть собраны для обучения очередного сильного классификатора. В соответствии со спецификой программы оЬ]её реальное количество собранных отрицательных примеров будет не меньше, чем Мед^шеСоип^

РозШуеСоип^Т^еэ^М. Задает порог обучения очередного сильного классификатора по количеству положительных примеров. Другими словами, если для обучения очередного сильного классификатора удалось собрать положительных примеров Роя^шеСои^ < Роя^шеСоипгГЛгеяЛоШ, то обучение будет остановлено. В основном, применяется при обучении древовидного классификатора.

NegativeCountThresho1d. Задает порог обучения очередного сильного классификатора по количеству отрицательных примеров. Другими словами, если для обучения очередного сильного классификатора удалось собрать отрицательных примеров Мед^шеСои^ < Меда^шеСоипгГЛгеяЛоШ, то обучение будет остановлено.

WeightShift. Задает первоначальный сдвиг ценности обучающей выборки. Если Ж^дЛ^М/^ ближе к 1.0, то положительные примеры считаются более ценными, если Ж^дЛ^М/^ ближе к 0.0, то отрицательные примеры считаются более ценными.

LevelCount. Задает количество сильных классификаторов, которые следует обучить в текущем процессе (запуске). Если LevelCount = 0, то ограничений по количеству обучаемых сильных классификаторов отсутствует.

WcCount. Задает количество слабых классификаторов, которые будут добавлены в сильный классификатор на очередной итерации обучения при условии установки флага StoppingCriterion = Count или StoppingCriterion = Any. Если WcCount = 0, то ограничений по количеству добавляемых слабых классификаторов отсутствует.

FalseNegativeRate, FalsePositiveRate. Задают критерии обучения очередного сильного классификатора в качественных характеристиках. Оценка качественных характеристик вычисляется на основе актуальной обучающей выборки. Данные критерии действуют при условии установки флага StoppingCriterion = Rate или StoppingCriterion = Any.

PositiveDatasetList, NegativeDatasetList. Задают списки положительных и отрицательных наборов изображений для обучения.

WcLineList. Задает семейства слабых классификаторов, которые могут быть использованы при обучении. Указание соответствующего семейства выполняется с помощью текстовой строки следующего вида:

<ТипКлассификатора> -preproc=<ВидПрепроцессинга> <ДопПараметры>

В настоящий момент поддерживаются следующие типы классификаторов:

- Haar1StumpWc - ступенчатый классификатор поверх 1-прямоугольных признаков Хаара, вычисляемых поверх одноканального изображения;

- Haar1PwWc - кусочно-постоянный классификатор поверх 1-прямоугольных признаков Хаара, вычисляемых поверх одноканального изображения;

- Haar2StumpWc - ступенчатый классификатор поверх 2-прямоугольных признаков Хаара, вычисляемых поверх одноканального изображения;

- Haar2PwWc - кусочно-постоянный классификатор поверх 2-прямоугольных признаков Хаара, вычисляемых поверх одноканального изображения;

- Haar3StumpWc - ступенчатый классификатор поверх 3-прямоугольных признаков Хаара, вычисляемых поверх одноканального изображения;

- Haar3PwWc - кусочно-постоянный классификатор поверх 3-прямоугольных признаков Хаара, вычисляемых поверх одноканального изображения;

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

- gray - «осерение» изображения путем усреднения каналов, на входе -трехканальное изображение, на выходе - одноканальное изображение;

- saturation - «осерение» путем вычисления насыщенности, на входе -трехканальное изображение, на выходе - одноканальное изображение;

- channel<index> - «осерение» путем взятия канала <index>, на входе -трехканальное изображение, на выходе - одноканальное изображение;

- gradient<direction> - вычисление модуля градиента в трех режимах: при <direction>=0 вычисляется классическое значение модуля градиента, при <direction>=1 вычисляется градиент прямых границ, при <direction>=2 вычисляется градиент диагональных границ;

- canny<direction> - вычисление карты границ в трех режимах: при <direction>=0 вычисляется классическая карта границ, при <direction>=1 вычисляется карта прямых границ, при <direction>=2 вычисляется карта направленных границ;

Препроцессинг может состоять из нескольких элементов, при этом элементы должны быть разделены вертикальной чертой, например: gray|gradient2.

Для кусочно-постоянных классификаторов необходимо указать кол-во интервалов с помощью параметра bin, например -bin=16.

Ширины и высоты образующих прямоугольных областей, а также допустимые зазоры для признаков Хаара задаются с помощью диапазонов следующим образом: <мин_знач>:<макс_знач>/<шаг>. Например, запись -wd=4:16/4 задает диапазон ширин, состоящий из 4, 8, 12 и 16.

С помощью дополнительного параметра normalize, принимающего булевое значение, можно управлять нормализацией значения признака. Если -normalize=true, то значение признака нормализуется на сумму яркостей внутри образующих прямоугольников. Если-normalize=false, то значение признака нормализуется исходя их максимально допустимых значений.

А.4. Инструмент визуального контроля работы классификатора objedcheck

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

Программа позволяет указать директорию с тестовыми изображениями, а также детектор (сущность инструментария objed, которая дополнительно к

<У Objedcheck ** - □ X

File View Actions Help Image List

I 00000421.jpg

00000422.jpg

00000423.jpg

00000424.jpg

00000425.jpg

00000426.jpg

00000427.jpg

imywft.inn

Proper Ses Detector: Minimum Power

Console

Image 000C

leaded

10 cbject:

\ 4 4 ro )

Рисунок А.2

— Внешний вид программы objedcheck

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

Под детекцией будем понимать обрамляющий прямоугольник и количество «срабатываний», которые были объединены в данную детекцию (мощность детекции). Программа objedcheck позволяет фильтровать детекци с малым значением мощности с помощью панели Properties.

Дополнительно к визуализации результатов детектирования, objedcheck позволяет визуализировать различные варианты препроцессинга, описанного в разделе А.3. Для этого необходимо открыть диалоговое окно Image View с помощью пункта меню View^Open Image View... и в появившемся диалоговом окне указать необходимую строку препроцессинга.

А.5. Инструмент анализа качества работы классификатора objedruncli

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

При запуске программы objedruncli необходимо передать в качестве аргумента путь к конфигурационному файлу в формате INI. Чтобы сгенерировать шаблон конфигурационного файла запустите программу следующим образом:

objedruncli -g [config_path]

Ниже представлено краткое описание основных элементов конфигурационного файла.

DetectorPath. Путь к детектору (аналогично программе objedckeck).

MinimumPower. Минимальное значение мощности детекций, которые принимаются в расчет.

IdealMarkupName. Задает имя размечаемых данных (должно совпадать со значением Ideal Markup, указанным при разметке данного тестового набора).

SaveRealMarkup. Указывает следует ли сохранять результат детектирования для последующего анализа с помощью objedmarker. Если true, то результат детектирования будет сохранен в директорию <IdealMarkupName>-yyyymmdd-HHMMss, где yyyymmdd-HHMMss задает дату и время начала процедуры детектирования.

Threshold. Указывает минимальный порог перекрытия найденного объекта и «идеального» для принятия решения о детектировании. Подробнее про оценку качества детекции изложено в разделе 1.2.3.

DatasetList. Задает список тестовых наборов изображений

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

- TP - true positive, количество верно найденных объектов;

- FP - false positive, количество ошибочно найденных объектов;

- FN - false negative, количество ненайденных объектов;

- IC - image count, количество обработанных изображений.

138

Приложение Б Алгоритм AdaBoost

Алгоритм AdaBoost (сокр. от adaptive boosting) - алгоритм машинного обучения, предложенный Йоавом Фройндом (Yoav Freund) и Робертом Шапиром (Robert Schapire). Является мета-алгоритмом, в процессе обучения строит композицию из базовых алгоритмов обучения для улучшения их эффективности. AdaBoost является алгоритмом адаптивного бустинга в том смысле, что каждый следующий классификатор строится по объектам, которые плохо классифицируются предыдущими классификаторами.

Изучим принцип работы алгоритма AdaBoost более подробно на примере задачи классификации на два класса, то есть ¥ = {-1, +1}. Пусть есть множество слабых классификаторов bt:X^Y. Будем строить сильный классификатор с помощью алгоритма AdaBoost следующего вида:

q(x) = sign (у qtbt(x}), хеХ. (Б. 1)

Определим функционал качества композиции как число ошибок, допускаемых ею на обучающей выборке Хг:

г

Cr = ^footo) < 0] = у yt y(aA(*i)) < 0

га(

¿=i ¿=i

т

t=i

, *f е Хг. (Б.2)

В итеративном алгоритме АёаВооБ1 используются два основополагающих приема:

1. При добавлении в композицию очередного слагаемого асЬс(х) оптимизируется только базовый алгоритм Ьс(х) и коэффициент при нём , а все предыдущие слагаемые а1Ь1(х),..., ас-1Ьс-1(х) остаются нетронутыми.

i

2. Пороговая функция потерь в функционале качества заменяется непрерывно дифференцируемой оценкой сверху:

ЬьФд <0]< е-у1а(х^ Xi е X1. (Б.3)

Оценим функционал QT сверху:

i i QT < QT =} e-yilt=i(atbt(xi)) = у e-yilt^^(atbt(xi'))e-yiatbt(xi') х

1 (Б.4)

i=1 i=1 v j ех1.

Обозначим Wi = е-^^1 atbt(xi). Заметим, что величина wt (назовем ее

«весом» обучающего примера xt) не зависит от атЬт и может быть вычислена

перед построением очередного слабого классификатора Ьт.

Введем понятие нормированного веса wt —, а также определим два

lj=iwj

функционала качества слабого классификатора Ь(х): суммарный вес ошибочных (negative) классификаций N(b) и суммарный вес правильных (positive) классификаций Р( b):

N(b)=ywt [b(xd = -yi]) (Б.5)

=1

Р(Ь) = ^щ [b(xi)=yi]. (Б 6)

=1

Заметим, что в силу нормировки веса справедливо равенство N + Р = 1.

Теорема Б.1. Пусть для нормированных весов ..., существует базовый классификатор Ь, для которого справедливо М(Ь) < -. Тогда минимум

функционала достигается при Ьт = а^тт(М(Ь)) и аТ = 11п ^^^

Доказательство. Заметим, что для любых а £ М и Ь £ {-1, +1} справедливо следующее тождество: е-аЬ = е-а[Ь = 1] + еа[Ь = -1]. Тогда, так как уь £ ¥ = {-1, +1} преобразуем функционал следующим образом:

(г г ч г

е-" ^ ^ [Ь(х^) = у^ + е« ^ ^ [Ь(х^) = -у^ (Б.7)

¿=1 ¿=1 / у=1

Из формулы (Б.7) следует:

<5Т = + . (5т-1 = (е-«(1 - М) + . дт-1. (Б.8)

Дифференцируя по параметру а и приравнивая к нулю производную

1, 1-Л(ЬГ) „

получаем оптимальное значение ат = -1п ^ ^ . Подставим найденное выражение ат обратно в формулу, получим:

<5т = <5т-1 . (ТЩ-Ю + 7^(1-^)) = 2 . (?Т-1 . Т^-М2. (Б.9)

Поскольку не зависит от ат и Ьт, минимизация эквивалентна

максимизации N - М2 при условии 0 < N < 1 То есть Ьт = а^тт(М(Ь)).

2 ь

Теорема доказана.

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

Теорема Б.2. Если на каждом шаге метод обучения обеспечивает построение

слабого классификатора bt такого, что N(bt) = £t, где 0 < £t < £ для некоторого i

0 < £ < -, то за конечное число шагов будет построен корректный сильный

классификатор а(х).

Доказательство. Из формулы (Б.9) следует:

< QT < 2 • (?T-1V7—< 2 . & (V£ - £2)7 (Б.10)

Так как 0 < £ < то V£ — £2 < 1. Следовательно, наступит момент, когда

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

Реализация алгоритма в виде блок-схемы показана на рисунке Б.2. Остановимся отдельно на идее назначении весов обучающим примерам. На каждом шаге итерации вес объекта увеличивается, если предыдущий слабый классификатор допустил на нем ошибку и уменьшается в противном случае. Таким образом, непосредственно перед настройкой очередного слабого классификатора наибольший вес накапливается у тех объектов, которые чаще оказывались трудными для предыдущих слабых классификаторов. Эта идея отражена на рисунке Б.1.

/

Шаг 1 Шаг 2 Шаг 3 Результат

Рисунок Б.1 — Наглядная демонстрация принципа алгоритма АёаВооБ!: поэтапное построение сильного классификатора из трех слабых (источник [128])

^ Начало ^

Х = [(Х1,у1),^,(х1,у1)} 1 = (Ъ:Х^ {+1,-1}}

1

* )

1 г

шц = 1л = 1,...,1

1

Здесь X - обучающая выборка, 1 - множество слабых классификаторов

Выполним начальную инициализацию весов обучающей выборки

Обучим слабые классификаторы на взвешенной обучающей выборке и выберем такой слабый классификатор Ъ, который минимизирует взвешенную ошибку классификации е1

Определим коэффициент а( вхождения в линейную комбинацию найденного слабого классификатора

Обновим веса обучающих примеров в соответствии с выбранным слабым классификатором Ъ1

Цикл выбора классификатора

Рисунок Б.2 — Блок-схема алгоритма АёаВооБ1

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

144

Приложение В Охранные документы на результаты интеллектуальной деятельности

Стр.: 1