BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CẦN THƠ
ĐỖ THANH CAO
PHÂN TÍCH CẤU TRÚC VÀ
NHẬN DẠNG BIỂU MẪU
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Cần Thơ - 2010
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CẦN THƠ
ĐỖ THANH CAO
PHÂN TÍCH CẤU TRÚC VÀ
NHẬN DẠNG BIỂU MẪU
Chuyên ngành: HỆ THỐNG THÔNG TIN
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Người hướng dẫn: TS. TRẦN CAO ĐỆ
Cần Thơ - 2010
quý báo trong quá trình theo học chương trình cao học tại Khoa. Xin cám ơn các
bạn Huỳnh Phước Hải, Phạm Thiên Ân và Nguyễn Chế Linh đã nhiệt tình giúp tôi
thu thập mẫu chữ viết tay.
Chân thành cám ơn.
Đỗ Thanh Cao
ii
MỤC LỤC
Chương 1:TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU ...................................................13
1.1.Giới thiệu...................................................................................................................13
1.2.Hệ thống xử lí biểu mẫu tự động...............................................................................14
1.2.1.Số hóa biểu mẫu giấy.........................................................................................15
1.2.2.Phân tích biểu mẫu.............................................................................................15
1.2.3.Nhận dạng biểu mẫu .........................................................................................16
1.2.4.Nhận dạng dữ liệu viết tay.................................................................................17
1.3.Phạm vi của đề tài......................................................................................................18
1.3.1.Mô hình hóa biểu mẫu (form modeling)............................................................19
1.3.1.1.Đăng ký biểu mẫu (form registration)........................................................19
1.3.1.2.Mô hình biểu mẫu (form template)............................................................19
1.3.2.Phân tích biểu mẫu.............................................................................................20
1.3.3.Nhận dạng biểu mẫu..........................................................................................20
1.3.4.Nhận dạng dữ liệu viết tay.................................................................................21
1.4.Bố cục của luận văn...................................................................................................21
Chương 2:BIỂU MẪU VÀ TRÍCH XUẤT ĐƯỜNG THẲNG TỪ ẢNH BIỂU MẪU .....23
2.1.Tổng quan về biểu mẫu.............................................................................................23
2.1.1.Khái niệm biểu mẫu...........................................................................................23
2.1.2.Lợi ích của biểu mẫu..........................................................................................23
Chương 4:MÔ HÌNH HÓA VÀ NHẬN DẠNG BIỂU MẪU..............................................59
4.1.Mô hình hóa biểu mẫu...............................................................................................59
4.1.1.Nội dung.............................................................................................................59
4.1.1.1.Thông tin chung.........................................................................................59
4.1.1.2.Thông tin về nhãn.......................................................................................60
4.1.1.3.Thông tin về cấu trúc ô nhập......................................................................60
4.1.2.Cấu trúc..............................................................................................................62
4.1.3.Lưu trữ...............................................................................................................63
4.1.3.1.XML và DOM............................................................................................63
4.1.3.2.Các phần tử (thẻ) XML trong tập tin mô hình...........................................64
4.1.3.3.Kết hợp thông tin ô nhập và nhãn tương ứng.............................................67
4.2.Nhận dạng biểu mẫu..................................................................................................69
4.2.1.Phương pháp nhận dạng biểu mẫu.....................................................................69
4.2.2.Nhận dạng biểu mẫu bằng từ khóa....................................................................71
4.3.Thực nghiệm..............................................................................................................75
4.3.1.Mô hình hóa:......................................................................................................75
4.3.2.Nhận dạng biểu mẫu..........................................................................................76
4.3.2.1.Mô tả tập dữ liệu........................................................................................76
4.3.2.2.Phương pháp kiểm chứng...........................................................................76
Chương 5:NHẬN DẠNG KÝ TỰ VIẾT TAY OFFLINE VỚI SVM..................................78
5.1.Giới thiệu...................................................................................................................78
5.2.Nhận dạng ký tự viết tay............................................................................................78
5.2.1.Đặt vấn đề..........................................................................................................78
5.2.2.Mô hình nhận dạng............................................................................................79
5.2.2.1.Tiền xử lí....................................................................................................79
5.2.2.2.Trích xuất đặc trưng...................................................................................80
5.3.Phương pháp huấn luyện và nhận dạng.....................................................................82
5.4.Thực nghiệm..............................................................................................................82
5.4.1.Mô tả tập dữ liệu................................................................................................82
Hình 2.9: Các ô nhập đồng dạng, có kích thước tương đương.............................................35
Hình 2.10: Các ô nhập không đồng dạng và có kích thước khác nhau................................35
Hình 2.11: Các ô nhập đồng dạng có kích thước khác nhau và biểu mẫu chứa logo...........36
Hình 2.12: Các ô nhập đồng dạng và có kích thước khác nhau...........................................36
Hình 2.13: Ô nhập dạng đường thẳng không liền nét..........................................................37
Hình 2.14: Lỗi trích đường thẳng.........................................................................................37
Hình 3.1: Phân tích biểu mẫu trắng (blank form).................................................................39
Hình 3.2: (a) là cấu trúc đóng, (b) là cấu trúc mở................................................................41
Hình 3.3: Các kiểu giao nhau của hai đường thẳng ngang và dọc.......................................42
Hình 3.4: Cấu trúc ba phần của một đường thẳng ngang (Nguồn: [12])..............................44
Hình 3.5: Sắp xếp các đường thẳng theo thứ tự...................................................................46
Hình 3.6: Ma trận chứa giá trị giao nhau của các đường thẳng...........................................47
Hình 3.7: Thứ tự duyệt ma trận giao điểm để xác định cấu trúc chữ nhật...........................47
Hình 3.8: Thứ tự duyệt ma trận giao điểm để xác định cấu trúc "răng cưa"........................49
Hình 3.9: Lỗi đường thẳng dọc ở giữa cấu trúc...................................................................50
Hình 3.10: Lỗi đường thẳng ngang và dọc ở cuối cấu trúc..................................................51
Hình 3.11: Lỗi đường thẳng ngang và dọc ở đầu cấu trúc...................................................51
Hình 3.12: Kết quả trích xuất cấu trúc vùng nhập................................................................56
Hình 3.13: Kết quả trích xuất cấu trúc vùng nhập (tiếp theo)..............................................56
Hình 3.14: Nhận dạng phần văn bản trong ảnh biểu mẫu....................................................57
Hình 3.15: Nhận dạng văn bản trong một phần của ảnh biểu mẫu......................................57
Hình 4.1: Thông tin nhãn của vùng nhập.............................................................................59
Hình 4.2: (a) đặc trưng một ô nhập chữ nhật, (b) đặc trưng một dãy các ô nhập liền nhau.59
Hình 4.3: Đặc trưng ô nhập dạng "răng cưa".......................................................................60
Hình 4.4: Đặc trưng của đường thẳng..................................................................................60
Hình 4.5: Đặc trưng được biểu diễn dưới dạng cây tài liệu (document tree).......................61
Hình 4.6: Tương quan về vị trí giữa nhãn và cấu trúc ô nhập..............................................66
Hình 4.7: Vị trí của nhãn so với vùng nhập.........................................................................67
Hình 4.8: Tính độ tương đồng (khớp) của biểu mẫu và mô hình biểu mẫu.........................71
Hình 4.9: Công cụ mô hình hóa biểu mẫu............................................................................74
mại. Vấn đề đặt ra là làm sao chuyển được nội dung viết/in trên biểu mẫu giấy
thành dạng máy đọc được (ASCII, unicode chẳng hạn). Vấn đề này liên quan đến
các nghiên cứu trong lĩnh vực: Phân tích & nhận dạng biểu mẫu (form analysis and
recognition), phân tích cấu trúc tài liệu (document analysis), nhận dạng chữ in và
nhận dạng chữ viết tay (OCR).
Có thể chia quá trình hiểu nội dung biểu mẫu theo ba bước. Bước đầu tiên là
phân tích và xây dựng cấu trúc của biểu mẫu được dùng, tức là phân tích và xây
dựng mô hình biểu mẫu (form template) ở dạng cơ sở dữ liệu, chứa trong tập tin
XML chẳng hạn. Bước kế đến là nhận diện đúng biểu mẫu khi cho một biểu mẫu đã
điền thông tin (filled form). Cuối cùng là áp dụng mô hình biểu mẫu tương ứng với
biểu mẫu đã điền thông tin để có thể cắt lấy từng phần ảnh tương ứng với từng
trường (field) trong biểu mẫu mang đi xử lí và nhận dạng chữ viết/chữ in.
Luận văn này đề cập đến hai bước đầu tiên trong quá trình “hiểu” biểu mẫu
nêu trên. Trước tiên, mỗi loại biểu mẫu (cụ thể là một form trống, chưa điền thông
tin) sẽ được phân tích và mô tả cấu trúc trong một tập tin XML, đây là mô hình biểu
mẫu. Có thể coi mẫu của biểu mẫu là một danh sách các trường (ô để điền thông
tin), mỗi trường có một tên và nhãn hay từ khoá đi kèm cùng với toạ độ của trường.
Ngoài ra còn có các thông tin khác để trợ giúp quá trình nhận dạng chữ viết trong
trường, chẳng hạn nội dung điền vào là số (chiffre) hay kí tự mẫu tự (alphabet). Như
vậy, mỗi form có thể được đặc trưng bởi danh sách các từ khoá diễn giải cho các
trường in trên biểu mẩu. Việc nhận dạng chữ in (các từ in trên biểu mẫu) sẽ được
thực hiện bởi công cụ nguồn mở Tesseract. Bước nhận dạng biểu mẫu có thể dựa
trên tập từ khoá này, cụ thể là đo độ tương đồng giữa các từ khoá đặc trưng cho biểu
mẫu với tập hợp các từ (in) nhận dạng được trên biểu mẫu đã điền thông tin đang
được quan tâm. Vấn đề nhận dạng chữ viết tay cũng được trình bày, thực nghiệm
trên tập dữ liệu tiếng Việt tự xây dựng.
Từ khoá: phân tích biểu mẫu (form analysis), nhận dạng biểu mẫu (form
recognition), phân tích tài liệu (document analysis), nhận dạng chữ in (OCR), trích
xuất đường thẳng (line detection), nhận dạng chữ viết tay (handwriting
recognition), xử lí biểu mẫu (form processing), máy học vectơ hỗ trợ (SVM),...
Keywords: form analysis, form recognition, document analysis, OCR, line
detection, handwriting recognition, form processing, SVM,....
ix
Chương 1:
1.1.
TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU
Giới thiệu
Ngày nay, việc sử dụng các biểu mẫu (form) trong các giao dịch thương mại
và hành chính đã trở nên rất phổ biến, góp phần vào chuẩn hóa các giao dịch và
thúc đẩy hành chính điện tử. Việc điền thông tin vào biểu mẫu và nộp cho nơi có
trách nhiệm xử lí không còn quá xa lạ với nhiều người, ví dụ khi đến ngân hàng
giao dịch chúng ta được yêu cầu ghi thông tin vào những biểu mẫu tương ứng như
biểu mẫu gửi tiền, biểu mẫu rút tiền, biểu mẫu chuyển khoản...; một ví dụ khác ở
Phòng Quản lí Xuất Nhập cảnh có các biểu mẫu: xin cấp hộ chiếu, xin gia hạn hộ
chiếu, xin thị thực, …
Việc nhập thông tin từ biểu mẫu vào máy tính hiện vẫn được xử lí hầu hết
theo cách thủ công. Con người đọc thông tin đã được điền trên biểu mẫu, sau đó
dùng bàn phím (keyboard) để nhập thông tin đó vào máy tính. Công việc này tốn
nhiều chi phí về thời gian và công sức cũng như phát sinh sai sót do cả hai yếu tố
khách quan và chủ quan. Trong những tình huống phải xử lí một số lượng lớn biểu
mẫu (biểu mẫu điều tra dân số, thi trắc nghiệm,...), loại biểu mẫu có thông tin cần
nhập rất nhiều, hay giao dịch cần thời gian đáp ứng nhanh, thì việc xử lí biểu mẫu
thủ công càng bộc nhiều hạn chế, thậm chí, trong vài trường hợp là không khả thi.
Số hóa biểu mẫu giấy (digitalization of form).
•
Phân tích biểu mẫu (form analysis).
13
•
Nhận dạng biểu mẫu (form recognition)
•
Nhận dạng dữ liệu viết tay (OCR - Optical Character Recognition hay
HandWritter recognition).
1.2.1.
Số hóa biểu mẫu giấy
Đây là bước đầu tiên trong quá trình xử lí biểu mẫu. Bước này có nhiệm vụ
chuyển thông tin từ biểu mẫu giấy thành thông tin dưới dạng ảnh, với những định
dạng ảnh quen thuộc (bmp, png, tif, jpeg,....). Ảnh này chứa thông tin nguyên cả
biểu mẫu. Thông thường máy quét ảnh được dùng để số hóa, với độ phân giải
300dpi hoặc cao hơn, không gian màu là RGB hoặc Grayscale. Ảnh của biểu mẫu
được lưu trong bộ nhớ máy tính trước khi được xử lí. Trong giai đoạn này ảnh được
tiền xử lí (preprocessing): chống nghiên (deskew), khử nhiễu (noise removal), …
Chất lượng ảnh càng tốt thì kết quả xử lí càng cao và ngược lại.
1.2.2.
Nhận dạng biểu mẫu là định danh (identification) một ảnh thuộc một loại
biểu mẫu nào đó trong tập hợp nhiều loại biểu mẫu (xem hình 1.3). Việc nhận dạng
sẽ dựa vào thông tin đặc trưng của biểu mẫu: như mã vạch (barcode), màu sắc
(color), ký hiệu đặc biệt (symbol), cấu trúc vùng nhập, từ khóa,....tiếp theo dùng các
giải thuật máy học hoặc so khớp mẫu để nhận dạng. Biểu mẫu là một loại ảnh tài
liệu (document image) đặc biệt và phương pháp so khớp được dùng phổ biến để
nhận dạng [11].
Hình 1.3: Nhận dạng biểu mẫu.
Để có thể dùng phương pháp so khớp, thông tin về loại biểu mẫu được biểu
diễn dưới dạng mô hình biểu mẫu (form prototype, form template). Mỗi mô hình
15
biểu mẫu chứa các thông tin đặc trưng một biểu mẫu, được biểu diễn bằng những
cấu trúc dữ liệu dể dàng xử lí được trong máy tính. Mỗi hệ thống đều có sẵn một cơ
sở dữ liệu mô hình biểu mẫu (form prototype database). Cơ sở dữ liệu này có thể
được cập nhật trong quá trình sử dụng.
Việc nhận dạng một biểu mẫu là việc so khớp (matching) những đặc trưng
của biểu mẫu đó với thông tin các biểu mẫu đã được lưu trong cơ sở dữ liệu. Dựa
vào mức độ tương đồng để xác định được loại biểu mẫu.
1.2.4.
Nhận dạng dữ liệu viết tay
Sau khi biểu mẫu đã được nhận dạng, bước tiếp theo là diễn dịch dữ liệu cần
quan tâm thành những định dạng điện tử quen thuộc (electronic format, computer
readable format).
vùng nhập
Biểu mẫu đã điền
Trích đặc trưng
cấu trúc vùng nhập
Nhận dạng biểu mẫu
Cơ sở dữ liệu
mẫu biểu mẫu
Kết hợp nhãn và
thông tin vùng nhập
Trích xuất dữ liệu
Nhận dạng dữ liệu
Tập tin XML
Cơ sở dữ liệu
khai thác
Hình 1.5: Sơ đồ hoạt động của hệ thống.
Để xử lí loại biểu mẫu tổng quát, đề tài tập trung giải quyết hai mục tiêu
chính là: nghiên cứu vấn đề mô hình hóa và nhận dạng biểu mẫu.
Bên cạnh đó, để hoàn chỉnh một hệ thống xử lí biểu mẫu, vấn đề nhận dạng
ký tự viết tay cũng được trình bày. Sơ đồ hoạt động của hệ thống thể hiện ở hình
1.5.
17
trọng nhất trong mô hình hóa là phân tích biểu mẫu. Phân tích biểu mẫu có nhiệm
vụ trích lọc (extraction) các thông tin cần mô hình hóa.
Thường các biểu mẫu trắng (blank form – biểu mẫu chưa được điền thông
tin) sẽ được dùng để mô hình hóa.
1.3.2.
Phân tích biểu mẫu
Phân tích biểu mẫu là quá trình trích xuất các thông tin ghi trên biểu mẫu từ
tập ảnh của nó. Phân tích là khâu quan trọng nhất của quá trình xử lí biểu mẫu.
Mục đích chính của việc phân tích biểu mẫu là trích xuất các thông tin cần
quan tâm trên biểu mẫu như: ký tự (nhãn), cấu trúc ô nhập (loại ô nhập). Các thông
tin này sẽ được dùng cho giai đoạn mô hình hóa, nhận dạng và trích xuất dữ liệu
điền vào biểu mẫu .
Nhãn (label)
Ô nhập (textbox)
Hình 1.7: Nhãn và ô nhập của biểu mẫu.
1.3.3.
Nhận dạng biểu mẫu
Hướng tiếp cận của đề tài là không dùng các giải thuật máy học và không
dựa vào các thông tin đánh dấu như mã vạch, màu sắc, ký hiệu đặc biệt in trên biểu
19
mẫu. Việc bổ sung thông tin đánh dấu làm tăng chi phí việc sử dụng biểu mẫu.
biểu mẫu tự động và phạm vi của đề tài.
20
Chương 2 – Biểu mẫu và trích xuất đường thẳng trên biểu mẫu: giới
thiệu khái niệm biểu mẫu, phân loại biểu mẫu, các loại thông tin điền trong biểu
mẫu. Tiếp theo trình bày phương pháp trích xuất đường thẳng từ ảnh biểu mẫu. Giới
thiệu chi tiết phương pháp Directional Single-Connected Chain (DSCC) để trích
xuất các đường thẳng trong ảnh biểu mẫu.
Chương 3 – Phân tích biểu mẫu: Trong chương này sẽ giải quyết vấn đề
trích xuất thông tin cấu trúc vùng nhập và nhãn. Từ kết quả các đường thẳng được
trích xuất ở chương hai, một phương pháp gom nhóm các đường thẳng này thành
cấu trúc ô nhập sẽ được trình bày. Giới thiệu phương pháp trích xuất nhãn dùng
công cụ OCR (Tesseract và VietOCR).
Chương 4 – Mô hình hóa và nhận dạng biểu mẫu: Thông tin về mô hình
biểu mẫu sẽ được trình bày chi tiết: nội dung, cấu trúc, lưu trữ và cách truy xuất.
Trong chương này một số phương pháp nhận dạng biểu mẫu cũng được giới thiệu
và phương pháp dùng từ khóa để nhận dạng sẽ được trình bày chi tiết.
Chương 5 – Nhận dạng ký tự viết tay offline dùng SVM: trình bày về
một mô hình dạng ký tự viết tay dạng offline dùng phương pháp máy học SVM.
Việc huấn luyện và kiểm tra dựa trên trên tập dữ liệu do chúng tôi tự xây dựng.
Chương 6 – Kết luận: đánh giá các kết quả đã đạt được và đề xuất hướng
phát triển của đề tài.
21
Chương 2:
Lợi ích của biểu mẫu
Biểu mẫu là một loại tài liệu đặc biệt, được dùng ngày càng nhiều do một số
lợi ích sau:
22
•
Người sử dụng viết ít hơn, do một số thông tin chung được in sẵn trên
biểu mẫu, nên chỉ cần điền vào một số thông tin cần thiết là có thể hoàn chỉnh một
tài liệu biểu mẫu. Ngoài ra, trên biểu mẫu còn có các thông tin chỉ dẫn giúp người
điền thông tin dễ dàng và chính xác hơn.
•
Thông tin thống nhất: do biểu mẫu được thiết kế và in sẵn với cấu trúc
xác định nên các thông tin cần thiết điền trên biểu mẫu là thống nhất. Dễ dàng kiểm
tra tính đúng đắn của thông tin.
•
Thuận lợi trong việc xử lý: tính xác định về mặt cấu trúc và tính nhất
quán về mặt thông tin nên dễ dàng hơn trong việc xử lý kể cả xử lý thủ công và xử
lý tự động. Đặc biệt là thuận lợi trong việc xử lý bằng máy tính điện tử.
2.1.3.
Các kiểu vùng nhập của biểu mẫu
Để đem lại những lợi ích cho việc điền và xử lí, các vùng nhập (input fields)
của biểu mẫu được thiết kế với cấu trúc xác định. Thông tin điền vào được giới hạn
trong các cấu trúc này. Việc chứa các cấu trúc vùng nhập là điểm đặc thù của ảnh
biểu mẫu so với các loại ảnh tài liệu khác.
Cấu trúc vùng nhập rất đa dạng, tùy theo mục đích sử dụng. Mỗi cấu trúc
•
Kiểu trường nhập dạng bảng (table form): cho phép điền thông tin tổ
chức dạng bảng, thường là dạng thông tin liên tục giống dạng đường thẳng. Kiểu
trường nhập này không thuộc phạm vi nghiên cứu của đề tài này.
24
•
Kiểu trường nhập tự do (free field): cho phép điền thông tin dạng hình
ảnh như ảnh chụp, hình vẽ, sơ đồ, chữ ký,......
Kiểu trường nhập dạng bảng và tự do không thuộc phạm vi nghiên cứu của
đề tài này.
2.1.4.
Kiểu dữ liệu chứa trong biểu mẫu
Thông tin trên biểu mẫu gồm 2 phần: phần được in sẵn và phần thông tin
được điền vào.
2.1.4.1. Thông tin in sẵn
▪
Chữ viết/số: chữ viết dạng in, thường là cùng font, rõ ràng.
▪
Hình ảnh: hình logo, mã vạch, màu sắc, kí hiệu đặc biệt, …..
2.1.4.2. Thông tin điền vào
▪
Copyright: Tài liệu đại học ©