Размещено на http://www.allbest.ru/

Структурный метод распознавания динамических сцен

А.В. Ганичева, А.В. Ганичев

Задача структурного распознавания динамических процессов является актуальной задачей коммуникационных процессов. В настоящее время идет активная разработка систем распознавания эмоционального состояния человека на основе нечётких систем и мягких вычислений (Бобков и др., 2009: 143-151, Розалиев, 2009: 121-147), большое внимание уделяется распознаванию динамических жестов на основе «Скрытых Марковских моделей» (Rigoll, Kosmala, Eickeler, 1997: 69, 80), в работе (Девятков, 2009) предложен метод нечёткого распознавания динамических образов на примере динамических жестов, основанный на использовании модели нечётких конечных автоматов при сравнении распознаваемых жестов с эталонами. В работе (Ганичева, Ганичев, 2012) предложен метод структурно - гармонического анализа движущихся объектов.

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

Основные понятия теории формальных грамматик и языков взяты из (Гладкий, 1973: 25-39).

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

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

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

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

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

1)

динамический эмоциональный задача

здесь, вообще говоря, последовательности могут быть и пустыми, но на первом месте в последовательности 1), по условию задачи, должен стоять символ «»; аналогично

Введем основные множества символов. Пусть множество нетерминальных символов А1, В1, С1, D1, … (шесть таких групп символов с индексами 1-6); I-начальный символ; - пустая цепочка; терминальные символы: <жилой дом >, <больница >, <почта >, <магазин>.

Здесь схема I описывает последовательность:

<жилой дом > <больница > <жилой дом >

<магазин > <жилой дом > < почта > <жилой дом >,

где 1;

схема II описывает последовательность:

<жилой дом > < больница > <жилой дом >

< почта > <жилой дом > <магазин > <жилой дом >,

где 1;

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

Таким образом, слово

= <жилой дом > <почта> <магазин><больница ><жилой дом > принадлежит языку построенной автоматной грамматики, а слово

= <жилой дом > <почта > <жилой дом > этому языку не принадлежит.

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

Для имитации движения по посёлку за данный промежуток времени обозначим через - количество людей (машин), движущихся по тротуару на данном временном промежутке слева направо, через - движущихся справа налево. Введем в рассмотрение нетерминальные информационные символы , означающие, что в данный момент времени данный объект (жилой дом, магазин, почту, больницу) миновали i людей , движущихся слева направо, j машин , движущихся слева направо, k людей , движущихся справа налево, l машин , движущихся справа налево, r людей , стоящих на месте, s машин , стоящих на месте. К правилам грамматики, построенной для посёлка, добавляются правила:

Рассмотрим пример. Пусть n=2, m1=2, m2=3, m3=1, т.е. рассматривается посёлок вида: ддбддтдддпд. Допустим, что p1=2, p2=2, p3=1, q1=1, q2=1, q3=4. Тогда цепочка дде(1,1,0,0,0,0)бде(1,0,1,1,0,0)дмдде(0,0,1,1,1,2)дпе(0,0,1,1,0,2)д означает, что в рассматриваемый промежуток времени мимо второго дома (считая слева направо) прошёл один человек и проехала одна машина, мимо первого дома после больницы (считая слева направо) прошёл один человек в направлении слева направо и один человек в направлении справа налево, мимо этого же дома проехала машина в том же направлении, мимо второго дома после магазина (считая слева направо) прошёл пешеход в направлении справа налево и проехала машина в том же направлении, кроме того, один пешеход и две машины в рассматриваемый промежуток времени стояли у этого дома, наконец, мимо почты в направлении справа налево прошёл пешеход и проехала машина, две машины в этот промежуток времени стояли у почты.

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

1,2,…,p1 - номера одиночных пешеходов;

- номера пар пешеходов;

- номера троек пешеходов и т.д.

Аналогично определяются индексы .

Итак, мы рассмотрели вариант описания посёлка с последующим моделированием движения пешеходов и машин по нему. Рассмотрим второй вариант.

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

Воспользуемся методом структурного описания и распознавания одномерных (линейных) и двумерных (плоскостных) объектов разработанным в (Ганичева, 2001: 204 - 226).

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

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

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

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

4. Использование терминальных и нетерминальных символов, несущих соответственную смысловую нагрузку. Например, терминальный символ - <стена сверху>, нетерминальный символ - <нижняя часть >.

Схема правил R задается следующим образом:

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

.

Правило 4 заменить на правило

правило 10 заменить на правило

и добавляется правило: .

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

Отметим, что для задания длин объектов и их структурных составляющих можно использовать методику примера 11 из (Ганичева, 2001, 16).

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

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

