CHƯƠNG 7
NHẬN DẠNG ẢNH
IMAGE RECOGNITION
IMAGE RECOGNITION
TRẦN THANH LƯƠNG
Khoa Công nghệ Thông tin
Trường Đại học Khoa học Huế
Email:
Website: />2
2
NỘI DUNG BÀI GiẢNG

Tổng quan về nhận dạng ảnh

Không gian biểu diễn đối tượng

Không gian diễn dịch

Mô hình nhận dạng

Phân hoạch không gian

Hàm phân lớp hay hàm ra quyết định

Một số thuật toán nhận dạng
3
3
TỔNG QUAN VỀ NHẬN DẠNG

Nhận dạng là quá trình phân loại các đối tượng đã
được biểu diễn theo một mô hình nào đó và gán chúng

vào một lớp dựa theo những quy luật vá các mẫu
chuẩn.

Quá trình nhận dạng ảnh có thể chia thành 4 mức ứng
với 4 giai đoạn liên tiếp nhau như sau:
–
Thu nhận
–
Tiền xử lý và trích chọn đặc trưng
–
Nhận dạng
–
Phân tích, giải thích, hiểu
4
4
KHÔNG GIAN BIỂU DIỄN ĐỐI TƯỢNG

Các đối tượng khi quan sát hay thu thập được
biểu diễn bởi tập các đặc trưng.

Các đặc trưng thương sử dụng như: Biên,
vùng, miền đồng nhất…

Người ta phân các đặc trưng này thành từng
loại như: đặc trưng tôpô, đặc trưng hình học,
đặc trưng về chức năng…
5
5
KHÔNG GIAN BIỂU DIỄN ĐỐI TƯỢNG


Giả sử đối tượng X (hình ảnh, chữ viết, dấu vân
tay…) được biểu diễn bởi n đặc trưng. Khi đó ta
ký hiệu: X = {x
1
, x
2
, …, x
n
}; mỗi x
i
biểu diễn một
đặc tính nào đó.

Không gian biểu diễn các đối tượng được gọi là
không gian đối tượng, được ký hiệu:
χ = {X
1
, X
2
, …, X
m
}
trong đó mỗi X
i
biểu diễn một đối tượng.

χ có thể là vô hạn hoặc hữu hạn.
6
6
KHÔNG GIAN DIỄN DỊCH


Không gian diễn dịch là tập các tên gọi của đối
tượng. Đây là một tập hữu hạn.
Ω = {w
1
, w
2
, …, w
k
}, w
i
, i=1, 2, …, k là tên các đối tượng.

Kết thúc quá trình nhận dạng, ta xác định được
tên gọi cho các đối tượng trong tập không gian
đối tượng hay nói cách khác là đã nhận dạng
được đối tượng.
7
7
KHÔNG GIAN DIỄN DỊCH

Quá trình nhận dạng đối tượng là quá trình ánh
xạ từ không gian biểu diễn đối tượng vào không
gian diễn dịch. Đó là một hàm f : χ → Ω.

Quá trình ánh xạ này biến một đối tượng trong χ
thành một đối tượng trong Ω.

Ví dụ: Nhận dạng chữ cái (A Z). Tập χ là các ký
tự viết tay. Ω là các ký tự {A,B,…, Z}

8
8
MÔ HÌNH NHẬN DẠNG

Trong nhận dạng người ta chia ra làm hai họ lớn:
–
Họ mô tả theo tham số
–
Họ mô tả theo cấu trúc

Tương ứng với hai mô hình:
–
Mô hình nhận dạng theo tham số
–
Mô hình nhận dạng theo cấu trúc
9
9
MÔ HÌNH NHẬN DẠNG

Mô hình nhận dạng theo tham số:
–
Sử dụng vectơ để biểu diễn, đặc tả đối tượng.
–
Mỗi phần tử của vectơ đặc tả một tính chất của đối
tượng.
–
Việc lựa chọn các phương pháp biểu diễn sẽ làm đơn
giản cách xây dựng hàm ánh xạ nhận dạng.
10
10

MÔ HÌNH NHẬN DẠNG

Ví dụ: Trong nhận dạng chữ người ta sử dụng
các tham số như:
–
Số điểm chạc ba, chạc tư.
–
Số điểm chu trình.
–
Số điểm ngoặt.
–
Số điểm kết thúc.

Hình chữ t ở trên có 4 điểm kết thúc.
11
11
MÔ HÌNH NHẬN DẠNG

Mô hình nhận dạng theo cấu trúc:
–
Dựa vào việc mô tả đối tượng thông qua đoạn thẳng,
cung, …
–
Sử dụng các văn phạm để xác định cấu trúc.

Bản chất của quá trình nhận dạng:
–
Lựa chọn mô hình biểu diễn đối tượng.
–
Lựa chọn luật ra quyết định và suy diễn quá trình học.

–
Học nhận dạng.
12
12
Nhận dạng là quá trình tìm ra các
quy luật, thuật toán để có thể gán
đối tượng vào một lớp hay nói cách
khác gán đối tượng với một tên.
13
13
NHẬN DẠNG DỰA TRÊN
PHÂN HOẠCH KHÔNG GIAN

Phân hoạch không gian

Hàm phân lớp hay hàm ra quyết định

Một số thuật toán nhận dạng
14
14
PHÂN HOẠCH KHÔNG GIAN

Không gian biểu diễn đối tượng:
χ = {X
i
, i=1, 2, 3,…, m}
trong đó X
i
là một véctơ. X
i

= {w
i1
, w
i2
, …, w
in
}

