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

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

4854370

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

05.13.01 - «Системный анализ, управление и обработка информации» (в области приборостроения)

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

1 7 ОЕВ 2011

Москва — 2011

4854370

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

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

Официальные оппоненты:

доктор технических наук Петричкович Ярослав Ярославович

доктор физико-математических наук Рычагов Михаил Николаевич

кандидат технических наук Панасенко Сергей Петрович

Ведушая огранизация:

ЗАО «Московский научно-исследовательский телевизионный институт»

Защита состоится « ¿Г» Мартй 2011 г. в часов ^^ минут в аудитории 3103 на заседании диссертационного совета Д 212.134.02 Московского государственного института электронной техники (технического университета) по адресу: 124498, Москва, г. Зеленоград, проезд 4806, д. 5, МИЭТ (ТУ).

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

Атореферат разослан «

4 л % 2011 года.

Ученый секретарь

диссертационного совета Д 212.134.02 доктор технических наук

Гуреев А. В.

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

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

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

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

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

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

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

ситуационного поведения динамических объектов.

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

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-4 раза, что, в свою очередь, позволило сократить число используемых в системе серверов в 3 раза. Для ЭВМ с процессором Intel Core 2 Duo, 2,66 ГГц, сокращение составило с 8мс до 2-3 мс на кадр размера 352x288. Указанное улучшение производительности распространяется на ЭВМ любой конфигурации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались

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

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

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

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

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

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

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

VJ(r, t) - V + /((г, i) = 0. (1)

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

Е = / ((V/ ■ V + It)2 + q(|V^|2 + |Vu„|a)) dx dy, (2)

Jd

где D = [0, w\ x [0, h] С Ж2 — область изображения, a > 0 — параметр регуляризации, не зависящий от х и у. Оптический поток определяется как векторное поле v(r), минимизирующее функционал (2). Экстремум энергии можно найти, решая уравнения Эйлера-Лагранжа. Для больших изображений (больше

105 пикселов) алгоритм Хорна-Шунка очень трудоёмкий. Его временная сложность имеет порядок Q(SN): где S = wh — количество пикселов в изображении, N — количество итераций метода Якоби или Гаусса-Зейделя. Алгоритм Лукаса-Канаде, предложенный также в 1981 году, может работать с локальными окрестностями. Оптический поток определяется отдельно в окрестности Г каждой точки как вектор v, минимизирующей взвешенную сумму квадратов невязки уравнений (1) для точек окрестности: 5Zrer wr(r) (VJ(r, t) ■ v + /¡(r, t)) —> min, где wr(r) — весовая функция, обычно имеющая большие значение к центру окрестности Г. Решение может быть найдено методом наименьших квадратов:

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

Методы, основанные на сравнении окрестностей определяют скорость v как смещение одного изображения относительно другого, дающее минимум расстояния между изображениями в некоторой окрестности исследуемой точки. Расстояние может определяться, например, как минимальная сумма квадратов разностей яркости Е = 2гег №(г + v) — ^i(r))2 в окрестности. Полный перебор для каждого из М потенциально возможных смещений требует в(5|Г|М) операций. При использовании так называемой гауссовой пирамиды алгоритмическая сложность имеет порядок в(5|Г| logМ).

Прослеживание особенностей изображения — один из наиболее качественных методов обнаружения движения, устойчивый к глобальным изменениям яркости, но и самый затратный по времени. Практически любой алгоритм прослеживания особенностей состоит из 2 этапов: выделение особенностей (feature detection) и сопоставление особенностей на различных кадрах (feature matching). Наиболее часто в литературе встречается поиск точечных особенностей. В 1977 году в своей работе Moravec предложил считать особыми те точки изображения, для окрестности Г которых автокорреляционная функция имеет большие значения для всех смещений (Дх,Ау). Кроме особых точек в качестве особенностей изображения также широко используются границы и особые связные области.

Метод вычитания фона предполагает, что если для пиксела с координатами (х, у) среднее значение яркости в случае, когда этот пиксел является неподвижным, известно и равно В(х,у), можно выяснить с некоторой достоверностью, принадлежит ли этот пиксел фону или какому-то подвижному объекту. Пусть интенсивность пиксела (х, у) на n-ом кадре равна 1п{х,у). Точка считается подвижной, если \In(x,y) — В(х,у)\ ^ Т, где Т — некоторый порог движения. Так как интенсивность фона В(х,у) заранее неизвестна, то наибольшее распространение получил метод вычитания фона, в котором используется адаптивное накопление средней интенсивности. Для каждого пиксела (х, у) мы храним в памяти так называемое скользящее среднее интенсивности Вп(х,у) н условную оценку шума Тп(х,у). Точка считается подвижной, если |/„(:г, у) - B„-i(x, у) [ ^ d ■ Т'п_1(ж, у), где Тп(х, у) — оценка шума на n-ом кадре.

Метод вычитания фона наиболее распространён из-за его высокой произво-

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

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

Для каждого пиксела возможно одно из двух: точка (х, у) принадлежит стационарному фону (гипотеза Щ) или движущемуся объекту (гипотеза Н{). Любой алгоритм обнаружения движения А должен определить некоторую индикаторную функцию тп(х,у): если тп(х,у) = 0, значит, согласно критерию алгоритма А, принята гипотеза Но, если тп(х,у) = 1, то Н\. Пусть 1п(х,у) — интенсивность пиксела на тг-ом кадре. Для определения тп(х, у) метод вычитания фона хранит так называемое скользящее среднее интенсивности Вп(х,у):

Во{х,у) = Io(x,y), Вп(х,у) = {1-а)Вп-1(х,у) + а1п{х,у), (3) где а 6 (0,1) — величина, характеризующая степень обновления. На первом кадре фон совпадает с изображением, а на каждом новом кадре Вп(х,у) изменяется по формуле (3). Для оценки уровня шума вводится изменяющийся порог

Т0(х,у)=Т0, Тп(х,у) = (1-ат)Тп-1(х,у) + ат\1я{х,у)-Вп-1{х,у)\, (4) где ат € (0,1) — коэффициент обновления порога, а Го — начальная завышенная оценка шума. В общем случае а ф ат■ Индикаторная функция тп(х,у) определяется следующим образом:

т <х у\ = / есл" IIn(x,y) - Bn^i{x,y)\ >d-Tn_i(x,y), ^

[0, в остальных случаях,

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

Пусть {au}5£Lo — последовательность одинаково распределённых независимых случайных величин с математическим ожиданием Мап = m и дисперсией Dan = а2. Если {bn}S£Lo ~~ последовательность, определённая как скользящее среднее последовательности ап с коэффициентом обновления а £ (0,1): &о = = ао, Ьп = (1 — a)bn-i + аап, то верно следующее: 1) математическое ожидание M(bn) = m для любых п, 2) последовательность дисперсий Ьп сходится: lim D(bn) = т^т, 3) если ап ~ Nim, а2), то Ь„ ~ ЛГ(т, аа2/(2 - а)).

П—»00 ^ '

Пусть последовательность {in}SLo задана следующим образом: to = То, t„ = = (1 — ß)tn-i+ß\an — b„-i|, где ß € (0,1). В работе показано, что jj. = lim Mtn =

= /^Мд^) ¿ж, где д(х) — плотность распределения случайной величины =

