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

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

МЕЛИХОВ Михаил Васильевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМИЧЕСКОГО АППАРАТА ОБРАБОТКИ ВИДЕОИНФОРМАЦИИ, РАСПОЗНАВАНИЯ ОБЪЕКТОВ И СЦЕН В ПРЕДОПРЕДЕЛЕННОЙ СИТУАЦИИ

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

АВТОРЕФЕРАТ диссертации на соискание учетной степени кандидата технических наук

Москва 2005

Работа выполнена на кафедре «Проблемы управления» Государственного образовательного учреждения высшего профессионального образования (ГОУ ВПО) «Московский государственный институт радиотехники, электроники и автоматики (технический университет)»

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

Попов Вадим Владимирович

Официальные оппоненты: д.т.н., профессор

Дорри Манучар Хабибуллаевич

к.т.н., доцент

Кравченко Вадим Борисович

Ведущая организация: Институт электронных

управляющих машин (ИНЭУМ)

Защита состоится «/6» Шок Л 2005 г. в часов в

аудитории Г-412 на заседании диссертационного совета Д.212.131.03 при ГОУ ВПО «Московский государственный институт радиотехники, электроники и автоматики (технический университет)» по адресу: 1 ] 9454, Москва, пр-т Вернадского, д.78.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Московский государственный институт радиотехники, электроники и автоматики (технический университет)».

Автореферат разослан « S» S&f 2005 г. Ученый секретарь

диссертационного совета О^с—

к.т.н., доцент Тягунов O.A.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования.

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

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

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

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

лема, когда происходит

одно-

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

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

Цель работы.

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

Задачи исследования.

В соответствии с указанной целью, в диссертационной работе решаются следующие задачи:

• анализ существующих методов и проблем обработки видеоданных с целью выделения информации и разработки функциональной схемы работы автоматизированной системы видеонаблюдения;

• построение эффективных алгоритмов и методов выделения объектов на стадии первичной обработки видеоданных;

• разработка последовательности алгоритмов выделения инфор-

• л) *

А • '

А" <

мации о внутренней структуре объектов наблюдения (людей) и исследование особенностей применения алгоритмов формирования информации о структуре объекта на основе построения «топографии» силуэта объекта;

• разработка алгоритмов и исследование свойств «скелетного» представления объектов, разработка математических моделей формы записи скелета объекта в виде информационного образа-схемы (ИОС);

• разработка методики, алгоритмического аппарата и информационной компоненты сравнения ИОС объекта с набором эталонных образов - личин, выражающих элементы невербальной информации об объектах живой природы;

• проведение программных экспериментов и обработка результатов с целью выявления возможностей разработанного алгоритмического аппарата и выделения показателей оценки сравнения ИОС.

Методы исследования.

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

Программное и информационное исследование работы алгоритмов обработки видеоинформации, распознавания объектов и сцен осуществлялось на ЭВМ с применением прикладных математических и офисных программ: MathCad, MathLab, MS Access, а также с использованием систем программирования: Visual Basic for Applications и Borland С++ Builder.

Научная новизна результатов работы заключается в следующем:

• предложен метод выделения информации, основанный на построении новой характеристики объекта наблюдения - топографии силуэта, что позволяет исследовать силуэт по характеристическим элементам представляющей его поверхности топографии: локальным максимумам, линиям уровня, «хребтам» и «перевалами»;

• разработан метод выделения данных о форме и структуре объекта, основанный на построении остовного дерева силуэта -«скелета» объекта, хранящего невербальную информацию о позе и действиях объекта наблюдения (человека);

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

• разработаны теоретические основы регуляризации скелетных линий и сформирован метод получения ИОС на основе скелетного описания;

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

Основные положения, выносимые на защиту:

• метод описания структуры силуэтного изображения объекта, формируемого на основе поверхности топографии;

• алгоритм формирования скелетного описания структуры объекта;

• методы регуляризации скелетных линий и построения информационного образа схемы;

• метод сопоставления двух ИОС с целью выделения информации об объектах и сцене.

