Метод виолы джонса кратко

Обновлено: 05.07.2024

Галеев Салават Фанилевич
Уфимский государственный авиационный технический университет
магистрант факультета информатики и робототехники


Аннотация
На основе объединения метода Виолы–Джонса и метода CAMShift в каскадную структуру, а также использования вейвлет - преобразования и метода линейного дискриминантного анализа предложена модификация алгоритма Виолы-Джонса для распознавания лиц на видеопоследовательностях в режиме реального времени. Целью данной работы повышение процента верно обнаруженных и распознанных лиц на видеопоследовательностях в режиме реального времени при использовании метода Виолы-Джонса.
Описан алгоритм и разработано программное обеспечение для распознавания лиц. Приведен пример работы программы.

Введение

В наши дни активно развивается направление, которое связано с интеллектуализацией алгоритмов обработки и анализа данных. Распознавание лиц является одной из главных практических задач, которая стала толчком для развития теории распознавания объектов [1].

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

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

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

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

С помощью алгоритма CAMShift (Continuously Adaptive MeanShift) можно отслеживать объекты на основе цветовой информации [3].
Вейвлет-преобразование является одной из лучших техник для извлечения характеристик изображения [4]. В данной работе для извлечения признаков лица применяется вейвлет-преобразование Хаара. Метод линейного дискриминантного анализа эффективно применяется в задачах распознавания лиц для сопоставления признаков неизвестного изображения с известными признаками, которые находятся в базе данных [5].

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

Целью данной работы является повышение процента верно обнаруженных и распознанных лиц на видеопоследовательностях в режиме реального времени при использовании метода Виолы-Джонса.

Для достижения указанной цели были поставлены следующие основные задачи:

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

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

3. Сравнить исходный метод Виолы-Джонса с предложенной модификацией.

1.Метод Виолы-Джонса

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

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

2. Алгоритм отслеживания объекта CAMShift

Алгоритм CAMShift был разработан Гарри Брадски в 1998 г. со способностью отслеживания лица. Данный алгоритм объединяет метод отслеживания объекта Mean Shift для точного позиционирования положения объекта, который основан на карте вероятности цвета кожи и адаптивный шаг изменения размера участка отслеживания [3]. Вероятность цвета кожи каждого пикселя изображения находится с помощью метода Histogram Backprojection. Этот метод основан на цвете, используемом в виде цветового тона (Hue) модели HSV. Алгоритм CAMShift позволяет отслеживать положение лица с четырьмя степенями свободы (три степени свободы перемещения и одна степень свободы вращения в плоскости изображения).

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

3. Вейвлет-преобразование

Вейвлеты находят применение во многих областях знаний при решении таких, задач как: распознавание образов, сжатие и обработка изображений, обработка и синтез сигналов, обучение нейросетей и во многих других. Вейвлеты – это общее название временных функций, которые имеют вид волновых пакетов с той или иной формой, расположенных по оси независимой переменной (t или х) и способных к смещению по ней, а также масштабированию (сжатию/растяжению). Вейвлеты можно создать при помощи особых базовых функций – прототипов, определяющих их вид и свойства. Вейвлет-коэффициенты получают интегральным преобразованием сигнала [4].

Для получения признаков изображения лиц в данной работе применяются вейвлет-преобразования Хаара. Был выбран данный вейвлет, поскольку он является одним из самых простых и легких в применении . К тому же пространство признаков вейвлета Хаара обладает достаточно полным (приемлемым) описанием объекта.

Вейвлет Хаара (Haar) – это кусочно-постоянные функции, заданные на нечетных интервалах разных масштабов, которые принимают два значения . Вейвлет Хаара единичного масштаба и нулевого смещения представлен в виде функции, равной +1 на интервале [0;1/2) и –1 на интервале [1/2;1). Также такой вейвлет называют материнским. Вейвлет Хаара широко используется в задачах обработки дискретных сигналов, таких как массивы отсчетов аудиосигналов и цифровые фотографии. Отличительной особенностью преобразования Хаара является то, что его можно разделить и легко вычислить.

При работе с графикой необходимо обрабатывать двумерные массивы данных.

На примере преобразования Хаара хороша видна структура дискретного вейвлет-преобразования. На каждом шаге преобразования сигнал распадается на две составляющие: приближение с более низким разрешением – аппроксимацию и детализирующую информацию.

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

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



Рисунок 1. Пример работы вейвлета Хаара

4. Метод линейного дискриминантного анализа (LDA)

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

Модификация алгоритма Виолы-Джонса для распознавания лиц.

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

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

