На правах рукописи

Малистов Алексей Сергеевич

Разработка и анализ информационных алгоритмов

повышения эффективности визуализации и достоверности

автоматической регистрации динамических объектов

компьютерными видеосистемами

05.13.01 – Системный анализ, управление и обработка информации

(в области приборостроения)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 2011

Работа выполнена на Государственном унитарном предприятии Научнопроизводственный центр Электронные вычислительно-информационные системы

Научный руководитель: доктор технических наук Петричкович Ярослав Ярославович

Официальные оппоненты: доктор физико-математических наук Рычагов Михаил Николаевич кандидат технических наук Панасенко Сергей Петрович Ведушая огранизация: ЗАО Московский научно-исследовательский телевизионный институт

Защита состоится 15 марта 2011 г. в 14 часов 30 минут в аудитории на заседании диссертационного совета Д 212.134.02 Московского государственного института электронной техники (технического университета) по адресу:

124498, Москва, г. Зеленоград, проезд 4806, д. 5, МИЭТ (ТУ).

С диссертацией можно ознакомиться в научной библиотеке Московского государственного института электронной техники (технического университета) Атореферат разослан 02 февраля 2011 года.

Ученый секретарь диссертационного совета Д 212.134. доктор технических наук Гуреев А. В.

Общая характеристика работы

Актуальность проблемы. Одним из наиболее эффективных средств сбора информации являются компьютерные системы видеонаблюдения. Почти до конца XX века все существующие системы были ориентированы на работу оператора, который не только принимает решения, но и обязан внимательно следить за происходящим в поле зрение видеокамер. С увеличением числа видеодатчиков, число операторов таких систем растёт пропорционально.

Система видеонаблюдения, соответствующая современным требованиям, обязана быть более автоматизированной. В процессе поиска система должна выбрать из всего имеющего объёма информации наиболее интересные для аналитика данные и представить их в удобном для дальнейшего анализа виде. Для удобства пользователя представление результатов должно быть интуитивно понятным, а качество результатов достаточным для работы аналитика. Такая система должна обладать интеллектуальными функциями анализа изображений, распознавания объектов и ситуаций.

Достигнутый техническим прогрессом к началу XXI века уровень производительности ЭВМ существенно оживил область интеллектуальной обработки видеоинформации компьютерными системами. Большой вклад в область информационной обработки, классификации и распознавания видеосигналов внесли известные учёные, работающие в России и за рубежом: Ю. И. Журавлев, В.Н.Вапник, А.И.Галушкин, Л.П.Ярославский, B.D. Lukas, T.Kanade, R.Collins, A.Lipton, C.Stauer, W.E.L.Grimson и другие.

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

Широкое распространение методов распознавания объясняется тем, что для их применения требуется значительно меньшая точность описания исследуемых явлений, чем при применении других математических методов. ЭВМ позволяют математикам проводить экспериментальные исследования. Сначала изучается реальная задача распознавания, выдвигается гипотеза и затем проводится эксперимент, который подтверждает или опровергает гипотезу. Строгие математические обоснования в таких случаях часто не проводятся. Это привело к построению большого числа экспериментальных (эвристических) алгоритмов распознавания, не достаточно обоснованных, но дающих в некоторых ситуациях удовлетворительный результат. Теоретическое обоснование алгоритмов позволит улучшить их показатели, что непосредственно повлияет на эффективность визуализации динамических объектов, и поэтому исследования и разработки в этом направлении являются актуальными.

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

Задачи работы. Для достижения поставленной цели необходимо решить следующие задачи:

1. Провести теоретический анализ метода вычитания фона и влияния коэффициентов этого метода на ошибки первого и второго рода, установить предельные значения указанных коэффициентов.

2. Разработать эффективный алгоритм, позволяющий осуществлять выбор коэффициентов метода вычитания фона в автоматическом режиме для минимизации ошибок первого и второго рода.

3. Разработать алгоритмы для выявления ситуационного поведения динамических объектов: обнаружение движения в поле сил тяготения по параболе с учётом пропуска кадров, распознавание остановки объекта, распознавание траекторий объектов, движущихся в запрещённых направлениях.

4. Обобщить задачу о максимальном взвешенном паросочетании в двудольном графе на случай множественного назначения и разработать эффективный алгоритм сопоставления объектов на различных кадрах при условии разделения некоторых объектов на части.

5. Исследовать зависимость результатов работы алгоритмов компенсации дрожания камеры от плотности движения в сцене наблюдения и разработать устойчивый алгоритм стабилизации изображения с учётом движения объектов в кадре.

6. Разработать быстрый алгоритм выравнивания яркости в случае локального изменении освещённости наблюдаемой сцены.

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

Научная новизна состоит в разработке, анализе и применении в компьютерных видеосистемах алгоритмов повышения эффективности визуализации и достоверности автоматической регистрации динамических объектов. При выполнении диссертационной работы получены следующие новые научные результаты:

1. Впервые теоретически получены предельные значения коэффициента обновления в методе вычитания фона. Для повышения достоверности автоматической регистрации динамических объектов предложен модифицированный алгоритм вычитания фона, который использует два различных коэффициента (коэффициент обновления и коэффициент порога) вместо одного.

2. Разработан алгоритм пороговой компенсации, выбирающий коэффициент обновления в методе вычитания фона таким образом, чтобы ошибка первого рода (ложные срабатывания), обусловленная шумами изображения (квантовыми, дробовыми, теневыми шумами, током смещения, шумом считывания, дискретизацией) была не выше 0,003% в час, а также минимизирующий ошибку второго рода (пропуск объектов) при фиксированной ошибке первого рода.

3. Предложен параллельно-конвейерный алгоритм обнаружения движения, который сокращает время обработки одного кадра в 3–4 раза и при этом не уменьшает достоверности обнаружения динамических объектов.

4. Для повышения эффективности визуализации разработаны алгоритмы выявления ситуационного поведения динамических объектов: обнаружение динамических объектов, двигающихся в поле сил тяготения; распознавание остановки объекта; распознавание траекторий объектов, движущихся в запрещённых направлениях.

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

6. Разработан устойчивый алгоритм стабилизации изображения с учётом движения объектов в кадре.

7. Разработан быстрый алгоритм выравнивания яркости в случае локального изменении освещённости.

Практическая значимость. Разработанные в диссертации теоретические расчёты, способы и алгоритмы используются в семействе компьютерных видеосистем: Orwell2k, Orwell2k-Barrier, Orwell2k-Cinema и др., разработанных на предприятии ГУП НПЦ ЭЛВИС.

Используемый в системах Orwell2k и Orwell2k-Cinema параллельно-конвейерный алгоритм позволил сократить время обработки одного кадра в 3– раза, что, в свою очередь, позволило сократить число используемых в системе серверов в 3 раза. Для ЭВМ с процессором Intel Core 2 Duo, 2,66 ГГц, сокращение составило с 8 мс до 2–3 мс на кадр размера 352288. Указанное улучшение производительности распространяется на ЭВМ любой конфигурации.

Алгоритм пороговой компенсации снижает ошибку первого рода (ложные срабатывания), обусловленную шумами яркости изображения (квантовыми, дробовыми, теневыми шумами, током смещения, шумом считывания, дискретизацией) до значения не выше 0,003% в час, а также минимизирует ошибку второго рода (пропуск объектов) при фиксированной ошибке первого рода.

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

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

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