Практическая ценность.

Практическая значимость результатов работы состоит в следующем:

• разработана функциональная схема работы автоматизированной системы наблюдения;

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

- детектирование движения;

- выделение силуэта;

- построение топографии силуэта;

- формирование структуры объекта наблюдения в виде «скелета»;

- регуляризация скелетных линий и построение по скелетному описанию ИОС;

- сравнение ИОС объекта с набором эталонных личин с целью распознавания сцены.

Личный вклад.

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

Результаты диссертации были использованы: при выполнении НИР № А04-3.16-785 Конкурсного Центра фундаментального естествознания г. Санкт-Петербург «Разработка автоматизированной системы распознавания сцен в задачах видеонаблюдения»; при внедрении системы видеоконтроля в местах общего пользования на территории Южного и Юго-Восточного округов города Москвы; при проектировании системы видеонаблюдения Научно-техническим центром автоматизированных систем жизнеобеспечения и безопасности. Отдельные результаты работы были использованы в учебном процессе кафедры «Технических и информационных средств систем управления» МИРЭА при создании курса «Защита информации и информационная безопасность».

Апробация результатов работы

Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях:

• межвузовский научно-методический семинар МИРЭА «Наукоемкие технологии образования», Москва, 2002;

• LVI, LVII, LVTII, LIX научные сессии, посвященные Дню Радио РНТОРЭС им. A.C. Попова (Москва, 2001, 2002, 2003, 2004 гг.);

• научно-технические конференции профессорско-преподавательского, научного и инженерно-технического со-

става МТУСИ (Москва, 2002, 2003, 2004, 2005 гг.);

Публикации.

Основные результаты диссертации отражены в 11 публикациях.

Структура и объем работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы (110 наименований) и 2 приложений. Объем основного текста составляет 146 страниц, 25 таблиц и 70 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В составе проблемы распознавания сцен была выделена важная в практическом отношении группа задач видеонаблюдения в предопределенной ситуации. В указанную группу входят актуальные задачи, связанные с распознаванием сцен при участии людей, такие как видеонаблюдение в местах общественного пользования; охранные системы и «интеллектуальный дом». Особенностью распознавания предопределенных сцен полагается возможность их классификации на основе данных о распознавании образов - участников сцены. При этом важным источником информации о содержании сцен с предопределенной ситуацией могут стать проявления невербального общения людей (позы, жесты, движения).

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

г^"---------

Устройства наблюден« контроля и сопровождения

- микрофоны.

- детекторы движем*!,

- детекторы дыма,

- кодовые замки, -консоги, -итл

- тдююпиры

Механизмы реагирования

- запорные механизмы;

- система управпен« освещением,

- система пожаротушен«, -итд

Устройства оповвшееия.

- сигнашэация

- система оповещен« правоохранительных органов, -итд

Автоматизированный проареымный комплекс обработки видеоинформации

Рис.1

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

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

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

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

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

г) Д)

Рис.2

В работе описание границ произвольной области производилось с помощью диаграмм (рис.3), лучи которых длины dk проведенные из некоторой базовой точки под углом и равномерно

разбивают диапазон круговой диапазон [0;2;г].

Анализ возможностей различных подходов, связанных с построением формального описания контура, проводился для математических моделей интерполяции, кусочной линеаризации, аппроксимации по методу наименьших квадратов и векторизации по методу Хафа. В частности, для метода кусочной линеари-Рис.З зации Сц„ было получено со-

отношение (1), связывающее точность метода с определяющим область диаграммным описанием.

max Id(u) - dLIN(u)\ < maxi - dk ие[0;2л\ к V

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

min [maxfix-хШ-/!)] при (х,у)е Sq

(x',y')eG _