2) На 2 этапе в процессе распознавания неизвестного лица повторяется 1 этап, только без сохранения в базе данных. Затем на основе использования метода линейного дискриминантного анализа происходит уменьшение числа признаков и их сопоставление с признаками, хранящимися в базе данных.

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

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



Рисунок 2. Структура каскадного детектора

Общие принципы работы каскадного классификатора на изображении приведены на рис.3.



Рисунок 3. Общие принципы работы каскадного классификатора

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



Рисунок 4. Обнаружение лица и сохранение в базе данных

Таким образом, процесс сохранения признаков лица в базу данных происходит так (рис. 4):

1. Предоставляется очередное изображение.

2. Применение к изображению метода Виолы-Джонса для поиска области лица.

3. Если область лица не обнаружена, то метод Виолы-Джонса применяется для следующего очередного изображения.

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

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

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

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

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

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



Рисунок 5. Блок-схема процесса распознавания лиц

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

Эксперименты



Рисунок 6. Пример сохранения обнаруженного лица в базу данных

Скорость работы системы достигает 18 кадров/с.



Рисунок 7. Пример распознавания лиц в видеопотоке в режиме реального времени

Ниже приведена таблица сравнения исходного метода Виолы-Джонса и предложенной модификации.

Таблица 1 – Сравнение метода Виолы-Джонса и предложенной модификации

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

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

Метод имеет следующие преимущества:

  • возможно обнаружение более одного лица на изображении;
  • использование простых классификаторов показывает хорошую скорость и позволяет использовать этот метод в видеопотоке.

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

Схема распознавания

Обобщенная схема распознавания в алгоритме Виолы-Джонса показана на рисунке ниже.

Обобщенная схема алгоритма Виолы-Джонса

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

Признаки класса

В качестве признаков для алгоритма распознавания авторами были предложены признаки Хаара, на основе вейвлетов Хаара. Они были предложен венгерским математиком Альфредом Хааром в 1909 году.

Пример вейвлета Хаара

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

Пример масок в алгоритме Виолы-Джонса

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

Набор признаков Хаара из метода Виолы-Джонса

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

F=X-Y

где X – сумма значений яркостей точек закрываемых светлой частью признака, а Y – сумма значений яркостей точек закрываемых темной частью признака.

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

Схема обучения

Обобщенная схема алгоритма обучения выглядит следующим образом. Имеется тестовая выборка изображений. Размер тестовой выборки около 10 000 изображений. На рисунке показан пример обучающих изображений лиц. Алгоритм обучения работает с изображениями в оттенках серого.

Пример обучающих изображений лиц

При размере тестового изображения 24 на 24 пикселя количество конфигураций одного признака около 40 000 (зависит от минимального размера маски). Современная реализация алгоритма использует порядка 20 масок. Для каждой маски, каждой конфигурации тренируется такой слабый классификатор, который дает наименьшую ошибку на всей тренировочной базе. Он добавляется в базу данных. Таким образом алгоритм обучается. И на выходе алгоритма получается база данных из T слабых классификаторов. Обобщённая схема алгоритма обучения показана на рисунке.

Обобщенная схема алгоритма обучения

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

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

количество всех тестовых изображений

где X – множество всех тестовых изображений, где для каждого заранее известно присутствует ли искомый объект или нет и отражено во множестве Y.

присутствует ли искомый объект или нет и отражено во множестве Y

присутствие объекта на изображении

Под признаком j будем понимать структуру вида

Под признаком j будем понимать структуру вида

Тогда откликом признака будет fj (x), который вычисляется как разность интенсивностей пикселей в светлой и темной областях. Слабый классификатор имеет вид:

Слабый классификатор имеет вид

Задача слабого классификатора – угадывать присутствие объекта в больше чем 50% случаев. Используя процедуру обучения AdaBoost создается очень сильный классификатор состоящий из T слабых классификаторов и имеющий вид:

очень сильный классификатор состоящий из T слабых классификаторов

Целевая функция обучения имеет следующий вид:

Целевая функция обучения имеет следующий вид

Интегральное представление изображений

Интегральное представление можно представить в виде матрицы, размеры которой совпадают с размерами исходного изображения I, где каждый элемент рассчитывается так:

Интегральное представление изображений

где I(r,c) — яркость пиксела исходного изображения.

Каждый элемент матрицы II[x,y] представляет собой сумму пикселов в прямоугольнике от (0,0) до (x,y). Расчет такой матрицы занимает линейное время. Для того, чтобы вычислить сумму прямоугольной области в интегральном представлении изображения требуется всего 4 операции обращения к массиву и 3 арифметические операции. Это позволяет быстро рассчитывать признаки Хаара для изображения в обучении и распознавании.