= ап — 6П_ 1- Если Уп ап ~ Л/"(т, ст2), то ц = + ^ и при малых

а получаем ^ « Следовательно последовательность в пРеДелс

оценивает средпсквадратическое отклонение шума ст.

Описанная идеальная модель не работает, если в последовательности 1п(х, у) встречаются значения интенсивностей подвижных точек. Чтобы избежать этого, во многих работах изменяют значения В(х, у) и Т(х, у) только для тех точек, которые мы определили как неподвижные (г = (х,у))~.

о (г\ _ / ~ а) ■ Ai-i(r) + а ' 4(г), если тп„(г) = 1, *пКТ> \ Bn-i(r), если m„(r) = О,

т лл = / (! _ ат) • Г„_х(г) + ат ■ |/„(г) - ß„_i(r)|, если ш„(г) = 1, \ Тп-1(

(6)

i(r), если m„(г) = 0.

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

Если точка г принадлежит фону и при этом значение интенсивности отклонилось от накопленного значения более, чем на k-Tn-i(r), то для неё mn(г) = 1, а, значит, ложно принята гипотеза Н\ (ошибка 1-го рода, ложная тревога). Такие точки не вносят вклад в оценку порога, и так как отбрасываются большие значения, это понижает величину !Гп+д„(г) по сравнению с Гп(г) через некоторое время An. В работе показано, что уменьшение порога можно оценить

У /У

ß* = м\т}\ = h(k ■ tn) = h{k ■ ß) + Sh, h(y)= J\x\g{x)dx / J g{x)àx. (7)

-y / -y

Здесь Sh — флуктуация, вызванная отклонением tn от ц. Размер этой флуктуации можно оценить по дисперсии случайной величины tn. Функцию h(y), которая позволяет найти новую оценку, будем называть функцией оценки шума. В диссертации определены некоторые полезные свойства функции h(y): 1) Vy > 0: 0 ^ h(y) ^ у; 2) h(y) не убывает; 3) h(y) ограничена; 4) lim h(y) = 0.

у->0

Для к > 0 рассмотрим функцию hk(x) = h(kx). Функция hk(x) получается из h(kx) сжатием вдоль оси Ох, поэтому она также определена на (0,+оо), ограничена и всюду не убывает. Новое значение оценки из формулы (7) выражается с помощью hk{x) следующим образом: ц* = /ifc(/x) + äh. Рассмотрим рекурсивную последовательность в которой каждый следующий член

выражается через предыдущий по формуле fin = hk{Hn-1) = h(k^n-1). Так как hk{x) ограничена, то последовательность также ограничена. Кро-

ме того, последовательность монотонна, так как функция hk{x) неубы-

вающая. Поэтому она сходится. Предел 1 этой последовательности равен одному из решений уравнения

х = hk(x)

х = h(kx) (8)

Рисунок 1. Сходимость к неподвиж-

ным точкам функции ^{х). Если Ц1 < х-2, то Цш ¡¡п = XI. Ест ¡ц > Х2, то 1ш1 /гп = х3.

или равен 0. Разобьём область определения функции hk(x) на непересекающиеся интервалы (см. рис. 1): (0,+оо) = = (х0,хi) U {х1,х2) U ... U (xi,xi+i) U U (xjt,+oo) U {xi}j=1, где х0 = 0, а ixi}i=i ~ решения уравнения (8), которые называются неподвижными точками. Если первый член {/aJ^Li попадает в интервал (xj,xi+i), где h^x) > х, то последовательность возрастает и сходится к Такие интервалы будем называть положительными. Если hk(^i) < то последовательность будет убывать и сходиться к Xi (отрицательные интервалы). Неподвижные точки называются устойчивыми узлами, если выражение (hk(x) — х) меняет знак с положительного на отрицательный в этих точках, то есть 0 < h'k(x) < 1. Для h(y) в работе доказаны следующие леммы.

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

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

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

Если учесть флуктуации цп — hk{nn-i)+ôhn, то на каждом шаге, кроме отображения ftfc(/in_i) мы смещаем положение цп на случайную величину 5hn, тем большую, чем больше дисперсия tn. Даже вблизи неподвижных точек значение /х„ меняется. Таким образом, с учётом флуктуаций, все возможные варианты сходимости указаны в таблице 1.

Таблица 1. Режимы сходимости

Режим Описание

1. Вырождение. Уравнение (8) решений не имеет. Предел lim ¡in = 0. л—»ОС

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

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

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

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

Если в кадре нет движения и величина распределена нормально Л/"(0, ст2), в формулу (7) необходимо подставить функцию дпогт(х) = (\/2тгсг)~1е~х2/2(т2.

Вырождение наблюдается при к si 2. Для к > 1 получаем регулярный режим с одним устойчивым узлом; при к > 4 пересечение графиков происходит в точке, близкой к пределу h"jn"(x) на бесконечности, то есть при и м i/2/тго" и 0,8ст.

Если в кадре присутствует движение с частотой р, то д(х) определяется следующим образом: х) = (1 — р) ■дпо™(х) +p-gumt(x), где gunlf(i) — плотность функции распределения для движущихся точек. В случае смешанного распределения, функция оценки смешанного шума h(y) из (7) будет вычисляться следующим образом: у у

(1 - р) ■ J |a;|<7norm(:r) da: + р ■ f |a;|gunif(a:) dx

h{p)(y) =-=*L_-=f-• (9)

(1 - p) • J gnonll(x) dx+p- J guaiC(x) da: -s -v