min [max(jx - х\\у - j'))] при (х,>>)(2 V

-Шы-täf) (О

Т{Х,У) =

(2)

где б - множество точек контура, ^ - множество точек силуэта. Разрабатывается волновой алгоритм построения топографии не-

посредственно на основе представляющего область массива точек - пикселей растра.

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

Рис.4

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

Рис.5

ный алгоритм восстановления контура области по диаграммному описанию с любой степенью точности (рис.5).

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

В третьей главе на основе введенного понятия топографии области, представляющей объект видеонаблюдения, построен и программно реализован новый алгоритм скелетизации изображения (рис.7а). Скелет, получаемый в результате работы алгоритма, основанного на волновом методе, представляет собой граф - ос-товное дерево (рис.2г на стр.11) и состоит из попарно смежных, образующих линии точек растра, обладающих свойством равно-удаленности от двух и более границ области.

Обоснована информационная сопоставимость формируемой

а)

б)

в)

Рис.6

Рис. 7

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

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

• в терминах слов над алфавитом переходов в коде Фримена (рис 8а);

• в виде 8-позиционного вектора спектра переходов (рис 86);

• в терминах параметрического задания протяженности (1) и возвышения (Ь) (например, переход в точку, расположенную «на юго-восток» от данной, характеризуется 1-1, А=-/).

Исследованы возможности предложенных моделей и разработаны алгоритмические механизмы их применения. Разработаны теоретические основы алгебраического описания и определены показатели численного сравнения скелетных линий (например, по спектру линии на рис. 86).

В четвертой главе на основе скелетного представления изображения была осуществлена разработка методов и средств формирования и распознавания информационного образа-схемы (ИОС) объекта.

Были разработаны и исследованы операции регуляризации скелетных линий, позволяющие упростить их представление при сохранении основных особенностей формы и направленности. Например, в табл.1 для линии из рис.8 представлены 3 операции неразрушающей (сохраняющей положение концевых точек) ре- (

гуляризации - СЭ, СП и СС, а также разрушающей, СД - регуляризации.

Табл. 1

Виды регуляризации Операция Результат

В классе спектрально эквивалентных (СЭ) линий. Группирование одноименных переходов 32140962

В класс спектрально приведенных (СП) линий Исключение взаимно обратных переходов 32о14о09о62

В классе спектрально сокращенных (СС) линий. Сведение к мин. возможному количеству переходов 14о07

Спектрально доминирующая (СД)-регуляризация линии Выбор главного из переходов О9

!

На основе построения алгебраической теории соединений регуляризованных линий скелета был предложен алгоритм формирования информационного образа-схемы (ИОС), образующегося в виде матрицы Е описания путей, попарно соединяющих концевые точки исходного скелета (рис.2д на ' стр.11). Пример такой матрицы для ИОС на рис.9а, приведен в

* табл. 2.

Табл. 2

1 3 5 6 7

1 0 ЬиЬ» * 65554445555500 07 ЬйЬмЬ«» 65555656566566 56654454 ЬвЬ»" 65556666601111 0 65555656566561 00100767767

3 ЬмЬц -34441111100011 12 0 ЬзгЬцЬ«" 34441111100056 56566566566544 54 ЦгЬм® 34441111100066 666011110 ЬзгЬ241_,47 = 34441111100056 56566561001007 67767

5 Ь54Ь42Ь21 ■ 01001221221221 21211112 ЬмЦгЬгз = 01001221221221 21214445555500 07 0 ЬмЦгЬг« = 01001221221221 21216666601111 0 I'541^47 01001221210010 0767767

6 ЬбгЬг! = 45555422222111 2 ЬбгЬй " 45555422222444 555550007 Ь«Ь241<45 • 45555422222565 65665665665445 4 0 Ь«Ь24Ь47 т 45555422222565 65665610010076 7767

7 Ьт^гЬг! = 32332344544521 22121211112 ЬтдЦг^з = 32332344544521 22121214445555 50007 Ь74Ь45 = 32332344544565 6654454 Ьт^гЬй = 32332344544521 22121216666601 1110 0

Для двух ИОС, заданных квадратными матрицами путей

Е( 1)

и соответственно размерности (ЛТхДг) и (МхМ), в

работе предложен метод оценки непохожести, опирающийся на оценки попарного сравнения путей. Так, элементы а¡^ матрицы

А размерности (Ы х М), равные:

^-яяжмь*®) (3)

(где Ьрд = - вычисленная некоторым способом

непохожесть путей Ь^ и ¿(2) в ИОС (1) и (2) соответственно),

характеризуют суммарную непохожесть линий двух ИОС, если в одном из них корнем дерева (от которого строилось описание) была вершина г, а в другом - корень был в вершине к.

Учитывая, что меньшим значениям а, к суммарной непохожести соответствуют более схожие описания соответствующих линий ИОС, можно полагать, что похожесть двух ИОС будет характеризоваться величиной наименьшего паросочетания, построенного по элементам матрицы А. При этом определяющее наименьшее паросочетание Р на матрице А находится решением задачи о назначениях:

(построенное выбором элементов а1к матрицы А, обладающих

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

каждого ИОС, и в матрице А подмножество I строк или подмножество К столбцов не содержат выбранных в Р элементах.

На основе реше-

ния задачи о назначениях были построены и экспериментально исследованы алгоритмический аппарат и информационная компонента, обеспечивающие формирование, хранение и сопоставления ИОС объектов видеонаб-

а)

б)

