“Nghiên cứu xây dựng phần mềm nhận dạng ảnh theo thuật toán PCA,
FLD” cho đồ án tốt nghiệp của mình 2
LỜI NÓI ĐẦU
Thế giới ngày nay với sự phát triển mạnh mẽ của kỹ thuật số và mạng
toàn cầu, vấn đề đảm bảo an toàn về thông tin cũng như vật chất trở nên ngày
càng quan trọng và khó khăn. Thỉnh thoảng chúng ta lại nghe nói đến những
vụ đánh cắp thẻ tín dụng, đột nhập trái phép vào các hệ thống máy tính hay
toà nhà của cơ quan nhà nước, chính phủ. Hơn 100 triệu đô la là con số đã bị
thất thoát ở Mỹ vào năm 1998 do các vụ gian lận và xâm nhập nói trên (theo
Reuters, 1999). Trong đa số các vụ phạm pháp này, tội phạm đã lợi dụng
những khe hở cơ bản trong quá trình truy cập vào các hệ thống thông tin và
kiểm soát. Phần lớn những hệ thống này không thực hiện quyền truy cập của
người sử dụng dựa vào thông tin “chúng ta là ai” mà chỉ dựa vào “chúng ta có
gì”. Nói cách khác, thông tin mà người sử dụng cung cấp cho hệ thống không
đặc trưng được cho bản thân họ, mà chỉ là những gì họ hiện đang sở hữu như
số chứng minh nhân dân, chìa khoá, mật mã, số thẻ tín dụng hoặc họ tên. Rõ
ràng những thông tin hay vật dụng này không mang tính đặc trưng mà chỉ
mang tính xác thực đối với người sử dụng, và nếu chúng bị đánh cắp hay sao
chép thì kẻ trộm hoàn toàn có quyền truy nhập, sử dụng dữ liệu hay phương
tiện của chúng ta bất cứ lúc nào họ muốn.
Nhận dạng khuôn mặt là một trong số ít các phương pháp nhận dạng dựa
vào đặc trưng sinh lý cho kết quả chính xác cao đồng thời rất thuận tiện khi sử
dụng. Hơn nữa, trong số các đặc trưng sinh lý học, khuôn mặt của mỗi người
là yếu tố đầu tiên và quan trọng nhất cho việc nhận biết lẫn nhau cũng như
biểu đạt cảm xúc. Khả năng nhận dạng nói chung và khả năng nhận biết
khuôn mặt người nói riêng của con người thật đáng kinh ngạc. Chúng ta có
khả năng nhận ra hàng ngàn khuôn mặt của những người mình đã gặp, đã
giao tiếp trong cuộc sống chỉ bằng một cái nhìn thoáng qua, thậm chí sau
1
nhiều năm không gặp cũng như những sự thay đổi trên khuôn mặt do tuổi tác,
cảm xúc, trang phục, mầu tóc,…Do đó, việc nghiên cứu các đặc tính của

người.
Chương 4: Cài đặt chương trình nhận dạng ảnh mặt người
Cài đặt chương trình đồng thời thể hiện các bước của quá trình nhận dạng
và giới thiệu ứng dụng đã xây dựng, cách sử dụng.
Kết luận
Những kết luận chung về đồ án, hướng phát triển và đề nghị.
Phụ lục 1,2:
Các công thức toán học dùng trong báo cáo, kết quả và chứng minh toán
học cho các kết luận.
Trong quá trình nhận và thực hiện đồ án của mình Em xin chân thành cám
ơn thầy giáo PGS.TS cùng các thầy cô trong khoa Công Nghệ Thông Tin -
đã tận tình giúp đỡ để Em hoàn thành đồ án tốt nghiệp của mình.
CHƯƠNG 1 : MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ SỬ LÝ ẢNH SỐ
1.1 Một số khái niệm cơ bản
3
 Pixel (picture element - điểm ảnh )
Ảnh trong thực tế là một ảnh liên tục về không gian và giá trị độ sáng.
Quá trình thu nhận ảnh số là quá trình số hoá ảnh. Đó là quả trình biến đổi
tín hiệu liên tục thành tín hiệu rời rạc. Một ảnh khi được số hoá là tập hợp
các điểm ảnh, nó được biểu diễn bởi mảng 2 chiều I(n,p) trong đó n- số
dòng, p- số cột. Ta nói ảnh gồm nxp điểm ảnh, ký hiệu I(x, y) là giá trị
điểm ảnh tại vị trí dòng y cột x.
 Ảnh đen trắng, ảnh đa mức xám, ảnh màu
 Ảnh đen trắng, ảnh đa cấp xám: gồm 2 màu (đen, trắng), người ta
phân các mức độ (L) đen trắng như sau:
+L=2: ảnh gồm 2 mức, mức 0 ứng với màu tối, mức 1 ứng với màu
sáng. Ảnh này gọi là ảnh nhị phân. Mỗi điểm ảnh được mã hoá trên
1 bit.
+L>2: Ảnh đa mức xám, việc xác định số mức phụ thuộc vào tiêu
chuẩn lượng hoá, L thường được chọn là 32, 64, 126, 256. Thường

1)-Nf(0, f(0,1) )0,0(f
),( yxf
Như vậy nếu ta có một ảnh kích thước 800x600 thì khi biểu diễn thành
ma trận 2 chiều có số hàng là 600, số cột là 800, mỗi phần tử của ma trận có
giá trị từ 0-255.
Đối với ảnh màu, mỗi phần tử của mảng 2 chiều là một bộ giá trị RGB.
Phần tử f(i,j) của ma trận có dạng
f(i, j)=(B(i, j), G(i, j), R(i, j)).
Giá trị điểm ảnh tại điểm (i, j) được tính:
f(i,j) = h (B(i, j), G(i, j), R(i, j))= B(i,j)*256
2
+ G(i, j)*256 + R(i, j).
Mô hình RGB:
Hệ này mô tả màu sắc thông qua 3 thành phần màu cơ bản là Red, Green và
Blue. Có thể mô xem xét mô hình RGB trong không gian 3 chiều như hình
1.2.1.
Mọi điểm nằm trong khối hộp chữ nhật có toạ độ (r,g,b) thể hiện một màu.
Màu nằm trên đường chéo (0,0,0) - (1,1,1) (3 thành phần R, G, B bằng nhau)
->thể hiện mức xám.

Red=(1,0,0)
Black=(0,0,0)
Magenta=(1,0,1)
Blue=(0,0,1)
Cyan=(0,1,1)
White=(1,1,1)
Green=(0,1,0)
Yellow=(1,1,0)
5
Hinh 1.2.1 - Mô hình màu RGB

Hình 1.3.1 Biến đổi xám từ ảnh mầu
6
Với Gray(i,j) được tính theo phương trình ở trên.
Với biến đổi nhị phân thì Gray(i,j) = 0 nếu Gray(i,j)<= Threshold, Gray(i,j) =
1 nếu ngược lại với 0<=Threshold <=255.
CHƯƠNG 2 : LÝ THUYẾT VỀ PCA VÀ FLD
2.1 Phương pháp thống kê đối với bài toán nhận dạng mẫu
2.1.1 Trung bình, độ lệch chuẩn, phương sai
Cho tập mẫu :
[ ]
1 2
, ,
n
X x x x
=
(2.1)
 Trung bình:
7
Mean của tập X kí hiệu là
X
là giá trị trung bình của mẫu hay kỳ
vọng mẫu
Tính theo công thức :
1
1
n
i
i
X x
n

1
1
n
i
i
x X
n
=
−
−
∑
(2.3)
“Trung bình khoảng cách từ giá trị trung bình đến mỗi phần tử trong
tập hợp”.
Độ lệch chuẩn cho biết sự phân bố của các phần tử so với giá trị trung
bình. Nếu giá trị này càng lớn thì các phần tử phân bố xa giá trị trung
bình(Độ phân tán dữ liệu cao) còn giá trị này nhỏ thì ngược lại chúng
gần giá trị trung bình(Độ phân tán dữ liệu thấp).
Ví dụ:
>> X1=[0 8 12 20];
>> X2=[8 9 11 12];
>> std(X1)
ans = 8.326
>> std(X2)
ans = 1.8257
9
Hình 2.1.1.2 Độ lệch chuẩn của tập
Như vậy các phần tử của X2(Xanh) gần giá trị Mean hơn X1(Đỏ).
Khi s = 0 thì tất cả các phần tử của tập bằng giá trị Mean.
 Phương sai:

[ ]
1 2
, , ,
n
X x x x=
,
[ ]
1 2
, , ,
n
Y y y y=
.
10
Covariance luôn được tính cho 2 chiều, nếu ta tính Covariance cho
một chiều và chính nó ta được Variance.
Công thức tính Covariance gần giống công thức tính Variance.
Công thức tính Variance:
( ) ( ) ( )
2
1 1
( )
1 1
n n
i i i
i i
X X X X X X
Var X
n n
= =
− − −

trị dương thì cho ta biết 2 chiều này tăng cùng nhau và khi giá trị âm
thì một chiều tăng chiều kia giảm. Qua thí dụ trên ta thấy một điều khi
giờ học cao lên thì kết quả học tập cũng tôt lên.
Khi Cov = 0 thì hai chiều độc lập nhau nghĩa là sao? Kết quả học
tập không phụ thuộc vào giờ học.
 Ma trận hiệp sai:
Cho N mẫu
1 2
, , ,
N
X X X
với
[ ]
( )
1 2
, , , 1
T
i i i iM
X x x x i N
= =
là các vector M-chiều, xét tập mẫu
[ ]
1 2
, , ,
N
X X X X
=
Kỳ vọng mẫu :
{ }
1

kỳ vọng mẫu.
( )
( ) ( )
( )
1 1
2
2
ij
1 1 1
1
1
1 1
1 1
N N
T
ii i i
i i
N M N
j i
i j i
Trace C C Trace X X X X
N
X X X X
N N
= =
= = =
 
= = − −
 ÷
−

)=Trace(B
mxn
A
nxm
). thật vậy do
1 1 1 1
n m m n
ij ji ji ij
i j j i
a b a b
= = = =
=
∑∑ ∑∑
với a
ij
và b
ji
là các phần tử của A
nxm
và
B
mxn
.
Vậy ta có
( ) ( )
( )
T T
Trace C Trace C Trace C
Φ Φ = ΦΦ =
vì

χ
µ µ
= ∈
= − −
∑ ∑
(2.9)
Ma trận hiệp sai trong cả lớp
( ) ( )
1
k i
C
T
T k k B W
i x
S X X S S
χ
µ µ
= ∈
= − − = +
∑ ∑
(2.10)
Với các tham số:
 C là số lớp
 µ
i
là Mean của lớp χ
i
14

µ

Nhược điểm:
 Khi có sự thay đổi nhỏ về ánh sang, cảm xúc, hướng đầu thì các giá trị
ảnh thay đổi rất nhiều và dẫn đến vị trí của chúng trong không gian mặt
thay đổi rất nhanh như vậy quá trình nhận dạng sẽ kém chính xác.
 Dung lượng để lưu các đặc trưng lớn.
Giải pháp:
Giảm số chiều dữ liệu – thông qua phép biến đổi tuyến tính.
2.2.2 Phép biến đổi tuyến tính:
T
Y A X
=
(2.11)
với
( )
,
K N
Y X K N
∈ ∈ ≤
¡ ¡
và các vector cột của
T
A
trực giao.
Ý nghĩa của phép biến đổi này cho phép ta giảm số chiều của dữ liệu (N
->K).
16
( )
1
1
2

nghiên cứu từng phương pháp.
2.3 Lý thuyết về PCA - Principal Component Analysis[5. Trang 331-340].
Phương pháp PCA:
 Thực hiện giảm số chiều và đảm bảo tối đa sự phân tán dữ liệu.
 Ý nghĩa của sự phân tán dữ liệu là đảm bảo các đặc trưng trong không
gian mới phân bố rộng (tính khác nhau) như vậy các mẫu khác nhau thì
đảm bảo xa nhau do vậy việc nhận dạng sẽ chính xác hơn.
 Nghiên cưú phương pháp
Có nhiều tên cho Principal Components Analysis-PCA và nó được
dung nhiều trong nghiên cứu và ứng dụng. PCA cùng nghĩa với
Karhunen-Loeve (KL) transform, Hoteling transform, Egenvalue
Aalysis, Eigenvector Dcomposion và Spectral Decomposion. Trong
phân tích ảnh nó được dung để giảm số chiều và tìm không gian con
(subspace) mà trong đó việc nhận dạng tốt hơn trong khônng gian với
số chiều đầy đủ. Không những thế nó còn có thuận tiện khi lưu trữ,
chuyển đổi và xử lý thuận tiện.
17
Xem tập quan sát gồm K-vectors.
{ }
1 2
, , , , ,
k K
f f f f f
=
(2.13)
Trong không gian M-chiều.
Không gian của tập quan sát có thể được thể hiện qua một số cơ sở giả
sử.
{ }
1 2

3 , 3 , , 3 , , 3

k K
k K
k k K K
k K
f f f f
f f f f
f f f f f f f f
f M f M f M f M
       
 ÷  ÷  ÷  ÷
 ÷  ÷  ÷  ÷
 ÷  ÷  ÷  ÷
= = = =
 ÷  ÷  ÷  ÷
 ÷  ÷  ÷  ÷
 ÷  ÷  ÷  ÷
 ÷  ÷  ÷  ÷
       
(2.15)
Ở đây
( )
k
f m
là thành phần thứ m của vector
k
f
. Mỗi vector
k

quá lớn. Ta có thể biểu diễn mỗi quan sát
N
Β
thông qua ít vector hơn.
18

( )
~
1
N
k m m
m
f f m
ψ
=
=
∑
với
N Mp
(2.17)
Nhận thấy điều khác nhau duy nhất giữa E.q 2.17 và 2.16 là số lấy
tổng N và M. theo thứ tự mỗi phương trình của 2.17 được thể hiện qua
2.17 ta được các vector .

~ ~ ~ ~
1 2
, , , , ,
k K
f f f f
(2.18)

≠
.
N
Β
được gọi là cắt (truncated) của
m
g = Ψ
khi nó nhận ít vector cơ sở
hơn. Vậy ta thể hiện
Ο
trong cơ sơ nhỏ hơn vói sai số :

2
~
1
1
K
k k
k
f f
K
=
−
∑
(2.21)
Chúng ta quan tâm là làm sao tổng này – Minimizing.
( )
(
)
2

∑
∑
(2.22)
Sử dụng 2.16 và 2.17 ta có
19
( ) ( )
( ) ( ) ( )
( ) ( )
2 2
2
~ ~
1 1 1 1
2
~
1 1 1 1
2
~ ~ ~
1 1 1
2 ,
2 ,
2 , 2 ,
K K M N
k k k k k m k m
k k m m
K N M N
k k m k m k m
k m m N m
K M N
k k k k m k m
k m N m

k
T f
=
=
∑
- Là hằng số (2.24)
Trong phương trình 2.23 thì đại lượng
2
~ ~ ~
,
k k k
f f f=
còn thành
phần thứ hai triệt tiêu do cơ sở trực giao, vậy ta có.

2 2
~ ~
1 1
1 1
K K
k k k
k k
T
f f f
K K K
= =
− = −
∑ ∑
(2.25)
Do T là hằng số lên Minimizing biểu thức tương đương Maximizing

ψ ψ
=
vậy
20

2
~ ~ ~
1 1 1 0
1 1 1 1
( )
1 1
, , ,
K K K N
k k k m k k m
k k k m
K N N K
T T T T
m k k m m k k m
k m m k
N N
T
m m m
m m
f f f f f
f f f f
K S K
ψ ψ
ψ ψ ψ ψ
ψ ψ λ
= = = =

∑
(2.28)
Thoả mãn
1 2
0
N
λ λ λ
≥ ≥ ≥
là các trị riêng của S(Do S đối xứng lên
có các trị riêng thực
≥
0 [Bổ đề 3]).
Đây là ma trận phân bố các quan sát
Ο
Theo cách xây dựng thì S là
ma trận nửa xác định riêng nghĩa là
0
T
g Sg
≤
với
M
g E∀ ∈
. thay
m
g = Ψ
Từ phương trình 2.25 và 2.27 ta có

2 2
~ ~

(1) (2) ( )
1
1

K
k M
k
T
f
K K
λ λ λ
=
= = + + +
∑
(2.30)
21
Ta nhận thấy xấp xỉ không lồi khi mà
~
k k
f f
=
nghĩa là ta dung
tất cả các vector cơ sở (i.e N=M Phương trình 2.24 và 2.27).
Biểu diễn 2.29 thể hiện khi ta chọn N-vectors riêng và sai số xấp
xỉ là nhỏ nhất và bằng tổng M-N trị riêng bé nhất của S. (2.28) thành.

[ ]
1
2
1 2

~
T
T
N
Ο = Ο Β
(2.32)
Với

[ ] [ ]
~ ~ ~ ~
1 2 1 2 1 2
, , , , , , , , , , ,
K N N K
f f f f f f
ψ ψ ψ
 
Ο = Ο = Β =
 
(2.33)
với
[ ]
1 2
, , ,
K
ψ ψ ψ
là K-vectors riêng tương ứng với K-trị riêng lớn
nhất của S(2.28)- ma trận hiệp sai của tập quan sát ban đầu.
Như ta biết phép biến đổi trực giao không làm thay đổi Trace-Vết của
ma trận mà phép biến đổi cơ sở này giứ lại K-vectors riêng ứng với K-trị
riêng lớn nhất. Nghĩa là ta sự phân bố các mẫu trong tập dữ liệu mới thu

≥ ≥ ≥
2.4 Lý thuyết về FLD – Fisher’s Linear Discriminant[4, Trang 436-472]
Có hai kiểu tiêu chuẩn thường được sử dụng trong nghiên cứu. Một là dựa
trên họ các hàm về ma trận phân bố chúng được tính toán đơn giản và cho ta
một hệ thống các thuật toán trích chọn đặc trưng. Tiêu chuẩn để đo sự phân
bố của L-classcs. thứ hai là họ các tiêu chuẩn cho ta biên trên của các lỗi
Bayes.
Ma trận phân bố và tiêu chuẩn phân bố:
Trong phân tích phân biệt của thống kê, Ma trận phân bố trong lớp, ngoài
lớp và của tất cả được sử dụng để tính các tiêu chuẩn phân lớp.
Ma trận phân bố trong một lớp cho ta biết sự phân bố các mẫu tương ứng
với kỳ vọng của lớp và cho bởi công thức.
( ) ( )
{ }
1 1
|
L L
T
W i i i i i i
i i
S PE X M X M P
ω
= =
= − − = Σ
∑ ∑
(2.35)
Trên vấn đề khác, một ma trận đặc trưng cho sự phân bố giữa các lớp
quanh kỳ vọng của cả tập là
( ) ( )
0 0

0 0
T
M W B
S E X M X M S S
= − − = +
(2.37)
Tất cả các ma trận được xây dựng ở trên bất biến đối với phép dịch
chuyển toạ độ.
Trong yêu cầu của các tiêu chuẩn phân lớp, ta cần chuyển ma trận thành
số để rễ đánh giá. Giá trị này lớn khi sự phân bố giữa các lớp lớn hoặc sự
phân bố trong các lớp nhỏ. dưới đây là một số công thức điển hình.
(1)
1
1 2 1
( )J tr S S
−
=
(2.38)
(2)
1
2 2 1 1 2
ln ( ) ln( ) ln( )J S S S S
−
= = −
(2.39)
(3)
( ) ( )
( )
3 1 2
J tr S tr S C

=
(2.42)
24
với A[NxM] và các cột của A độc lập tuyến tính. Da các ma trận
W
, or
B M
S S S
là các ma trận hiệp sai
1 2
,S S
trong không gian Y-space có
thể được tính thong qua
1 2
,S S
trong không gian X-space theo công thức.
( 1,2)
T
iY iX
S A S A i
= =
(2.43)
Vấn đề trích chọn đặc trưng là ta tìm A sao cho tối ưu J’s trong Y-Space.
Tối ưu J
1
: Giả sử J
1
(m) là giá trị của J
1
trong không gian m-chiều Y-space.

tối ưu A thoả mãn phương trình (2.45) bằng 0
( ) ( )
1 1
2 1 2 1X X Y Y
S S A A S S
− −
=
(2.46)
Hai ma trận
1 2Y Y
s ands
có thể được chéo hoá thành
m
µ
và
m
I
qua phép
biến đổi tuyến tính
T
Z B Y
=
như sau:
1 2
,
T T
Y m Y m
B S B B S B
µ
= = Ι