BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
o0o

ĐỒ ÁN TỐT NGHIỆP
NGÀNH CÔNG NGHỆ THÔNG TIN HẢI PHÒNG 2013
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
o0o


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
o0o NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP

Sinh viên: Nguyễn Sơn Hà Mã SV: 1351010034
Lớp: CT1301 Ngành: Công nghệ Thông tin
Tên đề tài:Tìm hiểu một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng
chữ viết.
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
CỘNG HÒA XA HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
o0o

NHIỆM VỤ ĐỀ TÀI
1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp
a. Nội dung
- Giới thiệu về trích chọn đặc trƣng:Đặc trƣng bất biến,khả năng khôi phục.
- Trích chọn đặc trƣng từ ảnh đa cấp xám:Đối sánh mẫu,mẫu biến
dạng,biến đổi ảnh Unitar,bất biến hình học,bất biến Zenite.
- Trích chọn đặc trƣng từ ảnh nhị phân:Đối sánh mẫu,mẫu biến dạng,biến
đổi ảnh Unitar,bất biến hình học.
- Trích chọn đặc trƣng từ biên ảnh:Chiếu nghiêng,tách vùng,xấp xỉ đƣờng
cong,mô tả Fourier.

Cán bộ hƣớng dẫn Đ.T.T.N

PGS TS Ngô Quốc Tạo
Hải Phòng, ngày tháng năm 2013
HIỆU TRƢỞNG
GS.TS.NGƯT Trần Hữu Nghị
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301

PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN

1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp:
2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã
đề ra trong nhiệm vụ đề tài tốt nghiệp)


Ngày tháng năm 2013
Cán bộ chấm phản biện
(Ký, ghi rõ họ tên)
LỜI CẢM ƠN

Trƣớc tiên em xin đƣợc bày tỏ sự trân trọng và lòng biết ơn đối với thầy giáo
PGS.TS. Ngô Quốc Tạo- Trƣởng phòng Nhận dạng và Công nghệ tri thức,Viện
Công nghệ thông tin,Viện Hàn Lâm Khoa Học và Công nghệ Việt Nam. Trong suốt
thời gian làm đồ án tốt nghiệp, thầy đã dành rất nhiều thời gian quí báu để tận tình
chỉ bảo, hƣớng dẫn, định hƣớng cho em thực hiện đồ án.
Em xin đƣợc cảm ơn các thầy cô giáo Trƣờng Đại học Dân lập Hải phòng đã
giảng dạy trong quá trình học tập, thực hành, làm bài tập, giúp em hiểu thấu đáo
hơn các nội dung học tập và những hạn chế cần khắc phục trong việc học tập,
nghiên cứu và thực hiện bản đồ án này.
Em xin cảm ơn các bạn bè và nhất là các thành viên trong gia đình đã tạo
mọi điều kiện tốt nhất, động viên, cổ vũ trong suốt quá trình học tập và đồ án tốt
nghiệp.
Do thời gian và kiến thức có hạn nên không tránh khỏi những thiếu sót nhất
định. Em rất mong nhận đƣợc sự đóng góp quý báu của thầy cô!
Em xin chân thành cảm ơn! Hải Phòng, ngày tháng năm 2013.
Sinh viên
Nguyễn Sơn Hà

Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng

2.1.3. Đặc trƣng hình học và hình thái 27
2.2. Đặc trƣng bất biến 28
2.3. Khả năng khôi phục 29
2.4. Trích chọn đặc trƣng từ ảnh đa cấp xám 29
2.4.1. Giới thiệu 29
2.4.2. Đối sánh mẫu 30
2.4.3. Mẫu biến dạng 30
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
2
2.4.4. Biến đổi ảnh Unitar 30
2.4.5. Bất biến Zenite 31
2.5. Trích chọn đặc trƣng từ ảnh nhị phân: 31
2.5.1. Giới thiệu 31
2.5.2. Biến đổi ảnh Unitar 32
2.5.3. Bất biến hình học 32
2.6. Trích chọn đặc trƣng từ biên ảnh: 32
2.6.1. Giới thiệu 32
2.6.2. Tách vùng 32
2.6.3. Xấp xỉ đƣờng cong: 33
2.6.4. Mô tả Fourier: 33
2.7. Trích chọn đặc trƣng từ biểu diễn véc tơ: 33
2.7.1. Giới thiệu 33
2.7.2. Đối sánh mẫu 34
2.7.3. Mẫu biến dạng 34
2.7.4. Đặc trƣng rời rạc 34
2.7.5. Biểu diễn Fourier 34
CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM 36
3.1. Giới thiệu 36
3.2. Xây dựng giao diện vẽ 36