Рис. 9

людения с имеющимися эталонными образами - личинами, наделенными определенными свойствами. Например, на рис. 9 отображены два ИОС, представляющих соответственно личины «человека быстро бегущего слева - направо» (рис.9а) и «человека идущего слева - направо» (рис.9б).

Проведенные программные эксперименты сопоставления ИОС при различных способах оценки непохожести их линий позволяют сделать вывод о работоспособности предложенного метода. Для качественно похожих ИОС сопоставление оказывается верным при любом способе оценки непохожести линий. Для визуально отличающихся ИОС сопоставление может оказаться неверным или неустойчивым по отношению к малым изменениям скелета. Вместе с тем во всех случаях выявление ошибки легко может быть произведено с помощью «кругового теста», анализирующего очередность кругового перечисления вершин объекта «до» и «после» сопоставления.

Для оценки правильности и устойчивости формируемого решения в качестве меры достоверности (правильности) сопоставления двух ИОС предлагается рассматривать две величины:

- показатель достоверности распознанного -

, (5)

/ \JLiel ¿¿кек"^ )

- показатель возможности нераспознанного -

V -V — '

2-ге/ Ьк^К а1,к

характеризующие соответственно уровень непохожести линий ИОС в распознанной (сопоставленной) и нераспознанной части.

Значения показателя Б - достоверности распознанного тем больше, чем более непохожими являются сопоставляемые ИОС и чем более неустойчивым (неправильным) является их сопоставление. Чем больше величина V, тем более устойчивым является полученное решение. В целом, устойчивым может считаться решение, для которого выполняется условие: В<У.

Иллюстрирующий возможности метода эксперимент с при-

менением показателей (5) и (6) по сопоставлению ИОС объектов рис.2 (стр.11) с личинами рис.9, заключающийся в выяснении вопроса «участники сцены бегут или идут», позволил классифицировать все объекты как «бегущие». Также, попарное сопоставление с применением показателей (5) и (6) ИОС участников сцены рис.2 подтвердило внутреннее единство объектов - участников сцены.

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