Внедрение результатов. Результаты диссертационной работы внедрены в компьютерной видеосистеме Orwell2k. Система введена в эксплуатацию на периметре и в зоне авиационной деятельности центра деловой авиации аэропорта Домодедово (система РАЯЖ 46652.001-ОС.ПЗ), при строительстве территории 1-го пускового комплекса II очереди особой экономической зоны ППТ Липецк (проект Система видеонаблюдения СПО 105-КТСО-СТН, РАЯЖ 46352.003) и на других объектах. Применение систем подтверждено актами о внедрении.

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

На защиту выносятся:

1. Вывод предельных значений коэффициента обновления в методе вычитания фона.

2. Алгоритм пороговой компенсации, выбирающий коэффициент обновления в методе вычитания фона таким образом, чтобы ошибка первого рода (ложные срабатывания), обусловленная шумами яркости изображения была не выше 0,003% в час, а также минимизирующий ошибку второго рода (пропуск объектов) при фиксированной ошибке первого рода.

3. Параллельно-конвейерный алгоритм обнаружения движения, сокращающий время обработки одного кадра в 3–4 раза.

4. Алгоритмы распознавания ситуационного поведения динамических объектов: обнаружение динамических объектов, двигающихся в поле сил тяготения;

распознавание остановки объекта; распознавание траекторий объектов, движущихся в запрещённых направлениях.

5. Модифицированный алгоритм Хатчинсона для генерации коллекции ограниченно растущих строк a1 a2... an, позволяющий пробегать лишь по ограниченным разбиениям.

6. Сведение задачи сопоставления объектов на различных кадрах при условии разделения некоторых объектов на части, к ограниченной задаче о максимальном взвешенном паросочетании (ОЗМВП). Алгоритм решения ОЗМВП для случая небольших входных данных, использующий модифицированный алгоритм Хатчинсона. Три приближенных алгоритма для общего случая.

7. Алгоритм стабилизации с учётом движения объектов в кадре.

8. Алгоритм выравнивания яркости при локальном изменении освещённости.

Апробация работы. Результаты диссертационной работы докладывались на XLVII и XLVIII научной конференции МФТИ, а также на XV, XVI и XVII конференциях молодых учёных, аспирантов и студентов по современным проблемам машиноведения в институте машиноведения им. А.А. Благонравова РАН. Компьютерные видеосистемы семейства Orwell2k, в которых внедрены результаты работы, демонстрировались на 13 выставках.

Публикации. Основное содержание диссертации отражено в 23 опубликованных работах, в том числе 5 статьях в журналах, входящих в перечень, утверждённый ВАК. Без соавторов опубликовано 9 статей. В соавторстве получены патента на изобретения, 3 свидетельства на полезную модель и 1 свидетельство о регистрации программы.

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка основных обозначений, списка литературы и приложений. Работа содержит 240 страниц, из них 177 страниц основного текста, 43 рисунка и 13 таблиц на 27 страницах, список литературы из 107 наименований и приложения на 16 страницах.

Во введении даётся обоснование актуальности темы диссертации, формулируются основные цели и задачи работы, перечисляются элементы научной новизны и практической значимости, даётся краткое содержание глав работы.

В первой главе проведён обзор современных методов повышения эффективности анализа видеоизображений статических и динамических объектов. Процесс выделения подвижных (динамических) объектов состоит из трёх основных этапов: предварительная стабилизация параметров изображения, выделение движущихся точек и/или областей, сопоставление движущихся точек и областей между кадрами. Выделение движущихся точек и областей производится алгоритмами обнаружения движения. Можно выделить четыре основных подхода: разность яркости соседних кадров (temporal dierence), вычисление оптического потока (optic ow), прослеживание особенностей (feature tracking) изображения и метод вычитания фона (background substraction). Разность яркости соседних кадров обычно вычисляется по двум или трём соседним кадрам и редко используется как самостоятельный инструмент из-за недостаточно качественного результата, получаемого на выходе алгоритма.

Задача вычисления оптического потока состоит в том, чтобы оценить сдвиг изображения в каждой точке по имеющимся данным о яркости пикселов на последовательных кадрах. Среди широко известных методов можно выделить три основные группы: дифференциальные методы, расчёт фазовой корреляции и методы, основанные на сопоставлении окрестностей.

Основой для дифференциальных методов послужили работы Хорна (Horn) и Шунка (Schunck), а также Лукаса (Bruce Lucas) и Канаде (Takeo Kanade). Методы называются дифференциальными благодаря использованию в них численных приближений пространственно-временных частных производных сигналов изображений. Если изображение в некоторой окрестности в момент времени t сдвинулось на некоторый вектор v = (vx, vy )T по сравнению со временем 0, тогда I(r, t) = I(r vt, 0). Основная идея дифференциальных методов заключается в том, чтобы разложить правую часть уравнения в ряд Тейлора:

Алгоритм Хорна-Шунка, предложенный в 1981 году, оценивает оптический поток, используя понятие глобальной функции энергии:

где D = [0, w] [0, h] R2 область изображения, > 0 параметр регуляризации, не зависящий от x и y. Оптический поток определяется как векторное поле v(r), минимизирующее функционал (2). Экстремум энергии можно найти, решая уравнения Эйлера–Лагранжа. Для больших изображений (больше 105 пикселов) алгоритм Хорна-Шунка очень трудоёмкий. Его времення сложа ность имеет порядок (SN), где S = wh количество пикселов в изображении, N количество итераций метода Якоби или Гаусса–Зейделя. Алгоритм Лукаса– Канаде, предложенный также в 1981 году, может работать c локальными окрестностями. Оптический поток определяется отдельно в окрестности каждой точки как вектор v, минимизирующей взвешенную сумму квадратов невязки уравнений (1) для точек окрестности: r w (r) I(r, t) · v + It(r, t) min, где w (r) весовая функция, обычно имеющая бльшие значение к центру окресто ности. Решение может быть найдено методом наименьших квадратов:

где сумма вычисляется по точкам окрестности. Алгоритм Лукаса–Канаде трудоёмок по времени, времення сложность имеет порядок (S · ||), где S размер изображения, || размер окрестности.

Методы, основанные на сравнении окрестностей определяют скорость v как смещение одного изображения относительно другого, дающее минимум расстояния между изображениями в некоторой окрестности исследуемой точки. Расстояние может определяться, например, как минимальная сумма квадратов разностей яркости E = r (I2 (r + v) I1 (r))2 в окрестности. Полный перебор для каждого из M потенциально возможных смещений требует (S||M ) операций. При использовании так называемой гауссовой пирамиды алгоритмическая сложность имеет порядок (S|| log M ).

Прослеживание особенностей изображения один из наиболее качественных методов обнаружения движения, устойчивый к глобальным изменениям яркости, но и самый затратный по времени. Практически любой алгоритм прослеживания особенностей состоит из 2 этапов: выделение особенностей (feature detection) и сопоставление особенностей на различных кадрах (feature matching).

Наиболее часто в литературе встречается поиск точечных особенностей. В году в своей работе Moravec предложил считать особыми те точки изображения, для окрестности которых автокорреляционная функция имеет большие значения для всех смещений (x, y). Кроме особых точек в качестве особенностей изображения также широко используются границы и особые связные области.

