Метод нечеткого распознавания динамических образов

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

Московский государственный технический университет им. Н.Э. Баумана

МЕТОД НЕЧЕТКОГО РАСПОЗНАВАНИЯ ДИНАМИЧЕСКИХ ОБРАЗОВ

Девятков В.В., д.т.н., профессор

Алфимцев А.Н., к.т.н.

1. ВВЕДЕНИЕ

В настоящее время разработка и исследование человеко-машинных интерфейсов, основанных на распознавании образов и визуальном представлении мультимедийной информации, становится передним краем в развитии современного математического и программного обеспечения [1,7,9,10]. Перед разработчиками подобных интерфейсов ставится задача использования естественных для человека способов общения с компьютерами с помощью жестов, голоса, мимики и других модальностей [3]. Жесты являются особенно перспективными для построения интерфейсов управления программным и аппаратным обеспечением компьютеров, роботов, позволяют расширить возможности интерфейса для людей с дефектами слуха и речи. Поэтому в данной статье метод нечеткого распознавания динамических образов будет рассмотрен на примере распознавания динамических жестов, имеющих большое прикладное значение.

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

Проведенный анализ популярных математических моделей распознавания динамических жестов: Скрытых Марковских моделей [11, 13, 14, 15], Нейронных сетей [12], Байесовых сетей [5, 10], показал, что оценки вычислительной сложности распознавания жестов с помощью этих моделей зависят от квадрата числа состояний (СММ), нейронов (Нейросети) или вершин (Байесовы сети), используемых для распознавания, умноженных на число символов наблюдаемой последовательности. Вследствие этого, с ростом этих величин, практическое использование для распознавания жестов в реальном времени указанных моделей, из-за высоких затрат процессорного времени и памяти компьютера, становится невозможным. Тем самым обоснована необходимость создания новых вычислительно-эффективных методов. распознавание нечеткий динамический жест

В данной статье предлагается метод нечеткого распознавания динамических жестов, основанный на использовании модели нечетких конечных автоматов. В разделе 2 описывается разработанная нечеткая модель. В разделе 3 рассматривается метод нечеткого распознавания. В разделе 4 приводятся результаты экспериментов. Раздел 5 является заключительным.

2. НЕЧЕТКАЯ МОДЕЛЬ РАСПОЗНАВАНИЯ

Нечеткая модель для распознавания динамических жестов, основанная на нечетких конечных автоматах, формируется для каждого динамического жеста. Для этого жест многократно повторяется и траектория каждого повторения фиксируется. Число повторений обычно равно 10-20. Так, например, для жеста, имеющего вид буквы «Z», траектории показаны на рис. 1а. В данном случае, для формирования траектории жеста используются алгоритмы компьютерного зрения захвата и отслеживания движения кисти в видеопотоке: нахождение двигающегося объекта в кадре (алгоритм вычитания кадров [4]), нахождение кисти (алгоритм определения цвета кожи [8]), нахождение центра тяжести.

Обобщенно траекторию перемещения всех жестов, имеющих вид буквы «Z» можно представить в виде графа, показанного на рис. 1б. Вершина A₁ этого графа объединяет множество точек, принадлежащих началу траекторий, вершины A₂ и A₃ соответствуют множествам точек перегиба траекторий, вершина A₄ объединяет множество точек концов траекторий, дуги графа указывают на направление перемещения центра тяжести объекта по траекториям. Этот граф может служить основой для построения нечеткой модели жеста. Каждая вершина графа объединяет характерные точки с определенным сходством. Множество точек, относящихся к одной вершине, составляют кластер. Каждая точка в общем случае принадлежит m-мерному пространству и является набором значений характерных признаков y₁, y₂,…, y_m. Для нахождения кластеров использовался алгоритм кластеризации с-средних.

Рис. 1 (а) Траектории жеста, повторенного несколько раз, (б) Граф жеста буквы «Z»