Gọi P là một phân hoặch của không gian χ thành
các lớp C
i
nếu thỏa hai điều kiện sau:
–
C
i
∩ C
j
= ∅, ∀ i ≠ j

∪ C
i
= χ

Xây dựng ánh xạ f: χ → P (công cụ là các hàm
phân lớp)
15
15
HÀM PHÂN LỚP hay
HÀM RA QUYẾT ĐỊNH


Để phân các đối tượng vào các lớp, ta phải xác
định số lớp và ranh giới giữa các lớp đó.

Để làm được điều đó chúng ta phải xây dựng các
hàm phân lớp.

Gọi {g
i
} là lớp các hàm phân lớp. Lớp này được
định nghĩa như sau:
Với đối tượng X, g
k
{X} > g
i
{X}, ∀ i ≠ k thì X thuộc lớp k
16
16
HÀM PHÂN LỚP hay
HÀM RA QUYẾT ĐỊNH

Hàm phân lớp g của một lớp nào đó thường là
hàm tuyến tính. Nghĩa là:
g(X) = w
0
+ w
1
X
1
+ w
2

X
2
+ … + w
n
X
n
trong đó w
i
là trọng số gán cho thành phần X
i
.

Hàm phân lớp này là một siêu phẳng.
17
17
HÀM PHÂN LỚP hay
HÀM RA QUYẾT ĐỊNH

Khoảng cách là một công cụ để xác định xem hai
đối tượng có giống nhau hay không.

Nếu hai đối tượng có khoảng cách nhỏ hơn một
giá trị θ nào đó thì ta nói rằng hai đối tượng này
giống nhau và thuộc cùng một lớp. Ngược lại ta
bảo hai đối tượng này khác nhau và thuộc vào
hai lớp.

Việc xây dựng hàm khảng cách tùy thuộc vào
từng bài toán cụ thể.
18

18
MỘT SỐ THUẬT TOÁN NHẬN DẠNG

Thuật toán K-Mean (K-Trung bình)

Thuật toán dựa Maximin
19
19
THUẬT TOÁN K-MEAN

Vào:
–
Tập m đối tượng X
1
, X
2
, …, X
m
.
–
Số lượng nhóm cần phân loại: K

Ra:
–
K tập phân loại khác nhau, C
1
, C
2
, …, C
k

.
20
20
THUẬT TOÁN K-MEAN

Phương pháp:
1. Cho n = 1, chọn K phần tử bất kỳ X
1
, X
2
, …, X
k
làm hạt
nhân tương ứng với K lớp C
1
, C
2
, …, C
k
. Tâm của K lớp
này là Z
1
(n) = X
1
, Z
2
(n) = X
2
, …, Z
K

(n) = X
K
.
2. Phân lớp cho K nhóm theo nguyên tắc khoảng cách
cực tiểu. Xét phân tử X
i
(i=1, 2,…, m), X
i
sẽ thuộc lớp
C
j
nếu khoảng cách từ X
i
đến tâm của lớp C
j
là nhỏ
nhất. Nghĩa là:
D(X
i
, Z
j
(n)) ≤ D(X
i
, Z
p
(n)), ∀ p ≠ j, p = 1, 2, …, m.
21
21
THUẬT TOÁN K-MEAN


Phương pháp:
3. n = n + 1.
4. Tính lại tâm của các lớp C
1
, C
2
, …, C
k
tương ứng là
Z
1
(n), Z
2
(n), …, Z
k
(n) theo công thức:
5. Nếu Z
j
(n) = Z
j
(n-1), ∀j = 1, 2, …, m thì dừng. Ngược
lại, quay lại bước 2.
mjX
CCard
nZ
jp
CX
p
j
j

, ,2,1,
)(
1
)(
==
∑
∈
22
22
VÍ DỤ THUẬT TOÁN K-MEAN

Cho tập gồm 12 đối tượng:
X
1
= (1, 1), X
2
= (2, 1), X
3
= (1, 2), X
4
= (5, 1),
X
5
= (5, 2), X
6
= (6, 1), X
7
= (6, 2), X
8
= (3, 5),

X
9
= (3, 6), X
10
= (4, 6), X
11
= (8, 5), X
12
= (8, 6).

Số lớp cần phân là 4.

Hãy phân lớp tập các đối tượng trên theo thuật
toán K-Mean.
23
23
VÍ DỤ THUẬT TOÁN K-MEAN
1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8 9 10
X
1
= (1, 1), X
2

= (2, 1),
X
3
= (1, 2), X
4
= (5, 1),
X
5
= (5, 2), X
6
= (6, 1),
X
7
= (6, 2), X
8
= (3, 5),
X
9
= (3, 6), X
10
= (4, 6),
X
11
= (8, 5), X
12
= (8, 6).
24
24
THUẬT TOÁN MAXIMIN


Vào:
–
Tập m đối tượng X
1
, X
2
, …, X
m
.
–
Ngưỡng phân loại θ

Ra:
–
N tập phân loại khác nhau, C
1
, C
2
, …, C
n
.
25
25
THUẬT TOÁN MAXIMIN

Phương pháp:
1. Cho n = 1, chọn một điểm X bất kỳ làm lớp C
1
. Gọi Z
1

là
tâm của lớp C
1
.
2. Tính khoảng cách D
j1
= D(X
j
, Z
1
), j = 1, 2, …, m.
3. Tìm k sao cho: D
k1
= max{D
j1
}, j = 1, 2, …, m.
4. n = n + 1.
5. Lập nhóm C
n
chứa phân tử X
k
. Tính khoảng cách từ
các tâm thu được đến các điểm còn lại:
d
kj
= D(Z
k
, X
j
), k = 1, 2, …, n, j = 1, 2, …, m.