Hình 2.8. Giá trị của các ô vùng khi đƣợc nhận dạng 42
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
4
DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT


k – láng giềng gần nhất
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
5

PHẦN MỞ ĐẦU

Công nghệ thông tin ngày càng phát triển và có vai trò hết sức quan trọng
không thể thiếu trong cuộc sống hiện đại. Con ngƣời ngày càng tạo ra những cỗ
máy thông minh có khả năng tự nhận biết và xử lí đƣợc các công việc một cách tự
động, phục vụ cho lợi ích của con ngƣời. Trong những năm gần đây, một trong
những bài toán nhận đƣợc nhiều sự quan tâm và tốn nhiều công sức nhất của lĩnh
vực công nghệ thông tin, đó chính là bài toán nhận dạng. Tuy mới xuất hiện chƣa
lâu nhƣng nó đã rất đƣợc quan tâm vì tính ứng dụng thực tế của bài toán cũng nhƣ
sự phức tạp của nó.
Nhận dạng chữ viết là một lĩnh vực đã đƣợc quan tâm nghiên cứu và ứng
dụng từ nhiều năm nay theo hai hƣớng chính:
-Nhận dạng chữ in: phục vụ cho công việc tự động hóa đọc tài liệu, tăng tốc
độ và hiệu quả nhập thông tin vào máy tính trực tiếp từ các nguồn tài liệu.
-Nhận dạng chữ viết tay: với những mức độ ràng buộc khác nhau về cách
viết, kiểu chữ phục vụ cho các ứng dụng đọc và xử lý chứng từ, hóa đơn, phiếu
ghi, bản thảo viết tay Nhận dạng chữ viết tay đƣợc tách thành hai hƣớng phát
triển: nhận dạng chữ viết tay trực tuyến (on-line) và nhận dạng chữ viết tay ngoại
tuyến (off-line).
Đến thời điểm này, bài toán nhận dạng chữ in đã đƣợc giải quyết gần nhƣ
trọn vẹn .Tuy nhiên trên thế giới cũng nhƣ ở Việt Nam, bài toán nhận dạng chữ viết
tay vẫn còn là vấn đề thách thức lớn đối với các nhà nghiên cứu. Bài toàn này chƣa
thể giải quyết trọn vẹn vì nó phụ thuộc quá nhiều vào ngƣời viết và sự biến đổi quá
đa dạng trong cách viết và trạng thái tinh thần của từng ngƣời viết. Đặc biệt đối với
việc nghiên cứu nhận dạng chữ viết tiếng Việt lại càng gặp nhiều khó khăn hơn do


Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
7
TÓM TẮT ĐỀ TÀI
Bài báo cáo đồ án tốt nghiệp của em, nghiên cứu về “Một số phƣơng pháp
trích chọn đặc trƣng cho nhận dạng chữ viết”. Nội dung nghiên cứu gồm 3 chƣơng
nhƣ sau:
- CHƢƠNG 1: Tổng quan về chữ viết và lý thuyết nhận dạng
Chƣơng này nghiên cứu tổng quan về chữ viết và lý thuyết nhận dạng.
Nhận dạng chữ là lĩnh vực đƣợc nhiều nhà nghiên cứu quan tâm và cho đến nay lĩnh
vực này cũng đã đạt đƣợc nhiều thành tựu lớn lao cả về mặt lý thuyết lẫn ứng dụng
thực tế.Đồng thời nêu mô hình tổng quát của một hệ nhận dạng chữ viết
- CHƢƠNG 2: Tổng quan về trích chọn đặc trƣng và một số phƣơng pháp
trích chọn đặc trƣng cho nhận dạng chữ viết.
Chƣơng này nghiên cứu tổng quan về trích chọn đặc trƣng và một số
phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết.Giới thiệu về trích chọn
đặc trƣng:Đặc trƣng bất biến,khả năng khôi phục ; trích chọn đặc trƣng từ ảnh đa
cấp xám( Đối sánh mẫu,mẫu biến dạng,biến đổi ảnh Unitar,bất biến hình học,bất
biếnZenite );trích chọn đặc trƣng từ ảnh nhị phân ( Đối sánh mẫu,mẫu biến
dạng,biến đổi ảnh Unitar,bất biến hình học ); trích chọn đặc trƣng từ biên ảnh(

khi cũng có nhiều sự khác biệt trong cách viết tuỳ thuộc vào từng ngữ cảnh, kiểu
viết của một ngƣời cũng có thể thay đổi theo thời gian hoặc theo thói quen Điều
này gây ra nhiều trở ngại trong việc trích chọn đặc trƣng cũng nhƣ lựa chọn mô
hình nhận dạng.
1.2. MÔ HÌNH TỔNG QUÁT CỦA MỘT HỆ NHẬN DẠNG
CHỮ VIẾT TAY
1.2.1. Tiền xử lý
Giai đoạn này góp phần làm tăng độ chính xác phân lớp của hệ thống nhận
dạng, tuy nhiên nó cũng làm cho tốc độ nhận dạng của hệ thống chậm lại. Vì vậy,
tùy thuộc vào chất lƣợng ảnh quét vào của từng văn bản cụ thể để chọn một hoặc
một vài chức năng trong khối này. Nếu cần ƣu tiên tốc độ xử lý và chất lƣợng của
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
9
máy quét tốt thì có thể bỏ qua giai đoạn này. Khối tiền xử lý bao gồm một số chức
năng:
Nhị phân hóa ảnh, lọc nhiễu, chuẩn hóa kích thƣớc ảnh, làm trơn biên chữ,
làm đầy chữ, làm mảnh chữ và xoay văn bản.
1.2.1.1. Nhị phân hóa ảnh
Nhị phân hóa ảnh là một kỹ thuật chuyển ảnh đa cấp xám sang ảnh nhị phân.
Trong bất kỳ bài toán phân tích hoặc nâng cao chất lƣợng ảnh nào, nó cũng cần thiết
để xác định các đối tƣợng quan trọng. Nhị phân hóa ảnh phân chia ảnh thành 2
phần: phần nền và phần chữ. Hầu hết các phƣơng pháp nhị phân hóa ảnh hiện nay
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
10
đều lựa chọn một ngƣỡng thích hợp theo cƣờng độ sáng của ảnh và sau đó chuyển

hình chữ nhật bao quanh ảnh. Thông qua khoảng cách lớn nhất đó, có thể xác định
đƣợc một tỷ lệ co, giãn của ảnh gốc so với kích thƣớc đã xác định, từ đó hiệu chỉnh
kích thƣớc ảnh theo tỷ lệ co, giãn này. Nhƣ vậy, thuật toán chuẩn hóa kích thƣớc
ảnh luôn luôn đảm bảo đƣợc tính cân bằng khi co giãn ảnh, ảnh sẽ không bị biến
dạng hoặc bị lệch.
1.2.1.4. Làm trơn biên chữ:
Đôi khi do chất lƣợng quét ảnh quá xấu, các đƣờng biên của chữ không còn
giữ đƣợc dáng điệu trơn tru ban đầu mà hình thành các đƣờng răng cƣa giả tạo.
Trong các trƣờng hợp này, phải dùng các thuật toán làm trơn biên để khắc phục. (a) (b)
Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi được làm trơn biên.
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
12
1.2.1.5. Làm đầy chữ
Chức năng này đƣợc áp dụng với các ký tự bị đứt nét một cách ngẫu nhiên.
Ảnh đứt nét gây khó khăn cho việc tách chữ, dễ bị nhầm hai phần liên thông của ký
tự thành hai ký tự riêng biệt, tạo nên sai lầm trong quá trình nhận dạng.
1.2.1.6. Làm mảnh chữ
Đây là một bƣớc quan trọng nhằm phát hiện khung xƣơng của ký tự bằng
cách loại bỏ dần các điểm biên ngoài của các nét. Tuy nhiên, quá trình làm mảnh
chữ rất nhạy cảm với việc khử nhiễu. Hình 1.6. Làm mảnh chữ.


Hình 1.8. Tách dòng chữ dựa trên histogram theo chiều ngang của khối chữ

Đối với chữ viết tay thì việc tìm đƣờng phân cách giữa các dòng và các ký tự
trong văn bản thƣờng rất khó khăn. Trong trƣờng hợp này, không thể tìm đƣờng
phân cách theo nghĩa thông thƣờng mà phải hiểu là đƣờng phân cách với số điểm
cắt hai dòng là ít nhất. Khi đó phải xây dựng lƣợc đồ sáng của các dòng chữ, từ đó
các đoạn thấp nhất trên lƣợc đồ chính là đƣờng phân cách cần tìm (hình 1.8 và 1.9).

Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
14

Hình 1.9. Xác định khoảng cách giữa hai kí tự và giữa hai từ dựa trên histogram
theo chiều thẳng đứng của dòng chữ.

1.2.3. Trích chọn đặc trƣng:
Trích chọn đặc trƣng đóng vai trò cực kỳ quan trọng trong một hệ thống
nhận dạng. Trong trƣờng hợp đơn giản nhất, ảnh đa cấp xám hoặc ảnh nhị phân
đƣợc sử dụng cho việc nhận dạng. Tuy nhiên, trong hầu hết các hệ nhận dạng, để
giảm độ phức tạp và tăng độ chính xác của các thuật toán phân lớp thì đòi hỏi các
đặc trƣng đƣợc trích chọn phải rút gọn lại càng nhỏ càng tốt nhƣng vẫn phải đảm
bảo đƣợc thông tin của ký tự. Với mục tiêu này, một tập các đặc trƣng đƣợc trích
chọn cho mỗi lớp sao cho có thể phân biệt đƣợc với các lớp khác.
1.2.4. Huấn luyện và nhận dạng :
Đây là giai đoạn quan trọng nhất, giai đoạn này quyết định độ chính xác của
hệ thống nhận dạng. Có nhiều phƣơng pháp phân lớp khác nhau đƣợc áp dụng cho
các hệ thống nhận dạng chữ viết tay.
1.2.5. Hậu xử lý :
Đây là công đoạn cuối cùng của quá trình nhận dạng. Có thể hiểu hậu xử lý

Các mẫu biến dạng và Đối sánh mềm: Một phƣơng pháp đối sánh khác là sử
dụng các mẫu biến dạng, trong đó một phép biến dạng ảnh đƣợc dùng để đối sánh
một ảnh chƣa biết với một cơ sở dữ liệu ảnh đã biết .
Ý tƣởng cơ bản của đối sánh mềm là đối sánh một cách tối ƣu mẫu chƣa biết
với tất cả các mẫu có thể mà các mẫu này có thể kéo giãn ra hoặc co lại. Chỉ một
không gian đặc trƣng đƣợc thành lập, các véc tơ chƣa biết đƣợc đối sánh bằng cách
sử dụng quy hoạch động và một hàm biến dạng .
Đối sánh giảm nhẹ: Đây là một kỹ thuật đối sánh ảnh ở mức độ tƣợng trƣng,
kỹ thuật này sử dụng hình dáng đặc trƣng cơ bản của ảnh ký tự. Thứ nhất, các vùng
đối sánh đã đƣợc nhận biết. Sau đó, trên cơ sở một số vùng đối sánh đƣợc đánh giá
tốt, các phần tử của ảnh đƣợc so sánh với các vùng đối sánh này. Công việc này đòi
hỏi một kỹ thuật tìm kiếm trong một không gian đa chiều để tìm cực đại toàn cục
của một số hàm .
Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng
Nguyễn Sơn Hà - CT1301
16
Các kỹ thuật đối sánh mẫu chỉ áp dụng tốt đối với nhận dạng chữ in, còn đối
với chữ viết tay thì các kỹ thuật này tỏ ra kém hiệu quả.
1.3.2. Phƣơng pháp tiếp cận cấu trúc:
Cách tiếp cận của phƣơng pháp này dựa vào việc mô tả đối tƣợng nhờ một số
khái niệm biểu diễn đối tƣợng cơ sở trong ngôn ngữ tự nhiê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,… Mỗi đối tƣợng
đƣợc mô tả nhƣ một sự kết hợp của các dạng nguyên thuỷ.
Các quy tắc kết hợp các dạng nguyên thuỷ đƣợc xây dựng giống nhƣ việc
nghiên cứu văn phạm trong một ngôn ngữ, do đó quá trình quyết định nhận dạng là
quá trình phân tích cú pháp. Phƣơng pháp này đặt vấn đề để giải quyết bài toán
nhận dạng chữ tổng quát. Tuy vậy, cho đến nay còn nhiều vấn đề liên quan đến hệ
nhận dạng cú pháp chƣa đƣợc giải quyết độc lập và chƣa xây dựng đƣợc các thuật
toán phổ dụng. Hiện nay, nhận dạng theo cấu trúc phổ biến là trích trọn các đặc
trƣng của mẫu học, phân hoạch bảng ký tự dựa trên các đặc trƣng này, sau đó ảnh