Đăng ký Đăng nhập
Trang chủ 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 Ti...

Tài liệu 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

.PDF
111
374
70

Mô tả:

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 -

Tài liệu liên quan