TRNG I HC KHOA HC T NHIÊN
KHOA CÔNG NGH THÔNG TIN
B MÔN CÔNG NGH PHN MM
INH BÁ THNG – NG BÁC VN
TÌM HIU CÁC K THUT
ÁP DNG CHO BÀI TOÁN
NHN DNG KÝ HIU NGI CÂM
KHÓA LUN C NHÂN TIN HC
Th.S NGUYN TRI TUN
NIÊN KHÓA 2001 - 2005
LI NHN XÉT CA GIÁO VIÊN HNG DN
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………

……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
Li cm n
Chúng em xin chân thành cm n Khoa Công ngh Thông tin, trng i hc

Li nói đu
S ra đi ca máy tính đã giúp ích rt nhiu cho công vic và cuc sng ca con
ngi. Vi máy tính, con ngi có th son tho vn bn, nghe nhc, xem phim, thit
k đ ha, x lý nh, biên tp phim Tuy nhiên, vic giao tip gia con ngi và máy
tính ph thuc ch yu vào bàn phím và chut, và hu nh con ngi luôn phi ngi
trc máy tính. Dn dn, các nhà sn xut thy đc s bt tin và đã to ra bàn phím
và chut không dây vi mong mun mang li s t do hn cho ngi dùng. Tuy nhiên,
bàn phím không dây thì vn là bàn phím, con ngi cng ch có th tng tác vi máy
tính thông qua h thng 104 phím. Con ngi ch tht s đc “gii phóng” khi vic
tng tác vi máy tính đc thc hin thông qua các c ch trong cuc sng hàng ngày,
tc là máy tính phi “hiu” đc các c ch ca con ngi. ó chính là vn đ đt ra
cho bài toán nhn dng và phân loi c ch. Cho đn thi đim hin nay, dù đã có
nhiu cách tip cn khác nhau cho bài toán này, nhng dng nh vn cha có mt h
thng nhn dng c ch nào thc s hiu qu.
Bên cnh đó, bài toán nhn dng mt ngi đang đt đc mt kt qu rt kh
quan vi mô hình Cascade of Boosted Classifiers do Viola và Jones [1] đ ngh. Mô
hình này đt hiu qu cao c v đ chính xác ln thi gian nhn dng. Eng Jon [14] đã
áp dng mô hình này lên bài toán nhn dng bàn tay và cng đt đc kt qu tt.
Mc tiêu ca khóa lun này là th áp dng mô hình Cascade of Boosted
Classifiers lên bài toán phân loi c ch vi hi vng nó cng s đt đc kt qu tt
nh trên bài toán nhn dng mt ngi và nhn dng bàn tay. Lun vn đc trình bày
trong 6 chng vi b cc nh sau:
• Chng 1-M đu: Nêu lên tm quan trng ca bài toán phân loi c ch và
mô t s b phm vi bài toán mà khóa lun này s gii quyt. ng thi gii
đim s qua các cách tip cn hin có vi các u khuyt đim ca chúng và gii
thiu v mô hình s dng trong khóa lun này. 1
Mc Lc
Chng 1 M đu 6
Chng 2 Gii thiu v h thng phân loi c ch 12
Chng 3 Các c s lý thuyt 15
3.1 Tip cn Boosting 15
3.2 AdaBoost 16
3.3 Haar Feature 20
3.4 Cascade of Classifiers 24
3.5 Cascade of Boosted Classifiers 25
3.6 ánh giá 26
Chng 4 Phân loi c ch vi Cascade of Boosted Classifiers 29
4.1 B nhn dng 1 c ch 29
4.1.1 Tp hun luyn 29
4.1.2 c trng 31
4.1.3 Xây dng b nhn dng vi AdaBoost 32
4.1.4 Cascade of Boosted Classifiers 36
4.1.5 Hot đng ca b nhn dng c ch 38
4.2 B phân loi c ch 41
Chng 5 Kt qu th nghim 43
5.1 Tp hun luyn 43
5.2 Cách tin hành hun luyn 47
5.3 Kt qu th nghim 49
5.4 So sánh và đánh giá 53
Chng 6 Tng kt 56
6.1 Kt lun 56
6.2 Hng phát trin 57

