BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

PHẠM HỒNG NGỰ

NHẬN DẠNG ĐỐI TƯỢNG
SỬ DỤNG THUẬT TOÁN ADABOOST

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC
CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN ĐĂNG BÌNH

Huế, 2009

MỞ ĐẦU


2

Nhận dạng hay nhận biết một đối tượng là một khả năng tự nhiên của con
người cũng như các loài vật, theo một cách bản năng nhất mọi loài vật qua cảm
nhận từ các cơ quan cảm giác như: mắt, mũi, miệng, tay,… bằng hành động nhìn,
nghe, ngửi,… có thể dễ dàng cảm nhận ngay được đối tượng đang tiếp xúc với mình
là cái gì, quen hay lạ. Chính vì vậy, có thể nói rằng cơ thể mỗi một loài vật chính là
một hệ thống nhận dạng tối ưu nhất.

AdaBoost (Adaptive Boosting) là một giải thuật máy học được đề xuất bởi
Yoav Freund và Robert Schapire [23] vào năm 1995. Nó là một tiếp cận boosting và
hoạt động trên nguyên tắc kết hợp tuyến tính các bộ phân loại yếu để có một bộ
phân loại mạnh. Do những ưu điểm đó nên đã có rất nhiều nghiên cứu về nhận dạng
đối tượng đã chọn AdaBoost để làm công cụ thực hiện.
Với những lý do trên tôi chọn đề tài “Nhận dạng đối tượng sử dụng thuật
toán AdaBoost”
Luận văn chia thành ba chương, nội dung chủ yếu của Chương 1 tìm hiểu
những kiến thức tổng quan về nhận dạng đối tượng và việc ứng dụng AdaBoost để
nhận dạng đối tượng, cụ thể là nhận dạng khuôn mặt người.
Trong Chương 2 tìm hiểu về thuật toán AdaBoost và mô hình áp dụng thuật
toán vào việc nhận dạng đối tượng
Chương 3 tập trung về vấn đề thực nghiệm nhận dạng khuôn mặt, bao gồm
chuẩn bị bộ dữ liệu, các bước tiến hành, lượng hóa kết quả huấn luyện và kết quả
kiểm thử
Phần cuối của luận văn là kết luận và hướng phát triển của đề tài.
Chương 1
TỔNG QUAN
Chương này giới thiệu tổng quan về nhận dạng đối tượng, các hướng nghiên
cứu về lĩnh vực này, sơ lược về những công trình nghiên cứu về nhận dạng có sử
dụng thuật toán AdaBoost


4

1.1 Định nghĩa bài toán nhận dạng đối tượng
Nhận dạng đối tượng (Object recognition) lĩnh vực thuộc “machine learning”
nghiên cứu việc tìm một đối tượng trong một ảnh hay video cho trước, đó là việc
phát hiện lớp đối tượng cụ thể với các lớp đối tượng khác của hệ thống.



6

c. Sự biến dạng của đối tượng: Biến dạng của đối tượng có thể làm ảnh
hưởng đáng kể lên các thông số của đối tượng đó. Chẳng hạn, cùng một khuôn mặt
một người, nhưng có thể sẽ rất khác khi họ cười hoặc sợ hãi,v.v...

Hình 1.4: Minh họa sự biến dạng
d. Sự che khuất: Đối tượng có thể bị che khuất bởi các đối tượng khác.

Hình 1.5: Minh họa sự che khuất
e. Sự phức tạp của hình nền: Hình nền phức tạp sẽ khiến việc nhận dạng
trở nên khó khăn.


7

Hình 1.6: Minh họa hình nền phức tạp

f. Điều kiện của ảnh: Ảnh được chụp trong các điều kiện khác nhau về:
chiếu sáng, về tính chất camera (máy kỹ thuật số, máy hồng ngoại,v.v...) ảnh hưởng
rất nhiều đến chất lượng ảnh.

Hình 1.7: Minh họa độ sáng khác nhau
1.3 Các ứng dụng nhận dạng đối tượng


8

Bài toán nhận dạng đối tượng có thể áp dụng rộng rãi trong nhiều ứng dụng

• Phát hiện đối tượng (detection)
• Phân lớp đối tượng (classification)

Ảnh/video

Tiền xử lý

Ảnh đã
xử lý

Trích chọn
đặc trưng
Vectơ
đặc
trưng

Vị trí đối
tượng

Nhận
dạng

Phát hiện
Phân lớp
đối tượng
đối tượng
Hình 1.8: Các bước trong hệ thống nhận dạng mặt người
Ảnh đầu vào được thu nhận và tiền xử lý sau đó các ảnh được qua công đoạn
tiền xử lý nhằm tăng độ chính xác cho hệ thống. Các ảnh sau đó được trích chọn đặc
trưng để tạo ra các vectơ đặc trưng trong bước rút trích đặc trưng. Những véc-tơ đặc

khi nhận dạng có thể nhận dạng thiếu các đối tượng có trong ảnh, vì những đối
tượng này không thể thỏa mãn tất cả các luật đưa ra. Nhưng các luật tổng quát quá
thì có thể chúng ta sẽ nhận dạng lầm một vùng nào đó không phải là đối tượng mà
lại nhận dạng là đối tượng và cũng khó khăn mở rộng yêu cầu từ bài toán để nhận
dạng các đối tượng có nhiều tư thế khác nhau. Có một số nghiên cứu từ rất sớm đã
áp dụng phương pháp này như của Kanade [17].
b. Hướng tiếp cận dựa trên đặc trưng bất biến: Mục tiêu các thuật toán đi
tìm các đặc trưng mô tả cấu trúc đối tượng, các đặc trưng này sẽ không thay đổi
khi vị trí đối tượng, vị trí đặt thiết bị thu hình hoặc điều kiện ánh sáng thay đổi.


11

Đây là hướng tiếp cận theo kiểu bottom-up. Các tác giả cố gắng tìm các đặc trưng
không thay đổi của đối tượng để nhận dạng đối tượng. Dựa trên nhận xét thực tế,
con người dễ dàng nhận biết các đối tượng trong các tư thế khác nhau và điều kiện
ánh sáng khác nhau, thì phải tồn tại các thuộc tính hay đặc trưng không thay đổi.
Có nhiều nghiên cứu đầu tiên nhận dạng các đặc trưng đối tượng rồi chỉ ra có đối
tượng trong ảnh hay không. Ví dụ: Các đặc trưng như: lông mày, mắt, mũi, miệng,
và đường viền của tóc được trích bằng phương pháp xác định cạnh. Trên cơ sở các
đặc trưng này, thực hiện việc xây dựng một mô hình thống kê để mô tả quan hệ của
các đặc trưng này và nhận dạng sự tồn tại của khuôn mặt trong ảnh.
Một vấn đề của các thuật toán theo hướng tiếp cận đặc trưng cần phải điều
chỉnh cho phù hợp điều kiện ánh sáng, nhiễu, và bị che khuất. Đôi khi bóng của đối
tượng sẽ tạo thêm cạnh mới, mà cạnh này lại rõ hơn cạnh thật sự của nó, vì thế nếu
dùng cạnh để nhận dạng sẽ gặp khó khăn. Những công trình sử dụng hướng tiếp cận
này có thể kể đến là: K. C. Yow và R. Cipolla 1997 [8], T. K. Leung 1995 [22].
c. Hướng tiếp cận dựa trên so khớp mẫu: Trong so khớp mẫu, các mẫu
chuẩn của đối tượng (thường được chụp thẳng) sẽ được nhận dạng trước hoặc nhận
dạng các tham số thông qua một hàm. Từ một ảnh đưa vào, tính các giá trị tương

hiện các mẫu đối tượng và không phải là đối tượng. Có nhiều mô hình máy học
được áp dụng trong hướng tiếp cận này: Eigenface (M. Turk và A. Pentland 1991
[10]), Mô hình dựa trên phân phối (K. Sung and T. Poggio 1998 [9]), Mạng Nơ-ron
(H. Rowley 1998 [20]), Support Vector Machine (E. Osuna et al 1997 [12]), Phân
lớp Bayes (H. Schneiderman và T. Kanade 1998 [19]), Mô hình Markov ẩn (A.


13

Rajagopalan et al 1998 [16]), và các mô hình tăng cường AdaBoost của P. Viola và
M. Jones [13],[14]; FloatBoost do Stan Z. Li và Zhen Qiu Zhang 2004 [20],[21].
1.6 Tổng quan về nhận dạng đối tượng với thuật toán AdaBoost
Nhận dạng đối tượng bằng thuật toán theo kỹ thuật boosting với thuật toán
AdaBoost đã và đang được coi là một phương pháp hiệu quả, vừa đảm bảo tốc độ
nhận dạng vừa có độ chính xác cao.
Violas và Jones [15],[16] áp dụng thành công trong việc xây dựng một bộ
phát hiện khuôn mặt nhanh bằng cách dùng thuật toán AdaBoost kết hợp các bộ
phân loại yếu sử dụng các đặc trưng Haar-like theo mô hình cascade. Đầu tiên, một
hình ảnh được chia nhỏ thành các ảnh con (sub-image), mỗi ảnh được biểu thị bởi
một vector đặc trưng. Violas và Jones đã trích xuất bốn đặc trưng bằng cách sử
dụng bộ mặt nạ như hình dưới để phát hiện khuôn mặt. Với mỗi mặt nạ, tổng cấp
xám của các điểm ảnh trong vùng sáng trừ tổng cấp xám trong cùng tối được coi
như là một đặc trưng. Vì vậy với cách phân chia thành các ảnh con sẽ có nhiều hơn
một triệu các đặc trưng và mỗi đặc trưng được tính rất nhanh.
Phương pháp của Viola và Jones có tốc độ xử lý khá nhanh, gấp khoảng từ
10-15 lần so với các phương pháp hiện tại và tỷ lệ chính xác hơn 80% trên ảnh xám.
Có thể nói, phương pháp này được công nhận là một trong những bước đột phá lớn
của lĩnh vực máy học tính nói chung và phát hiện khuôn mặt nói riêng.
Schneiderman và Kanade [19] cải tiến thành công bằng cách dùng wavelet
để trích đặc trưng rồi xây dựng hệ thống học với thuật toán Adaboost, dựa trên xác

học yếu và do đó có thể được linh hoạt kết hợp với phương pháp nào cho việc tìm
kiếm bộ bộ phân loại yếu. Với những ưu điểm đó, ta nghiên cứu áp dụng vào việc
phát hiện và nhận dạng đối tượng.
2.1 Thuật toán AdaBoost
2.1.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 bộ phân loại yếu


15

thành một bộ phân loại mạnh. Trong đó, bộ phân loại yếu là các bộ phát hiện đơ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át hiện đã
được “boost”.

Hình 2.1: Minh họa hoạt động theo kỹ thuật boosting
Xét một bài toán phát hiện 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 n1 mẫu từ tập D (n1
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ó).
Thuật toán có đầu vào là một tập huấn luyện {(x1, y1), (x2, y2),....,(xn, yn)}
trong đó mỗi xi thuộc về một số tên miền hay không gian X và mỗi nhãn yi thuộc
tập nhãn Y ta giả sử rằng Y = {-1, +1}. AdaBoost gọi một thuật toán học yếu trong
một dãy vòng lặp từ t= 1,…,T. Một trong những ý tưởng chính của thuật toán là để
duy trì một phân phối, hoặc thiết lập của trọng số qua tập huấn luyện. Ban đầu, tất
cả trọng số được thiết lập bằng nhau, nhưng trên mỗi vòng lặp, trọng số của các
mẫu phát hiện không chính xác được tăng lên để bộ học yếu tập trung vào các mẫu
khó trong tập huấn luyện.

Hình 2.3: Bộ phân loại mạnh H(x) xây dựng bằng AdaBoost


18

Công việc của bộ học yếu là để tìm một bộ phân loại yếu

ht : X → {−1, +1} tương ứng với bộ phân phối Dt. Độ tốt của một giả thuyết yếu
được đo bằng hệ số lỗi của nó:

ε t = Pri ~ D [ ht ( xi ) ≠ yi ] =
t

∑

i:ht ( xi ) ≠ yi

Dt (i )

⎟
2 ⎝ εt ⎠

Cập nhật: D t + 1 , i

−α t
, (xk ) = yi
D t ( i ) ⎧⎪ e
=
× ⎨ α
t
Zt
⎪⎩ e , ( x k ) ≠ y i


19

=

Dt (i ) exp(−α t yi ht ( xi ))
Zt

Với Zt là nhân tố bình thường hóa

- Đầu ra:

⎛ T
⎞
H ( x) = sign ⎜ ∑ α t ht ( x) ⎟
⎝ t =1


1
− γ t ; Freund và Schapire [24], [25] chứng minh rằng lỗi huấn
2

luyện (các mẫu lỗi trong tập huấn luyện) của phát hiện H vào khoảng:

∏ ⎡⎣2
t

⎛

⎞

ε t (1 − ε t ) ⎤⎦ = ∏ 1 − 4γ t2 ) ≤ exp ⎜ −2∑ γ t2 ⎟
t

⎝

t

⎠

Vì vậy, nếu mỗi bộ phân loại yếu hơi tốt hơn so với ngẫu nhiên do bởi
γ t > γ với mỗi γ > 0 thì lỗi huấn luyện cũng giảm theo cấp số nhân.

Đây là sự kế thừa các thuật toán boosting trước đó, tuy nhiên các thuật toán
boosting trước đây thì mức độ ràng buộc là thấp hơn. AdaBoost thích nghi ở chổ nó
điều chỉnh theo tỷ lệ lỗi của những bộ phân loại yếu do vậy thuật toán có tên là
AdaBoost là viết tắt của Adaptive.


Hình 2.6: Minh họa đặc trưng Haar-like
Trong quá trình huấn luyện, số lượng xử lý trên các đặc trưng Haar-like là rất
lớn, việc tính tổng các điểm ảnh cho bởi từng đặc trưng làm cho thời gian xử lý tăng
đáng kể. Để khắc phục điều này, Viola và Jones đã đưa ra khái niệm Integral
Image [13] để tính toán nhanh cho các đặc trưng cơ bản.
Integral Image

Hình 2.7: Giá trị integral image [13] tại điểm (x,y) bằng tổng giá trị của tất
cả điểm ảnh phía trên và bên trái (x,y)


23

Giá trị các đặc trưng có thể được tính toán nhanh chóng bằng cách sử dụng
khái niệm gọi là integral Image [13], Integral Image [13] tại vị trí (x,y) bằng tổng
các giá trị điểm ảnh phía trên và bên trái của (x,y), bao gồm:

ii ( x, y ) =

∑

i( x, , y , )

x, ≤ x , y , ≤ y

Với ii ( x, y ) là integral image và i(x,y) là giá trị điểm ảnh bao gồm cặp công
thức sau:

s ( x, y ) = s ( x, y − 1) + i ( x, y )

của cây, các bộ phân loại ở tầng sau được huấn luyện bằng những mẫu negative mà
bộ phân loại trước nó nhận dạng sai, tức là nó sẽ tập trung học từ các mẫu
background khó hơn, do đó sự kết hợp các bộ phân loại này lại sẽ giúp bộ phát hiện
có false alarm thấp. Với cấu trúc này, những mẫu background dễ nhận diện sẽ bị
loại ngay từ những tầng đầu tiên, giúp đáp ứng tốt nhất đối với độ phức tạp gia tăng
của các mẫu đưa vào, đồng thời giúp rút ngắn thời gian xử lý.

Mô hình cascade
Đúng

C1

Ảnh
Sai

Đúng

C2
Sai

Đúng

C3
Sai

C4
Sai

Không phải đối tượng


boost cascade để nhận dạng sơ bộ bàn tay, lớp bên dưới là từng mô hình boost
cascade ứng với từng cụm được chia bằng K-mediod. Kết quả thu được rất khả
quan, cấu trúc cascade của bộ nhận dạng ở lớp trên gồm 11 tầng với tổng cộng 634
bộ phân loại yếu đã đạt tỉ lệ nhận dạng là 99.8% trên tập kiểm thử, còn các bộ
cascade ớ lớp dưới có tỉ lệ nhận dạng trung bình là 97.4%.
2.2.1.4 Đánh giá
Trước khi có hệ thống của Viola và Jones [13], hệ thống của Rowley [17]
được đánh giá là bộ nhận dạng có tốc độ nhanh nhất. Hệ thống của Rowley thực