ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

CÙ VIỆT DŨNG

NGHIÊN CỨU VÀ XÂY DỰNG HỆ THỐNG XÁC ĐỊNH
KHUÔN MẶT CHUNG NHẤT TRONG TẬP ẢNH SỐ

LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM

Hà Nội – 2014


1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

CÙ VIỆT DŨNG

NGHIÊN CỨU VÀ XÂY DỰNG HỆ THỐNG XÁC ĐỊNH
KHUÔN MẶT CHUNG NHẤT TRONG TẬP ẢNH SỐ

Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS Bùi Thế Duy



Tôi xin cam đoan:
Những kết quả nghiên cứu đƣợc trình bày trong luận văn là hoàn toàn trung
thực, của tôi, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt
Nam. Nếu sai, tôi xin chịu hoàn toàn trách nhiệm trƣớc pháp luật.

TÁC GIẢ LUẬN VĂN

Cù Việt Dũng


4

MỤC LỤC
Trang
Lời cam đoan ................................................................................................................... 3
MỤC LỤC ....................................................................................................................... 4
Danh mục các ký hiệu và chữ viết tắt ............................................................................. 6
Danh mục các bảng ......................................................................................................... 7
Danh mục các hình vẽ, đồ thị .......................................................................................... 8
LỜI MỞ ĐẦU ................................................................................................................. 9
CHƢƠNG 1: TỔNG QUAN ......................................................................................... 10
1.1

Giới thiệu .........................................................................................................10

1.2

Phát biểu bài toán .............................................................................................11


Kết luận chƣơng 1 ............................................................................................17

CHƢƠNG 2: CƠ SỞ LÝ THUYẾT ............................................................................. 18
2.1

Phát hiện khuôn mặt.........................................................................................18

2.1.1

Các đặc trƣng giống Haar..........................................................................18

2.1.2

Phƣơng pháp Adaboost .............................................................................20

2.2

Tổng quan về các phƣơng pháp trích rút đặc trƣng .........................................22

2.2.1

Phƣơng pháp trích chọn đặc trƣng hình học .............................................23

2.2.2

Phƣơng pháp trích chọn đặc trƣng diện mạo ............................................23

2.3

Phƣơng pháp phân tích thành phần chính ........................................................24

Huấn luyện mô hình hình dáng .............................................................31

2.4.3.2

Huấn luyện hình ảnh ..............................................................................31

2.4.3.3 So khớp......................................................................................................32
2.5

Giới thiệu về phân cụm ....................................................................................33

2.5.1

Khái niệm ..................................................................................................33

2.5.2

Một số vấn đề trong phân cụm ..................................................................35

2.5.3

Phân cụm phân cấp ....................................................................................36

2.6

Kết luận chƣơng 2 ............................................................................................37

CHƢƠNG 3: XÂY DỰNG HỆ THỐNG ...................................................................... 38
3.1



4.2

Một số thực nghiệm .........................................................................................48

4.3

Kết luận chƣơng 4 ............................................................................................54

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .................................................................... 55
TÀI LIỆU THAM KHẢO ............................................................................................. 56


6

Danh mục các ký hiệu và chữ viết tắt
CSDL Cơ sở dữ liệu
ASM Active Shape Model
PCA Principal Component Analysis
HAC

Hierarchical

Agglomerative

Clustering


7


Hình 4.3:
Hình 4.4:
Hình 4.5:
Hình 4.6:
Hình 4.7:
Hình 4.8:
Hình 4.9:
Hình 4.10:
Hình 4.11:
Hình 4.12:
Hình 4.13:

Bốn đặc trƣng Haar-like cơ bản .................................................................18
Các đặc trƣng mở rộng của các đặc trƣng Haar-like cơ sở........................18
Cách tính Integral Image của ảnh ..............................................................19
Cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh .........................19
Cách tính nhanh tổng điểm ảnh của vùng D trên ảnh với các đặc trƣng
....................................................................................................................20
Thuật toán Adaboost ..................................................................................21
Hình dạng và biểu diễn của hình dạng trong mô hình ...............................29
Vị trí 68 điểm mốc trên khuôn mặt ............................................................29
Thuật toán gióng hàng tập huấn luyện .......................................................30
Quy trình huấn luyện mô hình hình dáng ..................................................31
Thuật toán so khớp hình dáng khuôn mặt..................................................32
Sơ đồ tổng quát của hệ thống .....................................................................38
Mã giả thuật toán tổng quát của hệ thống ..................................................39
Giao diện chính của hệ thống ....................................................................40
Giao diện kết quả sau khi xác định đƣợc khuôn mặt chung nhất ..............40
Giao diện kết quả phát hiện khuôn mặt .....................................................41
Chuyển ảnh khuôn mặt sang vector ...........................................................42

bức hình trong cơ sở dữ liệu. Việc tìm ra thông tin hữu ích trên lƣợng dữ liệu hình ảnh
lớn nhƣ vậy sẽ rất cấp thiết.
Nhiều thông tin đƣợc chia sẻ trên mạng xã hội thể hiện bằng các hình ảnh cung
cấp cho ngƣời dùng về thông tin của ngƣời, phong cảnh mang nhiều phong cách của
từng cá nhân. Mọi ngƣời thƣờng chia sẻ hình ảnh cá nhân trên các trang mạng xã hội
để chia sẻ chúng với gia đình, ngƣời thân, bạn bè và ngƣời quen. Tuy nhiên, mỗi khi
một ngƣời dùng muốn tìm hiểu thông tin về một ai đó gặp phải vấn đề phải tìm thông
tin về ngƣời đó rất khó khăn (tốn thời gian và nhiều khi không tìm đƣợc). Lý do của
việc này là lƣợng ảnh trên mạng xã hội quá nhiều và tăng nhanh hàng ngày.
Với một tập ảnh cho trƣớc, mỗi bức ảnh có thể có một hay nhiều hơn một khuôn
mặt gây ra nhiều khó khăn cho ngƣời dùng có thể xác định chủ thể trong tập ảnh đó
một cách nhanh nhất. Do đó, chúng ta nên cần một hệ thống có thể giúp gom các đối
tƣợng khuôn mặt về cùng một cụm (theo một độ đo tƣơng tự nào đó) trong một tập dữ
liệu ảnh có một hay nhiều khuôn mặt trong bức ảnh là vô cùng cần thiết. Từ đó xác
định đƣợc khuôn mặt chung nhất trong tập ảnh. Với sự cần thiết đó tác giả chọn đề tài
“Nghiên cứu và xây dựng hệ thống xác định khuôn mặt chung nhất trong tập ảnh
số”. Nội dung khóa luận gồm có 4 chƣơng:
Chƣơng 1: Tổng quan, giới thiệu và phát biểu bài toán, nêu một số hƣớng tiếp
cận trong việc phát hiện khuôn mặt trong ảnh
Chƣơng 2: Cơ sở lý thuyết, giới thiệu cơ sở lý thuyết một số phƣơng pháp liên
quan trong bài toán
Chƣơng 3: Xây dựng hệ thống, trình bày về xây dựng hệ thống giải quyết bài
toán.
Chƣơng 4: Thử nghiệm và kết quả đạt đƣợc, trình bày về cơ sở dữ liệu thực
nghiệm và kết quả thử nghiệm, đánh giá thử nghiệm


10

CHƢƠNG 1: TỔNG QUAN

không gian. Đề tài này nghiên cứu phân cụm ảnh thành từng cụm rồi trích chọn khuôn
mặt có trong cụm có số lƣợng lớn nhất, dựa vào đó ta có thể tra cứu xác định khuôn
mặt chung nhất một cách nhanh chóng và chính xác từ một cơ sở dữ liệu ảnh cho
trƣớc. Có nhiều phƣơng pháp phân cụm khác nhau nhƣ K-Means, Hierarchical
Agglomerative Clustering (HAC). Mỗi phƣơng pháp có những ƣu điểm, thế mạnh
riêng, và có yêu cầu riêng về cách biểu diễn dữ liệu, độ đo. So sánh các thuật toán