Алпроисимация,линвнваризация, интерполяциявекториэация[-

ОпределениелокальньюАЛАХ тогкхрафии

(свьеют нежилой прировьф

Вьделениесвяэногоподон-еа точек равнудаленных от двухи более границ

(чвповт и фушш обммль/ »той природы)

Рис.10

В приложении I приведено описание программного комплекса, реализующего разработанные алгоритмы обработки видеоданных. В приложении II. 1 приводится пример построения ИОС по трем фигурам. В приложении II.2 перечисляются предложенные оценки сравнения линий ИОС и дается описание информационных преобразований, связанных с формированием матрицы С сопоставления. В приложении II.3 приводятся результаты 56 экспериментов сопоставления качественно различных образов, позволяющие оценить возможности метода сравнения ИОС при различных способах сравнения линий. В приложении II.4. оценивается чувствительность показателей достоверности распознанного к малым изменениям линий ИОС. В приложении II.5 проводится распознавание образов и вытекающее из него распознавание сцены. В приложении II.6 рассмотрено получение оценки внутреннего единства объектов - участников сцены.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

При достижении поставленной цели и решении сформулированных задач диссертационной работы получены следующие

основные научные и практические результаты:

1. Разработаны общие принципы работы автоматизированной системы видеонаблюдения, производящей (без участия оператора) распознавание сцен в предопределенных условиях на основе выделения невербальной информации, связанной с объектами - участниками сцены.

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

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

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

5. Определены методы регуляризации (упрощения) скелетных линий и построена алгебраическая система описания их соединений. Разработаны оценки и способы сравнения регуляризо-ванных линий.

6. Построена новая форма описания скелетного представления объекта в виде информационного образа-схемы (ИОС).

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Шакин В.Н., Мелихов М.В., «Информационная модель динамической загрузки сети связи в задаче управления надежностью», Труды LVI научной сессии, посвященной Дню Радио РНТОРЭС им. A.C. Попова, М., 2001.-т.1, с. 136-138.

2. Шакин В.Н., Мелихов М.В., «Исследование взаимосвязи реорганизации сети с задачей формирования загрузки», Научно-техническая конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, М., 2002. -с. 400 - 401.

3. Шакин В.Н., Мелихов М.В., «Разработка программных средств имитации информационных характеристик видеоданных», Труды LVII научной сессии, посвященной Дню Радио РНТОРЭС им. A.C. Попова, М., 2002. -т.1, с. 281-283.

4. Попов В.В., Мелихов М.В., «Имитационный подход в проектировании средств обработки видеоинформации», Межвузовский научно-методический семинар МИРЭА «Наукоемкие технологии образования», М., 2002. -с. 44 - 46.

5. Шакин В.Н., Мелихов М.В., «Разработка алгоритмов упорядочения в системах с увеличением производительности», Научная конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, М., 2003. - кн.З, с. 58 - 59.

6. Попов В.В., Мелихов М.В., «Оценка производительности человеко-машинной системы видеонаблюдсния», Труды LVII1 научной сессии, посвященной Дню Радио РНТОРЭС им. A.C. Попова, М„ 2003- т.1, с.120-122.

7. Мелихов М.В., «Об одном подходе к описанию видеоданных, объектов и сцен», Научная конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, М., 2004 - с. 252 - 253.

8. Мелихов М.В., «Построение лабораторного практикума по освоению методов распознавания образов и анализа сцен», Научная конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, М., 2004. - с. 165.

9. Мелихов М.В., «Описание подходов и алгоритмов регистрации активности в задачах видеонаблюдения», Труды LIX научной сессии, посвященной Дню Радио РНТОРЭС им. A.C. Попова, М., 2004. - т. 1, с. 97 - 99.

10. Попов В.В., Мелихов М.В., «Регистрация активности в задачах видеонаблюдения», журнал «Авиакосмическое приборостроение», №10, М., 2004.-е. 21-27.

11. Мелихов В.О., Мелихов М.В., «Разработка методов обработки и распознавания видеоданных об объектах сцены», Научная конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, М., 2005. - с. 143 - 144.

Подписано в печать 25.04.2005. Формат 60x84 1/16.

Бумага офсетная. Печать офсетная. Усл. печ. л. 1,16. Усл. кр.-отт. 4,64. Уч.-изд. л. 1,25. Тираж 100 экз. Заказ 326

Государственное образовательное учреждение высшего профессионального образования "Московский государственный институт радиотехники, электроники и автоматики (технический университет)" 119454 Москва, пр-т Вернадского, 78.

t-8750

РНБ Русским фонд

2006-4 15547

Введение.

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

§1. Выделение основных категорий, последовательности стадий и особенностей обработки видеоинформации.

1.1. Выделение особенностей обработки видеоинформации.

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

§2.Исследование и разработка алгоритмов регистрации активности в задачах видеонаблюдепия.

2.1. Анализ принципов функционирования традиционного алгоритма детектора движения.

2.2. Исследование параметров и возможностей настройки алгоритма регистрации активности.

2.3. Разработка методов улучшения характеристик алгоритма регистрации активности.

§3.Исследование и разработка алгоритмов выделение силуэтов.

3.1. Исследование возможностей выделенияя силуэта методом вычитания фона.

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

§4. Анализ возможностей математических моделей описания силуэта для представления объекта видеонаблюдепия.

4.1. Определение и назначение векторизованого представления растрового изображения.

4.2. Исследование возможностей интерполяционных моделей для описания формы объекта.

4.3. Оценка погрешности линеаризационного приближения контура.

4.4. Исследование возможностей моделей аппроксимации контура методом наименьших квадратов и преобразования Хафа.

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

Глава 2. Формирование модели выделения структуры области силуэта и исследование информационных свойств точек.

§1. Определение топографии силуэта и разработка алгоритма ее формирования.

1.1. Обоснование формулы расчета топографии силуэта.

1.2. Волновой алгоритм нахождения топографии.

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

§2. Определение места и роли базовых точек в структуре произвольной области силуэта

2.1. Исследование методов отыскания позиций размещения базовых точек.

2.2. Уточнение диаграммного описания в случае произвольной области силуэта.

2.3. Исследование алгоритмов построения структуры области силуэта в виде правильного остовного дерева.

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

§3. Особенности выделения структуры области на растре.

Глава 3. Разработка и исследование структуры изображения на основе скелетизации.

§ 1. Разработка алгоритма скелетизации методом постепенной детализации срезов.

1.1. Описание основных принципов построения скелета изображения.

1.2. Реализация алгоритма на псевдоязыке.

1.3 Преимущества и недостатки алгоритма скелетизации.

§2. Определение взаимосвязи скелетной структуры с диаграммным описанием области

§3. Разработка методов выделения характеристических точек на скелете.

§4. Разработка автоматно-лингвистических, параметрических, спектральных моделей и теоретических основ алгебраического описания скелетных линий.

4.1. Разработка автоматно-лингвистических, параметрических и спектральных моделей скелетных линий.

4.2. Разработка теоретических основ алгебраического описания и показателей сравнения скелетных линий.

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

§1. Разработка и исследование операций регуляризации скелетных линий.

§2.Разработка методов оцеики и снижения рассогласования исходных и регуляризованных скелетных линий.

§3. Разработка методов формирования информационного образа-схемы объекта па основе регуляризованных линий скелета.

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

3.2. Разработка алгоритма формирования описания информационного образа-схемы.

§4. Разработка методов оценки похожести и средств распознавания информационных образов-схем.

4.1. Определение показателей сравнения двух информационных образов-схем.

4.2. Разработка алгоритмического аппарата и информационной компоненты сопоставления образов-схем.

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

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

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

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

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

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

Все сказанное в полной мере относится и к видеинформации, которая наряду с лексическими данными (текстами, гипертекстами, таблицами) и аудиоданными составляет основную часть наполнение информационной сферы [41].

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

Видеоинформация является наиболее информативной формой описания. Вместе с тем, эту форму отличает также смысловая избыточность [7, 42, 100] и большие объемы представляющих информацию данных (к тому же, сложно поддающихся сжатию [103, 33]).

Формирование видеоданных, происходит в реальном времени протекания процесса (или во времени, масштаб которого всегда кратен реальному времени), т.е. эта форма является наиболее удобной для мониторинга любых реальных процессов (формирования видеонаблюдений).

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

Для человека видеоданные, по сути, являются, главным источником получения информации об окружающем мире. Известно, что около 80-85% от всей информации поступает к человеку через органы зрения.

В культурном наследии человечества к разряду видеоинформации помимо всевозможных рисунков, схем и картин (от наскальных до компьютерных) относится вся фото кино и видео продукция. На сегодняшний день даже только оцифрованные видеоданные (т.е. картины, рисунки, схемы, фотографии, фильмы и голограммы в электронном представлении) составляют практически большую часть машинных мировых информационных ресурсов, по крайней мере в побайтном выражении. В настоящее время только форм электронного представления видеоинформации насчитывается несколько десятков (tif, jpg, bmp, gif, mpeg и т.д.). Причем за счет постоянного совершенствования процессов записи и хранения видеоинформации количество форм представления постоянно увеличивается.

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

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

Семантика видеоданных - контекстна [10, 74], т.е. определяется фреймом, кадром или сценой, в рамках которой происходит подлежащее распознаванию смысловое действие. И если на сегодняшний день говорить о распознавании смысла произвольных (пускай даже реальных сцен), по-видимому, преждевременно, то практическая ценность алгоритмов распознавания поведения людей в конкретной обстановке - не вызывает сомнения. В дальнейшем видеоданные поведения людей в конкретной обстановке с неизменным местом действия, фоном и освещенностью будем называть сценами с предопределенной ситуацией, указывая на ограниченный характер разворачивающихся в этих сценах реальных действий. Например, к таким сценам можно отнести видеонаблюдепия охранных систем; в местах общественного пользования (в подъездах и вестибюлях, в холлах и переходах, на лестничных маршах, и т.д.) и на транспорте (в кабинах лифтов, в вагонах, на эскалаторе и т.д.), а также большую часть информации, с которой работают системы «интеллектуального дома».

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

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

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

В соответствии с указанной целью, в диссертационной работе решаются следующие задачи:

• анализ существующих методов и проблем обработки видеоданных с целью выделения информации и разработки функциональной схемы работы автоматизированной системы видеонаблюдения;

• построение эффективных алгоритмов и методов выделения объектов на стадии первичной обработки видеоданных;

• разработка последовательности алгоритмов выделения информации о внутренней структуре объектов наблюдения (людей) и исследование особенностей применения алгоритмов формирования информации о структуре объекта на основе построения «топографии» силуэта объекта;

• разработка алгоритмов и исследование свойств «скелетного» представления объектов, разработка математических моделей формы записи скелета объекта в виде информационного образа-схемы (ИОС);

• разработка методики, алгоритмического аппарата и информационной компоненты сравнения ИОС объекта с набором эталонных - образов личин, выражающих элементы невербальной информации об объектах живой природы;

• проведение программных экспериментов и обработка результатов с целью выявления возможностей разработанного алгоритмического аппарата и выделения показателей оценки сравнения ИОС. Основные положения, выносимые на защиту разработанный метод описания структуры силуэтного изображения объекта, формируемого на основе поверхности топографии; алгоритм формирования скелетного описания структуры объекта; методы регуляризации скелетных линий и построения информационного образа -схемы объекта; метод сопоставления двух ИОС с целью выделения информации об объектах и сцене.

Выводы по главе 4

1) Построена алгебраическая система регуляризации скелетных линий. Выделены основные классы регуляризирующих преобразований и определены их характеристики. Конструктивно доказана автоматная реализуемость преобразований регуляризации.

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

3) Введено понятие информационного образа-схемы (ИОС) объекта и разработаны алгебраические методы и алгоритм формирования ИОС на основе регуляризованных линий скелета. С позиций введенного понятия ИОС задача распознавания сцены рассмотрена в плапе анализа структуры взаимодействий между участниками сцены.