Метод вычитания фона предполагает, что если для пиксела с координатами (x, y) среднее значение яркости в случае, когда этот пиксел является неподвижным, известно и равно B(x, y), можно выяснить с некоторой достоверностью, принадлежит ли этот пиксел фону или какому-то подвижному объекту. Пусть интенсивность пиксела (x, y) на n-ом кадре равна In (x, y). Точка считается подвижной, если |In (x, y) B(x, y)| T, где T некоторый порог движения. Так как интенсивность фона B(x, y) заранее неизвестна, то наибольшее распространение получил метод вычитания фона, в котором используется адаптивное накопление средней интенсивности. Для каждого пиксела (x, y) мы храним в памяти так называемое скользящее среднее интенсивности Bn (x, y) и условную оценку шума Tn (x, y). Точка считается подвижной, если |In (x, y) Bn1 (x, y)| d · Tn1 (x, y), где Tn(x, y) оценка шума на n-ом кадре.

Метод вычитания фона наиболее распространён из-за его высокой производительности: количество операций (S), где S количество пикселов изображения. Однако он имеет ряд недостатков: отсутствие теоретического обоснования выбора коэффициентов обновления и порога, неустойчивая работа при вибрации камеры и при изменении освещённости. Для компенсации вибрации камеры необходимо использовать алгоритмы стабилизации видеоизображений.

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

Во второй главе проведён теоретический анализ метода вычитания фона, разработана его модификация, позволяющая снизить ошибки I и II рода, предложен параллельно-конвейерный алгоритм, сокращающий время работы метода вычитания фона в 3–4 раза, разработаны алгоритмы распознавания ситуационного поведения динамических объектов.

Для каждого пиксела возможно одно из двух: точка (x, y) принадлежит стационарному фону (гипотеза H0 ) или движущемуся объекту (гипотеза H1 ). Любой алгоритм обнаружения движения A должен определить некоторую индикаторную функцию mn (x, y): если mn (x, y) = 0, значит, согласно критерию алгоритма A, принята гипотеза H0, если mn (x, y) = 1, то H1. Пусть In (x, y) интенсивность пиксела на n-ом кадре. Для определения mn (x, y) метод вычитания фона хранит так называемое скользящее среднее интенсивности Bn (x, y):

где (0, 1) величина, характеризующая степень обновления. На первом кадре фон совпадает с изображением, а на каждом новом кадре Bn (x, y) изменяется по формуле (3). Для оценки уровня шума вводится изменяющийся порог T0 (x, y) = T0, Tn (x, y) = (1 T )Tn1 (x, y) + T In (x, y) Bn1 (x, y), (4) где T (0, 1) коэффициент обновления порога, а T0 начальная завышенная оценка шума. В общем случае = T. Индикаторная функция mn(x, y) определяется следующим образом:

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

Пусть {an } последовательность одинаково распределённых независиn= мых случайных величин с математическим ожиданием M an = m и дисперсией Dan = 2. Если {bn } последовательность, определённая как скользящее среднее последовательности an с коэффициентом обновления (0, 1): b0 = = a0, bn = (1 )bn1 + an, то верно следующее: 1) математическое ожидание M (bn ) = m для любых n, 2) последовательность дисперсий bn сходится:

lim D(bn ) = (2), 3) если an N (m, 2), то bn N (m, 2/(2 )).

Пусть последовательность {tn } задана следующим образом: t0 = T0, tn = = (1)tn1 +|an bn1 |, где (0, 1). В работе показано, что µ = lim M tn = = |x|g(x) dx, где g(x) плотность распределения случайной величины n = получаем µ 2/. Следовательно последовательность {tn } в пределе оценивает среднеквадратическое отклонение шума.

Описанная идеальная модель не работает, если в последовательности In (x, y) встречаются значения интенсивностей подвижных точек. Чтобы избежать этого, во многих работах изменяют значения B(x, y) и T (x, y) только для тех точек, которые мы определили как неподвижные (r (x, y)):

Таким образом, коэффициент d имеет двойную функциональность. Во-первых, он используется в алгоритме вычитания фона (5), который определяет какая из гипотез верна: точка подвижная (H1 ) или нет (H0 ), тем самым влияя на ошибки первого и второго рода. Во-вторых, коэффициент d влияет на оценку шума в (6). Для большей гибкости при использовании алгоритма вычитания фона в работе предлагается ввести новый коэффициент k, который будет использоваться при оценке шума, а коэффициент d по-прежнему будет влиять на выбор той или иной гипотезы подвижности точек. Их можно выбирать независимо друг от друга, что позволяет регулировать алгоритм вычисление оценки шума, а также управлять ошибками первого и второго рода отдельно.

Если точка r принадлежит фону и при этом значение интенсивности отклонилось от накопленного значения более, чем на k · Tn1 (r), то для неё mn(r) = 1, а, значит, ложно принята гипотеза H1 (ошибка 1-го рода, ложная тревога). Такие точки не вносят вклад в оценку порога, и так как отбрасываются бльшие о значения, это понижает величину Tn+n (r) по сравнению с Tn (r) через некоторое время n. В работе показано, что уменьшение порога можно оценить Здесь h флуктуация, вызванная отклонением tn от µ. Размер этой флуктуации можно оценить по дисперсии случайной величины tn. Функцию h(y), которая позволяет найти новую оценку, будем называть функцией оценки шума. В диссертации определены некоторые полезные свойства функции h(y):

1) y > 0: 0 h(y) y; 2) h(y) не убывает; 3) h(y) ограничена; 4) lim h(y) = 0.

Для k > 0 рассмотрим функцию hk (x) = h(kx). Функция hk (x) получается из h(kx) сжатием вдоль оси Ox, поэтому она также определена на (0, +), ограничена и всюду не убывает. Новое значение оценки из формулы (7) выражается с помощью hk (x) следующим образом: µ = hk (µ) + h. Рассмотрим рекурсивную последовательность {µn }, в которой каждый следующий член выражается через предыдущий по формуле µn = hk (µn1 ) = h(kµn1 ). Так как hk (x) ограничена, то последовательность {µn } также ограничена. Кроn= ме того, последовательность {µn }n=1 монотонна, так как функция hk (x) неубыy Рисунок 1. Сходимость {µn } к неподвижn= то последовательность возрастает и сходится к xi+1. Такие интервалы будем называть положительными. Если hk (µ1 ) < µ1, то последовательность будет убывать и сходиться к xi (отрицательные интервалы). Неподвижные точки называются устойчивыми узлами, если выражение (hk (x) x) меняет знак с положительного на отрицательный в этих точках, то есть 0 < hk (x) < 1. Для h(y) в работе доказаны следующие леммы.

Лемма 2.1 Последний интервал (xk, +) всегда отрицательный.

Лемма 2.2 Если существует положительный интервал, тогда существует устойчивый узел.

Лемма 2.3 Если k 1, то все интервалы отрицательные.

Если учесть флуктуации µn = hk (µn1 )+hn, то на каждом шаге, кроме отображения hk (µn1 ) мы смещаем положение µn на случайную величину hn, тем большую, чем больше дисперсия tn. Даже вблизи неподвижных точек значение µn меняется. Таким образом, с учётом флуктуаций, все возможные варианты сходимости указаны в таблице 1.