Hình 5 - Boosting 16
Hình 6 - Strong classifier H(x) xây dng bng AdaBoost 17
Hình 7 - Haar Feature c bn 21
Hình 8 - Haar Feature cho mt ngi 21
Hình 9 - SAT(x,y) và cách tính tng các đim nh trong mt hình ch nht bt kì 22
Hình 10 - Haar Feature xoay 45º do Lienhart đ ngh 23
Hình 11 - RSAT(x,y) và cách tính tng các đim nh trong mt hình ch nht xoay 1
góc 45º 23
Hình 12 - Cascade of Classifiers 25
Hình 13 - B nhn dng c ch A 29
Hình 14 - Các mu positive cho b nhn dng ch A 30
Hình 15 - Các mu negative (B, C, D) cho b nhn dng ch A 30
Hình 16 - Tp hun luyn ca các weak classifiers 31
Hình 17 - Các Haar Feature s dng trong b nhn dng 1 c ch 31
Hình 18 - Cách chn weak classifier ca AdaBoost 34
Hình 19 - Chn ngng θ da vào min detection rate 35
Hình 20 - Các vùng nh không liên quan (nét mnh) s b loi ngay t nhng stages
đu tiên 39
Hình 21 - Khc phc trng hp nhiu vùng nh k cn nhau bng cách ly vùng nh
trung bình 39
Hình 22 - i vi các vùng nh lng nhau, các vùng nh bên trong s b loi b 40


5
Danh sách bng
Bng 1 - Kt qu hun luyn vi 3 kích thc ca mu positive 45
Bng 2 - Kt qu hun luyn qua 3 lp ca b nhn dng c ch B 49
Bng 3 - Kt qu thu đc ca b nhn dng c ch A trên 2 tp test 50
Bng 4 - Kt qu th nghim ca 24 b nhn dng trên tp test gm 592 hình 52

Chng 1. M đu
6

Chng 1 M đu
Mc dù nn công ngh thông tin vn phát trin liên tc vi tc đ v bão nhng
chúng ta vn còn mt chng đng rt dài đ có th giao tip mt cách hoàn toàn t
nhiên vi máy tính nh giao tip gia con ngi vi nhau. Cách giao tip t nhiên nht
vi máy tính chính là dùng giao tip thông qua ting nói và c ch. Trong khi lnh vc
nhn dng ting nói đã đt đc nhng thành công đáng k trong vòng 10 nm gn đây
thì lnh vc nhn dng c ch vn còn tt li phía sau. Tuy nhiên, ngôn ng c ch li
chính là ngôn ng chuyn ti thông tin gia ngi và ngi mt cách trn vn nht.
Nu gi s chúng ta phát trin đc mt h thng nhn dng ting nói kt hp vi nhn
dng c ch thì chúng ta hoàn toàn có th thay th chut hay bàn phím bng mt h

chuyên làm sai ch th thì khó có th đc chp nhn.
Bên cnh đó, đ có th tng tác vi ngi dùng, h thng nhn dng xây dng
phi là h thng thi gian thc, phi x lý nhanh. Mt chuyên viên đ ha s không
chp nhn mt h thng cn đn 30 giây đ xoay mô hình ca h. Mt con robot s
không đc chp nhn nu nó cn đn 20 giây đ hiu ra rng nó phi làm mt vic gì
đó ngay lp tc. Hay nh trong mt cuc giao tip, nu mt h thng phi mt đn 10
giây cho mi c ch mà ngi khim thính ra du thì nó cng không th đc chp
nhn.
Bài toán nhn dng c ch có th chia làm 2 loi chính: nhn dng c ch tnh và
nhn dng c ch đng. C ch tnh là các c ch ng vi mt t th c đnh ca mt
bàn tay, còn c ch đng là chuyn đng theo mt qu đo nht đnh ca mt hay hai
bàn tay. Nhn dng c ch đng bao hàm c nhn dng c ch tnh và mt s x lý trên
chuyn đng nên ht sc phc tp. Khóa lun này ch tp trung vào bài toán nhn dng
c ch tnh.
H thng phân loi c ch xây dng trong khóa lun này là mt h thng có kh
nng nhn dng và phân loi 24 c ch ng vi 24 kí t trong bng ch cái (tr ch J
và Z do đòi hi chuyn đng ca bàn tay) Chng 1. M đu
8

Hình 1 - H thng 24 c ch