4) Определены показатели оценки похожести регуляризованных линий. Разработан алгоритмический аппарат и структура информационной компоненты обеспечивающие сопоставления двух ИОС (на основе отыскания оптимального паросочета-ния их концевых вершин).

5) Проведено экспериментальное исследование возможностей алгоритмического аппарата сопоставления ИОС. Введены показатели устойчивости решения, достоверности распознавания, а также построен тест проверки правильности сопоставления ИОС с известным образцом (личиной). Определены рекомендации по применению показателей сравнения регуляризованных линий. Установлены требования к формированию скелетных описаний объекта. Работоспособность метода продемонстрирована на примерах сопоставления ИОС реальных объектов с подготовленными образцами, а также на примере оценки единства участников сцены.

Заключение

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

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

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

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

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

5. Определены методы регуляризации (упрощения) скелетных линий и построена алгебраическая система описания их соединений. Разработаны оценки и способы сравнения регуляризованных линий.

6. Построена новая форма описания скелетного представления объекта в виде информационного образа-схемы (ИОС), состоящего из описания регуляризованных скелетных линий и построенных из них путей, попарно определенных между концевыми вершинами скелета.

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

8. Полученные результаты позволяют уточнить общую структуру информационной взаимосвязи компонентов в алгоритмическом аппарате анализа и распознавания объектов и сцен, представленную на рис.4.21. Так на основе новой введенной характеристики - топографии силуэта выделима структура диаграммного описания (по которому с любой степенью точности восстанавливается контурное представление объекта); а также формируется скелетное описание, по которому строится специально разработанная форма — ИОС, пригодная для распознавания элементы невербальной информации.

