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

В настоящее время разработка и исследование человеко-машинных интерфейсов, основанных на распознавании образов и визуальном представлении мультимедийной информации, становится передним краем в развитии современного математического и программного обеспечения [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. Введем функцию выходов j конечного автомата M_j: j ( b_j(t_i)) = y_j(t_i) и функцию переходов f: f(b_j(t_i), t_i+1) = b_j(t_i+1).

Каждой дуге графа соответствуют две инцидентные вершины b_i и b_i+1. Координатой вершины b_i на оси абсцисс является t_i и j(b_i(t_i)) = y_i(t_i), а координата вершины b_i+1 на оси абсцисс есть t_i+1 и j (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_riÎB(b_i) и b_r(i+1)ÎB(b_i+1), для которых j(b_ri)=y_ri,j(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 будет следующим:

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

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

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

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

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

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

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

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

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

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

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

Главными преимуществами использованной модели нечеткого конечного автомата является возможность строить распознаватель, имея всего несколько примеров в обучающей выборке, строить автоматы разной длины, распознавать жесты с траекторией включающей пересечения. Эксперименты показали высокую надежность распознавания, программная система не требовала больших вычислительных ресурсов, позволяя совместно работать нескольким приложениям в операционной системе 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.