ĐẠI HỌC BÁCH KHOA
TÊN ĐỀ TÀI: (ĐỀ 13)
TÊN ĐỀ TÀI: (ĐỀ 13)
Hà Nội, tháng 12 năm 2012
GVHD: PGS.TS. Nguyễn Thị Hoàng Lan
Trình bày: Nhóm 13
Hoàng Văn Hải
Nguyễn Văn Dũng
Trần Đình Phương
Lớp: CH12BMTT
Tìm hiểu ứng dụng phương pháp nhận dạng
cấu trúc văn phạm trong nhận dạng
NỘI DUNG TRÌNH BÀY

TÌM HIỂU ỨNG DỤNG PHƯƠNG PHÁP NHẬN DẠNG
CẤU TRÚC VĂN PHẠM

PHƯƠNG THỨC NHẬN DẠNG ĐỒ THỊ VÀ NHẬN DẠNG
CHUỖI
GIỚI THIỆU

Được sự phân công, nhóm thực hiện đề tài: Tìm hiểu ứng
dụng phương pháp nhận dạng cấu trúc văn phạm trong
nhận dạng (nhận dạng chữ,…) và so sánh chất lượng và
hiệu năng với phương pháp khác để nhận dạng chữ. (Đề
13)

Điều kiện thời gian, khả năng còn nhiều hạn chế, nội dung
tiểu luận là một lĩnh vực tri thức rộng lớn, đa dạng và rất
phức tạp nên không tránh khỏi những sai sót và khiếm
khuyết. Rất mong nhận được sự góp ý, phê bình, đánh giá

/?@/)2>"*1A2%
<
=2;B-"#12>""*-C2>
)2>+2+1%
<
&>:;B+2C2):$%
<
B' D;   ./ 0 D -C   ./ 01 > 3 4
/> E + '   2  2>   2 
2>"%
PHƯƠNG PHÁP NHẬN DẠNG CẤU TRÚC VĂN PHẠM

Ngôn ngữ hình thức
Bằng cách áp đặt một số quy tắc hạn chế trên các luật sinh, Noam
Chomsky đề nghị một hệ thống phân loại các văn phạm dựa vào tính chất
các luật sinh. Hệ thống này cho phép xây dựng các bộ nhận dạng hiệu
quả và tương thích với từng loại văn phạm. Ta có 4 loại văn phạm như
sau:

Loại 0: (Văn phạm phi ngữ cảnh hay không hạn chế): Văn phạm
không cần thỏa mãn bất kỳ ràng buộc trên các luật sinh hay quy tắc nào.

Loại 1:(văn phạm cảm ngữ cảnh CSG): Nếu văn phạm G có luật sinh
dạng αIβ → αxβ. Trong đó α,β là một chuỗi bất kỳ chứa biến trung gian
hoặc biểu tượng kết thúc, I là biến trung gian, x là biến trung gian hoặc
biểu tượng kết thúc.

Loại 2: (văn phạm phi ngữ cảnh CFG): Nếu văn phạm G có luật sinh
dạng A α với A là một biến trung gian và α là một chuỗi ký hiệu kết →
thúc hoặc biến trung gian V∈

phạm

Ngôn ngữ mô tả hình ảnh (PDL) là một cách thức đầu tiên để mô
tả các mẫu hình ảnh sử dụng ngôn ngữ hình thức.

Các ký hiệu (biểu tượng) kết thúc: {t, b, u, o, s, *, - , +}; + đại
diện cho 2 vector nối đuôi nhau, * đại diện cho 2 vector cùng điểm
bắt đầu, và - đại diện đảo ngược vector. H đại diện cho cuối vector
và T đại diện cho đầu vector.
Phương pháp suy luận

- Là phương pháp học từ các mẫu có sẵn.

- Dữ liệu huấn luyện H có thể bao gồm mẫu tích cực S+ và
mẫu tiêu cực S-, có nghĩa là, H = {S
+
, S
-
}.Mục đích là để
học một ngữ pháp G-
learn
để mẫu trong S
+
thuộc về ngôn ngữ
được xác định bởi ngữ pháp, và các mẫu trong S
-
thì không.

F
5

VT = {I, +, *}, I {a, b, c}, và∈

P={S T, T T I, S S+T, T I}.→ → ∗ → →



Một chuỗi biểu tượng x = a * b + c * a + b thuộc ngôn ngữ L (G)



Vì có thể được phân tích cú pháp theo cách sau đây
Phương pháp top-down

• Phân tích cú pháp bắt đầu từ những kí tự gốc.

• S được phân rã thành một phần (subgoals): S X1X2. . . Xn.→

• Nếu X1 là một kí tự có thể phân rã, nó có phải là kí tự đầu tiên trong
chuỗi x được phân tích.

• Nếu X1 là một biểu tượng không thể phân rã, nó cần được đưa vào phần
của x tương ứng với nó.

• Nếu X1 có thể được phân tích thành công thì sẽ đến X2 và tiếp tục

• Nếu một số Xi không thể được phân tích cú pháp, phân tách mới ban
đầu với X1’X2’. . . Xn’ mới

Các subgoals có thể được tiếp tục phân hủy thành subgoals.



T5NL73,/(!2>95N
DD

U:X:> >DGE+94
"DG(M+2/%
<
=Y2Z[%
<
\[
<
P/E@[%
<
=Y2Z
<
P/E@

- Những khó khăn trong trường hợp đầu là lựa chọn các
tính năng và số liệu phù hợp, cách tiếp cận thứ hai được
tính toán.

TÀI LIỆU THAM KHẢO:

[1] Slide giáo trình giảng dạy môn Nhận dạng, PGS-TS
Nguyễn Thị Hoàng Lan, ĐHBKHN

[2] Pattern recognition: Esa Alhoniemi, Spring 2003

[3] Richard O. Duda, Peter E. Hart, David G. Stork
(2001) Pattern classification (2nd edition), Wiley