Аппроксимация,линенеаризация, интерполяциявекторизация объекты неживой природы)

ОпределениелокальныхМАХ топографии

Силуэт(контур) объекта

Топография

Выделениесвязногоподмн-ва точекравнудаленныхотдвухи болееграниц

Структуры диаграммного описания

Поиск Мах функции профиля

Приближенное описание контура

Скелетное описание

Определение характеристических точек^

Регуляризацияскелетных линий

ИОС человек и другие объекты живой природы)

Рис.4.21

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

1. Абрамов J1.M., Капустин В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. - 184 с.

2. Айзерман М.А.,Гусев Л.А., Розоноэр Л.И.,Смирнова И.М., Таль А.А. Логика. Автоматы. Алгоритмы. М.,Физматгиз, 1963, 556 е., ил.

3. Айра Пол. Объектно-ориентированное программирование на С++. Изд.:Бином, Невский Диалект, 2001. 464 с.

4. Айриг С., Айриг Э. Подготовка цифровых изображений для печати. Мп.: ООО "Попурри", 1997. 192 е., ил

5. Айриг С., Айриг Э. Сканирование профессиональный подход. Мн.: ООО "Попурри", 1997.- 176 е., ил.

6. Акоф Р., Сасиепи М. Основы исследования операций: Пер.с англ.- М.:Мир, 1971

