Tài liệu Nghiên cứu một số kỹ thuật hiệu chỉnh form tài liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC LẠC HỒNG *** NGUYỄN MINH AN NGHIÊN CỨU MỘT SỐ KỸ THUẬT HIỆU CHỈNH FORM TÀI LIỆU Luận văn Thạc sỹ Công nghệ Thông tin ĐỒNG NAI, 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC LẠC HỒNG *** NGUYỄN MINH AN NGHIÊN CỨU MỘT SỐ KỸ THUẬT HIỆU CHỈNH FORM TÀI LIỆU Chuyên ngành: Công nghệ Thông tin Mã số: 60.48.02.01 Luận văn Thạc sỹ Công nghệ Thông tin Người hướng dẫn khoa học: PGS. TS ĐỖ NĂNG TOÀN ĐỒNG NAI, 2013 LỜI CẢM ƠN Trước hết tôi xin gởi lời cảm ơn chân thành tới thầy PGS.TS Đỗ Năng Toàn, người thầy hướng dẫn khoa học, định hướng nghiên cứu và tận tình hướng dẫn cho tôi trong suốt quá trình làm luận văn. Nếu không có thầy, tôi khó có thể hoàn thành luận văn này. Bên cạnh đó, tôi cũng muốn gửi lời cảm ơn đến các thầy cô đang làm việc tại khoa Công nghệ Thông tin trường Đại học Lạc Hồng đã quan tâm chỉ bảo và trực tiếp giảng dạy lớp cao học khóa 3. Tôi xin chân thành cảm ơn Ban giám hiệu trường THCS Phú Mỹ Hưng đã tạo điều kiện thuận lợi và hỗ trợ cho tôi trong việc thu thập số liệu của trường để phục vụ cho nhu cầu luận văn. Cuối cùng, tôi xin cảm ơn gia đình và bạn bè, đặc biệt là thành viên của lớp CHK3 – Đại học Lạc Hồng - những người đã luôn ủng hộ và động viên để tôi yên tâm nghiên cứu và hoàn thành luận văn. Nguyễn Minh An LỜI CAM ĐOAN Tôi xin cam đoan luận văn: “Nghiên cứu một số kỹ thuật hiệu chỉnh form tài liệu” là kết quả quá trình học tập, nghiên cứu khoa học độc lập, nghiêm túc. Các số liệu trong luận văn là trung thực, có nguồn gốc rõ ràng, được trích dẫn và có tính kế thừa, phát triển từ các tài liệu, tạp chí, các công trình nghiên cứu đã được công bố, các website, … Các phương pháp nêu trong luận văn được rút ra từ những cơ sở lý luận và quá trình nghiên cứu tìm hiểu của tác giả. Đồng Nai, tháng 06 năm 2013 Tác giả Nguyễn Minh An TÓM TẮT LUẬN VĂN Một tệp tin ảnh sau khi scan để nhận dạng thành văn bản số thì giai đoạn tiền xử lí như lọc nhiễu, hiệu chỉnh độ nghiêng, hiệu chỉnh độ lệch là nhu cầu cần thiết. Về kỹ thuật lọc nhiễu, luận văn giời thiệu các kỹ thuật lọc tuyến tính và phi tuyến tính. Hiệu chỉnh độ dịch chuyển giới thiệu kỹ thuật so sánh histogram. Về phương pháp khử nghiêng, luận văn tìm hiểu các phương pháp phân tích hình chiếu, biến đổi Hough, phân tích láng giềng và phép toán hình thái. Các thuật toán nghiên cứu trong luận văn được áp dụng vào hiệu chỉnh form điểm tại trường THCS Phú Mỹ Hưng và bước đầu thu được những kết quả nhất định. MỤC LỤC LỜI CẢM ƠN LỜI CAM ĐOAN TÓM TẮT LUẬN VĂN MỤC LỤC PHẦN MỞ ĐẦU ............................................................................................................. - 1 Chƣơng 1: KHÁI QUÁT FORM TÀI LIỆU VÀ BÀI TOÁN HIỆU CHỈNH FORM TÀI LIỆU ........................................................................................................................ - 4 1.1. Khái quát về Form tài liệu ............................................................................. - 4 1.1.1. Form tài liệu là gì? ................................................................................. - 4 1.1.2. Phân loại form tài liệu ............................................................................ - 4 1.1.2.1. Ảnh trắng, đen ............................................................................ - 4 1.1.2.2. Ảnh màu ..................................................................................... - 4 1.2. Thu nhận và biểu diễn form tài liệu .............................................................. - 5 1.2.1. Thu nhận form tài liệu ............................................................................ - 5 1.2.2. Cấu trúc Form tài liệu ............................................................................ - 5 1.2.2.1. Mào đầu tệp(Header) .................................................................. - 5 1.2.2.2. Dữ liệu nén (Data Compression) ................................................ - 5 1.2.2.3. Bảng màu (Palette color) ............................................................ - 5 1.2.3. Một số phương pháp biểu diễn Form tài liệu ......................................... - 5 1.2.3.1. Mã loạt dài (Run – Length code)................................................ - 5 1.2.3.2. Mã xích (Chain Code) ................................................................ - 6 1.2.3.3. Mã tứ phân (Quad Tree Code) ................................................... - 7 1.3. Bài toán hiệu chỉnh Form tài liệu .................................................................. - 7 1.3.1. Một số vấn đề trong hiệu chỉnh form tài liệu ......................................... - 7 1.3.2. Một số cách tiếp cận trong hiệu chỉnh form tài liệu ............................... - 7 1.3.2.1. Nhiễu form tài liệu ..................................................................... - 7 1.3.2.2. Khử nhiễu ................................................................................... - 8 - Chƣơng 2: HIỆU CHỈNH FORM TÀI LIỆU ............................................................ - 15 2.1 Độ dịch chuyển của form tài liệu ................................................................. - 15 2.1.1 Giới thiệu.............................................................................................. - 15 2.1.2 Phát hiện độ dịch chuyển của form tài liệu .......................................... - 16 2.1.3 Hiệu chỉnh độ dịch chuyển form tài liệu .............................................. - 17 2.1.3.1 Phương pháp thứ nhất ............................................................... - 19 2.1.3.2 Phương pháp thứ hai ................................................................. - 20 2.2 Độ nghiêng của form tài liệu ........................................................................ - 22 2.2.1 Giới thiệu.............................................................................................. - 22 2.2.2 Một số thuật toán và phát hiện góc nghiêng văn bản ........................... - 23 2.2.2.1 Thuật toán dựa vào phân tích hình chiếu (Projection Profile) . - 23 2.2.2.2 Các thuật toán dựa vào biến đổi Hough (Hought Transform) .. - 28 2.2.2.3 Các thuật toán phân tích láng giềng (nearest Neighbour Clustering) ................................................................................................. - 35 2.2.2.4 Phương pháp dùng phép toán hình thái ..................................... - 41 Chƣơng 3: CHƢƠNG TRÌNH THỬ NGHIỆM ........................................................ - 48 3.1. Bài toán .......................................................................................................... - 48 3.2. Phân tích bài toán ......................................................................................... - 48 3.2.1. Module File .......................................................................................... - 49 3.2.2. Module Basic ....................................................................................... - 50 3.2.3. Module Filter ........................................................................................ - 51 3.2.4. Module Skew Detection ....................................................................... - 51 3.3. Một số kết quả hiệu chỉnh form tài liệu ...................................................... - 52 PHẦN KẾT LUẬN ....................................................................................................... - 60 TÀI LIỆU THAM KHẢO PHỤ LỤC (Một số định dạng form tài liệu) P.1. Định dạng ảnh IMG P.2. Định dạng ảnh PCX P.3. Định dạng ảnh TIFF P.4. Định dạng ảnh GIF P.5. Định dạng ảnh Bitmap DANH MỤC HÌNH, BẢNG Hình 1.1. Ảnh nhị phân và các biểu diễn mã loạt dài tương ứng. .................................. -6Hình 1.2: Minh hoạ mã xích ........................................................................................... -7Hình 1.3. Các toán tử gờ sai phân. ............................................................................... -12Hình 1.4. Sơ đồ bộ lọc thông cao. ................................................................................ -13Hình 1.5. Một số nhân chập trong lọc thông cao. ........................................................ -13Hình 1.6. Bảng điểm qua lọc thông cao ....................................................................... -14Hình 2.1. Bảng điểm bị dịch chuyển sau khi scan. ...................................................... -15Hình 2.2. Mô hình histogram dọc của bảng điểm mẫu. ................................................ -16Hình 2.3. Mô hình histogram dọc của bảng điểm cần nhận dạng. ................................ -16Hình 2.4. Mô hình histogram của bảng điểm mẫu và bảng điểm cần nhận dạng được xếp trên cùng một trục tọa độ............................................................................. -17Hình 2.5. Ảnh mẫu và ảnh cần nhận dạng. ................................................................... -19Hình 2.6. Mô hình histogram dọc của bảng điểm mẫu. ................................................ -20Hình 2.7. Mô hình histogram ngang của bảng điểm cần nhận dạng. ............................ -20Hình 2.8. Mô hình histogram của bảng điểm mẫu và bảng bảng điểm cần nhận dạng được xếp trên cùng một trục tọa độ. ..................................................................... -21Hình 2.9. Ảnh sau khi scan bị nghiêng......................................................................... -22Hình 2.10. Cấu trúc của dòng văn bản. ........................................................................ -23Hình 2.11. Phép chiếu ngang và chiếu dọc của trang tài liệu. ..................................... -24Hình 2.12. Phép chiếu dọc của dòng văn bản. ............................................................. -24Hình 2.13. Phép chiếu dọc của dòng văn bản. ............................................................. -24Hình 2.14. Đường thẳng Hough trong toạ độ cực. ...................................................... -33Hình 2.15. Biến đổi Hough phát hiện góc nghiêng. ..................................................... -34Hình 2.16. Các đối tượng trên ảnh. .............................................................................. -36Hình 2.17. Phân cụm các đối tượng. ............................................................................ -36Hình 2.18. NNC của hình có K=2, (b)K=3, (c)K  4. .................................................. -39Hình 2.19. Ảnh (d)đường kết nối với K=2 (e)đường kết nối với K=3 (f)đường kết nối với K  4. ......................................................................................................... -39- Hình 2.20. Các điểm left most bottom và bottom most left của thành phần liên thông.-42Hình 2.21. Những khoảng góc nghiêng khác nhau được sử dụng để ước lượng góc nghiêng phù hợp cho phần tử cấu trúc. ..................................................... -44Hình 2.22. Một thành phần liên thông dài với hệ tọa độ ảnh ....................................... -45Hình 3.1 Sơ đồ khối ...................................................................................................... -48Hình 3.2. Giao diện chương trình thử nghiệm ............................................................. -49Hình 3.3. Giao diện Module file................................................................................... -50Hình 3.4. Giao diện Module Basic ............................................................................... -50Hình 3.5. Giao diện Module Filter ............................................................................... -51Hình 3.6 Giao diện Module Skew Detection ............................................................... -52Hình 3.7. Bảng điểm sau khi scan chưa được xử lí ..................................................... -53Hình 3.8. Bảng điểm sau khi chuyển sang ảnh xám ................................................... -53Hình 3.9. Bảng điểm sau khi chuyển nhị phân............................................................. -54Hình 3.10. Bảng điểm sau khi được lọc trung bình không gian................................... -54Hình 3.11. Bảng điểm sau khi được lọc thông thấp ..................................................... -55Hình 3.12. Bảng điểm sau khi được lọc đồng hình ...................................................... -55Hình 3.13. Phát hiện độ nghiêng bảng điểm bằng Hough.......................................... -56Hình 3.14. Phát hiện độ nghiêng bảng điểm bằng phân tích láng giềng .................... -56Hình 3.15. Phát hiện độ nghiêng bảng điểm bằng phân tích hình chiếu .................... -57Hình 3.16. Hình sau khi thực hiện phép quay ............................................................. -57Hình 3.17. File hình được lưu lại sau khi thực hiện phép quay .................................. -58Bảng 1.1. Bảng so sánh kết quả áp dụng các thuật toán vào hiệu chỉnh độ nghiêng bảng điểm .............................................................................................................................. -59- -1- PHẦN MỞ ĐẦU 1. Lý do thực hiện đề tài Với sự phát triển như vũ bão của ngành công nghệ thông tin, hiện nay, hầu hết các lĩnh vực đều có sự hiện diện của máy tính điện tử: từ việc tự động hóa các công việc văn phòng đến việc điều khiển robot, thám hiểm vũ trụ,... Cùng theo sự phát triển đó, nhận dạng và xử lí ảnh là một lĩnh vực ngày càng nhiều các nhà khoa học quan tâm. Các công việc được lưu trữ theo lối cổ truyền như giấy, gỗ, vải,… chứa đựng một lượng lớn tri thức của nhân loại lại không có độ bền vĩnh cửu, khó xử lí và lưu trữ. Song song đó, các tài liệu như: sách, báo, văn bản, biểu mẫu,… khi lưu trữ phải tốn nhiều thời gian và tiền bạc cho việc nhập các tài liệu đó. Vậy, sao chúng ta không nghĩ đến việc dùng máy scan để quét các tài liệu đó vào máy tính và dùng các kỹ thuật xử lí ảnh để chúng thành các văn bản một cách tự động? Một giải pháp đó là xây dựng một hệ thống nhận dạng chữ, trong các tấm ảnh chứa chữ và các đối tượng đồ họa cần tách và chuyển thành dạng trang văn bản, mở và xử lí được trên các trình soạn thảo văn bản. Để hoạt động tốt, nhận dạng các tài liệu với độ chính xác cao, thì hệ thống cần phải tự động nâng cao chất lượng hình ảnh của form tài liệu, hiệu chỉnh góc nghiêng, hiệu chỉnh độ dịch chuyển, … của form tài liệu. Thực tế bản thân em là một giáo viên tin học, em nhận thấy nhu cầu tại đơn vị rất cần việc chuyển từ dữ liệu giấy sang dữ liệu số để lưu trữ các hồ sơ văn phòng tại đơn vị là cần thiết. Song song đó, xuất phát từ ý tưởng: các bài kiểm tra, bài thi của học sinh nếu được dùng máy scan để quét vào máy tính và thông qua một hệ thống nhận dạng và xử lý chuyển các bài kiểm tra từ văn bản giấy sang văn bản số. Đồng thời, ta xây dựng một hệ thống nhằm so sánh nội dung bài kiểm tra, bài thi với đáp án có sẵn và hệ thống sẽ đưa ra các phương án chấm bài cho học sinh thì việc tự động hóa công việc chấm bài cho học sinh sẽ giúp đỡ giáo viên một phần rất đáng kể. Nhưng để làm được việc trên, một ảnh tài liệu sau khi đưa vào máy tính từ các thiết bị như: scanner, camera,…sẽ bị nhiễu, bị nghiêng hay bị lệch do nhiều cách, có thể là do để giấy vào máy quét hay máy fax không chính xác hay ảnh tài liệu có phương ngang có thể bị quét theo phương dọc do kích thước máy quét không đủ,… -2- Do đó một ảnh tài liệu cần phải dùng một số kỹ thuật hiệu chỉnh ảnh như hiệu chỉnh độ lệch, hiệu chỉnh độ nghiêng,… trước khi tiến hành nhận dạng và xử lý các ảnh tài liệu này. Xuất phát từ ý tưởng trên, luận văn sẽ nghiên cứu một số kỹ thuật hiệu chỉnh form tài liệu nhằm giúp cho việc nhận dạng các tài liệu đạt chất lượng cao. Sau khi hoàn thành luận văn, em sẽ tiếp tục học tập và nghiên cứu để phát triển lên hệ thống chấm điểm các bài kiểm tra dạng tự luận một cách tự động.  Tình hình nghiên cứu trong nƣớc liên quan đến đề tài: - Đề tài “Thiết kế và cài đặt hệ thống nhập liệu tự động -MarkRead dựa trên các kỹ thuật nhận dạng và xử lý ảnh”, PGS.TS Đỗ Năng Toàn, Viện Công Nghệ Thông Tin, năm 1999-2000. - Luận văn Thạc sĩ “Nghiên cứu bài toán phân trang dựa vào ảnh quét tiếng việt”, Phạm Tuyết Trinh, ĐH KHTN TP.HCM, 1999.  Tình hình nghiên cứu ngoài nƣớc liên quan đến đề tài: - “Using White Space for Automated Document Structuring”, Daniela Rus and Kristen Summers, Department of Computer Science Cornell University, 1994. - “Document image analysis: A primer”, RANGACHAR KASTURI, LAWRENCE O’GORMAN and VENU GOVINDARAJU, Department of Computer Science & Engineering, The Pennsylvania State University, University Park, PA 16802, USA, 2002. - “Document Structure and Layout Analysis”, Anoop M. Namboodiri and Anil K. Jain, International Institute of Information Technology, Hyderabad, 500 019, India. - A Knowledge-Based Approach to the Layout Analysis, Floriana Esposito, Donato Malerba and Giovanni Semeraro, Dipartimento di Informatica - Universitd degli Studi via Orabona, 4 - 70126 Bari, Italy. Nhận xét: Mặc dù trong và ngoài nước hiện đang nghiên cứu nhiều lĩnh vực form tài liệu, nhưng chưa có một công trình nghiên cứu nào phát triển chuyên sâu và đầy đủ các kỹ thuật hiệu chỉnh form tài liệu để từ đó có thể giúp em phục vụ việc xây dựng hệ thống chấm điểm các bài kiểm tra tự luận một cách tự động. 2. Mục tiêu đề tài: Nghiên cứu một số kỹ thuật hiệu chỉnh độ dịch chuyển và độ nghiêng của phiếu điểm, phục vụ cho quá trình nhập điểm thi tự động nhờ máy quét. -3- 3. Nội dung thực hiện (Những công việc cần thực hiện để đạt mục tiêu):  Tìm hiểu khái quát về nhu cầu chuyển từ phiếu điểm văn bản giấy sang phiếu điểm số.  Tìm hiểu tổng quan về xử lí ảnh và form tài liệu.  Nghiên cứu một số kỹ thuật hiệu chỉnh form tài liệu như hiệu chỉnh độ dịch chuyển, hiệu chỉnh độ nghiêng,…  Thiết kế, phát triển chương trình thử nghiệm hiệu chỉnh độ dịch chuyển và độ nghiêng của phiếu điểm thi.  Xây dựng báo cáo sơ bộ và hoàn chỉnh báo cáo. 4. Phƣơng pháp thực hiện  Khảo sát thực tế về các nhu cầu chuyển các văn bản, biểu mẫu giấy sang văn bản, biểu mẫu số.  Tìm hiểu nghiên cứu tài liệu, tìm hiểu các thông tin trên Internet về các kỹ thuật xử lý ảnh và form tài liệu.  Nghiên cứu phương pháp Histogram chỉnh độ dịch chuyển của form tài liệu.  Nghiên cứu thuật toán Hough hiệu chỉnh góc nghiêng của form tài liệu.  Thực nghiệm: sử dụng các thuật toán hiệu chỉnh form tài liệu để xây dựng chương trình hiệu chỉnh độ dịch chuyển và độ nghiêng của phiếu điểm thi.  Sử dụng ngôn ngữ C# để xây dựng sản phẩm. Luận văn được chia làm 3 chương: Chƣơng 1: Khái quát form tài liệu và bài toán hiệu chỉnh form tài liệu: chương này đề cập đến các khái niệm cơ bản về form tài liệu, cách thu nhận, biểu diễn form tài liệu và một số phương pháp hiệu chỉnh form tài liệu. Chƣơng 2: Hiệu chỉnh form tài liệu: trong chương này đề cập đến phương pháp phát hiện và hiệu chỉnh độ lệch form tài liệu bằng thuật toán Histogram. Đồng thời còn nêu phương pháp phát hiện và hiệu chỉnh độ nghiêng form tài liệu bằng các phương pháp phân tích hình chiếu, biến đổi Hough, phân tích láng giềng, phép toán hình thái. Chƣơng 3: Chƣơng trình thử nghiệm: tiến hành xây dựng chương trình thừ nghiệm hiệu chỉnh độ lệch và độ nghiêng form tài liệu. -4- Chƣơng 1: KHÁI QUÁT FORM TÀI LIỆU VÀ BÀI TOÁN HIỆU CHỈNH FORM TÀI LIỆU 1.1. Khái quát về Form tài liệu 1.1.1. Form tài liệu là gì? Form tài liệu là các ảnh thu được của các tài liệu bằng giấy thông qua các thiết bị như: camera, scanner, máy fax, … Ảnh tài liệu gồm có các loại: ảnh đen trắng, ảnh màu, ảnh xám đa cấp, … với phần mở rộng là GIF, JPG, TIF,… 1.1.2. Phân loại form tài liệu 1.1.2.1. Ảnh trắng, đen Ảnh đen trắng chỉ bao gồm 2 màu: màu đen và màu trắng. Mức đen trắng được xác định là L, nếu sử dụng số bit B=8 bit để mã hóa thì mức đen trắng (hay mức xám) thì L được xác định: L=2B Nếu L = 2 thì B = 1, nghĩa là chỉ có 2 mức: 0 và 1, còn gọi là ảnh nhị phân. Mức 1 ứng với màu sáng, còn mức 0 ứng với màu tối. Nếu L>2 ta có ảnh đa xám. Như vậy, với ảnh nhị phân mỗi điểm ảnh được mã hóa trên 1 bit, còn với ảnh 256 mức, thì mỗi điểm ảnh được mã hóa trên 8 bit. Với ảnh đen trắng: nếu dùng 8 bit để biểu diễn mức xám, số các mức xám có thể được biểu diễn là 256. Mỗi mức xám được biểu diễn dưới dạng một số nguyên nằm trong khoảng từ 0 đến 255, với mức 0 biểu diễn cho mức cường độ đen nhất và với 255 biểu diễn cho mức cường độ sáng nhất. 1.1.2.2. Ảnh màu Ảnh màu theo lý thuyết của Thomas là ảnh tổ hợp từ 3 màu cơ bản: đỏ (R), lục (G), lam (B) và thường thu nhận trên các dải băng tần khác nhau. Với ảnh màu, cách biểu diễn cũng tự như với ảnh đen trắng, chỉ khác là các số tại mỗi phần tử của ma trận biểu diễn cho ba màu riêng lẻ gồm: đỏ (red), lục (green), lam (blue). Để biểu diễn cho một ảnh màu gồm 24 bit và được chia thành 3 khoảng 8 bit. Mỗi màu cũng phân thành L cấp màu khác nhau (thường L=256). Mỗi khoảng này biểu diễn cho cường độ sáng của một trong các màu chính. Do đó để lưu trữ ành màu người ta có thể lưu trữ từng màu riêng biệt, mỗi màu lưu trữ như một ảnh đa cấp xám. Nên không gian nhớ dành cho một ảnh màu lớn gấp 3 lần một ảnh đa cấp xám cùng kích cỡ. -5- 1.2. Thu nhận và biểu diễn form tài liệu 1.2.1. Thu nhận form tài liệu Đây là công bước đầu tiên trong quá trình xử lí form tài liệu nhưng nó có tính quyết định đến độ phân giải, chất lượng màu, dung lượng bộ nhớ của form tài liệu nên việc lựa chọn các thiết bị thu nhận cần quan tâm đến khả năng thu nhận ảnh của chúng. Các thiết bị thu nhận form tài liệu bao gồm camera, scanner,.. Các thiết bị thu nhận ảnh thông thường Raster là camera, còn Vester là sensor hoặc bàn số hóa Digitalizer hoặc được chuyển đổi từ ảnh Raster. Tóm lại, hệ thống thu nhận ảnh được thực hiện như một quá trình:  Cảm biến: biến đổi năng lượng quang học thành năng lượng điện.  Tổng hợp năng lượng điện thành ảnh. 1.2.2. Cấu trúc Form tài liệu 1.2.2.1. Mào đầu tệp(Header) Mào đầu tệp [2] là phần chứa các thông tin về kiểu ảnh, kích thước, độ phân giải, số bit dùng cho 1 pixel, cách mã hóa, vị trí màu… 1.2.2.2. Dữ liệu nén (Data Compression) Số liệu ảnh được mã hóa bởi kiểu mã hóa chỉ ra trong phần mào đầu tệp. 1.2.2.3. Bảng màu (Palette color) Bảng màu cho biết số màu dùng trong ảnh và bảng màu được sử dụng để hiển thị màu của ảnh 1.2.3. Một số phƣơng pháp biểu diễn Form tài liệu 1.2.3.1. Mã loạt dài (Run – Length code) Phương pháp này hay dùng biểu diễn cho vùng ảnh hay ảnh nhị phân. Một vùng ảnh R có thể biểu diễn đơn giản nhờ một ma trận nhị phân: 0 nếu (m,n)  R u(m,n) = 1 nếu không Với cách biểu diễn trên, một vùng ảnh hay ảnh nhị phân được xem như gồm các chuỗi 0 hay 1 đan xen. Các chuỗi này gọi là mạch (run). Theo phương pháp này, mỗi mạch sẽ được biểu diễn bởi địa chỉ bắt đầu của mạch và chiều dài mạch theo dạng: (, chiều dài)[3]. -6- 0 1 2 3 4 0 ảnh được biểu diễn 1 (1,1) 1, (1,3) 2 2 (2,0) 4, (3,1) 2 3 (nguồn [3]) Hình 1.1. Ảnh nhị phân và các biểu diễn mã loạt dài tƣơng ứng. 1.2.3.2. Mã xích (Chain Code) Mã xích [3] thường được dùng để biểu diễn biên ảnh. Thay vì lưu toàn bộ ảnh, người ta lưu trữ các dãy điểm ảnh như A, B, …, M. Theo phương pháp này, 8 hướng của vector nối 2 điểm biên liên tục được mã hóa. Khi đó ảnh được biểu diễn qua điểm ảnh bắt đầu A cùng với chuỗi các từ mã. Một biến thể của phương pháp này là tăng số hướng. Điều này được minh họa như hình dưới đây: -7- (nguồn [3]) Hình 1.2. Minh hoạ mã xích 1.2.3.3. Mã tứ phân (Quad Tree Code) Theo phương pháp mã tứ phân[3], một vùng ảnh coi như bao kín một hình chữ nhật. Vùng này được chia làm 4 vùng con (Quadrant). Nếu một vùng con gồm toàn điểm đen (1) hay toàn điểm trắng (0) thì không chia tiếp. Trong trường hợp ngược lại, vùng con gồm cả điểm đen và điểm trắng gọi là vùng không đồng nhất, ta tiếp tục chia thành 4 vùng con tiếp và kiểm tra tính đồng nhất của các vùng con đó. Quá trình chia dừng lại khi mỗi vùng con chỉ chứa thuần nhất điểm đen hoặc điểm trắng. Quá trình đó tạo thành một cây chia theo bốn phần gọi là cây tứ phân. Như vậy, cây biểu diễn ảnh gồm một chuỗi các kí hiệu b (black), w (while) và g (grey) kèm theo ký hiệu mã hóa 4 vùng con. Biểu diễn theo phương pháp này tốt hơn so với các phương pháp trên, nhất là so với mã loạt dài. Tuy nhiên, để tính số đo các hình như chu vi, mô men là tương đối khó khăn. 1.3. Bài toán hiệu chỉnh Form tài liệu 1.3.1. Một số vấn đề trong hiệu chỉnh form tài liệu Hiệu chỉnh form tài liệu là một bước quan trọng, là tiền đề cho quá trình nhận dạng ảnh được chính xác. Khi scan form tài liệu thì có thể bị nhiễu, mờ không sắc nét hoặc cần làm rõ các chi tiết như đường biên hay tài liệu bị nghiêng, bị lệch,…Mục đích chính của việc hiệu chỉnh form tài liệu là làm nổi bật một số đặc tính như thay đổi độ tương phản, lọc nhiễu, nổi biên, làm trơn, hiệu chỉnh độ lêch, hiệu chỉnh độ nghiêng,… 1.3.2. Một số cách tiếp cận trong hiệu chỉnh form tài liệu 1.3.2.1. Nhiễu form tài liệu Nhiễu do nhiều nguyên nhân: quá trình quét form tài liệu, quá trình sao chép, sự thoái hóa theo thời gian,.. Nhiễu sẽ làm ảnh hưởng lớn đến kết quả nhận dạng form tài -8- liệu. Thực tế có rất loại nhiễu nhưng thường người ta xét 3 loại nhiễu chính: nhiễu cộng, nhiễu nhân và nhiễu xung [1]:  Nhiễu cộng Nhiễu cộng thường phân bố khắp ảnh. Nếu gọi ảnh quan sát (ảnh thu được) là Xqs, ảnh gốc là X gốc, nhiễu là η, ảnh thu được có thể biểu diễn bởi: Xqs = Xgốc + η  Nhiễu nhân Nhiễu nhân thường phân bố khắp ảnh và ảnh thu được sẽ biểu diễn với công thức: Xqs = Xgốc * η  Nhiễu xung Nhiễu xung thường gây đột biến tại một số điểm ảnh. 1.3.2.2. Khử nhiễu a. Lọc tuyến tính Trong quá trình hiệu chỉnh form tài liệu cần có nhiều bộ lọc vì form tài liệu sẽ có nhiều loại nhiễu. Với nhiễu cộng và nhiễu nhân ta dùng bộ lọc thông thấp, trung bình và lọc đồng hình (Homomorphie), với nhiễu xung ta dùng lọc trung vị, lọc ngoài (outlier)  Lọc trung bình không gian Với lọc trung bình [3], mỗi điểm ảnh được thay thế bằng trung bình trọng số của các điểm lân cận và được định nghĩa như sau: v(m, n) = ∑ ∑a(k , l ) y(m − k , n − l ) ( k ,l )∈ W Nếu trong kỹ thuật lọc trên, ta dùng các trọng số như nhau, phương trình trên sẽ trở thành: 1 v(m, n) = N ∑ ∑ y(m − k , n − l ) ( k ,l )∈ W với : y(m, n): ảnh đầu vào, v(m, n): ảnh đầu ra, a(k, l) : là cửa sổ lọc. với a k ,l = 1 và Nw là số điểm ảnh trong cửa sổ lọc W. NW -9- Lọc trung bình có trọng số chính là thực hiện chập ảnh đầu vào với nhân chập H. Nhân chập H trong trường hợp này có dạng: Trong lọc trung bình, thường người ta ưu tiên cho các hướng để bảo vệ biên của ảnh khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng tùy theo các trường hợp khác nhau. Các bộ lọc trên là bộ lọc tuyến tính theo nghĩa là điểm ảnh ở tâm của số sẽ được thay bởi tổ hợp các điểm lân cận chập với mặt nạ. Giả sử đầu vào biểu diễn bởi ma trận I: Ảnh số thu được bởi lọc trung bình Y=H ⊗ I có dạng: Một bộ lọc trung bình không gian khác cũng hay được sử dụng. Phương trình của bộ lọc đó có dạng: Ở đây, nhân chập H có kích thuớc 2x2 và mỗi điểm ảnh kết quả có giá trị bằng - 10 - trung bình cộng của nó với trung bình cộng của 4 lân cận gần nhất. Lọc trung bình trọng số là một trường hợp riêng của lọc thông thấp.  Lọc thông thấp Lọc thông thấp [1] thường được sử dụng để làm trơn nhiễu.Về nguyên lý của bộ lọc thông thấp giống như đã trình bày trên. Trong kỹ thuật này người ta hay dùng một số nhân chập có dạng sau: Ta dễ dàng nhận thấy khi b =1, Hb chính là nhân chập Ht1 (lọc trung bình). Để hiểu rõ hơn bản chất khử nhiễu cộng của các bộ lọc này, ta viết lại phương trình thu nhận ảnh dưới dạng: Xqs[m,n] = Xgốc[m,n] + η[m,n] Trong đó η[m, n] là nhiễu cộng có phương nsai σ2. Như vậy, theo cách tính của lọc trung bình ta có: Như vậy, nhiễu cộng trong ảnh đã giảm đi Nw lần.  Lọc đồng hình (Homomorphie Filter) Kỹ thuật lọc này [1] hiệu quả với ảnh có nhiễu nhân. Thực tế, ảnh quan sát được gồm ảnh gốc nhân với một hệ số nhiễu. Gọi và (m, n) là nhiễu, như vậy: là ảnh thu được, X(m,n) là ảnh gốc - 11 - Lọc đồng hình thực hiện lấy logarit của ảnh quan sát. Do vậy ta có kết quả sau: Log(X(m, n)) = log( X (m, n) ) + log( η(m, n)) Rõ ràng, nhiễu nhân có trong ảnh sẽ bị giảm. Sau quá trình lọc tuyến tính, ta chuyển về ảnh cũ bằng phép biến đổi hàm e mũ. b. Lọc phi tuyến tính Với kỹ thuật lọc phi tuyến tính, ta dùng bộ lọc trung vị, giả trung vị, lọc ngoài. Với lọc trung vị, điểm ảnh đầu vào sẽ được thay thế bởi trung vị các điểm ảnh còn lọc giả trung vị sẽ là trung bình cộng của 2 giá trị “trung vị” (trung bình cộng của max và min)  Lọc trung vị Trung vị được viết với công thức: v(m, n) = Trungvi(y(m − k , n − l )) với {k, l}  W Kỹ thuật này [2] đòi hỏi giá trị các điểm ảnh trong cửa sổ phải xếp theo thứ tự tăng hay giảm dần so với giá trị trung vị. Kích thước cửa sổ thường được chọn sao cho số điểm ảnh trong cửa sổ là lẻ. Các cửa sổ hay dùng là cửa sổ có kích thước 3x3, hay 5x5 hay 7x7. Ví dụ: Nếu y(m) = {2, 3, 8, 4, 2} và cửa sổ W=(-1, 0, 1), ảnh thu được sau lọc trung vị là: v(m) = (2, 3, 4, 4, 2). do đó: v[0]= 2 ; v[1]=Trungvi(2,3,8)=3; v[2]=Trungvi(3,4,8)=4 v[3]= Trungvi(8,4,2)=4; v[4]= 2 . ; Tính chất của lọc trung vị:  Lọc trung vị là loại lọc phi tuyến. Điều này dẽ nhận thấy từ: Trungvi(x(m)+y(m)) ≠ Trungvi(x(m)) + Trungvi(y(m)).  Có lợi cho việc loại bỏ các điểm ảnh hay các hàng mà vẫn bảo toàn độ phân giải.  Hiệu quả giảm khi số điểm trong cửa sổ lớn hay bằng một nửa số điểm trong cửa sổ. Điều này dễ giải thích vì trung vị là (Nw+1)/2 giá trị lớn nhất nếu Nw lẻ. Lọc trung vị cho trường hợp 2 chiều coi như lọc trung vị tách được theo từng chiều.  Lọc ngoài (Outlier Filter) Giả thiết có ngưỡng nào đó cho các mức nhiễu (có thể dựa vào lược đồ xám).