Например, рассмотрим прямоугольник ABCD.

Интегральное изображение на примере прямоугольника ABCD

Сумму внутри прямоугольника ABCD можно выразить через суммы и разности смежных прямоугольников по формуле:

Сумму внутри прямоугольника ABCD можно выразить

Обучение

Перед началом обучения инициализируются веса w(q,i), где q – номер итерации, i-номер изображения.

инициализируются веса

После процедуры обучения получится T слабых классификаторов и T значений.

T слабых классификаторов и T значений

алгоритм обучения в методе виолы-джонса

На каждой итерации цикла происходит обновление весов так, что их сумма будет равна 1. Далее для всех возможных признаков происходит подбор таких значений p,θ,j что значение ошибки e_j будет минимально на этой итерации. Полученный признак J(t) (на шаге t) сохраняется в базу слабых классификаторов, обновляются веса и вычисляется коэффициент a_t.

В предложенном в 2001 году оригинальном алгоритме не была описана процедура получения оптимального признака на каждой итерации. Предполагается использование алгоритма AdaBoost и полный перебор возможных параметров границы и паритета.

Распознавание

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

На вход алгоритму поступает изображение I(r,c) размером W х H, где I(r,c) – яркостная составляющая изображения. Результатом работы алгоритма служит множество прямоугольников R(x,y,w,h), определяющих положение лиц в исходном изображении I.

Алгоритм сканирует изображение I на нескольких масштабах, начиная с базовой шкалы: размер окна 24х24 пикселя и 11 масштабов, при этом каждый следующий уровень в 1.25 раза больше предыдущего, по рекомендации авторов. Алгоритм распознавания выглядит следующим образом:

алгоритм распознавания в методе Виолы-Джонса

Недостатки алгоритма Виолы-Джонса

Базовый алгоритм Виолы-Джонса (далее базовый алгоритм) имеет ряд недостатков:


Вы никогда не задумывались, как эта коробка на вашей цифровой камере точно знает, где и какое лицо?

Еще в 2011 году, до того, как в моду вошли сверточные нейронные сети или любые другие методы глубокого обучения, существовал алгоритм Виолы-Джонса. Этот алгоритм был настолько инновационным и эффективным, что статья цитировалась более 19 000 раз.

Цель исследователя состояла в том, чтобы решить две самые большие проблемы с распознаванием лиц. Алгоритм достиг следующего:

  • Надежность - высокая частота обнаружения (истинно-положительная) и очень низкая ложно-положительная.
  • Скорость - для реального времени необходимо обрабатывать не менее двух кадров в секунду.

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

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

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



Исследователи нашли процесс, в котором вы можете довольно успешно определить, является ли подокно изображения лицом.

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

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


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

Интегральное изображение

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


Когда приходит новое изображение для классификации, сумма значений пикселей берется по строкам и столбцам, так что пиксель (i, j) является суммой всех пикселей перед ним.

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

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

Классификаторы Обучение / Выбор

Количество необработанных особенностей с этими прямоугольными коробками астрономическое. Согласно исследованию, всего в окне изображения 24х24 имеется 162,336 объектов.

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


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

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

Внимательный каскад

Чтобы классифицировать, если подокно изображения на самом деле является лицом, они создали Attentional Cascade. По сути, это дерево решений, где каждый узел является одним из построенных классификаторов.


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


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

Результат их модели был довольно выдающимся. В документе говорится, что на процессоре Pentium III с частотой 700 МГц детектор лица может обрабатывать изображение размером 384 на 288 пикселей примерно за 0,067 секунды.

Вывод

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

На практике одним из способов оптимизации распознавания и отслеживания в реальном времени является использование Viola Jones для обнаружения лица, а затем использование алгоритма, такого как Kanade-Lucas-Tomasi (KLT), для отслеживания обнаруженного лица в видео.

Если вы заинтересованы в том, чтобы попробовать это сами, у OpenCv есть реализация, на которую я буду ссылаться ниже, вместе с оригинальной статьей Виолы и Джонса и очень полезным объяснением доктора Майка Паунда о Computerphile.

Пол Viola ( в ) , Майкл Джонс ( в )

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

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

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

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

Этот метод выигрывает от реализации по лицензии BSD в OpenCV , библиотеке, широко используемой в компьютерном зрении .

Резюме

Исторический

