Метод распознавания объектов на базе алгоритма Виолы-Джонса. Часть 1

Введение

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

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

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

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

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

Обработка изображения выполняется с помощью метода скользящего окна. Так как искомый объект на изображении может иметь различный масштаб необходимо произвести поиск этого объекта с различным масштабом признаков. Эта процедура позволяет производить однотипные вычисления на разных областях исходного изображения и на разных масштабах признаков. Скользящее окно U описывается начальным размером Ux и Uy и величиной сдвига по осям ?U. В предложенном алгоритме минимальный размер скользящего окна был предложен 24x24 пикселя.

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

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

Постановка задачи

Описание базового алгоритма представлено в работе [1]. Алгоритм распознавания анализирует каждый регион отдельно и принимает жесткое решение о нахождении искомого объекта внутри рассматриваемого региона. Отклик признака fj (x) вычисляется как разность интенсивностей пикселей в светлой и темной областях. Базовый алгоритм оперирует понятием слабого классификатора hj (x), который вычисляется следующим образом:

Признак Виолы-Джонса

где pj (паритет), θj (граница), параметры подбираемые в процессе процедуры обучения. 

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

Сильный классификатор Виолы-Джонса

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

Критерии оценки эффективности распознавания

В данной работе рассматриваются известные критерии оценки [2], а также предлагается новый критерий на базе идеи Ground Truth. К известным критериям можно отнести:

Ошибка классификации происходит, когда классификатор относит входной объект к классу C_i, в то время как верный класс C_j, причем 

К типовым оценкам эффективности распознавания следует отнести: Доля истинно положительных примеров (True Positives Rate):

TRP (True Positive Rate)

Доля ложно положительных примеров (False Positives Rate):

False Positive Rate

Дополнительный критерий оценки эффективности работы алгоритма может быть сформулирован на основе Ground Truth. За основу взята работа [4] и предложен алгоритм вычисления численного критерия оценки er, как отношения непересекающихся частей к общей площади регионов (рис 2).

Критерий оценки эффективности

Формула вычисления критерия

Введенный критерий показывает ошибку несовпадения двух рассматриваемых регионов, при этом он учитывает взаимное положение объектов между собой. Численное значение критерия ограничено интервалом [0,1], при достижении значения 1 можно сделать вывод, что объекты не пересекаются и получен результат FP. При значении er равным 0 получаем полное совпадение с указанным вручную регионом, что означает TP.

Модификация сильного классификатора в форме мягкого решения

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

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

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

Напомним, в оригинальном алгоритме для того, чтобы классификатор вынес решение о том, что в рассматриваемом окне присутствует искомый шаблон, необходимо, чтобы выполнилось условие сильного клас-сификатора (3). Модифицируем формулу (3) к следующему виду:

Промежуточная формула мягкого выхода

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

Формула мягкого выхода

Одним из возможных применений мягкого выходя является принятие однозначного решения о найденном объекте, исходя из значения Hs(x). Однако применение такого критерия впрямую имеет ряд недостатков. На рис. 3 показан пример работы оригинального алгоритма Виолы Джонса с дополнительными значениями. Белым отмечено истинное лицо (Ground Truth). Красным выделены регионы, найденные алгоритмом Виола Джонса. В каждом найденном регионе числом записано значение мягкого выхода. Также есть отметка “GT”, как регион с наименьшей ошибкой Ground Truth, по отношению к вручную проставленному региону (белым цветом). Видно, что найденный алгоритмом объект в реальности не имеет наибольшее значение мягкого выхода.

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

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

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

На рис. 5 видно, что единственный найденный алгоритмом регион явля-ется ложно положительным срабатыванием.

Пример изображение с единственный найденным объектом с максимальным значением мягкого выхода

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

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

Метод распознавание объектов на базе алгоритма Виолы-Джонса. Часть 2

Статья в PDF paper-2014.pdf

Комментарии

comments powered by Disqus