7. Александров В.В., Горский Н.Д. Представление и обработка изображений: Рекурсивный подход,-Л.: Наука, 1985.-192 с.

8. Александров П.С. Лекции по аналитической геометрии М.: Наука, 1968 — 911 е., ил.

9. Андервуд, Гейтс (Underwood S, Gates С.). Visual Learning and Recognition by Computer, TR-123, Elect. Res. Center University of Texas, 1972.

10. Андреев В.П., Белов Д.А., Вайнштейн Г.Г., Москвина Е.А. Эксперименты с машинным зрением. М.: Наука, 1987. -128 с.

11. Архангельский А.Я. Программирование в С++ Builder 5. Изд.: Бином, 2001. 1152 с.

12. Асапов М.О., Баранский В.А., Расин В.В.Дискретная математика: Графы матроиды, алгоритмы. Ижевск, НИЦ "РХД", 2001- 288 с.

13. Банди Б. Основы линейного программирования: Пер. с англ. М.: Радио и связь, 1989,- 176 е., ил.

14. Баяковский Ю.М. (Yu. М. Bayakovskii). Convergence of Computer Graphics and Machine Vision (From the Editor of the Special Issue). Programming and Computer Software, Vol. 30, No. 5, 2004, p. 241.

15. Баяковский Ю.М., Галактионов B.A. О некоторых фундаментальных проблемах компьютерной (машинной) графики, Информационные технологии и вычислительные системы, № 4, 2004, с. 3-24

16. Баяковский Ю.М., Галактионов В.А. Современные проблемы компьютерной (машинной) графики. Будущее прикладной математики. Лекции для молодых исследователей. М.: Едиториал УРСС, с. 445-473, 200517.