Быстрый алгоритм построения фонового изображения на основе интервалов стабильности

Запропоновано швидкий алгоритм попіксельної побудови фонового зображення для унімодальних сцен. Алгоритми на основі усереднення останніх значень та на основі композиції гауссівських щільностей удосконалено шляхом додання процедури перевірки на стабільність останніх значень піксела, що дозволило змен...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автор:	Прокофиев, А.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Назва видання:	Проблемы управления и информатики
Теми:	Методы обработки информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/209137
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности / А.В. Прокофиев // Проблемы управления и информатики. — 2008. — № 3. — С. 119-126. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-209137
record_format	dspace
spelling	irk-123456789-2091372025-11-16T01:18:37Z Быстрый алгоритм построения фонового изображения на основе интервалов стабильности Швидкий алгоритм побудови фонового зображення на основі інтервалів стабільності Fast background modeling algorithm based on stability intervals Прокофиев, А.В. Методы обработки информации Запропоновано швидкий алгоритм попіксельної побудови фонового зображення для унімодальних сцен. Алгоритми на основі усереднення останніх значень та на основі композиції гауссівських щільностей удосконалено шляхом додання процедури перевірки на стабільність останніх значень піксела, що дозволило зменшити кількість обчислень та збільшити продуктивність. A fast algorithm of per pixel background modeling for unimodal scenes is proposed. Ideas of recent values average algorithm and mixture of Gaussian densities algorithm were improved with the idea of stability checking for recent pixel values. As consequence an amount of calculation was reduced and a better performance was achieved 2008 Article Быстрый алгоритм построения фонового изображения на основе интервалов стабильности / А.В. Прокофиев // Проблемы управления и информатики. — 2008. — № 3. — С. 119-126. — Бібліогр.: 6 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209137 004.932 10.1615/JAutomatInfScien.v40.i6.70 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Прокофиев, А.В. Быстрый алгоритм построения фонового изображения на основе интервалов стабильности Проблемы управления и информатики
description	Запропоновано швидкий алгоритм попіксельної побудови фонового зображення для унімодальних сцен. Алгоритми на основі усереднення останніх значень та на основі композиції гауссівських щільностей удосконалено шляхом додання процедури перевірки на стабільність останніх значень піксела, що дозволило зменшити кількість обчислень та збільшити продуктивність.
format	Article
author	Прокофиев, А.В.
author_facet	Прокофиев, А.В.
author_sort	Прокофиев, А.В.
title	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности
title_short	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности
title_full	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности
title_fullStr	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности
title_full_unstemmed	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности
title_sort	быстрый алгоритм построения фонового изображения на основе интервалов стабильности
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2008
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/209137
citation_txt	Быстрый алгоритм построения фонового изображения на основе интервалов стабильности / А.В. Прокофиев // Проблемы управления и информатики. — 2008. — № 3. — С. 119-126. — Бібліогр.: 6 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT prokofievav bystryjalgoritmpostroeniâfonovogoizobraženiânaosnoveintervalovstabilʹnosti AT prokofievav švidkijalgoritmpobudovifonovogozobražennânaosnovííntervalívstabílʹností AT prokofievav fastbackgroundmodelingalgorithmbasedonstabilityintervals
first_indexed	2025-11-16T02:06:03Z
last_indexed	2025-11-17T02:08:51Z
_version_	1849001594476036096
fulltext	© А.В. ПРОКОФИЕВ, 2008 Проблемы управления и информатики, 2008, № 3 119 УДК 004.932 А.В. Прокофиев БЫСТРЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ФОНОВОГО ИЗОБРАЖЕНИЯ НА ОСНОВЕ ИНТЕРВАЛОВ СТАБИЛЬНОСТИ Введение Современные автоматизированные системы используются для решения задач наблюдения и контроля обстановки, выполняя часть рутинной работы. Перед про- граммным обеспечением таких систем ставятся все более интеллектуальные зада- чи, например такие, как комплексный анализ полученных данных и принятие ло- гических решений. Так, в современных автоматических системах видеонаблюде- ния уже недостаточно просто отображать данные с камеры, нужно выполнять поиск на изображениях движущихся объектов, отслеживать их из кадра в кадр, классифицировать. Именно задаче поиска движущихся объектов на изображении посвящена эта работа. Простейший способ поиска движущихся объектов — построение модели фо- нового изображения сцены и сравнение этой модели с текущим изображением. Под фоновым изображением понимается совокупность пикселов, которые отно- сятся к неподвижным объектам сцены или объектам, не интересующим систему наблюдения (они могут и не быть неподвижными, к примеру крона дерева на вет- ру, волны на поверхности воды). Тогда можно считать, что в областях текущего изображения, которые не согласуются с моделью фонового изображения, проис- ходит движение. Характерные проблемы, с которыми приходится сталкиваться при по- строении фонового изображения на основе цветовой информации, такие [1]: 1) изменение освещения (внезапное или постепенное); 2) движение объектов, ко- торые ранее относились к фоновому изображению; 3) инициализация алгоритма при наличии движущихся объектов на сцене; 4) тени, отбрасываемые движущи- мися объектами. Автоматические системы наблюдения должны работать в реальном времени. Их основная задача — захват и сопровождение движущихся объектов. Эта задача более сложная, чем определение областей, в которых происходит движение. По- этому при построении фонового изображения следует находить компромисс меж- ду временем выполнения алгоритма и его точностью, выбирать наиболее быстрый алгоритм из удовлетворительных. 1. Требования к алгоритмам построения фонового изображения Рассмотрим задачу построения фонового изображения, которая состоит в сле- дующем. По последовательности полутоновых изображений, получаемых в реаль- ном времени с одной зафиксированной видеокамеры, необходимо построить модель фонового изображения, которая позволяла бы на каждом входном изобра- жении находить передний план изображения — области пикселов, соответствую- щие движущимся объектам. Алгоритм построения фонового изображения должен удовлетворять сле- дующим требованиям. 1. Корректно инициализироваться при наличии движущихся объектов. 2. Обеспечивать быстрый захват/обновление при отсутствии изменений. 120 ISSN 0572-2691 3. Гарантировать постоянное обновление при наличии незначительных изме- нений во входном изображении (плавное изменение освещения). 4. Обеспечивать мгновенное обнаружение масштабных изменений (резкое изменение освещения или положения камеры) и перестраивание изображения в результате. 5. Обеспечивать корректную обработку при перемещении предметов сцены, которые ранее относились к фоновому изображению (предмет, который действи- тельно начал двигаться, относить к переднему плану, а часть сцены, где предмет находился ранее, — к фоновому изображению). 6. Предусматривать возможность задания областей, в которых не нужно вы- полнять вычисления. 7. Основываться на блочных, а не попиксельных вычислениях, что гаран- тирует возможность применения оптимизированных библиотек для обработки изображений. 2. Реализация алгоритмов построения фонового изображения 2.1. Фоновое изображение как усреднение нескольких последних кадров. Один из простых и быстрых алгоритмов построения фонового изображения осно- вывается на принципе усреднения нескольких (N) последовательных входных изображений. В частности, выполнение п. 3 требований к алгоритму при усредне- нии может быть обеспечено, если его проводить по последним полученным изо- бражениям. Движущиеся объекты оказывают незначительное влияние на отдель- ный пиксел фонового изображения, поскольку время, в течение которого изобра- жение объекта содержало этот пиксел, относительно невелико по сравнению со временем отсутствия движения в этом пикселе. Фоновое изображение вычисляет- ся попиксельно согласно рекуррентной формуле (индексы i, j для изображений )(kf и ,)(kb отвечающие конкретному пикселу, опущены): ,)1( )()()1()()( kkkkk fbb   (1) где )(k — весовые коэффициенты усредняемых изображений-кадров,        ;1,/1 ,,/1 )( Nkk NkN k )(kf — входное изображение-кадр с соответствующим номером; )(kb — фоно- вое изображение на соответствующем рекуррентном шаге усреднения. Количество кадров N, по которым проводится усреднение, следует выбирать с учетом частоты кадров и интервала времени, за которое фоновое изображение должно быть полностью обновлено. Недостаток рассматриваемого алгоритма состоит в том, что за движущимися объектами в результате усреднения образуются шлейфы. Размер шлейфа тем больше, чем меньше скорость движения объекта. 2.2. Модель фонового изображения на основе композиций гауссовских плотностей. Среди существующих алгоритмов моделирования фонового изобра- жения наиболее универсален вероятностный подход попискельного моделирова- ния на основе композиций плотностей гауссовских ),( N -распределений в евк- лидовых пространствах [1]. Идея алгоритма заключается в том, чтобы для каждо- го пиксела определить интервалы, содержащие близкие и регулярно принимаемые им значения. Каждый интервал задается с помощью гауссиана — плотности гаус- Проблемы управления и информатики, 2008, № 3 121 совского распределения случайной величины, параметрами которого служат среднее арифметическое и матрица ковариации значений, попадающих в интер- вал. Поскольку в общем случае таких интервалов для пиксела может быть не- сколько, то его значение моделируется композицией гауссианов и к параметрам гауссиана добавляется весовой коэффициент. Изначально композиция гауссианов, представляющая пиксел, пуста. Для ка- ждого входного изображения новое значение пиксела проверяется на принадлеж- ность к существующим гауссианам (считается, что оно принадлежит гауссиану, если новое значение отличается от среднего значения гауссиана не более чем на 2,5 величины его среднеквадратического отклонения). Если такие гауссианы су- ществуют, то их средние значения и матрицы ковариации пересчитываются. Если же такого гауссиана нет, то гауссиан с наименьшим весовым коэффициентом за- мещается новым гауссианом с текущим значением пиксела в качестве среднего значения, изначально большим разбросом и малым весовым коэффициентом. Да- лее выполняется перерасчет и нормирование весовых коэффициентов гауссианов, вследствие чего они возрастают для гауссианов, которым принадлежит значение пиксела. Детальное описание алгоритма содержится в [1, 2]. Алгоритм позволяет моделировать сложные многомодальные фоновые изо- бражения, т.е. такие, которые нельзя представить одним значением с некоторой погрешностью, но можно описать в виде периодических переходов между фикси- рованными значениями. Такими могут быть изображения волн на воде, крон де- ревьев. Этот алгоритм самонастраивающийся, может работать с цветными изо- бражениями. Недостаток алгоритма состоит в том, что он требует значительных объемов вычислений, особенно для пикселов, в которых происходит движение, поскольку их значения существенно меняются (рис. 1) и на каждом кадре прихо- дится сначала просматривать все их гауссианы, а затем обновлять последний. Вычисление среднего значения и матрицы ковариации — промежуточный этап алгоритма, тем не менее использование этих характеристик уже по себе дос- таточно для построения фоновых изображений унимодальных сцен. Опишем один из вариантов такого алгоритма. 2.3. Фоновое изображение на основе интервалов стабильности. 2.3.1. Построение фонового изображения на основе интервалов стабиль- ности. Значения, которые принимает отдельный пиксел изображения, имеют дос- таточно сильный разброс, когда в нем происходит движение, и почти не изменя- ются, когда движения нет (исключения бывают, когда сцена соответствует дви- жению однотонного большого или медленного объекта). Предположим, что фоновое изображение унимодально (т.е. для его представления достаточно одного гауссиана). Тогда для построения его модели следует сосредоточиться только на интервалах времени, в которые значение пиксела относительно стабильно. На- пример, разброс последних l значений не должен превышать допустимого преде- ла. Текущее значение пиксела стоит использовать для вычисления его фонового значения, только если оно стабильно. Пусть },,,{ 21 nxxxX  — значения отдельного пиксела полутонового изображения в моменты времени .,,1 n Обозначим )(, xm lt среднее значение l последовательных элементов выборки X, которые заканчиваются t-м значением :)( lt  . 1 )( 1 ,    t lti ilt x l xm (2) 122 ISSN 0572-2691 Тогда при поступлении нового изображения 1tx значение )(,1 xm lt можно вы- числить так: ).( 1 )( 11 )( 11,11 1 1 ,1                 lttlttlt t lti i t lti ilt xx l xmxxx l x l xm (3) Это требует сохранения в памяти l последних значений выборки X. В случае выпол- нения условия стабильности корректным будет допущение, что ),(,1 xmx ltlt  и тогда уравнение (3) приобретает вид . 1 ,)()1( 1 )( 1 )( 1,1,,1 l xxmx l xm l l xm tlttltlt     (4) Заметим, что это уравнение используется в алгоритме построения фонового изо- бражения для усреднения нескольких последних кадров и именно из-за отсутст- вия проверки на стабильность могут появится шлейфы за движущимися объектами. Дисперсию 2 ,lt вычисляем по формуле ).()( 2 , 2 , 2 , xmxm ltltlt  (5) В качестве условия стабильности можно взять ограничение максимального значе- ния дисперсии .22 , hlt  (6) Однако при расчете дисперсии по формуле (5) необходимо сохранять и пересчи- тывать значение ),( 2 , xm lt что приводит к неэффективности вычислений. Поэто- му будем рассматривать текущее отклонение пиксела от его среднего значения tltt xxm   )(,1 и среднее отклонение пиксела ),(, xlt которое определим аналогично (4): . 1 1 ),()()1()( 1,,1    l xxx tltlt (7) Для проверки стабильности последних значений пиксела используем систему не- равенств ,)(, hxlt  (8) ),( ht  (9) где  — ограничение на максимально допустимое отклонение от среднего значе- ния. Условие (9) необходимо для мгновенного обнаружения начала изменений, а условие (8) отвечает за среднее отклонение последних l значений пиксела от среднего значения. Проверка с использованием этой системы неравенств соответ- ствует отбору пикселов изображения с помощью «трубочного фильтра». В ре- зультате такой фильтрации при подсчете фонового изображения учитываются значения только тех пикселов, которые на протяжении минимального интервала стабильности («длины трубки») отклонялись от своего среднего значения не бо- лее чем на h («толщину трубки»). На рис. 1 показано изменение значения пиксела полутонового изображения со временем. Пунктирной кривой изображены реально принимаемые значения, Проблемы управления и информатики, 2008, № 3 123 непрерывной кривой — значения пиксела фонового изображения, построенного на основе интервалов стабильности. Значительные колебания пунктирной кривой соответствуют наличию движения в пикселе. 170 190 210 230 1 51 101 151 201 251 150 201 Полутоновые значения пиксела Кадры Рис. 1 Таким образом, текущее значение пиксела фонового изображения следует вычислять по формуле (4), если стабильность его значения проверяется условия- ми (8), (9), и оставлять неизменным (равным значению на предыдущей итерации) в противном случае. Поскольку изначальное значение фонового пиксела не зада- но, то оно вычисляется при первом выполнении условий (8), (9), и на это может потребоваться некоторое время. 2.3.2. Определение пикселов, в которых произошли изменения. Следую- щий этап обработки входного изображения — определение пикселов, соответст- вующих областям, в которых происходит движение. Критерий отнесения пиксе- лов к таким областям основывается на анализе изображения, полученного путем применения медианного фильтра к изображению, пикселы которого представляют собой абсолютные отклонения значений входного и фонового изображений. Зна- чения этих пикселов должны превышать порог .t Опишем один из способов вы- бора .t Пусть },1,0,:{  NjjzzZ },,1,,1,),({ hjwiZyxII ji  (10) I — анализируемое полутоновое изображение размера w×h с N градациями серого цвета. Рассмотрим нормализованную гистограмму }1,1:]1,0[{  NjHH j этого изображения, )),,(,( 1 ,1 ,1 yxIje wh H hy wx j     (11)        .,0 ,,1 ),( ba ba bae (12) Практика применения обсуждаемого алгоритма показала, что значение t следует выбирать в соответствии с выражением ,min it Ti   (13) 124 ISSN 0572-2691 где },1,,:{  NljkHZlT j 0 ≤ k ≤1, — некоторый порог. При таком вы- боре пороговую фильтрацию проходят те значения изображения I, которые рас- положены в максимально широкой (но не содержащей значений, превышаю- щих k) правой части гистограммы H. Им соответствуют наиболее отличающиеся пикселы входного и фонового изображений. Действительно, поскольку в большей части пикселов входного изображения изменений не происходит, то эти пикселы мало отличаются от фонового изобра- жения. Поэтому основная часть пикселов для изображения-разности сосредоточе- на в малых значениях. Таким образом, выбор подходящего порогового значения позволит избавиться от них. 3. Результаты тестирования Работа алгоритма проверена на нескольких видеофайлах с разными размера- ми, типом и скоростью движущихся объектов, с разным качеством изображения. Во всех тестах использованы одинаковые значения параметров: высота трубки h5, длина трубки l5, k0,025 (таблица). Таблица Файл PETS2001\camera1 People_counting_test HighwayII_raw Разрешение 768×576 384×288 320×240 Размеры объектов Мелкие Большие Мелкие Скорость движения объектов Низкая Средняя Высокая Уровень шума Низкий Большой Средний На тесте с файлом из базы PETS2001 (рис. 2, PETS2001\DATASET1\ TRAINING\camera1.mov, 245, 940, 1040, 1382 кадры) алгоритмом достаточно точно обнаружено движение пешеходов и автомобилей, а также отнесены к фоно- вому изображению остановившиеся автомобили. К ошибкам алгоритма можно отнести кратковременное обнаружение области прежней стоянки автомобиля по- сле того, как автомобиль начал движение. Рис. 2 При обработке файла people_counting_test (рис. 3, People counting test, 39, 63, 490, 517 кадры), имеющего низкое качество изображений, алгоритм также обна- ружил и разграничил большие движущиеся объекты, корректно обновил фоновое изображение при убирании предметов со сцены (кадры 490, 517). В видеофайле HighwayII_raw (рис. 4, http://cvrr.ucsd.edu_aton_shadow/ HighwayII_raw.AVI, 32, 120, 179, 482 кадры) снято интенсивное движение транс- Проблемы управления и информатики, 2008, № 3 125 порта. На кадре 32 по сравнению с кадром 120 видны вытянутые в направлении движения участки. Это значит, что области стабильности для пикселов этих про- долговатых участков были обнаружены только к 120-му кадру, что связано с на- личием движущихся объектов на первых кадрах. После 120-го кадра алгоритм продолжил свою работу корректно. Рис. 3 Рис. 4 К недостаткам алгоритма относятся его неудовлетворительная работа на некоторых цветных изображениях после их приведения к полутоновому виду (те- ряется различимость движущегося объекта и фонового изображения), а также обнаружение вместе с реально движущимися объектами их теней. Заключение Предложен алгоритм построения фонового изображения на основе интер- валов стабильности для случаев, когда обрабатываемые изображения унимо- дальны. Алгоритм основан на блочных вычислениях, что позволяет использо- вать оптимизированные библиотеки по обработке изображений и снизить вре- менне затраты. Результаты тестирования показали высокую скорость и в целом корректную работу алгоритма в различных условиях. Цель дальнейшей разработки — динамическое определение оптимальных параметров длины и толщины трубки стабильности, а также усовершенствование алгоритма для от- слеживания внезапных изменений освещения, разрешения ситуаций, в которых объекты были предварительно отнесены к фоновому изображению, но начинают двигаться. 126 ISSN 0572-2691 А.В. Прокофієв ШВИДКИЙ АЛГОРИТМ ПОБУДОВИ ФОНОВОГО ЗОБРАЖЕННЯ НА ОСНОВІ ІНТЕРВАЛІВ СТАБІЛЬНОСТІ Запропоновано швидкий алгоритм попіксельної побудови фонового зображен- ня для унімодальних сцен. Алгоритми на основі усереднення останніх значень та на основі композиції гауссівських щільностей удосконалено шляхом додання процедури перевірки на стабільність останніх значень піксела, що дозволило зменшити кількість обчислень та збільшити продуктивність. A.V. Prokofiyev FAST BACKGROUND MODELING ALGORITHM BASED ON STABILITY INTERVALS A fast algorithm of per pixel background modeling for unimodal scenes is proposed. Ideas of recent values average algorithm and mixture of Gaussian densities algorithm were improved with the idea of stability checking for recent pixel values. As conse- quence an amount of calculation was reduced and a better performance was achieved. 1. Javed O., Shafique K., Shah M. A hierarchical approach to robust background subtraction using color and gradient information // IEEE Workshop on Motion and Video Computing. — 2002. — P. 22–27. 2. Stauffer C., Grimson W.E.L. Learning patterns of activity using real-time tracking // IEEE Trans. on PAMI. — 2000. — 22(8). — P. 747–757. 3. Yilmaz A., Javed O., Shah M. Object tracking: a survey // ACM Computing Surveys. — 2006. — 38. — P. 4–13. 4. Rittscher J., Kato J., Joga S., Blake A. A probabilistic background model for tracking // Proc. Eu- ropean Conf. on Computer Vision. Dublin, Ireland. — 2000. — 2. — P. 336–350. 5. Elgammal A., Duraiswami R., Harwood D., Davis L.S. Background and foreground modeling using nonparametric kernel density estimation for visual surveillance // Proc. of the IEEE. — 2002. — 90, N 7. — P. 1151–1163. 6. Mittal A., Paragios N. Motion-based background subtraction using adaptive kernel density estimation // Proc. IEEE Conf. on Computer Vision and Pattern Recognition. Washington. — 2004. — 2. — P. 302–309. Получено 16.01.2008 Статья представлена к публикации членом редколлегии Ф.Г. Гаращенко.

Быстрый алгоритм построения фонового изображения на основе интервалов стабильности

Репозитарії

Схожі ресурси