NGHIÊN CỨU NHẬN DẠNG NGÔN NGỮ CỬ CHỈ
THÔNG QUA QUỸ ĐẠO CHUYỂN ĐỘNG LIÊN TỤC
CỦA ĐỐI TƯỢNG DỰA TRÊN MÔ HÌNH MARKOV ẨN
Dương Khắc Hưởng, Nguyễn Đăng Bình
Trường THPT chuyên Lê Quý Đôn - Khánh Hòa
Khoa CNTT trường ĐH Khoa Học Huế - T.P. Huế
[email protected], [email protected]
Tóm tắt: Nhận dạng quỹ đạo chuyển động liên tục của đối tượng là một lĩnh vực mới trong nghiên cứu
khoa học thị giác máy tính, chủ yếu cho mục đích nhận dạng ngôn ngữ cử chỉ, tương tác giữa con
người - máy tính. Trong bài báo này chúng tôi đề xuất một hệ thống nhận dạng các ngôn ngữ cử chỉ
dựa vào quỹ đạo chuyển động của đối tượng được phát hiện qua màu sắc. Sử dụng mô hình Markov
ẩn (HMM) để huấn luyện và nhận dạng quỹ đạo thu được từ chuyển động của đối tượng. Hệ thống
có năm bước chính: Phân đoạn hình ảnh thu được từ chuỗi hình ảnh qua camera để phát hiện quỹ đạo
chuyển động của đối tượng; Tiền xử lý và trích chọn đặc trưng của quỹ đạo chuyển động của đối
tượng bằng thuật toán được đề xuất để tạo lập bộ tham số đầu vào ban đầu cho mô hình HMM;
Quá trình học bằng thuật toán Baum-Welch và quá trình nhận dạng quỹ đạo bằng thuật toán Viterbi;
Phân tích thiết kế hệ thống và tạo lập bộ dữ liệu thực nghiệm. Các kết quả thực nghiệm cho thấy Hệ
thống đề xuất có thể nhận dạng thành công các cử chỉ rời rạc với ý nghĩa của nó và tỉ lệ nhận dạng thu
được kết quả là 98,4% trên bộ dữ liệu thực nghiệm.
Từ khóa: Nhận dạng cử chỉ, Nhận dạng đối tượng, Nhận dạng ký tự, Thị giác máy tính, Tương tác
người-máy tính.

1

Đặt vấn đề

Nhận dạng ngôn ngữ cử chỉ từ quỹ đạo chuyển động của đối tượng là lĩnh vực tương đối mới
trong vấn đề nghiên cứu nhận dạng cử chỉ tương tác người - máy tính (HCI – Human Computer
Interaction). Quỹ đạo chuyển động của đối tượng là một tập hợp rời rạc của các điểm (tâm của đối tượng)
thu được từ chuỗi hình ảnh của đối tượng chuyển động trong không gian theo thời gian. Mục tiêu của
nhận dạng ngôn ngữ cử chỉ là nhằm nâng cao khả năng tương tác từ xa giữa người và máy tính mà không

Hình. 2.1. Các giai đoạn chính của hệ thống.

Hệ thống của chúng tôi đưa ra có thể thu thập được các quỹ đạo chuyển động của đối tượng trong
không gian theo thời gian thực. Đối tượng được phát hiện dựa vào màu sắc của đối tượng và được theo
dõi sự thay đổi vị trí của nó trong không gian theo thời gian. Mốc để xác định vị trí của đối tượng là tâm
của đối tượng. Từ quỹ đạo chuyển động có ý nghĩa của đối tượng, chúng tôi đưa ra phương pháp tiền xử
lý dữ liệu và trích chọn đặc trưng của quỹ đạo chuyển động của đối tượng và sửa dụng mô hình HMM để
huấn luyện tập dữ liệu thu được cho các lớp ký tự số từ “0” đến “9” và các lớp chữ cái từ “a” đến “z”.
2.1 Dò tìm và theo dõi đối tượng dựa vào màu sắc
Đối tượng chúng tôi sử dụng trong hệ thống là bất kỳ đối tượng nào có kích thước đủ lớn và màu
sắc có độ tương phản cao so với màu nền. Màu sắc của đối tượng sẽ được chọn khi đối tượng xuất hiện
lần đầu tiên trong các khung ảnh thu được từ camera. Trong bài báo này chúng tôi sử dụng không gian
màu YCbCr để phát hiện và theo dõi đối tượng. Một màu trong không gian màu YcbCr là một bộ gồm ba
giá trị là Y (độ sáng), Cb (sắc độ màu xanh) và Cr (sắc độ màu đỏ). Sau khi các giá trị này được chọn từ
màu của đối tượng, chúng tôi sử dụng thêm một ngưỡng cho các giá trị này. Với Y nằm trong khoảng từ 0
đến 255, Cb giao động trong khoảng ∆Cb = ±40 và Cr giao động trong khoảng ∆Cr = ±30. Đối tượng sau
khi được phát hiện, tâm của đối tượng tính được dựa vào công thức tính moment thứ nhất trong không
gian 2D bằng các công thức (2.1) và (2.2) [9] sau đây.
Gọi (xc, yc) là tọa độ tâm của đối tượng thì xc và yc được xác định theo công thức sau:

∑x xI ( x, y)
M 10
xc =
=
M 00 ∑∑ I ( x, y )
x

(2.1)

y


min (

( xi −1 − xi ) 2 + ( yi −1 − yi ) 2 +

( xi − xi +1 ) 2 + ( yi − yi +1 ) 2

i =1.. m −1

)

(2.3)

Gọi v là vị trí tương ứng khi dmin đạt giá trị nhỏ nhất.
Bước 2: Loại bỏ điểm thứ v ra khỏi quỹ đạo
t = t-1;
for i = v to m-1
Pi = Pi+1;
endfor
Bước 3: Lặp lại
If (m> t) lặp lại Bước 1.
2.2 Trích chọn đặc trưng quỹ đạo chuyển động của đối tượng
Theo một số nghiên cứu trước đây [7], [8], đặc trưng của một quỹ đạo phụ thuộc vào các yếu tố cơ
bản như: vị trí, vận tốc và hướng của chuyển động nhưng trong đó, vị trí và vận tốc ít ảnh hưởng đến
hình dáng của quỹ đạo trong không gian 2D mà chủ yếu là hướng chuyển động của mỗi điểm so với điếm
trước nó trong quỹ đạo cho nên chúng tôi chọn hướng chuyển động của các điểm trong quỹ đạo làm đặc
trưng cho quỹ đạo.
Góc của một điểm tại thời điểm t+1 so với điểm trước nó tại thời t được mô tả trong Hình 2.2 (a) và
được tính theo công thức:


For i =1 to t

θ i = arctan(

yi − yi −1
)
xi − xi −1

Endfor
Bước 3: Chuyển đổi giá trị góc sang giá trị hướng
O0 = 0;
For i = 1 to m

Oi =

18θ i

(2.5)

π

Endfor
Bước 4: Kết thúc.
Ta có véc tơ đặc trưng O = {o0, o1, o2, ..., om }.
2.3

Mô hình Markov ẩn cho bài toán nhận dạng ngôn ngữ cử chỉ

2.3.1 Mô hình Markov ẩn
Mô hình HMM là mô hình trong toán học thống kê [2], [5], [7], [8], [9], [10]. Trong đó hệ thống được

i =1

πi = 1.

Mỗi lớp ngôn ngữ cử chỉ được biểu diễn bằng một mô hình HMM độc lập. Mỗi mô hình HMM có
ba bài toán cần giải quyết: (1) Cho mô hình Markov ẩn λ = (A, B, π), tính p(O| λ) là xác suất xảy ra chuỗi
tín hiệu O = { o1, o2, ..,oT }. (2) Cho mô hình Markov ẩn λ = (A, B, π), tìm chuỗi trạng thái Q = {q1, q2, …, qT}
sao cho xác suất tương ứng với chuỗi tín hiệu quan sát được O = { o1, o2, ..,oT } lớn nhất, tức là P(O,Q|λ) cực
đại. (3) Xây dựng mô hình Markov ẩn λ = (A, B, π) sao cho p(O|λ) hoặc p(O,Q|λ) đạt cực đại. Ngoài ra mô
hình HMM cũng có ba kiểu: Kiểu kết nối đầy đủ; Kiểu kết nối từ trái sang phải và Kiểu kết nối từ trái
sang phải theo đường thẳng [8]. Theo kết quả nghiên cứu trước đây [8] thì mô hình kết nối kiểu trái phải
theo đường thẳng là mô hình cho kết quả tốt nhất trong ba mô hình với bài toán huấn luyện và nhận dạng

4


quỹ đạo. Mô hình kết nối đầy đủ và mô hình kết nối từ trái sang phải kiểu đường thẳng được mô tả trong
Hình. 2.3.