Вырождение c неус- Уравнение (8) среди решений имеет только неустойчивые узлы. С тойчивыми узлами. учётом флуктуаций lim µn = 0.

Решения уравнения (8) включают устойчивые узлы, но несколько Частичное вырожде- первых интервалов отрицательные. Сходимость к устойчивому ние. узлу возможна только при флуктуациях, меньших величины Регулярный режим Уравнение (8) имеет единственное решение в устойчивом узле.

4. с одним устойчивым Всего два интервала, первый из которых отрицательный. Сходиузлом. мость возможна только к единственному устойчивому узлу.

Регулярный режим с Решения уравнения (8) включают устойчивые узлы, и нескольнесколькими устой- ко первых интервалов положительные. Сходимость возможна к чивыми узлами. нескольким устойчивым узлам, что влечёт неопределённость.

Если в кадре нет движения и величина n распределена нормально N (0, 2 ), в формулу (7) необходимо подставить функцию g Вырождение наблюдается при k 2. Для k > 2 получаем регулярный режим с одним устойчивым узлом; при k > 4 пересечение графиков происходит в точке, близкой к пределу hnorm (x) на бесконечности, то есть при 2/ 0,8.

Если в кадре присутствует движение с частотой p, то g(x) определяется следующим образом: g (p) (x) = (1 p) · g norm (x) + p · g unif (x), где g unif (x) плотность функции распределения для движущихся точек. В случае смешанного распределения, функция оценки смешанного шума h(y) из (7) будет вычисляться следующим образом: y y Лемма 2.4 Для функции оценки смешанного шума верно двойное неравенство: min hnorm (y), hunif (y) h(p) (y) max hnorm (y), hunif (y).

2. 0. для k = 3,5 и для различных значений верояткоторый оценивает шум яркости фононости p движения.

точек, а шум яркости подвижных точек, что не позволит нам классифицировать точки на подвижные и неподвижные. Величина частоты движения p0 (k, I/), с которой начинается регулярный режим с несколькими устойчивыми узлами, зависит от выбираемого значения k. И наоборот, при данных значениях I/ и p0, существует минимальная величина k = k0 (p0, I/), с которой начинается регулярный режим с несколькими устойчивыми узлами.

Линейный коэффициент порога d оказывает непосредственное влияние на ошибки первого и второго рода распознавания подвижности пикселов, что в дальнейшем сказывается на достоверности обнаружения динамических объектов. Значение d необходимо подобрать таким образом, чтобы точки, яркости которых отличаются лишь на величину шума, не были признаны движимыми.

Обычно выбирают фиксированное значение d. Однако, если распределение шума не совпадает с нормальным, то выбирать постоянное значение d нельзя.

Будем называть точки, ложно определённые как движимые, шумовыми точками. Существование небольшого количества шумовых точек не является критичным для алгоритма вычитания фона: они будут разбросаны по изображению и мы сможем определить их как шум, так как площадь областей будет 1–2 пиксела. Если же шумовых точек много, то повышается вероятность, что несколько точек окажутся рядом и могут быть ложно определены как движущаяся область. В диссертации оценивается вероятность появления областей из шумовых точек площадью не менее 4 пикселов. Доказывается, что если доля шумовых точек равна p (0, 1), то для вероятности события P, что хотя бы одна группа из 4 рядом расположенных точек будет ложно считаться подвижной, справедливо двойное неравенство 1 Np4 1 (N/4 1)N · p8 P kNp4, где N число точек изображения. Например, для изображения 352288 и плотности шумовых точек 1%, получаем: 0,000253 < P < 0,0193. При потоке видео 25 кадров в секунду мы получим, что в течение часа вероятность возникновения ложных областей на пяти кадрах подряд не выше 2,3 · 105. Если плотность шумовых точек возрастает до 5%, то P > 0,14, что уже недопустимо. Оценить шум можно, вычислив сумму площадей всех областей, площадь которых не превышает установленный порог в 4–8 точек. Каждый раз, оценивая фактическую долю шума на текущем кадре, следует изменять значение коэффициента таким образом, чтобы на следующих кадрах поддерживать долю шумовых точек на уровне 1–2%.

В диссертационной работе предложены способы обнаружения динамических объектов, которые появляются в зоне обзора камеры и двигаются под действием только гравитационных сил. Их траектория проецируется на ПЗС-матрицу в виде кривой второго порядка. Если вертикальная ось ПЗС-матрицы расположена перпендикулярно поверхности земли, то точки центра масс объекта будут проецироваться на параболу. Проверить гипотезу, лежит ли траектория движения объекта на параболе, можно, приблизив эту траекторию некоторой параболой методом наименьших квадратов. Чтобы повысить достоверность обнаружения, используется тот факт, что объект имеет постоянную скорость движения вдоль горизонтальной оси. Устройство видеозахвата получает кадры с постоянной периодичностью, поэтому время каждого кадра ti = t0 +ki ·t, где t промежуток между съемками соседних кадров (обычно около 40 мс), t0 момент съемки нулевого кадра, ki N {0}. Показано, что если некоторые кадры пропущены, то восстановить значения ki и ti можно по формуле ki = ki1 + хi /x + 0,5, где x = MEDIAN(xi ) i=0. Оценить линейность горизонтальной скорости предлагается по коэффициенту корреляции между хi и ti.

Автором диссертации разработаны способы обнаружения динамических объектов, которые двигались в зоне обзора камеры, а затем остановились на определённое время. Для обнаружения остановки можно оценить дисперсию положения геометрического центра масс объекта по последним n кадрам, где n параметр алгоритма. Такой способ не работает, если положение центра масс объекта определяется не очень точно. Рассмотрим траекторию объекта как последовательность прямоугольных рамок Ri, i = n0, nk с вертикальными и горизонтальными сторонами: левая i = left(Ri ), правая ri = right(Ri ), верхняя ti = top(Ri ) и нижняя bi = bottom(Ri ). Здесь n0 и nk ограничивают период анализа, который зависит от скоростей движущихся объектов и лежит в промежутке от 5 секунд до 10–20 минут. В системах реального времени nk обычно совпадает с последним кадром. Упорядочим все левые стороны i рамок по возрастанию и возьмем -квантиль указанного ряда и (1 )-квантиль +.

Аналогичную операцию проведем для верхней (t, t ), нижней (b, b ) и правой (t, t+ ) границы рамок. Разница между и + показывает насколько сильно изменялась левая граница рамки объекта в течение анализируемого промежутка времени. Рассмотрим рамку S1 c левой границей +, правой r, верней t+, нижней b и прямоугольную рамку S2 с соответствующими сторонами, r, t, b+. Если объект не движется, то в идеальном случае, когда нет шума, рамка S2 должна совпадать с рамкой S1. Площади рамок связаны соотношением S1 S2. Значение отношения = S1 /S2 принадлежит отрезку [0,1]. Чем ближе к единице, тем вероятнее, что объект не движется. Если близка к нулю, то объект находится в движении: его смещение за анализируемый период сопоставимо или больше размеров самого объекта. Характеристику предлагается рассматривать как признак для распознавания остановки объекта.

В диссертации разработаны способы обнаружения динамических объектов, которые двигались в зоне обзора камеры в запрещённых направлениях. Для этого на изображении вводится векторное поле запрещённых направлений E(x, y):