Эта мера определяется на основе экспериментальных данных или путем экспертного оценивания. В результате получается стохастическая (вероятностная) грамматика Г=<>, где Q - множество вероятностных (нечетких) мер, заданных на множестве правил R.

Если терминальная цепочка x выводится из I применением последовательности правил т.е. и P(ri) - вероятность применения правила ri, то вероятность порождения (мера вывода) цепочки x определяется как произведение вероятностей (мер) используемых в ее выводе правил:

,

где - условная вероятность, поставленная в соответствие правилу ri при предварительном применении правил . Если имеется несколько правил с одинаковой левой частью, то сумма вероятностей применения этих правил равна единице.

Вывод

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

Литература

1. Бобков А.С. Распознавание неуверенности и негативного состояния человека. Проведение научных исследований в области обработки, хранения, передачи и защиты информации. - Сборник научных трудов Всероссийской конференции с элементами научной школы для молодежи. - Т. II. - Ульяновск, 2009. - 549 с.

2. Ганичева А.В. Структурное распознавание образов. - Конспект лекций: ВКА ПВО, 2000. - 22 с.

3. Ганичева А.В. Об одном методе структурного распознавания сложных объектов. Сборник научных трудов. - Тверь: ТФ МЭСИ, 2001. - 250 с.

4. Ганичева А.В., Ганичев А.В. Метод структурно-гармонического анализа движущихся объектов // В мире научных открытий. Серия «Математика. Механика. Информатика». - Красноярск. - 2012. - № 1.1 (25). - С. 202 - 217.

5. Ганичева А.В., Ганичев А.В. Структурное распознавание объектов при коммуникациях [Электронный ресурс] // Электрон. данные. - 2012. - № 3 (24). - Режим доступа: http: // www. tverlingua.ru, свободный. - Загл. с экрана. - Яз. англ., дата обращения.

6. Гладкий А.В. Формальные грамматики и языки. - М.: Наука, 1973. - 368 с.

7. Девятков В.В., Алфимцев А.Н. Метод нечеткого распознавания динамических образов // Сборник трудов 5-ой межд. науч.-прак. конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». - Коломна: Коломенский филиал МГОУ, 2009. Т.2. - С. 870 - 878.

8. Розалиев В.Л. Система распознавания эмоционального состояния человека на основе видеоряда. - Нечёткие системы и мягкие вычисления (НСМВ-2009) // Сборник статей третьей Всероссийской научной конференции. - Волгоград. - 2009. - Т. II, - 284 с.

9. Rigoll G., Kosmala A., Eicker S., High Performance Real-Time Gesture Recognition Using Hidden Markov Models // Proceedings of the Gesture Workshop on Gesture and Sigh Langkage in Human. Computer Interaction. - Bielefeld, 1997. - P. 69 - 80.

References

1. Bobkov A.S. Recognition of uncertainty and the adverse condition of the person. Scientific research in the field of processing, storage, transfer and information protection. - Collection of scientific papers of the all-Russian conference with elements of a scientific school for young people. - I. II. - Ulyanovsk, 2009. - 549 p.

2. Ganicheva A.V. Structural image recognition. - Summary of lectures: VCA air defense, 2000. - 22 p.

3. Ganicheva A.V. On one method of structural recognition of complex objects. Collection of scientific works. - Tver: TF MESI, 2001. - 250 p.

4. Ganicheva A.V., A.V. Ganichev Method of structural-harmonic analysis of moving objects // In the world of scientific discoveries. Series «Mathematics. Mechanics. Informatics». - Krasnoyarsk. - 2012. - № 1.1 (25). - p. 202 - 217.

5. Ganicheva A.V., Ganichev A.V. Structural recognition communications [Electronic resource] // Electron. data. - 2012. - № 3 (24). - Mode of access: http: // www. tverlingua.ru free. - Title from the screen. - Lang. eng., date of request.

6. Gladky A.V. Formal grammars and languages. - M: Nauka, 1973. - 368 p.

7. Devyatkov V.V., Alfimtsev A.N. The method of fuzzy recognition of dynamic images // proceedings of the 5th Intern. nauch.-Prak. conference «Integrated models and soft computing in artificial intelligence». Kolomna: Kolomna branch of the Moscow state regional University, 2009. Vol.2. - p. 870 - 878.

8. Rozaliev V.L. System of recognition of a person's emotional state based on the video. - Fuzzy systems and soft computing (НСМВ-2009) // Collection of articles of the third all-Russian scientific conference. - Volgograd. - 2009. - II, - 284 p.

9. Rigoll G. A. Kosmala, Eicker S., High Performance Real-Time Gesture Recognition Using Hidden Markov Models // Proceedings of the Gesture Workshop on Gesture and Sigh Langkage in Human. Computer Interaction. - Bielefeld, 1997. - P. 69 - 80.

Размещено на Allbest.ru