ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN LÊ HỒNG DŨ PHÁT HIỆN KHUÔN MẶT
DỰA TRÊN ĐẶC TRƯNG LỒI LÕM

LUẬN VĂN THẠC SĨ NGÀNH TIN HỌC

Thành phố Hồ Chí Minh - 2005

Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 1
Nội dung

Trang
Mục lục 1

Lời cám ơn 4

Chương 1. Giới thiệu 5

1.1 Bài toán nhận dạng mặt người và những khó khăn 5

1.1.1 Bài toán nhận dạng mặt người 5

1.1.2 Những khó khăn của nhận dạng khuôn mặt 5

1.2 Các ứng dụng liên quan đến nhận dạng mặt người 6

1.3 Tổng quan kiến trúc của một hệ thống nhận dạng mặt người 7

1.4 Xác định phạm vi đề tài 8

Chương 2. Các công trình liên quan 10

2.1 Các hướng tiếp cận liên quan đến phát hiện và nhận dạng khuôn mặt 10

2.2 Các tiếp cận liên quan đến phân tích đặt trưng lồi lõm 11



Chương 4. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm 30

4.1 Tập mẫu học 30

4.2 Mô hình thống kê 31

4.2.1 Gán nhãn 31

4.2.2 Thống kê 32

4.2.3 Đánh giá dùng cho phát hiện khuôn mặt 33

4.2.4 Hậu xử lý 34

4.3 Cơ sở lý thuyết của mô hình 35

Chương 5. Thử nghiệm và kết quả 38

5.1 Thử nghiệm 38

5.2 Kết quả 38

Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 3
5.3 Nhận xét 39
5.4 Một số kết quả tiêu biểu 40

Chương 6. Kết luận và hướng phát triển 46

chia sẽ với con những khó khăn trong lúc làm luận văn này.
Xin cám ơn những người bạn thân yêu, những người đã yêu mến, chia sẽ với
tôi trong lúc tôi thực hiện luận văn này.
Xin cám ơn các thầy cô, các anh chị và các bạn đồng nghiệp trong Khoa Công
nghệ thông tin, ĐH Khoa học tự nhiên đã giúp đỡ
, tạo điều kiện tốt nhất để tôi có thể
hoàn thành tốt luận văn này.
Luận văn này là món quà mà tôi dành tặng cho tất cả mọi người thân yêu của
tôi, với tất cả tấm lòng mình!
Thành phố Hồ Chí Minh, ngày 10 tháng 11 năm 2005
Trần Lê Hồng Dũ
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 5
CHƯƠNG 1
GIỚI THIỆU
1.1 Bài toán nhận dạng mặt người và những khó khăn
1.1.1 Bài toán nhận dạng mặt người
Hệ thống nhận dạng mặt người là một hệ thống nhận vào là một ảnh hoặc một
đoạn video (một chuỗi các ảnh). Qua xử lý tính toán hệ thống xác định được vị trí
mặt người trong ảnh (nếu có) và xác định là người nào trong số những người hệ
thống đã được biết (qua quá trình học) hoặc là người lạ.

Hình 1.1 Ví dụ
về hệ thống nhận dạng mặt người
1.1.2 Những khó khăn của nhận dạng khuôn mặt
Bài toán nhận dạng mặt người là bài toán đã được nghiên cứu từ những năm
70. Tuy nhiên, đây là một bài toán khó nên những nghiên cứu hiện tại vẫn chưa đạt
được kết quả mong muốn. Chính vì thế vấn đề này vẫn đang được nhiều nhóm trên
Hệ thống nhận

ủa ảnh: Các ảnh của khuôn mặt có thể biến đổi rất nhiều với các
góc quay khác nhau của trục camera. Chẳng hạn chụp với trục máy ảnh nghiêng làm
cho khuôn mặt bị nghiêng so với trục của ảnh.
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 khuôn mặt.
1.2 Các ứng dụng liên quan đến nhận dạng mặt người
Bài toán nhận dạng mặt người có thể áp dụng rộng rãi trong nhiều ứng dụng
thực tế khác nhau. Đó chính là lý do mà bài toán này hấp dẫn rất nhiều nhóm nghiên
cứu trong thời gian dài. Các ứng dụng liên quan đến nhận dạng mặt người có thể kể
như:
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 7
- Hệ thống phát hiện tội phạm: camera được đặt tại một số điểm công cộng
như: siêu thị, nhà sách, trạm xe buýt, sân bay,v.v... Khi phát hiện được sự xuất hiện
của các đối tượng là tội phạm, hệ thống sẽ gởi thông điệp về cho trung tâm xử lý.
- Hệ thống theo dõi nhân sự trong một đơn vị: giám sát giờ ra vào của từng
nhân viên và chấm công.
- Hệ thống giao tiếp ng
ười máy: thay thế việc tương tác giữa người và máy
theo những cách truyền thống như: bàn phím, chuột,v.v...Thay vào đó là sử dung các
giao tiếp trực quan: biểu cảm khuôn mặt, dấu hiệu, cử chỉ bằng tay (visual input,
visual interaction).
- Hệ thống tìm kiếm thông tin trên ảnh, video dựa trên nội dung (chỉ mục theo
người). Chẳng hạn như: đài truyền hình Việt Nam (VTV) có một kho dữ liệu video
tin tức khá lớn cần tìm kiếm nhanh những đoạ
n video nào có G. Bush hoặc Bin
Laden.

định vị khuôn mặt nếu có trong ảnh. Do các
điều kiện khó khăn của bài toán (nêu trong phần 1.1.2), chúng tôi đưa ra những giả
định và ràng buộc sau nhằm giảm độ phức tạp của bài toán phát hiện khuôn mặt:
- Thuật toán giải quyết cho ảnh đơn (chưa xử lý cho video)
- Ảnh khuôn mặt được chụp thẳng hay góc nghiêng không đáng kể (không
quá 10
0
).
Phát hiện
khuôn mặt
(Theo dõi)
Phân đoạn
khuôn mặt
Rút trích
đặc trưng
Phân lớp
khuôn mặt
Ảnh/Video
Vị trí
khuôn
mặt
Khuôn mặt đã
đư
ợc phân đoạn
Véc-tơ
đ
ặc trưng
Chỉ số
khuôn mặt
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Phương pháp đối sánh mẫu: Trong hướng tiếp cận này, một mẫu khuôn mặ
t
chuẩn được định nghĩa bằng tay trước hoặc được tham số hóa bằng một hàm số. Mẫu
này được sử dụng để phát hiện khuôn mặt bằng cách quét nó qua ảnh và tính toán giá
trị tương đồng cho mỗi vị trí. Việc xuất hiện một khuôn mặt tại một vị trí nào đó
trong ảnh phụ thuộc vào giá trị tương đồng của điểm đó so với mẫu chuẩn. I. Craw
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 11
1992 [17] đã áp dụng một mẫu cứng trong khi A. Lanitis 1995 [15] sử dụng một mẫu
có thể biến dạng trong bước phát hiện khuôn mặt.
Phương pháp dựa trên máy học: Ngược với phương pháp đối sánh mẫu sử
dụng các mẫu được các chuyên gia định nghĩa trước, phương pháp này sử dụng
những mẫu được rút trích qua một quá trình học. Nói cách khác, các thuật toán dựa
trên máy học dùng các kỹ thuật phân tích thống kê và máy học để xấp x
ĩ một hàm
phân lớp tuyến tính. 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 [16]), Mô hình dựa trên phân phối (K.
K. Sung and T. Poggio 1998 [6]), Mạng Nơ-ron (H. Rowley 1998 [7]), Support
Vector Machine (E. Osuna et al 1997 [10]), Phân lớp Bayes (H. Schneiderman và T.
Kanade 1998 [8]), Mô hình Markov ẩn (A. Rajagopalan et al 1998 [9]), và các mô
hình tăng cường (AdaBoost của P. Viola và M. Jones 2001 [4][5]; FloatBoost do Stan
Z. Li và Zhen Qiu Zhang 2004 [2][3]).
2.2 Các tiếp cận liên quan đến phân tích đặt trưng lồi lõm
Năm 1983, James L. Crowley đã đưa ra khái niệm ridge và peak [19][20].
Ridge là các điểm lồi trên ảnh. Tập các điểm ridge trên ảnh sẽ tạo thành những đường
xương sống và các đường này sẽ tạo thành các chùm tia gọi là peak (chùm). James L.
Crowley sử dụng phép hiệu của lọc Low Pass để rút ra các điểm ridge (lồi) trên ảnh,
và sau đó một thuật toán duyệt để kết chúng lại với nhau thành các đặc trư
ng ridge và

Các hướng tiếp cận trình bày trong phần 2.1 cho thấy khá tổng quát và ổn
định, nhưng vẫn còn một vài hạn chế nhất định. Hầu hết các hướng tiếp cận nêu trên
sử dụng các đặc trưng chủ yếu dựa trên độ sáng điểm ảnh, với mức độ ý niệm ngữ
nghĩa thấp. Vì vậy, các mối quan hệ giữa các đặc trưng rút trích được cần phải thêm
vào các luật heuristic để
phân tích hiệu quả hơn. Mặt khác, nếu không có các tri thức
bổ sung được định nghĩa trước, các mô hình có cấp ý niệm thấp này không thể đạt
được độ chính xác cao hơn trong nhận dạng mặt người. Vì thế, để đạt độ chính xác
cao hơn trong nhận dạng mặt người, chúng ta cần phải hướng đến một loại đặc trưng
dựa trên mô hình ý niệm cao hơn như là cấu trúc của khuôn mặt.
Để gi
ải quyết khó khăn nêu trên, trong luận văn này chúng tôi đề xuất một đặc
trưng có mô hình ý niệm cao hơn: lồi và lõm tại nhiều mức. Theo cách tiếp cận này,
cấu trúc khuôn mặt được biểu diễn bằng một cây cấp bậc của các lồi (chỏm) và lõm
(thung lũng). Dựa trên đặc trưng này, chúng tôi áp dụng một mô hình thống kê để xác
định, phát hiện khuôn mặt. Trong luận văn này, chúng tôi tập trung chính vào bài
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 13
toán phát hiện khuôn mặt mà không giải quyết bài toán nhận dang. Tuy nhiên, trong
phần cuối, chúng tôi sẽ thảo luận chi tiết hơn khả năng sử dụng đặc trưng này để nhận
dạng khuôn mặt cũng như việc mở rộng đặc trưng này cho bài toán rộng hơn: phân
loại đối tượng dựa theo cấu trúc.
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 14
CHƯƠNG 3
ĐẶC TRƯNG LỒI LÕM
3.1 Lồi và Lõm
Hiểu theo nghĩa thật sự của nó, lồi (chỏm) là các điểm cao nhất trên dãy núi và

vùng lồi và lõm kích thước lớn và ít chi tiết hơn. Ý tưởng nghiên cứu này đến một
cách tự nhiên, cũng giống như khi nhìn một người từ rất xa, ta chỉ có thể nhìn được
dáng, gần hơn một tí ta có thể nhìn được mặt nhưng không nhìn được các chi tiết mắt,
mũi, miệng trên khuôn mặt, và gần hơn nữa ta mới có thể nhìn chi tiết mắt mũi,
mi
ệng. Việc này tương ứng với cách tiếp cận phân tích nhiều mức khác nhau của
chúng tôi.
Do bộ lọc Laplacian-of-Gaussian chỉ có thể sử dụng để phát hiện thông tin
cạnh qua các điểm biên (zero crossing), nên nó không thể dùng cho việc phát hiện
các vùng lồi và lõm khi các thông tin cạnh biên bị đứt nét. Trong phần tiếp theo
chúng tôi sẽ đề xuất một phương pháp đơn giản để rút trích các vùng lồi và lõm.
(a) Ảnh gốc

(b) Ảnh ridge và valley

Hình 3.2 Dò tìm thông tin lồi và lõm trên ảnh khuôn mặt sử dụng LoG với σ =
2

Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 16
3.2 Rút trích vùng lồi và vùng lõm
3.2.1 Điểm lồi và điểm lõm
Gọi
),( yxI
là một hàm hai biến biểu diễn một ảnh I. Hàm số này thiết lập một
mặt

P
δ
(3.2)
Trong công thức 3.1 và 3.2, R
P
là tập các điểm lồi và V
P
là tập các điểm lõm.
Ký hiệu
),( yxLoG
là giá trị của Laplacian-of-Gaussian tại điểm
),( yx
. Như đã trình
bày trong phần 3.1, mục đích của chúng tôi là rút trích các vùng lồi và lõm chứ không
chỉ rút trích điểm lồi và điểm lõm. Vì thế chúng tôi đã mở rộng công thức 3.1 và 3.2
cho phù hợp với bài toán rút trích vùng.
3.2.2 Dò tìm và rút trích vùng lồi và vùng lõm
Để đánh giá một vùng có phải là lồi, là lõm hoặc không lồi cũng không lõm,
chúng tôi đề xuất một bộ lọc như sau:

Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 17

(a) Vùng đang xét trên ảnh

(b) một bộ lọc
vuông
Hình 3.3 Dò tìm vùng trên ảnh
Ứng với vùng đang xét – một hình vuông

<∧≥⇔
>∧≥⇔
=
otherwisenormal
RFRFvalley
RFRFridge
R 0)()(
0)()(
δ
δ
(3.4)
Công thức 3.4 là công thức mở rộng của 3.1 và 3.2 nhằm để dò tìm các vùng
lồi và lõm trên ảnh. Sự khác biệt chủ yếu ở chổ ta sử dụng bộ lọc hiệu trong 3.4 thay
vì sử dụng Laplacian-of-Gaussian trong 3.1 và 3.2. Chúng ta để ý rằng, bằng cách
thay kích thước S của vùng đang xét, hay nói cách khác là kích thước của lọc, chúng
ta có thể dò tìm các vùng lồi và lõm ứng với nhiều kích cở, mức độ khác nhau. Ngoài
ra, để dò tìm và rút trích các vùng lồi lõm có hình dạng khác nhau, chúng tôi sử dụng
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 18
một tập các lọc hình học có hình dạng như trong hình 3.4 thay vì chỉ sử dụng một bộ
lọc vuông.

(a) Lọc hình vuông

(b) Lọc chữ nhật ngang

(c) Lọc chữ nhật đúng
Hình 3.4 Tập các bộ lọc kích thước S
Với sự bổ sung tập bộ lọc như trên, công thức 3.3 được viết lại như sau:

tích của vùng lân cận. Trong hình 3.4a, tổng di
ện tích của các vùng đen xung quanh
gấp đôi diện tích phần ở giữa, vì vậy chúng ta có hệ số 2. Trong hình 3.4b và 3.4c,
tổng diện tích các vùng đen gấp rưỡi diện tích phần hình chữ nhật ở giữa. Một cách
chính xác chúng ta phải dùng hệ số 1.5 trước hàm sum(R), nhưng việc tính toán trên
số thực rất chậm, do đó để tăng tốc độ tính toán ta dùng 2 hệ số nguyên là 3 và 2 thay
vì chỉ dùng 1 hệ số 1.5.
Một thông số quan tr
ọng khác trong công thức 3.4 là ngưỡng
δ
. Ngưỡng
δ

phải phụ thuộc tuyến tính vào diện tích của vùng đang xét. Chúng tôi sử dụng
Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 19
2
1
KS=
δ
đối với lọc hình vuông có kích thước S và
2
2
4KS=
δ
đối với các lọc hình
chữ nhật có kích thước S. K là một thông số thực nghiệm. Ngưỡng
δ
1

(d) Các vùng lồi lõm dò tìm với lọc kích
thước 20
(e) σ = 60, ảnh sau khi smoth bằng
Gaussian
260

(f) Các vùng lồi lõm dò tìm với lọc kích
thước 60
Hình 3.5 Dòm tìm vùng lồi lõm ở nhiều mức khác nhau
Đặt
1
σ
,
2
σ
,..
n
σ
là các mức độ được định nghĩa trước và có độ lớn tăng dần.
1
σ
là mức độ thấp nhất. Tại mức độ này, chúng ta có thể dò tìm các vùng lồi, lõm có
kích thước nhỏ và chi tiết.
n
σ
là mức độ cao nhất mà tại đó chúng ta có thể dò tìm các
vùng lồi lõm lớn hơn, ít chi tiết hơn. Tại mỗi mức, trước tiên chúng ta áp dụng một
lọc Gaussian với kích thước
2
i

),( yxS
sao cho
),( yxS
là tổng mức sáng của toàn bộ điểm ảnh trong hình chữ nhật
),,1,1( yxR
. Chúng ta có thể dễ dàng tính được
),( yxS
theo công thức truy hồi 3.7:
⎩
⎨
⎧
≠∧≠+−−−−+−
=∨=
=
00),()1,1()1,(),1(
000
),(
yxyxIyxSyxSyxS
yx
yxS
(3.7) Hình 3.6 Ảnh tích phân
Từ ảnh
),( yxS
, ta dễ dáng tính được tổng độ sáng của một hình chữ nhật bất
kỳ
),,,( btrlR
theo công thức 3.8 sau:

i
σ
bị che khuất hơn hai phần
l r
t

b

(1,1)

(W,H)

Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

Trần Lê Hồng Dũ Trang 23
ba diện tích của nó bởi vùng R’ của mức
1+i
σ
, R sẽ được gán nhãn là nút con của R’.
Bằng cách này chúng ta có thể dễ dàng tạo cây cấp bậc từ các vùng đã rút trích được.
Các vùng rút trích được trong hình 3.5 được xây dựng thành cây như sau (xem hình
3.9)

Hình 3.9 Một ví dụ về cây rút trích từ khuôn mặt
Đối với mỗi nút trong cây, chúng ta cần lưu các thông tin của nút này như: loại
(lồi hay lõm), hình dạng (vuông, chữ nhật ngang, chữ nhật đứng), vị trí tương đối của
nó so với nút cha của nó (có giá trị từ 0 đến 12, xem hình 3.10), và thông tin về độ
sáng của nó.