Tài liệu Tách và nhận dạng số viết tay trong phiếu nhập dữ liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THANH PHÚC TÁCH VÀ NHẬN DẠNG SỐ VIẾT TAY TRONG PHIẾU NHẬP DỮ LIỆU LUẬN VĂN THẠC SĨ Hà Nội – 2008 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THANH PHÚC TÁCH VÀ NHẬN DẠNG SỐ VIẾT TAY TRONG PHIẾU NHẬP DỮ LIỆU Ngành: Công nghê ̣ Thông tin Chuyên ngành: Công nghệ Phần mềm Mã số: 60 48 10 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. Ngô Quốc Tạo Hà Nội – 2008 i MỤC LỤC MỤC LỤC .................................................................................................................. i MỘT SỐ THUẬT NGỮ ANH-VIỆT ...................................................................... iii DANH MỤC HÌNH VẼ ........................................................................................... iv DANH MỤC BẢNG................................................................................................. vi MỞ ĐẦU ................................................................................................................... 1 1.1 Đặt vấn đề .......................................................................................................... 1 1.2 Nội dung và cấu trúc của khóa luận .................................................................... 3 Mở đầu ................................................................................................................. 3 Chương 1: Đề xuất giải pháp tiền xử lý ảnh .......................................................... 4 Chương 2: Đề xuất giải pháp phân vùng và nhận dạng ảnh ................................... 4 Chương 3: Xây dựng hệ thống tích hợp ................................................................ 5 Chương 4: Thực nghiệm ....................................................................................... 5 Kết luận ................................................................................................................ 5 CHƢƠNG 1 – ĐỀ XUẤT GIẢI PHÁP TIỀN XỬ LÝ ẢNH ................................... 6 1.1 Lọc nhiễu và nhị phân hoá. ................................................................................. 6 Mô tả thuật toán.................................................................................................... 6 1.2 Xác định góc nghiêng của ảnh .......................................................................... 11 1.2.1 Phương pháp xác định góc nghiêng dựa trên phép chiếu. ........................... 13 1.2.2 Phương pháp xác định góc nghiêng dựa trên các block. ............................. 18 CHƢƠNG 2 – ĐỀ XUẤT GIẢI PHÁP PHÂN VÙNG VÀ NHẬN DẠNG ẢNH . 21 2.1 Tách vùng nhập dữ liệu trên ảnh ....................................................................... 21 2.1.1 Đặc trưng bài toán...................................................................................... 21 2.1.2 Xác định vùng nhập liệu dựa trên các mốc quy chiếu ................................. 22 2.1.3 Xác định vùng dựa vào vị trí tương đối đến các các mốc quy chiếu trên form ........................................................................................................................... 23 2.1.4 Xác định vùng nhận dạng dựa trên vị trí tương đối đến các đường thẳng ... 29 2.2 Nhận dạng vùng nhập liệu ................................................................................ 42 2.2.1 Nhận dạng vùng đánh dấu .......................................................................... 43 2.2.2 Nhận dạng vùng nhập liệu dạng số ............................................................. 48 CHƢƠNG 3 - XÂY DỰNG HỆ THỐNG TÍCH HỢP .......................................... 55 3.1 Phân tích bài toán ............................................................................................. 55 3.2 Xây dựng hệ thống ........................................................................................... 62 3.2.1 Xác định các đối tượng .............................................................................. 62 3.2.2 Mô hình khái niệm ..................................................................................... 63 3.2.3 Biểu đồ các quy trình thiết kế, nhận dạng ................................................... 67 CHƢƠNG 4 – THỰC NGHIỆM ............................................................................ 72 4.1 Môi trường thực nghiệm ................................................................................... 72 ii 4.2 Thực nghiệm về Lọc nhiễu, tách nền và tìm ngưỡng nhị phân hóa. ................... 72 4.3 Thực nghiệm về xác định góc nghiêng của ảnh dựa trên phép chiếu ................. 73 4.4 Thực nghiệm về xác định góc nghiêng của ảnh dựa trên block ......................... 75 4.5 Thực nghiệm về phân vùng ảnh dựa trên block................................................. 76 4.6 Thực nghiệm về phân vùng ảnh dựa trên đường thẳng ...................................... 77 4.6.1 Thực nghiệm 1: Xác định các đường thẳng ................................................ 77 4.6.2 Thực nghiệm 2: Tìm cặp các đường thẳng giữa ảnh scan với ảnh mẫu. ...... 78 4.6.3 Thực nghiệm 3: Xác định các vùng cần nhận dạng..................................... 78 4.6.4 Thực nghiệm 4: tìm kích thước trung bình trên ảnh.................................... 79 4.7 Thực nghiệm nhận dạng ................................................................................... 80 4.7.1 Thực nghiệm nhận dạng ô đánh dấu ........................................................... 80 4.7.2 Thực nghiệm nhận dạng số ........................................................................ 81 4.8 Thực nghiệm tích hợp các thành phần .............................................................. 81 KẾT LUẬN ............................................................................................................. 83 TÀI LIỆU THAM KHẢO ...................................................................................... 85 iii MỘT SỐ THUẬT NGỮ ANH-VIỆT Thuật ngữ Giải nghĩa Black run Tập hợp các điểm đen liên tiếp kề nhau theo chiều thẳng đứng hoặc theo chiều ngang trên ảnh Block Một hoặc một cụm các đối tượng được coi là liền kề nhau Bounding Box Hình hộp bao quanh một đối tượng hay một khối các đối tượng Deskew Khử nghiêng DPI Dots per inch – Số lượng các điểm trên một inch Form Recognition Nhận dạng form Object Là một tập hợp các điểm đen liền kề nhau để tạo nên một đối tượng như chữ cái, đường thẳng, điểm, … Region Extraction Tách vùng Resolution Độ phân giải Skewed Image Ảnh bị nghiêng iv DANH MỤC HÌNH VẼ Hình 1-1: Lƣợc đồ mức xám của ảnh .................................................................................. 7 Hình 1-2: Đồ thị biến đổi mức xám ..................................................................................... 8 Hình 1-3: Ảnh trƣớc (a) và sau biến đổi lần 1 (b) ............................................................... 9 Hình 1-4: (a) Ảnh scan; (b) Ảnh sau lần lọc thứ nhất; (c) Ảnh sau lần lọc cuối cùng; (d) Ảnh sau khi nhị phân hóa .......................................................................................... 11 Hình 1-5: (a) ảnh sau khi khử nhiễu và tách nền; (b) ảnh sau khi khử nghiêng ............. 12 Hình 1-6: (a)ảnh với góc nghiêng bằng không; (b) đồ thị của phép chiếu ngang trên ảnh (a) ................................................................................................................................ 13 Hình 1-7: (a) ảnh với góc nghiêng 50; (b) đồ thị của phép chiếu ngang trên ảnh (a) ....... 13 Hình 1-8: (a) Ảnh scan, các đƣờng màu đỏ là các đƣờng chiếu ở góc nghiêng θ. (b) Ảnh đƣợc xấp xỉ bởi các hình bình hành........................................................................... 15 Hình 1-9: (a) Ảnh scan. (b) (c) (d) Ảnh các đƣờng chiếu đen và trắng ở các góc nghiêng 2.5, -3.5, 2 .................................................................................................................... 15 Hình 1-10: (a) Ảnh scan. (b) Ảnh sau khi chính xác góc nghiêng .................................... 17 Hình 1-11: Một phần ảnh mẫu với các block ở lề phải ..................................................... 18 Hình 1-12: block trong mẫu và block bị nghiêng trong ảnh scan .................................... 19 Hình 1-13: (a) ảnh scan bị nghiêng; (b) các đối tƣợng tìm đƣợc trên ảnh; (c) sau khi loại các đối tƣợng quá lớn, bé; (d) sau khi loại các đối tƣợng rỗng; (e) sau khi loại các đối tƣợng không sát lề; (f) xấp xỉ đƣờng thẳng qua các block .................................. 20 Hình 2-1: form mẫu và các vùng nhập dữ liệu đƣợc định nghĩa...................................... 21 Hình 2-2: Form sau khi đƣợc in ra, điền thông tin và scan vào máy tính........................ 22 Hình 2-3: (a) ảnh gốc; (b) ảnh scan sau khi tiền xử lý ...................................................... 23 Hình 2-4: Nội suy block bị mất .......................................................................................... 25 Hình 2-5: Khoảng cách các block trong mẫu và trong ảnh scan...................................... 25 Hình 2-6: Tƣơng ứng các mốc quy chiếu trong ảnh scan và trong mẫu .......................... 26 Hình 2-7: Mốc quy chiếu gần nhất đến các vùng nhập liệu.............................................. 27 Hình 2-8: Vùng tìm kiếm đƣợc xác định trên ảnh ............................................................ 27 Hình 2-9: Vùng nhập liệu đƣợc sử dụng làm mốc quy chiếu ........................................... 28 Hình 2-10: Cập nhật khoảng cách đến mốc quy chiếu gần nhất ...................................... 28 Hình 2-11: (a)ảnh sau khi tiền xử lý; (b)ảnh sau khi lọc các black run ngắn theo chiều ngang (c) ảnh sau khi hợp cách black run dài theo chiều ngang; (d) ảnh sau khi lọc các black run ngắn theo chiều thẳng đứng (e)ảnh sau khi hợp các black run dài theo chiều thẳng đứng (f)các đƣờng thẳng xác định đƣợc trên ảnh ......................... 30 Hình 2-12: (a) đƣờng thẳng mờ và bị đứt doạn (b) đƣờng thẳng xác định đƣợc khi tính đến mật độ .................................................................................................................. 31 Hình 2-13: xác định nhầm đƣờng thẳng do phân bố không đều trên đƣờng................... 31 Hình 2-14: chia đƣờng thẳng thành các đoạn ngắn rồi tính mật độ trên các đoạn này .. 32 Hình 2-15: Ảnh cần xác định kích thƣớc font chữ trung bình ......................................... 36 Hình 2-16: Hình chữ nhật bao các đối tƣợng tìm đƣợc trên ảnh ..................................... 36 Hình 2-17: Hình chữ nhật bao quanh các đối tƣợng chữ tìm đƣợc trên ảnh................... 36 Hình 2-18: Đối tƣợng tạo bởi các black run ...................................................................... 37 v Hình 2-19: gán nhãn các đối tƣợng trên ảnh nhị phân ..................................................... 38 Hình 2-20: ảnh sau khi giảm bớt các điểm đen ................................................................. 39 Hình 2-21: Kết quả xác định các đối tƣợng ...................................................................... 40 Hình 2-22: Hình chữ nhật bao quanh các đôi tƣợng tìm đƣợc......................................... 40 Hình 2-23: (a) vùng nhập dữ liệu trên ảnh mẫu; (b) ảnh scan; (c) các đƣờng thẳng gần vùng nhập dữ liệu nhất; (d) kết quả tách vùng trên ảnh scan .................................. 42 Hình 2-24: Những kiểu vùng nhập dữ liệu giải quyết trong luận văn ............................. 43 Hình 2-25: Vùng đánh dấu trả lời câu hỏi trong bài thi trắc nghiệm .............................. 43 Hình 2-26: Kết quả phép chiếu theo chiều ngang ............................................................. 44 Hình 2-27: Các phân đoạn tiềm năng................................................................................ 45 Hình 2-28: Các phân đoạn đúng tìm đƣợc ........................................................................ 45 Hình 2-29: (a) Kết quả phép chiếu theo chiều dọc, (b) các phân đoạn tiềm năng, (c) các phân đoạn đúng tìm đƣợc .......................................................................................... 45 Hình 2-30: Vùng nhập số ................................................................................................... 48 Hình 2-31: (a) vùng tìm kiếm bị mất đƣờng bao; (b) vùng tìm kiếm đƣợc mở rộng ....... 48 Hình 2-32: Các đƣờng thẳng trong vùng .......................................................................... 49 Hình 2-33: Các đƣờng thẳng sau bƣớc 2........................................................................... 49 Hình 2-34: Các đƣờng thẳng sau bƣớc 3........................................................................... 49 Hình 2-35: Các đƣờng đứng xác định đƣợc sau bƣớc 4 ................................................... 49 Hình 2-36: Kết quả tách ô bởi các đƣờng thẳng bƣớc 3,4 ................................................ 50 Hình 2-37: Vùng nhập số trong mẫu và trong ảnh scan ................................................... 50 Hình 2-38: Ảnh trƣớc và sau khi lọc nhiễu ....................................................................... 51 Hình 2-39: Hình bao xác định đƣợc trên ảnh ................................................................... 51 Hình 2-40: Các nét cơ bản tạo nên số dạng nét thẳng ...................................................... 51 Hình 2-41: Các số mẫu từ 0 đến 9 ..................................................................................... 51 Hình 2-42: Các nét ngang .................................................................................................. 52 Hình 2-43: Các nét đứng .................................................................................................... 52 Hình 3-1: Mẫu form nhập liệu “Sample Dta Etry Form” ................................................ 57 Hình 3-2: Mẫu form nhập liệu “Sample Data Entry Form” có sử dụng block ............... 58 Hình 3-3: Mẫu form nhập liệu “Mẫu Dữ Liệu Số” với các block và vùng định danh form ..................................................................................................................................... 59 Hình 3-4: Mẫu form nhập liệu “Mẫu Phiếu Trả Lời Bài Thi Trắc Nghiệm” .................. 60 Hình 3-5: Mẫu form nhập liệu “Phiếu Đánh giá môn học”.............................................. 61 Hình 3-6: Mô hình khái niệm ............................................................................................ 64 Hình 3-7: Quy trình thiết kế mẫu phiếu............................................................................ 68 Hình 3-8: Vùng mã form trên ảnh..................................................................................... 69 Hình 3-9: Quy trình nhận dạng mẫu phiếu khi chƣa biết mã phiếu ................................ 70 Hình 3-10: Quy trình nhận dạng mẫu phiếu khi đã biết mã phiếu .................................. 71 Hình 4-2: Vùng cần xác định bị lệch so với vùng xác định thực tế .................................. 79 Hình 4-3: (a) Ảnh mẫu (b) Kết quả thu đƣợc sau khi phân vùng ................................... 79 Hình 4-1: (a) ảnh thử nghiệm; (b) Một phần của ảnh đƣợc phóng to.............................. 80 vi DANH MỤC BẢNG Bảng 1: Bảng phân loại ảnh............................................................................................... 72 Bảng 2: Lọc nhiễu .............................................................................................................. 73 Bảng 3: Góc nghiêng với ảnh 150DPI ............................................................................... 74 Bảng 4: độ lệch trung bình so với góc thực tế ................................................................... 74 Bảng 5: So sánh hiệu năng của phƣơng pháp phép chiếu tối ƣu với phƣơng pháp phép chiếu ............................................................................................................................ 75 Bảng 6: Kết quả xác định góc nghiêng bằng block ........................................................... 76 Bảng 7: Thời gian xâc định block ...................................................................................... 76 Bảng 8: Độ chính xác phƣơng pháp tách vùng dựa trên block ........................................ 77 Bảng 9: Độ chính xác của phƣơng pháp xác định đƣờng thẳng....................................... 77 Bảng 10: Độ chính xác của phƣơng pháp ghép cặp các đƣờng thẳng trong tập mẫu và tập ảnh mới ................................................................................................................. 78 Bảng 11: Độ chính xác phƣơng pháp tách vùng dựa trên đƣờng thẳng .......................... 79 Bảng 12: Kết quả xác định kích thƣớc trung bình của các đối tƣợng.............................. 80 Bảng 13: Thời gian xác định kích thƣớc trung bình ......................................................... 80 Bảng 14: Độ chính xác phƣơng pháp tách vùng dựa trên đƣờng thẳng .......................... 81 Bảng 15: Kết quả thực nghiệm nhận dạng số ................................................................... 81 Bảng 16: Kết quả thực nghiệm tích hợp............................................................................ 82 1 MỞ ĐẦU 1.1 Đặt vấn đề Nhận dạng là bài toán đã xuất hiện khá lâu và đã đạt được nhiều thành tựu. Tuy nhiên nhận dạng một văn bản bất kì bao gồm cả các văn bản có lẫn chữ viết tay hoặc hình ảnh luôn là một bài toán khó mà cho đến nay vẫn chưa thật sự có giải pháp hoàn chỉnh. Để giải quyết bài toán nhận dạng hiện đang có nhiều xu hướng tiếp cận khác nhau tương ứng với những loại văn bản khác nhau, trong đó nhập dữ liệu tự động là phương pháp tiếp cận về nhận dạng đối với các văn bản kiểu form nhập liệu. Càng ngày nhu cầu xử lý dữ liệu của con người trên máy tính càng tăng lên. Chính vì lý do đó bài toán nhập dự liệu tự động đang ngày càng thu hút được nhiều sự chú ý và đầu tư. Nó đã vượt ra ngoài khuôn khổ các lĩnh vực nghiên cứu và đang dần được áp dụng vào thực tế bởi khả năng áp dụng rộng rãi cùng những hiệu quả mà nó có thể mang lại. Trên thế giới, hiện đã có nhiều ứng dụng liên quan đến vấn đề nhận dạng văn bản hay nhập dữ liệu tự động. Có thể kể đến như : sản phẩm FineReader, Scan To Office của hãng ABBYY, Smart scan Xpress của Pegasus Image, các ứng dụng chấm thi tự động …Ở Việt Nam cũng đã có các ứng dụng nhận dạng văn bản như VNDocR của Viện Công nghệ Thông tin hay ImageScan của CardPro. Đây là các ứng dụng nhận dạng chữ in. Việc nhận dạng chữ viết tay đang còn là một thách thức. Đã có một số nghiên cứu về nhận dạng chữ viết tay và chữ viết tay tiếng Việt như đề tài "Ứng dụng mạng Neural trong nhận dạng văn bản"[1]. Tuy nhiên các nghiên cứu này vẫn còn rất nhiều hạn chế do khả năng nhận dạng chữ viết tay chưa đạt được độ chính xác cần thiết để có thể áp dụng trên thực tế một cách rộng rãi. Cùng với sự phát triển của công nghệ thông tin hiện nay, các thuật toán nhận dạng cũng ngày càng chính xác và đưa ra được các kết quả đáng tin cậy. Ngay cả đối với chữ viết tay cũng có thể đạt được độ chính xác cao với điều kiện là chỉ nhận dạng từng chữ riêng biệt và chữ viết đẹp. Với các văn bản thông thường ta khó có thể đạt được điều này. Tuy nhiên, Các form nhập liệu là kiểu văn bản có cấu trúc và ta có thể đưa ra một số quy tắc ràng buộc để tăng độ chính xác cho việc nhận dạng - chẳng hạn như: các chữ được viết riêng rẽ trên các ô riêng biệt của các vùng nhập liệu. Mặt khác, việc nhận dạng không cần thiết phải tiến hành trên toàn bộ ảnh của tài liệu mà chỉ giới hạn ở những vùng nhập dữ liệu. Đặc điểm này cũng cho phép ta tiếp cận bài toán một cách hiệu quả hơn, chẳng hạn có thể sử dụng các thông tin sẵn có từ form mẫu như định dạng vùng nhập liệu, kích thước ô,…làm tham số nhận dạng. Một khía cạnh khác của nhận dạng form nhập liệu là các dữ liệu nhận dạng được của mỗi vùng trên form sẽ phải được tự động gắn vào một trường dữ liệu xác định của ứng dụng. 2 Bài toán nhập liệu tự động từ form tài liệu bao gồm các vấn đề sau :  Quản trị form: thiết kế form nhập liệu ; quản lý và lưu trữ tự động các tham số của form để có thể cung cấp dữ liệu cho quá trình nhận dạng sau này nhanh chóng và tin cậy ; tích hợp với cơ sở dữ liệu.  Nhận dạng các vùng dữ liệu (bài toán phát hiện và phân vùng dữ liệu).  Nhận dạng chữ viết tay trên các vùng dữ liệu ; xử lý từ vựng và ghi nhận vào cơ sở dữ liệu.  Nhưng trước hết phải tiền xử lý ảnh để làm tốt ảnh, phục vụ cho quá trình nhận dạng, đảm bảo độ tin cây. Hình 0-1: Sơ đồ hệ thống Luận văn này chỉ giới hạn trình bày các giải pháp bao gồm các công việc cụ thể như sau :  tiền xử lý ảnh để làm tốt ảnh, phục vụ cho quá trình nhận dạng, đảm bảo độ tin cậy. - Thuật toán lọc nhiễu, khử nền và nhị phân hóa ảnh. - Thuật toán xác định góc nghiêng dựa trên phép chiếu. - Thuật toán xác định góc nghiêng dựa trên các block.  Tách các vùng nhập dữ liệu (bài toán phát hiện và phân vùng dữ liệu). - Thuật toán xác định các đường thẳng trong văn bản phục vụ cho việc xác định các vùng nhận dạng. 3 - Phân vùng ảnh dựa trên các đường thẳng xác định được. - Phân vùng ảnh dựa trên vị trí tương đối đến các mốc quy chiếu.  Nhận dạng các vùng nhập liệu. - Nhận dạng số viết tay dạng nét thẳng. - Nhận dạng các ô đánh dấu.  Quản trị form - Thiết kế form nhập liệu. - Quản lý và lưu trữ tự động các tham số của form để có thể cung cấp thông tin cho quá trình nhận dạng sau này nhanh chóng và tin cậy ; hỗ trợ các thông tin để tích hợp với cơ sở dữ liệu. 1.2 Nội dung và cấu trúc của khóa luận Hệ thống mà tôi thực hiện như đã giới thiệu ở trên là bài toán xác định dữ liệu được nhập vào form sau khi có ảnh từ máy quét. Quy trình xử lý bao gồm : tiền xử lý ảnh, phân vùng ảnh, nhận dạng ảnh và quản trị form. Nắm bắt được khó khăn cũng như những đặc trưng của bài toán này, hệ thống được xây dựng đã áp dụng các giải pháp có độ chính xác cao, phù hợp với đặc trưng ảnh của form nhập dữ liệu với các giả thiết, ràng buộc của loại ảnh này sẽ được nêu cụ thể ở từng chương tương ứng. Với nội dung chính là trình bày những lý thuyết cơ bản về xử lý ảnh, về các bước trong quy trình xử lý của hệ thống và lựa chọn các giải pháp áp dụng vào bài toán, khóa luận được tổ chức như sau : Mở đầu Phần mở đầu giới thiệu về bài toán nhập dữ liệu tự động nói chung: tình hình Việt Nam và thế giới, các thành tựu đã đạt được trong lĩnh vực nhận dạng chữ viết, những khó khăn cũng như các đặc trưng của bài toán nhận dạng form nhập dữ liệu so với các bài toán nhận dạng khác. Phần tiếp theo giới thiệu về hệ thống mà tôi đang tiến hành nghiên cứu và xây dựng : Tách và nhận dạng số viết tay trong phiếu nhập dữ liệu cùng với quy trình nhập dữ liệu tự động bằng nhận dạng quang học, phạm vi giới hạn và trình tự giải quyết bài toán. Từ đó nêu lên nội dung mà tôi nghiên cứu và thực hiện thông qua việc trình bày nội dung và cấu trúc của khóa luận. 4 Chƣơng 1: Đề xuất giải pháp tiền xử lý ảnh Chương này trình bày về các phần việc chính liên quan đến tiền xử lý ảnh trong hệ thống đó là : Giải pháp lọc nhiễu, khử nền và nhị phân hóa thông qua giãn độ tương phản kết hợp loại bỏ nền lặp lại nhiều lần trên lược đồ histogram; Giải pháp cho việc khử nghiêng ảnh bằng phép chiếu, bằng các block với các biện pháp tối ưu hóa và xác định ảnh ngược. Nội dung của chương tập trung vào:  Phân tích những đặc trƣng của ảnh dạng form nhập liệu từ đó đưa ra giải pháp cho việc tiền xử lý ảnh.  Quy trình thực hiện các giải pháp này.  Đánh giá ưu và nhược điểm của các phương pháp. Chƣơng 2: Đề xuất giải pháp phân vùng và nhận dạng ảnh Chương này trình bày về các giải pháp tách vùng nhập liệu trên ảnh dựa vào các thông tin cung cấp bởi các form mẫu. Tập trung vào hai hướng chính là xác định vị trí các vùng theo tọa độ tương đối từ các đường thẳng trên form và từ các mốc quy chiếu. Sau khi tách các vùng nhập liệu trên ảnh, các vùng này sẽ được nhận dạng. Trong khuôn khổ luận văn chỉ trình bày về nhận dạng số viết tay dạng nét thẳng và các ô đánh dấu là các đối tượng nhập liệu phổ biến nhất. Nội dung của chương tập trung vào:  Phân tích những đặc trƣng của ảnh dạng form nhập liệu từ đó đưa ra giải pháp cho việc tách vùng và nhận dạng.  Xác định các đối tượng làm mốc quy chiếu trên ảnh( đường thẳng, các block bên cạnh form).  Tách vùng nhập liệu.  Nhận dạng số viết tay và các ô đánh dấu.  Đánh giá ưu và nhược điểm của các phương pháp. 5 Chƣơng 3: Xây dựng hệ thống tích hợp Chương 4 trình bày về module quản trị form nhập liệu cho các nhóm form với các đặc điểm mà các giải pháp ở các chương trước hướng đến. Nội dung của chương tập trung vào:  Giới thiệu đặc trƣng của các form nhập liệu mà luận văn này tập trung giải quyết.  Thiết kế form nhập liệu.  Quản lý và lưu trữ tự động các tham số của form để có thể cung cấp thông tin cho quá trình nhận dạng ảnh sau này nhanh chóng và tin cậy ; hỗ trợ các thông tin để tích hợp với cơ sở dữ liệu. Chƣơng 4: Thực nghiệm Chương 5 mô tả chi tiết quá trình thực nghiệm với các giải pháp đề xuất trong luận văn cùng với thực nghiệm về hệ thống chung. Đồng thời chương cũng đề cập đến quá trình thu thập và xây dựng cơ sở dữ liệu ảnh dạng form sử dụng cho thực nghiệm. Kết luận Tổng kết lại những kết quả đạt được và chưa đạt được trong quá trình nghiên cứu và thực hiện khóa luận. Từ đó nêu lên những kết quả cần hướng tới và hướng nghiên cứu, phát triển trong tương lai. 6 CHƯƠNG 1 – ĐỀ XUẤT GIẢI PHÁP TIỀN XỬ LÝ ẢNH Sau khi nhận được ảnh từ máy quét, ảnh thu được có thể bị nghiêng do đặt lệch giấy trong quá trình quét hoặc có thể có nhiễu nền. Những nguyên nhân này làm cho các vùng nhập liệu trên ảnh bị thay đổi vị trí, biến dạng. Do đó tiền xử lý là một bước rất quan trọng, tạo tiền đề để có thể nhận dạng ảnh chính xác và hiệu quả. Các giải pháp được áp dụng trong hệ thống bao gồm : lọc nhiễu và nhị phân hóa [3], xác định góc nghiêng dựa trên phép chiếu [3] và xác định góc nghiêng dựa trên các block. 1.1 Lọc nhiễu và nhị phân hoá. Thông thường văn bản được quét và lưu trữ dưới dạng ảnh đa mức xám trong khi đó hầu hết các thuật toán về xử lý và phân tích văn bản đều dựa trên ảnh nhị phân. Việc sử dụng ảnh nhị phân chỉ với hai mức trắng và đen giảm bớt được khối lượng tính toán và đơn giản hoá các phương pháp phân tích so với ảnh xám( 256 mức). Do vậy việc tìm ra một thuật toán nhị phân hóa nhanh và hiệu quả là một điều rất cần thiết Nhiều phương pháp về nhị phân hóa ảnh đã được phát triển, trong số đó có những phương pháp đem lại kết quả rất tốt. Có thể kể đến như thuật toán dựa trên sự biến thiên về cường độ mức xám ở các vùng khác nhau của văn bản [24], thuật toán về tính ngưỡng nhị phân cục bộ [18] hay thuật toán dựa trên đa độ phân giải [17] … Tuy nhiên các phương pháp này thường áp dụng đối với những hình ảnh tổng quát và đòi hỏi tính toán phức tạp bởi vì đều phải tính đến cấu trúc của ảnh. Trong bài toán này, chúng tôi chỉ xử lý trên các văn bản kiểu form nhập liệu, vốn dĩ là các ảnh đơn giản chỉ gồm hai mức đen (để thể hiện chữ) và trắng (nền của văn bản); văn bản cũng thường phân bố khá đồng đều. Chính vì vậy việc nhị phân hóa ảnh có thể được thực hiện chỉ dựa trên lược đồ xám của ảnh mà không phụ thuộc vào cấu trúc. Trên cơ sở này, chúng tôi đã kết hợp các kỹ thuật thực hiện nhiều lần tăng cường độ tương phản bằng cách điều chỉnh mức xám, phân ngưỡng tự động để nhị phân hoá ảnh. Mô tả thuật toán Ảnh của văn bản gốc vốn dĩ là ảnh nhị phân, tức là chỉ có hai ngưỡng đen, trắng cho chữ và nền. Song sau khi in ra và quét lại vào máy tính, nó trở thành ảnh đa mức xám tức là có 256 ngưỡng khác nhau. Một số vùng nền có thể xám hơn, ngược lại một số đối tượng chữ, bảng và dòng kẻ có thể mờ đi. Nhiệm vụ của chúng ta ở đây là tách các đối tượng cần xử lý ra khỏi hình nền. Thuật toán được xây dựng dựa trên giả thiết tổng diện tích của hình( chữ và đối tượng trên form) so với diện tích ảnh là nhỏ ,và tuy có sự biến đổi về ngưỡng nhưng vẫn có sự khác biệt tương đối giữa ngưỡng của chữ và của nền. Thông qua việc 7 tăng cường độ tương phản lặp lại nhiều lần, ta hi vọng rằng có thể khuyếch đại sự khác biệt này một cách đáng kể. Ảnh là một tập các điểm ảnh, được biểu diễn bởi công thức : I  x, y   n  n [0,255] Công thức 1-1 Trong đó x,y là các trục tọa độ của ảnh và n có thể lấy bất kì giá trị nào trong khoảng [0, 255]. Khi n = 255 thì đó là điểm trắng, n = 0 thì đó là điểm đen. Khi đó giá trị trung bình của mức xám là: x W y  H T   I ( x, y ) x 0 y 0 W H  W : Width   H : Height Công thức 1-2 Hình 1-1: Lƣợc đồ mức xám của ảnh Với giả định rằng tổng số lượng điểm ảnh biểu diễn cho chữ và các đối tượng chứa thông tin là nhỏ so với kích cỡ của ảnh, và các điểm ảnh này cũng có mức xám nhỏ hơn so với các điểm ảnh nền, chúng tôi cho rằng giá trị trung bình của mức xám của ảnh được quyết định bới các điểm ảnh nền. Dựa trên giả thiết này, để tăng độ tương phản của ảnh – tức là làm tăng độ nổi của các điểm ảnh chứa thông tin so với nền, chúng tôi coi như tất cả các điểm ảnh có mức xám lớn hơn giá trị của mức xám trung bình là các điểm ảnh nền và đặt lại mức xám của chúng là 255 (trắng). Sau bước biến đổi này ta thu được một ảnh mới: I ' ( x, y)  n' (n' [0, T ]  {255}) Công thức 1-3 8 Tiếp đó để tăng cường độ tương phản của ảnh sau khi chọn T là ngưỡng để tách nền, ta tăng cường độ tương phản của ảnh mới thông qua việc giãn khoảng của mức xám [2] của các điểm ảnh có mức xám nhỏ hơn mức xám trung bình từ [0,T] lên [0,255] n1  f ( n ') f ( n ')  255.n ' T Công thức 1-4 Cuối cùng ta thu được ảnh mới : I1 ( x, y)  n1 (n1  [0,255]) Công thức 1-5 Hình 1-2: Đồ thị biến đổi mức xám 9 Hình 1-3: Ảnh trƣớc (a) và sau biến đổi lần 1 (b) Công việc trên được thực hiện lặp đi lặp lại cho đến khi hình ảnh đạt được đến một độ sạch cần thiết. Điều kiện kết thúc là khi mức xám trung bình của ảnh trước và sau khi biến đổi không thay đổi. Ta có thể tóm tắt quy trình lọc nhiễu như sau : Bƣớc 1 : Tính giá trị trung bình T W Tk  H  I ( x, y) x 0 y 0 k W H Công thức 1-6 Bƣớc 2 : Loại nền cho ảnh dựa vào Tk  I ( x, y ) I k' ( x, y )   k 255 Công thức 1-7 Bƣớc 3 : Tăng độ tương phản cho ảnh mới I k ( x, y )  Tk I k ( x, y)  Tk 10 I k 1  f ( I k' ) Công thức 1-8 Bƣớc 4 : Lặp lại bước 1 cho tới khi giá trị T giữa 2 lần lọc liên tiếp nhau là gần như nhau Với cách lọc trực tiếp trên ảnh ở trên, thì tiếp chi phí tính toán cho phương pháp lọc này chủ yếu tập trung vào chi phí tính toán ở Tk và Ik+1. Trong công thức tính Tk, giá trị của Tk chỉ phụ thuộc vào giá trị của Ik(x,y) chứ không phụ thuộc vào vị trí. Nếu ta lưu lại được giá trị này thì sẽ không cần đọc lại ảnh trong mỗi bước lặp. Để giảm chi phí tính toán cho phép lọc này chúng ta chỉ tính lược đồ histogram của ảnh, sau đó tất cả các tính toán đều thực hiện trên lược đồ histogram với 256 phần tử( so với 1241x1755 điểm ảnh của ảnh trang A4 scan với độ phân giải 150DPI). Phép lọc ảnh được thực hiện nhiều lần chỉ trên lược đồ mức xám và cuối cùng mới thực hiện phép biến đổi tăng độ tương phản( công thức 2-7) cho ảnh cuối Ifinal. Ta có thể hình dung các bước thực trên lược đồ mức xám như sau:  Bước 1 : Xác định lược đồ mức xám của ảnh  Bước 2 : Tính giá trị trung bình Tk, dựa vào lược đồ mức xám  Bước 3 : Biến đổi lược đồ mức xám dựa trên Tk  Bước 4 : Lặp lại bước 2, cho tới khi Tk và Tk-1 gần như nhau.  Bước 5 : Thực hiện điều chỉnh độ tương phản cho ảnh gốc cuối cùng dựa trên kết quả của lược đồ mức xám ở bước cuối. Sau cùng, khi ảnh đã được lọc nền và làm sạch, ta tiến hành nhị phân hóa ảnh. Ngưỡng nhị phân được chọn là: 3 Threshold  T final  10 N 4 Công thức 1-9 Trong đó Tfinal là mức xám trung bình trong bước biến đổi cuối cùng, N là số bước thực hiện biến đổi. 11 Ta thu được ảnh đã lọc nhiễu và nhị phân hóa như trong hình vẽ Hình 1-4: (a) Ảnh scan; (b) Ảnh sau lần lọc thứ nhất; (c) Ảnh sau lần lọc cuối cùng; (d) Ảnh sau khi nhị phân hóa Dựa trên kết quả thực nghiệm sau khi áp dụng thuật toán đối với 60 form văn bản thuộc về 4 loại khác nhau, chúng tôi thấy rằng kết quả thu được hoàn toàn có thể so sánh với kết quả của các thuật toán khác. Thời gian để nhị phân hóa ảnh có độ phân giải là 300 DPI với 10 lần lặp chỉ là 66 ms. Điều này chứng minh rằng thuật toán có thể áp dụng rất hiệu quả khi ta cần xử lý văn bản với số lượng lớn. 1.2 Xác định góc nghiêng của ảnh Văn bản bị nghiêng xảy ra trong quá trình copy hoặc khi quét vào máy tính, điều này ảnh hưởng đến toàn bộ các đối tượng có trong văn bản nhất là các vùng mà ta cần phải nhận dạng. Văn bản bị nghiêng là một điều không thể tránh khỏi, và trong nhiều trường hợp gây ảnh hưởng không tốt đến độ chính xác đối với kết quả phân vùng và nhận dạng ký tự. Cũng có một số phương pháp về phân vùng ảnh không yêu cầu văn bản phải có góc nghiêng bằng không [5, 25]. Tuy nhiên các phương pháp này vẫn đòi hỏi góc nghiêng của văn bản nằm trong một khoảng giới hạn cho phép. Bên cạnh đó, đơn giản hóa vấn đề này sẽ dẫn tới phức tạp hóa cũng như tốn thời gian xử lý đối với các nhiệm vụ khác. Do đó chính xác lại góc nghiêng của ảnh là một việc làm tất yếu và phải được thực hiện trước khi tiến hành phân vùng và nhận dạng ảnh. 12 Hình 1-5: (a) ảnh sau khi khử nhiễu và tách nền; (b) ảnh sau khi khử nghiêng Các văn bản có rất nhiều đặc trưng khác nhau như đặc trưng về hướng, về cấu trúc phân bố các đối tượng... Từ đó cũng có một số phương pháp xác định góc nghiêng cho ảnh của văn bản tương ứng như các phương pháp dựa trên phép biến đổi Hough [9,19,14,29,34], hàng xóm gần nhất( Nearest Neighbour) [7,30,37], phép chiếu [6,8,22,36] , đối tượng liên kết [28,31], và một số phương pháp khác [10,15,32,38]. Mỗi phương pháp có một cách tiếp cận khác nhau cùng những ưu điểm và nhược điểm nhất định. Một số phương pháp có khả năng tìm góc nghiêng trong khoảng [-50,+50] cho đến [-450,+450]. Một số phương pháp khác cho phép tìm góc nghiêng bất kỳ đối với nhiều loại văn bản đa dạng và phức tạp. Bên cạnh đó còn một số phương pháp đặc thù như sử dụng đường thẳng dày [4], sử dụng khung [11] …Các phương pháp này gắn chặt với một vài loại form văn bản nhất định đã được định nghĩa từ trước. Góc nghiêng tìm được thông qua việc tìm các đối tượng đánh dấu trên form. Trong bài toán mà ta đang xem xét, khi nhận dạng để nhập dữ liệu tự động, ta thu được một tập ảnh của cùng một loại form mẫu để nhận dạng, thông thường là qua quét ảnh theo lô. Góc nghiêng của ảnh chỉ có thể lên đến nhiều nhất là ±200. Cộng với cấu trúc của không quá phức tạp và yêu cầu về tốc độ xử lý. Do đó tôi đã lựa chọn hai phương pháp trình bày dưới đây khi xây dựng hệ thống, những phương pháp này tuy còn một số hạn chế nhưng phù hợp với đặc trưng ảnh của bài toán, cho thời gian tính toán nhanh và chính xác.