Биометрия. Метод Viola Jones

Содержание

Слайд 2

Метод Viola Jones используются изображения в интегральном представлении, что позволяет вычислять

Метод Viola Jones

используются изображения в интегральном представлении, что позволяет вычислять быстро

необходимые объекты;
используются признаки Хаара, с помощью которых происходит поиск нужного объекта (в данном контексте, лица и его черт);
используется бустинг (от англ. boost – улучшение, усиление) для выбора наиболее подходящих признаков для искомого объекта на данной части изображения;
все признаки поступают на вход классификатора, который даёт результат «верно» либо «ложь»;
используются каскады признаков для быстрого отбрасывания окон, где не найдено лицо.
Слайд 3

https://habrahabr.ru/post/135244/ https://habrahabr.ru/post/134857/ https://habrahabr.ru/post/133909/ https://habrahabr.ru/post/133826/

https://habrahabr.ru/post/135244/
https://habrahabr.ru/post/134857/
https://habrahabr.ru/post/133909/
https://habrahabr.ru/post/133826/

Слайд 4

Метод Viola Jones. Основные принципы используются изображения в интегральном представлении, что

Метод Viola Jones. Основные принципы

используются изображения в интегральном представлении, что позволяет

вычислять быстро необходимые объекты;
используются признаки Хаара, с помощью которых происходит поиск нужного объекта (в данном контексте, лица и его черт);
используется бустинг (от англ. boost – улучшение, усиление) для выбора наиболее подходящих признаков для искомого объекта на данной части изображения;
все признаки поступают на вход классификатора, который даёт результат «верно» либо «ложь»;
используются каскады признаков для быстрого отбрасывания окон, где не найдено лицо.
Слайд 5

Краткий алгоритм имеется изображение, на котором есть искомые объекты. Оно представлено

Краткий алгоритм

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

w*h, в которой каждый пиксель имеет значение: — от 0 до 255, если это черно-белое изображение; — от 0 до 2553, если это цветное изображение (компоненты R, G, B).
в результате своей работы, алгоритм должен определить лица и их черты и пометить их – поиск осуществляется в активной области изображения прямоугольными признаками, с помощью которых и описывается найденное лицо и его черты: rectanglei = {x,y,w,h,a}, 
где x, y – координаты центра i-го прямоугольника, w – ширина, h – высота, a – угол наклона прямоугольника к вертикальной оси изображения.
Слайд 6

Интегральное представление изображений вейвлет-преобразования SURF SIFT рассчитывать суммарную яркость произвольного прямоугольника

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

вейвлет-преобразования
SURF
SIFT
рассчитывать суммарную яркость произвольного прямоугольника на изображении, причем какой

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

где I(i,j) — яркость пикселя исходного изображения. Каждый элемент матрицы L[x,y]

где I(i,j) — яркость пикселя исходного изображения. Каждый элемент матрицы L[x,y] представляет

собой сумму пикселей в прямоугольнике от (0,0) до (x,y), т.е. значение каждого пикселя (x,y) равно сумме значений всех пикселов левее и выше данного пикселя (x,y). Расчет матрицы занимает линейное время, пропорциональное числу пикселей в изображении, поэтому интегральное изображение просчитывается за один проход.

L(x,y) = I(x,y) – L(x-1,y-1) + L(x,y-1) + L(x-1,y)

Слайд 8

S(ABCD) = L(A) + L(С) — L(B) — L(D)

S(ABCD) = L(A) + L(С) — L(B) — L(D)

Слайд 9

Пример расчета

Пример расчета

Слайд 10

Признаки Хаара Признак— отображениеf: X => Df, где Df— множество допустимых

Признаки Хаара

Признак— отображениеf: X => Df, где Df— множество допустимых значений признака.
Если

заданы признакиf1,…,fn, то вектор признаковx = (f1(x),…,fn(x)), называется признаковым описанием объекта x∈X.
Признаковые описания допустимо отождествлять с самими объектами. При этом множествоX = Df1* …* Dfnназывают признаковым пространством.
Слайд 11

типы в зависимости Признаки делятся на следующие типы в зависимости от

типы в зависимости

Признаки делятся на следующие типы в зависимости от множества Df:
бинарный