кадр делится на несколько частей и для каждой задаётся запрещённое направление. Пусть r(t) траектория движения некоторого объекта O. Для объекта O в работе определяется понятие совершённой работы A: An = n E(ri )·(ri ri1 ).

Возрастание An означает движение в запрещённом направлении, убывание, наоборот, показывает, что объект двигается по разрешённой траектории. Чтобы определить степень увеличения An, вводится понятие максимальной разности за промежуток от 1 до n: n = An Mn, где Mn = mini=0,n1 Ai. Для ускорения вычислений минимум Mn корректируется на каждом шаге. Если n превысит установленный порог, значит, объект проделал путь в запрещённом направлении, достаточный для выдачи сигнала тревоги. В работе также обобщён данный алгоритм на случай нескольких запрещённых направлений в одной точке. Если задано k векторных полей запрещённых направлений Ej (x, y), j = 1, k, то формула расчёта работы будет следующей: An = n maxj=1,k Ej (ri ) · (ri ri1 ).

Третья глава посвящена вопросам построения траекторий динамических объектов и алгоритмам предварительной обработки видеопотока для стабилизации параметров изображения. Впервые идея применить задачу о максимальном взвешенном паросочетании (ЗМВП) для построения траекторий особых точек была предложена в 1996 году в работе Collins и др. В диссертации предлагается обобщить и развить задачу продолжения траекторий на случай с областями движения и динамическими объектами. Область движения состоит из близких по расстоянию пикселов, принадлежит конкретному кадру t = 1, 2,..., характеризуется положением на этом кадре, формой и площадью, которые определяются расположением движущихся точек, входящих в рассматриваемую область. Множество областей движения мы будем обозначать R = {rtk }, k = 1, 2,..., m(t) номер области, m(t) количество областей в кадре t. Подмножество областей движения, которые обнаружены на кадре с номером t, обозначим Rt.

Наша цель соединить области движения на разных кадрах таким образом, чтобы они образовали оптимальное множество вершинно-независимых путей (траекторий). Траектория это последовательность областей rtnkn, n = 1, N, такая, что ti < tj для i < j. Момент времени t1 называется моментом появY. Cheng, V. Wu, R. Collins, A. Hanson and E. Riseman. “Maximum-Weight Bipartite Matching Technique and Its Application in Image Feature Matching,” 1996, Proc. SPIE Visual Comm. and Image Processing ления объекта, момент времени tN + 1 моментом исчезновения. Оптимальность построения траекторий можно определить, если сформулировать задачу в терминах теории графов. Будем считать, что в любой момент времени t уже построено некоторое множество Ot = {O1, O2,... O|Ot | } траекторий, которые назовём объектами. Объекты представляют из себя последовательность областей движения на кадрах, которые предшествуют текущему кадру t. Определим неориентированный взвешенный двудольный граф G = (V, E) следующим образом: V = Ot Rt, E = {eij }. Каждое ребро eij соединяет вершины Oi Ot и rtj Rt. Вес каждого ребра wij = w(eij ) определяет меру схожести объекта с областью нового кадра. Задача однозначного назначения это задача построения паросочетания с максимальным суммарным весом в графе G. Решение задачи сопоставит объектам текущего кадра новые области движения, при этом каждому объекту будет сопоставлено не более одной области движения, а каждой области движения сопоставлено не более одного объекта. Объект Ot будет временно пропавшим, если он не сопоставлен ни одной из областей движения.

Задача однозначного назначения не учитывает ошибки некорректного выделения областей движения в случае, когда эти области разделяются на части.

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

Число всех возможных непустых подмножеств конечного множества размера n равно 2n 1. Однако, не все комбинации допустимы. Пусть G = (Rt, E) неориентированный граф, вершинами которого являются области движения Rt, а ребра соединяют те области, которые находятся на достаточно близком расстоянии (меньше заданного алгоритмом порога). Показано, что вместо генерации всех подмножеств множества Rt можно составлять связные подграфы для изолированных подграфов G. Мы хотим построить оптимальное соответствие между сложными областями и сложными объектами. Однако, не каждое даже одB нозначное соответствие может считаться удачным:

Решение классической задачи о максимальном взвешенном паросочетании на двудольном графе, в коРисунок 3. Нетранзитивность отношения несовместности. тором в левую часть входят сложные объекты, в правую сложные области движения, может дать паросочетание, в котором встречаются несовместные сложные области (объекты). Необходимо разработать новый алгоритм, позволяющий решить более общую задачу. Ограничение несовместности можно обойти, если отношение транзитивно. В этом случае все сложные области (объекты) можно разделить на непересекающиеся классы, причём элементы каждого класса будут попарно несовместны, а элементы из разных классов, напротив, будут совместными. Задача сводится к проблеме назначения классов друг другу. К сожалению, отношение несовместности не всегда транзитивно (см. рис. 3). В работе вводится новое понятие ограниченной задачи о максимальном взвешенном паросочетании (ОЗМВП).

Рисунок 4. Ограниченная засоединены ребром из E2. В работе показано, что задача о максимальном взвешенном паросочетании.

разрешения ОЗМВП, поэтому последняя является NP-полной задачей. Точного решения NP-полных задач скорее всего не существует, однако можно рассмотреть приближенные и переборные решения. В диссертации разработаны три приближенных полиномиальных алгоритма для ОЗМВП, проведён анализ временнй сложности, а для двух последних получена оценка коэффициента аппроксимации, показывающая степень близости решения к оптимальному.

Алгоритм GF (Жадный выбор экстремального паросочетания). Для данного графа G = (L R, E1 E2 ) алгоритм находит экстремальное паросочетание, выбирая по очереди рёбра с максимальным весом. Экстремальным паросочетанием называется паросочетание, которое не входит целиком в другое паросочетание. Будем считать, что L = {vi }n, R = {vi }nr, E1 = {eij } eij = (vi, vj ) соединяет вершины vi и vj, E2 несовместные связи.

GF 1. [Инициализация] M. Включить в список E все ребра из E1.

GF 2. [Поиск ребра] Найти в E ребро eij с максимальным весом. Завершить работу, если ребро не найдено. Добавить eij к паросочетанию M.

GF 3. [Удаление ребра] Удалить из E ребро eij, рёбра, смежные вершинам vi и vj и рёбра, инцидентные вершинам, которые несовместны с vi и vj.

GF 4. [Повтор] Вернуться к шагу GF 2.

Множество E, представляющее из себя очередь с приоритетом, предлагается реализовать с помощью бинарной кучи. Показано, что в этом случае время работы алгоритма GF есть O(E1 log E1 + E2 ). Если веса всех рёбер равны 1, вместо бинарной кучи можно использовать обыкновенный массив, в котором операция ExtractMax равносильна удалению последнего элемента и занимает O(1). Общее время работы алгоритма GF тогда будет O(E1 + E2 ) или O(E).

Если число несовместных связей невелико (не более k для каждой вершины), то можно построить полиномиальный приближённый алгоритм. Вариант задачи, когда для каждой вершины существует не более k несовместных вершин, назовём k-ограниченной задачей о максимальном взвешенном паросочетании (k-ОЗМВП). Если добавляется условие, что ограничения введены лишь с правой стороны графа, то такой вариант задачи назовём односторонней k-ОЗМВП.

