BỘ GIÁO DỤC & ĐÀO TẠO
BỘ GIÁO DỤC & ĐÀO TẠO
ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐÀO TẠO SAU ĐẠI HỌC

TIỂU LUẬN MÔN HỌC
Đề 13: 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ữ.
GVHD: PGS.TS. Nguyễn Thị Hoàng Lan
Học viên: Hoàng Văn Hải
Nguyễn Văn Dũng
Trần Đình Phương
Lớp: CH-12BMTT

Hà nội, 12/2012
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
MỞ ĐẦU
Được sự phân công của ban cán sự lớp, 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). Trong phạm vi của tiểu luận này, với những kiến thức đã được học
cũng như tự nghiên cứu thêm tài liệu từ các giáo trình, bài giảng và mạng Internet,
chúng tôi xin trình bày các nội dung sau:
Phần 1: Sơ lược về nhận dạng
Phần 2: 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ữ, hình học, ảnh nhị phân,…).
Phần 3: 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ữ (phương thức đồ thị, chuỗi).
Cho dù đã hết sức cố gắng, nhưng do điều kiện thời gian và khả năng còn

, , x
n
}; mỗi x
i
biểu diễn một đặc tính. Không gian biểu diễn đối
tượng thường gọi tắt là không gian đối tượng X được định nghĩa:
X = {X
1
, X
2
, , X
m
}
trong đó mỗi X
i
biểu diễn một đối tượng. Không gian này có thể là vô hạn. Để
tiện xem xét chúng ta chỉ xét tập X là hữu hạn.
b) 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. 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 là đã nhận dạng được đối tượng. Một cách hình thức gọi
Ω
là tập tên đối
tượng:

Ω
= {w
1
, w
2

Phương pháp này xây dựng mô tả thứ bậc các mô hình phức tạp từ các yếu tố
nguyên thủy đơn giản. Để mô tả đối tượng, người ta dùng một số dạng nguyên
thuỷ như đoạn thẳng, cung,…
Chẳng hạn một hình chữ nhật được định nghĩa gồm 4 đoạn thẳng vuông góc với
nhau từng đôi một. Trong mô hình này người ta sử dụng một bộ kí hiệu kết thúc
V
t
, một bộ kí hiệu không kết thúc gọi là V
n
. Ngoài ra có dùng một tập các luật sản
xuất để mô tả cách xây dựng các đối tượng phù hợp dựa trên các đối tượng đơn
giản hơn hoặc đối tượng nguyên thuỷ (tập V
t
). Trong cách tiếp cận này, ta chấp
nhận một khẳng đinh là: cấu trúc một dạng là kết quả của việc áp dụng luật sản
xuất theo theo những nguyên tắc xác định bắt đầu từ một dạng gốc bắt đầu. Một
cách hình thức, ta có thể coi mô hình này tương đương một văn phạm G = (V
t
, V
n
,
P, S) với:
- V
t
là bộ ký hiệu kết thúc,
- V
n
là bộ ký hiệu không kết thúc,
- P là luật sản xuất,
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 4

- Các ký tự: Mỗi câu bao gồm một chuỗi ký tự (hay biểu tượng nguyên thủy,
biểu tượng kết thúc) từ bảng chữ cái.
- Các biến: Là (ký hiệu) biểu tượng không kết thúc (hoặc biểu tượng trung
gian, biểu tượng nội bộ).
- Biểu tượng gốc: Là một biến đặc biệt, là gốc cho tất cả các chuỗi.
- Luật sinh: là các quy tắc sinh (hoặc viết lại quy tắc) để xác định chuyển đổi
một tập hợp các biến và biểu tượng vào các biến và biểu tượng khác.
Ví dụ, nếu A là biến và c là ký hiệu kết thúc, quy tắc cA -> cc nghĩa là bất kỳ
thời điểm nào phân khúc cA xuất hiện trong chuỗi có thể được thay thế bởi cc.
Ngôn ngữ L(G) được tạo ra bởi một văn phạm G là tập hợp tất cả các chuỗi (có
thể là số vô hạn) có thể được tạo ra bởi G.
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 6
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
Hình 2: Cây trên minh họa một câu tiếng Anh được tạo ra bởi văn phạm.
Một vài đặc điểm của phương thức nhận dạng theo cú pháp và cấu trúc như
sau:
+ Các mẫu được phân tách thành các mẫu nhỏ dựa trên mối quan hệ.
+ Các mẫu được hình thành bởi các mẫu nhỏ hơn được phân cấp.
+ Các lớp khác nhau có các mẫu nhỏ khác nhau, quy luật giữa các mẫu nhỏ
khác nhau có thể khác với các lớp khác nhau.
Ví dụ cho một mẫu nhận dạng:
Hình 3 – Phân tích nhận dạng cú pháp một khuông nhạc
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 7
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
Như vậy, đối tượng cần nhận dạng X được miêu tả bởi xâu chuỗi, đồ thị hoặc
văn phạm. Ta có cấu trúc văn phạm G dựa trên bộ tứ G = (V
N
, V
T
, P, S), V

2
, γ = ω
1
β ω
2
, và
có tồn tại một quy tắc sinh α → β.
• có nghĩa là η gián tiếp tạo ra câu γ, tức là, có tồn tại một chuỗi các
câu ς
1
. . . , ς
n
để η = ς
1
, γ = ς
n
, và ς
i
⇒ ς
i
+1, i = 1,. . . , n - 1. Các câu ς
1
,. . . , ς
n
được
gọi là nguồn gốc của γ từ η.
Nếu G là một cấu trúc văn phạm, khi đó
là một cụm từ có cấu trúc được tạo ra bởi văn phạm.
Một ngôn ngữ có thể có nhiều cách đặc tả, do đó cũng có thể có nhiều văn
phạm khác nhau sinh ra cùng một ngôn ngữ. Hai văn phạm sinh ra cùng một ngôn

Loại 3: (văn phạm chính quy RG): Nếu văn phạm G có luật sinh dạng tuyến
tính: α → zβ hoặc α → βz hoặc α → z với α,β là các biến trung gian và z là chuỗi
ký hiệu kết thúc (có thể là rỗng).
Lớp của văn phạm kiểu i bao gồm tất cả văn phạm kiểu i + 1.
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 9
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
2.3 Nhận dạng sử dụng cấu trúc văn phạm
Giả sử có một câu x được tạo bởi ngôn ngữ c có các mẫu hoặc lớp khác nhau.
Câu x được phân loại theo ngữ pháp đã sinh nó, x là một thành viên của ngôn ngữ
L(G
i
).
Phân tích cú pháp là quá trinh xử lý ngược, cho x cụ thể, tìm một dẫn xuất
trong G, dẫn đến x.
Phân tích cú pháp từ dưới lên bắt đầu với câu x, và tìm cách đơn giản nó, coi
nó là biểu tượng gốc. Phương pháp tiếp cận cơ bản là sử dụng các luật sinh trở về
trước, tức là tìm viết lại quy tắc bên phải của chuỗi hiện tại, và thay thế nó với một
phân khúc.
Phân tích cú pháp từ trên xuống bắt đầu với nút gốc và liên tục áp dụng luật
sinh để tìm gốc của câu x. Từ đó xác định được quy tắc sinh.
2.4 Ngôn ngữ mô tả hình ảnh sử dụng nhận dạng cấu trúc văn phạm
Hình 5: Sử dụng ngôn ngữ mô tả hình ảnh (PDL) để nhận dạng cấu trúc văn 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.
Trong hình trên:
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.
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 10
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan

Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 13
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
PHẦN 3: SO SÁNH CHẤT LƯỢNG VÀ HIỆU NĂNG NHẬN
DẠNG VỚI PHƯƠNG PHÁP KHÁC ĐỂ NHẬN DẠNG CHỮ.
3.1 Phương pháp suy luận
Trong nhiều ứng dụng, ngữ pháp được thiết kế bằng tay. Một phương pháp
khác là học ngữ pháp từ các mẫu có sẵn. Việc học này được gọi là phương pháp
suy luận.
Dữ liệu huấn luyện thiết lập 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
ngữ pháp
để 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.
Ngoài ra, các mẫu huấn luyện có thể được "ngoại suy". Nếu:
S+={ab, aabb, aaabbb, aaaabbbb}
Có thể được phát biểu rằng:
L(Glearn) ={anbn|n≥1} và P={S→ab, S→aSb}.
Một văn phạm chính quy có thể được hình thành bằng cách sử dụng một dữ
liệu huấn luyện theo cách sau.
• S + và S- được cho là có sẵn.
• Khởi tạo ngữ pháp G

• Xem tập huấn luyện x
(i)
S∈
+
. Nếu có có thể được phân tích và chỉnh sửa
G
learn
để nó có thể phân tích được và không có x S∈
-
có thể được phân tích.
• Nếu i < |S
+
|, đặt i = i + 1 và quay lại bước trước đó, nếu không thì thoát.
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 14
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
Một điểm yếu rõ ràng về thủ tục là đặc điểm kỹ thuật của quy tắc chỉnh sửa
thích hợp cho P, V
N
, V
T
là khó khăn.Hơn nữa, nếu các quy định là không duy nhất,
số lượng G
learn
ngữ pháp có thể phát triển nhanh chóng.
3.2 Nhận dạng dựa vào đồ thị.
Một đồ thị có hướng có thể được sử dụng để đại diện cho phụ thuộc phức tạp
hơn giữa các nguyên thủy (biểu tượng) hơn bằng cách sử dụng các chuỗi biểu
tượng một chiều. Như vậy, so sánh các mẫu đại diện sử dụng đồ thị có thể được
nhìn thấy trong một cảm giác như là một sự tổng quát so sánh các chuỗi biểu
tượng.

cho mỗi đỉnh của N2 tồn tại chính xác một đỉnh tương ứng trong N1 (song ánh),
sao cho (v1, w1)∈R1⇔(f(v1), f(w1))∈R2
Nói cách khác, G2 thu được từ G1 bằng cách đánh lại chỉ số các đỉnh.
Ví dụ về đồ thị đẳng cấu:
Hình 12: Một ví dụ về đẳng cấu của hai đồ thị vô hướng với p = 4
Trong thực tế đẳng cấu của đồ thị không phải là một biện pháp tốt tương tự
trong việc phân loại, bởi vì nó không cho phép bất kỳ sự khác biệt nào giữa đồ
thị.Vì thế, rất nhạy cảm với các sai sót trong giai đoạn khai thác tính năng. Ngoài
ra, phát hiện của phép đẳng cấu giữa đồ thị tính toán rất đòi hỏi:
• Xem xét so sánh các đồ thị G1 và G2 biểu diễn bằng cách sử dụng ma trận
kề M1 và M2.
• Nếu M1 = M2 đồ thị đẳng cấu. Sự so sánh này cần được thực hiện cho tất cả
các yếu tố của một ma trận p × p (O (| N1 | 2)).
• Nếu M1 != M2, có thể tất cả các cách khác để đánh chỉ số đỉnh M1 phải
được cố gắng thực hiện.
Thông thường, kiểm tra thất bại nếu đồ thị không đẳng cấu được sử dụng.Các
tính chất đồ thị dưới đây là bất biến để đẳng cấu:
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 16
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
• Số đỉnh (loại nhất định).
• Số cạnh (loại nhất định).
• Số cạnh (loại nhất định) kết nối với đỉnh (của một số loại).
Có tồn tại nhiều thuật toán để cho phép so sánh sự khác biệt giữa các đồ thị.
Hai cách tiếp cận điển hình là:
• Vectơ tính năng được xây dựng cho các biểu đồ và các vectơ được so sánh.
• Số lượng các phép toán tối thiểu cần thiết để sửa đổi một đồ thị khác được
sử dụng như một biện pháp thay thế.
o Chèn và loại bỏ các đỉnh.
o Kết hợp và chia tách các đỉnh
o Thay đổi loại của các đỉnh.

Trong quá trình phân tích cú pháp, các quy tắc được lựa chọn tại các nút
con.Tuy nhiên, lựa chọn của một số quy tắc có thể dẫn đến phân tích cú pháp
không thành công mặc dù chuỗi thuộc vào ngôn ngữ. Trong trường hợp đó, người
ta phải trở về điểm bị sai và chọn quy tắc khác. Điều này được gọi là quay lại.
Phân tích cú pháp có thể dung phương pháp top-down hoặc bottom-up
Phân tích kiểu top-down (từ trên xuống)
• Phân tích cú pháp bắt đầu từ những kí tự gốc.
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 18
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan

• 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 →
X1’X2’. . . Xn’ được thử.
• Các subgoals có thể được tiếp tục phân hủy thành subgoals.
• Nếu một số của subgoals không thể đạt được, phân tích cú pháp trả về với
mức độ cao hơn và một phân rã mới được thực hiện.
• Căn cứ từ trái sang phải cùng với quá trình đệ quy.
Một form → Aα có thể sinh ra vòng lặp vô hạn trong phân tích cú pháp. Cần
phải tránh điều này nếu có thể.
• Một cách kiểm tra hiệu quả lựa chọn của subgoals: hãy chắc chắn rằng khi
chưa xử lý, kí tự tận cùng bên trái không thể phân rã được thành subgoals.
Hình 15: Ví dụ phân tích kiểu top-down
Phân tích kiểu bottom – up
Phân tích cú pháp bắt đầu từ toàn bộ cấu trúc của x.
• Các quy tắc tính được áp dụng "ngược".

chuỗi thời gian (ví dụ, khoảng cách Euclide),

Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 20
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
Dynamic Time Warping thuật toán (DTW) có thể được sử dụng.
DTW là thuật toán kết nối các điểm của hai chuỗi thời gian tổng hợp của các
chi phí trên tất cả các cặp điểm càng nhỏ càng tốt.
• Hãy xét r(i), i = 1,. . . , I, và t(j), j = 1,. . . , J thành hai chuỗi thời gian.
Thường I = J.
• Xác định một điểm lưới hai chiều (i, j) tương ứng để kết nối các điểm r (i) và
t (j) của chuỗi thời gian.
• Kết nối các điểm của hai chuỗi thời gian có thể được biểu bằng cách sử dụng
đường dẫn sau đây: (i0, j0), (i1, j1). . . , (if, jf).
Đối với mỗi con đường, có tồn tại một tổng chi phí
trong đó K là số lượng các kết nối (chiều dài của con đường), và d (ik, jk) (d
(ik, jk | ik-1, jk-1)) là chi phí kết nối các điểm r (ik) và t (jk) khi chi phí của các kết
nối trước đó được thực hiện.
Thuật toán DTW được dựa trên các nguyên tắc tối ưu Bellman
Ký hiệu đường đi tối ưu bằng cách

• Đi qua con đường tối ưu thông qua các điểm (i, j) được ký hiệu là

• Theo nguyên tắc tối ưu
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 21
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan

Với ⊕ biểu thị nối của đường dẫn.
• Như vậy, đường đi tối ưu có thể được tính đệ quy:
(Nếu tổng chi phí là sản phẩm của chi phí, thay thế tổng hợp theo sản phẩm.)
Thuật toán DTW đã được sử dụng rộng rãi trong công nhận bài phát biểu và

đồ thị, và chuỗi ký tự với phương pháp nhận dạng chữ dựa vào cấu trúc.
Mặc dù đã hết sức cố gắng, nhưng do điều kiện thời gian và khả năng kiến
thức còn nhiều hạn chế nên chắc chắn không thể không tránh khỏi những sai sót và
khiếm khuyết, tiểu luận mới chỉ mang tính chất mở rộng kiến thức về nhận dạng
cấu trúc văn phạm chứ chưa mang tính chất chuyên sâu.
Rất mong nhận được sự góp ý, phê bình, đánh giá của PGS.TS và của các bạn
trong lớp để nhóm chúng tôi rút kinh nghiệm và hoàn thiện tốt hơn, nghiên cứu
chuyên sâu hơn trong thời gian tới.
Chúng tôi xin gửi lời cảm ơn chân thành đến PGS.TS Nguyễn Thị Hoàng Lan
đã giảng dạy kiến thức, cung cấp tài liệu, định hướng và hướng dẫn chúng tôi trong
suốt thời gian qua để nhóm chúng tôi hoàn thành tiểu luận này.
Mọi sự đóng góp và phê bình xin gửi về:
1. Hoàng Văn Hải, Tổng cục An ninh I – Bộ Công an.
Địa chỉ: 44 Yết Kiêu, P.Trần Hưng Đạo, Q.Hoàn Kiếm, TP.Hà Nội
Điện thoại: 0916.286.256
Email:ithoanghai @ gmail.com
2. Nguyễn Văn Dũng.
Địa chỉ:
Điện thoại: 0948.128.086
Email:[email protected]
3. Trần Đình Phương.
Địa chỉ:
Điện thoại: 0166.657.9501
Email:[email protected]
Hà Nội, ngày 20 tháng 12 năm 2012
Nhóm 13: Hoàng Văn Hải – Nguyễn Văn Dũng – Trần Đình Phương Trang 24
Tiểu luận môn học: Nhận dạng GVHD: PGS. TS. Nguyễn Thị Hoàng Lan
Thay mặt nhóm
Hoàng Văn Hải
TÀI LIỆU THAM KHẢO