Hình. 2.3. Mô hình HMM kiểu đầy đủ và kiểu đường thẳng.

Hình. 2.3.(a) là mô hình HMM kiểu kết nối đầy đủ, Hình. 2.3.(b) là mô hình HMM kiểu kết nối từ
trái sang phải theo đường thẳng. Với mô hình kiểu kết nối từ trái sang phải theo đường thẳng, tại mỗi
thời điểm khi chuyển qua thời điểm tiếp theo thì trạng thái cũ vẫn giữ nguyên hoặc chuyển sang trạng
thái mới. Số lượng trạng thái của mô hình là thông số quan trọng ảnh hưởng đến quá trình huấn luyện và
nhận dạng. Nếu số trạng thái quá nhiều quá sẽ sinh ra hiện tượng lặp lại quá nhiều số ký hiệu quan sát
còn nếu số trạng thái quá ít sẽ làm giảm độ chính xác của quá trình nhận dạng. Trong bài báo này chúng
tôi sẽ thực nghiệm trên ba bộ dữ liệu với số lượng trạng thái là 10, 18 và 36 (số trạng thái ít hơn hoặc bằng
số ký hiệu quan sát). Ví dụ quỹ đạo của chữ số “3” với số trạng thái bằng 10 và số ký hiệu quan sát là 36
được mô tả như Hình. 2.4.


b j (k ) =

p
M

(2.8)

Với ý nghĩa ở trạng thái thứ j thì có p ký hiệu vk trong các chuỗi quan sát O1, O2, ..., Om và vk là ký
hiệu thứ k trong tập gồm M ký hiệu quan sát phân biệt của mô hình HMM.
Và cuối cùng chúng tôi tạo ma trận xác suất ban đầu π = {1 0 0 ... 0 }T
(2.9)
Ma trận π có N phần tử, trong đó phần tử đầu tiên có giá trị bằng 1, các phần tử khác có bằng 0.

5


2.3.2 Huấn luyện dữ liệu với mô hình Markov ẩn
Mỗi lớp ký hiệu ngôn ngữ được biểu diễn một mô hình HMM độc lập. Mô hình HMM được huấn
luyện với bộ dữ liệu mẫu độc lập chỉ chứa một số mẫu dương (hữu hạn). Mỗi mẫu dùng cho huấn luyện
được trích chọn véc tơ đặc trưng tương ứng và sử dụng thuật toán Baum-Welch để cập nhật mẫu, ước
tính các véc tơ tham số của mô hình HMM của lớp đó. Mỗi lớp được huấn luyện độc lập với từng bộ dữ
liệu riêng của từng lớp.
Thuật toán 2.3: Thuật toán Baum-Welch ước lượng các véc tơ tham số mô hình HMM
Dữ liệu vào: Tập gồm m véc tơ đặc trưng O1, O2, ..., Om của một lớp.
Dữ liệu ra: Giá trị ước lượng của các véc tơ tham số của mô hình Markov ẩn λ = (A, B, π ).
Phương pháp:
Bước 1: Khởi tạo các tham số ban đầu cho mô hình HMM
Khởi tạo A = {aij} (i = 1..n, j=1..n) theo công thức (2.10)
Khởi tạo B = {bj(k)} (j = 1..n, k = 1..36) từ tập các véc tơ đặc trưng theo công thức (2.11)


γ t (i ) = ∑ ξt (i, j )

(2.14)

j =1

Bước 4: Cập nhật lại giá trị các tham số cho mô hình
Xác suất trạng thái i là trạng thái bắt đầu πi:

π i = γ 1 (i )

(2.15)

T −1

∑ ξ (i, j)

Xác suất chuyển trạng thái:

t

aij =

t =1
T −1

(2.6)

∑ γ (i)

Dữ liệu ra: n mô hình λi. (1 ≤ i ≤ n)
Phương pháp:
Bước 1: Huấn luyện n bộ dữ liệu cho n mô hình HMM
For i = 1 to n
Thực hiện thuật toán 2.3 trên m véc tơ đặc trưng O1, O2, ..., Om cho lớp thứ i;
Bước 2 Kết thúc.
Ta có n mô hình HMM (λ1, λ2, ..., λn).

