ỦY BAN NHÂN DÂN TP.HCM
SỞ KHOA HỌC VÀ CÔNG NGHỆ

BÁO CÁO NGHIỆM THU

PHÁT TRIỂN MỘT SỐ HÌNH TÍNH TỐN MỀM CHO BÀI TỐN
TRUY TÌM ẢNH MẶT NGƯỜI NHÌN THẲNG

CHỦ NHIỆM ĐỀ TÀI

Lê Hồng Thái
CƠ QUAN QUẢN LÝ

CƠ QUAN CHỦ TRÌ

THÀNH PHỐ HỒ CHÍ MINH
THÁNG 06 / 2010


TĨM TẮT NỘI DUNG NGHIÊN CỨU

1. Tìm hiểu, nghiên cứu các kỹ thuật tính tốn thơng minh (NN, FL, GA,
SVM,…) và các ứng dụng của nó.
2. So sánh các kỹ thuật thông minh: nêu ưu khuyết điểm từng kỹ thuật, lớp bài
tốn mà kỹ thuật đó có thể giải quyết, sự thể hiện của từng kỹ thuật như thế
nào trong từng lớp bài tốn.
3. Tìm hiểu về các nghiên cứu đã có về bài tốn nhận dạng mặt người nhìn
thẳng: mơ hình thực hiện qua các bước, các kỹ thuật đã nghiên cứu và áp
dụng.
4. Phát triển các kỹ thuật tính tốn thơng minh ứng dụng cho từng khâu trong
mơ hình nhận dạng mặt người nhìn thẳng để có được những giải pháp tốt

hơn cho từng khâu trong mơ hình. Trong từng kỹ thuật đề xuất, đều có so
sánh đánh giá với các kỹ thuật hiện có để chỉ ra tính ưu việt của kỹ thuật đề
xuất. Kỹ thuật đề xuất ở đây có thể sử dụng một, nhiều hay phối hợp các kỹ
thuật thơng minh để có hiệu ứng tốt nhất.
5. Xây dựng mơ hình thơng minh tổng qt cho bài tốn nhận dạng mặt người
nhìn thẳng.
6. Cài đặt một chương trình ứng dụng thể hiện mơ hình thơng minh giải quyết
bài tốn nhận dạng mặt người nhìn thẳng.
7. So sánh đối chiếu với các mơ hình, ứng dụng đã có thơng qua thực nghiệm
để chứng minh tính ưu việt của mơ hình đề xuất.


SUMMARY OF RESEARCH CONTENT

1. Surveying, studying techniques of clever computing (NN, FL, GA, SVM,…)
and its Applications.
2. Compare some intelligent techniques: present advantage and disadvantage of
each technique, the class of problem which the techniques can solve, the
performance of each technique in each problem.
3. Surveying the current research approach about frontal face recognition
problem: model of processing steps, some techniques, some available
techniques and applications.
4. Developing the techniques of intelligent computing in applying for each
processing stage in model of frontal face recognition in order to get better
solution for each stage in the model. In each proposal technique, there is
comparison and evaluation these techniques with available other techniques
in order to point out the advantage of the proposal method. The proposal
method can use one or many or combination of some intelligent technique in
order to have the good performance.
5. Constructing the general intelligent model for frontal face recognition.


6. Implementing the application which demonstrates the intelligent model in
solving the frontal face recognition problem.
7. Comparing with the available models and applications by experimental
results in order to demonstrate the feasibility of the proposal model.


MỤC LỤC

DANH MỤC BẢNG ............................................................................. 1
DANH MỤC HÌNH .............................................................................. 2
PHẦN MỞ ĐẦU ................................................................................... 7
CHƢƠNG 1: TÌM HIỂU VỀ CÁC KỸ THUẬT TÍNH TỐN MỀM
...................................................................................... 9
1.1

Các kỹ thuật tính tốn mềm ứng dụng trong đề tài .................................... 9

1.2

Các kỹ thuật trích chọn không gian biểu diễn mẫu .................................... 9

1.2.1

Phương pháp phân tích thành phần chính : ......................................... 9

1.2.2

Phương pháp phân tích thành phần độc lập: ..................................... 11


1.2.3

Phân tích tách lớp tuyến tính:........................................................... 16

1.3

Các kỹ thuật phân lớp mẫu phổ cập ........................................................ 19

1.3.1

Phương pháp AdaBoost ................................................................... 19

1.3.2

Cơ sở lý thuyết mạng nơron ............................................................. 28

1.3.3

Support Vector Machine (SVM) ...................................................... 33

1.4

Các kỹ thuật tính toán gần đúng hỗ trợ cho bài toán nhận dạng ............... 43

1.4.1

Tìm hiểu các kiến thức về GA ......................................................... 43

1.4.2


Lý thuyết về tập mờ ......................................................................... 46

1.5

Ví dụ về mơ hình lai hai kỹ thuật tính tốn mềm ..................................... 63

1.5.1

Mơ hình lai GA-FL cho điều khiển trực thăng không người lái ........ 63

1.5.2

Tóm tắt mục 1.5............................................................................... 64

1.6

Kết luận chương 1................................................................................... 64

CHƢƠNG 2: TỔNG QUAN VỀ BÀI TỐN TRUY TÌM ẢNH MẶT
NGƢỜI
2.1

................................................................................... 66

Khảo sát chung và giới hạn phạm vi nghiên cứu ..................................... 66

2.1.1

Tổng quan tình hình nghiên cứu về truy tìm ảnh mặt người tự động 66


2.1.2

Tính cấp thiết của việc giải quyết bài toán ....................................... 76

2.1.3

Phạm vi nghiên cứu ......................................................................... 78


2.2

Khảo sát các nghiên cứu đã có cho từng giai đoạn của bài tốn truy tìm ảnh mặt

người nhìn thẳng ............................................................................................... 79
2.2.1

Các bước giải quyết bài tốn truy tìm ảnh mặt người ....................... 79

2.2.2

Dị tìm và Phát hiện ảnh khn mặt ................................................. 79

2.2.3

Chuẩn hóa khn mặt ...................................................................... 88

2.2.4

Rút trích và so khớp không gian biểu diễn ảnh khuôn mặt ............. 100


2.3

Kết luận chương 2................................................................................. 104

CHƢƠNG 3:

DÕ TÌM VÀ PHÁT HIỆN MẶT NGƢỜI BẰNG

ADABOOST KẾT HỢP MẠNG NƠRON NHÂN TẠO ................ 105
3.1

Đề xuất phương pháp xác định phạm vi nghiên cứu .............................. 105

3.2

Bài tốn phân lớp mẫu (Pattern Classification) trong dị tìm mặt .......... 105

3.3

Mơ hình phân lớp Cascade of Boosted Classifiers................................. 107

3.4

Mơ hình phân lớp Artificial Neural Network ........................................ 110

3.5

Mơ hình phân lớp kết hợp Cascade of Boosted Classifiers + Artificial Neural

Network .......................................................................................................... 111

3.6

Phương thức dị tìm sử dụng cửa sổ tìm kiếm ....................................... 113

3.7

Dữ liệu thực nghiệm ............................................................................. 116

3.7.1

Dữ liệu huấn luyện: ....................................................................... 116

3.7.2

Dữ liệu thử nghiệm ........................................................................ 116

3.8

Kết quả và đánh giá .............................................................................. 117

3.9

Nhận xét mơ hình đề xuất ..................................................................... 118

3.10

Kết luận chương 3................................................................................. 118

CHƢƠNG 4:


CHUẨN

HÓA

MẶT

NGƢỜI

BẰNG

MẠNG

PERCEPTRON ĐA LỚP ................................................................. 120
4.1

Giới thiệu.............................................................................................. 120

4.2

Thuật giải ASM tổng quát ..................................................................... 122

4.2.1

Mô hình dáng điệu thống kê .......................................................... 122

4.2.2

Thuật giải ASM ............................................................................. 124

4.3


Mơ hình lấy vân ảnh cục bộ cổ điển ...................................................... 125

4.4

Mạng Perceptron đa lớp cho phân loại vân ảnh địa phương .................. 127


4.4.1

Cấu trúc mạng Perceptron đa lớp [90][95] ..................................... 127

4.4.2

Áp dụng mạng Perceptron đa lớp cho tìm kiếm các điểm đặc trưng 128

4.5

Các kết quả thử nghiệm ........................................................................ 130

4.5.1

Độ chính xác ................................................................................. 130

4.5.2

Thời gian thực hiện ........................................................................ 131

4.6


Kết luận chương 4................................................................................. 132

CHƢƠNG 5: RƯT TRÍCH VÀ SO KHỚP KHƠNG GIAN BIỂU DIỄN
ẢNH KHN MẶT......................................................................... 133
5.1

Trích chọn đặc trưng ảnh mặt người bằng phương pháp hình học kết hợp phân

tích thành phần độc lập .................................................................................... 133
5.1.1

Khảo sát và đề xuất........................................................................ 133

5.1.2

Sự kết hợp đặc trưng của các thành phần quan trọng của khn mặt134

5.1.3

Phương pháp phân tích thành phần độc lập trong rút trích đặc trưng mặt

người

...................................................................................................... 136

5.1.4

Sự kết hợp của phương pháp dựa trên đặc trưng hình học và ICA .. 139

5.1.5


Kết quả thực nghiệm và thảo luận .................................................. 139

5.1.6

Kết luận ......................................................................................... 143

5.2

Kết hợp phân tích thành phần độc lập (ICA) và phân tích tách lớp tuyến tính

(LDA) cho nhận dạng mặt người ..................................................................... 144
5.2.1

Phân tích đánh giá các phương pháp trích chọn đặc trưng ảnh khn mặt
...................................................................................................... 144

5.2.2

Phân tích đánh giá, đề xuất mơ hình ICA+LDA cho rút trích và so khớp

không gian biểu diễn ảnh khuôn mặt ............................................................ 148
5.2.3
5.3

Kết luận: ........................................................................................ 154

Kết luận chương 5................................................................................. 154

CHƢƠNG 6: XÂY DỰNG MƠ HÌNH TỔNG QT CHO TRUY TÌM

ẢNH MẶT NGƢỜI NHÌN THẲNG TRÊN ỨNG DỤNG THỰC TẾ156
6.1

Mơ hình truy tìm ảnh mặt người nhìn thẳng 1 cho CSDL trường ĐHKHTN tp.

HCM ............................................................................................................. 156
6.1.1

Xây dựng cơ sở dữ liệu cho ứng dụng:........................................... 156


6.1.2

Mơ hình nhận dạng trong ứng dụng thử nghiệm............................. 157

6.1.3

Sử dụng ICA và LDA rút trích đặc trưng cho khn mặt ............... 158

6.1.4

Sử dụng mơ hình kết hợp cho q trình nhận dạng: ....................... 158

6.1.5

Báo cáo kết quả: ............................................................................ 159

6.1.6

Phân tích đề xuất mơ hình.............................................................. 160


6.1.7

Đánh giá và kết luận ...................................................................... 160

6.2

Mơ hình truy tìm ảnh mặt người nhìn thẳng 2 cho CSDL ảnh hộ chiếu cục quản

lý xuất nhập cảnh Q1 tp. HCM ........................................................................ 161
6.2.1

Giới thiệu bài toán ......................................................................... 161

6.2.2

Cơ sở dữ liệu thử nghiệm............................................................... 162

6.2.3

Đề xuất mơ hình truy tìm ảnh nhìn thẳng, khơng quay ................... 164

6.2.4

Rút trích khơng gian đặc trưng trên sáu vùng phân chia hình học của ảnh

mặt người..................................................................................................... 165
6.2.5

Các phương pháp tổng hợp kết quả so khớp................................... 171


6.2.6

Xác định bộ hệ số tin cậy cho sáu vùng đặc trưng đã rút trích bằng Thuật

giải di truyền ................................................................................................ 175
6.2.7

Tổng hợp kết quả thực nghiệm ...................................................... 182

6.2.8

Đánh giá và kết luận về mơ hình đề xuất ....................................... 184

6.3

Kết luận chương 6................................................................................. 186

CHƢƠNG 7:

ỨNG DỤNG THỰC NGHIỆM TẠI CỤC QUẢN LÝ

XUẤT NHẬP CẢNH........................................................................ 187
7.1

Nhu cầu ứng dụng của Cục Quản lý xuất nhập cảnh Q1 tp. HCM ......... 187

7.2

Bài toán đề nghị tương ứng ................................................................... 189


7.3

Giao diện chương trình ......................................................................... 190

7.4

Phương pháp đề xuất ............................................................................ 191

7.5

Các kết quả thực nghiệm....................................................................... 194

7.6

Phân tích đánh giá kết quả thực nghiệm ................................................ 195

7.7

Lời cảm ơn ........................................................................................... 196

7.8

Kết luận chương 7................................................................................. 196

KẾT LUẬN ....................................................................................... 197


PHỤ LỤC.......................................................................................... 200
TÀI LIỆU THAM KHẢO................................................................ 205



DANH MỤC BẢNG
SỐ

TÊN BẢNG SỐ LIỆU

TRANG

Bảng 1-1 Thuật toán AdaBoost ............................................................................. 22
Bảng 1-3 Bảng trị chân lý các phép toán ............................................................... 50
Bảng 1-4 Quan hệ giữa T và S .............................................................................. 52
Bảng 3-1 Kết quả thực nghiệm dị tìm khn mặt ............................................... 117
Bảng 4-1 Thời gian thực hiện trung bình trên một lần lặp (xử lý hai giai đoạn) .. 132
Bảng 5-1 Phần trăm tỉ lệ nhận dạng chính xác trên CSDL CalTech. ................... 141
Bảng 5-2 Phần trăm tỉ lệ nhận dạng chính xác trên CSDL tự tạo. ........................ 142
Bảng 5-3 So sánh kết quả giữa PCA, ICA và LDA. ............................................ 147
Bảng 5-4 Kết quả thống kê theo độ đo Euclidean ............................................... 152
Bảng 5-5 Kết quả thống kê theo độ đo Mahattan ................................................ 153
Bảng 5-6 Kết quả thống kê theo độ đo Cosin ...................................................... 153
Bảng 5-7 Kết quả thống kê theo các độ đo .......................................................... 153
Bảng 5-8 Kết quả thống kê theo các phương pháp kết hợp.................................. 153
Bảng 6-1 Kết quả nhận dạng............................................................................... 159
Bảng 6-2 Bảng công thức xác định các vùng hình học ........................................ 166
Bảng 6-3 Khoảng cách từ ảnh test đến các lớp 2, 3, 4 ......................................... 174
Bảng 6-4 Mức độ tin cậy của các vùng thuộc các lớp 2,3,4 ................................. 175
Bảng 6-5 Kết quả thống kê theo độ đo Euclide ................................................... 183
Bảng 6-6 Kết quả thống kê theo độ đo Mahattan ................................................ 183
Bảng 6-7 Kết quả thống kê theo độ đo Cosin ...................................................... 183
Bảng 6-8 Kết quả thống kê theo các độ đo .......................................................... 184

Bảng 6-9 Kết quả thống kê theo các phương pháp kết hợp.................................. 184
Bảng 7-1 Tỷ lệ so khớp ảnh trên ba bộ cơ sở dữ liệu (200 ảnh, 700 ảnh và 1800
ảnh) ..................................................................................................................... 194
Bảng 7-2 Kết quả truy tìm trên ba bộ cơ sở dữ liệu (200, 700 và 1800 ảnh) ........ 195

-1-


DANH MỤC HÌNH
SỐ

TÊN HÌNH ẢNH

TRANG

Hình 1-1 Hướng của vector riêng ......................................................................... 10
Hình 1-2 Sự phân phối dữ liệu, và các trục tương ứng của PCA & ICA ................ 12
Hình 1-3 Vector đặc trưng cho mỗi kĩ thuật. ......................................................... 13
Hình 1-4 Minh họa kiến trúc 1 trong mơ hình ICA ............................................... 14
Hình 1-5 Minh họa kiến trúc 2 trong mơ hình ICA ............................................... 14
Hình 1-6 Mơ hình tổng hợp ảnh cho kiến trúc 2 của ICA ...................................... 15
Hình 1-7 Mơ hình tổng hợp ảnh cho kiến trúc 2 của ICA trên pixel ...................... 15
Hình 1-8 Khơng gian con của LDA ...................................................................... 16
Hình 1-9 Minh họa trường hợp phân biệt 2 lớp ..................................................... 17
Hình 1-10 Minh họa trường hợp phân biệt 2 lớp ................................................... 17
Hình 1-11 Minh họa khái niệm ―bên trong‖ (within) và ―bên cạnh‖ (between) ..... 18
Hình 1-12 Strong classifier H(x) được xây dựng bằng AdaBoost ......................... 20
Hình 1-13 Ví dụ minh hoạ sự kết hợp của 3 phân lớp tuyến tính........................... 22
Hình 1-14 Các đặc trưng Haar-like cơ sở .............................................................. 24
Hình 1-15 Các miền hình học đặc trưng Haar – like ............................................. 24

Hình 1-16 Ý nghĩa hình học của đạo hàm ảnh ...................................................... 25
Hình 1-17 Cách tính giá trị một ơ đặc trưng .......................................................... 25
Hình 1-18 Dị tìm bàn tay bằng đặc trưng Haar – like ........................................... 25
Hình 1-19 Dị tìm khn mặt bằng đặc trưng haar – like....................................... 26
Hình 1-20 Cascade Classifier................................................................................. 27
Hình 1-21 Sơ đồ Cascade of Boosted Classifiers ................................................... 27
Hình 1-22 Mơ hình một Nơron thần kinh............................................................... 28
Hình 1-23 Mơ hình Nơron nhân tạo ....................................................................... 28
Hình 1-24 Mơ hình tốn học tổng qt của một Nơron .......................................... 29
Hình 1-25 Các xử lý tương đương trong một Nơron ............................................. 30
Hình 1-26 Hoạt động tính tốn của Nơron ............................................................. 32
Hình 1-27 Các loại liên kết của Nơron .................................................................. 33
-2-


Hình 1-28 Minh hoạ khoảng cách từ x đến mặt phẳng .......................................... 34
Hình 1-29 Siêu mặt phân cách .............................................................................. 35
Hình 1-30 Véc tơ hỗ trợ là những điểm có màu đen và đỏ .................................... 35
Hình 1-31 (a) Siêu mặt phân cách với khoảng cách 2 bờ nhỏ. (b) Siêu mặt phân
cách với khoảng cách 2 bờ lớn hơn trường hợp (a). ............................................... 36
Hình 1-32 Minh họa các phần tử bị lỗi.................................................................. 38
Hình 1-33 Minh họa việc chuyển từ khơng gian đầu vào (Input space) khơng tìm
được siêu mặt phẳng) sang khơng gian đặc trưng (Feature space) và tìm được siêu
mặt phân cách. ....................................................................................................... 41
Hình 1-34 các bước thực hiện của GA .................................................................. 45
Hình 1-35 Ví dụ về tập mờ ................................................................................... 47
Hình 1-36 Hệ thống nhiều đầu vào, một đầu ra ..................................................... 48
Hình 2-1 Qui trình nhận dạng mặt người ............................................................. 68
Hình 2-2 Phân loại các thuật giải nhận dạng khn mặt trên cơ sở : phụ thuộc vào
tư thế, cách biểu diễn khuôn mặt và các đặc trưng được sử dụng cho đối sánh....... 72

Hình 2-3 Cấu trúc của hệ thống nhận dạng mặt người. ......................................... 79
Hình 2-4 Minh họa tập ảnh face và non-face ........................................................ 81
Hình 2-5 Kết quả dị tìm khn mặt ...................................................................... 82
Hình 2-6 Minh họa hit, false-alarm và miss ....................................................... 87
Hình 2-7 Minh họa về đánh nhãn điểm trong ảnh khn mặt ................................ 88
Hình 2-8 Véc tơ tương ứng của tập các điểm biểu diễn hình dáng ........................ 89
Hình 2-9 Mơ hình các điểm khớp với ảnh ............................................................ 91
Hình 2-10 Minh họa khớp mơ hình (bên trái) vào ảnh mới (bên phải)................... 92
Hình 2-11 Minh họa quá trình làm khớp ............................................................... 92
Hình 2-12 Tìm cạnh sắc nhất ................................................................................ 93
Hình 2-13 Cạnh sắc nhất khơng phải là biên cần tìm ............................................ 94
Hình 2-14 Mơ hình thống kê profile ..................................................................... 94
Hình 2-15 Khám phá sự tương quan ..................................................................... 96
Hình 2-16 Mơ hình diện mạo tích cực (AAM) ...................................................... 97

-3-


Hình 2-17 Đánh giá độ khớp................................................................................. 98
Hình 2-18 Quá trình lặp ........................................................................................ 99
Hình 3-1 Minh họa khơng gian đặc trưng khn mặt .......................................... 106
Hình 3-2 Minh họa tập mẫu huấn luyện trong khơng gian .................................. 106
Hình 3-3 Sơ đồ Cascade of Boosted Classifiers .................................................. 107
Hình 3-4 Minh họa cho một bộ phân lớp mạnh H sử dụng 3 đặc trưng ............... 108
Hình 3-5 Minh họa mặt phẳng cắt trong khơng gian ........................................... 109
Hình 3-6 Minh họa bộ phân kết hợp nhiều mặt phẳng cắt ................................... 109
Hình 3-7: Sơ đồ bộ phân lớp ANN .................................................................... 110
Hình 3-8 Minh họa bộ phân lớp ANN với số nút ẩn ít và nhiều .......................... 110
Hình 3-9 Chi phí các bộ phân lớp của CBC trong q trình dị tìm ..................... 112
Hình 3-10 Minh họa kết hợp CBC + ANN.......................................................... 112

Hình 3-11 Sơ đồ kết hợp CBC + ANN ............................................................... 113
Hình 3-12 Phương pháp dị tìm khn mặt trên ảnh của Rowley ........................ 114
Hình 3-13 Minh họa trường hợp kết quả chồng lấp và khử chồng lấp ................. 115
Hình 3-14 Ảnh minh họa cho tập CALTECH ..................................................... 116
Hình 3-15 Minh họa tập ảnh trong nước. ............................................................ 116
Hình 4-1 Chuẩn hóa khn mặt. ......................................................................... 120
Hình 4-2 Mơ hình dáng điệu của một ảnh ........................................................... 122
Hình 4-3 Áp dụng PCA tính tốn mơ hình dáng điệu thống kê. .......................... 124
Hình 4-4 Chuyển từ mơ hình đến ảnh. ............................................................... 124
Hình 4-5 Mơ hình lấy vân ảnh 1-D ..................................................................... 126
Hình 4-6 Tính tốn hàm g(k) .............................................................................. 126
Hình 4-7 Chọn các điểm đặc trưng tại các đường biên ........................................ 127
Hình 4-8 Cấu trúc mạng Perceptron đa lớp ......................................................... 128
Hình 4-9 Mạng Perceptron đa lớp cho tìm kiếm các điểm đặc trưng ................... 129
Hình 4-10 So sánh giữa ASM cổ điển và MLP ASM ........................................ 130
Hình 4-11 Các kết quả thử nghiệm trên một vài ảnh từ cơ sở dữ liệu CalTech và
CSDL của chúng tôi. ........................................................................................... 131

-4-


Hình 5-1 Chuẩn hố tồn cục khn mặt ........................................................... 135
Hình 5-2 Trích chọn mắt, miệng từ khn mặt ................................................... 135
Hình 5-3 Sự kết hợp đặc trưng toàn cục và các đặc trưng bộ phận của khn mặt
............................................................................................................................ 136
Hình 5-4 Tìm tập các hệ số biểu diễn cho ảnh là độc lập .................................... 137
Hình 5-5 Hàng đầu chứa 8 mặt riêng ứng với 8 trị riêng đầu tiên trong PCA. Hàng
2 chứa 8 ảnh cơ sở đầu tiên trong kiến trúc 2 ICA. .............................................. 138
Hình 5-6 Rút trích đặc trưng của khn mặt dựa trên đặc trưng hình học kết hợp
với phương pháp ICA .......................................................................................... 139

Hình 5-7 Một vài ảnh mẫu trong CSDL ảnh CalTech ......................................... 140
Hình 5-8 Một vài ảnh mẫu trong CSDL tự tạo của chúng tơi. ............................. 140
Hình 5-9 Rank-curves trên CSDL CalTech. Kết quả báo cáo cho thấy phương pháp
GICA tạo ra một hệ thống nhận dạng tin cậy hơn. ............................................... 142
Hình 5-10 Rank-curves trên CSDL tự tạo. Kết quả báo cáo cho thấy phương pháp
GICA tạo ra một hệ nhận dạng tin cậy hơn. ......................................................... 143
Hình 5-11 Một số ảnh minh họa cho tập dữ liệu ORL ......................................... 145
Hình 5-12 Một số ảnh minh họa cho tập dữ liệu YALE ...................................... 145
Hình 5-13 Một số ảnh minh họa cho tập dữ liệu CALTECH............................... 145
Hình 5-14 Một số ảnh minh họa cho tập ảnh trong nước ..................................... 146
Hình 5-15 Mơ hình kết hợp theo phương pháp tuần tự ........................................ 149
Hình 5-16 Mơ hình thử nghiệm cụ thể kết hợp theo kiểu tuần tự ........................ 150
Hình 5-17 Mơ hình kết hợp kiểu song song tổng quát ......................................... 151
Hình 5-18 Bộ kết hợp kiểu trung bình. ................................................................ 151
Hình 5-19 Mơ hình kết hợp theo phương pháp nối kết. ....................................... 152
Hình 6-1 Một số ảnh train trong ứng dụng .......................................................... 157
Hình 6-2 Một số ảnh test trong ứng dụng ........................................................... 157
Hình 6-3 Mơ hình tổng qt trong ứng dụng thực nghiệm ................................. 158
Hình 6-4 Mơ hình kết hợp theo phương pháp trung bình. ................................... 159
Hình 6-5 Mơ hình ứng dụng thực nghiệm ........................................................... 160

-5-


Hình 6-6 Một vài ảnh mẫu trong cơ sở dữ liệu ảnh CalTech ............................... 162
Hình 6-7 Một vài ảnh mẫu trong cơ sở dữ liệu ảnh tự tạo ................................... 163
Hình 6-8 Một vài ảnh mẫu trong cơ sở dữ liệu ảnh hộ chiếu ............................... 163
Hình 6-9 Kết quả thực hiện ở giai đoạn dị tìm khn mặt .................................. 165
Hình 6-10 Phân chia hình học ảnh mặt người ..................................................... 166
Hình 6-11 Chuẩn hóa ảnh khn mặt .................................................................. 167

Hình 6-12 Sự kết hợp của phương pháp dựa trên đặc trưng hình học và PCA_LDA
............................................................................................................................ 170
Hình 6-13 Mơ hình so khớp vector đặc trưng...................................................... 172
Hình 6-14 Tính giá trị thích nghi cho một chuỗi ................................................. 180
Hình 6-15 Các bước cơ bản của Thuật giải di truyền ......................................... 181
Hình 6-16 Sơ đồ giải thuật của phương pháp đề nghị .......................................... 182
Hình 6-17 Mơ hình ứng dụng thực nghiệm ......................................................... 185
Hình 7-1 Xác thực ảnh đối tượng tại cửa khẩu .................................................... 188
Hình 7-2 Truy tìm ảnh trong CSDL- Tại phịng khai thác thơng tin Cục QLXNC
............................................................................................................................ 188
Hình 7-3 Hai bài tốn đề xuất tương ứng ............................................................ 189
Hình 7-4 Giao diện cho bài tốn xác thực ảnh (Khối mặt người ở giữa chuyển màu
xanh: trường hợp hai ảnh trùng khớp; màu đỏ: trường hợp hai ảnh sai khác). ...... 190
Hình 7-5 Giao diện cho bài tốn truy tìm ảnh (có hai đối tượng gần giống với ảnh
thu nhận – đối tượng 1 có 5 ảnh ứng với 5 lần làm hộ chiếu). .............................. 190
Hình 7-6 Phân chia hình học một ảnh về 6 vùng ................................................ 192
Hình 7-7 Minh họa Phân tích thành phần chính (PCA); Phân tích tách lớp tuyến
tính (LDA). ......................................................................................................... 193
Hình 7-8 Minh họa Mơ hình kết hợp các phương pháp cho nhận dạng ảnh hộ
chiếu.................................................................................................................... 193

-6-


PHẦN MỞ ĐẦU
1. Tên đề tài/dự án: PHÁT TRIỂN MỘT SỐ MƠ HÌNH TÍNH TỐN MỀM
CHO BÀI TỐN TRUY TÌM ẢNH MẶT NGƯỜI NHÌN THẲNG.
Chủ nhiệm đề tài/dự án: Lê Hồng Thái
Cơ quan chủ trì:Trường Đại học Khoa học tự nhiên.
Thời gian thực hiện: 10/2007 – 06/2010

Kinh phí được duyệt: 317.000.000
Kinh phí đã cấp: 200.000.000 theo TB số: TB-SKHCN ngày /
2. Mục tiêu
Trên cơ sở nghiên cứu các kỹ thuật tính tốn mềm đã có, chúng tơi đề xuất một số mơ
hình tính tốn mềm riêng nhằm giải quyết từng giai đoạn của bài tốn truy tìm ảnh mặt
người.nhìn thẳng. Các mơ hình đề xuất được chỉ ra tính ưu việt thơng qua việc so sánh
đánh giá nó với một số phương pháp truyền thống khác.
Mục đích chính của nghiên cứu này nhằm chỉ ra tính hiệu quả của mơ hình tính tốn
mềm trong ứng dụng: truy tìm dữ liệu trong cơ sở dữ liệu thơng qua khóa tìm là ảnh mặt
người nhìn thẳng.
Hơn nữa, vai trị thực tiễn của nghiên cứu cũng được khẳng định thông qua lĩnh vực
thực tế: phần mềm truy tìm ảnh các đối tượng bị truy nã thơng qua khóa tìm là ảnh chụp hộ
chiếu cá nhân. Phần mềm này sẽ được ứng dụng thử nghiệm tại Cục Quản lý xuất nhập
cảnh, 254 Nguyễn Trãi, Q1, tp. Hồ Chí Minh.

3. Nội dung
Đề tài gồm ba giai đoạn chính:
Giai đoạn 1: Tìm hiểu, nghiên cứu các kỹ thuật tính tốn mềm, tìm hiểu thử
nghiệm việc kết hợp các kỹ thuật.
Giai đoạn 2: Khảo sát về bài tốn Truy tìm ảnh mặt người (các bước cần thiết
để giải quyết bài tốn, các nghiên cứu đã có). Tiến tới, đề xuất mơ hình tính tốn
mềm riêng cho từng bước, minh chứng tính khả thi của các mơ hình đề xuất thông
qua các kết quả thử nghiệm. Cuối cùng, đề xuất mơ hình truy tìm ảnh mặt người
nhìn thẳng tổng quát cho một ứng dụng thực nghiệm (tự xây dựng).

-7-


Giai đoạn 3: Tìm hiểu ứng dụng thực tế của bài tốn truy tìm ảnh mặt người
nhìn thẳng: bài tốn nhận diện thông tin đối tượng thông qua ảnh hộ chiếu . Đề xuất

mơ hình phù hợp với ứng dụng này, và kiểm chứng các kết quả thử nghiệm.
Dưới đây trích nội dung nghiên cứu của đề tài:
STT
1

Nội dung
Tìm hiểu, nghiên cứu các kỹ thuật tính tốn thơng minh (NN, FL, GA, SVM,…)
và các ứng dụng của nó.

2

So sánh các kỹ thuật thông minh: nêu ưu khuyết điểm từng kỹ thuật, lớp bài tốn
mà kỹ thuật đó có thể giải quyết, sự thể hiện của từng kỹ thuật như thế nào trong
từng lớp bài tốn.

3

Tìm hiểu về các nghiên cứu đã có về bài tốn nhận dạng mặt người nhìn thẳng:
mơ hình thực hiện qua các bước, các kỹ thuật đã nghiên cứu và áp dụng.

4

Phát triển các kỹ thuật tính tốn thơng minh ứng dụng cho từng khâu trong mơ
hình nhận dạng mặt người nhìn thẳng để có được những giải pháp tốt hơn cho
từng khâu trong mơ hình. Trong từng kỹ thuật đề xuất, đều có so sánh đánh giá
với các kỹ thuật hiện có để chỉ ra tính ưu việt của kỹ thuật đề xuất. Kỹ thuật đề
xuất ở đây có thể sử dụng một, nhiều hay phối hợp các kỹ thuật thơng minh để
có hiệu ứng tốt nhất.

5


Xây dựng mơ hình thơng minh tổng qt cho bài tốn nhận dạng mặt người nhìn
thẳng.

6

Cài đặt một chương trình ứng dụng thể hiện mơ hình thơng minh giải quyết bài
tốn nhận dạng mặt người nhìn thẳng.

7

So sánh đối chiếu với các mơ hình, ứng dụng đã có thơng qua thực nghiệm để
chứng minh tính ưu việt của mơ hình đề xuất.
4. Sản phẩm của đề tài/dự án

Phần mềm truy tìm ảnh mặt người của các đối tượng bị truy nã thơng qua khóa
là ảnh chụp hộ chiếu cá nhân. Đề tài sẽ được ứng dụng thử nghiệm tại Cục Quản Lý
Xuất Nhập Cảnh- Bộ Công An. Địa chỉ: 254 Nguyễn Trãi, Q1, tp. Hồ Chí Minh.

-8-


CHƢƠNG 1:

TÌM HIỂU VỀ CÁC KỸ THUẬT TÍNH TỐN
MỀM

1.1

Các kỹ thuật tính tốn mềm ứng dụng trong đề tài

Trong đề tài, chúng tơi nghiên cứu tìm hiểu nhóm kỹ thuật sau: Nhóm 1gồm

các kỹ thuật trích chọn khơng gian biểu diễn mẫu: Phân tích thành phần chính
(Principal Component Analysis - PCA), Phân tích thành phần độc lập
(Independence Component Analysis - ICA), Phân tích tách lớp tuyến tính (LDA).
Nhóm 2 gồm các kỹ thuật phân lớp mẫu phổ cập: Phân lớp tuyến tính (Ada-Boost),
phân lớp bằng mạng Nơron nhân tạo (ANN) và phân lớp Suport Vector Machine
(SVM). Nhóm 3 gồm các kỹ thuật tính tốn gần đúng hỗ trợ cho bài toán nhận dạng
mẫu: Số mờ (Fuzzy), Thuật giải di truyền (Genetic Algorithms - GA).

1.2

Các kỹ thuật trích chọn khơng gian biểu diễn mẫu

1.2.1 Phƣơng pháp phân tích thành phần chính :
Q trình rút trích đặc trưng đã được thực hiện bởi các phương pháp truyền
thống : chia ô lưới, phép phân tích thành phần chính PCA, phân tích đặc trưng hình
học bằng cách xác định các thành phần quan trọng của khuôn mặt như mắt, mũi,
miệng… Trong các phương pháp trên phổ biến nhất là phương pháp PCA.
PCA (Principal Componens Analysis) [4][5][6] còn được gọi là Karhunen-Loeve
Transform (KLT) hay Hotelling transform. PCA tìm phép biến đổi tuyến tính để:

 Giảm số chiều của không gian đặc trưng nhưng vẫn giữ được các đặc trưng
chính.

 Cực tiểu hóa việc mất mát thông tin.
Phương pháp PCA chiếu dữ liệu theo chiều biến đổi nhiều nhất.


Hình 1-1 Hƣớng của vector riêng

 Ví dụ của phương pháp PCA: Rút trích đặc trưng cho tập mẫu khn mặt
Các tác giả đã trình bày phương pháp rút trích đặc trưng ảnh mặt người bằng
phương pháp kết hợp các đặc trưng hình học và PCA. Ý tưởng chính là:

 Khn mặt sau khi chuẩn hố sẽ được biểu diễn bằng vector có kích thước
30x30:
x face  ( x1 , x 2 ,..., x 900 ) .

 Sau đó vector

x

sẽ được ánh xạ vào trong không gian đặc trưng của khuôn

mặt . Vector biểu diễn trong không gian đặc trưng của khuôn mặt:

y face  ( y1 , y 2 ,..., y K )
K: số chiều trong không gian đặc trưng.
Vector trên được gọi là vector tồn cục của khn mặt.
Việc rút trích đặc trưng bằng phương pháp cho tập mẫu học gồm 2 bước chính:
Phân tích các thành phần chính của tập mẫu và ánh xạ tập mẫu vào trong miền
khơng gian đặc trưng.
 Các bước PCA rút trích đặc trưng cho tập mẫu khn mặt:

 Tính vector trung bình của tập mẫu M có kích thước 900 (30 x 30).
 Tính ma trận hiệp phương sai C (900 x 900).
 Tính các giá trị riêng (eigenvalue) và vector riêng (eigenvector) tương ứng
của ma trận hiệp phương sai C.

 Chọn K vector riêng tương ứng với K giá trị riêng tương ứng lớn nhất.



 Xây dựng ma trận U mà mỗi cột là một vector đặc trưng 900 chiều. Vậy
kích thước của ma trận U là 900 x K.

 Ánh xạ toàn bộ tập mẫu khuôn mặt vào miền không gian đặc trưng (K
chiều).
Qua quá trình thực nghiệm, chọn giá trị K = 100 cho tất cả các bộ dữ liệu thử
nghiệm vì nó đáp ứng được yêu cầu nhận dạng.
 Khuyết điểm của phương pháp PCA:
Đích đến của PCA là tìm một tập ảnh cơ sở tốt hơn, để trong tập ảnh cơ sở mới
này sự phối hợp các ảnh là không tương quan (các thành phần chính là khơng tương
quan). Để làm được điều đó, PCA đã sử dụng thống kê bậc hai (ma trận hiệp
phương sai). Vì vậy các sự phụ thuộc thống kê bậc cao vẫn còn tồn tại trong phép
phân tích PCA.
Trong các cơng việc như nhận dạng mặt người, nhiều thơng tin quan trọng có thể
được chứa trong mối quan hệ thống kê bậc cao giữa các pixel của ảnh, không chỉ là
thống kê bậc hai, như PCA. Vì vậy chúng ta cần tìm một phương pháp tống quát
hơn PCA.
1.2.2 Phƣơng pháp phân tích thành phần độc lập:
Với các khuyết điểm của PCA ta cần tìm một phương pháp tổng qt hơn PCA,
đó chính là ICA (Independent Component Analysis) [2][10][13][14].
ICA đã được áp dụng thành công trong bài tốn tách nguồn mù (cocktail party
problem), tách tín hiệu điện não đồ (Electroencephalo gram – EEG).
PCA có thể được xem như một trường hợp đặc biệt của ICA khi các nguồn có
phân phối Gauss, trong trường hợp này thì ma trận trộn không xác định được.
Phương pháp PCA chưa phải là một phương pháp tốt trong trường hợp các nguồn
có phân phối phi Gauss. Theo kinh nghiệm quan sát, người ta đã xác định được rằng
nhiều tín hiệu tự nhiên như âm thanh, ảnh tự nhiên, và EEG là sự tổ hợp tuyến tính
của các nguồn với phân phối siêu Gauss (kurtosis dương), trong trường hợp này,

ICA là một phương pháp tốt hơn PCA vì:


 Cung cấp một mơ hình xác suất tốt hơn của dữ liệu.
 Nó xác định duy nhất ma trận trộn.
 Nó tìm thấy một cơ sở khơng cần thiết trực giao mà có thể xây dựng lại dữ
liệu tốt hơn PCA.

 Nó áp dụng các thống kê bậc cao trong dữ liệu không chỉ là ma trận hiệp
phương sai như PCA.

 ICA tốt hơn PCA trong môi trường nhiễu chẳng hạn như độ sáng biến đổi,
các biến đổi cảm xúc trên khn mặt, trang điểm trên khn mặt...
Hình 1-2 chỉ ra các mẫu trong một không gian ba chiều, được xây dựng bởi sự
kết hợp tuyến tính của hai nguồn có phân phối siêu Gauss.
Các vector cơ sở của PCA và ICA cũng được xác định, bởi vì ba vector cơ sở của
ICA là không trực giao nên chúng sẽ thay đổi khoảng cách giữa các điểm dữ liệu, vì
nếu các vector là trực giao thì khi chiếu dữ liệu xuốn g khơng gian trực giao mới
này thì khoảng cách giữa các điểm dữ liệu không thay đổi (PCA). Điều này có thể
hữu dụng cho các thuật tốn phân lớp, giống như thuật toán người láng giềng gần
nhất, luật quyết định dựa trên khoảng cách giữa các điểm dữ liệu...

Hình 1-2 Sự phân phối dữ liệu, và các trục tƣơng ứng của PCA & ICA
Mỗi trục là một cột của ma trận nghịch đảo của ma trận trộn W-1 tìm thấy bởi
PCA và ICA. Các trục của PCA trực giao trong khi ICA thì khơng, do đó khoảng
cách các điểm dữ liệu sẽ thay đổi khi chiếu xuống không gian mới này.
 Có hai kiến trúc để áp dụng ICA rút trích đặc trưng trong ảnh.
Hàng giữa trong hình 1-3 chỉ ra 8 ảnh cơ sở sinh ra bởi kiến trúc 1, chúng xác
định không gian khuôn mặt không giống như PCA (hàng trên) và ICA kiến trúc 2
(hàng cuối). Barlett [10][13] trước tiên đã áp dụng PCA để chiếu dữ liệu xuống



một không gian con m chiều để điều khiển số thành phần độc lập xác định bởi ICA.
Một trong các thuật toán ICA được áp dụng lên các vectơ riêng để cực tiểu hóa sự
phụ thuộc thống kê giữa các ảnh cơ sở kết quả. Như vậy PCA bất tương quan dữ
liệu đầu vào, các sự phụ thuộc bậc cao cịn lại được tách ra bởi ICA.

Hình 1-3 Vector đặc trƣng cho mỗi kĩ thuật.
Hàng đầu chứa 8 vector riêng với 8 trị riêng lớn nhất trong PCA.
Hàng 2 chứa các vectơ đặc trưng trong ICA với kiến trúc I.
Hàng 3 chỉ ra 8 vector đặc trưng trong ICA với kiến trúc 2.
 Áp dụng ICA trong rút trích đặc trưng trong ảnh:
Đặt X là ma trận dữ liệu với nr hàng và nc cột. Chúng ta xem các cột của ma trận
X là như là các kết quả quan sát (các thử nghiệm độc lập) của các thực nghiệm ngẫu
nhiên. Ta xem hàng thứ i của X như là các giá trị quan sát được của biến ngẫu nhiên
Xi thơng qua nc lần thử nghiệm độc lập. Ta có xác suất phân phối của X1, …, Xnr
trong mỗi cột của X là 1/nc. Ta nói hai hàng i và j của X là độc lập nếu khơng thể
dự đốn các giá trị của Xj thông qua các cột từ các giá trị tương ứng của Xi.
P(Xi = u, Xj= v) = P(Xi = u)P(Xj = v) với mọi u,v thuộc R.
Mục đích của chúng ta là tìm một tập ảnh cơ sở tốt để đại diện cho tập ảnh khuôn
mặt. Chúng ta sắp xếp mỗi ảnh trong cơ sở dữ liệu như là một vectơ với số chiều là
số pixel của ảnh. Chúng ta có hai cách tiếp cận (hai kiến trúc):

 Kiến trúc 1:
Chúng ta sắp xếp ma trận ma trận dữ liệu X với mỗi hàng là là một ảnh khác
nhau, trong cách tiếp cận này các ảnh là các biến ngẫu nhiên và các pixel là các


quan sát, ở đây tạo cho chúng ta cảm giác về sự độc lập của các ảnh. Hai ảnh i, j
được gọi là độc lập nếu chúng ta không thể dự đoán giá trị của pixel trên ảnh j dựa

trên giá trị của pixel tương ứng cột trên ảnh i.

Hình 1-4 Minh họa kiến trúc 1 trong mơ hình ICA

 Kiến trúc 2:
Đặt các ảnh thành các cột của ma trận dữ liệu X. Trong cách sắp xếp này, các
pixel xem như các biến ngẫu nhiên, số lượng pixel của một ảnh cũng chính bằng số
micro, bằng số thành phần độc lập, các ảnh là các sự quan sát. Ở đây tạo cho chúng
ta cảm giác nói về sự độc lập của các pixel. Ví dụ pixel i và j được gọi là độc lập
nếu chúng ta không thể dự đoán giá trị của của pixel i dựa trên giá trị của pixel j
tương ứng trên cùng một ảnh.

Hình 1-5 Minh họa kiến trúc 2 trong mơ hình ICA
Minh họa ICA cho kiến trúc 2:


Hình 1-6 Mơ hình tổng hợp ảnh cho kiến trúc 2 của ICA

Hình 1-7 Mơ hình tổng hợp ảnh cho kiến trúc 2 của ICA trên pixel
S là các nguồn độc lập chưa biết. Ma trận A xem như là tập ảnh cơ sở. Mỗi ảnh
trong tập dữ liệu X được xem như là tổ hợp tuyến tính của tập ảnh cơ sở trong ma
trận A. Tập ảnh cơ sở được kết hợp với một tập các nguồn độc lập S. A = W I-1 với
WI được ước lượng thông qua ICA.

U chứa các hệ số độc lập cho sự kết hợp tuyến tính của các ảnh cơ sở trong A để
cấu thành nên mỗi ảnh trong X.


Sau khi rút trích đặc trưng của khn mặt bằng phương pháp PCA ta có các
vector đặc trưng. Đặc trưng khuôn mặt yface, trong đặc trưng này các pixel là bất

tương quan nhưng vẫn có thể tồn tại các sự phụ thuộc bậc lớn hơn hai giữa các
pixel, vì vậy ta phân tích thành phần độc lập cho vector yface để tạo sự độc lập cho
dữ liệu :

y face   y face
ICA

_ ICA

1.2.3 Phân tích tách lớp tuyến tính:
Nếu như các phương pháp như PCA và ICA mạnh về khả năng rút trích đặc
trưng (feature classification) thì LDA [7][8][9][12][14] mạnh về phân lớp dữ liệu
(data classification). PCA và ICA tìm ra 1 khơng gian để khi chiếu 1 ảnh khn mặt
vào đó, những gì đặc trưng nhất của khn mặt sẽ được giữ lại, điều này phục vụ
cho quá trình nhận dạng, theo đó, sự khác biệt giữa những khn mặt sẽ được làm
nổi bật lên. LDA thì tìm ra 1 không gian để khi chiếu tập ảnh khuôn mặt vào đó,
các mẫu trong tập ảnh được phân thành từng lớp riêng biệt tùy thuộc nội dung ảnh
khuôn mặt đó thuộc lớp nào.
Một ―khơng gian chiếu tốt‖ là một không gian mà khi chiếu tập dữ liệu vào,
những mẫu cùng phân lớp sẽ nằm gần nhau, còn những mẫu khác phân lớp sẽ nằm
xa nhau, hình 1 -8 minh họa 1 trường hợp điển hình.

Khơng

Khơng

gian chiếu

gian chiếu


khơng tốt

tốt

Hình 1-8 Không gian con của LDA


Chỉ cần tối đa (Số lớp – 1) không gian chiếu để phân biệt tất cả các lớp. Thật vậy,
ta dễ dàng chứng minh nhận định trên: do tính chất của sự phân bố dữ liệu, các mẫu
thuộc cùng 1 lớp nằm gần nhau hơn trong không gian. Cho nên đối với bài tốn
phân biệt 2 lớp, ta có thể nhận thấy rằng chỉ cần chiếu tập dữ liệu xuống 1 ―đường
thẳng‖ duy nhất là có thể phân biệt rõ ràng 2 lớp.

Hình 1-9 Minh họa trƣờng hợp phân biệt 2 lớp
Đối với bài toán phân biệt 3 lớp, ta cần 3 – 1 = 2 ―đường thẳng‖ để chiếu dữ liệu.

Hình 1-10 Minh họa trƣờng hợp phân biệt 2 lớp
Bằng cách chứng minh quy nạp, ta có thể kết luận rằng: chỉ cần chiếu tập dữ liệu
về không gian (n-1) chiều thì có thể phân biệt được n lớp.