Алгоритм Gk (Жадное просеивание неограниченного паросочетания).

Для данного графа G = (L R, E1 E2 ) этот алгоритм находит паросочетание, удаляя несовместные рёбра.

Gk1. [Решение ЗМВП] Решить классическую ЗМВП на графе G = (L R, E1 ).

Gk2. [Инициализация] M найденное паросочетание.

Gk3. [Поиск ребра] Найти в M ребро eij с максимальным весом. Если ребро не найдено, закончить алгоритм. Добавить найденное ребро в M.

Gk4. [Удаление рёбер] Удалить из M ребро eij ; все ребра, смежные вершинам vi и vj ; все рёбра, инцидентные вершинам, которые несовместны с vi и vj.

Gk5. [Повтор] Вернуться к шагу Gk 3.

В работе доказана следующая теорема: алгоритм Gk это (2k + 1)приближённый алгоритм для k-ОЗМПВ и (k + 1)-приближённый алгоритм для односторонней k-ОЗМПВ с полиномиальным временем работы O(E1 V log V +E2 ).

Алгоритм Gk (Сведение к транзитивному случаю). Для данного графа G = (L R, E1 E2 ) этот алгоритм сводит задачу к транзитивному случаю k-ОЗМВП и находит для этого паросочетание, которое путём удаления несовместных рёбер преобразуется в допустимое приближённое решение.

Gk1. Построить паросочетание N E2 в графе G = (V, E2 ), покрывающее вершины степени k. Если паросочетание построить не удалось, завершить алгоритм неудачей. Если N существует, то разбить множество вершин на транзитивные классы (из N по парам и остальные одиночные). Построить для данного транзитивного случая паросочетание максимального веса M.

Gk2.... Остальные шаги аналогичны алгоритму Gk.

Для работы алгоритма Gk требуется построить покрывающее паросочетание.

В третьей главе предложен алгоритм N, строящий такое паросочетание или возвращающий результат, что такого паросочетания не существует. Общее время работы Gk не превышает O(EV log V ). Если покрывающего паросочетания не существует, то следует использовать алгоритмы GF и Gk. В работе доказана следующая теорема: алгоритм Gk это полиномиальный (2k 1)-приближённый алгоритм для k-ОЗМПВ и k-приближённый для односторонней k-ОЗМПВ.

Для случая входных данных небольшого размера возможно использование переборных способов решения. Так как сложные области являются подмножествами множества областей движения, мы получаем, что в правой части графа должны находится непересекающиеся подмножества областей движения. Чтобы сгенерировать все разбиения, можно воспользоваться алгоритмом, который был предложен Джорджем Хатчинсоном в 1963 году. Для ускорения работы алгоритма мы будем рассматривать лишь ограниченные разбиения, подмножества которых содержат не более, чем r элементов. Модифицируем схему генерации, предложенную Хатчинсоном. Его метод использует одно из наиболее удачных представлений разбиения множества {1, 2,..., n} в компьютере, которое кодирует разбиение ограниченно растущей строкой, т. е. строкой a1 a2... an, в которой При этом aj = ak тогда и только тогда, когда элементы j и k принадлежат одному и тому же блоку. Кроме того, необходимо наименьшее доступное число для aj, где j наименьшее число в своём блоке. Чтобы просматривать только ограниченные разбиения, будем в процессе алгоритма рассчитывать число элементов в каждом блоке. Это позволит предотвратить посещение недопустимых строк. Допустимой строкой мы будем называть строку, соответствующую разбиению, в котором мощность каждого блока не превосходит заданного r:

Алгоритм Hr (Допустимые ограниченно растущие строки в лексикографическом порядке). Для данных n 2 и r 2 алгоритм генерирует все ограниченные разбиения {1, 2,..., n}, в которых мощность каждого блока не превышает r, путём посещения всех ограниченно растущих строк a1 a2... an, удовлетворяющих условиям (10) и (11). Как и в оригинальном алгоритме Хатчинсона, поддерживается вспомогательный массив b1 b2... bn, где bj = 1 + max(a1,..., aj );

значение переменной bn из соображений эффективности содержится в отдельной переменной m. Кроме того, мы вводим дополнительный массив c1 c2... cn, где ck = n kai, чтобы следить за числом элементов в блоках.

Hr 1. [Инициализ.] Для j = 1, n установить значения aj j1, bj+1 aj + 1, m bn. Для k = 1, n установить ck = n kai. Значение ck можно выi= числить в процессе установки aj, предварительно установив c1... cn 0.

Hr 2. [Посещение.] Если can r, то посетить ограниченно растущую строку a1 a2... an, которая представляет ограниченное разбиение на m + [an = m] блоков. Затем, если an = m, перейти к шагу Hr 4.

Hr 3. [Увеличение an.] Уменьшить can can 1. Установить a a + 1n, увеличить can can + 1 и вернуться к шагу Hr2.

Hr 4. [Поиск j.] Установить j n 1. Пока aj = bj, устанавливать j j 1.

Hr 5. [Увеличение aj.] Завершить работу, если j = 1. Иначе уменьшить caj caj 1, установить aj aj + 1, продолжать выполнять aj aj + 1 до тех пор, пока не окажется caj < r. Наконец, увеличить caj caj + 1.

Hr 6. [Обновление m.] Установить m bj + [aj = bj ], j j + 1 и t 0.

Hr 7. [Инициализация aj+1... an.] Если j < n, проверить условие ct = r и увеличивать t t + 1 до тех пор, пока не станет ct < r. Потом установить этот шаг, пока выполняется j < n.

Hr 8. [Возврат.] Увеличивать t t + 1 до тех пор, пока не станет ct < r.

Установить an = t, m max(m, an1 + 1) и вернуться к шагу Hr 2.

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

Разделяют глобальное и локальное выравнивание. Локальное выравнивание яркости преобразование изображения, основанное на распределении яркостей (или других характеристик) в окрестности каждого элемента изображения:

где mi(xy ) i-ая характеристика гистограммы яркостей в локальной окрестности xy точки (x, y). Пример: I (x, y) = I(x, y) m(x, y) + C, где m(x, y) средняя яркость в окрестности x,y Известные подходы по локальному выравниванию требует времени O(whSокр ), где w и h размеры изображения, Sокр площадь окрестности. Для уменьшения количества вычислений иногда применяют линейный алгоритм выравнивания, который использует непересекающиеся окрестности, но приводит к появлению нежелательного эффекта шахматного поля. Чтобы избавиться от такого эффекта, не ухудшив при этом производительность, в работе предложена модификация этого алгоритма. Введём на изображении прямоугольную равномерную сетку с шагом hx, hy (желательно, чтобы w. hx и h. hy ). Будем рассчитывать значение i-ой характеристики mi (xy ) лишь в узлах этой сетки. Все остальные значения будем линейно интерполировать по четырём ближайшим (по пространству) значениям в узлах сетки.