Лемма 2.4 Для функции оценки смешанного шума верно двойное неравенство: min(haorm(y),huni{(y)) s; /i(!%) ^ max(/inorm(y),huaiC(y)).

На рисунке 2 показаны графики функций hf\x) для к = 3,5 для и различных значений р € [0,1]. Все они располагаются между двумя графиками для значений р = 0 и р = 1. В модели предполагалось, что <7umf (х) задаёт равномерное распределение с диапазоном AI, равным 20сг. Для малых значений р решение уравнения (8) даёт регулярный режим с одним устойчивым узлом, который оценивает шум яркости фоновых точек. Однако, начиная с некоторого р = Ро(к, AI/а), мы выходим на регулярный режим с несколькими устойчивыми узлами, причём наибольший из них оценивает не шум яркости фоновых 1 точек, а шум яркости подвижных точек, что не позволит нам классифицировать точки на подвижные и неподвижные. Величина частоты движения ро{к, А//сг), с которой начинается регулярный режим с несколькими устойчивыми узлами, зависит от выбираемого значения к. И наоборот, при данных значениях ДI/а и ро, существует минимальная величина к = ко(ро,А1/а), с которой начинается регулярный режим с несколькими устойчивыми узлами.

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

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

Рисупок 2. Оценка шума при наличии движения для к ~ 3,5 и для различных значений вероятности р движения.

ла. Если же шумовых точек много, то повышается вероятность, что несколько точек окажутся рядом и могут быть ложно определены как движущаяся область. В диссертации оценивается вероятность появления областей из шумовых точек площадью не менее 4 пикселов. Доказывается, что если доля шумовых точек равна р 6 (0,1), то для вероятности события Р, что хотя бы одна группа из 4 рядом расположенных точек будет ложно считаться подвижной, справедливо двойное неравенство \Ыр1 — ^(N/4 — -р8 ^ Р ^ кЫр4, где N — число точек изображения. Например, для изображения 352x288 и плотности шумовых точек 1%, получаем: 0,000253 < Р < 0,0193. При потоке видео 25 кадров в секунду мы получим, что в течение часа вероятность возникновения ложных областей на пяти кадрах подряд не выше 2,3 • Ю-5. Если плотность шумовых точек возрастает до 5%, то Р > 0,14, что уже недопустимо. Оценить шум можно, вычислив сумму площадей всех областей, площадь которых не превышает установленный порог в 4-8 точек. Каждый раз, оценивая фактическую долю шума на текущем кадре, следует изменять значение коэффициента таким образом, чтобы на следующих кадрах поддерживать долю шумовых точек на уровне 1-2%.

В диссертационной работе предложены способы обнаружения динамических объектов, которые появляются в зоне обзора камеры и двигаются под действием только гравитационных сил. Их траектория проецируется на ПЗС-матрицу в виде кривой второго порядка. Если вертикальная ось ПЗС-матрицы расположена перпендикулярно поверхности земли, то точки центра масс объекта будут проецироваться на параболу. Проверить гипотезу, лежит ли траектория движения объекта на параболе, можно, приблизив эту траекторию некоторой параболой методом наименьших квадратов. Чтобы повысить достоверность обнаружения, используется тот факт, что объект имеет постоянную скорость движения вдоль горизонтальной оси. Устройство видеозахвата получает кадры с постоянной периодичностью, поэтому время каждого кадра и = ¿о + ^г • Д£, где Д^ — промежуток между съемками соседних кадров (обычно около 40 мс), ¿о — момент, съемки нулевого кадра, /с; € N и {0}. Показано, что если некоторые кадры пропущены, то восстановить значения А;г- и и можно по формуле к= + [Аа^/Да:' + 0,5], где Да;' = МЕША^Да;*)!?^1. Оценить линейность горизонтальной скорости предлагается по коэффициенту корреляции между щ и ¿¿.

Автором диссертации разработаны способы обнаружения динамических объектов, которые двигались в зоне обзора камеры, а затем остановились на определённое время. Для обнаружения остановки можно оценить дисперсию положения геометрического центра масс объекта по последним п кадрам, где п — параметр алгоритма. Такой способ не работает, если положение центра масс объекта определяется не очень точно. Рассмотрим траекторию объекта как последовательность прямоугольных рамок г = ЩйЩ с вертикальными и горизонтальными сторонами: левая = 1е:Е1;(Д;), правая г,: = ^¿ЪХ(Ри), верхняя ^ = -Ьор(Дг) и нижняя = Ьо-М;от(/^). Здесь по и пь ограничивают период анализа, который зависит от скоростей движущихся объектов и лежит в промежутке от 5 секунд до 10-20 минут. В системах реального времени щ обычно совпадает с последним кадром. Упорядочим все левые стороны £{ рамок по возрастанию и возьмем а-квантиль указанного ряда £,~ и (1 — а)-квантиль Аналогичную операцию проведем для верхней (¿~, нижней , 6+) и правой

(t~, t^) границы рамок. Разница между £~ и показывает насколько сильно изменялась левая граница рамки объекта в течение анализируемого промежутка времени. Рассмотрим рамку Si с левой границей правой г~, верней ij, нижней Ь~ и прямоугольную рамку §2 с соответствующими сторонами £~, г£|, t~, . Если объект не движется, то в идеальном случае, когда нет шума, рамка S2 должна совпадать с рамкой Sj. Площади рамок связаны соотношением Si ^ S'z- Значение отношения г/ = S1/S2 принадлежит отрезку [0,1]. Чем ближе rj к единице, тем вероятнее, что объект не движется. Если т) близка к нулю, то объект находится в движении: его смещение за анализируемый период сопоставимо или больше размеров самого объекта. Характеристику 77 предлагается рассматривать как признак для распознавания остановки объекта.

В диссертации разработаны способы обнаружения динамических объектов, которые двигались в зоне обзора камеры в запрещённых направлениях. Для этого на изображении вводится векторное поле запрещённых направлений Е(х,у): кадр делится на несколько частей и для каждой задаётся запрещённое направление. Пусть r(i) — траектория движения некоторого объекта О. Для объекта О в работе определяется понятие совершённой работы A: An = Е(гг)-(г;—г,-^). Возрастание Ап означает движение в запрещённом направлении, убывание, наоборот, показывает, что объект двигается по разрешённой траектории. Чтобы определить степень увеличения Ап, вводится понятие максимальной разности за промежуток от 1 до п: Д„ = Ап — Мп, где Mn = mmi=g^rj -А,-. Для ускорения вычислений минимум Мп корректируется на каждом шаге. Если Д„ превысит установленный порог, значит, объект проделал путь в запрещённом направлении, достаточный для выдачи сигнала тревоги. В работе также обобщён данный алгоритм на случай нескольких запрещённых направлений в одной точке. Если задано к векторных полей запрещённых направлений Ej(x,у), j = 1, к, то формула расчёта работы будет следующей: An = maxj=Ij(E;(rt) • (г* — r/_i)).

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

Наша цель — соединить области движения на разных кадрах таким образом, чтобы они образовали оптимальное множество вершинно-независимых путей (траекторий). Траектория — это последовательность областей rtnkn, п. = 1, N, такая, что < tj для г < j. Момент времени t\ называется моментом появ-

1 У. 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

ления объекта, момент времени i^r + 1 — моментом исчезновения. Оптимальность построения траекторий можно определить, если сформулировать задачу в терминах теории графов. Будем считать, что в любой момент времени t уже построено некоторое множество Ot = {Ci, О?,... Оц^} траекторий, которые назовём объектами. Объекты представляют из себя последовательность областей движения на кадрах, которые предшествуют текущему кадру t. Определим неориентированный взвешенный двудольный граф G = (V, Е) следующим образом: V = Ot U 1Zt, Е = {бу}. Каждое ребро e,j соединяет вершины € Ot и rtj € TZf. Вес каждого ребра Wij = w(eij) определяет меру схожести объекта с областью нового кадра. Задача однозначного назначения — это задача построения паросочетания с максимальным суммарным весом в графе G. Решение задачи сопоставит объектам текущего кадра новые области движения, при этом каждому объекту будет сопоставлено не более одной области движения, а каждой области движения сопоставлено не более одного объекта. Объект Ot будет временно пропавшим, если он не сопоставлен ни одной из областей движения.

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

Число всех возможных непустых подмножеств конечного множества размера п равно 2" — 1. Однако, не все комбинации допустимы. Пусть G = (7Zt,E) — неориентированный граф, вершинами которого являются области движения 1Zt, а ребра соединяют те области, которые находятся на достаточно близком расстоянии (меньше заданного алгоритмом порога). Показано, что вместо генерации всех подмножеств множества 7Zt можно составлять связные подграфы для изолированных подграфов G. Мы хотим построить оптимальное соответствие между сложными областями и сложными объектами. Однако, не каждое даже однозначное соответствие может считаться удачным: разные подмножества могут включать одни и те же области движения. Такие подмножества мы будем называть несовместными: Лх В АГ\В ф 0. Решение классической задачи о максимальном взвешенном паросочетании на двудольном графе, в котором в левую часть входят сложные объекты, в правую — сложные области движения, может дать паросочетание, в котором встречаются несовместные сложные области (объекты). Необходимо разработать новый алгоритм, позволяющий решить более общую задачу. Ограничение несовместности можно обойти, если отношение х транзитивно. В этом случае все сложные области (объекты) можно разделить на непересекающиеся классы, причём элементы каждого класса будут попарно несовместны, а элементы из разных классов, напротив, будут совместными. Задача сводится к проблеме назначения классов друг другу. К сожалению, отношение несовместности не

в

Oj3 0G)

А С

Рисунок 3. Нетранзитивиость отношения несовместности.

всегда транзитивно (см. рис. 3). В работе вводится новое понятие ограниченной задачи о максимальном взвешенном паросочетании (ОЗМВП).

Пусть G = (V, Е) — неориентированный взвешенный двудольный граф, V = LU R — множество вершин графа, Е = Е[ U Е-2 ~ множество рёбер двух типов. Ребра из Е\ имеют вес и связывают вершины из разных долей графа, а рёбра — из одной доли (L или В). Вершины v\ и V2, связанные ребром е £ £21 называются несовместными: V\ >; х V2 <=> Зе = (v\, V2) € £2- В общем случае, отношение не обязательно транзитивно. Требуется найти паросочетание М С Е\ максимального веса такое, что никакие две вершины, входящие в М не соединены ребром из £2- В работе показано, что задача CLIQUE полиномиально сводится к варианту разрешения ОЗМВП, поэтому последняя является Л^Р-полной задачей. Точного решения NP-полных задач скорее всего не существует, однако можно рассмотреть приближенные и переборные решения. В диссертации разработаны три приближенных полиномиальных алгоритма для ОЗМВП, проведён анализ временной сложности, а для двух последних получена оценка коэффициента аппроксимации, показывающая степень близости решения к оптимальному. Алгоритм Gp (Жадный выбор экстремального паросочетания). Для данного графа G = (L U R, Е\ U £2) алгоритм находит экстремальное паросочетание, выбирая по очереди рёбра с максимальным весом. Экстремальным паросочетанием называется паросочетание, которое не входит целиком в другое паросочетание. Будем считать, что L — {vf}"^, R = Е\ = {e,j} (eij = (vf, Vj) соединяет вершины vf и Vj), E2 — несовместные связи. GfI- [Инициализация] M <— 0. Включить в список Е* все ребра из Е\. Gf2. [Поиск ребра[ Найти в Е* ребро е^ с максимальным весом. Завершить

работу, если ребро не найдено. Добавить еу к паросочетанию М. Gf3. [Удаление ребра] Удалить из Е* ребро ец, рёбра, смежные вершинам v\ и

Vj и рёбра, инцидентные вершинам, которые несовместны с vf и Vj. Gf4. [Повтор] Вернуться к шагу Gp2.

Множество £*, представляющее из себя очередь с приоритетом, предлагается реализовать с помощью бинарной кучи. Показано, что в этом случае время работы алгоритма Gf есть 0(Е\ log Е\ + E-i). Если веса всех рёбер равны 1, вместо бинарной кучи можно использовать обыкновенный массив, в котором операция ExtractMax равносильна удалению последнего элемента и занимает 0(1). Общее время работы алгоритма Gf тогда будет 0(Е\ + £2) или О(Е).

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

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

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

Для данного графа й = (Ь и Я, Е\ и Е2) этот алгоритм находит паросочстание, удаляя несовместные рёбра.

вк!- [Решение ЗМВП) Решить классическую ЗМВП на графе С = (ЬИЯ, Е\). Ск2. [Инициализация] М — найденное паросочетанне.

СкЗ. [Поиск ребра] Найти в М ребро е^ с максимальным весом. Если ребро не

найдено, закончить алгоритм. Добавить найденное ребро в М'. Ск4. [Удаление рёбер] Удалить из М ребро еу, все ребра, смежные вершинам и/ и Ир все рёбра, инцидентные вершинам, которые несовместны с V* и уГу Ск5. [Повтор] Вернуться к шагу СкЗ.

В работе доказана следующая теорема: алгоритм Ск — это (2к + 1)-приближённый алгоритм для /с-ОЗМПВ и (к + 1)-приближённый алгоритм для односторонней А-ОЗМПВ с полиномиальным временем работы 0(Е\У log У+Е2). Алгоритм Ск (Сведение к транзитивному случаю). Для данного графа <3 = (Ь и Л, Е\ и Е2) этот алгоритм сводит задачу к транзитивному случаю &-ОЗМВП и находит для этого паросочетанне, которое путём удаления несовместных рёбер преобразуется в допустимое приближённое решение. Ск1. Построить паросочетанне N С Е2 в графе 0 = (V, Е^), покрывающее вершины степени к. Если паросочетанне построить не удалось, завершить алгоритм неудачей. Если N существует, то разбить множество вершин на транзитивные классы (из N по парам и остальные одиночные). Построить для данного транзитивного случая паросочетанне максимального веса М. Ск2. ... Остальные шаги аналогичны алгоритму

Для работы алгоритма требуется построить покрывающее паросочетанне. В третьей главе предложен алгоритм 14, строящий такое паросочетанне или возвращающий результат, что такого паросочетания не существует. Общее время работы не превышает 0{ЕУ\о£У). Если покрывающего паросочетания не существует, то следует использовать алгоритмы вр и вь В работе доказана следующая теорема: алгоритм — это полиномиальный (2/с — 1)-приближённый алгоритм для А>ОЗМПВ и /г-приближённый для односторонней /г-ОЗМПВ.

Для случая входных данных небольшого размера возможно использование переборных способов решения. Так как сложные области являются подмножествами множества областей движения, мы получаем, что в правой части графа должны находится непересекающиеся подмножества областей движения. Чтобы сгенерировать все разбиения, можно воспользоваться алгоритмом, который был предложен Джорджем Хатчинсоном в 1963 году. Для ускорения работы алгоритма мы будем рассматривать лишь ограниченные разбиения, подмножества которых содержат не более, чем г элементов. Модифицируем схему генерации, предложенную Хатчинсоном. Его метод использует одно из наиболее удачных представлений разбиения множества {1,2,..., п} в компьютере, которое кодирует разбиение ограниченно растущей строкой, т.е. строкой а10,2 .. . ап, в которой

(Х\ — 0 и ^ 1 -Ь тах(аь ... для 1 ^ ^ < п. (10)

При этом а= ад. тогда и только тогда, когда элементы ] и к принадлежат одному и тому же блоку Кроме того, необходимо наименьшее доступное число

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

V/c et = Yli=i^kai ^ т — символ Кронекера). (11)

Алгоритм Нг (Допустимые ограниченно растущие строки в лексикографическом порядке). Для данных п ^ 2 и г ^ 2 алгоритм генерирует все ограниченные разбиения {1,2,..., п}, в которых мощность каждого блока не превышает г, путём посещения всех ограниченно растущих строк а\0,2 ... ап, удовлетворяющих условиям (10) и (11). Как и в оригинальном алгоритме Хатчинсона, поддерживается вспомогательный массив Ьфг ■ ■ ■ Ьп, где bj = 1 + max(aj,..., aj); значение переменной bn из соображений эффективности содержится в отдельной переменной т. Кроме того, мы вводим дополнительный массив С1С2 ■ ■ ■ c,t, где c/t = 2Г=1 ^kao чтобы следить за числом элементов в блоках. Нг1. [Инициализ.] Для j = 1,п установить значения aj <— L^J ■, fy+i aj +1, m <— bn. Для k = 1, n установить Ck = ¿ha,■ Значение Ck можно вычислить в процессе установки aj, предварительно установив с\... Сп «— 0. Нг2. [Посещение.] Если сап < г, то посетить ограниченно растущую строку а iü2 ■ ■ - а„, которая представляет ограниченное разбиение на т+[ап = т] блоков. Затем, если ап = т., перейти к шагу Нг4. Нг3. [Увеличение ап.] Уменьшить с0п <— са„ — 1- Установить а а + 1„, увеличить са„ сап 4-1 и вернуться к шагу Нг2. Нг4. [Поиск j] Установить j <— п — 1. Пока aj = bj, устанавливать j j — 1. Нг5. [Увеличение a.j.] Завершить работу, если j = 1. Иначе уменьшить сй] <— <— cüj — 1, установить aj <— aj + 1, продолжать выполнять aj <— aj + 1 до тех пор, пока не окажется сП] < г. Наконец, увеличить са> <— caj + 1. Нг6. [Обновление т.] Установить rn <— bj + [aj = bj\, j <— j + 1 и t <— 0.

Hr7. [Инициализация %+1... ап\ Если j < n, проверить условие et = г и увеличивать t t + 1 до тех пор, пока не станет q < г. Потом установить с^ caj — 1, aj <— t, caj сП] + 1 и bj = max(m, + 1). Повторять этот шаг, пока выполняется j < п. Нг8. [Возврат.] Увеличивать t <— t + 1 до тех пор, пока не станет Ct < г. Установить ап = t, rn max(m,an_1 + 1) и вернуться к шагу Нг2.

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

у) = f(Hx, У), mi(Q.xy), т2(Пху),..., mn(ilxy)), (12)