Freeman s dng đc trng Orientation Histogram [15] vi thi gian tính toán nhanh,
nhng li đòi hi mu nhn dng phi là mu chp cn cnh ca bàn tay. ng thi
cách này không áp dng đc khi h thng có các c ch tng t nhau, vì các c ch
tng t nhau cho Orientation Histogram ging nhau.
Bowden và Sarhadi [16] s dng mô hình nonlinear PDM (nonlinear point
distribution model) đ biu din đc nhiu thông tin v bàn tay. Nhng vic hun
luyn bng PDM nói chung khó đt đc s vng chc.
Ngoài ra, còn có cách tip cn da trên màu sc ca da trên bàn tay [17] bi vì
màu da tng đi thun nht. ây cng không phi mt cách tip cn tt vì các b
nhn dng xây dng trên đc trng là màu da rt nhy cm vi ánh sáng, và h thng
s nhn dng sai khi mu đa vào có cha các đi tng khác có màu ging vi màu
da
Nhìn chung, trong các cách tip cn trên đu có chung mt hn ch là không th
đt đc s cân đi gia kh nng nhn dng và thi gian x lý. Trong khi đó, hin có
mt mô hình đang đt đc s cân đi gia 2 mt này và hin đang đc Viola và
Jones áp dng rt thành công trong lnh vc nhn dng mt ngi: mô hình Cascade of
Boosted Classifiers vi đc trng s dng là Haar Feature [1] (mô hình cascade này
do chính Viola và Jones đ ngh). Chng 1. M đu
10
Cascade of Boosted Classifiers là mt cu trúc cây mà  mi tng là mt classifier
(b phân loi). Classifier này đc xây dng bng thut toán AdaBoost trên nguyên tc

tun t nh trong hình 3 mà bn thân các c ch cng đc phân thành nhóm do s
ging nhau gia mt s c ch trong h thng 24 c ch. S ging nhau này s đc
xác đnh thông qua kt qu ca quá trình th nghim.
Các phn tip theo ca lun vn s ln lt trình bày các vn đ liên quan.
Chng 2 gii thiu cn k hn v bài toán, các vn đ đt ra, các cách tip cn và lý
do ti sao chn mô hình cascade. Chng 3 trình bày c s lý thuyt ca cách tip cn
cascade, thut toán AdaBoost và Haar Feature cùng vi các ng dng thành công ca
chúng. Chng 4 là phn áp dng mô hình lên bài toán phân loi c ch, bao gm cách
hun luyn , h thng các Haar Features s dng cùng vi cu trúc cây cascade và
cách kt hp các b nhn dng c ch đ hình thành b phân loi. Chng 5 là kt qu
th nghim và chng 6 là các đánh giá và hng phát trin ca lun vn. Chng 2. Gii thiu v h thng phân loi c ch
12
Chng 2 Gii thiu v h thng phân loi c ch
Nh đã trình bày  phn trên, nhng ng dng to ln ca bài toán phân loi c ch
mang li nhiu khó khn không nh, vic gii quyt nó đòi hòi kin thc c v nhn
dng ln máy hc. Trong đó, 2 mc tiêu ln sau cùng chính là đ chính xác và tc đ.
H thng nhn dng phi có đc các đc trng tt, cha đng đc nhiu thông tin v
đi tng. i vi các c ch, tuy có th s dng các đc trng v hình hc nh chiu
ca ngón tay hay đng bao, nhng các đc trng này không phi lúc nào cng rõ ràng
và đ tin cy đ phân bit bàn tay vi các đi tng xung quanh, đc bit là di các
điu kin chiu sáng khác nhau.


Hình 4 - H thng 24 c ch
H thng phân loi gm 3 phn chính:
1. Module hun luyn: xây dng b nhn dng cho tng c ch (Sign Detector). B
nhn dng này đc t chc theo cu trúc Cascade of Boosted Classfiers, mt
cascade tree mà mi tng là mt strong classifier đc xây dng bng Gentle
AdaBoost [4] - mt bin th ca thut toán AdaBoost. Mi classifier này là mt
chui các weak classifiers – các classifier đn gin ch cn có đ chính xác trên
50% - mi weak classifier s gm 1 haar feature và 1 ngng đ phân loi. Kt
qu tr ra ca module này là các tp tin d liu ng vi cu trúc cascade tree to
thành.
2. Module nhn dng c ch: to li cascade tree t tp tin ca b nhn dng đã
xây dng đ tin hành nhn dng. Ví d s dng tp tin ca b nhn dng c ch
A thì ta s đc A-Detector, vic nhn dng s là nhn dng mt vùng nh có
phi c ch A hay không. Module này nhn vào mt nh, trích ra tt c các vùng
nh vi v trí và kích thc khác nhau, đa chúng vào cascade tree và tr ra các Chng 2. Gii thiu v h thng phân loi c ch
14
hình ch nht ng vi các vùng nh đc b nhn dng đánh giá là c ch. Vic
nhn dng  khâu này đc áp dng thêm mt s phng pháp heuristic nhm
tng detection rate và gim false alarm cho h thng.
3. B phân loi c ch: kt hp các b nhn dng c ch đ thc hin phân loi. B

Chng 3 Các c s lý thuyt
3.1 Tip cn Boosting
Boosting là k thut dùng đ tng đ chính xác cho các thut toán hc (Learning
algorithm). Nguyên lý c bn ca nó là kt hp các weak classifiers thành mt strong
classifier. Trong đó, weak classifier là các b phân loi đn gin ch cn có đ chính
xác trên 50%. Bng cách này, chúng ta nói b phân loi đã đc “boost”.
Xét mt bài toán phân loi 2 lp (mu cn nhn dng s đc phân vào 1 trong 2 lp)
vi D là tp hun luyn gm có n mu. Trc tiên, chúng ta s chn ngu nhiên ra n
1

mu t tp D (n
1
<n) đ to tp D
1
. Sau đó, chúng ta s xây dng weak classifier đu
tiên C
1
t tp D
1
. Tip theo, chúng ta xây dng tp D
2
đ hun luyn b phân loi C
2
.
D
2
s đc xây dng sao cho mt na s mu ca nó đc phân loi đúng bi C
1
và
na còn li b phân loi sai bi C

cùng, chúng ta s hun luyn b phân loi C
3
t D
3
.
Bây gi chúng ta đã có mt strong classifier: s kt hp C
1
, C
2
và C
3
. Khi tin
hành nhn dng mt mu X, kt qu s đc quyt đnh bi s tha thun ca 3 b C
1
,
C
2
và C
3
: Nu c C
1
và C
2
đu phân X vào cùng mt lp thì lp này chính là kt qu
phân loi ca X; ngc li, nu C
1
và C
2
phân X vào 2 lp khác nhau, C3 s quyt đnh
X thuc v lp nào.
Chng 3. Các c s lý thuyt
17
Có th hình dung mt cách trc quan nh sau: đ bit mt nh có phi là bàn tay
hay không, ta hi T ngi (tng đng vi T weak classifiers xây dng t T vòng lp
ca boosting), đánh giá ca mi ngi (tng đng vi mt weak classifier) ch cn
tt hn ngu nhiên mt chút (t l sai di 50%). Sau đó, ta s đánh trng s cho đánh
giá ca tng ngi (th hin qua h s
α
), ngi nào có kh nng đánh giá tt các mu
khó thì mc đ quan trng ca ngi đó trong kt lun cui cùng s cao hn nhng
ngi ch đánh giá tt đc các mu d. Vic cp nht li trng s ca các mu sau
mi vòng boosting chính là đ đánh giá đ khó ca các mu (mu càng có nhiu ngi
đánh giá sai là mu càng khó).

Hình 6 - Strong classifier H(x) xây dng bng AdaBoost
Các weak classifiers h
k
(x) đc biu din nh sau:
⎩
⎨
⎧
<
=
otherwise
pxfp
xh
kkkk
k

k
: h s quyt đnh chiu ca bt phng trình
Công thc trên có th đc din gii nh sau: nu giá tr vector đc trng ca mu cho
bi hàm lng giá ca b phân loi vt qua mt ngng cho trc thì mu là object
(đi tng cn nhn dng), ngc li thì mu là background (không phi đi tng).
Thut toán AdaBoost:
1. Cho mt tp hun luyn gm n mu có đánh du (x
1
, y
1
), (x
1
, y
1
), , (x
n
,
y
n
) vi x
k
∈ X = (x
k1
, x
k2
, , x
km
) là vector đc trng và y
k
∈ {-1, 1} là

vi
ε
j
nh nht, ta đc h
t
.
}1,1{:
−
→Xh
t

• Cp nht li trng s
⎩
⎨
⎧
≠
=
×=
−
+
kkt
kkt
t
k,t
k,t
y)x(h,e
y)x(h,e
Z
w
w