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

Метод Виолы—Джонса (англ.Viola–Jones object detection) — алгоритм, позволяющий обнаруживать объекты на изображениях в реальном времени. Его предложили Паул Виола и Майкл Джонс в 2001 году.[1][2] Хотя алгоритм может распознавать различные классы изображений, основной задачей при его создании было обнаружение лиц. У метода имеется множество реализаций, в том числе в составе библиотеки компьютерного зренияOpenCV (функция cvHaarDetectObjects()).

Алгоритм находит лица с высокой точностью и низким количеством ложных срабатываний.

Описание алгоритма[править | править код]

Признаки и их поиск[править | править код]

Признаки, используемые алгоритмом, используют суммирование пикселей из прямоугольных регионов. Сами признаки несколько напоминают признаки Хаара, которые ранее также использовались для поиска объектов на изображениях.[3] Однако признаки, использованные Виолой и Джонсом содержат более одной прямоугольной области и несколько сложнее.

На иллюстрации справа показано 4 различных типа признаков.

Метод Виолы — Джонса

Величина каждого признака вычисляется как сумма пикселей в белых прямоугольниках, из которой вычитается сумма пикселей в черных областях. Прямоугольные признаки более примитивны чем steerable filter, и, несмотря на то, что они чувствительны к вертикальным и горизонтальным особенностям изображений, результат их поиска более груб. Однако, при хранении изображения в интегральном формате (integral image, в каждом пикселе изображения записана сумма всех пикселей левее и выше данного), проверка прямоугольного признака на конкретной позиции проводится за константное время, что является их преимуществом по сравнению с более точными вариантами. Каждая прямоугольная область в используемых признаках всегда смежна с другим прямоугольником, поэтому расчет признака с 2 прямоугольниками состоит из 6 обращений в интегральный массив, для признака с 3 прямоугольниками — из 8, с 4 прямоугольниками — из 9.

Обучение[править | править код]

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

Каскад[править | править код]

См. также[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Типы «признаков», использованные в алгоритме

.

Автор: Билл Грин

Перевод с английского: Чудовская А.К.

Название статьи: Алгоритм выделения контуров CANNY

Источник: Дрексельская лаборатория автоматизированных систем, 2002.
http://www.pages.drexel.edu/~weg22/can_tut.html

Этот урок научит вас:

(1) Выделять края с помощью алгоритма Canny.

ВВЕДЕНИЕ

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

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

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

Детекторы особенностей в методе Виолы Джонса, построенные на основе конечных автоматов

Далее он находит градиент изображения чтобы подсветить области с высокими пространственными производными. Далее алгоритм проходит по этим областям и подавляет все пиксели, которые не в максимуме (немаксимальное подавление). Градиентный массив далее уменьшается гистерезисом. Гистерезис используется, чтобы отследить оставшиеся пиксели, которые не были подавлены. Гистерезис использует два порога и если величина ниже первого порога, то она устанавливается в ноль (делается не краевой). Если величина выше высокого порога, она делается краевой. И если величина между этими 2 порогами, то она установливается в ноль, в том случае если нет пути от этого пиксела к пикселю с градиентом выше T2. Ниже приведены шаги алгоритма.

Шаг 1

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

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

Шаг 2

Нахождение края силы путем взятия градиента изображения. Оператор Собеля выполняет 2-D пространственное измерение градиента в изображении. Тогда приближенные градиенты абсолютных величин (края сил) в каждой точке может быть найдено.  Оператор Собеля использует пару 3×3 масок свертки: оценки градиента в направлении х (столбцы) и оценки градиента в Y-направлении (строк).  Они показаны ниже:

Величина, или край силы, градиента затем аппроксимируется по формуле:

|G| = |Gx| + |Gy|

Шаг 3

Нахождение направления края тривиально, поскольку градиент в направлениях X и Y известны. Однако если сумма Х будет равняться нулю, будет сгенерирована ошибка. Так что при реализации алгоритма, должно быть ограничение набора, когда это происходит. Всякий раз, когда градиент в направлении х равен нулю, направление края должно быть равно 90 градусам или 0 градусов, в зависимости от того, чему равно значение градиента в направлении оси Y. Если GY имеет нулевое значение, направление края будет равно 0 градусов. В противном случае направление края будет равно 90 градусов. Формула для нахождения направления края:

theta = invtan (Gy / Gx)

Шаг 4

Связывание направления края с направлением, которое может быть прослежено в изображении. Таким образом, если пиксели 5×5 изображения расположены как указано ниже:

x x x x x
x x x x x
x x a x x
x x x x x
x x x x x

видно, что для пикселя "а" существуют только четыре возможных направления описания окружающих пикселей — 0 градусов (в горизонтальном направлении), 45 градусов (вдоль положительной диагонали), 90 градусов (в вертикальном направлении), или 135 градусов (по отрицательной диагонали).  Теперь ориентация края должна быть выбрана в одном из этих четырех направлений, в зависимости от того, какое направление находится ближе (например, если угол ориентации оказывается +3 градуса, сделать его 0 градусов). Для этого представляют полукруг, разделенный на 5 регионов


Поэтому любое направление края, входящего в желтый диапазон (от 0 до 22,5 & 157,5 до 180 градусов) устанавливается в 0 градусов. Любое направление краю, попадающее в зеленый диапазон (22,5 до 67,5 градуса) устанавливается на 45 градусов. Любое направление краю в синем диапазоне(67,5 до 112,5 градусов) устанавливается в 90 градусов. И, наконец, любое направление края в красном диапазоне (112,5 до 157,5 градусов) устанавливается в 135 градусов.

Шаг 5

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

Шаг 6

Гистерезис используется в качестве средства устранения полос. Полоса – это разбиение контура края, вызванное оператором выходного колебания выше и ниже порогового уровня. Если единственный порог, T1 применяется к изображению и край имеет среднюю силу, равную T1, то из-за шума, будут случаи, когда край опускается ниже порогового уровня. В равной степени он будет также распространяться выше порога принятия края, похожего на  пунктирную линию. Чтобы избежать этого, гистерезис использует 2 порога, высокий и низкий. Любой пиксель в изображении, который имеет значение большее, чем T1 предположительно является краевым пикселем, и немедленно обозначается как таковой. Затем, любые пиксели, которые соединяются с этим краевым пикселем, и которые имеют значение, большее, чем T2, также выбираются как краевые пиксели. Для начала движения вдоль края необходим градиент T2, а для окончания – градиент ниже T1.

Добавить комментарий

Закрыть меню