где mi(Q,Xy) — г-ая характеристика гистограммы яркостей в локальной окрестности Qxy точки (х,у). Пример: 1*(х,у) = 1(х,у) — т(х,у) + С, где т{х,у) — средняя яркость в окрестности ПХ:!/ Известные подходы по локальному выравниванию требует времени 0(whSOKр), где w и h — размеры изображения, ^кр — площадь окрестности. Для уменьшения количества вычислений иногда применяют линейный алгоритм выравнивания, который использует непересекающиеся окрестности, но приводит к появлению нежелательного эффекта шахматного поля. Чтобы избавиться от такого эффекта, не ухудшив при этом производительность, в работе предложена модификация этого алгоритма. Введём на изображении прямоугольную равномерную сетку с шагом hx, hy (желательно, чтобы w; hx и h: hy). Будем рассчитывать значение г-oft характеристики rrii(Q,xy) лишь в узлах этой сетки. Все остальные значения будем линейно интерполировать по четырём ближайшим (по пространству) значениям в узлах сетки. Алгоритм L (Быстрое локальное выравнивание яркости изображения). Для данного массива 1{х,у) интенсивностей и заданных шагов сетки hx и hy этот алгоритм получает новый массив 1*(х,у), дающий приближенное локальное выравнивание яркости исходного изображения. Пусть (Xi,yj) — узлы построенной сетки, т(х, у) — статистика изображения в окрестности Qxy, значение которой алгоритм будет интерполировать. Если х, у удовлетворяют условию Xi < х < х2, yi < у < 2/2, где Xi, х2 — абсциссы соседних вертикальных линий введённой сетки, а у\, у2 — ординаты соседних горизонтальных линий, то