2.3.3 Nhận dạng ký hiệu ngôn ngữ dựa vào mô hình Markov ẩn
Sau khi các mô hình HMM của các lớp đã được huấn luyện. Từ chuỗi quan sát chuyển động của
đối tượng Thuật toán 2.5 dùng để ước lượng độ tương tự được ứng dụng để nhận dạng trên bộ dữ liệu
thực nghiệm được mô tả trong Hình 2.6.
Thuật toán 2.5: Thuật toán Viterbi(λ, O)
Dữ liệu vào: Chuỗi quan sát O = (o1, o2,..,oT) , mô hình λ = (A, B, π).
Dữ liệu ra: Chuỗi trạng thái Q* , xác suất p*(λ| O).
Phương pháp:
Bước 1: Khởi tạo
δ1(i) = pi bi(o1)
ψ1(i) = 0 , i =1, ... , N
Bước 2: For t = 1 to T-1
δt (j) = maxi [δt - 1(i) aij] bj(ot)
ψt(j) = arg maxi [δt - 1(i) aij]
Endfor
Bước 3: Kết thúc
p* = maxi [δT(i)]
q*T = arg maxi [δT(i )]
Bước 4: Kết quả:
q*t = ψt+1(q*t+1)
với t = T - 1, T - 2 , . . . , 1.
Thuật toán 2.6: Thuật toán nhận dạng ngôn ngữ cử chỉ

Hình. 3.1. Giao diện chính của hệ thống.

Hệ thống bao gồm những chức năng chính sau đây:
• Thu hình ảnh từ camera, phát hiện đối tượng bằng màu sắc được chỉ định và theo dõi đối
tượng để lấy quỹ đạo chuyển động của đối tượng.
• Sau khi hệ thống lấy được quỹ đạo chuyển động của đối tượng, nó sẽ tự động tiền xử lý dữ
liệu bằng thuật toán 2.1 và trích chọn đặc trưng bằng thuật toán 2.2. Tập các véc tơ đặc trưng

8


•

•

•

thu được của từng lớp được lưu vào một tệp văn bản trong từng thư mục tương ứng với tên
lớp ký tự dùng để huấn luyện hoặc lưu vào một tệp văn bản riêng dùng để nhận dạng.
Khi dữ liệu ban đầu của từng lớp đã được tạo ra, hệ thống có thể để huấn luyện dữ liệu cho
các lớp. Chức năng huấn luyện dữ liệu được xây dựng bởi thuật toán 2.5. Dữ liệu của mỗi mô
hình HMM sau khi huấn luyện được lưu trữ trong một tệp có cấu trúc nằm trong cùng thư
mục của lớp đó để phục vụ cho quá trình nhận dạng.
Hệ thống có thể nhận dạng cùng một lúc trên nhiều mẫu dữ liệu đã được tạo lập trong tệp
riêng trước đó và đưa ra kết quả thống kê số liệu nhận dạng đúng hoặc sai trong tệp văn bản
kết quả.
Hệ thống cũng có thể nhận dạng trực tiếp và đưa ra kết quả nay sau khi nhận dạng được trên
giao diện của chương trình. Kết quả là ký tự được nhận dạng hiển thị ngay trên cùng màn
hình của hình ảnh từ camera. Chức năng này được mô phỏng bằng video clip đã được chúng
tôi upload tại trang youtube tại chỉ: https://www.youtube.com/watch?v=0zCTP9szFPM

Hình 4.1. Tạo lập dữ liệu và thực nghiệm.

Các số liệu cụ thể của từng bộ dữ liệu và kết quả nhận dạng được trình bày trong bảng 4.1. Với kết
quả sau khi thực nghiệm trên 3 bộ dữ liệu thể hiện trong Bảng. 4.1. trên, chúng tôi có thể đánh giá rằng
kết quả nghiên cứu các thuật toán tiền xử lý dữ liệu, thuật toán trích chọn đặc trưng, xây dựng các tham
số cho mô hình HMM, lựa chọn và ứng dụng thuật toán huấn luyện, thuật toán nhận dạng là phù hợp
với bộ dữ liệu mà chúng tôi đã tạo ra.

9


Bảng. 4.1. Kết quả thực nghiệm.
Số trạng thái

Số mẫu
huấn luyện

Số mẫu
nhận dạng

Số mẫu
nhận dạng sai

Tỷ lệ

10

360

431


25

94.2%