Алгоритм L (Быстрое локальное выравнивание яркости изображения). Для данного массива I(x, y) интенсивностей и заданных шагов сетки hx и hy этот алгоритм получает новый массив I (x, y), дающий приближенное локальное выравнивание яркости исходного изображения. Пусть (xi, yj ) узлы построенной сетки, m(x, y) статистика изображения в окрестности xy, значение которой алгоритм будет интерполировать. Если х, у удовлетворяют условию x1 x < x2, y1 y < y2, где x1, x2 абсциссы соседних вертикальных линий введённой сетки, а y1, y2 ординаты соседних горизонтальных линий, то где mij = m(xi, yj ), = (x2 x)/(x2 x1 ), = (y2 y)/(y2 y1 ). Если абсцисса точки (x, y) меньше абсциссы самой левой вертикальной линии (x < xmin ) или не меньше абсциссы самой правой вертикальной линии (x xmax ), то интерполяция m(x, y) выполняется по ближайшим двум узлам сетки m(xmin, y1 ) и m(xmin, y2 ) или m(xmax, y1 ) и m(xmax, y2 ), где y1 y < y2 :

L1. [Иницализация.] Для всех узлов сетки (xi, yj ) рассчитать mij m(xi, yj ).

L2. [Интерполяция.] Для всех точек (x, y) изображения рассчитать приближенное значение m(x, y) по формулам (13) и (14).

L3. [Локальное улучшение яркости.] Для всех точек (x, y) вычислить новое значение яркости I (x, y) по формуле (12) или аналогичной.

Так как интерполяция линейная, то порядок аппроксимации первый, тем не менее его можно улучшить, воспользовавшись методом Рунге–Ромберга.

С 1981 года в компьютерном зрении широко используются методы стабилизации изображений, основанные на алгоритме Лукаса-Канаде. Цель алгоритма минимизировать сумму квадратов ошибок E = x I W(x; p) T (x) 2, выбрав наиболее подходящее преобразование W(x, p). Нелинейное выражение аппроксимируется первым приближением в разложении Тейлора, а затем смещение p вычисляется методом наименьших квадратов (МНК): p = рах присутствуют подвижные объекты, то МНК может дать ненулевой результат даже, если смещение отсутствует. Чтобы избежать этого, включим весовые коэффициенты в формулу ошибки: E = x w(x, p) I W(x; p + p) T (x) 2.

Значение веса будем выбирать из следующих соображений. Алгоритм ЛукасаКанаде определяет незначительные смещения изображения, поэтому |p| < p, где p максимально установленный модуль смещения. Поэтому, если разность |T (x)I(W(x; p))| значительно превосходит максимально возможное изменение I W · p, значит она обусловлена не сдвигом изображений друг относительно друга, а появлением в заданной области движущихся объектов. Зададим в этом случае вес w(x, p) = 0. Для остальных ошибок примем вес, равный 1. Остаётся лишь модифицировать формулу расчёта p, исключив из суммы члены с нулевым весом: p = H 1 x w(x, p) I W T T (x) I W(x; p). Таким образом, мы получаем значение смещения p, более устойчивое к движению.

В четвёртой главе приведены экспериментальные результаты проверки обнаружения объектов, дано описание схем построения производственных образцов аппаратуры, дана методика оценки достоверности обнаружения динамических объектов. С участием автора данной диссертации на предприятии ГУП НПЦ ЭЛВИС было разработано семейство систем компьютерного зрения Orwell2k, имеющих широкий диапазон применения: приём, обработка, запись, хранение и анализ видеосигналов; обнаружение, идентификация и распознавание различных объектов; вывод полученной после обработки информации и взаимодействие с пользователем. Среди указанных применений особую роль играет процесс осуществления указанных операций с динамическими объектами.

На основе теоретических предпосылок разработана конструкторская документация и осуществлено серийное производство систем видеонаблюдения с компьютерным зрением (СВКЗ), которые используются в различных отраслях науки и техники. Структурно комплекс СВКЗ и его компоненты делятся на периферийную и станционную части. К периферийной части относятся средства телевизионного наблюдения, средства сбора и передачи информации, устанавливаемые на периметре, средства электропитания. устанавливаемые в распределительных шкафах на мачтах видеонаблюдения. К станционной части относятся средства сбора, обработки и отображения информации, средства электропитания, устанавливаемые в помещениях АДЦ (Административный Деловой центр) и КПП автотранспорта. Информационная связь между аппаратурой СВКЗ осуществляется по локальной вычислительной сети. Система, используя видеоизображение, обнаруживает динамические объекты, автоматически уведомляя оператора о появлении этих объектов в зоне охраны. Вся информация о подвижных объектах и ситуациях (появление в заданное время и в определённом месте), возникающих в зоне контроля системы, в режиме реального времени в виде мнемонических символов выводится на графический план охраняемого объекта на АРМ оператора, размещаемом в помещении операторской здания АДЦ.

В работе приведены результаты тестирования системы Orwell 2k-Barrier, предназначенной для обнаружения предметов, перебрасываемых через заграждение. Технические характеристики приборов экспериментальной проверки алгоритма обнаружения предметов для некоторого частного случая приведены в таблице 2. В действительности алгоритмы имеют более общее применение Таблица 2. Технические характерасстояниях и при разной ширине зоны ристики приборов.

Частота обмена с памятью 400 МГц Объем оперативной памяти 1 Гб блюдения, скорости объектов, разрешеРазрешение кадра ние видеоизображения, частота обработки кадров. Результаты натурного эксперимента показали, что для зоны шириной 9 метров предельно допустимый размер предмета составляет 80 мм (только объект из 100 оказался пропущен, ошибка II рода), что соответствует теоретическим вычислениям. Объекты меньшего размера (40 мм) система не обнаружила (ошибка II рода). Все объекты размера 170 мм были обнаружены системой.

Максимальная ширина зоны наблюдения Wmax = 4 d·w, d линейный размер объекта, w ширина кадра в пискелах. Обратно, dmin = 4 пксл · W/w. Максимально допустимая горизонтальная скорость объекта определяется предельной шириной зоны обзора: Vxmax = Wmin = fps · Wmin, nmin 6 – 8 минимально необходимое число кадров наблюдения, fps число кадров в секунду. Минимально допустимая горизонтальная скорость бросания Vxmin = min · fps · W, w min 3 минимальное горизонтальное смещение в пикселах.

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

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

1. Получены предельные значения коэффициента обновления в методе вычитания фона. Предложен модифицированный алгоритм вычитания фона, который использует два различных коэффициента (коэффициент обновления и коэффициент порога) вместо одного.

2. Разработан алгоритм пороговой компенсации, выбирающий коэффициент обновления в методе вычитания фона таким образом, чтобы ошибка первого рода (ложные срабатывания), обусловленная шумами изображения была не выше 0,003% в час, а также минимизирующий ошибку второго рода (пропуск объектов) при фиксированной ошибке первого рода.

3. Предложен параллельно-конвейерный алгоритм обнаружения движения, который сокращает время обработки одного кадра в 3–4 раза и при этом не уменьшает достоверности обнаружения динамических объектов.

4. Разработаны алгоритмы для распознавания ситуационного поведения динамических объектов.