признак, Df = {0,1};
номинальный признак: Df— конечное множество;
порядковый признак: Df— конечное упорядоченное множество;
количественный признак: Df— множество действительных чисел.
Слайд 12

В стандартном методе Виолы – Джонса Вычисляемым значением такого признака будет

В стандартном методе Виолы – Джонса

Вычисляемым значением такого признака будет F =

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

В расширенном методе Виолы – Джонса

В расширенном методе Виолы – Джонса

Слайд 14

Сканирование окна есть исследуемое изображение, выбрано окно сканирования, выбраны используемые признаки;

Сканирование окна

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

сканирования начинает последовательно двигаться по изображению с шагом в 1 ячейку окна (например, 24*24 ячейки);
при сканировании изображения в каждом окне вычисляется приблизительно 200 000 вариантов расположения признаков, за счет изменения масштаба признаков и их положения в окне сканирования;
сканирование производится последовательно для различных масштабов;
масштабируется не само изображение, а сканирующее окно (изменяется размер ячейки);
все найденные признаки попадают к классификатору, который «выносит вердикт».
Слайд 15

Слайд 16

Используемая в алгоритме модель машинного обучения «Машинное обучение — это наука,

Используемая в алгоритме модель машинного обучения

«Машинное обучение — это наука, изучающая

компьютерные алгоритмы, автоматически улучшающиеся во время работы» (Michel, 1996)

Обучение машины — это процесс получения модулем новых знаний.

Слайд 17

Обучение классификатора в методе Виолы-Джонса Классифицировать объект — значит, указать номер

Обучение классификатора в методе Виолы-Джонса

