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

За последние годы для задач видеонаблюдения предложено и реализовано множество алгоритмов обнаружения конкретных нештатных ситуаций на основе строгих правил [1, 2]. Хотя данный подход позволяет с высокой надёжностью распознавать заранее известные типы нештатных ситуаций, модификация алгоритмов для выявления иного типа аномалий нетривиальна. Для устранения данного недостатка было предложено множество подходов к обнаружению аномалий в сцене [3]. Одним из них является поиск отклонений от модели, составленной на основе примеров нормального поведения. Для решения данной задачи часто используют оценки на основе метода главных компонент [4]. Ранее был предложен алгоритм обнаружения нештатных ситуаций на основе метода главных компонент [5]. Данный алгоритм обучается путём вычисления набора главных компонент для векторов характеристик нормального поведения. При поступлении нового примера нормального поведения требуется повторное вычисление главных компонент по старым и новым данным, но вычислительная сложность данной процедуры не позволяет применить её в реальном времени. Одним из способов устранения данного недостатка является инкрементное обучение [6], которое заключается в адаптации модели по новым данным.

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

• 1.    Метод

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

Выделение фона

Для выделения фона использовалась самоорганизующаяся искусственная нейронная сеть, предложенная в работе [7]. Параметры сети подбирались на основе экспериментальных данных. Хотя предложенный ранее критерий качества выделения фона на основе морфологических операторов [8] позволяет получить некие оценки параметров самоорганизующейся сети, он не учитывает особенностей остальных этапов алгоритма. Например, ложные объекты мало влияют на оценку движения в сцене, но отнесение объекта к фону вносит существенное искажение в характеристики поведения.

Оценка движения

Для оценки движения пикселей объектов между двумя последовательными кадрами был использован пирамидальный метод Лукаса–Канаде [9]. Для компенсации влияния перспективной проекции методом плоской гомографии [10] рассчитывались векторы смещения – проекции векторов оптического потока на плоскость пола. Затем вычислялись значения длин векторов смещения, к которым применялся медианный фильтр.

Извлечение признаков поведения

Вектор признаков поведения был выбран как последовательность отфильтрованных длин векторов смещения для всех пикселей на изображении. Пусть изображение имеет размеры W × H , а d ( x , y ) – вектор смещения для пикселя с координатами ( x , у ). Тогда вектор признаков поведения f можно записать в следующем виде:

f ={| <^(0,0)|,| d (1,0)|,...| d(w ,0)|,

I J(0,1)|,^| d(W ,1)|,™| d(W , H )| } .

Обнаружение нештатных ситуаций

Для оценки аномальности поведения в сцене по векторам признаков применялся метод на основе главных компонент [5], суть которого заключается в следующем. На стадии обучения для всех примеров «нормального» поведения извлекаются вектора признаков, и для получившегося набора векторов находятся главные компоненты. Во время работы текущий вектор признаков поведения проецируется на набор векторов главных компонент и обратно. В общем случае набор векторов главных компонент не является базисом и некоторая составляющая вектора теряется при проецировании. Далее эта составляющая называется вектором невязки, и её можно вычислить из следующих выражений:

r = f - f = f - F - Z>V , р. =(f - F, v),

где r - вектор невязки, f - текущий вектор характеристик поведения, f r - результат прямого и обратного проецирования вектора f , F – среднее значение вектора характеристик поведения по обучающей выборке, v - вектор i -й главной компоненты, р , -проекция вектора f на вектор v , ( f - F , v i ) - скалярное произведение векторов v и f - F , q - общее количество главных компонент.

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

Инкрементное обучение данного метода сводится к задаче обновления главных компонент по новому значению вектора характеристик нормального поведения. Пусть n – размерность вектора характеристик поведения, а m – количество примеров в исходной обучающей выборке. Если пренебречь изменением среднего значения вектора характеристик F , то ковариационную матрицу C' размером n × n для дополненной обучающей выборки можно записать в следующем виде:

1 m+1

C '= — 7 Z ( f k - F )( f k - F ) m + 1 к

T

m

---7Z( fk - F )( f_k - F ) T + m + 1 _k

+ -^( f m +1 - F )( f +1 - F ) T = m + 1

m m +1

C +

----; ( f m +1 m +1

- F )( f m +1 - F ) T ,

где C’ - ковариационная матрица для дополненной обучающей выборки, f m _{+ 1} - новое значение вектора характеристик нормального поведения, а C – ковариационная матрица для исходной обучающей выборки.

Если количество главных компонент q для исходной обучающей выборки совпадает с размерностью вектора характеристик n , то вектора главных компонент образуют базис и вектор невязки равен нулю. Рассмотрим случай, когда q <  n . Составим ортонор-мированный базис из векторов главных компонент, нормализованного вектора невязки r m _{+ 1} /1 r m _{+ 1}1 для нового примера нормального поведения и произвольных векторов { v_{q +} 2 ... vn }. С учётом выражения (2) новое значение вектора характеристик нормального поведения f m _{+ 1} после вычитания среднего значения вектора характеристик F можно записать в данном базисе следующим образом:

v v           q          q fm+1 - F = rm+1 + Z Pivi = Z PiV,■+ Irm+1 I Tm^ .

I                   I                          I rm +1|

Определим ортогональную матрицу V размером n × n вида:

V = [V0 _ Vq rm+1/rm+11 Vq+2 ^ V„ J.(5)

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

~X0 ■ ; 0 0 ■ 0" : 0 • XQ 0 0 C = V q VT = VЛ VT ,     (6) 0 ■ 0 0 0 _ 0 • 0 0 • 0_ где Xi - собственное значение i-й главной компоненты.

Аналогично спектральное разложение ковариационной матрицы C ' для дополненной обучающей выборки можно представить в виде:

C ' = V 'A'V' T = -m- V Л V T + m + 1

+ ^Т( f m +1 - F )( f m +1 - F ) T .

m + 1

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

V 'л,V' T = my л VT + m +1

+      VV T ( f m +1 - F ) ( f m _{+ 1} - F ) T VV T =           (8)

m + 1

= -1- V [ m л + V T ( f m +1 - F ) ( f m +1 - F ) T V J V T .

m + 1

Определим матрицу M размером n × n следующим образом:

M = m Л + V T ( f m +1 - F )( f m +1 - F ) T V ,           (9)

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

V 'Л'V' T = J- VV m Л M V MT V T , m + 1

V '= VVm , Л =    Л M , m +1

где V_m - матрица из собственных векторов M , Л _M -матрица из собственных чисел M .

Для анализа структуры матрицы M необходимо рассмотреть часть второго слагаемого с учётом выражений (4) и (5):

m % о + p 2 •	p 0 p q	p 0 F m +1	0	■ 0"
p q p 0	• m % q + p q	p q V m +1	0	0
F m +1 p 0    •	■    r m +1 p q	V m +12	0	0	• (13)
0	0	0	0	0
0	0	0	0	• 0 _

Из (13) видно, что все столбцы и строки матрицы M с индексами больше q +1 равны нулю, что позволяет произвести спектральное разложение лишь для верхнего левого блока. Тем не менее, средняя вычислительная сложность данной операции составляет O ( q ³) [12], что при большом количестве главных компонент не позволяет применить её в реальном времени.

Предлагаемая схема инкрементного обучения заключается в следующем. Если пренебречь взаимоза-висимостями между проекциями вектора характеристик f_{m + 1} на составленный базис, то обновление главных компонент можно производить по набору векторов следующего вида:

{ F + ( f m +1 , 1 ) V o , _ , F + ( f m +1 , V q ) V q , F + ^ +1 } • (14)

При проецировании таких векторов только одна из компонент вектора (12) отлична от нуля, и матрица M принимает диагональный вид. Введя шаг инкрементального обучения c , получаем следующую схему обновления собственных значений:

(1 - c ) % i + c • p , ², i <  q, c • r m +1|² , i = q + 1.

V T ( f m +1

- F) =

vq rm+1/ m+1|

V q +2

V n

(^L Piv'i ⁺ r m +1| r ^m )• (11) i                          | rm +11

Поскольку вектора { Vq _{+ 2} ... V_n } вместе с векторами главных компонент v i и нормализованным вектором невязки r_{m + 1} /1 r_{m + 1}1 образуют ортонормирован-ный базис, то выражение (11) сводится к следующему:

p 0

V T ( f m +1 - F ) =

p q

| Fm +1|

Тогда матрица M запишется в виде:

Таким образом, инкрементное обучение метода сводится к добавлению главной компоненты с вектором r_{m + 1} /1 r_{m + 1}1 и обновлением собственных значений по формуле (15). Данный подход использует неточный способ определения главных компонент для дополненной обучающей выборки, но его вычислительная сложность составляет O ( q ).

2. Результаты экспериментов

Предлагаемая схема инкрементного обучения алгоритма обнаружения нехарактерного поведения на основе главных компонент была реализована в качестве алгоритма обработки видеоизображений. Работа алгоритма была протестирована на наборе данных лаборатории университета Калифорнии в Сан-Диего (UCSD) [11] и экспериментально полученных видео. Видеозапись «Работа и ремонт» была сделана в компьютерном классе ННГУ. На ней в качестве нормального поведения была взята работа за компьютером, а в качестве нештатного – манипуляции с задней панелью системного блока. Видеозапись лаборатории UCSD содержит пешеходную улицу, обычная ходьба

по которой была взята за нормальное поведение, а проезд транспортных средств – за нештатное.

Из каждого видео бралось ограниченное число примеров нормального поведения. Часть примеров использовалась для обычного обучения алгоритма, а остальная часть – для инкрементного обучения. Затем вычислялись значения максимальной невязки для остальных кадров с нормальным и аномальным поведением из выбранного видео. На основе полученных значений рассчитывались равные уровни ошибок, которые представляют собой уровень ошибок при равной частоте ложных тревог и пропуска события [11]. При этом для уменьшения влияния шума и вычислительных погрешностей отбрасывались главные компоненты, которые описывали менее 0,1 % вариации характеристик нормального поведения. Для сравнения также рассматривался случай, когда все примеры нормального поведения использовались для обычного обучения алгоритма.

Параметры самоорганизующейся сети для извлечения фона [7] и размер медианного фильтра для длин векторов смещения подбирались из условия минимума равного уровня ошибок алгоритма на видеозаписях и приведены в табл. 1. Шаг инкрементного обучения c был задан равным 0,00001.

Табл. 1. Параметры извлечения характеристик поведения из видео «Работа и ремонт» и видео лаборатории UCSD

Параметр	Работа и ремонт	UCSD
Начальный порог сети для извлечения фона	1	1
Рабочий порог сети для извлечения фона	0,001	0,05
Начальная скорость обучения сети для извлечения фона	1	1
Рабочая скорость обучения сети для извлечения фона	0,001	0,001
Размер медианного фильтра, пиксели	3	5

В табл. 2 приведены равные уровни ошибок алгоритма при разном количестве примеров нормального поведения для обычного и инкрементного обучения. Из табл. 2 видно, что предложенная схема инкрементного обучения позволяет достичь результатов, аналогичных обычному обучению. При этом расхождение в равных уровнях ошибок объясняется неточностью определения главных компонент при инкрементном обучении. Для видео лаборатории UCSD полученные результаты близки к равному уровню ошибок в 23 %, который является минимальным среди всех методов, рассмотренных в работе [11].

Тестирование предлагаемого алгоритма было проведено на компьютере с четырёхъядерным CPU Intel Core i7 4,2 ГГц и 16 GB RAM. В табл. 3 приведено среднее время инкрементного обучения на одном примере нормального поведения на основе спектрального разложения матрицы M и по предложенной схеме при разном количестве главных компонент. Из табл. 3 видно существенное сокращение времени инкрементного обучения при использовании предложенной схемы вместо подхода на основе спектрального разложения.

Табл. 2. Равный уровень ошибок максимальной невязки для видео «Работа и ремонт» и видео лаборатории UCSD при разном количестве примеров нормального поведения для обычного и инкрементного обучения. Знак «+» обозначает инкрементное обучение и разделяет количество примеров для обычного и инкрементного обучения

Название видео	Количество примеров	Максимальная невязка
Работа и ремонт	3+2	5,72 %
Работа и ремонт	3+4	7,02 %
Работа и ремонт	3+6	1,47 %
Работа и ремонт	5	5,72 %
Работа и ремонт	7	1,58 %
Работа и ремонт	9	1,47 %
UCSD	5+5	28,56%
UCSD	5+10	26,20%
UCSD	5+15	27,95 %
UCSD	5+20	26,57%
UCSD	10	28,85 %
UCSD	15	26,63 %
UCSD	20	28,60%
UCSD	25	27,41 %

Табл. 3. Среднее время инкрементного обучения на одном примере нормального поведения для кадров из видео «Работа и ремонт» и видео лаборатории UCSD на основе спектрального разложения и предложенной схемы при разном количестве главных компонент

Название видео	Количество главных компонент	Обучение на основе спектрального разложения, мс	Предложенная схема, мс
Работа и ремонт	205	199,68	14,74
UCSD	624	5438,52	68,58

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

Заключение

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

Табл. 4. Среднее время извлечения вектора характеристик и расчета невязок для кадров из видео «Работа и ремонт» и видео лаборатории UCSD при разном количестве примеров нормального поведения для обычного и инкрементного обучения. Знак «+» обозначает инкрементное обучение и разделяет количество примеров для обычного и инкрементного обучения

Название видео	Количество примеров	Количество главных компонент	Извлечение харак-тери-стик, мс	Вычисление невязок, мс
Работа и ремонт	3	205	98,9	13,9
Работа и ремонт	5	227	99,2	15,2
Работа и ремонт	7	257	98,5	17,2
Работа и ремонт	9	265	99,4	17,7
Работа и ремонт	3+2	220	99,2	14,8
Работа и ремонт	3+4	202	99,7	13,7
Работа и ремонт	3+6	265	98,9	17,8
UCSD	5	624	13,3	32,7
UCSD	10	1353	13,3	69,4
UCSD	15	1161	13,7	59,9
UCSD	20	1614	13,7	83,8
UCSD	25	1815	13,6	93,7
UCSD	5+5	703	13,7	36,8
UCSD	5+10	366	13,4	19,3
UCSD	5+15	456	13,6	24,0
UCSD	5+20	593	13,2	30,5