Для того чтобы можно было учесть время, вместо графа на рис. 1б, (для случая двумерного пространства) использовались два графа, полученные в результате проекции траекторий перемещения центров тяжести кисти руки на ось абсцисс и ось времени, а также на ось ординат и ось времени (рис. 2). В общем случае m-мерного пространства таких проекций y_i(t) будет m: (i=1,…,m).

Значение y_i(t) в некоторый момент времени, будем называть отсчетом y_i(t). Последовательность n+1 отсчетов Y_i[t₀, t_n] = {y_i(t₀), y_i(t₁), y_i(t₂), …, y_i(t_n)} i-ой проекции одного и того же жеста в течение нескольких подряд идущих моментов времени t₀, t₁, t₂, …, t_n (в течение временного интервала [t₀, t_n]) назовем сигналом. Сопоставим каждому отсчету y_j(t_i) одного и того же сигнала состояние b_j (t_i) конечного автомата M_j. Введем функцию выходов конечного автомата M_j: ( b_j(t_i)) = y_j(t_i) и функцию переходов f: f(b_j(t_i), t_i+1) = b_j(t_i+1).

Рис. 2 Проекции графа жеста

Таким образом, каждый отсчет является значением функции выхода y_j(t) = (b_j(t)) автомата M_j, каждый сигнал является последовательностью значений функций выхода y_j(t) = (y_j(t₀), y_j(t₁),…, y_j(t_n)) одного и того же автомата M_j.

Представим автомат M_j, соответствующий какой-либо проекции некоторого жеста, его графом переходов (рис. 3а). Каждая вершина графа помечена символом b_i, i = 0, 1, …, 12. (вершины обозначены кружками). Каждая пара соседних вершин b_i, b_i+1, i=0, 1, 2,…, 11 соединена дугой, направленной от вершины i к вершине i+1. Дуги, направленные от вершины i к вершине i+1 помечены символом t_i в алфавите T ={t₀, t₁, t₂, t₃,…, t_m-1}. Если выписать обозначения всех дуг слева направо, то получим последовательность символов t₁t₂t₃t₄t₅t₆t₇t₈t₉t₁₀t₁₁t₁₂ (здесь - пустой символ, который может опускаться). Эта последовательность может рассматриваться как слово или предложение некоторого языка L= L(G), порождаемого автоматной грамматикой G_j = {V, T, P, S= b₀}, V={ b₁, b₂, b₃, b₄, b₅, b₆, b₇, b₈, b₉, b₁₀, b₁₁}, T = {t₀, t₁, t₂, t₃, t₄, t₅, t₆, t₇, t₈, t₉, t₁₀, t_11, }, P= { b₀t₁b₁, b₁t₂b₂, b₂t₃b₃, b₃t₄b₄, b₄t₅b₅, b₅t₆b₆, b₆t₇b₇, b₇t₈b₈, b₈t₉b₉, b₉t₁₀b₁₀, b₁₀t₁₁b₁₁, b₁₁t₁₂ b₁₂, b₁₂}.

Каждой дуге графа соответствуют две инцидентные вершины b_i и b_i+1. Координатой вершины b_i на оси абсцисс является t_i и (b_i(t_i)) = y_i(t_i), а координата вершины b_i+1 на оси абсцисс есть t_i+1 и (b_i+1(t_i+1)) = y_i+1(t_i+1).

Полагаем, что отсчеты y_i(t_i) одного и того же кластера, соответствующие l различным траекториям одного и того же жеста, могут изменяться в пределах среднеквадратичного отклонения s_i от проекции центра кластера v_i(t_i):

,

где N - число отсчетов принадлежащих кластеру, v_i - координата центра i-ого кластера, y^l_i(t_i) отсчет, принадлежащий i-ому кластеру. Для простоты полагаем, что s_i одно и то же для всех i и равно s. Для каждого множества отсчетов y^l_i(t_i) задаем треугольную функцию принадлежностей м_i(y), определяемую точками, , причем (рис. 3б).