Классифицировать объект — значит, указать номер (или наименование

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

Постановка классификации Есть X – множество, в котором хранится описание объектов,

Постановка классификации

Есть X – множество, в котором хранится описание объектов,
Y –

конечное множество номеров, принадлежащих классам.
зависимость – отображение Y*: X => Y.
Обучающая выборка  Xm = {(x1,y1), …, (xm,ym)}.
Конструируется функция f от вектора признаков X, которая выдает ответ для любого возможного наблюдения X и способна классифицировать объект x∈X. 
Слайд 19

Бустинг и разработка AdaBoost Бустинг — комплекс методов, способствующих повышению точности

Бустинг и разработка AdaBoost

Бустинг — комплекс методов, способствующих повышению точности аналитических

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

Идея бустинга Роберт Шапир (Schapire) в конце 90-х годов построение цепочки

Идея бустинга

Роберт Шапир (Schapire) в конце 90-х годов
построение цепочки (ансамбля) классификаторов, который называется каскадом,

каждый из которых (кроме первого) обучается на ошибках предыдущего.
Boost1 использовал каскад из 3-х моделей,
первая из которых обучалась на всем наборе данных,
вторая – на выборке примеров, в половине из которых первая дала правильные ответы,
третья — на примерах, где «ответы» первых двух разошлись.
имеет место последовательная обработка примеров каскадом классификаторов,
задача для каждого последующего становится труднее.
Результат определяется путем голосования: пример относится к тому классу, который выдан большинством моделей каскада.
Слайд 21

Математическое объяснение Наряду с множествами X и Y вводится вспомогательное множество

Математическое объяснение

Наряду с множествами
X и Y
вводится вспомогательное множество R,

называемое пространством оценок.
Рассматриваются алгоритмы, имеющие вид суперпозиции
a(x) = C(b(x)),
где функция b: X → R называется алгоритмическим оператором,
функция C: R → Y –решающим правилом.
Слайд 22

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

Структура алгоритмов классификации

вычисляются оценки принадлежности объекта классам,
решающее правило переводит эти

оценки в номер класса.
Значение оценки, как правило, характеризует степень уверенности классификации. 
Слайд 23

Алгоритмическая композиция алгоритм a: X → Y вида a(x) = C(F(b1(x),

Алгоритмическая композиция

алгоритм a: X → Y вида a(x) = C(F(b1(x), . .

. , bT (x)), x ∈ X ,
составленный из алгоритмических операторов bt :X→R, t=1,..., T,
корректирующей операции F: RT→R
решающего правила C: R→Y. Базовыми алгоритмами обозначаются функции at(x) = C(bt(x)), а при фиксированном решающем правиле C — и сами операторы bt(x).
Суперпозиции вида F(b1,..., bT ) являются отображениями из X в R, то есть, опять же, алгоритмическими операторами.
Слайд 24

совместное применение нескольких критериев построено заданное количество базовых алгоритмов T; достигнута

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

на обучающей выборке;
достигнутую точность на контрольной выборке не удаётся улучшить на протяжении последних нескольких шагов при определенном параметре алгоритма.
Слайд 25

AdaBoost (adaptive boosting – адаптированное улучшение) Йоав Фройнд (Freund) и Роберт

AdaBoost (adaptive boosting – адаптированное улучшение)

Йоав Фройнд (Freund) и Роберт Шапир (Schapire) в

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

задача классификации на два класса, Y = {−1,+1}. К примеру, базовые

задача классификации на два класса, Y = {−1,+1}. К примеру, базовые

алгоритмы также возвращают только два ответа −1 и +1, и решающее правило фиксировано: C(b) = sign(b). Искомая алгоритмическая композиция имеет вид:
Функционал качества композиции Qt определяется как число ошибок, допускаемых ею на обучающей выборке:
Для решения задачи AdaBoosting’а нужна экспоненциальная аппроксимация пороговой функции потерь [z<0], причем экспонента Ez = e-z 
Слайд 27

Дано: Y = {−1,+1}, b1(x), . . . , bT (x)

Дано: Y = {−1,+1},
b1(x), . . . , bT (x) возвращают −1 и

+ 1,
Xl – обучающая выборка.

Решение: 1. Инициализация весов объектов:  wi:= 1/ℓ, i = 1, . . . , ℓ; (1.9) для всех t = 1, . . . , T, пока не выполнен критерий останова: 2 а. 
2 б.
3. Пересчёт весов объектов. Правило мультипликативного пересчёта весов.
Вес объекта увеличивается в раз, когда bt допускает на нём ошибку, и во столько же раз уменьшается, когда bt правильно классифицирует xi.

Слайд 28

непосредственно перед настройкой базового алгоритма наибольший вес накапливается у тех объектов,

непосредственно перед настройкой базового алгоритма наибольший вес накапливается у тех объектов,

которые чаще оказывались трудными для предыдущих алгоритмов:
4. Нормировка весов объектов
Слайд 29

Слайд 30

Плюсы AdaBoost хорошая обобщающая способность. В реальных задачах практически всегда строятся

Плюсы AdaBoost

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

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

Минусы AdaBoost: Бывает переобучение при наличии значительного уровня шума в данных.

Минусы AdaBoost:

Бывает переобучение при наличии значительного уровня шума в данных. Экспоненциальная

функция потерь слишком сильно увеличивает веса «наиболее трудных» объектов, на которых ошибаются многие базовые алгоритмы. Однако именно эти объекты чаще всего оказываются шумовыми выбросами. В результате AdaBoost начинает настраиваться на шум, что ведёт к переобучению. Проблема решается путём удаления выбросов или применения менее «агрессивных» функций потерь. В частности, применяется алгоритм GentleBoost;
AdaBoost требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных;
Бывает построение неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново.
Бустинг может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных временных затрат на вычисление классификаций.
Слайд 32

Принципы решающего дерева в алгоритме function Node = Обучение_Вершины( {(x,y)} )

Принципы решающего дерева в алгоритме

function Node = Обучение_Вершины( {(x,y)} ) { if

{y} одинаковые return Создать_Лист(y); test = Выбрать_лучшее_разбиение( {(x,y)} ); {(x0,y0)} = {(x,y) | test(x) = 0}; {(x1,y1)} = {(x,y) | test(x) = 1}; LeftChild = Обучение_Вершины( {(x0,y0)} ); RightChild = Обучение_Вершины( {(x1,y1)} ); return Создать_Вершину(test, LeftChild, RightChild); } //Обучение дерева function main() { {(X,Y)} = Прочитать_Обучающие_Данные(); TreeRoot = Обучение_Вершины( {(X,Y)} ); }
Слайд 33

Каскадная модель алгоритма Алгоритм бустинга для поиска лиц с моей точки

Каскадная модель алгоритма

Алгоритм бустинга для поиска лиц с моей точки зрения

таков: 1. Определение слабых классификаторов по прямоугольным признакам; 2. Для каждого перемещения сканирующего окна вычисляется прямоугольный признак на каждом примере; 3. Выбирается наиболее подходящий порог для каждого признака; 4. Отбираются лучшие признаки и лучший подходящий порог; 5. Перевзвешивается выборка.
Слайд 34

Сложность обучения таких каскадов равна О(xyz), где применяется x этапов, y

Сложность обучения таких каскадов равна О(xyz), где применяется x этапов, y

примеров и z признаков. Далее, каскад применяется к изображению: 1. Работа с «простыми» классификаторами – при этом отбрасывается часть «отрицательных» окон; 2. Положительное значение первого классификатора запускает второй, более приспособленный и так далее; 3. Отрицательное значение классификатора на любом этапе приводит к немедленному переходу к следующему сканирующему окну, старое окно отбрасывается; 4. Цепочка классификаторов становится более сложной, поэтому ошибок становится намного меньше.
Слайд 35

Для тренировки такого каскада потребуются следующие действия: 1. Задаются значения уровня

Для тренировки такого каскада потребуются следующие действия: 1. Задаются значения уровня ошибок

для каждого этапа (предварительно их надо количественно просмотреть при применении к изображению из обучающего набора) – они называются detection и false positive rates – надо чтобы уровень detection был высок, а уровень false positive rates низок; 2. Добавляются признаки до тех пор, пока параметры вычисляемого этапа не достигнут поставленного уровня, тут возможны такие вспомогательные этапы, как: а. Тестирование дополнительного маленького тренировочного набора; б. Порог AdaBoost умышленно понижается с целью найти больше объектов, но в связи с этим возможно большее число неточных определений объектов; 3. Если false positive rates остается высоким, то добавляется следующий этап или слой; 4. Ложные обнаружения в текущем этапе используются как отрицательные уже на следующем слое или этапе.
Слайд 36

В более формальном виде алгоритм тренировки каскада: a) Пользователь задает значения

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

уровень ложных срабатываний на слой) и d (минимально допустимый уровень обнаружений на слой) b) Пользователь задает целевой общий уровень ложных срабатываний Ftarget c) P – набор положительных примеров d) N – набор отрицательных примеров e) F0 = 1,0; D0 = 1,0; i = 0 f) while ( Fi > Ftarget) i = i+1; ni = 0; Fi = Fi-1 while (Fi = f * Fi-1 ) ni = ni + 1 AdaBoost(P, N, ni) Оценить полученный каскад на тестовом наборе для определения Fi и Di ; Уменьшать порог для i-того классификатора, пока текущий каскад будет иметь уровень обнаружения по крайней мере d*Di-1 (это же касается Fi) ; g) N = Ø; h) Если Fi > Ftarget , то оценить текущий каскад на наборе изображений, не содержащих лиц, и добавить все неправильно классифицированные в N.
Слайд 37