11

khác nhau ở các phạm vi khác nhau là không đơn giản, do vậy việc đánh giá thƣờng
dựa vào chất lƣợng kết quả phân cụm. HAC là thuật toán phân cụm cây phân cấp có
tính gia tăng cao và tạo ra đƣợc một cây phân cấp dựa theo yếu tố nào đó, theo hƣớng
tiếp cận này khóa luận sẽ áp dụng phƣơng pháp phân cụm HAC để phân cụm dữ liệu
sau đó tìm ra cá nhân xuất hiện nhiều nhất trong kho ảnh cho trƣớc bằng cách xác định
cụm có số lƣợng khuôn mặt nhiều nhất.
1.2 Phát biểu bài toán
Hệ thống xác định khuôn mặt ngƣời là một hệ thống nhận đầu vào là một tập
ảnh có thể chứa nhiều khuôn mặt trong ảnh. Qua quá trình 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 ngƣời nào là xuất hiện
nhiều nhất trong số những ngƣời hệ thống tách đƣợc.
1.2.1 Quy trình xử lý
Hệ thống gồm các bƣớc xử lý cơ bản sau
-

Dò tìm khuôn mặt
Trích rút đặc trƣng
Phân cụm

 Dò tìm khuôn mặt



12

mặt giống nhau về cùng một cụm. Khoảng cách Euclide đƣợc áp dụng để tính
toán khoảng cách giữa các đặc trƣng đƣợc trích rút cho ta biết đƣợc sự giống
nhau của các khuôn mặt. Cụm có số lƣợng lớn nhất chứa khuôn mặt chung nhất
trong tập ảnh
1.2.2 Những khó khăn, thách thức
Những bài toán liên quan đến xử lý khuôn mặt là một trong những 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ì vậy
vấn đề này vẫn đang đƣợc nhiều nhóm tác giả trên thế giới quan tâm nghiên cứu.
Những khó khăn, thách thức của bài toán có thể kể đến nhƣ sau:
 Tư thế, góc chụp: Ảnh chụp khuôn mặt có thể thay đổi rất nhiều bởi vì góc
chụp giữa camera và khuôn mặt. Chẳng hạn nhƣ: chụp thẳng, chụp
nghiêng bên trái
, hay nghiêng bên phải
, chụp từ trên xuống, chụp từ
dƣới lên,... Với các tƣ thế khác nhau, các thành phần trên khuôn mặt nhƣ mắt,
mũi, miệng có thể bị khuất một phần hoặc thậm chí khuất hết.
 Sự xuất hiện hoặc thiếu một số thành phần của khuôn mặt: Các đặ trƣng
nhƣ: râu mép, râu hàm, mắt kính,... có thể xuất hiện hoặc không. Vấn đề này
làm cho bài toán càng trở nên khó hơn rất nhiều.
 Sự biểu cảm của khuôn mặt: Biểu cảm của khuôn mặt ngƣời có thể làm ảnh
hƣởng đáng kể lên các thông số của khuôn mặt. 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,...
 Sự che khuất: Khuôn mặt có thể bị che khuất bởi các đối tƣợng khác hoặc các
khuôn mặt khác.
 Hướng củ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

so khớp mẫu, các mô hình (hay các mẫu) sẽ đƣợc học từ một tập ảnh huấn
luyện trƣớc đó theo một phƣơng pháp học nào đó thể hiện tính chất tiêu biểu
của sự xuất hiện của mặt ngƣời trong ảnh. Sau đó hệ thống (mô hình) sẽ xác
định khuôn mặt ngƣời. Phƣơng pháp này còn đƣợc biết đến với tên gọi tiếp
cận theo các phƣơng pháp học máy
1.3.1 Hƣớng tiếp cận dựa trên tri thức
Trong hƣớng tiếp cận này, các phƣơng pháp xác định mặt ngƣời đƣợc xây dựng
dựa vào các luật, các luật này phụ thuộc vào tri thức của các tác giả nghiên cứu về bài
toán xác định khuôn mặt. Có thể xây dựng các luật cơ bản để mô tả các đặc trƣng của
khuôn mặt và các quan hệ tƣơng ứng. Ví dụ, một khuôn mặt thƣờng có hai mắt đối
xứng qua trục thẳng đứng giữa khuôn mặt và có một mũi một miệng. Các quan hệ đặc
trƣng có thể là quan hệ về vị trí và khoảng cách tƣơng đối. Khó khăn của hƣớng tiếp
cận này đó là làm thế nào để chuyển các tri thức của con ngƣời về khuôn mặt sang các
luật cho máy tính một cách hiệu quả. Nếu các luật này quá chi tiết, chặt chẽ thì sẽ có
thể xác định thiếu các khuôn mặt có trong ảnh, nhƣng nếu các luật quá tổng quát thì sẽ
dẫn đến xác định sai khu vực không phải là khuôn mặt thành khuôn mặt. Ngoài ra
cũng khó để mở rộng phạm vi của bải toán để xác định các khuôn mặt có nhiều tƣ thế
khác nhau.
Có nhiều cách để xây dựng chƣơng trình xác định mặt ngƣời theo hƣớng tiếp
cận dựa trên tri thức. Thông thƣờng chƣơng trình sẽ đƣợc xây dựng theo hƣớng dựa
vào một phƣơng pháp nào đấy chọn ra các ứng viên trong bức ảnh trƣớc, sau đó sẽ áp
dụng các luật để xác định ứng viên nào là khuôn mặt, ứng viên nào không phải là
khuôn mặt. Quá trình này có thể đƣợc áp dụng nhiều lần để giảm sai sót. Các luật đƣợc


14

xây dựng dựa vào tri thức của ngƣời nghiên cứu về các đặc trƣng của khuôn mặt (ví
dụ nhƣ cƣờng độ phân phối, sự khác nhau) của vùng trên khuôn mặt
Yang và Huang đã sử dụng hƣớng tiếp cận dựa trên tri thức để xác định khuôn

Dựa trên thực tế, chúng ta cố gắng tìm ra những đặc điểm không thay đổi khi của
khuôn mặt khi ở các tƣ thế khác nhau và các điều kiện môi trƣờng nhƣ ánh sáng khác
nhau. Đã có rất nhiều nghiên cứu về hƣớng tiếp cận này, các đặc điểm không thay đổi
đƣợc tìm thấy nhƣ lông mày, mắt, mũi, miệng hay các đƣờng viền trên tóc … Trên cơ
sở các đặc trƣng này, các nhà nghiên cứu xây dựng lên một mô hình thống kê mô tả
quan hệ của các đặc trƣng và từ đó xác định sự xuất hiện của khuôn mặt trong bức ảnh.
Khó khăn của hƣớng tiếp cận này đó là phải mô tả các đặc trƣng không thay đổi và
quan hệ giữa chúng phù hợp với điều kiện ánh sáng, độ nhiễu hay bị che khuất.


15

Có rất nhiều nghiên cứu về các đặc trƣng của khuôn mặt. Có thể dựa vào các đặc
trƣng nhƣ hai mắt, hai lỗ mũi, miệng, phần nối giữa mũi và miệng … hoặc dựa vào
đƣờng viền của khuôn mặt.
Leung đã đƣa ra một mô hình xác xuất để xác định khuôn mặt trong ảnh có hình
nền phức tạp dựa trên việc tìm kiếm các đặc trƣng không thay đổi của khuôn mặt trong
ảnh, sau đó dùng đồ thị ngẫu nhiên để xác định khuôn mặt. Tƣ tƣởng của phƣơng pháp
này đó là xem bài toán xác định khuôn mặt nhƣ là bài toán tìm kiếm với mục tiêu là
tìm thứ tự các đặc trƣng không thay đổi của khuôn mặt. Dùng năm đặc trƣng (hai mắt,
hai lỗ mũi, phần nối giữa mũi và miệng) để mô tả một khuôn mặt. Đồng thời tính quan
hệ khoảng cách cho tất cả các cặp đặc trƣng (nhƣ mắt trái, mắt phải), sau đấy dùng
phân bố Gauss để mô hình hóa. Một mẫu khuôn mặt đƣợc đƣa ra thông qua trung bình
tƣơng ứng cho một tập đa hƣớng, đa tỷ lệ của bộ lọc đạo hàm Gauss. Từ một ảnh, các
đặc trƣng của ứng viên đƣợc xác định bằng cách so khớp từng điểm ảnh khi lọc tƣơng
ứng với vector mẫu. Hai ứng viên có đặc trƣng đứng đầu sẽ đƣợc chọn để tìm kiếm
cho các đặc trƣng khác của khuôn mặt. Từ các đặc trƣng không thay đổi, các đặc trƣng
khác sẽ đƣợc xác định thông qua sự đánh giá xác xuất khoảng cách giữa các đặc trƣng,
hơn nữa phƣơng sai của phép thống kê này có thể đƣợc tính toán trƣớc để xác định các
đặc trƣng với xác xuất lớn.

Trong hƣớng tiếp cận dựa trên so sánh khớp mẫu, các mẫu chuẩn của khuôn mặt
(thƣờng là khuôn mặt đƣợc chụp thẳng) sẽ đƣợc xác định trƣớc hoặc đƣợc biểu diễn
thành một hàm với các tham số cụ thể. Từ một ảnh đƣa vào, tính các giá trị tƣơng quan
so với các mẫu chuẩn về đƣờng viền khuôn mặt, mắt, mũi và miệng. Thông qua các
giá trị tƣơng quan này mà hệ thống sẽ quyết định có hay không có tồn tại khuôn mặt
trong ảnh. Hƣớng tiếp cận này có lợi thế là rất dễ cài đặt, nhƣng không hiệu quả khi tỷ
lệ, tƣ thế, và hình dáng thay đổi.
Sakai đã cố gắng thử xác định khuôn mặt ngƣời chụp thẳng trong ảnh [9]. Ông
dùng vài mẫu con ( sub template ) về mắt, mũi, miệng, và đƣờng viền khuôn mặt để
mô hình hóa một khuôn mặt. Mỗi mẫu con đƣợc định nghĩa trong giới hạn của các
đoạn thẳng. Các đƣờng thẳng trong ảnh đƣợc trích bằng cách xem xét thay đổi của hệ
số góc và so khớp các mẫu con. Đầu tiên tìm các ứng viên thông qua mối tƣơng quan
giữa các ảnh con và các mẫu về đƣờng viền. Sau đó, so khớp với các mẫu con khác.
Hay nói một cách khác, giai đoạn đầu xem nhƣ là giai đoạn sơ chế để tìm ứng viên,
giai đọan thứ hai là giai đoạn tinh chế để xác định ứng viên có phải là khuôn mặt hay
không. Ý tƣởng này đƣợc duy trì cho đến các nghiên cứu sau này.
Craw đƣa ra một phƣơng pháp xác định khuôn mặt ngƣời dựa vào các mẫu về
hình dáng của các ảnh đƣợc chụp thẳng (dùng vẻ bề ngoài của hình dáng khuôn mặt).
Đầu tiên dùng phép lọc Sobel (Phép lọc Sobel dựa vào tích vô hƣớng của hai vector
gradient) để tìm các cạnh. Các cạnh này sẽ đƣợc nhóm lại theo một số ràng buộc. Sau
đó, tìm đƣờng viền của đầu, quá trình tƣơng tự đƣợc lặp đi lặp lại với mỗi tỷ lệ khác
nhau để xác định các đặc trƣng khác nhƣ: mắt, lông mày, và môi. Sau đó Craw mô tả
một phƣơng thức xác định dùng một tập có 40 mẫu để tìm các đặc trƣng khuôn mặt
và điều khiển chiến lƣợc dò tìm.
Một số nhà nghiên cứu sử dụng hình chiếu nhƣ các mẫu để xác định khuôn mặt
ngƣời. Silhouettes dùng Principal Component Analysis [10] (phân tích thành phần
chính – Principal Component Analysis - PCA) để có một tập hình chiếu cơ bản từ các
mẫu khuôn mặt, hình chiếu đƣợc mô tả nhƣ một mảng các bit. Dùng đặc trƣng hình
chiếu riêng kết hợp biến đổi Hough để xác định khuôn mặt ngƣời. Sau đó một phƣơng
pháp xác định dựa trên đa loại mẫu để xác định các thành phần của khuôn mặt đƣợc

đó có thể sử dụng mặt phẳng phân loại để phân loại các mẫu là khuôn mặt hay không
phải là khuôn mặt.
1.4 Kết luận chƣơng 1
Trong chƣơng này, tác giả đã phát biểu và đặt vấn đề cho bài toán. Bên cạnh đó,
tác giả cũng phân tích: những ƣu, nhƣợc điểm, các khó khăn thách thức của lớp bài
toán đã đặt ra trong luận văn. Để giải quyết yêu cầu đặt ra của luận văn, tác giả đi sâu
nghiên cứu và giải quyết hai vấn đề chính: Vấn đề thứ nhất, giới thiệu trình tự các
bƣớc giải quyết cho lớp bài toán. Vấn đề thứ hai, nghiên cứu và xây dựng ứng dụng
hệ thống xác định khuôn mặt chung nhất trong một tập ảnh cho trƣớc.


18

CHƢƠNG 2: CƠ SỞ LÝ THUYẾT
Trong chƣơng này tác giả sẽ trình bày tổng quan lý thuyết để giải quyết bài toán
bao gồm lý thuyết thuật toán, phƣơng pháp của các giai đoạn nhƣ phát hiện khuôn mặt,
trích rút đặc trƣng, và xác định khuôn mặt chung nhất trong tập ảnh cho trƣớc.
2.1 Phát hiện khuôn mặt
2.1.1 Các đặc trƣng giống Haar
Viola và Jones dùng 4 đặc trƣng cơ bản [18] để xác định khuôn mặt ngƣời. Mỗi
đặc trƣng Haar–like là sự kết hợp của hai hay ba hình chữ nhật "trắng" hay "đen" nhƣ
trong hình sau:

Hình 2.1: Bốn đặc trưng Haar-like cơ bản
Để áp dụng các đặc trƣng này vào việc bài toán xác định mặt ngƣời, 4 đặc trƣng
Haar-like cơ bản đƣợc mở rộng ra, và đƣợc chia làm 3 tập đặc trƣng nhƣ sau:
1

Đặc trưng cạnh (edge features):


P(x,y)

(2.2)
Hình 2.3: Cách tính Integral Image của ảnh
Sau khi đã tính đƣợc Integral Image, việc tính tổng điểm ảnh của một vùng bất
kỳ nào đó trên ảnh thực hiện rất đơn giản theo cách sau: (Giả sử ta cần tính tổng điểm
ảnh của vùng D nhƣ trong hình 2.4:
D = A + B + C + D – (A+B) – (A+C) + A
Với A + B + C + D chính là giá trị tại điểm P4 trên Integral Image, tƣơng tự nhƣ
vậy A+B là giá trị tại điểm P2, A+C là giá trị tại điểm P3, và A là giá trị tại điểm P1.
Vậy ta có thể viết lại biểu thức tính D ở trên nhƣ sau:
(2.3)
A

P1

C

B

P2

D
P3

P4

Hình 2.4: Cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh



Nhƣ đã biết, AdaBoost [18] ( Adaptive Boost ) là một bộ phân loại mạnh phi
tuyến phức dựa trên hƣớng tiếp cận boosting đƣợc Freund và Schapire đƣa ra vào năm
1995. Adaboost hoạt động trên nguyên tắc kết hợp tuyến tính các weak classifier dựa
trên các đặc trƣng Haar- Line để hình thành một strong classifier.
Để có thể kết hợp các bộ phân loại yếu, adaboost sử dụng một trọng số (weight)
để đánh dấu các mẫu khó nhận dạng. Trong quá trình huấn luyện, cứ mỗi weak
classifier đƣợc xây dựng, thuật toán sẽ tiến hành cập nhật lại trọng số để chuẩn bị cho
việc xây dựng weak classifier tiếp theo: tăng trọng số của các mẫu bị nhận dạng sai và
giảm trọng số của các mẫu đƣợc nhận dạng đúng bởi weak classifier vừa xây dựng.
Bằng cách này, các weak classifier sau có thể tập trung vào các mẫu mà các weak
classifier trƣớc đó chƣa thực hiện tốt. Sau cùng các weak classifier sẽ đƣợc kết hợp tùy
theo mức độ „tốt‟ của chúng để tạo nên một strong classifier.
Các weak classifiers hk(x) là các bộ phân loại yếu, đƣợc biểu diễn nhƣ sau:
(2.5)


21

Trong đó:
X : mẫu hay cửa sổ con cần xét ( X = (x1,x2,…,xn) là vector đặc trƣng của mẫu)
Ok: ngƣỡng (O = teta)
fk: giá trị của đặc trƣng Haar-like
pk: hệ số quyết định chiều của bất phƣơng trình
Công thức trên có thể diễn giải nhƣ sau: Nếu giá trị đặc trƣng của mẫu cho bởi
hàm đánh giá của bộ phân loại vƣợt qua một ngƣỡng cho trƣớc thì mẫu đấy là khuôn
mặt ( gọi là object : đối tƣợng cần nhận dạng ), ngƣợc lại thì mẫu là background (
không phải là đối tƣợng ).
Thuật toán AdaBoost:
1. Cho một tập gồm n mẫu có đánh dấu (x1,y1), (x2,y2),… (xn,yn) với xk ∈
(xk1, xk2, … , xkm) là vector đặc trƣng và yk ∈ (-1, 1) là nhãn của mẫu (1

Hệ số αt nói lên mức độ quan trọng của ht:
 Trong công thức của bộ phân loại H(x):
(2.6)
Ta thấy tất cả các bộ phân loại ht đều có đóng góp vào kết quả của bộ
phân loại H(x), và mức độ đóng góp của chúng phụ thuộc vào giá trị αt tƣơng
ứng: ht với αt càng lớn thì nó càng có vài trò quan trọng trong H(x).
 Trong công thức tính αt:
(2.7)
Dễ thấy giá trị αt tỉ lệ nghịch với εt. Bởi vì ht đƣợc chọn với tiêu chí đạt εt
nhỏ nhất, do đó nó sẽ đảm bảo giá trị αt lớn nhất.
Sau khi tính đƣợc giá trị αt, Adaboost tiến hành cập nhật lại trọng số của các
mẫu: tăng trọng số các mẫu mà ht phân loại sai, giảm trọng số các mẫu mà ht phân loại
đúng. Bằng cách này, trọng số của mẫu phản ánh đƣợc mức độ khó nhận dạng của
mẫu đó và ht+1 sẽ ƣu tiên học cách phân loại những mẫu này.
Vòng lặp xây dựng strong classifier sẽ dừng lại sau T lần lặp. Trong thực tế cài
đặt (thƣ viện OpenCV của Intel), ngƣời ta ít sử dụng giá trị T vì không có công thức
nào đảm bảo tính đƣợc giá trị T tối ƣu cho quá trình huấn luyện. Thay vào đó, ngƣời ta
sử dụng giá trị max false positive hay max false alarm (tỉ lệ nhận dạng sai tối đa các
mẫu background). Tỉ lệ này của bộ phân loại cần xây dựng không đƣợc phép vƣợt quá
giá trị này. Khi đó, qua các lần lặp, false alarm của strong classifier Ht(x) xây dựng
đƣợc (tại lần lặp thứ t) sẽ giảm dần, và vòng lặp kết thúc khi tỉ lệ này thấp hơn max
false alarm.
2.2 Tổng quan về các phƣơng pháp trích rút đặc trƣng
Hiện nay có rất nhiều các phƣơng pháp trích dẫn dữ liệu từ khuôn mặt, mỗi
phƣơng pháp có những ƣu nhƣợc điểm và đặc điểm riêng nhƣng theo cách
thức mà những phƣơng pháp và hình thức của dữ liệu đƣợc trích dẫn thì chia ra làm 2
hƣớng tiếp cận chính:
Thứ nhất, hƣớng tiếp cận dựa trên đặc trƣng hình học là hƣớng tiếp cận dựa vào
các bức ảnh trực diện khuôn mặt lấy từ khâu phát hiện khuôn mặt, trích chọn đặc trƣng


Một dạng khác của trích chọn đặc trƣng là trích trọn đặc trƣng diện mạo để xác
định những thay đổi trên khuôn mặt. Đặc trƣng về diện mạo biểu diễn sự thay đổi
vẻ bề ngoài: kết cấu da nhƣ các nếp nhăn trên khuôn mặt; biểu đồ nhiệt của khuôn mặt:
các mẫu nhiệt khuôn mặt là duy nhất với mỗi ngƣời và đặc trƣng về nụ cƣời.
Các đặc trƣng về diện mạo có thể đƣợc trích rút trên cả khuôn mặt hoặc phần
nào đó trên khuôn mặt. Một số phƣơng pháp tiểu biểu nhƣ : Principal component
analysis (PCA) [10,14], Gabor Wavelet Analysis [19] và Local Binary Pattern
[15, 16] và đƣợc áp dụng trên toàn bộ bề mặt bức ảnh hoặc một phần để trích ra các
đặc trƣng và phát hiện sự thay đổi của khuôn mặt.


24

2.3 Phƣơng pháp phân tích thành phần chính
2.3.1 Sơ lƣợc đại số tuyến tính
 Vector riêng, trị riêng và sự chéo hóa của ma trận
Cho A là một ma trận vuông cấp n trên trƣờng K. Một số   K đƣợc gọi là giá
trị riêng của ma trận A nếu tồn tại vectơ u khác không u  K n , sao cho thỏa mãn điều
kiện A(u)  u . Khi đó vectơ u đƣợc gọi là vectơ riêng của ma trận A ứng với giá trị
riêng  . Ma trận A với kích thƣớc n x n sẽ có tối đa n trị riêng và n vector riêng tƣơng
ứng.
2

3

1

1 

Ví dụ cho ma trận A  

chiều.
X = [x1, x2,…, xn]T

(2.8)

Khi đó kỳ vọng của biến ngẫu nhiên X cũng là một vector n chiều,
trong thống kê, kỳ vọng E[X] của biến ngẫu nhiên X có thể ƣớc lƣợng bằng trung
bình mẫu , và đƣợc tính bằng công thức:
(2.9)
Trong đó: M là tổng số mẫu có trong thống kê.
 Ma trận hiệp phƣơng sai

Trích đoạn Xác định khuôn mặt chung nhất Kết luận chƣơng 3 Một số thực nghiệm Kết luận chƣơng 4

---