Luận văn Phương pháp phân tích trang văn bản dựa trên Tab-Stop

thống là khoanh vùng được vùng ảnh và vùng văn bản. 48 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 3. CÀI ĐẶT THỬ NGHIỆM, ĐÁNH GIÁ KẾT QUẢ Chương này tập trung vào việc xây dựng và cài đặt các chức năng của chương trình demo với mục đích chính là phân tích đưa ra cấu trúc vật lý của ảnh đầu vào là ảnh đa cấp xám, ảnh những trang tài liệu có độ phức tạp cao sử dụng phương pháp phân tích trang tài liệu dựa trên Tab-Stop. 3.1. Yêu cầu hệ thống Theo như phần lựa chọn giải pháp (II.2) thì đề tài tập trung vào việc triển khai cài đặt Demo chương trình theo phương pháp phân tích trang văn bản dựa trên Tab-Stop. Với mục đích này thì những yêu cầu cho chương trình như sau: - Cho phép chọn phân tích ảnh trang văn bản theo phương pháp phân tích trang văn bản dựa trên Tab-Stop - Cho phép tùy chọn ảnh màu đầu vào dạng *.bmp và *.jpg - Ảnh kết quả đã khoanh vùng các vùng văn bản, bảng biểu hoặc đồ họa - Tự động lọc và làm trơn nhiễu ảnh đầu vào trước khi phân tích Các thuật toán mô tả ở đây được thực hiện trong C++ và mã nguồn có sẵn như là một phần của hệ thống mã nguồn mở Tesseract OCR. Chạy trên một hình ảnh 8M Pixel điển hình trong khoảng 1 giây trên máy tính Pentium 4 tốc độ 3.,4 GHz. 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 37:. Kết quả trên một số bộ tiêu chí đánh giá đối tƣợng ICDAR2007. 3.2 Một số anh debug của chƣơng trình Ảnh debug các bước của thuật toán phân tích trang văn bản dựa trên Tab–Stop Hình 38: ảnh 002.LeaderNeighbours 50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 39: ảnh 003.FindTabBoxes: Các thành phần tab-stop ứng cử (candidate tab-stop CCs) 51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ảnh debug các bước của thuật toán phân tích trang văn bản dựa trên Tab–Stop trong quá trình tìm các đoạn tab-stop, là các đường kẻ dọc xanh/đỏ (tab-stop line segments) trong ảnh tài liệu 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 40: ảnh 004.FindAllTabVectors_Finding Ảnh debug các bước của thuật toán phân tích trang văn bản dựa trên Tab– top thể hiện quá trình tìm bố cục cột (column layout) trong ảnh tài liệu + Đường phân tách các cột là đường kẻ dọc mầu tím, chạy từ đầu đến cuối trang + Column Partition (CP) là dòng văn bản nằm trong một cột (được đóng khung và nối CCs trong dòng) + Column Partition Set (CPset) là tập các CP cùng nằm trên một hàng (dòng văn bản nằm trên nhiều cột) Hình 41: ảnh 017.ImproveColumnCandidates2_column 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 42: ảnh 020.MovePartitionsToGrid 54 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 43: ảnh 024.InitialPartitions 55 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Các Ảnh debug các bước của thuật toán phân tích trang văn bản dựa trên Tab–Stop thể hiện quá trình tìm bảng trong ảnh tài liệu Hình 44: ảnh 025.ColumnPartitionsAndNeighbors 56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ảnh debug các bước của thuật toán Tab-Stop thẻ hiện quá trình tìm các vùng (regions) trong ảnh trang tài liệu Hình 45: ảnh 036.FindPartitionPartners 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 46: ảnh 038.RefinePartitionPartners 58 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 47: ảnh 040.Blocks 3.3 Đánh giá thực nghiệm Demo chương trình phân tích trang văn bản dựa trên tab-Stop được thực hiện bằng mã nguồn C++ hoàn chỉnh có sẵn như là một phần của hệ thống mã nguồn mở Tesseract OCR trên trang: Chương trình chạy khá nhanh và ổn định cho kết quả phân tích trang văn bản khả tốt, đặc biệt chạy trên cả những ảnh trang văn bản màu. Phương pháp phân tích trang văn bản dựa trên Tab-Stop đã phân tích rất tốt các ảnh trang văn bản. Demo chương trình cài đặt bằng phương pháp này đã khoanh 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên vùng được văn bản, đồ họa và bảng biểu trong ảnh trang văn bản đầu vào. Phương pháp phân tích này đã khắc phục rất tốt những hạn chế mà phương pháp phân tích trang văn bản Top – down như: 1- Kém hiệu quả với các loại tài liệu có bố cục phức tạp 2- Làm việc tốt chỉ với ảnh nhị phân. 3- Kém hiệu quả với các trang tài liệu sử dụng nhiều loại font và size khác nhau. 4- Thông thường top-down được sử dụng cho các loại tài liệu biết trước form bố cục, và có bố cục vật lý đơn giản. Trên đây là 4 hạn chế mà phương pháp phân tích ảnh trang tài liệu mà Top– Down không thể phân tích được thì phương pháp phân tích văn bản dựa trên Tab– Stop lại làm rất tốt điều đó. Ví dụ như ảnh sau: Hình 48: ảnh đầu vào 60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Cũng như Top-Down, phương pháp phân tích trang tài liệu Bottom-up cũng có những hạn chế tương tự như: 1- Cần phải phân đoạn để xác định các thành phần cơ sở trước khi có thể nhóm lại. 2- Tốc độ thực hiện chậm và phụ thuộc vào số thành phần trong trang tài liệu 3- Kém hiệu quả với những trang tài liệu có cấu trúc phức tạp (nhiều bảng, tỷ lệ đồ họa lớn hơn văn bản). 4- Kém hiệu quả với loại trang tài liệu có nhiều loại Font chữ (chứa nhiều size chữ khác nhau), vì với các trang chứa nhiều font có size khác nhau hoặc loại font chữ nghiêng Những hạn chế này đều được khắc phục rất tốt trong phương pháp phân tích trang văn bản dựa vào Tab-Stop. Ví dụ như ảnh có cấu trúc khá phức tạp và nhiều kiểu font với size khác nhau ở trên đã được phân tích rất tốt cho ta kết quả như sau: Hình 49: ảnh kết quả 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Vậy qua đây cho thấy phương pháp phân tích trang văn bản dựa trên Tab- Stop khá tốt trong phân tích ảnh trang văn bản. Phương pháp đã cho thấy những ưu điểm vượt trội so với các phương pháp phân tích trang văn bản truyền thống như: Top-Down, Bottom-up, nó đã khắc phục khá tốt những hạn chế mà hai phương pháp này mắc phải trong phân tích các ảnh trang tài liệu. 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên KẾT LUẬN Qua nhiều mẫu ảnh phân tích cho thấy phương pháp phân tích trang văn bản dựa trên Tab-Stop làm việc rất hiệu quả về nhiệm vụ phát hiện vùng văn bản, bảng biểu hay vùng đồ họa. Đặc biệt là Demo chương trình làm việc thành công với ảnh đầu vào là các trang văn bản màu và có độ phức tạp cao. Phương pháp phân tích trang văn bản dựa trên Tab-Stop là một phương pháp hay vì không phụ thuộc vào font chữ, tuy nhiên trong giới hạn đề tài này chưa trình bày và cài đặt hoàn thiện được. Demo chương trình thử nghiệm phân tích định dạng của trang ảnh văn bản trên còn rất thô sơ, chủ yếu là dùng để mô tả cho phần lý thuyết phân tích định dạng trang ảnh văn bản. Để đưa chương trình áp dụng thực tế còn phải qua một đoạn đường dài, tuy nhiên với kết quả đầu tiên trong quá trình phân tích trang văn từ phương pháp phân tích trang văn bản dựa trên Tab – Stop cho thấy rất khả quan trong việc phân tích các ảnh trang văn bản thành các văn bản word có thể chỉnh sửa được. Từ đó làm phong phú thêm nguồn tài liệu học tập và nghiên cứu khoa học. Hƣớng phát triển đề tài: - Đánh giá một cách hệ thống phương pháp phân tích trang văn bản dựa trên Tab-Stop trên một tập dữ liệu chuẩn. - Phát triển chương trình Demo thành chương trình hoàn chỉnh với đầy đủ các chức năng trong phân tích ảnh trang văn bản, đưa chương trình vào làm việc thực tế. 63 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO Tiếng việt [2]. Lƣơng Mạnh Bá, Ngô Thanh Thủy(1999). Nhập môn xử lý ảnh số : Nhà xuất bản khoa học kỹ thuật, Hà Nội. Chương 4, Tr. 83-87. [8]. Ngô Quốc Tạo (2008). Xử lý và nhận dạng ảnh : Bài giảng cao học, Viện Công nghệ Thông tin. Hà Nội. Tiếng Anh [6].Anoop M. Namboodiri and Anil K. Jain, Document Structure and Layout Analysis, Michigan State University, East Lansing, MI-48824, USA, pp. 31-34, 38- 41. [7].Jiming Lui, Yuan Y Tang, Ching Y Suen (1997), Chinese document layout analysic based on adaptive Split-and-Merge and qualitation spatial reasoning, Elsevier Science, Oxford, ROYAUME-UNI, pp. 4-9. [3].MathWorks (1997), Image Processing Toolbox User’s Guide. MathWorks, 1997. [5]. Sadhana (2002), Document image analysis: A primer, India, pp. 3-7. [4].TANG, Yuan Y (2000), Documnet analysis and recogniton by computers. Handbook of Pattern recognition and computer vision, World Scientific Company, pp. 1-15. [1].Yuan Y. Tang, Hong Mat, Xiaogang Maot, Dan Liu and Ching Y. Suen (1997), A New Approach to Document Analysis Based on Modified Fractal Signature, Washington, DC, USA : IEEE Computer Society. i Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN Để hoàn thành luận văn đúng thời gian quy định và đáp ứng được yêu cầu đề ra, bản thân tôi đã cố gắng nghiên cứu, học tập và làm việc trong thời gian dài. Tôi đã tham khảo một số tài liệu đã nêu trong phần “Tài liệu tham khảo” và không hề sao chép nội dung từ bất kỳ luận văn nào khác. Toàn bộ luận văn do bản thân tôi tự tìm hiểu. Cho đến nay nội dung luận văn của tôi chưa từng được công bố, xuất bản dưới bất kỳ hình thức nào và cũng không được sao chép từ bất cứ luận văn của học viên hay một công trình nghiên cứu nào. Tôi xin cam đoan những lời khai trên là đúng, mọi thông tin sai lệch tôi xin hoàn toàn chịu trách nhiệm trước Hội đồng. Thái Nguyên, ngày 25 tháng 10 năm 2012. Học viên Bùi Phƣơng Thảo ii Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC LỜI CAM ĐOAN ............................................................................................................................ i MỤC LỤC........................................................................................................................................ ii DANH MỤC CÁC HÌNH ẢNH ................................................................................................. iv MỞ ĐẦU .......................................................................................................................................... 1 1. Đặt vấn đề ............................................................................................................ 2 2. Nội dung nghiên cứu ........................................................................................... 3 2.1.Mục tiêu nghiên cứu chính của đề tài ............................................................ 3 2.2.Ý nghĩa khoa học của đề tài ........................................................................... 4 2.3.Nhiệm vụ nghiên cứu ..................................................................................... 4 2.4. Phương pháp nghiên cứu .............................................................................. 4 2.5. Phạm vi nghiên cứu ...................................................................................... 4 3. Bố cục của luận văn ............................................................................................. 5 CHƢƠNG 1. NỘI DUNG TRANG VĂN BẢN VÀ CÁC PHƢƠNG PHÁP TIỀN XỬ LÝ ............................................................................................................................................................ 6 1.1. Ảnh tài liệu và nhận dạng ảnh tài liệu .............................................................. 6 1.1.1. Tổng quan về ảnh tài liệu ........................................................................... 6 1.1.2. Nhận dạng tài liệu và vai trò của phân tích ảnh tài liệu............................. 7 1.2. Cấu trúc của ảnh tài liệu ................................................................................... 8 1.2.1. Cấu trúc vật lý ............................................................................................ 9 1.2.2. Cấu trúc logic ........................................................................................... 10 1.3. Quá trình phân tích tài liệu ............................................................................. 11 1.3.1. Tiền xử lý (preprocessing): ...................................................................... 12 1.3.2. Phân tích cấu trúc vật lý ........................................................................... 13 1.3.3. Phân tích cấu trúc logic ............................................................................ 15 1.4. Một số hệ thống phân tích tài liệu hiện nay ................................................... 15 1.4.1. VnDOCR ................................................................................................. 15 1.4.2. OminiPage ............................................................................................... 19 2.4.3. Finereader ................................................................................................ 21 iii Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 2. MỘT SỐ KỸ THUẬT XỬ LÝ TRANG VĂN BẢN ....................................... 24 2.1. Các phương pháp phân tích định dạng trang tài liệu ...................................... 24 2.1.1. Top-down ................................................................................................. 24 2.1.2. Bottom-up ................................................................................................ 29 2.1.3. Phương pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) ... 31 2.1.4 Phương pháp phân tích trang văn bản dựa trên Tab-Stop ........................ 33 2.2. Lựa chọn giải pháp ......................................................................................... 47 CHƢƠNG 3. CÀI ĐẶT THỬ NGHIỆM, ĐÁNH GIÁ KẾT QUẢ ..................................... 48 3.1. Yêu cầu hệ thống ............................................................................................ 48 3.2 Một số anh debug của chương trình ................................................................ 49 3.3 Đánh giá thực nghiệm...................................................................................... 58 KẾT LUẬN .................................................................................................................................... 62 TÀI LIỆU THAM KHẢO ........................................................................................................... 63 iv Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC HÌNH ẢNH Hình 1: Sơ đồ tổng quan quá trình tạo ảnh tài liệu ..................................................................... 6 Hình 2: Ví dụ ảnh tài liệu ................................................................................................................ 7 Hình 3: Sơ đồ OCR cơ bản ............................................................................................................. 8 Hình 4: b-Cấu trúc vật lý: c,d-Cấu trúc logic của một tài liệu[4] ............................................ 10 Hình 5: Ví dụ loại tài liệu có bố cục phức tap ............................................................................ 11 Hình 6: Sơ đồ nguyên lý hệ thống xử lý tài liệu[6] .................................................................... 12 Hình 7: a - Ảnh gốc b - Ảnh sau khi tách nền ............................................................................. 13 Hình 8: Ví dụ một ảnh tài liệu bị nghiêng một góc 5 độ ............................................................ 14 Hình 9: Ví dụ một cây mô tả cấu trúc logic của một trang tài liệu[5] ..................................... 15 Hình 10: VnDOCR và một ví dụ nhận dạng ............................................................................... 16 Hình 11: Ảnh mẫu có cấu trúc vật lý phức tạp ........................................................................... 17 Hình 12: Kết quả ra hai vùng ảnh với ảnh mẫu 11 .................................................................... 17 Hình 13: Mẫu ảnh có cấu trúc vật lý phức tạp, nhưng các khối bao bởi hình chữ nhật ........ 18 Hình 14: Kết quả phân tích với ảnh 13 ....................................................................................... 19 Hình 15: Đầu ra phân vùng chỉ có 1 vùng văn bản ................................................................... 20 Hình 16: Đầu ra có vùng chứa cả ảnh và text ............................................................................ 21 Hình 17: Với ảnh 13 đạt hiệu quả 90% ....................................................................................... 22 Hình 18 Với ảnh I-15 hiệu quả đạt 100% ................................................................................... 23 Hình 19: Với mẫu phức tạp hơn Finereader cho kết quả 95% ................................................ 23 Hình 20: Kết quả chiếu nghiêng theo phương ngang và phương thẳng đứng của một trang tài liệu4 ............................................................................................................................................ 25 Hình 21: Phân tách cột dựa vào phép chiếu nghiêng theo phương ngang5 ........................... 26 Hình 22: Phép chiếu nghiêng theo phương ngang để phân đoạn ký tự hoặc từ ..................... 26 Hình 23: Lược đồ chiếu ngang của một dòng chữ nghiêng - rất khó phân đoạn ký tự ......... 27 Hình 24: Lược đồ chiếu đứng của trang tài liệu bị nghiêng ..................................................... 28 Hình 25: Lược đồ chiếu đứng của một bài báo .......................................................................... 28 Hình 26: Phương pháp Dostrum cho phân tích định dạng trang từ dưới lên. (a) Một phần v Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên của nội dung văn bản gốc. (b) Các thành phần lân cận gần nhất được xác định. (c) Các hình chữ nhật tối thiểu tạo nên nhóm láng giềng gần nhất từ đó xác định được dòng văn bản. ... 30 Hình 27: Mô tả thuật toán Tách và Nối thích nghi .................................................................... 32 Hình 28: ảnh đầu vào .................................................................................................................... 34 Hình 29. (a) Đường dọc, (b) Các thành phần hình. ................................................................... 36 Hình 30: filtered CCs .................................................................................................................... 37 Hình 31. (a) Các thành phần tab-stop phù hợp (b) Dòng tab hợp lý và những kết nối dấu vết .......................................................................................................................................................... 38 Hình 32: cho thấy các phân đoạn dòng tab cuối. ....................................................................... 39 Hình 33: Cột chính(cps) ................................................................................................................ 41 Hình 34: làm sạch các tab-stop .................................................................................................... 43 Hình 35: Typed partition chains .................................................................................................. 44 Hình 36: Các khối cuối cùng ........................................................................................................ 46 Hình 37:. Kết quả trên một số bộ tiêu chí đánh giá đối tượng ICDAR2007. .......................... 49 Hình 38: ảnh 002.LeaderNeighbours .......................................................................................... 49 Hình 39: ảnh 003.FindTabBoxes: Các thành phần tab-stop ứng cử (candidate tab-stop CCs) .......................................................................................................................................................... 50 Hình 40: ảnh 004.FindAllTabVectors_Finding ......................................................................... 52 Hình 41: ảnh 017.ImproveColumnCandidates2_column ......................................................... 52 Hình 42: ảnh 020.MovePartitionsToGrid................................................................................... 53 Hình 43: ảnh 024.InitialPartitions ............................................................................................... 54 Hình 44: ảnh 025.ColumnPartitionsAndNeighbors .................................................................. 55 Hình 45: ảnh 036.FindPartitionPartners ................................................................................... 56 Hình 46: ảnh 038.RefinePartitionPartners ................................................................................. 57 Hình 47: ảnh 040.Blocks ............................................................................................................... 58 Hình 48: ảnh đầu vào .................................................................................................................... 59 Hình 49: ảnh kết quả ..................................................................................................................... 60