Пол Виола и Майкл Джонс, работавшие тогда в Кембриджской исследовательской лаборатории американской компании Compaq , впервые публикуют метод, носящий их имя, в 13 июля 2001 г. в научном журнале International Journal of Computer Vision (IJCV). Затем два автора опубликовали две другие статьи об этом методе: менее подробную версию, представленную на конференции по компьютерному зрению и распознаванию образов (CVPR) в декабрь 2001 и пересмотренная версия в 2004 году, все еще находится в IJCV.

В особенности , добытая этот метод, вдохновленные работами Папагеорьи, Орны и Поджио, начиная с 1998 года, который в использовании функции построена из вейвлет Хаара . Этот метод также вдохновлен предыдущими работами Пола Виолы и Кин Тиеу в другой области, в области поиска изображений по содержанию , за счет использования идеи выбора функций с помощью AdaBoost . Среди множества методов обнаружения лиц, опубликованных в то время, Виола и Джонс рассматривают, в частности, метод Роули- Канаде : благодаря его отличным результатам и скорости они считают его эталоном для сравнений. Для обеспечения эквивалентной производительности Виола и Джонс отмечают, что обнаружение их методом в 15 раз быстрее, чем детектор Роули-Канаде.

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

Элементы метода

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

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

Характеристики

Описание

Вместо того, чтобы работать непосредственно со значениями пикселей, чтобы быть более эффективными и быстрыми, Виола и Джонс предлагают использовать характеристики , то есть синтетическое и информативное представление, рассчитанное на основе значений пикселей. Виола и Джонс определяют очень простые характеристики, характеристики псевдо-Хаара , которые вычисляются как разность сумм пикселей двух или более смежных прямоугольных областей. На рисунке напротив приведены примеры характеристик, предложенных Виолой и Джонсом для 2, 3 или 4 прямоугольников, в которых сумма темных пикселей вычитается из суммы белых пикселей. Их название происходит от их сходства с вейвлетами Хаара , ранее предложенными в качестве характеристик Папагеоргиу и которыми были вдохновлены Виола и Джонс.

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

Расчет

Характеристики вычисляются во всех положениях и во всех масштабах в небольшом окне обнаружения, обычно 24 × 24 пикселей или 20 × 15 пикселей. Таким образом, создается очень большое количество характеристик для каждого окна, Виола и Джонс приводят пример окна размером 24 × 24, которое генерирует приблизительно 160 000 характеристик.

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

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

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

Подбор характеристик по бусту

Более формально мы рассматриваем набор изображений и связанных с ними меток , которые могут быть такими, как если бы изображение было отрицательным примером, а если бы - примером обнаруживаемого объекта. Алгоритм повышения состоит из ряда итераций, и для каждой итерации и каждой характеристики мы создаем слабый классификатор . В идеале, цель состоит в том, чтобы получить классификатор , который точно предсказывает метки для каждого образца, т.е. . На практике классификатор не идеален, и ошибка, генерируемая этим классификатором, определяется следующим образом: нет ( Икс 1 , . , Икс нет ) , \ ldots, x_ )> ( y 1 , . , y нет ) , \ ldots, y_ )> y я знак равно 0 = 0> Икс я > y я знак равно 1 = 1> Икс я > Т т j час j > час y я знак равно час ( Икс я ) = ч (х_ )> ∀ я ∈ < 1 . нет >>

это веса, связанные с каждым примером и обновляемые на каждой итерации как функция ошибки, полученной на предыдущей итерации. Затем выбирает итерацию классификатора с наименьшей ошибкой . ш я > т час т > ϵ т знак равно мин j ( ϵ j ) = \ min _ (\ epsilon _ )>

Последний сильный классификатор создается путем определения порога взвешенной суммы выбранных слабых классификаторов: час ( Икс )

Каскад классификаторов

Иллюстрация архитектуры каскада: окна последовательно обрабатываются классификаторами и сразу отклоняются, если ответ отрицательный ( F ).

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

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

Выбор этажности устанавливается пользователем; В своем оригинальном методе Виола и Джонс используют полы. Пользователь также должен указать минимальную частоту обнаружения и максимальную частоту ложных тревог, которая должна быть достигнута для этажа . В этом случае частота каскадного обнаружения определяется как: K K знак равно 38 d я > ж я > я

и частоту ложных тревог на:

На практике ставки и являются одинаковыми для всех этажей. Косвенно эти показатели также определяют количество характеристик, используемых сильными классификаторами на каждом этаже: итерации Adaboost продолжаются до тех пор, пока не будет достигнута целевая частота ложных срабатываний. Слабые функции / классификаторы добавляются до тех пор, пока не будут достигнуты целевые показатели, прежде чем перейти на следующий уровень. d я > ж я >

