Các văn bản giấy trong các thư viện truyền thống dần được thay thế bởi cáctài liệu dạng tệp số, lưu trữ trong ổ cứng máy tính với nhiều định dạng như: .doc,.pdf... Trong quá trình số hóa, có rất nhiều văn bản viết tay lâu năm như: di chúccủa chủ tịch Hồ Chí Minh, bản thảo tập thơ viết tay Hoa Lúa của Thi sĩ Hữu Loan...với mong muốn giữ trọn giá trị nguyên văn của các tác phẩm này và khai thác đượcgiá trị nội dung, lưu trữ sao cho phù hợp với nhu cầu lập chỉ mục và tìm kiếm làmột thách thức lớn đặt ra. Trước mắt người ta chỉ có thể lưu giữ các ảnh thông quaviệc scan từng trang tài liệu. Nói một cách khác, đó là quá trình thủ công sao chépy văn từ tài liệu giấy vào máy tính được thực hiện bởi bàn tay con người. Vì vậy,nguồn tài nguyên bỏ ra về thời gian và tiền bạc để thực hiện công việc này là rấtđắt đỏ.Trong nghiên cứu này, đề xuất sử dụng một phương pháp tiếp cận; đó là đánhdấu từ Word Spotting trong tài liệu tiếng Việt viết tay. Đầu tiên, phải chuyển tấtcả hình ảnh văn bản viết tay về dạng nhị phân (trắng và đen) bằng phương phápphân ngưỡng với giá trị ngưỡng thích hợp. Tiếp đến, bằng các bộ lọc đơn giản nhưlọc trung vị 20 để khữ các nhiễu muối tiêu, các vết bẩn và vết mực mờ 33 34.Dựa vào độ đo của giải thuật Dynamic Time Warping mà phân cụm với số kcụm(tùy chọn) với phương thức gom cụm kmedoids. Kết quả của quá trình gom cụm,sẽ nhận được kcụm tượng trưng cho k mẫu unigram từ; giá trị trọng tâm centroidscủa mỗi mẫu sẽ được sử dụng cho quá trình so khớp (matching) của các nghiêncứu sau đó.
LỜI CAM ĐOAN
Tôi xin cam đoan Luận văn Thạc sĩ Công nghệ Thông tin đề tài “Nghiên cứu
về đánh dấu văn bản chữ viết tay tiếng Việt với giải thuật Dynamic Time
Warping” được hoàn thành trên kết quả nghiên cứu của bản thân. Các công việc
nghiên cứu và nội dung thực hiện trong luận văn chưa từng được nộp để lấy bằng
cấp từ một trường hay một tổ chức nào; ngoại trừ phần cơ sở lý thuyết và các kết
quả từ các giáo trình, báo cáo khoa học được tôi tham khảo, ghi rõ trong phần tài
liệu tham khảo của luận văn.
Cần Thơ, ngày 27 tháng 10 năm 2017
Học viên thực hiện
(Ký và ghi rõ họ tên)
NGÔ GIANG THANH
i
LỜI CẢM ƠN
Trong quá trình học tập, nghiên cứu và thực hiện luận văn Cao học, em đã
nhận được sự giúp đỡ rất nhiệt tình từ quý thầy cô, bạn bè và gia đình. Em xin bày
tỏ lòng biết ơn sâu sắc tới:
Hai thầy hướng dẫn PGS. TS Trần Cao Đệ và TS. Lê Văn Lâm, các thầy
không chỉ hướng dẫn em nghiên cứu tận tâm mà còn giúp đỡ em rất nhiệt tình
trong mọi việc. Chính điều đó đã tạo niềm tin, động lực cho em có thể hoàn thành
đề tài nghiên cứu của mình.
Các thầy cô trong Khoa Công nghệ Thông tin và Truyền thông, trường Đại
học Cần Thơ, trong hơn 2 năm qua các thầy cô đã truyền đạt rất nhiều kiến thức
và kinh nghiệm quý giá giúp em trưởng thành hơn trong cuộc sống, cũng như trong
học tập và nghiên cứu.
Con cũng xin cảm ơn cha mẹ là nguồn động lực luôn động viên, khích lệ mỗi
khi con gặp khó khăn. Luôn là chỗ vựa vững chắc cho con đứng lên mỗi khi con
vấp ngã. Mình cảm ơn những người bạn thân đã luôn giúp đỡ, ủng hộ và bên cạnh
mình trong suốt thời gian khi mình gặp phải khó khăn.
Một lần nữa xin kính chúc quý mọi người luôn dồi dào sức khỏe, thành công
trong công việc và cuộc sống.
Chân thành cảm ơn./.
Cần Thơ, ngày 27 tháng 10 năm 2017
Học viên thực hiện
(Ký và ghi rõ họ tên)
NGÔ GIANG THANH
ii
MỤC LỤC
Trang
CHƯƠNG 1 TỔNG QUAN ................................................................................1
1.1 Lý do chọn đề tài ...........................................................................................1
1.2 Các vấn đề liên quan ......................................................................................1
Các hệ thống đã có hiện tại .................................................................2
Kỹ thuật đánh dấu từ - Word Spotting ................................................3
Mô hình tổng quan của nghiên cứu .....................................................4
1.3 Đối tượng và phạm vi nghiên cứu ..................................................................6
Đối tượng nghiên cứu .........................................................................6
Phạm vi nghiên cứu ............................................................................6
1.4 Mục tiêu của đề tài.........................................................................................6
1.5 Phạm vi đề tài ................................................................................................7
1.6 Ý nghĩa thực tiễn của đề tài nghiên cứu .........................................................7
1.7 Phương pháp nghiên cứu ...............................................................................8
1.8 Cấu trúc luận văn ...........................................................................................9
CHƯƠNG 2 CƠ SỞ LÝ THUYẾT ...................................................................10
2.1 Xử lý ảnh là gì? ...........................................................................................10
2.2 Thu nhận và biểu diễn ảnh ...........................................................................11
Các thiết bị thu nhận ảnh ..................................................................11
Mô hình lưu trữ Raster .....................................................................11
Một số khái niệm cơ bản ..................................................................12
2.3 Nhiễu và khữ nhiễu......................................................................................13
2.4 Một số phép toán logic trên ảnh ...................................................................14
iii
Phép toán NOT.................................................................................14
Phép toán AND ................................................................................14
Phép toán OR ...................................................................................14
2.5 Phân ngưỡng................................................................................................15
Phân ngưỡng cơ bản .........................................................................15
Nhị phân Otsu ..................................................................................15
2.6 Phép cuộn và mẫu ........................................................................................17
2.7 Bộ lọc Gaussian ...........................................................................................18
2.8 Bộ lọc trung vị .............................................................................................18
Định nghĩa và mệnh đề .....................................................................19
Kỹ thuật lọc trung vị.........................................................................19
2.9 Các phép toán xử lý hình thái học ................................................................20
Phép toán Dilation ............................................................................20
Phép toán Erosion ............................................................................21
Phép toán Gradient ...........................................................................22
2.10 Gom cụm dữ liệu .......................................................................................22
Gom cụm là gì? ..............................................................................22
Chuẩn hóa dữ liệu ..........................................................................23
Phương pháp phân hoạch ................................................................24
Cách thức đánh giá kết quả gom cụm .............................................25
2.11 Thưviện OpenCV .....................................................................................25
Tổng quan ......................................................................................25
OpenCV 3.x và ngôn ngữ C++ trên Visual Studio 2015 .................26
Các thuộc tính và phương thức .......................................................27
iv
2.12 Ngôn ngữ R và R Studio ............................................................................32
Vài nét về R và R Studio ................................................................32
Thưviện gom cụm dữ liệu ..............................................................33
2.13 Đặc điểm của tiếng Việt và mô hình unigram ............................................33
Đặc điểm của tiếng Việt .................................................................33
Mô hình từ đơn ...............................................................................34
2.14 Trích chọn đặc trưng ..................................................................................35
Tổng quan ......................................................................................35
Projection Profile............................................................................36
Word Profile...................................................................................36
2.15 Euclidean Distance Mapping .....................................................................37
Công thức tính khoảng cách ...........................................................37
Giải thuật EDM ..............................................................................38
2.16 Dynamic Time Warping ............................................................................38
Vài nét về Dynamic Time Warping ................................................38
Lược tả về kỹ thuật về DTW ..........................................................39
Cận dưới Lemire ............................................................................41
2.17 Kết luận chương ........................................................................................43
CHƯƠNG 3 NỘI DUNG NGHIÊN CỨU .........................................................45
3.1 Tiền xử lý – Preprocessing...........................................................................45
Mô hình tiền xử lý hình ảnh .............................................................45
Giải thuật tách dòng .........................................................................47
Giải thuật tách từ ..............................................................................58
Giải thuật chuẩn hóa từ.....................................................................61
v
3.2 Gom cụm dữ liệu .........................................................................................65
Các chiến lược đề xuất .....................................................................65
Cách thức lưu trữ dữ liệu đặc trưng ..................................................66
Kiểm chứng tốc độ tính toán của DTW ............................................66
3.3 Các module xây dựng ..................................................................................67
3.4 Kết luận chương ..........................................................................................68
CHƯƠNG 4 CÁC THỰC NGHIỆM VÀ ĐÁNH GIÁ .......................................69
4.1 Cách thức thu thập và nội dung của dữ liệu..................................................69
Đặc điểm của tập dữ liệu dùng để kiểm chứng .................................69
Nội dung trang viết tay .....................................................................69
4.2 Các thực nghiệm và đánh giá .......................................................................70
Giải thuật phân tách đoạn và tách từ .................................................70
Giải thuật chuẩn hóa từ.....................................................................75
Quá trình gom cụm dữ liệu ...............................................................79
Cải tiến tốc độ tính toán DTW ..........................................................85
4.3 Kết luận chương ..........................................................................................86
CHƯƠNG 5 KẾT LUẬN VÀ KIẾN NGHỊ .......................................................90
5.1 Kết quả đạt được..........................................................................................90
5.2 Các hạn chế và hướng phát triển ..................................................................90
TÀI LIỆU THAM KHẢO .................................................................................93
PHỤ LỤC..........................................................................................................96
vi
DANH MỤC BẢNG
Trang
Bảng 2.1: Giải thuật k-medoids ......................................................................... 24
Bảng 2.2: Liệt kê các phương thức cơ bản nhập xuất trong OpenCV ................. 28
Bảng 2.3: Liệt kê các phương thức logic và dilation trong OpenCV .................. 30
Bảng 2.4: Liệt kê các phương thức khác trong OpenCV .................................... 31
Bảng 2.5: Giải thuật LB_Improved Nearest-Neighbor ....................................... 42
Bảng 3.1: Input/Output giải thuật tiền xử lý hình ảnh ........................................ 46
Bảng 3.2: Input/Output giải thuật khởi tạo và làm mượt y-projection ................ 47
Bảng 3.3: Input/Output giải thuật xác định thung lũng ....................................... 52
Bảng 3.4: Input/Output giải thuật kẽ dòng ......................................................... 54
Bảng 3.5: Input/Output giải thuật tách từ ........................................................... 59
Bảng 3.6: Giải thuật ước lượng giá trị AST ....................................................... 62
Bảng 3.7: Giải thuật loại bỏ đường gạch ngang ................................................. 62
Bảng 3.8: Giải thuật phát hiện đường Baseline .................................................. 63
Bảng 3.9: Giải thuật xóa đường gạch dưới ......................................................... 64
Bảng 3.10: Giải thuật tính giá trị CoM ............................................................... 65
Bảng 3.11: Mô tả sơ lược chức năng các modules được xây dựng ..................... 67
Bảng 4.1: Kết quả tách dòng và từ trên tập dữ liệu............................................. 73
Bảng 4.2: Một số trường hợp tách từ bị lỗi ........................................................ 75
Bảng 4.3: Kết quả thực nghiệm module chuẩn hóa từ ........................................ 77
Bảng 4.4: Một số trường hợp gặp phải khi chuẩn hóa từ .................................... 78
Bảng 4.5: Danh sách top 12 từ được viết nhiều nhất trong tập dữ liệu................ 79
Bảng 4.6: Kết quả khi gom cụm với đặc trưng Projection Profile ...................... 80
vii
Bảng 4.7: Kết quả khi gom cụm với đặc trưng Word Profile ............................. 81
Bảng 4.8: Kết quả gom cụm với k là số cụm tùy chọn trên dữ liệu tác giả 1 ...... 82
Bảng 4.9: Kết quả gom cụm với k là số cụm tùy chọn trên dữ liệu tác giả 2 ...... 82
Bảng 4.10: Kết quả gom cụm trên dữ liệu tác giả 1 và 2 với FastDTW .............. 83
Bảng 4.11: Thời gian tính toán (giây) khi so sánh từng đôi trên dữ liệu ............. 85
Bảng 4.12: Số lần gọi tới hàm DTW .................................................................. 85
viii
DANH MỤC HÌNH ẢNH
Trang
Hình 1.1: Mô hình tổng quan của nghiên cứu ......................................................5
Hình 1.2: Minh họa mục tiêu đạt được của nghiên cứu ........................................7
Hình 2.1: Quá trình xử lý ảnh ............................................................................ 10
Hình 2.2: Sơ đồ tổng quát của một hệ thống xử lý ảnh....................................... 10
Hình 2.3: Ma trận dữ liệu của mô hình Raster.................................................... 12
Hình 2.4: Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB................ 12
Hình 2.5: Ví dụ về giá trị mức xám của các điểm ảnh trong ảnh số .................... 13
Hình 2.6: Ví dụ về khữ nhiễu trong ảnh số ........................................................ 13
Hình 2.7: Phép toán NOT ảnh............................................................................ 14
Hình 2.8: Phép toán AND hai ảnh ..................................................................... 14
Hình 2.9: Phép toán OR ..................................................................................... 15
Hình 2.10: Ví dụ về phương pháp nhị phân Otsu ............................................... 16
Hình 2.11: Lọc nhiễu bằng bộ lọc trung vị ......................................................... 19
Hình 2.12: Các cấu trúc nối kết được sử dụng thông dụng ................................. 21
Hình 2.13: Ví dụ cách tính Dilation ................................................................... 21
Hình 2.14: Ví dụ cách tính Erosion .................................................................... 21
Hình 2.15: Xử lý Gradient với bộ phần tử liên thông 3x3 gồm 4 nối kết ............ 22
Hình 2.16: Gom cụm dữ liệu ............................................................................. 23
Hình 2.17: Logo nhận diện thư viện OpenCV .................................................... 26
Hình 2.18: Ví dụ về unigram trong chữ viết Tay ................................................ 34
Hình 2.19: Từ và đặc trưng Projection Profile ................................................... 36
Hình 2.20: Upper Word đã được trích chọn và chuẩn hóa .................................. 37
ix
Hình 2.21: Lower Word đã được trích chọn và chuẩn hóa ................................. 37
Hình 2.22: Ví dụ về phương pháp so khớp EDM ............................................... 38
Hình 2.23: Minh họa về cách thức so khớp của giải thuật DTW ........................ 39
Hình 2.24: Các ràng buộc trong Dynamic Time Warping .................................. 40
Hình 2.25: Minh họa các đường U(x) và L(x) được tạo ra từ chuỗi x ................. 41
Hình 2.26: Minh họa các bước tính LB_Improved ............................................. 43
Hình 3.1: Các bước trong giai đoạn tiền xử lý văn bản viết tay .......................... 45
Hình 3.2: Lưu đồ các bước tiền xử lý đối với hình ảnh tiếng Việt viết tay ......... 46
Hình 3.3: Lưu đồ giải thuật bước khởi tạo và làm mượt cho y-projection .......... 48
Hình 3.4: Minh họa về khởi tạo y-projection cho đoạn văn bản viết tay ............. 49
Hình 3.5: Minh họa về y-projection và MAF y-projection ................................. 50
Hình 3.6: Minh họa định nghĩa thung lũng trong y-projection ........................... 50
Hình 3.7: Lưu đồ giải thuật xác định thung lũng ................................................ 51
Hình 3.8: Lưu đồ giải thuật hàm identify_valley ................................................ 52
Hình 3.9: Minh họa về giải thuật nối kết thung lũng .......................................... 53
Hình 3.10: Sơ lược các bước kẽ dòng ................................................................ 54
Hình 3.11: Lưu đồ giải thuật lấy thành phần liên thông ..................................... 56
Hình 3.12: Minh họa về giải thuật lấy phần liên thông ....................................... 57
Hình 3.13: Thành phần liên thông trên và dưới .................................................. 57
Hình 3.14: Minh họa trường hợp kẽ dòng khi chạm ........................................... 58
Hình 3.15: Minh họa kết quả tách chữ ............................................................... 58
Hình 3.16: Lưu đồ giải thuật tách từ .................................................................. 60
Hình 3.17: Các thành phần trong một từ ............................................................ 61
Hình 3.18: Các giải thuật trong chuẩn hóa unigram từ ....................................... 61
x
Hình 4.1: Đặc điểm chữ viết tay giữa hai tác giả................................................ 69
Hình 4.2: Giao diện module tiền xử lý khữ nhiễu và phân ngưỡng .................... 71
Hình 4.3: Giao diện module tách đoạn ............................................................... 71
Hình 4.4: Minh họa kết quả quá trình khữ nhiễu ................................................ 72
Hình 4.5: Trường hợp tách đúng và tách sai dòng .............................................. 72
Hình 4.6: Một trang sau khi tách dòng ............................................................... 74
Hình 4.7: Giao diện module chuẩn hóa từ .......................................................... 76
Hình 4.8: Số từ chuẩn hóa đúng trên các tập Dataset trong các lần thực hiện ..... 77
Hình 4.9: Tốc độ tính toán giữa các độ đo khi gom cụm .................................... 83
Hình 4.10: So sánh thông số entropy giữa các độ đo .......................................... 84
Hình 4.11: Thời gian tính toán giữa DTW và Lemire LB................................... 86
Hình 4.12: Mô hình đánh dấu từ đề xuất xây dựng ............................................ 88
Hình 4.13: Mô hình tra cứu và so khớp với chữ ký tay ...................................... 89
xi
DANH MỤC TỪ VIẾT TẮT
STT
Từ viết tắt
Giải thích
Application Programming Interface
1.
API
Giao diện/giao thức cung cấp khả năng truy xuất đến
các hàm/thư viện đã được cài đặt trước đó
Average Stroke Thickness
2.
AST
Giá trị trung bình dùng để xác định độ rộng của
đường gạch ngang trong từ
Center of Mass
3.
CoM
Thông số quan trọng dùng để xác định độ nghiêng
(skew) trong từ
Cơ Sở Dữ Liệu
4.
CSDL
Các dữ liệu đặc trưng của từ đã được trích chọn và
lưu trữ trong bộ nhớ ngoài của máy tính
Device Independent Bitmap
5.
DIB
Cấu trúc lưu trữ tập tin đồ họa kiểu bitmap, tên tiếng
Anh là Windows Bitmap
Dynamic Linked Libraries
6.
DLL
Thư viện liên kết động, có tính khả chuyển cao; là
một thành phần được liên kết sử dụng trong nhiều
phần mềm
Dynamic Time Warping
7.
DTW
Tên một giải thuật so khớp, một độ đo được sử dụng
trong nghiên cứu này
Euclidean Distance Mapping
8.
EDM
Tên một giải thuật so khớp dựa trên khoảng cách
Euclid, xem chi tiết tại [23]
9.
IDE
Integrated Development Environment
xii
Là một phần mềm cung cấp cho các lập trình viên
một môi trường tích hợp, bao gồm nhiều công cụ
khác nhau
Intel’s Integrated Performance Primitives
10.
IPP
Một dạng thưviện tối ưu các phép toán/thuật toán xử
lý ảnh trong OpenCV với các chip Intel
Optical Character Recognition
11.
12.
OCR
Hướng tiếp cận trong nhận dạng chữ viết tay; nhận
dạng ký tự quang học
Object-Oriented Programming
OOP
Lập trình hướng đối tượng
Partitioning Around Medoids
13.
PAM
Một giải thuật gom cụm theo phương pháp phân
hoạch, tên gọi khác của k-medoids
Random Access Memory
14.
RAM
15.
SC
Bộ nhớ khả biến cho phép truy xuất đọc-ghi ngẫu
nhiên của máy tính
Shape Content matching
Tên một giải thuật so khớp, xem chi tiết tại [4]
Scott and Longuet Higgins
16.
SLH
17.
SSD
Tên một giải thuật so khớp, xem chi tiết tại [23]
the Sum of Squared Differences
Tên một giải thuật so khớp, xem chi tiết tại [23]
xiii
ABSTRACT
In the sector of processing images of Vietnamese handwritten text, the technique
of Optical Character Recognition is replaced with Word Spotting, which is
presented in this thesis. Word Spotting is not a separated processing algorithm that
it is a sequential one; including many operations basing on digital images such as:
images clarification, line/word segmentation, normalization, featured extraction,
matching and clustering. Clarification is known as reducing noise image (impulse
noise) and improving image quality (blurred ink, stains). Next is the process of
transferring text images into black and white images (binary) those are
processable. Word segmentation is the defining the location where the content has
phrases to be used; processing is based on y-projection (line segmentation), xprojection (word segmentation), combined with valleys and peaks - finding
manipulation in order to determine the splitting lines. Next, standardized operation
is detection and elimination the arising noises in the process of writing the text,
such as: dashes, italic words by using the AST and CoM values. Finally, the
characteristics of Word Profile (includes upper and lower word) and Projection
Profile will be extracted and clustered with Dynamic Time Warping and Euclid
distances by k-medoids/PAM algorithm. In the experiments, the data of 17
handwritten pages including 2693 words by two persons with the same content
were collected. As a result, the accuracy of line segmentation is 97% and word
segmentation is 84%. Beside that, the normalized algorithm is effective with low
skew words. In short, the 2693 unigrams were clustered into 80 partitions (k) with
DTW distance’s entropy value better (lower) than Euclid distance. Especially, the
computational time is clearly improved when we combined FastDTW and Lemire
Lower bound with Vietnamese handwritting features.
Keywords: Pre-processing of handwritten text, word segmentation, normalization
word, Dynamic Time Warping, word spotting, word profile, projection profile,
time series clustering k-medoids, Lemire lower bound
xiv
TÓM TẮT
Trong lĩnh vực xử lý hình ảnh văn bản tiếng Việt viết tay, ngoài phương pháp nhận
dạng ký tự quang học, thì kỹ thuật đánh dấu từ sẽ là nội dung được trình bày trong
nghiên cứu. Đánh dấu từ không phải là một giải thuật xử lý rời rạc, mà đó là một
quá trình tuần tự; bao gồm nhiều thao tác xử lý dựa trên ảnh số như: Làm rõ ảnh,
phân tách dòng/từ, chuẩn hóa, trích chọn đặc trưng, tính toán so khớp và gom cụm.
Làm rõ ảnh là việc làm giảm độ nhiễu (impulse noise) và cải thiện chất lượng ảnh
(mực bị mờ, vết bẩn). Song song với đó là thao tác phân ngưỡng hình ảnh văn bản
thành dạng ảnh mức xám, với giá trị trắng và đen có thể xử lý được. Phân tách từ
ngữ là việc xác định khoảng vùng tọa độ, mà ở đó có chứa nội dung cụm từ cần sử
dụng; việc xử lý dựa vào phép chiếu y-projection (tách dòng), x-projection (tách
unigram từ), kết hợp với thao tác tìm các đỉnh và thung lũng để xác định đường
phân cách. Tiếp đến, thao tác chuẩn hóa là phát hiện và loại bỏ các nhiễu phát sinh
trong quá trình viết văn bản đó có thể là: đường gạch ngang, chữ bị nghiêng bằng
các giá trị AST và CoM. Cuối cùng, các đặc trưng Word Profile (bao gồm upper
và lower word) và Projection Profile sẽ được trích chọn; đó cũng là dữ liệu đầu
vào của quá trình gom cụm k-medoids với độ đo Dynamic Time Warping và
Euclid. Trong phần thực nghiệm, tiến hành thu thập dữ liệu 17 bản viết tay với
2693 từ của 2 tác giả về cùng một nội dung. Lần lượt kiểm chứng thực nghiệm với
các giải thuật tiền xử lý, tách dòng, tách từ, chuẩn hóa và gom cụm. Kết quả của
quá trình tách dòng đạt 97% trong khi tách từ đạt 85%. Quá trình chuẩn hóa giải
quyết tốt trên các từ có độ nghiêng (skew) nhỏ. Cuối cùng, khi tiến hành gom cụm
với 2693 unigram từ vào 80 mẫu với DTW đạt kết quả tốt hơn so với độ đo Euclid.
Đặc biệt, tốc độ tính toán khi kết hợp giữa kỹ thuật tính cận dưới Lemire với
FastDTW đã được cải thiện rõ rệt.
Các từ khóa: tiền xử lý chữ viết tay, phân tách từ, chuẩn hóa, dynamic time
warping, word spotting, word profile, projection profile, k-medoids, cận dưới
Lemire
xv
CHƯƠNG 1
TỔNG QUAN
1.1 Lý do chọn đề tài
Các văn bản giấy trong các thư viện truyền thống dần được thay thế bởi các
tài liệu dạng tệp số, lưu trữ trong ổ cứng máy tính với nhiều định dạng như: .doc,
.pdf... Trong quá trình số hóa, có rất nhiều văn bản viết tay lâu năm như: di chúc
của chủ tịch Hồ Chí Minh, bản thảo tập thơ viết tay Hoa Lúa của Thi sĩ Hữu Loan...
với mong muốn giữ trọn giá trị nguyên văn của các tác phẩm này và khai thác được
giá trị nội dung, lưu trữ sao cho phù hợp với nhu cầu lập chỉ mục và tìm kiếm là
một thách thức lớn đặt ra. Trước mắt người ta chỉ có thể lưu giữ các ảnh thông qua
việc scan từng trang tài liệu. Nói một cách khác, đó là quá trình thủ công sao chép
y văn từ tài liệu giấy vào máy tính được thực hiện bởi bàn tay con người. Vì vậy,
nguồn tài nguyên bỏ ra về thời gian và tiền bạc để thực hiện công việc này là rất
đắt đỏ.
Trong nghiên cứu này, đề xuất sử dụng một phương pháp tiếp cận; đó là đánh
dấu từ - Word Spotting trong tài liệu tiếng Việt viết tay. Đầu tiên, phải chuyển tất
cả hình ảnh văn bản viết tay về dạng nhị phân (trắng và đen) bằng phương pháp
phân ngưỡng với giá trị ngưỡng thích hợp. Tiếp đến, bằng các bộ lọc đơn giản như
lọc trung vị [20] để khữ các nhiễu muối tiêu, các vết bẩn và vết mực mờ [33] [34].
Dựa vào độ đo của giải thuật Dynamic Time Warping mà phân cụm với số k-cụm
(tùy chọn) với phương thức gom cụm k-medoids. Kết quả của quá trình gom cụm,
sẽ nhận được k-cụm tượng trưng cho k mẫu unigram từ; giá trị trọng tâm centroids
của mỗi mẫu sẽ được sử dụng cho quá trình so khớp (matching) của các nghiên
cứu sau đó.
1.2 Các vấn đề liên quan
Người ta đã bắt đầu nghiên cứu về lĩnh vực nhận dạng chữ viết tay trước đây
khá lâu. Nhiều nghiên cứu trong báo cáo khoa học về chủ đề này cũng đã được
công bố trong các hội thảo; nhiều ứng dụng có liên quan cũng đã được xuất bản
rộng rãi dưới dạng mã nguồn mở hoặc bản quyền thương mại. Nhìn chung, có hai
1
hướng tiếp cận phổ biến khi đề cập đến vấn đề xử lý văn bản viết tay là Optical
Character Recognition và Word Spotting.
Các hệ thống đã có hiện tại
Từ những năm 1929, ý tưởng cơbản về nhận dạng chữ viết tay dần được hình
thành khi Gustav Tauschek ở Đức được cấp bằng sáng chế OCR. Thiết bị của ông
là một thiết bị cơ khí sử dụng các mẫu và một bộ tách sóng quang. Cho đến thời
điểm hiện nay, OCR ngày càng khẳng định sự tiện ích của nó. Cùng với sự phát
triển của máy tính, OCR cũng dần nâng cao được khả năng nhận dạng.
Hiện nay có rất nhiều phần mềm thương mại và tự do về OCR. Một trong số
đó phải kể đến ứng dụng FreeOCR1. Đây là một phần mềm mã nguồn mở dựa trên
nền tảng mã nguồn mở Tesseract-OCR2 do Google tài trợ. Ưu điểm của phần mềm
này là nhận dạng các ký tự hình ảnh hoặc tập tin PDF, hỗ trợ một số định dạng ảnh
như: TIF, BMP, JPG, PNG. Loại bỏ được các thành phần không phải văn bản (hình
ảnh, bảng tính). Xử lý riêng lẻ các trang đối với tài liệu nhiều trang. Khuyết điểm
là không hỗ trợ nhận dạng văn bản chữ viết tay. Ngoài ra, VnDOCR3 là phần mềm
thương mại do Phòng nhận dạng và Công nghệ Tri thức – Viện Công nghệ Thông
tin nghiên cứu và phát triển. Ưu điểm nổi bật của ứng dụng này là có thể trực tiếp
nhận dạng tài liệu quét qua máy scanner mà không cần lưu trữ trung gian dưới
dạng hình ảnh. Khuyết điểm của phần mềm là chỉ làm việc trên tài liệu chữ in.
Đối với các văn bản hình ảnh dạng chữ in thì cho kết quả rất cao trên 90%.
Tuy nhiên, khó khăn và hạn chế chung của hướng tiếp cận này là chất lượng hình
ảnh, font chữ đặc biệt và chữ viết tay cho ra kết quả không khả quan. Đặc biệt, với
ngôn ngữ tiếng Việt thì tỉ lệ chính xác không cao so với các ngôn ngữ khác (tiếng
Anh). Do sự xuất hiện của các dấu giọng (huyền, sắc, hỏi, ngã, nặng) chỉ các thanh
của âm tiếng Việt.
1
Xem thêm tại: http://www.freeocr.net/
2
Xem thêm tại: https://github.com/tesseract-ocr
3
Xem thêm tại: http://www.vndocr.com/home/Products.asp?ProductID=2
2
Một nghiên cứu khác của Tomai [6] đã thể hiện sự khó khăn của phương
pháp nhận diện tài liệu viết tay cổ. Mục tiêu của họ trong nghiên cứu này là sinh
ra một ánh xạ biểu diễn cặp từ – từ giữa hình ảnh văn bản viết tay và một bản chép
lại thủ công của văn bản đó. Hiệu suất của việc nhận diện khá thấp. Rõ ràng phương
pháp OCR không thích hợp cho việc nhận diện các tài liệu viết tay.
Tóm lại, các báo cáo nghiên cứu hướng đến cách giải quyết xử lý văn bản
viết tay cho một ngôn ngữ đặc trưng (đa phần là tiếng Anh). Trong khi đó, nghiên
cứu về đặc trưng của ngôn ngữ viết tay tiếng Việt còn khá ít. Một trong số đó, phải
kể đến nghiên cứu [29] của nhóm tác giả Phạm Anh Phương, Ngô Quốc Tạo,
Lương Chi Mai về các thức chọn đặc trưng Wavelet Haar kết hợp với SVM4 trong
chữ viết tay tiếng Việt. Trong bài báo của họ, đã đề xuất được một phương pháp
theo hướng OCR, nhận dạng chữ viết tay tiếng Việt là nhận dạng dấu với chữ cái
riêng nhau. Tuy nhiên, nghiên cứu chỉ dừng lại ở mức nhận dạng mà không nêu cụ
thể các phương pháp tiền xử lý văn bản trước đó.
Kỹ thuật đánh dấu từ - Word Spotting
Thay vì kì vọng chuyển tất cả từ ngữ trong văn bản viết tay sang chữ đánh
máy, tức là toàn bộ nội dung viết tay thành một dạng kí tự sửa đổi được như mã
Unicode, UTF-8, ASCII... Người ta chấp nhận việc chỉ tìm một từ khóa nào đó
xem có trong tài liệu hay không. Vấn đề này dẫn tới việc tìm kiếm (search) một
mẫu (pattern) như một từ khóa trong văn bản viết tay ở dạng tài liệu ảnh quét.
Người đề xuất ra hướng tiếp cận này là Manmatha trong nghiên cứu [26] năm 1996.
Báo cáo khoa học của nhóm này đã trình bày sơbộ các kĩ thuật so khớp và phương
thức cắt tỉa5, giúp loại bỏ các thành phần không phù hợp cho việc so khớp và giữ
lại những đặc trưng cơ bản của một từ. Dữ liệu thực nghiệm được gồm 10 trang
lấy trong tập tài liệu của George Washington tại [24].
4
Viết tắt của Support Vector Machine là một khái niệm trong thống kê và khoa học máy tính cho một tập
hợp các phương pháp học có giám sát liên quan đến nhau để phân loại và phân tích hồi quy.
5
Từ tiếng Anh là Pruning
3
Sự đổi khác trong cách tiếp cận này là không hướng đến việc nhận diện từng
ký tự chữ cái rời rạc, thay vào đó phân tách các từ/cụm từ và so khớp sự tương
đồng với mẫu tìm kiếm theo đặc trưng tiêu biểu của bản thân nó. Đây là một kỹ
thuật mới được đánh giá là dễ và hiệu quả hơn kỹ thuật OCR, trong lĩnh vực xử lý
văn bản viết tay.
Mô hình tổng quan của nghiên cứu
Để giải quyết bài toán đặt ra thì có rất nhiều công đoạn và thao tác phải thực
hiện. Tuy nhiên có một số vấn đề chính cần giải quyết là:
Vấn đề tiền xử lý văn bản viết tay, khi gặp các trường hợp hình ảnh văn bản
sau giai đoạn số hóa (scan hoặc chụp) bị phát sinh nhiễu (nhiễu muối tiêu), cũng
nhưvết mực của chữ viết bị mờ hoặc các vết bẩn xuất hiện trong các trang tài liệu
lâu năm. Bằng các phép lọc và phân ngưỡng cơ bản trong xử lý hình ảnh, nghiên
cứu sẽ chỉ ra một quy tắc xử lý chung khi gặp các trường hợp nêu trên.
Vấn đề tách dòng, khi văn bản viết với độ nghiêng vừa phải, trong trường
hợp hai dòng chạm nhau và trường hợp có một dòng nào đó trong văn bản không
xuất hiện từ cực trái ảnh đến cực phải ảnh. Các trường hợp này sẽ được giải quyết
bằng phương pháp chia ảnh thành các cột và thực hiện đếm số lượng điểm ảnh
theo chiều dọc kết hợp với việc xác định thành phần liên thông.
Vấn đề tách từ, các từ và cụm từ được viết liên tục với nhau gây khó khăn và
nhầm lẫn trong quá trình tách. Hơn thế nữa, sự đa dạng trong cách viết như: Cỡ
chữ, khoảng cách giữa các từ cũng ảnh hưởng đến việc tách chính xác. Để giải
quyết vấn đề này, nghiên cứu sử dụng phương pháp đếm số lượng điểm ảnh theo
chiều ngang kết hợp với các thông tin về phân bố và tính liên tục của các điểm ảnh
đen để tìm ra điểm phân tách từ hợp lý.
Vấn đề trích chọn đặc trưng, Word Profile và Projection Profile là hai dạng
đặc trưng chính sẽ được sử dụng trong nghiên cứu. Hai đặc trưng này dựa trên hình
thái của từ nên sẽ rất nhạy cảm; sự nhạy cảm này thể hiện rõ ở sự sai lệch về
4
nghiêng - skew 6 của từ. Vì vậy, đòi hỏi thêm một quá trình chuẩn hóa xoay
nghiêng cho các unigram từ. Phép biến đổi Hough và nghiên cứu [5] có phải chăng
là sự lựa chọn thích hợp! Trong nghiên cứu này, sử dụng các giá trị AST và CoM
tại [5] đóng vai trò là các giá trị xác định đường gạch ngang và độ nghiêng (skew)
của từ.
Vấn đề so khớp độ tương đồng, So với các giải thuật so khớp như XOR,
SSD7, SLH8, EDM9 [23], SC10 [4], CORR [35], thì Dynamic Time Warping đã tỏ
ra vượt trội về mặt hiệu quả [32] [33] [34]. Tuy vậy, có một điểm cần lưu ý về tốc
độ tính toán, cũng nhưkích thước của dữ liệu đầu vào của giải thuật.
So sánh và đánh
giá kết quả
Tiền xử lý
Phân tách theo
dòng, từ
Gom cụm với PAM
Rút trích đặc trưng
unigram
Tính toán độ đương
đồng DTW, EDM
Hình 1.1: Mô hình tổng quan của nghiên cứu
6
Slant chỉ độ nghiêng đặc trưng của người viết, Skew chỉ độ nghiêng toàn cục của từ đó xuất hiện khi số
hóa hoặc do thói quen viết của người đó
7
Viết tắt của từ the Sum of Squared Differences
8
Viết tắt của từ Scott and Longuet Higgins
9
Viết tắt của từ Euclidean Distance Mapping
10
Viết tắt của từ Shape Content
5
- Xem thêm -