Trong Bảng. 4.1. trên chúng tôi thấy rằng tỷ lệ nhận dạng sai sẽ tăng khi số các trạng thái của mô
hình HMM giảm, điều này phù hợp với nhận định ban đầu của chúng tôi là khi số trạng thái ít thì trong
chuỗi trạng thái của kết quả nhận dạng sẽ có nhiều trạng thái bị lặp lại làm cho xác suất của chuỗi trạng
thái trên các lớp gần nhau nên dẫn đến kết quả phân lớp bị sai lệch.
Từ kết quả nghiên cứu lý thuyết mô hình HMM, xây dựng cài đặt hệ thống và thực nghiệm chúng
tôi đưa ra một số nhận xét về đề tài này như sau:
•
Số trạng thái của mô hình HMM càng ít thì tốc độ thực hiện của hệ thống càng nhanh nhưng
kết quả nhận dạng của hệ thống càng thấp và ngược lại.
Số lượng ký hiệu quan sát phân biệt của mô hình HMM càng nhiều thì độ chính xác của
•
hệ thống càng cao nhưng nếu số lượng ký hiệu quan sát nhiều quá sẽ ảnh hưởng đến tốc độ của
hệ thống.
•
Độ dài của chuỗi quan sát (quỹ đạo) cũng có ảnh hưởng đến kết quả của hệ thống. Nếu chuỗi
quan sát dài quá cũng sẽ gây nên hiện tượng lặp lại của các trạng thái trong kết quả nhận dạng,
nếu độ dài chuỗi quan sát quá ngắn sẽ làm giảm tỷ lệ nhận dạng đúng. Ngoài ra độ dài chuỗi
quan sát còn phụ thuộc vào hình dáng của ký tự cần nhận dạng.
•
Một số điều kiện khác cũng có thể làm ảnh hưởng đến kết quả của hệ thống như: tốc độ và độ
phân giải của camera, cường độ ánh sáng của môi trường, khoảng cách từ đối tượng chuyển
động đến camera, sự tương phản giữa màu sắc của đối tượng và màu nền.
•
Ngoài ra hình dáng quỹ đạo của một số ký tự cũng có thể ảnh hưởng đến kết quả nhận dạng
ví dụ như hình dáng của ký tự chữ cái “o” và ký tự chữ số “0” tương đối giống nhau nên nếu


7.
8.

9.
10.

A.A. Randive, H. B. Mali, S. D. Lokhande (2012), “Hand Gesture Segmentation”, International Journal of
Computer Technology and Electronics Engineering (IJCTEE), Vol.2, pp.125-129.
A.Elmezain, A. Al-Hamadi (2007), “Gesture Recognition for Alphabets from Hand Motion Trajectory Using
Hidden Markov Models”, IEEE International Symposium on, pp.1209-1214.
Antonis A. Argyros, Manolis I.A. Lourakis (2006), “Vision-Based Interpretation of Hand Gestures for Remote
Control of a Computer Mouse”, ECCV'06 Proceedings of the 2006 international conference on Computer Vision in
Human-Computer Interaction, pp.40-51.
Ch.Srinivasa Rao, S.Srinivas Kumar and B.Chandra Mohan (2010), “Content Based Image Retrieval Using
Exact Legendre Moments And Support Vector Machine”, International journal of multimedia & Its applications
(IJMA), Vol 2, pp.69-79.
Feng-Sheng Chen, Chih-Ming Fu, Chung-Lin Huang (2003), “Hand gesture recognition using a real-time
tracking method and hidden Markov models”, Institute of Electrical Engineering, National Tsing Hua University,
Hsin Chu 300, Taiwan, ROC Vol.21, pp.745–758.
J. M. Palacios, Carlos Sag, Eduardo Montijano and Sergio Llorente (2013), “Human-Computer Interaction
Based on Hand Gestures Using RGB-D Sensors”, This article belongs to the Special Issue State-of-the-Art Sensors
Technology in Spain, ISSN 1424-8220, pp.11843-11860.
Mahmoud Elmezain, Ayoub Al-Hamadi, and Bernd Michaelis (2009), “Hand Gesture Recognition Based on
Combined Features Extraction”, World Academy of Science, Engineering and Technology, Vol.3, pp.853-858.
Mahmoud Elmezain , Ayoub Al-hamadi , Bernd Michaelis (2008), “A Hidden Markov Model-Based Isolated
and Meaningful Hand Gesture Recognition”, World Academy of science, engineering and technology, Vol 31,
pp.394-401.
Nguyen Dang Binh, Enokida Shuichi and Toshiaki Ejima (2005), “Real-Time Hand Tracking and Gesture
Recognition System”, IGGST International Journal on Graphics, Vision Image Processing, Vol.6, pp.31-39.