fh(x,y) = Р(а ■ шц + (1 - а) ■ т21) + (1 - Р)(а -тп + (1 - се)-т22), (13) где my = m{xi,yj), а = (х2 - х)/(х2 - х{), /3 - (у2 - у)/(у2 - у{). Если абсцисса точки (х, у) меньше абсциссы самой левой вертикальной линии (я < xmin) или не меньше абсциссы самой правой вертикальной линии (х > хтах), то интерполяция т(х,у) выполняется по ближайшим двум узлам сетки т(хт\п,у\) и у2) (или т{хтах,у1) и т{хтах, у2)), где yi^y < у2~.

Р • т{хmi„(max), 2/i) + (1 - Р) ■ m(xmhlimSlx),y2). (14)

L1. [Иницализация.] Для всех узлов сетки (xi, yj) рассчитать m,:j <— m(xi: yj). L2. [Интерполяция.] Для всех точек (х,у) изображения рассчитать приближенное значение т(х,у) по формулам (13) и (14). L3. [Локальное улучшение яркости.) Для всех точек (х, у) вычислить новое значение яркости Г(х,у) по формуле (12) или аналогичной. Так как интерполяция линейная, то порядок аппроксимации первый, тем не менее его можно улучшить, воспользовавшись методом Рунге-Ромберга.

С 1981 года в компьютерном зрении широко используются методы стабилизации изображений, основанные на алгоритме Лукаса-Канаде. Цель алгоритма — минимизировать сумму квадратов

ошибок е = Ex(7(w(x;P)) - т(х))2.

выбрав наиболее подходящее преобразование W(x, р). Нелинейное выражение аппроксимируется первым приближением в разложении Тейлора, а затем смещение Др вычисляется методом наименьших квадратов (МНК): Др = = Я'1 £*[V/^mx)-/(W(x;p))], Я = Если вкад-

pax присутствуют подвижные объекты, то МНК может дать ненулевой резуль-

тат даже, если смещение отсутствует. Чтобы избежать этого, включим весовые коэффициенты в формулу ошибки: Е = ui(x, р) (/(\¥(х; р + Др)) — Т(х))2. Значение веса будем выбирать из следующих соображений. Алгоритм Лукаса-Канаде определяет незначительные смещения изображения, поэтому |Др| < Sp, где 6р — максимально установленный модуль смещения. Поэтому, если разность |r(x)-/(W(x; р))| значительно превосходит максимально возможное изменение ^-j - Sp, значит она обусловлена не сдвигом изображений друг относительно друга, а появлением в заданной области движущихся объектов. Зададим в этом случае вес w(x, р) = 0. Для остальных ошибок примем вес, равный 1. Остаётся лишь модифицировать формулу расчёта Др, исключив из суммы члены с нулевым весом: Др = Я"1 w(x,р)[У/^]г[Г(х) -/(W(x;р))]. Таким образом, мы получаем значение смещения Др, более устойчивое к движению.

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

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

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

Таблица 2. Технические характе- от микро- ДО макрообъектов, на разных

расстояниях и при разной ширине зоны наблюдения. На вход алгоритм получает положение объекта на каждом кадре г е [¿1,^2], иа выходе — принимает или отвергает указанную гипотезу. Алгоритм реализован на языке С++.

На предельные размеры обнаруживаемых предметов влияют ширина зоны наблюдения, скорости объектов, разрешение видеоизображения, частота обработки кадров. Результаты натурного эксперимента показали, что для зоны шириной 9 метров предельно допустимый размер предмета составляет 80 мм (только 1 объект из 100 оказался пропущен, ошибка II рода), что соответствует теоретическим вычислениям. Объекты меньшего размера (40 мм) система не обнаружила (ошибка II рода). Все объекты размера 170 мм были обнаружены системой. Максимальная ширина зоны наблюдения Wmaji = 4 d — линейный размер объекта, w — ширина кадра в пискелах. Обратно, ¿min = 4пксл • W/w. Максимально допустимая горизонтальная скорость объекта определяется предельной шириной зоны обзора: Vlmax = v™* = fPs ' «min ~ 6-8 — минимально

'min ^rnin

необходимое число кадров наблюдения, fps — число кадров в секунду.. Минимально допустимая горизонтальная скорость бросания V™1" = Amin • fps • Amin ~ 3 — минимальное горизонтальное смещение в пикселах.

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

Основные результаты работы

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

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

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

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

ристики приборов.

Тактовая частота процессора 3 ГГц

Частота обмена с памятью 400 МГц

Объем оперативной памяти 1 Гб

Тип ПЗС-матрицы '/г дюйма

Ширина дальней зоны 9 м

Угол обзора камеры 20°

Фокусное расстояние объектива 18 мм

Разрешение кадра 352 х 288

Алгоритмы Функции

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

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

Параллельно-конвейерный алгоритм обнаружения движения Ускоряет работу модифицированного метода вычитания фона

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

Три жадных алгоритма решения ограниченной задачи о максимальном паросочетании Приближенное решение ограниченной задачи о назначении, позволяют повысить достоверность построения траекторий

Модифицированный алгоритм Хатчинсона Точное решение задачи построения траекторий объектов для небольшого размера входных данных

Быстрый алгоритм выравнивания локальной яркости изображения Минимизирует ошибки первого рода, связанные с локальными изменениями яркости фона

Алгоритм стабилизации изображения с учётом движения объектов Минимизирует ошибки первого рода, связанные с дрожанием камеры

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

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

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

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

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

Основные работы, опубликованные по теме диссертации

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

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

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

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

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

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

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

8. И.А. Кая, К.В. Лунин, А. С. Малистов, Я.Я. Петричкович, A.A. Солохин, В.П. Сомиков, A.B. Хамухин, «Система и способ автоматизированного видеонаблюдения и распознавания объектов и ситуаций». //Патент РФ на полезную модель №36912, бюл. №9, 2004.

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

B. П. Сомиков, А. В. Хамухин, «Система и способ автоматизированного видеонаблюдения и распознавания объектов и ситуаций». //Патент РФ №2268497, бюл. №02, 2006.

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

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

12. Я.Я. Петричкович, И.А. Кан, В.П. Сомиков, К.В. Лядвинский, К.В. Лунин, A.B. Хамухин, А. С. Малистов, A.A. Солохин, А.Х. Ахриев, Е.В. Горбачев,

C.Л. Мурга, A.A. Болтнев, «Устройство автоматизированного контроля об-

\>

становки в зрительных залах». //Патент РФ на полезную модель №47546, бюл. №24, 2005.

13. А.Х. Ахриев, А. С. Малистов, A.B. Хамухин, П. А. Александров, «Комплексный подход к созданию систем автоматического видеонаблюдения и видеоконтроля на объектах высокой сложности типа ITER и атомных станций», «Вопросы атомной науки и техники», серия «Термоядерный синтез», 2006, вып. 3., с. 69-81.

14. А. С. Малистов, «Обнаружение движения по параболе с учётом пропуска кадров в системе видеонаблюдения реального времени», М.: из-во «Компания Спутник+», научно-технический журнал «Естественные и технические науки», №5, 2007, с. 195-196.

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

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

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

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

Заказ №2. Формат 60x84у16 Уч.-нзд. л. 1 Тираж 100 экз. Отпечатано в ГУП НПЦ «ЭЛВИС»

Введение

1. Современные методы повышения эффективности анализа видеоизображений статических и динамических объектов.

1.1. Приборы и методы представления и восприятия видеоизображений. Модели цифровых сигналов.

1.2. Анализ и классификация современных алгоритмов обнаружения движения.

1.3. Применение теории графов для обнаружения движущихся объектов.

1.4. Основные показатели достоверности обнаружения динамических объектов

1.5. Методы стабилизации параметров видеоизображений

1.6. Анализ достоинств и недостатков существующих методов выделения динамических объектов.

1.7. Цели и задачи диссертационной работы.

Выводы.

2. Исследование, разработка и анализ быстрых алгоритмов выделения движения

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

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

2.3. Параллельно-конвейерный алгоритм обнаружения движения и выделения соответствующих областей в последовательности видеоизображений

2.4. Градиентный анализ границ областей движения при визуализации объектов, покидающих зону наблюдения.

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

2.6. Алгоритм распознавания остановки объекта в системе видеонаблюдения с детектором движения

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

Выводы.

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

3.1. Анализ пространственных перемещений на основе принципа однозначного назначения

3.2. Анализ пространственных траекторий на основе принципа множественного назначения

3.3. Ограниченная задача о максимальном взвешенном паросо-четании (ОЗМВП)

3.4. Жадные приближённые алгоритмы решения ограниченной задачи о максимальном взвешенном паросочетании

3.5. Точное решение ОЗМВП для небольших размеров входных данных

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

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

Выводы.

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

4.1. Функциональная схема и основные параметры компьютерных систем видеонаблюдения

4.2. Описание схем построения производственных образцов аппаратуры

4.3. Экспериментальные результаты проверки обнаружения динамических объектов.

4.4. Методика оценки достоверности обнаружения динамических объектов

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

Выводы.

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

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

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

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

Большой вклад в область информационной обработки, классификации и распознавания видеосигналов внесли известные учёные, работающие в России и за рубежом: Ю. И. Журавлев, В. Н. Вапник, А. И. Галушкин, JI. П. Ярославский, В. D. Lukas, Т. Kanade, В. К. P. Horn, В. G. Schunck, R. Collins, A. Lipton, С. Stauffer, W. Е. L. Grimson и другие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) системы видеонаблюдения с компьютерным зрением «Orwell2k» (патенты РФ на полезные модели №36315 от 07.08.2003 и №36912 от 23.06.2003, патенты РФ №2265531 от 07.08.2003 и №2268497 от 23.06.2003);

2) видеодетектор предметов «Orwell2k-Barrier», распознающий динамические объекты при движении в поле сил тяжести;

3) система подсчета зрителей в кинозалах «Orwell2k-Cinema» (патент РФ на полезную модель №47546 и на изобретение №2296434)

Все указанные системы были разработаны при непосредственном участии автора на предприятии ГУП НПЦ «ЭЛВИС». Основные программные средства видеосистем официально зарегистрированы (свидетельство №2003612604 от 28.11.2003).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компьютерные видеосистемы семейства «Orwell2k», в которых внедрены результаты работы, демонстрировались на 13 выставках.

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

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

Выводы

1. Проведён анализ функциональной схемы и основных параметров компьютерных систем видеонаблюдения.

2. На примере проекта Система видеонаблюдения СПО Ю5-КТСО-СТН, РАЯЖ 46352.003, была описана схем построения производственных образцов аппаратуры.

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

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

Заключение

При выполнении диссертационной работы достигнуты следующие результаты.

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

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

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

4. Для повышения эффективности визуализации разработан способ распознавания покидающих зону наблюдения динамических объектов для решения проблемы «дыр» в методе вычитания фона.

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

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

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

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

9. Результаты диссертационной работы применены в программно-аппаратных комплексах «Ог\уе112к», разработанных при непосредственном участии автора (свидетельство о регистрации программы №2003612604 от 28.11.2003, патенты РФ №36315 от 07.08.2003, №36912 от 23.06.2003, №2265531 от 07.08.2003, №2268497 от 23.06.2003).

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

1. Физическая Энциклопедия / Гл. ред. А. М. Прохоров. Ред. кол. Д. М. Алексеев, А. М. Балдип, А. М. Бонч-Бруевич, А. С. Боровик-Романов и др. — М.: Большая Российская Энциклопедия, т. 5, 1998.

2. Зворыкин В. К. Телевидение // УФЫ, 1934, т. 14

3. Boyle W. S., Smith G. Е. Charge coupled semiconductor devices. // Bell Systems Technical Journal, vol. 49, pp. 587-593, April 1970.

4. Boyle W. S., Smith G. E. The Inception of Charge-Coupled Devices // IEEE Transactions on electron devices, vol. ED-23, No. 7, July 1976.

5. Прокофьева В. В. Исследование слабых астрономических объектов методами телевизионной электроники. // УФН, 1979, т. 127, вып. 3.

6. Oppenheim А. V., Schafer R. W., Stockham Т. G., Nonlinear Filtering of Multiplied and Convolved Signals, Proceedings of the IEEE, vol. 56, No. 8, August 1968.

7. Гонсалес P., Вудс P. Цифровая обработка изображений — M.: Техносфера, 2005.

8. Л. Шапиро, Дж. Стокман Компьютерное зрение — М.: Бином. Лаборатория знаний, 2006.

9. Форсайт, ДэвидА., Понс, Жан. Компьютерное зрение. Современный подход.: Пер. с англ. — М.: Издательский дом «Вильяме», 2004.

10. Healey G. Е., Kondepudy R. Radiometric CCD camera calibration and noise estimation // IEEE Pattern analysis and machine intelligence, vol. 16, No. 3, pp. 267-276, 1994.

11. C. Anderson, Peter Burt, and G. van der Wal. Change detection and tracking using pyramid transformation techniques. In Proceedings of SPIE

12. Intelligent Robots and Computer Vision, volume 579, pages 72-78, 1985.

13. P. L. Rosin and T. Ellis, "Image difference threshold strategies and shadow detection," in Proc. British Machine Vision Conf., pp. 347-356, 1995.

14. J. Barron, D. Fleet, and S. Beauchemin. Performance of optical flow techniques. International Journal of Computer Vision, 12 (1), 42-77, 1994.

15. Lukas B. D. and Kanade T. "An iterative image registration technique with an application to stereo vision". In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 674-679, 1981.

16. Horn B. K. P. and Schunck B. G. "Determining optical flow." Artificial Intelligence, vol. 17, pp. 185-203, 1981.

17. Lucas B. D. "Generalized Image Matching by the Method of Differences", PhD Dissertation, Dept. of Computer Science Carnegie-Mellon University.

18. Eero Simoncelli, Edward H. Adelson, David J. Hecgcr, "Probability Distributions of Optical Flow", Proc. Conf. on Computer Vision and Pattern Recognition, pp. 310-315.

19. Andres Bruhn, Joachim Weickert, Christoph Schnorr. Lucas/Kanade meets Horn/Schunck: Combining Local and Global Optic Flow Methods. International Journal of Computer Vision 61 (3): 211-231, 2005.

20. Tomasi C. and Kanade T. "Detection and Tracking of Point Features," Tech. Rept. CMU-CS-91132, Carnegie Mellon University, April 1991.

21. Shi J. and Tomasi C. Good Features to track. IEEE Conference on Computer Vision and Pattern Recognition (CVPR'94), pp. 593-600, June 1994.

22. H.P. Moravec. Towards automatic visual obstacle avoidance. In Proceedings of the 5th International Joint Conference on Artificial Intelligence, Cambridge, Massachusetts, USA, page 584, 1977.

23. S.M. Smith and J.M. Brady. Asset-2: Real-time motion segmentation and shape tracking. Transactions of the IEEE on Pattern Matching and Machine Intelligence, 1995, vol. 17, number 8, pp. 814-820.

24. C. Harris and M. Stephens. A combined corner and edge detector. In Alvey Vision Conference, pages 147-151, 1988.

25. Schmid, Mohr, Bauckhage. "Evaluation of Interest Point Detectors", International Journal of Computer Vision, vol. 37, No. 2, p. 151-172, 2000.

26. H. Asada and M. Brady. The curvature primal sketch, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(1), pp. 2-14, 1986.

27. S. Baker, S. Nayar, and H. Murase. Parametric feature detection. International Journal of Computer Vision, 27(l):27-50, 1998.

28. T. Lindeberg. "Edge detection and ridge detection with automatic scale selection". International Journal of Computer Vision 30 (2), pp. 117-154, 1998.

29. T. Lindeberg. "Detecting Salient Blob-Like Image Structures and Their Scales with a Scale-Space Primal Sketch: A Method for Focus-of-Attention". International Journal of Computer Vision 11 (3), pp. 283-318, 1993.

30. T. Lindeberg. "Feature detection with automatic scale selection". International Journal of Computer Vision 30 (2), pp. 77-116, 1998.

31. 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,1. Orlando, FL.

32. K. Sha&que, M. Shah, A Noniterative Greedy Algorithm for Multiframe Point Correspondence, Transactions of the IEEE on Pattern Matching and Machine Intelligence, 2005, vol. 27, number 1.

33. K. Toyama, J. Krumm, B. Brumitt, and B. Meyers, "Wallflower: Principles and practice of background maintenance," in Proc. Int. Conf. Computer Vision, Corfu, Greece, 1999, pp. 255-261.

34. Anandan P. "Measuring Visual Motion from Image Sequences", Doctoral Dissertation, Computer Science Department, University of Massachusetts, 1987.

35. Burt P. J. and Adelson E. H. "The Laplacian pyramid as a compact image code", IEEE Trans, on Communications 31, pp. 532-540.

36. J.J. Little and A. Verri. "Analysis of differential and matching methods for optical flow", Proc. Workshop on Visual Motion pp. 173-180, 1989.

37. C.D. Kuglin and D.C. Hines, "The phase correlation image alignment method," in IEEE International Conference on Systems, Man and Cybernetics, September 1975, pp. 163-165.

38. E. De Castro and C. Morandi "Registration of Translated and Rotated Images Using Finite Fourier Transforms", IEEE Transactions on Pattern analysis and machine intelligence, Sept. 1987.

39. Eric Grimson and Paul Viola. A forest of sensors. In Proceedings of DARP — VSAM workshop II, November 1997.

40. I. Haritaoglu, D. Harwood, and L. S. Davis, "W4: Real-time surveillance of people and their activities," IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, pp. 809-830, Aug. 2000.

41. C. Stauffer and W. E. L. Grimson, "Learning patterns of activity using real-time tracking," IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, pp. 747-757, Aug. 2000.

42. C. Stauffer and W. E. L. Grimson, "Adaptive background mixture models for real-time tracking," in IEEE Computer Vision and Pattern Recognition,1999, pp. 11:246-252.

43. C. R. Wren, A. Azarbayejani, T. J. Darrell, and A. P. Pentland, "Pfinder: Real-time tracking of the human body," IEEE Trans. Pattern Anal. Mach. Intell., vol. 19, pp. 780-785, July 1997.

44. M. Cristani, M. Bicegi, and V. Murino, "Integrated Region- and Pixel-based Approach to Background Modeling", Proceedings of the MOTION, 2002.

45. Y. Tian, M. Lu, and A. Hampapur. Robust and effcient foreground analysis for real-time video surviellance. In IEEE Conference on Computer Vision and Pattern Recognition, 2005, Volume 1, pp. 1182-1187

46. T. Kanade, R. Collins, A. Lipton, P. Anandan, and P. Burt. Cooperative multisensor video surveillance. In Proceedings of the 1997 DARPA Image Understanding Workshop, volume 1, pp. 3-10, May 1997.

47. T. Kanade, R. Collins, A. Lipton, P. Burt, and L. Wixson, "Advances in cooperative multi-sensor video surveillance," in Proc. 1998 DARPA Image Understanding Workshop, vol. 1, Monterey, CA, Nov. 1998, pp. 3-24.

48. R. Collins, A. Lipton, T. Kanade, H. Fujiyoshi, D. Duggins, Y. Tsin, D. Tolliver, N. Enomoto, and O. Hasegawa, "A system for video surveillance and monitoring: VSAM final report," Robotics Inst., CMU-RI-TR-00-12,

49. Журавлёв Ю. И., Гуревич И. Б. Распознавание образов и распознавание изображений, Распознавание, классификация, прогноз. — 1989. — т. 2.

50. Журавлёв Ю. И. Избранные научные труды. — М. Издательство Магистр, 1998.

51. АсановМ.О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

52. Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.

53. Берж К. Теория графов и её применения. — М.: Издательство иностранной литературы, 1962.

54. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

55. Kuhn Н. W. The Hungarian Method for the Assignment Problem, Naval Res. Legist. Quart., vol. 2, pp. 83-97, 1955.

56. Hopcroft J.E., Karp R. M. An n5//2 algorithm for maximum matchings in bipartite graphs, Proceedings of the 12th Annual Symposium on Switching and Automata Theory (East Lansing, 1971), IEEE Computer Society Press, New York, 1971, 122-125 54, 201.

57. Hopcroft J. E., KarpR.M. An n5/2 algorithm for maximum matching in bipartite graphs //J. SIAM Comput, 1973. vol. 2. - pp. 225-231.

58. Gabow H. N. Implementation of algorithms for maximum matching on nonbipartite graphs, Ph. D. Thesis, Stanford University, 1973.

59. Gabow H. N. An efficient implementation of Edmonds algorithm for maximum matching on graphs //J. ACM. — 1976.- Vol. 23. P. 221-234.

60. Lawler E. L. Combinatorial Optimization: Networks and Matroids, Holt, Rine-hart, and Winston, New York, 1976.

61. Galil Z. Efficient algorithms for finding maximal matching on graphs // Lect. Notes Comput. Sci, 1983. Vol. 159. - pp. 90-113.

62. Galil Z., Micali S., Gabow II. An 0(EV logV) algorithm for finding a maximal weighted matching in general graphs, SI AM Journal on Computing, v.15 n.l, p.120-130, Feb. 1986

63. Gabow H. N. "Data structures for weighted matching and nearest common ancestors with linking", in: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, New York, 1990, pages 434-443.

64. Свами M., Тхуласираман К. Графы, сети и алгоритмы. —- М.: Мир, 1984.

65. Micali S., Vazirani AV. V. An 0{\/VE) algorithm for finding maximum matching in general graphs // Proc. 21st Ann. Symp. on the Foundations of Сотр. Sci., Long Beach, California: IEEE. 1980. - P. 17-27.

66. Майника Э. Алгоритмы оптимизации па сетях и графах. — М.: Мир, 1981.

67. Пападимитриу X., СтайглицК. Комбинаторная оптимизация: Алгоритмы и сложность. — М.: Мир, 1985.

68. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Пер. с англ. под. ред. А. Шеня. — М.: МЦНМО: БИНОМ. Лабораториязнаний, 2004. — 2-е изд.

69. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

70. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Издательский дом "Вильяме", 2000.

71. Стенли, Ричард. Перечислительная комбинаторика. — М.: Мир, 1990.

72. Стенли, Ричард. Перечислительная комбинаторика: Деревья, производящие функции и симметрические функции. — М.: Мир, 2005.

73. Эндрюс Г. Теория разбиений. Перев. с англ. — М.: Наука. Главная редакция физико-математической литературы, 1982.74., Системы охранного телевидения,http://www.orbitacom.ru/decision/tse/videocontrol75. http://elvees.ru/index.php?id==241

74. Ван дер Варден Б. Л., Математическая статистика. — М.: Издательство иностранной литературы, 1960

75. Вентцель Е. С. Теория вероятностей. — М.: Издательство «Наука», 1969

76. Колмогоров А. Н. Основные понятия теории вероятностей. — М.: Издательство «Наука», 1974

77. Калиткин Н. Н. Численные методы. — М.: Наука, 1978.

78. Нечепуренко М. И. Итерации вещественных функций и функциональные уравнения. — Новосибирск, 1997.

79. АхиезерН.И. Лекции но вариационному исчислению. — М.: Государственное издательство техиико-теоретической литературы, 1955

80. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы, 3-е изд., перераб. и доп. — М.: БИНОМ, Лаборатория знаний, 2003.

81. Кнут Д. Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с англ. — М.: Издательский дом «Вильяме», 2002.

82. Кнут Д. Э. Искусство программирования, том 4, выпуск 3: генерация всех сочетаний и разбиений. : Пер. с англ. — М.: Издательский дом «Вильяме», 2007.

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

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

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

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

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

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

89. Малистов А. С. «Обнаружение движения по параболе с учётом пропуска кадров в системе видеонаблюдения реального времени», М.: из-во «Компания Спутник+», научно-технический журнал «Естественные и технические науки», №5, 2007, с. 195-196.

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

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

92. А. С. Малистов, A.A. Солохин, A.B. Хамухин, «Слежение за целями в мультисенсорных системах видеонаблюдения с компьютерным зрением», труды XLVIII научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук», Москва, 2005.

93. С.Т. Иванченко, И.А. Канн, К.В. Лунин, А. С. Малистов, Я.Я. Пет-ричкович, A.A. Солохин, В.П. Сомиков, A.B. Хамухин, «Система обеспечения безопасности и мониторинга мобильных объектов». //Патент РФ на полезную модель №36315, бюл. №7, 2004.

94. С.Т. Иванченко, И.А. Канн, К.В. Лунин, А. С. Малистов, Я.Я. Пет-ричкович, A.A. Солохин, В.П. Сомиков, A.B. Хамухин, «Система обеспечения безопасности и мониторинга мобильных объектов». //Патент РФ №2265 531, бюл. №34, 2005.

95. И.А. Кан, К.В. Лунин, А. С. Малистов, Я.Я. Петричкович, A.A. Солохин, В.П. Сомиков, A.B. Хамухин, «Система и способ автоматизированного видеонаблюдения и распознавания объектов и ситуаций». //Патент РФ на полезную модель №36912, бюл. №9, 2004.

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