1. P. Viola and M.J. Jones, «Rapid Object Detection using a

1. P. Viola and M.J. Jones, «Rapid Object Detection using a

Boosted Cascade of Simple Features», proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR 2001), 2001 2. P. Viola and M.J. Jones, «Robust real-time face detection», International Journal of Computer Vision, vol. 57, no. 2, 2004., pp.137–154 3. Р.Гонсалес, Р.Вудс, «Цифровая обработка изображений», ISBN 5-94836-028-8, изд-во: Техносфера, Москва, 2005. – 1072 с. 4. Местецкий Л. М., «Математические методы распознавания образов», МГУ, ВМиК, Москва, 2002–2004., с. 42 – 44 5. Jan ˇSochman, Jiˇr´ı Matas, «AdaBoost», Center for Machine Perception, Czech Technical University, Prague, 2010 6. Yoav Freund, Robert E. Schapire, «A Short Introduction to Boosting», Shannon Laboratory, USA, 1999., pp. 771-780
Слайд 38

https://habrahabr.ru/post/133909/

https://habrahabr.ru/post/133909/

Слайд 39

Улучшение контрастности между фоном и кровеносными сосудами G Выбор цветового канала

Улучшение контрастности между фоном и кровеносными сосудами

G

Выбор цветового канала

Слайд 40

контрастно-ограниченное адаптивное выравнивание гистограммы (contrast limited adaptive histogram equalization – clahe)