Чтобы добиться правильного обнаружения и частоты ложных тревог в конце каскада, необходимо, чтобы сильные классификаторы каждой ступени имели хорошую частоту обнаружения; с другой стороны, у них может быть высокий уровень ложных тревог. Если мы возьмем пример 32-ступенчатого каскада, чтобы получить окончательную производительность и , каждый сильный классификатор должен достичь , но может себе позволить (т.е. и ). Таким образом, каждый добавленный этап снижает количество ложных срабатываний, но также снижает уровень обнаружения. D знак равно 0,9 F знак равно 10 - 6 > d я знак равно 0 , 997 = 0,997> ж я знак равно 0 , 65 = 0,65> 0 , 65 32 знак равно 10 - 6 = 10 ^ > 0 , 997 32 знак равно 0 , 9 = 0.9>

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

Обучение

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

  • Расчет характеристик псевдо-Хаара на положительном и отрицательном примерах;
  • Обучение водопада: на каждом уровне водопада AdaBoost тренирует сильный классификатор. Он строится путем последовательного добавления слабых классификаторов, обученных одной характеристике, до тех пор, пока производительность не будет достигнута в соответствии с желаемой частотой обнаружения и ложных тревог для данной стадии.

Обнаружение

Обнаружение применяется к пробному изображению, на котором желательно обнаружить присутствие и местоположение объекта. Вот шаги:

  • просмотреть все изображение во всех положениях и масштабах, с размером окна 24 × 24 пикселя, и применить водопад к каждому подокну, начиная с первого этапа:
    • расчет характеристик псевдо-Хаара, используемых классификатором текущей стадии,
    • затем расчет ответа классификатора,
    • затем перейдите на верхний этаж, если ответ положительный, в другое подокно в противном случае,
    • и, наконец, пример объявляется положительным, если все этапы реагируют положительно;

    Представление

    Виола и Джонс протестировали свой алгоритм с использованием лиц MIT + CMU , которые состояли из 130 изображений, содержащих 507 фронтальных лиц. Они представляют свой результат в виде кривой рабочих характеристик приемника (ROC), которая дает правильную скорость обнаружения в соответствии с общим количеством ложных срабатываний на всех изображениях корпуса. Например, для 50 ложных срабатываний они получают уровень обнаружения 88,8%.

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

    Скорость обнаружения, в свою очередь, напрямую зависит от количества оцениваемых характеристик и, следовательно, от содержания изображения. На ПК Pentium III, работающем на частоте 700 МГц , авторы сообщают о среднем времени обработки 0,067 секунды для изображения размером 384 × 288 пикселей, что соответствует средней скорости 15 изображений в секунду, что довольно близко к требованиям обработки видео по времени. . реальные (т.е. 25 изображений в секунду). Наконец, на основе граней MIT + CMU их детектор в 15 раз быстрее, чем у Rowley-Kanade, и в 600 раз быстрее, чем у Schneiderman-Kanade, для сопоставимых показателей обнаружения и ложных тревог.

    Ограничения и расширения

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

    Другие типы функций также использовались для замены функций Хаара: гистограммы ориентированных градиентов , локальные битовые шаблоны или ковариация области. Исследователи также предложили использовать варианты алгоритма повышения , в том числе RealBoost , который выдает реальный индекс уверенности в дополнение к классификации. Таким образом, в нескольких работах показано превосходство RealBoost над AdaBoost в рамках алгоритма Виолы и Джонса.

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

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

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

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

    Приложения

    Иллюстрация распознавания лиц методом Виолы и Джонса библиотекой OpenCV. Распознаются 3 лица из 4, 4-е пропущено, находится в профиль.

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

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

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

    Реализации

    Существует множество реализаций детектора Виолы и Джонса, наиболее широко используемой является реализация на языке C ++ в библиотеке компьютерного зрения OpenCV , выпущенной под лицензией BSD . Реализации были разработаны для конкретных сред или платформ, особенно для выполнения в веб-браузерах с использованием языка сценариев ActionScript для мультимедийного программного обеспечения Flash . Аппаратные реализации также были разработаны на ASIC , FPGA и GPU . Использование их параллельной архитектуры позволяет значительно сэкономить время обнаружения по сравнению с традиционной реализацией OpenCV.

    Примечания и ссылки

    Библиография

    (ru) Ричард Селиски, Компьютерное зрение: алгоритмы и приложения , Springer , 2010 г.

    Смотрите также

    Статьи по Теме

    Внешние ссылки

    Читайте также: