Chương 6: Nhận Dạng Ảnh

170
Chương 6

NHẬN DẠNG ẢNH
6.1 Giới thiệu
 Có 3 cách tiếp cận nhận dạng ñối tượng:
o Dựa vào phân hoạch không gian
o Dựa vào cấu trúc
o Dựa vào kỹ thuật mạng neural (cơ chế ñoán nhận, lưu trữ, phân biệt ñối
tượng, mô phỏng theo hoạt ñộng hệ thần kinh)
Nhận dạng là quá trình phân loại các ñối tượng biểu diễn theo một mô hình
nào ñó, gán chúng vào 1 lớp dựa theo các quy luật, các mẫu chuẩn.
 Có hai loại nhận dạng:
1. Nhận dạng có thầy (học có giám sát): supervised learning.
2. Nhận dạng không có thầy (học không giám sát): non-supervised learning.
 Các ứng dụng nhận dạng:
o Nhận dạng chữ viết tay (Document Handling)

Hình 6.1 Ảnh chữ viết tay
o Nhận dạng chữ ký (Signature Verification)

Chương 6: Nhận Dạng Ảnh

biểu diễn 1 ñối tượng.
b. Không gian diễn dịch
o Không gian diễn dịch là tập các tên gọi của ñối tượng.
Ω - tập tên ñối tượng.

Chương 6: Nhận Dạng Ảnh

172
Ω = {w
1
, w
2
,…, w
k
}.
w
i
(i =1, 2,…) là tên các ñối tượng.
o Quá trình nhận dạng ñối tượng f là 1 ánh xạ f: ℵ→Ω với f là tập các quy
luật ñể xác ñịnh 1 phần tử trong ℵ ứng với một phần tử trong Ω.
o Nếu tập hợp các quy luật và tập tên các ñối tượng ñược biết trước, (ví dụ
như nhận dạng chữ viết, có 26 lớp từ A ñến Z), thì gọi là nhận dạng có thầy.
o
Ngược lại gọi là nhận dạng không có thầy (khó hơn).

6.1.2 Mô hình và bản chất của quá trình nhận dạng
a. Mô hình của quá trình nhận dạng

y
N
yx
N
x
Tọa ñộ tâm ñiểm (6.0)
o Nên moment trung tâm bậc p,q của ñường bao sẽ là:

Chương 6: Nhận Dạng Ảnh

173
( ) ( )
q
oi
N
i
p
oiqp
yyxx
N
−−=
∑
=1
,
1
µ

b. B
ản chất của quá t
o Quá trình nh
ận d
1. L
ựa chọn mô
2. L
ựa chọn luậ
trình học.
3. H
ọc nhận dạn
o Khi ñã xác ñ
ịnh
ñ
ịnh tính: mô h
o Nh
ận dạng chính
vào 1 l
ớp, nói cá
 H
ọc có giám sát (supe
o K
ỹ thuật phân lo
o ðặc ñiểm c
ơ b
(cánh ñ
ồng lúa, c
o B

mô h
ình cấu trúc), thì chuy
ển sang giai ñoạn 3 (
chính l
à tìm ra quy luật và các thu
ật toán ñể có
nói cách
khác là gán cho ñối tượng 1 tên.
t (supervised learning):

hân loại nhờ kiến thức biết tr
ước gọi là h
ọc có g
ơ b
ản là có 1 thư vi
ện các mẫu chuẩn ñể biết
g lúa, cánh rừng, v
ùng ñ
ất hoang, sông, biển, ñ
thiết kế 1 hệ thống ñể so sánh v
à quy
ết ñịnh gá
phân l
ớp hay hàm ra quyết ñịnh)
sát (unsupervised learning):

nh ra các lớp khác nhau v
à xác ñ
ịnh các tham
ày ti

a. Kết nhóm là gì?
Kết nhóm l
à ñi
m
ột nhóm sẽ giống nh
b. Các ki
ểu kết nhóm
Kiểu nhóm l
à t
kiểu bậc và ki
ểu phân
o Ki
ểu nhóm phân
t
ập con không c
giống nhau.

Chươ
175
ình 6.6 S
ơ ñồ khối các giai ñoạn nhận dạng

à ñi t
ìm nhóm của các ñối tượng m
à các ñ
iống nhau v
à ngược lại
Hình 6.7 Kết nhóm dữ liệu ảnh
nhóm



o Ki
ểu nhóm dạng
cây bậc
c. Các cách k
ết nhóm
o K
ết nhóm dựa v
t
ập hợp các ñiểm
ñi
ểm ở nhóm kh
o K
ết nhóm dựa
tượng mà ñ
ối t
khác. Tr
ọng tâm
trong nhóm ñ
ể ñ

Chươ
176
dạng nhiều bậc: Mỗi tập của nhóm phân v
ùng
Hình 6.9 Kết nhóm kiểu nhiều bậc
nhóm

dựa v
ào cách phân chia chính xác (Well-

ột nhóm l
à tập của ñối
nhất so với các nhóm
ủa các tất cả các ñiểm Hìn
o K
ết nhóm dựa v
ñi
ểm trong nhóm
o K
ết nhóm dựa v
trong vùng mà n
m
ật ñộ cao. Khi
nhau thì khi
ñó s
Hì
o K
ết nhóm dựa v
các nhóm ñ
ể mô
Hình 6

Chươ
177

ết nhóm theo ñặc tính và thu
ộc tính
hương 6
: Nhận Dạng Ảnh

g tâm

à t
ập các ñiểm mà các
ới các nhóm
hóm l
à mật ñộ các ñiểm
ật ñộ thấp sang v
ùng có
au hoặc không bện v
ào
ên ngoài.ân bố

y or C
onceptual): Tìm ra
ên quan ñ
ặc biệt
ính


ng cho trư
Hình 6.15 Phân lớp ảnh có giám sát
hương 6
: Nhận Dạng Ảnh
à các ñ
ối tượng ñịnh
ệm: phân hoạch không

ho trư
ớc
 Phân l
ớp không giám
nó có th
ể theo một qu
Hìn
 Phân ho
ạch không gia
o Không gian ñ
ối t
o Ρ
ΡΡ
Ρ -1 phân ho
ạch
∪ C

(X

Chươ
179
g giám sát:
Phân l
ớp theo ñặc tính hay tích chấ
ột qui luật nhất ñịnh.

Hình 6.16 Phân l
ớp ảnh không giám sát
ng gian

ối t
ượng H ={X
i
,i=1,2,…,m} ; X
i

là 1 vector
ạch của
H thành các lớp C
i
, C
j
∈ H, nếu: C
i

ây là trư
ờng hợp lý tưởng, tập H tách ñược ho

i
àn toàn

ant functions)Chương 6: Nhận Dạng Ảnh

180
o ðể phân biệt k lớp, cần (k-1) hàm phân biệt (tuyến tính):
g(X)=W
0
+W
1
X
1
+W
2
X
2
+…+W
k
X
k
(6.3)
W
I

(
)
(
)
1
( / ) ( / )
( / )
( )
( / )
i i i i
i
n
i
i
p X C p C p X C p C
p C X
p X
p C X
=
= =
∑

(6.4)
Nếu p(C
i
/X)>p(C
k
/X) với ∀i và k, thì X∈C
i 182
o Các tập training ñược dùng ñể ước ñoán các tham số của giải thuật phân lớp
sẽ sử dụng (các tham số thuộc 1 lớp training gọi là mã của lớp ñó).
o Dựa vào các tập training, xếp loại tất cả các pixel của ảnh sao cho mỗi pixel
sẽ thuộc về một lớp duy nhất.
o Tạo ảnh (hoặc bản ñồ) phân lớp, tính toán các thống kê của việc phân lớp
6.2.4 Thuật toán nhận dạng theo phân lớp có giám sát
a. Phương pháp Maximum Likelihood
Là phương pháp thông dụng nhất. Sử dụng các thống kê (mean, variance
covariance) trong không gian phổ ñể xây dựng thuật toán.
Giả ñịnh rằng các giá trị phổ (ña chiều) trong mỗi lớp ñều có phân bố chuẩn
(normal distribution).
 Lý thuyết Bayes:
Giả sử có M lớp, gọi x là một vector phổ của một pixel ñang xét, p(x,i) là
xác suất ñể vector x thuộc lớp i. Nguyên tắc Maximum Likelihood là x thuộc lớp
i nếu p(x,i)>p(x,j) với mọi j
≠
i. Gọi p(i,x) là xác suất ñể lớp i hiện hữu, với x cho
trước, lớp i chứa vector x.


ðịnh lý Bayes:
p(i | x)= p(x | i) p(i) / p(x)
(6.5)

Do ñó ñiều kiện chọn lớp cho vector x trở thành
p(x,i) p(i) > p(x,j) p(j)







−
−=
2
2
2
2
exp
2
1
|
i
i
x
ixp
σ
µ
πσ

(6.8)

µ
i
: trị trung bình lớp i
σ

2
ln
2
1
2ln
2
1
)(ln
i
i
i
x
ip
σ
µ
σπ

(6.9)

b. Phương pháp Parallepiped
ðồ thị mô tả phương pháp parallepiped trong không gian ñặc trưng 3 chiều

Hình 6.17 Phân lớp ảnh theo phương pháp Parallepiped

Chương 6: Nhận Dạng Ảnh

184

2. M
ột vector pixe
ñ
ến tâm của lớp
3. Tính l
ại tâm của
4. N
ếu tất cả các t
Sau phân lớp k-
mean
o Lớp có
quá ít ph
o Hai lớp có ñ
ặc tr
o Một lớp n
ào ñó
deviation cho cá
 Các tham s
ố của thuậ
o Số các lớp: ng
ư
o S
ố lần lặp: số lầ
tốn thời gian h
ơn
o Ngưỡng thay
ñ
n
ếu sau một lần
không vư

ào ñó
quá lớn: có thể chia nhỏ (bằng cách ch
ỉ ra
cho các kênh ph
ổ)
a thuật toán K
-means:
ư
ời dùng chỉ ñịnh trước số lớp mà thu
ật toá
: số lần c
àng nhiều thì phân hoạ
ch càng “chính
ơn
(cần phải dung hòa).
ñ
ổi lớp (change threshold, thư
ờng tính bằn
ột lần lặp n
ào ñó, số phần trăm pixel thay ñ
ổi t
t quá, th
ì ngừng quá trình lặp.
hương 6
: Nhận Dạng Ảnh

p khởi ñầu

uclide, ch
ẳng hạn) từ nó

i
i
xmdistSSE
1
2
),(

(6.10)

o Nếu có k (số thực) nhóm thì sự thay ñổi mỗi trọng tâm của nhóm sẽ nhỏ ñi
o Nếu các nhóm có cùng kích thước n thì:
KK
k
K
K
Kn
nK
P
!
)(
!
==

(6.11)

 Ví dụ nếu k=10 thì: P=10!/10
10
=0,00036
o ðôi khi giá trị khởi tạo sẽ ñiều chỉnh chính trọng tâm ñó theo cách ñúng
nhưng có lúc thì không.

1
1.5
2
2.5
3
x
y
Iteration 3
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 4
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 5

:

một phân hoạch ban ñầu tr
ên các tâm b
ất kỳ (
thuộc v
ào phân lớp ban ñầu).
ằng cách sắp xếp các ñiểm v
ào tâm g
ần nh
ợng lớp ban ñầu, nếu khoảng cách > ng
ư
ỡng t
phân hoạch mới tr
ên cơ s
ở các lần vừa xác ñịnh
m mới.

ả các khoảng cách ñến tâm.

c vùng v
ới tâm theo ngưỡng t
2
lặp lại các
bư
ẩn phân hoạch.

.21 Phân l
ớp ảnh theo ph
ương pháp ISODAT

(x),…Hàm phân biệt có mọi ký hiệu (a,b,…)
Giả sử ta có từ (a,b,c,e) ñược biểu diễn bằng 1 dãy ký tự X={x
1
,x
2
,x
3
,x
4
}. Tính
các hàm tương ứng 4 ký tự trên
g
a
(X
1
)+g
b
(X
2
)+g
c
(X
3
)+g
e
(X
4
) (“+” = “OR”).
(6.12)


p – tập luật sản sinh

Chương 6: Nhận Dạng Ảnh

189
6.3.2 Các bước nhận dạng
Các ñối tượng ñược biểu diễn bằng 1 câu trong ngôn ngữ L(G). Thao tác phân
lớp là xét 1 ñối tượng có thuộc văn phạm L(G) hay không? Có nghĩa là nó có ñược
sinh ra bởi các luật của văn phạm G không?
 Phân lớp theo cấu trúc cần phải xác ñịnh:
o Tập V
t
chung cho mọi ñối tượng.
o Các quy tắc sinh p (ñể sinh 1 câu và dùng khác nhau ñối với mỗi lớp)
Quá trình học với các câu biểu diễn các ñối tượng mẫu I nhằm xác ñịnh văn
phạm G. Quá trình ra quyết ñịnh: xác ñịnh ñối tượng X (ñược biểu diễn bằng 1 câu I
X
).
Nếu I
X
nhận biết ñược bằng ngôn ngữ L(G
X
), thì ta nói C
k
∈X. Ra quyết ñịnh phân lớp
là dựa vào phân tích cú pháp của văn phạm (G
k

190
o Xác ñịnh các cặp ñiểm, bằng một ñường trong ma trận xấp xỉ.
o Hai nhóm giống nhau thì dựa vào 2 ñiểm giống nhau gần nhất ở 2 nhóm
khác nhau.
o Ưu ñiểm của phương pháp kết nhóm MIN: Cần thiết ñối với hình dạng Ellip
o Khuyết ñiểm: Nhạy với nhiễu và tác ñộng bên ngoài
 MAX:
o Hai nhóm giống nhau thì dựa vào 2 ñiểm giống nhau xa nhất ở 2 nhóm khác
nhau.
o Xác ñịnh các cặp ñiểm, bằng một ñường trong ma trận xấp xỉ. Hai nhóm
giống nhau thì dựa vào 2 ñiểm giống nhau nhất ở 2 nhóm khác nhau.
o Ưu ñiểm của phương pháp kết nhóm MAX: Ít ảnh hưởng nhiễu và tác ñộng
bên ngoài
o Khuyết ñiểm: ðịnh hướng ñể phân nhỏ nhóm lớn. Biến nhóm thành dạng
hình cầu
 Trung bình nhóm:
o Xấp xỉ của 2 nhóm là giá trị trung bình xấp xỉ của một cặp các ñiểm trong 2
nhóm


 

 





a. Neural sinh học
Mạng neural sinh học bao gồm các thành phần
o Nhánh và rễ: ðây là bộ phận tiếp nhận thông tin của tế bào neural.
o Thân thần kinh: Thân thần kinh chứa các nhân và cơ quan tổng hợp protein.
o Dây thần kinh: ðây là phương tiện truyền dẫn tín hiệu giữa các neural.
o Khớp thần kinh: Là bộ phận tiếp xúc của ñầu ra neural với nhánh, rễ của các
neural khác

Hình 6.23 Cấu tạo mạng neural sinh học

Chương 6: Nhận Dạng Ảnh

192
b. Neural nhân tạo
 Khái niệm mạng neural nhân tạo
Các neural sinh học liên kết với nhau thành lớp tạo thành mạng neural sinh
học. Neural nhân tạo là sự mô phỏng neural sinh học. Có nhiều cách kết hợp các
neural nhân tạo thành mạng, mỗi cách kết hợp tạo thành một lớp mạng neural
nhân tạo khác nhau.

Hình 6.24 Cấu tạo mạng neural nhân tạo
 Phân loại mạng neural nhân tạo
Có nhiều cách ñể phân loại mạng neural nhân tạo, tùy theo tiêu chí ñề ra:
o Dựa vào số lượng lớp có trong mạng, ta phân thành:
+ Mạng một lớp
+ Mạng nhiều lớp
o Dựa vào ñường truyền tín hiệu trong mạng, ta phân thành:

(6.14)

o v(t): Tổng tất cả các ñầu vào mô tả toàn bộ thế năng tác ñộng ở thân neural.
o x
k
(t): Các ñầu vào từ bên ngoài; với k là chỉ số chạy, k=1,2…m.
o m: Số lượng ñầu vào mô tả tín hiệu vào từ các ñầu nhạy thần kinh hoặc các
neural khác.
o w
k
: Trọng tâm liên kết ngoài giữa các ñầu vào k tới neural hiện tại.
o y(t): Tín hiệu ñầu ra neural.
o θ: Ngưỡng (là hằng số), xác ñịnh ngưỡng kích thích hay ức chế.

Chương 6: Nhận Dạng Ảnh

194
 Bộ ñộng học tuyến tính
ðầu vào của phần ñộng học tuyến tính là v(t), ñầu ra của nó là u(t) gọi là
ñầu ra tương tự. Hàm truyền tương ứng của phần ñộng học tuyến tính có thể mô
tả dưới dạng:
( )
(
)
( )
( ) ( ) ( )
sVsHsUhay

Khái niệm học trong mạng neural ñược hiểu theo hai nghĩa: Học về cấu trúc
và học về tham số.
o Học tham số (Parameter Learning)
Mục tiêu của việc học tham số là thay ñổi, cập nhật các trọng số liên kết.
Hầu hết các luật học tồn tại thuộc kiểu học tham số. Các kiểu học ñiển hình mà
chúng ta sẽ nghiên cứu trong phần trên cũng thuộc dạng học tham số. Thông
thường, luật học tham số ñược chia thành ba dạng chính, ñó là: Học giám sát, học
không giám sát và học củng cố.
o Học có thầy (Học giám sát) Supervised Learning:
Với kiểu học này, tại mỗi thời ñiểm có ñầu vào mạng neural thì ñầu ra
mong muốn của hệ sẽ ñược cho sẵn. Có thể cụ thể hóa như sau: Mạng ñược cung
cấp một tập các mẫu (x(1),d(1)), (x(2),d(2)),… (x(n),d(n)) là các cặp ñầu vào –
ñầu ra mong muốn.