Вершину b_i с координатами t_i, y_i заменим множеством вершин b_ri B(b_i) с координатами, изменяющимися по оси ординат в пределах области y_i^- = y_i-s, y_i⁺= y_i+s. Каждая вершина b_ri соответствует какому-либо пикселю, а множество B(b_i) вершин (пикселей) вычисляется как множество всех пикселей, с координатой t_i по оси ординат. Вместо одной дуги (b_i, b_i+1) теперь будем иметь множество дуг {(b_ri, b_r(i+1)) b_ri B(b_i), b_r(i+1) B(b_i+1)}, соединяющих каждую вершину множества B(b_i) с каждой вершиной множества B(b_i+1) и помеченных тем же символом t_i+1, что и дуга (b_i, b_i+1).

Рис. 3 (а) Граф переходов четкого автомата, (б) Функции принадлежности вершин, графа переходов нечеткого автомата

Будем полагать, что функция принадлежности каждой дуги (b_ri, b_r(i+1)), инцидентной вершинам b_riB(b_i) и b_r(i+1)B(b_i+1), для которых (b_ri)=y_ri,(b_r(i+1))=y_r(i+1) определяется как:

Нечеткая грамматика G_F={V, T, P_F, S_F} получается из четкой грамматики G={V, T, P, S} следующим образом. Единственный начальный нетерминальный символ четкой грамматики заменяется множеством начальных нетерминальных символов: Множество правил P_F нечеткой грамматики G_F будет следующим:

P_F = {b_ri t_i+1 b_r(i+1), м(b_ri t_i+1 b_r(i+1)) =, i=0,…, n-1 }.

3. МЕТОД НЕЧЕТКОГО РАСПОЗНАВАНИЯ

В начале для каждого жеста k=1,…, K строится множество нечетких эталонных грамматик G^k_F1, G^k_F2,…, G^k_Fm, базируясь на изложенных принципах. Будем говорить, что четкая грамматика G', содержащая правила {b_it_i+1b_i+1, i=0,…, n-1}, сравнима с нечеткой грамматикой G_F, если существует последовательность правил {b_rit_i+1b_r(i+1), i=0,…, n-1} этой нечеткой грамматики, для которых имеет место b_i=b_ri для всех i=0,…,n-1. Метод нечеткого распознавания динамических жестов с использованием модели, основанной на нечетких конечных автоматах и соответствующем им множестве эталонных нечетких грамматик G_F1, G_F2,…, G_Fm, будет следующим.

Шаг 1. Распознаваемый жест обрабатывается с теми же шагами дискретизации по временной оси, что и эталонные жесты, и для него строится множество четких грамматик G₁ G_2, …, G_m, ему соответствующих.

Шаг 2. Осуществляется сравнение четких грамматик G₁ G_2, …, G_m, соответствующих распознаваемому жесту, с каждой соответствующей нечеткой эталонной грамматикой G^k_F1, G^k_F2,…, G^k_Fm. Здесь k{1,…, K}, а K-число распознаваемых жестов.

Шаг 3. Для тех множеств нечетких эталонных грамматик G^k_F1, G^k_F2,…, G^k_Fm сравнение с которыми оказалось успешным, вычисляется соответствующее множество значений функций принадлежности по формуле:, а затем значение меры A_k, характеризующей близость распознаваемого жеста к эталонным жестам k по формуле:

.

Шаг 4. Распознаваемый жест считается совпадающим с тем эталонным жестом k, для которого значение меры A_k оказалась максимальным.

Шаг 5. Если не было ни одного успешного сравнения грамматик, то распознавание этого жеста заканчивается неудачей (жест не был распознан).

Вычислительная сложность распознавания динамических жестов с помощью нечетких моделей равна O(mn), где m - количество нечетких автоматов, n - максимальное количество состояний нечеткого конечного автомата используемого для распознавания.

4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ

Разработанный метод был апробирован в программной системе на персональном компьютере с использованием видеокамеры. Для захвата изображения использовалась бытовая видеокамера (web-камера) разрешением 640x480, 8 бит, 30 кадр/сек. Алфавит распознаваемых жестов состоял из десяти жестов: Буква Z, Буква M, Буква P, Буква N, Буква W, Волна, Бесконечность, Треугольник, Квадрат, Крест. Выбор данного алфавита обосновывался на соображениях применения жестов, не использующихся в обычном общении и состоящих из базовых жестов языка глухонемых, интуитивно понятных пользователю.

Были проведены следующие эксперименты:

1. Нахождение надежности распознавания жеста, выполняемого одной рукой одним человеком.

2. Нахождение надежности распознавания жестов, выполняемых двумя руками по очереди одним человеком (рис.4).

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

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

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

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

5. ЗАКЛЮЧЕНИЕ

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

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

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

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

Литература

1. Alon J., Athistos V., Yuan Q. and Sclaroff S. Simultaneous Localization and Recognition of Dynamic Hand Gestures // Proceedings of WACV MOTION'05. Breckenridge, 2005. Vol.2. P. 254-260.

2. Bobick A.F., Wilson A.D. A State-Based Approach to the Representation and Recognition of Gesture // IEEE Transactions on pattern analysis and machine intelligence. 1997. Vol.19, №12. P. 1325-1337.

3. Carbini S., Viallet J.E., Bernier O., Bascle B. Tracking body parts of multiple people for multi-person multimodal interface // Computer Vision in Human-Computer Interaction in ICCV 2005 Workshop. Beijing, 2005. P. 16-25.

4. Cutler R., Turk M. View-based Interpretation of Real-time Optical Flow for Gesture Recognition // Proceedings of Third IEEE Conference on Autom. Face and Gesture Recognition -Nara, 1998. P. 416-421.

5. Darwiche A. A Differential Approach to Inference in Bayesian Networks // Journal of the ACM. 2001. Vol.50, №3. P. 280 -305.

6. Hong P., Turk M., Huang T. Gesture Modeling and Recognition Using Finite State Machines // Proceedings of IEEE Conference on Face and Gesture Recognition. Grenoble, 2000. P. 410-416.

7. Malassiotis S., Aifanti N., Strintzis M. A Gesture Recognition System Using 3D Data // Proceedings of First Symposium on 3D Data Processing Visualization and Transmisssion. Padova, 2002. P. 190-193.

8. Lichtenauer J.F., Reinders M.J.T., Hendriks E.A. A self-calibrating chrominance model applied to skin color detection // Proceedings of the 2nd International Conference on Computer Vision Theory and Applications (VISAPP). Barcelona, 2007. P. 115-120.

9. Ong C.W., Ranganath S., Venkatesh Y.V. Understanding gestures with systematic variations in movement dynamics // Pattern recognition. 2006. Vol.39, №9. P. 1633-1648.

10. Rett J., Dias J. Gesture Recognition Using a Marionette Model and Dynamic Bayesian Networks // Lecture notes in computer science. 2006. Vol.4142. P. 69-80.

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

12. Sandberg A. Gesture Recognition using Neural Networks: Master thesis. Stockholm, 1997. 76 p.

13. Starner T., Weaver J., and Pentland A. Real-Time American Sign Language Recognition Using Desk and Wearable Computer Based Video // IEEE Transactions. Pattern Analysis and Machine Intelligence. 1998. Vol.20, №12. P. 1371-1375.

14. Patwardhan K.S., Dutta Roy S. Dynamic hand gesture recognition using predictive eigentracker // Proceedings of Indian Conference on Computer Vision, Graphics and Image Processing. Calcutta, 2004. P. 675-680.

15. Yamato J., Ohya J., Ishii K. Recognizing Human Action in Time-Sequential Images Using Hidden Markov Model // Proceedings of Computer Vision and Pattern Recognition- Champaign, 1992. P. 379-385.

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