Цель НИР – разработка системы захвата и последующего воспроизведения мимики лица.
Захват движений может быть выполнен при работе со специально приглашенными лицами, например, спортсменами или артистами, являющимся профессионалами в области интереса. Также можно говорить о захвате (импорте) движений, наблюдаемых при просмотре фильма, например, документального фильма о животных.
Захваченные движения независимо от формы хранения данных в конечном итоге используются для анимации моделей людей, представителей флоры и фауны или различных природных явлений.
Системы, принимающие захваченные движения, известны – это, например, 3ds Max или Maya.
Говоря о системах захвата движений, можно выделить три следующих подхода.
Каждый из методов имеет недостатки.
Так, датчики и неудобны в работе и непригодны для анализа мимики лица.
Маркеры замедляют получение результата при работе с готовым видео, поскольку должны быть нанесены на большом числе кадров, образующих используемый фильм.
Видеоанализ с целью захвата движений – это одна из подзадач системы искусственного зрения, не имеющая в настоящее время эффективных методов решения.
Очевидны и положительные стороны каждого из подходов.
Так, системы с датчиками и маркерами достаточно легко реализуемы и обеспечивают высокую точность передачи движений. Видеоанализ, если реализован надлежащим образом, весьма экономичен, поскольку позволяет работать с ранее отснятыми фильмами.
Задача НИР – это разработка безмаркерной, основанной на видеоанализе системы захвата мимики лица. Не очень выразительные результаты, полученные в области захвата мимики лица, позволяют говорить об актуальности настоящей работы.
Разработать систему захвата движений, ориентированную на модель человека.
На данном этапе остановимся на проблеме анимации лица. При ее решении возникают следующие задачи:
Решение последней задачи выходит за рамки настоящей работы.
Достигается фильтрацией видеопотока. Проблема хорошо изучена и не требует специального рассмотрения.
В машинном зрении часто встречаются две модификации задачи обнаружения лица – локализация лица (face localization) и отслеживание перемещения лица (face tracking). Локализация лица является упрощенным вариантом задачи обнаружения, так как опирается на знание о том, что на изображении присутствует одно и только одно лицо. Задачу отслеживания перемещения лица в видеопотоке можно сформулировать как задачу локализации лица на текущем кадре, опираясь на информацию о его положении на предыдущих кадрах.
| Задача | Исходные данные | Результат |
|---|---|---|
| Обнаружение лица | Изображение | Вынесение решения о наличии и, возможно, количестве лиц на изображении, определение их положения |
| Локализация | Изображение (или его фрагмент), содержащее ровно одно лицо | Положение лица на изображении |
| Отслеживание лица | Текущий кадр видеопотока, положение лица на предыдущих кадрах | Позиция лица в текущем кадре видео |
Задача обнаружения лица на изображении является простой для человеческого зрения, однако при попытке построения автоматической системы обнаружения лиц возникают следующие сложности:
Существующие алгоритмы обнаружения лиц можно разбить на две категории. К первой относятся методы, отталкивающиеся от опыта человека в распознавании лиц и делающие попытку формализовать и алгоритмизировать этот опыт, построив на его основе автоматическую систему распознавания. Вторая категория опирается на инструментарий распознавания образов, рассматривая задачу обнаружения лица, как частный случай задачи распознавания.
Человеческий мозг непринужденно справляется с задачей обнаружения лиц на изображениях. Естественно было бы попробовать определить и использовать принципы, которыми руководствуется мозг при решении задачи распознавания. Среди методов, делающих такую попытку, можно выделить два направления: методы распознавания "сверху вниз" основанные на знаниях и методы распознавания "снизу вверх" основанные на особенностях.
Распознавание "сверху вниз" означает построение некоторого набора правил, которым должен отвечать фрагмент изображения, для того чтобы быть признанным человеческим лицом. Этот набор правил является попыткой формализовать эмпирические знания о том, как именно выглядит лицо на изображениях и чем руководствуется человек при принятии решения, наблюдает ли он лицо или нет. Несложно построить набор простых и очевидных (как кажется) свойств изображения лица, например: лицо обычно симметрично, черты лица (глаза, носа, рот) отличаются от кожи по яркости (обычно им также соответствуют области резкого изменения яркости), черты лица расположены вполне определенным образом. Опираясь на перечисленные свойства, можно построить алгоритм, проверяющий их наличие на фрагменте изображения. К этому же семейству методик можно также отнести распознавание с помощью шаблонов, заданных разработчиком (predefined template matching). Шаблоны задают некий стандартный образ изображения лица, например, путем описания свойств отдельных областей лица и их возможного взаимного расположения. Обнаружение лица с помощью шаблона заключается в проверке каждой из областей изображения на соответствие заданному шаблону.
Принципы шаблонов и другие методы распознавания "сверху вниз" использовались, в основном, в ранних работах по обнаружению лица. Это были первые попытки формализации признаков изображений лица, к тому же вычислительные мощности компьютеров в те годы не позволяли эффективно использовать более сложные методы распознавания изображений. Несмотря на несовершенство алгоритмов, не стоит недооценивать их значение. На основе этих алгоритмов разработаны или адаптированы к конкретной проблеме многие методики, успешно применяемые в настоящее время.
Распознавание "снизу-вверх" использует инвариантные свойства (invariant features) изображений лиц, опираясь на предположение, что раз человек может без усилий распознать лицо на изображении независимо от его ориентации, условий освещения и индивидуальных особенностей, то должны существовать некоторые признаки присутствия лиц на изображении, инвариантные относительно условий съемки. Алгоритм работы методов распознавания "снизу вверх" может быть кратко описан следующим образом:
Обнаружение элементов и особенностей, которые характерны для изображения лица
Края. Резкие переходы яркости. Края обычно соответствуют границам объектов на изображении. Используя этот факт и то, что лицо представляет собой эллипс определенных пропорций (близких для разных людей) были сделаны попытки распознавания лица с помощью карты краев (изображения, на котором обозначены резкие переходы яркости) и характерной формы лица. Резкие переходы яркости также часто соответствуют чертам лица (facial features) – границам глаз, бровей, рта, носа. Это свойство также используется в ряде работ, которые рассматривают края на изображении как признаки потенциального присутствия лица.
Яркость. Области изображения, соответствующие чертам лица, зачастую темнее, чем окружающая их кожа. Воспользовавшись этим наблюдением, ряд исследователей использует алгоритмы обнаружения и подчеркивания областей локальных минимумов яркости, рассматривая их как потенциальные черты лица. В некоторых работах делается попытка использовать определенные схемы взаимоотношений яркостей, характерных для некоторых черт лица.
Цвет. Несмотря на то, что яркость обычно является основным источником информации во многих задачах машинного зрения, цвет (благодаря дополнительной информации об оттенке объекта) является более мощным средством распознавания и различения объектов на изображении. Как показали эксперименты, цвет кожи разных людей занимает достаточно небольшую ограниченную подобласть цветового пространства, даже при рассмотрении цветов кожи различных рас. Причем основное отличие заключается в яркости, а не оттенке цвета, что позволяет сделать вывод о близости оттенка цвета кожи разных людей и использовать характерный цвет кожи как признак для распознавания лиц.
Характерная форма черт лица. Исходя из того, что процессам распознавания визуальных образов высокого уровня в мозгу предшествует некая низкоуровневая организация визуальной информации, было предложено несколько операторов, подчеркивающих области изображения, обладающими свойствами, характерными для черт лица. Такими, например, как симметричность, близость границы черт лица по форме к параболе. Результатом применения таких операторов является набор точек на изображении, с высокой вероятностью относящиеся к чертам лица. Другой близкий вариант распознавания – использование жестких или деформируемых шаблонов для обнаружения черт лица (например, глаз).
Анализ обнаруженных особенностей, вынесение решения о количестве и расположении лиц
После того, как на изображении выделены области, обладающие свойствами, характерными для человеческого лица, производится их комплексная проверка для выявления областей, действительно являющихся лицами. Сущность этой проверки зависит от характера используемых признаков, а также от избранной исследователями стратегии. Например, если в качестве признаков выступают потенциальные черты лица, обнаруженные с помощью анализа карты краев, то проверкой будет анализ их взаимного расположения с целью определения, могут ли они образовывать человеческое лицо. Если используется также распознавание по цвету, то может быть добавлено дополнительное условие, что рассматриваться в качестве потенциальных лиц будут только области близкие по цвету к оттенку кожи, причем форма областей должна быть эллиптической. Проверка соотношения обнаруженных признаков лица может быть основана:
Второе семейство методов подходит проблеме с другой стороны, и, не пытаясь в явном виде формализовать процессы, происходящие в человеческом мозге, стараются выявить закономерности и свойства изображения лица неявно, применяя методы математической статистики и машинного обучения. Методы этой категории опираются на инструментарий распознавания образов, рассматривая задачу обнаружения лица, как частный случай задачи распознавания. Изображению (или его фрагменту) ставится в соответствие некоторым образом вычисленный вектор признаков, который используется для классификации изображений на два класса – лицо/не лицо. Самый распространенный способ получения вектора признаков это использование самого изображения: каждый пиксель становится компонентом вектора, превращая черно-белое изображение N*M в вектор пространства RN*M. Недостатком такого представления является чрезвычайно высокая размерность пространства признаков. Достоинство заключается том, что используя все изображение целиком вместо вычисленных на его основе характеристик, из всей процедуры построения классификатора (включая выделение устойчивых признаков для распознавания) полностью исключается участие человека, что потенциально снижает вероятность ошибки построения неправильной модели изображения лица вследствие неверных решений и заблуждений разработчика.
Обычно поиск лиц на изображениях с помощью методов, основанных на построении математической модели изображения лица, заключается в полном переборе всех прямоугольных фрагментов изображения всевозможных размеров и проведения проверки каждого из фрагментов на наличие лица. Поскольку схема полного перебора обладает такими безусловными недостатками, как избыточность и большая вычислительная сложность, авторами применяются различные методы сокращения количества рассматриваемых фрагментов.
Моделирование класса изображений лиц с помощью Метода главных компонент (Principal Components Analysis)
Метод главных компонент (МГК) применяется для снижения размерности пространства признаков, не приводя к существенной потере информативности тренировочного набора объектов (в данном случае – изображений лиц). Применение метода главных компонент к набору векторов линейного пространства RN, позволяет перейти к такому базису пространства, что основная дисперсия набора будет направлена вдоль нескольких первых осей базиса, называемых главными осями (или главными компонентами). Таким образом, основная изменчивость векторов тренировочного набора представляется несколькими главными компонентами, и появляется возможность, отбросив оставшиеся (менее существенные), перейти к пространству существенно меньшей размерности. Натянутое на полученные таким образом главные оси подпространство размерности M << N является оптимальным среди всех пространств размерности M в том смысле, что наилучшим образом (с наименьшей ошибкой) описывает тренировочный набор изображений. В приложении к задаче обнаружения лиц, МГК обычно применяется следующим образом. После вычисления главных осей тренировочного набора изображений лиц, вектор признаков тестового изображения проецируется на подпространство, образованное главными осями. Вычисляются две величины: расстояние от проекции тестового вектора до среднего вектора тренировочного набора – Distance in Feature Space, и расстояние от тестового вектора до его проекции в подпространство главных компонент – Distance From Feature Space. Исходя из этих расстояний, выносится решение о принадлежности тестового изображения классу изображений лиц.
Моделирование класса изображений лиц с помощью Факторного анализа (Factor Analysis)
Факторный анализ (ФА), как и многие методы анализа многомерных данных, опирается на гипотезу о том, что наблюдаемые переменные являются косвенными проявления относительно небольшого числа неких скрытых факторов. ФА, таким образом, это совокупность моделей и методов, ориентированных на выявление и анализ скрытых (латентных) зависимостей между наблюдаемыми переменными. В контексте задач распознавания, наблюдаемыми переменными обычно являются признаки объектов. ФА можно рассматривать как обобщение метода главных компонент. Цель ФА в контексте задачи обнаружения лиц – получить модель изображения лица (с обозримым числом параметров), с помощью которой можно провести оценку близости тестового изображения к изображению лица.
Проблема сбора контрпримеров для тренировки классификаторов
Методы, использующие МГК и ФА требуют для тренировки классификатора только набора положительных случаев распознавания (изображений лиц), им не требуются контрпримеры (изображения без лиц). Методы, описанные ниже, нуждаются также и в контрпримерах, что поднимает проблему поиска репрезентативного набора изображений "не лица" для успешной тренировки классификатора. Эту проблему можно решить методом самонастройки. Он заключается в постепенном формировании набора контрпримеров по результатам проводимых тестов. На первом шаге для тренировки классификатора используется небольшой тренировочный набор изображений контрпримеров. Затем производится тестирование на некоторой случайной выборке из базы данных изображений. Все изображения, в ходе теста ошибочно распознанные как лица, добавляются в набор контрпримеров и тренировка повторяется.
Линейный дискриминантный анализ (Linear Discriminant Analysis).
Линейный дискриминантный анализ (ЛДА), в отличие от МГК и ФА, не ставит своей целью найти подпространство меньшей размерности, наилучшим образом описывающее набор тренировочных изображений. Его задача – найти проекцию в пространство, в котором разница между различным классами объектов максимальна. Это требование формулируется как получение максимально компактных кластеров, соответствующих различным классам, удаленных на максимально возможное расстояние. С помощью ЛДА удается получить подпространство небольшой размерности, в котором кластеры изображений лиц и "не лиц" пересекаются минимально. Производить классификацию в таком пространстве значительно проще.
Метод опорных векторов (Support Vector Machines).
Цель тренировки большинства классификаторов – минимизировать ошибку классификации на тренировочном наборе (называемую эмпирическим риском). В отличие от них, с помощью метода опорных векторов можно построить классификатор минимизирующий верхнюю оценку ожидаемой ошибки классификации (в том числе и для неизвестных объектов, не входивших в тренировочный набор). Применение метода опорных векторов к задаче обнаружения лица заключается в поиске гиперплоскости в признаковом пространстве, отделяющий класс изображений лиц от изображений "не лиц".
Возможность линейного разделения столь сложных классов, как изображения лиц и "не лиц" представляется маловероятной. Однако, классификация с помощью опорных векторов позволяет использовать аппарат ядерных функций для неявного проецирования векторов-признаков в пространство потенциально намного более высокой размерности (еще выше, чем пространство изображений!), в котором классы могут оказаться линейно разделимы. Неявное проецирование с помощью ядерных функций не приводит к усложнению вычислений, что позволяет успешно использовать линейный классификатор для линейно неразделимых классов.
Искусственные нейронные сети (Neural Networks)
Нейросети давно и успешно применяются для решения многих задач распознавания. Для решения задачи обнаружения лица применялось большое количество нейронных сетей различных архитектур, в частности: многослойные персептроны, probabilistic decision-based neural networks, и так далее. Достоинством использования нейросетей для решения задачи обнаружения лица является возможность получения классификатора, хорошо моделирующего сложную функцию распределения изображений лиц. Недостатком же является необходимость в тщательной и кропотливой настройке нейросети для получения удовлетворительного результата классификации.
Разреженная сеть окон (Sparse Network of Winnows)
Разреженная сеть окон (РСО) для обнаружения лиц представляет собой двухслойную сеть, входной слой которой состоит из узлов, каждый из которых соответствует некоторой характеристике входного изображения (генерирует 1 при наличии некоторой особенности на изображении или 0 – в противном случае), выходной же состоит всего из двух узлов, каждый из которых соответствует распознаваемым классам изображений ("лицо", "не лицо"). В качестве характеристик изображения используются флаги равенства определенным величинам среднего значения и дисперсии яркости в каждом из прямоугольных фрагментов изображения размером 1*1, 2*2, 4*4 и 10*10 (все изображения имеет размер 20*20 пикселей). Это дает пространство признаков размерности 135424. При проведении классификации на входные узлы подается информация о присутствии определенных характеристик в обрабатываемом изображении. Узлы выходного слоя вычисляют линейную комбинацию сигналов, генерируемых входными узлами. Коэффициенты линейной комбинации задаются весами связей между входными и выходными узлами. При превышении заданного порога, принимается решение о наличии лица на изображении.
РСО специально разработана для случаев классификации, когда потенциальное число характеристик объектов, важных для классификации, может быть очень велико, но неизвестно заранее. Разреженная архитектура сети позволяет использовать огромное количество свойств изображения в качестве входных данных, поскольку в процессе тренировки все несущественные характеристики отбрасываются и не замедляют, в конечном итоге, функционирование классификатора.
Скрытые Марковские модели (Hidden Markov Models)
Скрытые Марковские модели (СММ) являются одним из способов получения математической модели (описания свойств) некоторого наблюдаемого сигнала. СММ относятся к классу стохастических моделей. Стохастические модели пытаются охарактеризовать только статистические свойства сигнала, не обладая информацией о его специфических свойствах. В основу стохастических моделей положено допущение о том, что сигнал может быть описан некоторым параметрическим случайным процессом и что параметры этого процесса могут быть достаточно точно оценены некоторым, вполне определенным способом. Настроенную СММ можно рассматривать как источник некоторого случайного сигнала со вполне определенными характеристиками. Для настроенной СММ есть возможность подсчитать вероятность генерации тестового сигнала данной моделью. В приложении к задаче распознавания, представив вектор признаков объекта в виде сигнала (набора последовательных наблюдений), можно смоделировать класс объектов с помощью СММ. Вероятность принадлежности тестового объекта классу, заданному СММ оценивается как вероятностью генерации сигнала, соответствующего его вектору признаков. Настройка (обучение) СММ – состоит в модификации ее параметров для того, чтобы добиться максимальной вероятности генерации сигналов, соответствующих векторам тренировочного набора.
Для применения СММ к задаче обнаружения лиц, нужно определить способ, которым изображения лица преобразуется в сигнал (набор последовательных наблюдений). Изображение лица можно естественным образом разделить на несколько горизонтальных областей: лоб, глаза, рот и подбородок. Лицо может быть представлено в виде сигнала, в котором передаются эти области в определенном порядке (обычно сверху вниз, слева направо). Таким образом, изображение лица представляется в виде последовательности наблюдений векторов (каждый из векторов представляет собой горизонтальную полосу пикселей лица), которые во время тренировки и распознавания последовательно передаются случайному процессу, моделируемому СММ.
Активные модели (Active Appearance Models)
С помощью активных моделей (АМ) можно моделировать изображения объектов, подверженных как жесткой (rigid) так и нежесткой (non rigid) деформации. Жесткая деформация – любая деформация, которая может быть представлена в виде композиции переноса, поворота и масштабирования. AM состоит из набора параметров, часть из которых контролируют форму объекта, остальные задают его текстуру. Параметры модели выбираются автоматически, исходя из наиболее характерных деформаций формы и изменений текстуры, присутствующих в тренировочном наборе изображений объекта. Активная модель внешнего вида лица задает изменения формы лица и его характерных черт (формы глаз, бровей, рта, носа, подбородка), а также возможные изменения текстуры лица. Для решения задачи обнаружения лица на изображении делается попытка найти параметры (расположение, форма и текстура) AM, которые задают изображение, наиболее близкое к наблюдаемому. Степень близости внешнего вида модели в оптимальной конфигурации к наблюдаемому изображению дает возможность оценить, видим мы лицо или нет.
Основа методов первой категории – эмпирические знания, является одновременно их сильной и слабой стороной. Большая изменчивость объекта распознавания, зависимость вида лица на изображении от условий съемки и освещения позволяют без колебаний отнести обнаружение лица на изображении к задачам высокой сложности. Применение эмпирических правил позволяет построить некоторую модель изображения лица и свести задачу к выполнению некоторого количества относительно простых проверок. Однако, несмотря на безусловно разумную посылку – попытаться использовать и повторить уже успешно функционирующий инструмент распознавания – человеческое зрение, методы первой категории пока далеки по эффективности от своего прообраза, поскольку исследователи, решившие избрать этот путь, сталкиваются с рядом серьезных трудностей. Во-первых, процессы, происходящие в мозгу во время решения задачи распознавания изображений, изучены далеко не полностью, и тот набор эмпирических знаний о человеческом лице, которые доступны исследователям на "сознательном уровне", далеко не исчерпывает инструментарий, используемый мозгом "подсознательно". Во-вторых, трудно эффективно перевести неформальный человеческий опыт и знания в набор формальных правил, поскольку чересчур жесткие рамки правил приведут к тому, что в ряде случаев лица не будут обнаружены, и напротив, слишком общие правила приведут к большому количеству случаев ложного обнаружения. Можно перечислить следующие проблемы, общие для методов второй категории:
Сравнивать между собой качество распознавания методов разных категорий достаточно тяжело, поскольку в большинстве случаев опираться можно только на данные испытаний, предоставляемые самими авторами, поскольку провести крупномасштабное исследование по реализации большинства известных методов и сравненииы их между собой на едином наборе изображений не представляется возможным по причине высокой трудоемкости этой задачи.
На основе информации, предоставляемой авторами методов, также сложно провести корректное сравнение, поскольку проверка методов часто производится на разных наборах изображений с разной формулировкой условий успешного и неуспешного обнаружения. К тому же проверка для многих методов первой категории производилась на значительно меньших наборах изображений.
Заметное различие между первой и второй категориями методов распознавания заключается еще и в том, что эмпирические методы часто довольно просты в реализации (особенно относительно методов второй категории) и предоставляют возможность гибкой настройки под конкретную задачу путем модификации интуитивно понятных параметров. Методы, опирающиеся на инструментарий распознавания образов, требуют значительных усилий по формированию тренировочных наборов изображений и обучению классификатора. Влияние параметров, контролирующих классификатор, на его поведение часто далеко неочевидно. Однако трудоемкость создания работающих прототипов методов второй категории частично компенсируется высокими заявленными показателями качества распознавания на больших коллекциях изображений.
Выбор метода зависит от конкретной задачи и условий, в которых должен функционировать разрабатываемый алгоритм. Построение универсального метода, обеспечивающего высокий уровень распознавания при отсутствии ограничений на исходные изображения, в настоящее время не представляется возможным, однако для большинства конкретных задач можно создать методы, предоставляющие достаточный уровень распознавания.
В качестве условий, влияющих на выбор метода решения задачи, можно перечислить следующие:
Самым распространенным и эффективным является выделение характерных точек (глаз, бровей, рта) с дальнейшим анализом, например на заранее обученной нейронной сети.
Рис. 1. Характерные точки лица
Рассмотрим семейство алгоритмов, в основе которых лежит алгоритм AdaBoost (от английских слов адаптивность и усиление) описанный в 1996 Freund и Schapire. Этот алгоритм был успешно использован во многих областях, в частности для задачи поиска лиц на изображении. Подход усиления простых классификаторов применяется во многих задачах и до сих пор является объектом прикладных и теоретических исследований.
На основе AdaBoost построена на данный момент, пожалуй, самая эффективная (как по уровню распознавания, так и по скорости работы) система поиска объектов на изображении (Viola-Jones Object Detector). На данный момент наиболее распространёнными вариантами базового алгоритма являются Gentle AdaBoost и Real AdaBoost, превосходящие базовый алгоритм по своим характеристикам, но сохраняющие все основные принципы. К основным достоинствам AdaBoost и его вариантов можно отнести высокую скорость работы, высокую эффективность распознавания, простоту реализации и общность.
Требуется построить классифицирующую функцию F:X –> Y, где X – пространство векторов признаков, Y – пространство меток классов. Пусть имеется обучающая выборка (x1, y1), …, (xN, yN), где xi ∈ X вектор признаков, а yi ∈ Y метка класса, к которому принадлежит xi. Также имеется семейство простых классифицирующий функций H:X –> Y.
Рассмотрим задачу с двумя классами, то есть Y = {-1; +1}.
Строим финальный классификатор в следующей форме:
F(x) = sign[∑Mm=0αmhm(x)], где αm ∈ R, hm ∈ H.
Приведем итеративный процесс (Discrete AdaBoost Freud & Schapire, 1996), в котором на каждом шаге добавляется новое слагаемое
fm = αm hm(x), вычисляемое с учётом уже построенной части классификатора:
Dm+1(i) = Dm(i)•exp(-yi•fm(xi)) / Zi,
где Zi – нормализующий коэффициент, такой, что ∑Ni=1Dm+1(i) = 1.
Вес Dm+1(i) каждого элемента обучающей выборки на текущем шаге задает важность этого примера. Чем больше вес, тем больше алгоритм будет стараться на данном шаге классифицировать этот пример правильно. Как видно из формулы вычисления Dm+1(i), чем уверенней пример распознаётся предыдущими шагами, тем его вес меньше. Таким образом, самые большие веса получают примеры, которые предыдущими шагами были классифицированы неверно. То есть веса изменяются таким образом, чтобы классификатор, включенный в комитет на текущем шаге, концентрировался на примерах, с которыми алгоритм не справился на предыдущих шагах. Таким образом, на каждом шаге ведется работа с частью данных, плохо классифицируемой предыдущими шагами, а в итоге все промежуточные результаты комбинируются.
Очередной простой классификатор выбирается исходя из взвешенной с распределением Dm ошибки. Алгоритм выбирает (тренирует) hm ∈ H, минимизирующий взвешенную ошибку классификации em.
Заметим, что если рассмотреть Dm как распределение вероятности над X, что правомерно, так как
∑Ni=1Dm+1(i) = 1,
то
em = PrX∈Dm[h(x) ≠ y]
Далее вычисляется вклад текущего слагаемого классифицирующей функции – коэффициент αm.
Процесс продолжается до некоторого шага M , номер которого определяется вручную.
В разделе рассматривается основа всех методов усиления простых классификаторов – семейство простых классификаторов H: X –> Y.
Приведём пример. Пусть входные данные это n-мерные векторы X = RN, пусть тогда
H = [hΘ,k(x = (x1,…, xk,…, xN)) = {+1, xk > Θ или –1, xk < Θ}].
То есть это порог по k-й координате.
При таком множестве H выбор наилучшего классификатора hΘ,k выполняется на каждой итерации (шаг 2.a вышеприведенного алгоритма) следующим образом.
Для каждого k = 1…n, вычисляется порог Θk, реализующий минимум взвешенной ошибки em, затем из полученных классификаторов hΘ,k, k = 1…n выбирается соответствующий минимальной ошибке em.
Несмотря на свою простоту, этот классификатор, усиленный алгоритмом AdaBoost, дает весьма впечатляющие результаты. Система поиска объектов на изображении Viola-Jones находит 95% всех искомых объектов с 0.0001% ложных срабатываний.
Вероятность ошибки простого классификатора должна быть хотя бы немного меньше 1/2, то есть он должен работать лучше чем "орел/решка".
Фактически, AdaBoost осуществляет два действия:
Первое действие является своеобразным отображением пространства входных векторов в пространство значений простых классификаторов:
x = (x1, x2,…, xN) –> (h1(x), h2(x),…, hM(x))
Комбинирование простых классификаторов происходит линейно (составляется линейная комбинация), а решение принимается в зависимости от знака полученной комбинации. Это фактически эквивалентно разделению пространства значений простых классификаторов гиперплоскостью и принятию решения в зависимости от того, по какую сторону гиперплоскости лежит отображение вектора признаков.
Таким образом, готовый классификатор производит вначале отображение в некое пространство, обычно намного более высокой размерности, чем исходное, в котором производит линейную классификацию. На этапе тренировки алгоритм последовательно строит и это отображение, и саму гиперплоскость.
Стоит заметить, что работа AdaBoost в значительной мере напоминает работу алгоритма ядерной машины опорных векторов (Kernel Support Vector Machine). Исследования последних лет показывает глубокую связь этих двух алгоритмов.
Одна из интерпретаций работы алгоритмов на основе AdaBoost основана на понятии границы (margin). В случае AdaBoost граница определяется как:
μ(x, y) = ∑Mm=1y•fm(x) / ∑ Mm=1αm
Эту величину можно интерпретировать как меру уверенности классификатора в примере (x, y). Если классификация правильная, то граница больше нуля, иначе граница отрицательна. Чем больше простых классификаторов правильно классифицируют пример, тем больше его граница.
Если учесть, как на каждом шаге вычисляются веса примеров, то легко видеть, что на каждом шаге AdaBoost пытается максимизировать минимальную границу тренировочной выборки. Утверждается, что данное действие положительно сказывается на обобщающих способностях алгоритма.
Отметим следующие достоинства алгоритма:
Алгоритму присущи следующие недостатки:
Основная идея каскадного детектора заключается в том, чтобы обученный классификатор был способен обнаруживать все позитивные экземпляры, но при этом отклонять все негативные экземпляры. Каскадный детектор имеет структуру, приведенную на рис. 2.
Рис. 2. Структура каскадного детектора
Каскад состоит из слоев, которые представляют собой нейронную сеть, обученную с помощью процедуры AdaBoost.
Процесс функционирования происходит следующим образом: на вход каскада подается скользящее окно изображения, которое попадает на первый слой. Если текущий слой классифицирует окно как негативное, то происходит выход и анализ последующими слоями не выполняется, то есть окно классифицируется как негативное.
Если же текущий слой определяет окно как позитивное, то окно анализируется следующим слоем. Такой процесс происходит до тех пор, пока не будут пройдены все слои с позитивной классификацией или не произойдет выход по негативному экземпляру. Учитывая тот факт, что на изображении количество фоновых скользящих окон во много раз превышает количество окон, на которых присутствует распознаваемый объект (для задачи поиска лица это может быть глаз), то выигрыш очевиден. Скорость обработки изображения при этом возрастает в 10…20 раз в зависимости от изображения, но при этом не теряется качество распознавания.
При конструировании каскада, его структура определяется исходя из того, какие целевые требования предъявляются ему. Среди основных требований выделим два:
Приведем теперь алгоритм обучения нейронной сети AdaBoost с каскадным детектором:
В каскаде из K слоев общий коэффициент детекции D каскадного детектора определяется как произведение коэффициентов детекции каждого слоя:
D = ∏Ki=1di,
где di – коэффициент детекции i-го слоя. Коэффициент позитивной ошибки F каскадного детектора определяется по аналогичной формуле:
F = ∏ Ki = 1fi,
где fi – коэффициент позитивной ошибки i-го слоя.
Смысл процесса обучения каскада заключается в том, чтобы одновременно решить две задачи: достигнуть высокого значения коэффициента детекции и при этом получить как можно меньший коэффициент позитивной ошибки. Можно сказать, что детектор должен обнаружить все области глаз, присутствующие на изображении, но в то же время отклонить фоновые окна. В результате обучения определяются следующие параметры каскада:
На практике используется стратегия обучения, которая довольно проста, но при этом эффективна. Задаются требуемые значения коэффициентов детекции и позитивной ошибки для каждого слоя. Каждый слой формируется с помощью процедуры AdaBoost, в процессе которой количество простых классификаторов увеличивается до тех пор, пока не будут достигнуты требуемые значения коэффициентов. Во время процедуры обучения данные разделяются на две выборки: обучающую и контрольную. Формирование простых классификаторов происходит с использованием обучающей выборки, а определение коэффициентов детекции и позитивной ошибки – с использованием контрольной выборки. По ходу формирования слоев каждый новый слой обучается на тех негативных экземплярах, которые были ошибочно классифицированы предыдущими слоями. Благодаря этому каскад обладает высокими обобщающими способностями и низким коэффициентом ошибки.
Для полного анализа изображения необходимо сканировать изображение скользящим окном, которое изменяет не только свое положение, но и свои размеры. Это обусловлено тем, что глаз может находиться в различных местах на изображении, а также имеет различный размер в зависимости от расстояния до объектива камеры во время съемки. При масштабировании геометрических параметров фильтров их вычисление происходит с постоянной скоростью в независимости от размера. При сканировании скользящее окно передвигается дискретно на определенное количество пикселей. Когда изображение сканировано полностью на текущем масштабе, происходит переход на другой масштаб фильтров и заново происходит сканирование уже на новом масштабе. Таким образом, выбор значений изменения шага передвижения окна, а также шага масштаба влияют на качество обнаружения искомого объекта (например глаза) и на время работы детектора. Эти значения определяются экспериментально. Шаг передвижения окна согласовывается с текущим масштабом.
Изначально решается, какие точки будут использоваться для нахождения лица на кадре. Возьмем, к примеру, глаза. Обучаем сеть на примерах “глаз” и “не глаз”. Допустим, что на кадре расположено одно лицо. Найдя глаза, сканируем предполагаемые области местонахождения рта и бровей. Если подтверждается полное наличие геометрически верного лица, распознаем геометрию глаз, бровей и рта.
Среда разработки Visual Studio 9.0; использована библиотека OpenVC.
#include "cv.h"
#include "highgui.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <float.h>
#include <limits.h>
#include <time.h>
#include <ctype.h>
#ifdef _EiC
#define WIN32
#endif
static CvMemStorage* storage = 0;
static CvHaarClassifierCascade* cascade = 0;
void detect_and_draw(IplImage* image);
const char* cascade_name = "haarcascade_frontalface_alt.xml";
int main(int argc, char** argv)
{
CvCapture* capture = 0;
IplImage *frame, *frame_copy = 0;
int optlen = strlen("--cascade=");
const char* input_name;
if(argc > 1 && strncmp(argv[1], "--cascade=", optlen) == 0)
{
cascade_name = argv[1] + optlen;
input_name = argc > 2 ? argv[2] : 0;
}
else
{
cascade_name = "../../data/haarcascades/haarcascade_frontalface_alt2.xml";
input_name = argc > 1 ? argv[1] : 0;
}
cascade = (CvHaarClassifierCascade*)cvLoad(cascade_name, 0, 0, 0);
if(!cascade)
{
fprintf(stderr, "ERROR: Could not load classifier cascade\n");
fprintf(stderr, "Usage: facedetect --cascade=\"<cascade_path>\" [filename|camera_index]\n");
return -1;
}
storage = cvCreateMemStorage(0);
if(!input_name || (isdigit(input_name[0]) && input_name[1] == '\0'))
capture = cvCaptureFromCAM(!input_name ? 0 : input_name[0] - '0');
else
capture = cvCaptureFromAVI(input_name);
cvNamedWindow("result", 1);
if(capture)
{
for(;;)
{
if(!cvGrabFrame(capture)) break;
frame = cvRetrieveFrame(capture);
if(!frame) break;
if(!frame_copy)
frame_copy = cvCreateImage(cvSize(frame->width,frame->height), IPL_DEPTH_8U, frame->nChannels);
if(frame->origin == IPL_ORIGIN_TL)
cvCopy(frame, frame_copy, 0);
else
cvFlip(frame, frame_copy, 0);
detect_and_draw(frame_copy);
if(cvWaitKey(10) >= 0) break;
}
cvReleaseImage(&frame_copy);
cvReleaseCapture(&capture);
}
else
{
const char* filename = input_name ? input_name : (char*)"lena.jpg";
IplImage* image = cvLoadImage(filename, 1);
if(image)
{
detect_and_draw(image);
cvWaitKey(0);
cvReleaseImage(&image);
}
else
{
// Текстовый файл со списком файлов обрабатываемых образов (каждое имя на своей строке)
FILE* f = fopen(filename, "rt");
if(f)
{
char buf[1000+1];
while(fgets(buf, 1000, f))
{
int len = (int)strlen(buf);
while(len > 0 && isspace(buf[len - 1])) len--;
buf[len] = '\0';
image = cvLoadImage(buf, 1);
if(image)
{
detect_and_draw(image);
cvWaitKey(0);
cvReleaseImage(&image);
}
}
fclose(f);
}
}
}
cvDestroyWindow("result");
return 0;
}
void detect_and_draw(IplImage* img)
{
static CvScalar colors[] =
{
{{0, 0, 255}},
{{0, 128, 255}},
{{0, 255, 255}},
{{0, 255, 0}},
{{255, 128, 0}},
{{255, 255, 0}},
{{255, 0, 0}},
{{255, 0, 255}}
};
double scale = 1.3;
IplImage* gray = cvCreateImage(cvSize(img->width,img->height), 8, 1);
IplImage* small_img = cvCreateImage(cvSize(cvRound(img->width/scale), cvRound(img->height/scale)), 8, 1);
int i;
cvCvtColor(img, gray, CV_BGR2GRAY);
cvResize(gray, small_img, CV_INTER_LINEAR);
cvEqualizeHist(small_img, small_img);
cvClearMemStorage(storage);
if(cascade)
{
double t = (double)cvGetTickCount();
CvSeq* faces = cvHaarDetectObjects(small_img, cascade, storage,
1.1, 2, 0 /*CV_HAAR_DO_CANNY_PRUNING*/, cvSize(30, 30));
t = (double)cvGetTickCount() - t;
printf("Detection time = %gms\n", t / ((double)cvGetTickFrequency() * 1000.));
for(i = 0; i < (faces ? faces->total : 0); i++)
{
CvRect* r = (CvRect*)cvGetSeqElem(faces, i);
CvPoint center;
int radius;
center.x = cvRound((r->x + r->width * 0.5) * scale);
center.y = cvRound((r->y + r->height * 0.5) * scale);
radius = cvRound((r->width + r->height) * 0.25 * scale);
cvCircle(img, center, radius, colors[i % 8], 3, 8, 0);
}
}
}
Конфигурация системы: Pentium D 805 2,66 ГГц, ОЗУ 2 Гб.
Первый анализируемый образ приведен на рис. 3.
Рис. 3. Первый распознаваемый образ
Размер рисунка 512 * 512 пикселей. Программа нашла одно лицо за 192 мс.
Второй анализируемый образ показан на рис. 4.
Рис. 4. Второй распознаваемый образ
Обнаружено 7 очертаний лица: 4 верных и 3 ошибочных. Время обнаружения 803 мс.
В отчете приведены основные известные методы захвата движений. Описан алгоритм AdaBoost и дана его реализация, которая хотя и не обладает надлежащей эффективностью (см. пример 2), но может быть использована в качестве основы при построении более точного классификатора.