контрастно-ограниченное адаптивное выравнивание гистограммы (contrast limited adaptive histogram equalization – clahe)

Слайд 41

Удаление фона при помощи average фильтра Маска сетчатки

Удаление фона при помощи average фильтра

Маска сетчатки

Слайд 42

автоматическое пороговое преобразование методом Otsu, медианный фильтр и фильтр по длине

автоматическое пороговое преобразование методом Otsu, медианный фильтр и фильтр по длине

Слайд 43

Фильтр Габора Способен выделять прямые линии определённого размера и под определённым углом

Фильтр Габора

Способен выделять прямые линии определённого размера и под определённым углом

Слайд 44

применить фильтр Габора с различными углами наклона ядра рассчитать максимальный отклик

применить фильтр Габора с различными углами наклона ядра
рассчитать максимальный

отклик каждого пикселя на серию фильтров

слева – исходное изображение после clahe, справа – результат применения серии габоровских фильтров

Слайд 45

Удаление фона слева – исходное изображение, полученное при помощи алгоритма background

Удаление фона

слева – исходное изображение, полученное при помощи алгоритма background exclusion,

справа – результат применения серии габоровских фильтров
Слайд 46

Пороговое преобразование интенсивности изображения слева – исходное изображение, полученное после перекрашивания

Пороговое преобразование интенсивности изображения

слева – исходное изображение, полученное после перекрашивания пикселей

в соответствии с параметром чувствительности, справа – результат метода Otsu
Слайд 47

Marwan D. Saleh, C. Eswaran, and Ahmed Mueen. An Automated Blood

Marwan D. Saleh, C. Eswaran, and Ahmed Mueen. An Automated Blood

Vessel Segmentation Algorithm Using Histogram Equalization and Automatic Threshold Selection // Journal of Digital Imaging, Vol 24, No 4 (August), 2011, pp 564-572
P. C. Siddalingaswamy, K. Gopalakrishna Prabhu. Automatic detection of multiple oriented blood vessels in retinal images // J. Biomedical Science and Engineering, 2010, 3, pp 101-107
www.isi.uu.nl/Research/Databases/DRIVE
www.ces.clemson.edu/~ahoover/stare
Слайд 48

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

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

Слайд 49

Алгоритм, основанный на методе фазовой корреляции

Алгоритм, основанный на методе фазовой корреляции

Слайд 50

Алгоритм, использующий углы Харриса

Алгоритм, использующий углы Харриса

Слайд 51

Алгоритм, основанный на поиске точек разветвления

Алгоритм, основанный на поиске точек разветвления

Слайд 52

Reddy B.S. and Chatterji B.N. An FFT-Based Technique for Translation, Rotation,

Reddy B.S. and Chatterji B.N. An FFT-Based Technique for Translation, Rotation,

and Scale-Invariant Image Registration // IEEE Transactions on Image Processing. 1996. Vol. 5. No. 8. pp. 1266-1271.
Human recognition based on retinal images and using new similarity function / A. Dehghani [et al.] // EURASIP Journal on Image and Video Processing. 2013.
Hortas M.O. Automatic system for personal authentication using the retinal vessel tree as biometric pattern. PhD Thesis. Universidade da Coruña. La Coruña. 2009.
VARIA database
MESSIDOR database
Слайд 53

Геометрия рук

Геометрия рук

Слайд 54

Движения глаз фиксация глаза на определенной точке дисплея момент движения яблока

Движения глаз

фиксация глаза на определенной точке дисплея
момент движения яблока при

перемещении взгляда с одной точки на другую
Слайд 55

Neurotechnology http://www.neurotechnology.com/

Neurotechnology

http://www.neurotechnology.com/

Слайд 56

Поведенческая биометрия

Поведенческая биометрия

Слайд 57

Биометрия по электрокардиограмме

Биометрия по электрокардиограмме

Слайд 58

Биометрия по почерку

Биометрия по почерку

Слайд 59

Биометрия по походке

Биометрия по походке

Слайд 60

Биометрия по особенностям чтения

Биометрия по особенностям чтения

Слайд 61

Биометрия по особенностям набора текста

Биометрия по особенностям набора текста

Слайд 62

Идентификация личности на основе данных о перемещениях (трекинга)

Идентификация личности на основе данных о перемещениях (трекинга)