Модифицированный метод вычитания фона Минимизирует ошибки первого рода, связанные с шуАлгоритм пороговой компенсации мами яркости изображения (квантовыми, теневыми и Параллельно-конвейерный алгоритм Ускоряет работу модифицированного метода вычитаобнаружения движения ния фона Алгоритм обнаружения объектов, дви- Позволяют автоматизировать распознавание различгающихся под действием сил тяжести ных ситуаций, например, фиксация нарушений и Алгоритм распознавания объектов, контроль за дорожной обстановкой предупреждение двигающихся в запрещенных направ- фактов хищений, контрабанды, преднамеренных полениях пыток переброса взрывчатых веществ на охраняемые Алгоритм распознавания остановки объекты, незаконной передачи предметов Три жадных алгоритма решения огра- Приближенное решение ограниченной задачи о наниченной задачи о максимальном па- значении, позволяют повысить достоверность поросочетании строения траекторий Модифицированный алгоритм Хат- Точное решение задачи построения траекторий объчинсона ектов для небольшого размера входных данных Быстрый алгоритм выравнивания ло- Минимизирует ошибки первого рода, связанные с локальной яркости изображения кальными изменениями яркости фона Алгоритм стабилизации изображения Минимизирует ошибки первого рода, связанные с с учётом движения объектов дрожанием камеры 5. Для решении задачи о сопоставлении объектов между кадрами предложено использовать множественное назначение. Обобщена задача о максимальном взвешенном паросочетании в двудольном графе на случай ограниченного взвешенного паросочетания, к которому сведена задача о множественном назначении. Разработан алгоритм сопоставления объектов на различных кадрах при условии разделения некоторых объектов на части.

6. Разработан устойчивый алгоритм стабилизации изображения с учётом движения объектов в кадре.

7. Разработан быстрый алгоритм выравнивания яркости в случае локального изменении освещённости.

8. Результаты диссертации применены в программно-аппаратных комплексах Orwell2k, разработанных при непосредственном участии автора (свидетельство о регистрации программы №2003612604 от 28.11.2003, патенты РФ №36315 от 07.08.2003, №36912 от 23.06.2003, №2265531 от 07.08.2003, № от 23.06.2003).

9. Разработанные в диссертационной работе теоретические расчёты, способы и алгоритмы используются в семействе компьютерных видеосистем Orwell2k . Программно-аппаратный комплекс Orwell2k был применён на территории особой экономической зоны ППТ Липецк, а также для обеспечения охраны территории и видеонаблюдения зоны авиационной деятельности центра деловой авиации аэропорта Домодедово и на других объектах.

Основные работы, опубликованные по теме диссертации 1. А. С. Малистов, Алгоритм пороговой компенсации влияния фоновых шумов на качество изображения, M.: из-во Компания Спутник+, научно-технический журнал Естественные и технические науки, №5, 2007, с. 191–192.

2. А. С. Малистов, Расчёт допустимых значений линейного коэффициента порога в методе вычитания фона при обнаружении движения, M.: из-во Компания Спутник+, научно-технический журнал Актуальные проблемы современной науки, №6, 2007, с. 165–168.

3. А. С. Малистов, Параллельно-конвеерный алгоритм обнаружения движения и выделения соответствующих областей в последовательности видеоизображений, M.: из-во Компания Спутник+, научно-технический журнал Техника и технология, №5, 2007, с. 29–30.

4. А. С. Малистов, А.А. Солохин, А.В. Хамухин, Формальный подход к оценке качества алгоритмов обработки изображений в интеллекуальных системах видеонаблюдения, журнал Вопросы радиоэлектроники, серия общетехническая(ОТ), выпуск 2, ОАО ЦНИИ Электроника, 2006.

5. А. С. Малистов, А.А. Солохин, А.В. Хамухин, Методы оценки эффективности алгоритмов в интеллектуальных системах видеонаблюдения, труды XLVII научной конференции МФТИ Соверменные проблемы фундаментальных и прикладных наук, ч. 3, c. 216–217, Москва, 2004.

6. А. С. Малистов, А.А. Солохин, А.В. Хамухин, Оценка эффективности алгоритмов в системах видеонаблюдения, XVI Международная Интернетконференция молодых ученых, аспирантов и студентов по современным проблемам машиноведения, тезисы докладов, с. 177, издательство ИМАШ РАН, Москва, 2004.

7. А. С. Малистов, Алгоритмы стабилизации изображения с учётом движения объектов в кадре, M.: из-во Компания Спутник+, научно-технический журнал Естественные и технические науки, №5, 2007, с. 193–194.

8. И.А. Кан, К.В. Лунин, А. С. Малистов, Я.Я. Петричкович, А.А. Солохин, В.П.

Сомиков, А.В. Хамухин, Система и способ автоматизированного видеонаблюдения и распознавания объектов и ситуаций. //Патент РФ на полезную модель №36912, бюл. №9, 2004.

9. И. А. Кан, К. В. Лунин, А. С. Малистов, Я. Я. Петричкович, А. А. Солохин, В. П. Сомиков, А. В. Хамухин, Система и способ автоматизированного видеонаблюдения и распознавания объектов и ситуаций. //Патент РФ №2268497, бюл. №02, 2006.

10. А. С. Малистов, Градиентный анализ границ областей движения в методе вычитания фона при решении проблемы покидающих зону наблюдения объектов, M.: из-во Компания Спутник+, научно-технический журнал Техника и технология, №5, 2007, с. 191–192.

11. А. С. Малистов, Быстрое выравнивание локальной яркости видеоизображений в условиях переменной облачности, M.: из-во Компания Спутник+, научно-технический журнал Техника и технология, №5, 2007, с. 26–27.

12. Я.Я. Петричкович, И.А. Кан, В.П. Сомиков, К.В. Лядвинский, К.В. Лунин, A.В. Хамухин, А. С. Малистов, А.А. Солохин, А.Х. Ахриев, Е.В. Горбачев, С.Л. Мурга, А.А. Болтнев, Устройство автоматизированного контроля обстановки в зрительных залах. //Патент РФ на полезную модель №47546, 13. А. Х. Ахриев, А. С. Малистов, А. В. Хамухин, П. А. Александров, Комплексный подход к созданию систем автоматического видеонаблюдения и видеоконтроля на объектах высокой сложности типа ITER и атомных станций, Вопросы атомной науки и техники, cерия Термоядерный синтез, 2006, 14. А. С. Малистов, Обнаружение движения по параболе с учётом пропуска кадров в системе видеонаблюдения реального времени, M.: из-во Компания Спутник+, научно-технический журнал Естественные и технические науки, №5, 2007, с. 195–196.

15. А. С. Малистов, Алгоритм распознавания остановки объекта в системе видеонаблюдения с детектором движения, M.: из-во Компания Спутник+, научно-технический журнал Актуальные проблемы современной науки, №6, 2007, с. 164–165.

16. А. С. Малистов, Алгоритм анализа траекторий движущихся на видеопоследовательности объектов с помощью потенциалов, M.: из-во Компания Спутник+, научно-технический журнал Актуальные проблемы современной науки, №6, 2007, с. 162–163.

17. Я. Я. Петричкович, В. П. Сомиков, А. С. Малистов, A. В. Хамухин, А. А. Солохин, К. В. Лунин, Система автоматизированного наблюдения и распознавания объектов и ситуаций “Orwell2k”. //Свидетельство об официальной регистрации программы для ЭВМ №2003612604, 2003.

Подписано в печать:

Заказ № 2. Формат 6084 1/16 Уч.-изд. л. 1 Тираж 100 экз.

Отпечатано в ГУП НПЦ ЭЛВИС