ТЕХНИЧЕСКИЕ НАУКИ
Информатика, вычислительная техника
и управление
Системный анализ, управление и обработка
информации
Малистов А. С., кандидат технических наук, зам. руководителя отдела ЗАО «ЭЛВИС-НеоТек»
АЛГОРИТМЫ ОБНАРУЖЕНИЯ ДВИЖЕНИЯ КОМПЬЮТЕРНЫМИ
ВИДЕОСИСТЕМАМИ
Среди способов решения задачи выделения движущихся объектов компьютерными видеосистемами выделим четыре: по разности яркости соседних кадров (temporal difference), по интенсивности оптического потока (optic flow), по выявлению особенностей (feature tracking) изображения и методом вычитания фона (background substraction).
Оптическим потоком называется векторное поле смещений пикселов между последовательными кадрами, заданное на двухмерном изображении. Задача вычисления оптического потока состоит в том, чтобы оценить сдвиг изображения в каждой точке по имеющимся данным о яркости пикселов на последовательных кадрах. Среди широко известных методов можно выделить три основные группы: дифференциальные методы (Horn and Schunck, Bruce Lucas and Takeo Kanade), расчёт фазовой корреляции (Kuglin and D.C. Hines, E. De Castro and C. Morandi) и методы, основанные на сопоставлении окрестностей (Anan-dan P, J.J. Little and A. Verri).
Основой для дифференциальных методов послужили работы Хорна и Шунка, а также Лукаса и Канаде. Методы называются дифференциальными благодаря использованию в них численных приближений пространственно-временных частных производных сигналов изображений. Пусть I(r,t) = l{x,y,t) — интенсивность пиксела г = (х,у) в момент времени t. Если изображение в некоторой окрестности в момент времени t сдвинулось на некоторый вектор v = (vx,Vy)T по сравнению со временем 0, тогда I(r, t) = I(r — vt, 0). Основная идея дифференциальных методов заключается в том, чтобы разложить последнее выражение в ряд Тейлора:
Vl{r,t)-v + lt{r,t) = 0, (1)
где VI(r, t) = (Ix(r, t), Iy(r, t))T. К сожалению, уравнение (1) — это уравнение с двумя неизвестными (vx и vy), поэтому не может быть решено в таком виде. Это называется апертур-ной проблемой вычисления оптического потока. Можно лишь вычислить проекцию вектора v на направление градиента VI.
Алгоритм Хорна-Шунка, предложенный в 1981 году, оценивает оптический поток, используя понятие глобальной функции энергии:
Е = I((17/ • v + /t)2 + a(IVvxl2 + IVVyl2)) dxdy,
(2)
D
где й = [0, ш] X [0, й]с!2 - область изображения, а> 0 - параметр регуляризации, не зависящий от х и у. Экстремум энергии можно найти, решая уравнения Эйлера-Лагранжа с помощью метода Якоби (метод простых итераций) или итерационным методом Гаусса-
Зейделя. Алгоритмическая сложность метода Хорна-Шунка имеет порядок 0(SN), где S = wh — количество пикселов в изображении, N — количество итераций метода Якоби или Гаусса-Зейделя.
Алгоритм Лукаса-Канаде, предложенный также в 1981 году, может работать c локальными окрестностями. Оптический поток определяется отдельно в окрестности Г каждой интересующей нас точки как вектор V, минимизирующей взвешенную сумму квадратов невязки уравнений (1) для точек окрестности. Алгоритмическая сложность алгоритма Лукаса-Канаде имеет порядок 0(S • |Г|), где S — размер изображения, |Г| — размер окрестности Г. Более подробно об алгоритмах Хорна-Шунка и Лукаса-Канаде можно узнать в работе Andres Bruhn и соавторов (IJCV, 2005, vol. 61).
Применение дифференциальных методов не всегда возможно из-за шума и неровностей изображения. Более подходящими в этом случае считаются методы, основанные на сравнении окрестностей. Поток v определяется как смещение одного изображения относительно другого, дающее минимум расстояния между изображениями в окрестности исследуемой точки. Расстояние может определяться, например, как минимальная сумма модулей (или квадратов) разностей яркости или нормированная кросс-корреляция. Временная сложность таких алгоритмов имеет порядок 0(S|f|M) для М потенциально возможных смещений. Если использовать гауссову пирамиду, то сложность сокращается до 0(5|Г| logМ). Более подробно о дифференциальных методах и методах сравнения окрестностей можно узнать в работе J.J. Little and A. Verri.
Одним из наиболее качественных способов определения наличия движения является метод прослеживания особенностей, одновременно оставаясь и самым затратным по времени. В действительности, нет никакого универсального или точного определения, что такое особенность изображения. Каждый раз определение зависит от выбора алгоритма, который работает с особенностями. Считается, что, особенность — это некоторая «интересная» часть изображения. Практически любой алгоритм прослеживания особенностей состоит из двух этапов: выделение особенностей (feature detection) и сопоставление особенностей на различных кадрах (feature matching). Качество алгоритма зависит от того, насколько верно дано определение особенности и как хорошо работает выделение этих особенностей. Необходимо задавать их таким образом, чтобы та же самая особенность могла быть обнаружена на различных изображениях той же самой сцены наблюдения. Одним из наиболее встречаемых в литературе подходов является поиск точечных особенностей. В работе Moravec предложено использовать автокорреляционную функцию для выделения особых точек:
fr(Ax,Ay) = ^ (1(х + Ах,у + Ау)-1(х,у))2.
(х,у)ег
(Особыми точками считаются те точки, для окрестности Г которых автокорреляционная функция превышает порог для всех смещений (Ах, Ау). Для небольших смещений (Ах, Ау) можно использовать разложение в ряд Тейлора, аппроксимируя автокорреляционную функцию квадратичной формой. Для того, чтобы любые направления смещения (Ах, Ау) давали большие значения /г, необходимо, чтобы были большими оба собственных значения Л1 и Л2 матрицы квадратичной формы: тт(Л1,Л2)>Л*. В работе Harris и Stephens используется взвешенная сумма при определении автокорреляционной функции:
fF(Ax,Ay)= ^ w (x,y)(I(x + Ах,у + Ау)-/(х,у))2,
(х,у)ег
где wr(r) — весовая функция, обычно имеющая большие значение к центру окрестности Г.
Среди других способов выделения особых точек широко используются методы, основанные на выделении контуров (H. Asada and M. Brady) и методы, использующие моделирование особенностей (S. Baker, S. Nayar, and H. Murase). При выделении контура особыми
точками считаются точки перегиба и/или точки высокой кривизны. Методы, использующие моделирование особенностей, основаны на построении моделей различных кривых и поиске этих кривых на градиентном изображении.
Метод вычитания фона предполагает, что если для каждого пиксела с координатами (х, у) среднее значение яркости в случае, когда этот пиксел является неподвижным, известно и равно В(х,у), можно выяснить с некоторой достоверностью, принадлежит ли этот пиксел фону или какому-то подвижному объекту. Так как значение интенсивности фона заранее неизвестно, то наибольшее распространение получил метод вычитания фона, в котором используется адаптивное накопление средней интенсивности. Основная идея, описанная у Grimson и Viola, состоит в том, что для каждого пиксела (х, у), интенсивность которого на этом кадре равна /п(х, у), мы храним в памяти так называемое скользящее среднее интенсивности Вп(х,у) и условную оценку шума Гп(х,у), которые обновляются на каждом кадре. Статистический критерий использует значения Вп(х,у) и Тп(х,у) вместо фиксированных В{х,у) и Г(х,у):
m (хул = Î1, если КпС^У) - 5n_i(x,y)1 > d • Гn_1(x>y)> п\. >У) |о, в остальных случаях, ( )
где d — так называемый линейный коэффициент порога. Значение этого коэффициента позволяет манипулировать ошибками первого и второго рода. Чем меньше d, тем выше доля ложных срабатываний, напротив, чем больше d, тем выше вероятность пропуска движения. В работе T. Kanade, R. Collins, A. Lipton, P. Anandan, and P. Burt обновление статистики предлагается производить лишь для неподвижных пикселов.
Метод вычитания фона является широко используемым из-за его высокой производительности. Алгоритмическая сложность имеет порядок 0(5), где S - количество пикселов изображения. К достоинствам можно также отнести адаптацию к медленному изменению освещённости (смена дня и ночи) и обнаружение объектов, двигающихся с малой скоростью. Из недостатков отметим несоответствие теоретической модели следующим реальным условиям: дрожание камеры, быстрые глобальные изменения освещённости (переменная облачность), локальные изменения фона (добавление или исчезновения объектов).
Для уменьшения влияния локального изменения фона в работе Stauffer и Grimson предлагается ввести множественный фон. Вместо единственного значения фона Вп(х>у) и оценки шума Гп(х>у)> предлагается хранить несколько пар таких значений (5^(х, у), 7п^(х, у)), i = 1, к, предполагая, что интенсивность фона моделируется случайной величиной, функция распределения которой представляет собой смесь нормальных распределений. Обновление значений усреднённой интенсивности и оценки шума производим лишь для той пары Г, для которой минимальным будет значение следующего отношения:
i = argmin
/®(х,у)-Я®(х,У)
тХ\х,у)
Для уменьшения влияния дрожания фона необходимо использовать алгоритмы стабилизации видеоизображений. Для уменьшения влияния изменения освещённости используются методы выравнивания яркости. После разбиения множества всех точек изображения на подвижные и неподвижные производится сегментация близлежащих точек на области движения. Эти области служат выходом алгоритма вычитания фона и входом для задачи построения траекторий.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.