›

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

pdf 68 trang yendo 4170
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Phương pháp phân tích trang văn bản dựa trên Tab-Stop", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_phuong_phap_phan_tich_trang_van_ban_dua_tren_tab_st.pdf

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

  1. 1 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG  BÙI PHƢƠNG THẢO PHƢƠNG PHÁP PHÂN TÍCH TRANG VĂN BẢN DỰA TRÊN TAB-STOP Chuyên ngành : Khoa học máy tính Mã số : 60.48.01 Luận văn thạc sĩ khoa học máy tính Ngƣời hƣớng dẫn khoa học: TS. Nguyễn Đức Dũng Thái Nguyên, 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  2. 2 MỞ ĐẦU 1. Đặt vấn đề Hiện nay, hầu hết tài liệu của con người đều đã được số hóa và được lưu trữ trên máy tính, việc số hóa đảm bảo tính an toàn và thuận tiện hơn hẳn so với sử dụng tài liệu giấy. Tuy nhiên việc sử dụng giấy để lưu trữ tài liệu trong một số mục đích là không thể thay thế hoàn toàn được (như sách, báo, tạp chí, công văn, ). Hơn nữa, lượng tài liệu được tạo ra từ nhiều năm trước vẫn còn rất nhiều mà không thể bỏ đi được vì tính quan trọng của chúng. Việc chuyển đổi tài liệu điện tử sang tài liệu giấy có thể thực hiện được dễ dàng bằng cách in hay fax, nhưng công việc ngược lại là chuyển từ tài liệu giấy sang tài liệu điện tử lại là một vấn đề không hề đơn giản. Chúng ta mong muốn có thể số hóa tất cả các tài liệu, sách, báo đó và lưu trữ chúng trên máy tính, việc tổ chức và sử dụng chúng sẽ thuận tiện hơn rất nhiều. Vậy nhưng giải pháp sẽ là gì? Công nghệ đang phát triển một cách chóng mặt, các máy scan với tốc độ hàng nghìn trang một giờ, các máy tính với công nghệ xử lí nhanh chóng và chính xác một cách siêu việt. Vậy tại sao chúng ta không quét các trang tài liệu vào và xử lý, chuyển chúng thành các văn bản một cách tự động? Nhưng vấn đề là khi quét chúng ta chỉ thu được các trang tài liệu đó dưới dạng ảnh nên không thể thao tác, sửa chữa, tìm kiếm như trên các bản Office được, khi đó máy tính không phân biệt được đâu là điểm ảnh của chữ và đâu là điểm ảnh của đối tượng đồ họa. Một giải pháp được đưa ra đó là xây dựng các hệ thống nhận dạng chữ trong các tấm ảnh chứa cả chữ và đối tượng đồ họa, sau đó chuyển thành dạng trang văn bản và có thể mở, soạn thảo được trên các trình soạn thảo văn bản. Một cách tổng quát thì cách thức hoạt động của một hệ thống nhận dạng chữ đó như sau [5]: 1. Chụp ảnh hoặc scan các trang tài liệu và lưu lại trên máy tính dưới dạng hình ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  3. 3 2. Phân tích hình ảnh sau khi quét, đọc được ký tự trên hình ảnh và ghi lại vào máy tính theo cách mà máy tính quản lý được thông tin dữ liệu đó. - Bước 1: phân tích cấu trúc của ảnh tài liệu, từ đó xác định đâu là phần chứa ký tự, đâu là phần chứa cả ảnh lẫn ký tự và đâu chỉ chứa hình ảnh. Bước này thực sự quan trọng cho bước nhận dạng. Bởi nó định vị chính xác cho việc áp dụng các thuật toán nhận dạng lên vùng đã xác định tính chất, nếu bước này chính xác trước tiên nó hạn chế thời gian cho việc nhận dạng, sau là tăng ngữ nghĩa bổ sung cho việc nhận dạng. - Bước 2: nhận dạng ký tự dựa vào các tính chất của ký tự, ví dụ như sắp xếp theo dòng, khoảng cách giữa 2 từ lớn hơn khoảng cách giữa 2 ký tự, dùng trí tuệ nhân tạo để dự đoán các ký tự kề nhau phải như thế nào, các từ trong câu phải như thế nào để câu có nghĩa. Từ đó có nội dung đúng để lưu trữ, quản lý . Trong thực tế không phải quá trình nhận dạng nào cũng chỉ trải qua hai bước như trên, bởi vì có rất nhiều tham số ảnh hưởng đến kết quả của các chương trình nhận dạng như nhiễu, Font chữ, kích thước chữ, kiểu chữ nghiêng, đậm, gạch dưới. Ngoài ra các dòng chữ cũng có thể trộn lẫn với các đối tượng đồ họa, vì thế trước khi nhận dạng chữ, một số thao tác tiền xử lý sẽ được tác động lên ảnh như, lọc nhiễu, chỉnh góc nghiêng và đặc biệt quan trọng là phân tích trang tài liệu để xác định cấu trúc của trang văn bản đồng thời tách biệt hai thành phần là chữ và các đối tượng đồ họa. 2. Nội dung nghiên cứu 2.1.Mục tiêu nghiên cứu chính của đề tài Tìm hiểu cấu trúc trang tài liệu (cấu trúc vật lý, logic) Tìm hiểu một số kỹ thuật phân tích trang tài liệu (phân vùng, phân đoạn, top- down hay bottom-up, ) Trình bày kỹ thuật phân tích trang văn bản Tab-Stop Cài đặt thử nghiệm một giải pháp phân tích trang văn bản trên kỹ thuật Tab- Stop. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  4. 4 Từ kết quả nghiên cứu có một sự chuẩn bị kiến thức đẩy đủ cho bước nghiên cứu tiếp theo là nhận dạng ký tự quang. 2.2.Ý nghĩa khoa học của đề tài Giải quyết được vấn đề về học thuật: đề tài sẽ mang ý nghĩa cung cấp về mặt lý thuyết để làm rõ về các phương pháp phân tích trang tài liệu. Đáp ứng được yêu cầu của thực tiễn: từ các lý thuyết đã được nghiên cứu, từ đó liên hệ và gắn vào thực tiễn để có thể áp dụng vào các lĩnh vực như: Số hóa tài liệu, lưu trữ thư viện, điện tử hóa văn phòng, nhận dạng và xử lý ảnh, 2.3.Nhiệm vụ nghiên cứu Mục đích của luận văn đề cập được đến hai phần: Phần lý thuyết: Nắm rõ và trình bày những cơ sở lý thuyết liên quan đến cấu trúc trang tài liệu, một số kỹ thuật phân tích trang tài liệu, từ đó có để có thể xác định tính quan trọng của bước này trong nhận dạng ký tự, đồng thời hiểu các công việc kế tiếp cần làm trong bước nhận dạng ký tự. Phần phát triển ứng dụng: Áp dụng các thuật toán đã trình bày ở phần lý thuyết từ đó lựa chọn một giải pháp tối ưu và cài đặt thử nghiệm chương trình phân tích trang tài liệu. 2.4. Phƣơng pháp nghiên cứu Tìm kiếm, tham khảo, tổng hợp tài liệu từ các nguồn khác nhau để xây dựng phần lý thuyết cho luận văn. Sử dụng các kỹ thuật được áp dụng phân tích trang tài liệu để làm rõ bản chất của các vấn đề được đưa ra trong phần lý thuyết. Xây dựng chương trình Demo. 2.5. Phạm vi nghiên cứu Bài toán phân tích trang tài liệu đã được phát triển với nhiều thành tựu trong thực tế, có rất nhiều thuật toán tối ưu đã được các nhà khoa học đề nghị. Tuy nhiên có thể nói chưa có một chương trình nào có thể “đọc” một ảnh văn bản như con người, vì thực tế có rất nhiều kiểu trang văn bản khác nhau, khác nhau về cấu trúc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  5. 5 trình bày, ngôn ngữ, kiểu font, chữ viết tay, Đây thực sự là một bài toán lớn, chính vì thế trong phạm vi của luận văn chỉ tìm hiểu một số kỹ thuật phân tích trang văn bản tiêu biểu với mục đích để so sánh với một thuật toán mới chưa được đưa ra ở các đề tài trước. Cuối cùng, dựa vào đó để xây dựng Demo cho một ứng dụng. Các kết quả nghiên cứu dự kiến cần đạt được: Tìm hiểu tài liệu liên quan đến lĩnh vực quan tâm để nắm bắt được bản chất vấn đề đặt ra. Báo cáo lý thuyết Chương trình Demo. 3. Bố cục của luận văn Nội dung của luận văn được trình bày trong ba chương với nội dung chính sau: Chƣơng 1: Trình bày nội dung trang văn bản và các phương pháp tiền xử lý trang văn bản, cấu trúc trang tài liệu và quá trình phân tích trang tài liệu Chƣơng 2: Trình bày một số phương pháp phân tích trang tài liệu, từ đó đánh giá ưu nhược điểm để lựa chọn kỹ thuật Tab-Stop cho chương trình thử nghiệm. Chƣơng 3: Cài đặt chương trình Demo và đánh giá kết quả chương trình Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  6. 6 CHƢƠNG 1. NỘI DUNG TRANG VĂN BẢN VÀ CÁC PHƢƠNG PHÁP TIỀN XỬ LÝ Chương này đưa ra các khái niệm về đối tượng làm việc của đề tài là ảnh tài liệu, khái niệm về cấu trúc vật lý và cấu trúc logic. Giới thiệu các khâu trong một hệ thống nhận dạng chữ viết hoàn chỉnh. Đồng thời đưa ra một số phần mềm nhận dạng của Việt Nam và Thế giới cùng với các mẫu kết quả phân tích của nó nhằm mục đích so sánh và xác định phạm vi cho đề tài. 1.1. Ảnh tài liệu và nhận dạng ảnh tài liệu 1.1.1. Tổng quan về ảnh tài liệu Trang ảnh tài liệu được đề cập ở đây là các file ảnh số hoá thu được bằng cách quét các trang tài liệu dùng máy scanner, hoặc chụp từ các máy ảnh số, hay nhận từ một máy fax (Hình 1), file ảnh này được lưu giữ trong máy tính. Ảnh tài liệu có nhiều loại: ảnh đen trắng, ảnh đa cấp xám, ảnh đa cấp xám với các phần mở rộng như TIF, BMP, PCX, (Hình 2) và ảnh tài liệu được đưa ra trong luận văn này là ảnh đa cấp xám. Tài liệu Thiết bị thu nhận ảnh Ảnh số tài liệu Hình 1: Sơ đồ tổng quan quá trình tạo ảnh tài liệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  7. 7 Hình 2: Ví dụ ảnh tài liệu 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 Ngày nay, máy tính đang phát triển mạnh mẽ, tốc độ xử lý không ngừng được nâng lên. Cùng với nó là sự ra đời của các phần mềm thông minh đã khiến máy tính ngày một gần gũi với con người hơn. Một trong các khả năng tuyệt vời của con người mà các nhà khoa học máy tính muốn đạt được đó là khả năng nhận dạng và lĩnh vực nhận dạng thu được nhiều thành công nhất là nhận dạng ký tự quang OCR–Optical Character Recognition. OCR có thể được hiểu là quá trình chuyển đổi tài liệu dưới dạng file ảnh số hoá (là dạng chỉ có người đọc được) thành tài liệu dưới dạng file văn bản (là tài liệu mà cả người và máy đều có thể đọc được). OCR có rất nhiều ứng dụng hữu ích trong cuộc sống như: - Sắp xếp thư tín, dựa vào việc nhận dạng mã bưu chính (Zipcode) hay địa chỉ gửi tới. - Tự động thu thập dữ liệu từ các mẫu đơn/báo biểu hay từ các hồ sơ lao động. - Hệ thống tự động kiểm tra trong ngân hàng (tự động xác nhận chữ ký) - Tự động xử lý các hóa đơn hay các yêu cầu thanh toán - Hệ thống tự động đọc và kiểm tra passport - Tự động phục hồi và copy tài liệu từ các ảnh quét. - Máy đọc cho những người khiếm thính - Các ứng dụng Datamining - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  8. 8 Sơ đồ một hệ thống OCR cơ bản ở Hình 3. Trong đó: - Scanner: Thiết bị quét ảnh - OCR hardware/software: o Document analysis: Phân tích tài liệu o Character recognition: Nhận dạng ký tự o Contexttual processor: Xử lý văn cảnh - Output interface: Đầu ra  Như vậy vai trò chính của khâu phân tích ảnh tài liệu là việc phân đoạn trang, tách vùng văn bản ra khỏi nền và đồ họa tạo mẫu chuẩn cho khâu nhận dạng. Rõ ràng là kết quả của khâu phân tích này ảnh hưởng rất lớn đến hiệu qủa của khâu nhận dạng nếu sử dụng mẫu hay các chuỗi văn bản đầu ra của nó. Hình 3: Sơ đồ OCR cơ bản 1.2. Cấu trúc của ảnh tài liệu Một khái niệm mấu chốt trong xử lý tài liệu đó là cấu trúc của tài liệu. Cấu trúc tài liệu thu được từ việc liên tiếp chia nhỏ nội dung của tài liệu thành các phần nhỏ đơn vị (tức không thể phân chia được nữa) và chúng được gọi là các đối tượng cơ sở (basic objects). Còn tất cả các đối tượng khác được gọi là các đối tượng hỗn hợp. Có hai loại cấu trúc của tài liệu được quan tâm ở đây đó là cấu trúc vật lý Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  9. 9 (hay bố cục vật lý) và cấu trúc logic mô tả mối quan hệ logic giữa các vùng đối tượng trong tài liệu. 1.2.1. Cấu trúc vật lý Bố cục vật lý của một tài liệu mô tả vị trí và các đường danh giới giữa các vùng có nội dung khác nhau trong một trang tài liệu[6]. Quá trình phân tích bố cục tài liệu là thực hiện việc tách từ một trang tài liệu ban đầu thành các vùng có nội dung cơ sở như hình ảnh nền, vùng văn bản, Để mô tả bố cục vật lý của tài liệu người ta sử dụng một cấu trúc hình học với mỗi đối tượng trong cấu trúc là một phần tử chỉ chứa nội dung đồng nhất. Các kiểu đối tượng hình học được định nghĩa như sau[4]: Block là đối tượng cơ sở tương ứng với một vùng hình chữ nhật chứa một phần nội dụng của tài liệu. Frame một đối tượng hỗn hợp tương ứng với một hình chữ nhật bao gồm một hoặc nhiều block hoặc bao gồm các frame. Page là đối tượng hình học hoặc hỗn hợp các thành phần cơ sở tương ứng với một vùng hình chữ nhật, nếu là đối tượng hỗn hợp nó chứa một hoặc nhiều block, một hoặc nhiều frame. Page set (tập trang) là một tập của một hoặc nhiều page. Điểm gốc của cấu trúc (hay nút gốc) là một đối tượng ở mức cao nhất trong sơ đồ phân cấp của cấu trúc hình học tài liệu. Hình 4(b) cho ví dụ một cấu trúc hình học mô tả bố cục vật lý của trang tài liệu tương ứng. Các thuật toán phân tích bố cục tài liệu có thể được chia làm ba loại chính dựa theo phương pháp thực hiện của nó. - Bottom-up: Ý tưởng chính của các thuật toán loại này là bắt đầu từ những phần tử nhỏ nhất (như từ các pixel hay các phần tử liên thông) sau đó liên tục nhóm chúng lại thành các vùng lớn hơn. - Top-down: Thuật toán này bắt đầu từ vùng lớn nhất chứa cả trang tài liệu sau đó liên tục phân chia thành các vùng nhỏ hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  10. 10 - Các thuật toán không theo thứ bậc: như Fractal Signature, Adaptive split- and-merge 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] 1.2.2. Cấu trúc logic Ngoài bố cục vật lý, các trang tài liệu còn chứa đựng nhiều thông tin về ngữ cảnh và nội dung như các tiêu đề, đoạn văn, đề mục, và mỗi vùng nội dung này lại được gán các nhãn logic hay nhãn theo chức năng tương ứng, khác biệt hoàn toàn với các nhãn trong bố cục vật lý. Hầu hết các tài liệu đều có một quy tắc đọc để có thể hiểu hết nội dung của tài liệu. Với một số ngôn ngữ đặc biệt như tiếng Trung, tiếng Ả rập lại có quy cách đọc khác biệt (như đọc từ phải qua trái, trên xuống). Tập hợp tất cả các yếu tố logic và chức năng trong một tài liệu và mối quan hệ giữa chúng được gọi là cấu trúc logic của tài liệu[6]. Thông thường pha phân tích cấu trúc logic của tài liệu được thực hiện trên kết quả của bước phân tích bố cục vật lý. Tuy nhiên với một số loại tài liệu phức tạp, thì pha phân tích bố cục vật lý lại cần thêm một số thông tin logic liên quan đến các vùng để có thể phân đoạn một cách chính xác. Hình 4(c,d) mô tả một ví dụ cấu trúc logic của tài liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  11. 11 1.3. Quá trình phân tích tài liệu Ảnh tài liệu chứa rất nhiều loại vùng thông tin khác nhau như các block, lines, words, figures, tables và background. Ta có thể gọi các vùng này theo chức năng của nó trong tài liệu hoặc gán cho nó các nhãn logic như sentences, titles, captions, address, Quá trình phân tích tài liệu là thực hiện việc tách một tài liệu thành các vùng theo một tiêu chuẩn hay mối quan hệ lẫn nhau nào đấy. Công việc này được thực hiện qua nhiều bước như tiền xử lý, tách vùng, lặp cấu trúc tài liệu, Một số loại tài liệu như báo, tạp chí, sách quảng cáo, chúng có cấu trúc và bố cục rất phức tạp và không có một form chung nào cả (Hình 5). Với con người để có thể đọc hiểu được một trang tài liệu còn cần thêm nhiều kiến thức bổ sung như ngôn ngữ, hoàn cảnh, các luật ngầm định, vì thế việc tự động phân tích các trang tài liệu một cách tổng quát là một việc rất khó khăn thậm chí là không khả thi ngay cả với các hệ thống phân tích tài liệu tiên tiến nhất[6]. Hình 5: Ví dụ loại tài liệu có bố cục phức tap Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  12. 12 Sơ đồ nguyên lý của một hệ thống tự động phân tích tài liệu như sau: Hình 6: Sơ đồ nguyên lý hệ thống xử lý tài liệu[6] 1.3.1. Tiền xử lý (preprocessing): Hầu hết các ảnh tài liệu đều có nhiễu do quá trình thu nhận ảnh gây ra (môi trường, chất lượng máy quét, máy ảnh), vì thế trong quá trình xây dựng các thuật toán phân tích cần loại bỏ các nhiễu này và công việc này thường được tiến hành trước khi bắt đầu phân tích bố cục hay cấu trúc và gọi là Tiền xử lý. Nhiệm vụ chính của bước này là loại bỏ nhiễu, tách nền ra khỏi nội dung, phát hiện và xoay góc nghiêng,  Lọc nhiễu(noise removal): Nhiễu luôn là một vấn đề trong hầu hết các bài toán đọc hiểu tài liệu. Nhiễu sinh ra không chỉ do quá trình scan ảnh mà còn bao gồm cả các nhiễu trắng gây ra từ chính sensor hay các mạch thu nhận trong các máy thu nhận ảnh số. Nhiễu có thể được loại bớt sử dụng một số các kỹ thuật như lọc trung bình, lọc trung vị, lọc thông thấp,  Tách nền (Background separation): Đây là một vấn đề rất quan trọng ảnh hưởng trực tiếp đến hiệu quả của các thuật toán phân tích tài liệu. Nếu đối với các loại tài liệu có nền đồng nhất đa cấp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  13. 13 xám trắng hoặc đen thì việc tách có thể thực hiện đơn giản bằng phép phân ngưỡng, tuy nhiên trong thực tế rất nhiều ảnh tài liệu có nền rất phức tạp như ảnh hay đồ họa (Hình 7) thì việc xác định các pixel nào thực sự thuộc về “phần nổi” là một công việc khó khăn. Ta có thể tách nền bằng một số kỹ thuật như sau: - Gán mỗi điểm ảnh vào “phần nổi” hay phần nền dựa theo một tiêu chí nào đấy (như ngưỡng mức xám, ) - Dựa theo độ đo xác suất xuất hiện của mỗi điểm ảnh mà phân lớp nó vào nền hay phần nổi - Dựa vào các pixel liên thông kết hợp với mạng noron để phân tách. Hình 7: a - Ảnh gốc b - Ảnh sau khi tách nền  Xác định góc nghiêng: Do quá trình thu nhận ảnh (như đặt lệch tài liệu khi scan, ) ảnh tài liệu thu được rất có thể bị nghiêng, tức trục của các dòng văn bản không song song với trục ngang (Hình 8). Việc xác định được góc nghiêng và xoay lại tài liệu là một khâu rất quan trọng ảnh hưởng đến hiệu quả trong một số thuật toán phân tích. Ví dụ như các thuật toán dựa theo biểu đồ sau phép chiếu nghiêng để tiến hành phân tích thì sẽ hoàn toàn thất bại nếu văn bản bị nghiêng. Tuy nhiên việc có thể tự động ước lượng được chính xác góc nghiêng của ảnh tài liệu là một bài toán khó. Có nhiều kỹ thuật để có thể xác định được góc nghiêng của tài liệu, điểm chung trong hầu hết các thuật toán là xác định góc nghiêng bằng việc xác định hướng của các dòng văn bản dựa vào vị trí một số ký tự trong tài liệu. 1.3.2. Phân tích cấu trúc vật lý Phân tích tài liệu được định nghĩa là quá trình xác định cấu trúc vật lý của Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  14. 14 một tài liệu. Trong khâu này thì từ một ảnh tài liệu đầu vào sẽ được chia thành một số khối (block) chứa các nội dung thành phần của tài liệu như các dòng văn bản, tiêu đề, đồ họa, cùng với có hoặc không các tri thức biết trước về định dạng của nó[6]. Có một số phương pháp phân tích và được phân ra làm hai loại như sau:  Các phương thức có thứ bậc: Trong quá trình chia tài liệu thành các block chúng ta quan tâm đến mối quan hệ về mặt hình học giữa các block. Có ba phương pháp thuộc loại này là: o Phân tích top-down (trên xuống) o Phân tích buttom-up (dưới lên) o Phân tích kiểu Adaptive split-and-merge (tách và nối thích nghi)  Các phương pháp không có thứ bậc: Trong quá trình chia tài liệu thành các khối chúng ta không quan tâm đến mối quan hệ hình học giữa các block. Hình 8: Ví dụ một ảnh tài liệu bị nghiêng một góc 5 độ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  15. 15 1.3.3. Phân tích cấu trúc logic Từ kết quả của pha phân tích cấu trúc vật lý, phân tích cấu trúc logic sẽ đi xác định mối quan hệ logic giữa các vùng đã được gắn nhãn như tiêu đề, văn bản, đề mục, hearder, Bước này là cơ sở cho việc nhận dạng ký tự. Việc xác định được vị trí chính xác của mỗi vùng trong cấu trúc logic sẽ tăng thêm thông tin cho quá trình nhận dạng như thông tin về ngữ cảnh, đoán nhận được kiểu font và kích thước chữ nếu biết nó thuộc vùng tiêu đề, đề mục hay trong đoạn văn, (Hình 9) document(page) article(page) article(page) abstract sub-title sub-title sub-title paragraphs paragraphs paragraphs 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] 1.4. Một số hệ thống phân tích tài liệu hiện nay 1.4.1. VnDOCR Vndocr phần mềm nhận dạng tiếng Việt là một sản phẩm của Viện công Nghệ thông tin. VnDOCR thu thập thông tin nhờ quá trình quét các loại sách báo thông qua máy quét thành các tệp ảnh và chuyển đổi thành các tệp có định dạng *.doc, *.xls, *.txt, *.rtf, có thể đọc và chỉnh sửa được trên các phần mềm soạn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  16. 16 thảo văn bản thông dụng như Office, Wordpad, (Hình 10) Môi trƣờng  PC với hệ điều hành Windows 9x, ME, 2000, XP, NT, Tiện ích: Bộ gõ chữ Việt, bộ font ABC, VNI, Unicode, Thông tin đƣa vào  Quét trực tiếp các loại sách báo, văn bản qua máy quét (Scanner).  Đọc và xử lý hơn 30 dạng tệp tin ảnh phổ dụng nhất như PCX, BMP, TIF, GIF, JPG,  Có thể nhận dạng trực tiếp tài liệu quét qua Scanner không cần lưu trữ dưới dạng tệp ảnh trung gian. Các trang tài liệu có thể được quét và lưu trữ dưới dạng tệp tin nhiều trang. Các chức năng chính: - Phân tích cấu trúc vật lý của tài liệu và đưa ra cấu trúc phân vùng - Phân tích và nhận dạng chữ đầu ra là text có thể copy hay lưu trữ và soạn thảo lại được. Hình 10: VnDOCR và một ví dụ nhận dạng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  17. 17 Một số hạn chế: Tính đến phiên bản 4.0 - VnDOCR chỉ làm việc với ảnh đen trắng - Với các ảnh có cấu trúc vật lý phức tạp VnDOCR cho kết quả còn hạn chế (Hinh 11, 12) Thí nghiệm 1: - Với ảnh đầu vào như sau: Hình 11: Ảnh mẫu có cấu trúc vật lý phức tạp - Kết quả phân tích của VnDOCR không tim thấy vùng văn bản nào mà chỉ khoanh vùng được 2 vùng ảnh (1,2) như Hình 12 Hình 12: Kết quả ra hai vùng ảnh với ảnh mẫu 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  18. 18 Thí nghiệm 2: Với ảnh đầu vào có cấu trúc vật lý đơn giản hơn (các vùng cơ sở có bao là hình chữ nhật – Hình 13). 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  19. 19 Kết quả phân tích bởi VnDOCR bỏ sót một vùng văn bản và gộp nhầm 2 vùng ảnh vào vùng văn bản số 1 (Hình 14). Hình 14: Kết quả phân tích với ảnh 13 1.4.2. OminiPage OmniPage là phần mềm nhận dạng văn bản của NUANCE. Nó có thể chuyển đổi các file ảnh tài liệu hay file PDF sang dạng file văn bản có thể đọc được bởi các phần mềm soạn thảo như Office, với khả năng nhận dạng các ký tự la tinh chính xác tới 99%. Một số đặc tính chính: - Nhận dạng chính xác tới 99% trên 119 ngôn ngữ khác nhau - Nhận dạng cả các file vào là PDF - Nhận dạng được các trang có nhiều loại font, kiểu font hoặc có nền là ảnh mầu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  20. 20 - Một số hạn chế chính: Chưa hiệu quả với các ảnh tài liệu có cấu trúc phức tạp. Thí nghiệm 1: Với ảnh đầu vào Hình-11 có kết quả như sau: Omnipage đoán nhận tất các ảnh đều là vùng văn bản (Hình-15) Thí nghiệm 2: Với ảnh đầu vào 13, tương tự như VnDOCR OmniPage vẫn phân vùng sai (Hình 16) Hình 15: Đầu ra phân vùng chỉ có 1 vùng văn bản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  21. 21 Vùng lỗ i Hình 16: Đầu ra có vùng chứa cả ảnh và text 2.4.3. Finereader Finereader là một sản phẩm ORC của ABBYY với một số tính năng chính sau: - Cho phép kết nối và nhận dạng ảnh trực tiếp từ Camera. - Nhận dạng được 38 ngôn ngữ khác nhau. - Nhận dạng cả text trong đồ họa. - Với 2 mẫu văn bản có cấu trúc phức tạp như trên thì Finereader đều cho hiệu quả cao, nói chung Fineread đều có hiệu quả cao với các tài liệu có bố cục phức tạp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  22. 22 Hình 17: Với ảnh 13 đạt hiệu quả 90% Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  23. 23 Hình 18 Với ảnh I-15 hiệu quả đạt 100% Hình 19: Với mẫu phức tạp hơn Finereader cho kết quả 95% Hạn chế chính của Finereader là tốc độ làm việc chậm so với 2 phần mềm kể trên. I.5. Kết luận Từ những kết quả ở trên phạm vi đề tài ở đây sẽ chỉ tập trung vào việc phân tích cấu trúc vậy lý của một trang tài liệu (trình bày chi tiết ở chương 2). Để cải tiến hơn, đối tượng của đề tài sẽ là ảnh màu có độ phức tạp cao. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  24. 24 CHƢƠNG 2. MỘT SỐ KỸ THUẬT XỬ LÝ TRANG VĂN BẢN Với phạm vi đặt ra ở chương một và phần mở đầu là đề tài sẽ tập trung vào giải pháp phân tích cấu trúc vật lý của trang tài liệu, chương 2 sẽ giới thiệu một số phương pháp phân tích hiện nay, từ đó đưa ra và đánh giá được ưu nhược điểm của mỗi phương pháp đó. Sau đó sẽ tập trung phân tích kỹ một phương pháp mới chưa được trình bày ở các đề tài trước đó là Fractal Signature với những ưu điểm vượt trội của nó là hiệu quả cao với tài liệu phức tạp, không phân biệt góc nghiêng. Đồng thời thiết kế hệ thống demo với giải pháp mới này. 2.1. Các phƣơng pháp phân tích định dạng trang tài liệu 2.1.1. Top-down a) Tổng quan Ý tưởng chính của thuật toán là phân tách liên tiếp từ một trang ban đầu thành các vùng cơ sở nhỏ hơn. Các khối cơ sở ở đây là các khối như đoạn văn, tiêu đề, đồ họa, Việc phân tách chúng thành các vùng riêng biệt dựa trên tiêu chí về ngưỡng khoảng cách mà phương pháp phổ thông nhất là xác định thông qua kết quả của phép chiếu nghiêng.  Phép chiếu nghiêng theo hướng x bất kỳ: Thực chất là đi xác định lược đồ xám bằng cách tính tổng các điểm ảnh đa cấp xám đen (hoặc trắng) theo phương vuông góc với x dọc theo trục y. Trong thực tế x thường là phương nằm ngang hay phương thẳng đứng so với trang văn bản. Một ví dụ về phép chiếu nghiêng với một trang tài liệu cho ở Hình-20: Trên lược đồ xám của phép chiếu nghiêng sẽ xuất hiện các điểm cực trị, với phép chiếu nghiêng theo phương thẳng đứng ta dễ nhận thấy độ rộng của các đáy chính là khoảng cách giữa hai dòng, với các độ rộng của đáy nào đó mà tần suất xuất hiện ít hoặc vượt quá một ngưỡng chính là khoảng các giữa hai vùng văn bản. Còn tại vị trí các đỉnh là trục của mỗi dòng văn bản. Với phép chiếu nghiêng theo phương ngang ta có thể phân tách được các cột hay các vùng cơ sở dựa vào ngưỡng khoảng cách của đáy (Hình-20). Cũng theo Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  25. 25 nguyên tắc này nếu áp dụng phép chiếu nghiêng trên mỗi dòng văn bản ta cũng có thể phân đoạn được các ký tự hoặc các từ dựa vào khoảng cách của đáy (ví dụ như Hình-21). 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  26. 26 Hình 21: Phân tách cột dựa vào phép chiếu nghiêng theo phƣơng ngang5 Hình 22: Phép chiếu nghiêng theo phƣơng ngang để phân đoạn ký tự hoặc từ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  27. 27 b) Hạn chế: Phân tích top-down tồn tại nhiều hạn chế như: - Kém hiệu quả với các loại tài liệu có bố cục phức tạp (hình 25). - Cần xoay ảnh về đúng vị trí ngang nếu ảnh bị nghiêng (hình 23,24). - Làm việc tốt chỉ với ảnh nhị phân. - 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. - 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. 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ự Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  28. 28 Hình 204: Lƣợc đồ chiếu đứng của trang tài liệu bị nghiêng Hình 215: Lƣợc đồ chiếu đứng của một bài báo Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  29. 29 2.1.2. Bottom-up a) Tổng quan Bottom-up bắt đầu với những phần nhỏ và tìm cách nhóm chúng vào những phần lớn hơn, liên tiếp tới khi mọi khối trên trang được xác định. Trong phạm vi luận văn này, chỉ giới thiệu một số cách tiếp cận được coi là bottom-up nhưng sử dụng những phương pháp trực tiếp rất khác nhau nhằm đạt cùng mục đích.  Môt giải pháp được mô tả với các bước như sau: 1. Xác định góc nghiêng  thông qua phép biến đổi Hough 2. Xác định khoảng cách giữa các dòng thông qua việc xác định khoảng cách giữa các đỉnh của phép chiếu nghiêng  cố định bằng góc nghiêng tìm được. 3. Làm trơn theo loạt (run-length-smothing), sau đó thực hiện tách các từ hoặc ký tự dựa vào việc xác định các khoảng trắng trong dòng thông qua việc tìm đỉnh trên biểu đồ chiếu nghiêng và các độ dài vùng đen (các từ). 4. Thực hiện phép nhóm bottom-up các phần văn bản nhờ một loạt thao tác làm trơn theo loạt, theo các hướng. Kết quả thu được là các vùng ON và ta phân tích các vùng liên thông trên đó. Tính toán một vài số liệu trên những vùng liên thông này, ví dụ khoảng chiều cao và chiều dài các từ. Những thông tin đặc trưng này được dùng để phân biệt các khối văn bản và phân biệt phần văn bản và phần đồ họa. Esposito đã dùng cách tiếp cận tương tự, nhưng trước hết xác định hợp biên của từng ký tự, sau đó thao tác trên hợp biên này, thay vì trên từng pixel nhằm giảm lượng tính toán.  Một phương pháp Dostrum bó cụm khác thực hiện với k lân cận gần nhất để nhóm các ký tự và các dòng văn bản và các khối cấu trúc (Hình 26). - Trước tiên, với mỗi phần tài liệu, xác định các đường nối k lân cận gần nhất với các phần xung quanh. Khoảng cách và góc của các đường nối này được vẽ trên các biểu đồ. Vì hầu hết các đường nối được tạo giữa các ký tự cùng dòng, góc tối đa sẽ chỉ ra góc nghiêng và khoảng cách tối đa sẽ là khoảng cách giữa các ký tự. Sử dụng các ước lượng này, các dòng văn bản được xác định như nhóm các ký tự và các từ dọc theo hướng của trang. Các dòng văn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  30. 30 bản được nhóm thành các khối-sử dụng đặc tính của tài liệu là các dòng cùng khối thường gần nhau hơn các dòng khác khối. Hình 226: Phƣơng pháp Dostrum cho phân tích định dạng trang từ dƣới lên. (a) Một phầ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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  31. 31 b) Hạn chế Phương pháp phân tích Bottom-Up cũng tồn tại nhiều hạn chế như sau: - 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. - 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 - Cũng như Top-Down hiệu quả phục thuộc trực tiếp vào việc xác định được góc nghiêng của tài liệu, vì khoảng cách dòng và từ chỉ xác định chính xác được nếu góc nhiêng của tài liệu ≈00 - 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). - 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 đặc biêt với chữ viết tay thì chương trình rất khó có thể tính được chiều cao chữ hay độ rộng giữa hai dòng thông qua biểu đồ chiếu nghiêng. 2.1.3. Phƣơng pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) a) Tổng quan Phương pháp phân tích Adaptive Split – and – Merge được Lui, Tang và Suen thiết kế với ý tưởng chính từ một trang tài liệu ban đầu và coi đó như một vùng chưa đồng nhất, từ đó liên tiếp chia mỗi vùng thành các vùng nhỏ hơn, tại mỗi bước chia thực hiện nối các vùng đồng nhất và chia tiếp các vùng không đồng nhất. Để có thể mô tả được thuật toán một cấu trúc cây tứ phân phân lớp được sử dụng để biểu diễn quá trình tách và nối của thuật toán. Trong đó nút ở đỉnh tương ứng với trang tài liệu ban đầu và là gọi là lớp cao nhất, các nút con tiếp theo là các vùng con tương ứng với lớp thứ k của bước chia thứ k các vùng không đồng nhất (mô tả ở hình).  Các bước của thuật toán[7]: B1: Tại lớp thứ K nếu tìm thấy một vùng không đồng nhất thì tiến hành chia vùng đó thành 4 vùng nhỏ hơn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  32. 32 B2: Nếu thấy ít nhất 2 vùng trong 4 vùng vừa tách là đồng nhất thì tiến hành nối chúng lại, còn các vùng không đồng nhất ta qua lại B1 và tách chúng thành các vùng ở lớp thứ K+1. Lớp 0 (Trang tài liệu) (Nối 2 vùng đồng nhất) Lớp 1 (Trang tài liệu được Tách vùng không chia thành 4 cùng nhỏ đồng nhất ở lớp 1 hơn) thành 4 vùng nhỏ hơn Lớp 2 Hình 237: Mô tả thuật toán Tách và Nối thích nghi   Tiêu chuẩn xác định vùng đồng nhất để nối ghép[7] Hai vùng tương ứng rm và rn được coi là đồng nhất nếu chúng thảo mãn điều kiện sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  33. 33 Trong đó: Trong đó: Nm và Nn biểu thị số vùng con trong mỗi vùng tương ứng rm và rn. và biểu thị giá trị trung bình của mỗi vùng tương ứng rm và rn. b) Ƣu điểm - Có thể áp dụng với các loại trang tài liệu có cấu trúc phức tạp vì thuật toán này không quan tâm đến việc phân đoạn các thành phần cơ sở, mà chỉ chia trang tài liệu thành các vùng hình chữ nhật và xem xét giá trị trung bình của nó. Như vậy các trang tài liệu có thể bỏ qua khâu xác định và hiệu chỉnh độ nghiêng - Có thể áp dụng cho các loại trang tài liệu có nhiều loại font chữ khác nhau - Tốc độ thực hiện nhanh hơn so với Top-down và Bottom-up c) Hạn chế - Hiệu quả của thuật toán phụ thuộc vào giá trị trung bình của vùng được xét, trong một số tình huống thì giá trị trung bình của vùng văn bản và vùng đồ họa là như nhau. Cho nên thuật toán này vẫn có thể phân đoạn nhầm. - Không có một giá trị hằng số τ cho mọi trang tài liệu vì thế việc xác định giá τ là một vấn đền khó. 2.1.4 Phƣơng pháp phân tích trang văn bản dựa trên Tab-Stop a) Tổng quan Khi một trang được bố trí, hoặc bằng một hệ thống xuất bản chuyên nghiệp, hoặc bằng một trình xử lý thông thường, các vùng của trang được các tab-stop giới hạn. Các mép, lề cột, thụt đầu dòng và các cột của bảng tất cả được đặt cố định tại Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  34. 34 các vị trí - x mà tại đó các cạnh hoặc các trung tâm của dòng văn bản được theo chiều dọc. Các tab-stop chỉ ra sự khác biệt các bảng từ văn bản chính và các tab- stop cũng giới hạn các yếu tố hình chữ nhật không cột, chẳng hạn như hình ảnh rời và một đoạn văn bản rời. Hình 28: ảnh đầu vào Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  35. 35 Các tab-stop trong ví dụ của Hình 28 là ranh giới cột với một tab-stop bổ sung cho thụt đầu dòng đoạn văn bản, không cần thiết cho việc tìm bố trí trang. Hình rời không phải hình chữ nhật thông thường, ra bên ngoài các ranh giới cột. Một mặt nào đó, các hình chữ nhật màu trắng phù hợp với các tab-stop, nhưng hình chữ nhật trắng có thể bị gián đoạn bởi nhân vật nền hoặc hình ảnh nền. Ngoài ra các đoạn cuối của hình chữ nhật trắng không phù hợp với các đoạn cuối của khu vực được các tab-stop giới hạn, bởi vì các hình chữ nhật màu trắng chạy vào các khoảng trắng vuông góc. Thuật toán đề xuất tương tự như các phương pháp hình chữ nhật khoảng trắng trong đó nó sử dụng một phương pháp từ dưới lên để tìm cấu trúc từ trên xuống, nhưng thay vì tìm khoảng không giữa các cột, thì nó lại tìm các tab-stop đánh dấu các cạnh của chúng và thông qua việc kết hợp thêm các phương pháp từ dưới lên và từ trên xuống, đối phó một cách dễ dàng với vùng không phải hình chữ nhật. Có những giai đoạn chính: tiền xử lý, trong đó phân tích thành phần tiếp nối và hình thái đi từ dưới lên từ giả thuyết ban đầu trên các loại dữ liệu tại chỗ; định dạng tab-stop từ dưới lên; tìm cách bố trí cột, và cuối cùng áp dụng cách bố trí cột để tạo ra một tập lệnh của các vùng đánh máy b) Phƣơng pháp phân tích trang văn bản dựa trên Tab-Stop Phương pháp phân tích trang văn bản được xây dựng theo các bước sau: 1- Tiền xử lý Mục đích của bước tiền xử lý là xác định các dải phân cách dòng, các khu vực hình và tách các bộ phận kết nối còn lại vào các thành phần văn bản chờ đợi và một lượng nhỏ hơn của loại không cụ thể. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  36. 36 Hình 29. (a) Đƣờng dọc, (b) Các thành phần hình. Bắt đầu với hình của Hình 28, việc xử lý hình thái học từ Leptonica [8] xác định các đường thẳng đứng cho thấy ở Hình. 29 (a) và mặt nạ hình được hiển thị trong Hình. 29 (b). Những yếu tố được xác định này trừ từ các hình đầu vào trước khi đi qua các hình làm sạch để phân tích thành phần kết nối. Các thành phần kết nối (CCs) được lọc theo chiều rộng (w) và chiều cao (h) thành các cỡ nhỏ, vừa và lớn như sau: CCs với h 2h75 hoặc w> 8h75 là lớn, và phần còn lại là trung bình. Việc tách lọc này quan trọng vì các thành phần kết nối nhỏ (CCs) (tab hay các dấu) và thành phần kết nối lớn (bản vẽ, biểu tượng hoặc khung) có khả năng đảo lộn các thuật toán dòng văn bản, nhưng các tiêu đề văn bản lớn là rất quan trọng để đọc xác định trình tự. Các thành phần kết nối lớn được coi là văn bản ở giai đoạn này nếu có phần bên trái hoặc phải có dải chiều rộng tương đương. Trên phông chữ "bắt buộc", dải chiều rộng trên đường thẳng đứng là lớn hơn hơn trên đường ngang, do vậy dải chiều rộng được tính riêng theo cả hai hướng. Dải chiều Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  37. 37 rộng được tính từ theo tối đa chiều ngang và chiều dọc tại chỗ của hàm khoảng cách trên hình đôi của thành phần kết nối. Hình 3 cho thấy các thành phần kết nối được tách lọc như là văn bản trung bình và lớn. Hình 30: filtered CCs 2 - Tìm các vị trí Tab Quá trình các đoạn dòng tab-stop tìm thấy có một số bước nhỏ chính: các thành phần kết nối ứng tab-stop thích hợp mà dường như chúng có thể tại cạnh của một vùng văn bản được tìm thấy và sau đó được nhóm vào các dòng tab-stop, sau đó kết nối giữa các dòng tab-stop được tìm thấy, cho phép loại dương bản giả. a.Tìm kiếm thành phần tab-stop phù hợp Các thành phần kết nối tab-stop ban đầu phù hợp được tìm thấy bằng tìm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  38. 38 kiếm tỏa tròn bắt đầu từ mỗi thành phần kết nối CC lọc từ tiền xử lý. Cho rằng thành phần kết nối CC là tại một điểm dừng tab, việc tìm kiếm cho bên cạnh liên kết và các bên cạnh trong rãnh nơi có phải là một khoảng không. Mỗi thành phần kết nối CC đều được xử lý một cách độc lập và đánh dấu dù cho đó là một tab trái, tab bên phải phù hợp hoặc đều không phù hợp. Hình 4 (a) minh họa Các thành phần kết nối tab-stop phù hợp . 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 b. Nhóm các thành phần tab phù hợp Các thành phần kết nối tab phù hợp được nhóm thành các dòng và nơi đủ nhiều các thành phần kết nối trong một nhóm, chúng được giữ lại. Một trung tuyến nhỏ nhất của thuật toán hình vuông được sử dụng để phù hợp với một dòng vào cạnh (trái hoặc phải) thích hợp của từng thành phần kết nối trong một nhóm. Sau khi tìm thấy tất cả các đoạn dòng tab-stop, tất cả các dòng được làm phù hợp lại để hướng điều kiện trang có nghĩa là tất cả các thành viên của thành phần kết nối rơi vào một bên của đoạn dòng. c. Đặt các dòng văn bản để kết nối các tab-stop Bước tiếp theo kết nối các tab-stop bằng cách đặt dòng văn bản từ một tab- Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  39. 39 stop đến tab-stop khác. Liền sát, các thành phần kết nối chồng chéo theo chiều dọc đủ điều kiện, nhưng không thể nhảy những khoảng trống lớn. Các tab-stop có một dòng văn bản kết nối chúng được kết hợp với nhau, khi dường như hai bên đối diện của một cột văn bản. Hình 4 (b) cho thấy các dòng tab -stop và các dòng văn bản kết nối. Các dòng Tab-stop dòng không có kết nối được loại bỏ. Chiều rộng xảy ra thường xuyên nhất của các dòng văn bản kết nối tab-stop được ghi nhận để sử dụng trong việc tìm kiếm bố trí cột. d. Làm sạch đoạn cuối tab-stop Bước cuối cùng cố gắng để làm các dòng kết nối các dòng tab kết thúc tại tung độ y, bằng cách cho phép đoạn cuối để di chuyển giữa thành phần kết nối thành viên, mà cạnh của nó được sử dụng cho dòng tab và thành phần kết nối không phải là thành viên thứ nhất đó là sự phân cách dòng. Hình 32: cho thấy các phân đoạn dòng tab cuối. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  40. 40 Sau khi xây dựng các tab-stop, các thành phần nối tiếp được phân loại lại, thì "văn bản" hoặc "vô danh" sử dụng các thuật toán theo dòng văn bản giống nhau như đã được sử dụng như trên để tìm các kết nối giữa những tab-stop. Nếu một nhóm của các thành phần kết nối có độ rộng đáng kể tạo thành một gới hạn văn bản, thì sau đó chúng được phân loại như văn bản. Hình nhân tạo các thành phần nối tiếp tương tự như thành phần kết nối (CCd) văn bản chính được tạo ra từ mạng hình ảnh từ việc tiền xử lý hình thái. 3 – Tìm các bố trí cột Bước lớn tiếp theo là tìm cách bố trí cột của trang. Tất cả các phần còn lại của các bước làm cho việc sử dụng các đối tượng Phân vùng Cột (CP) được tạo ra ngay bây giờ. Quét các thành phần kết nối từ trái sang phải và trên xuống dưới, chạy các thành phần kết nối được phân loại giống nhau (văn bản, hình ảnh, hoặc vô danh) được tập hợp vào các Phân vùng Cột bị ràng buộc không có Phân vùng Cột có thể vượt qua một giới hạn tab-stop. Hình 6 cho thấy kết quả của quá trình này. Một tập hợp của các thành phần kết nối từ một lần quét ngang được lưu trữ trong một bộ Phân vùng Cột. Mỗi bộ Phân vùng Cột có khả năng chia trang vào các cột tại vị trí thẳng đứng. Do vậy, tìm cách bố trí cột do đó là một quá trình tìm một bộ Phân vùng Cột tối ưu mà mọi "những giải thích" tốt nhất (xem bên dưới) về các bộ Phân vùng Cột trên trang, nhưng đầu tiên có một số định nghĩa: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  41. 41 Hình 33: Cột chính(cps) Một Phân vùng Cột tốt hoặc chạm vào một giới hạn tab trên cả hai cạnh dọc của khung giới hạn của nó, hoặc chiều rộng của nó là gần với một chiều rộng thường xảy ra. (Xem 2.c). Độ bao phủ của một bộ Phân vùng Cột là tổng chiều rộng của tất cả các Phân vùng Cột tốt mà nó chứa. Bộ Phân vùng Cột A là tốt hơn so với Bộ Phân vùng Cột B nếu A có độ bao phủ rộng hơn, hoặc tương tương, nhưng các Phân vùng Cột tốt hơn, hoặc các Phân vùng Cột bằng nhau, nhưng tổng số các Phân vùng Cột nhiều hơn. Bộ Phân vùng Cột A giải thích bộ B trừ khi một hoặc nhiều điều sau đây là đúng: 1. Cạnh của một trong những Phân vùng Cột B nằm ngoài của tất cả các Phân vùng Cột A. Điều này không được phép, vì nó cho thấy rằng B có nhiều văn bản hơn so với A. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  42. 42 2. Các cạnh của một trong các Phân vùng Cột B rơi vào các thành phần kết nối khác nhau của A và chiều rộng của Phân vùng Cột B là chung. Điều này có nghĩa rằng A đã chia một cột có chiều rộng chung. 3. Cạnh phải của một trong các Phân vùng Cột B rơi vào các Phân vùng Cột A giống nhau khi cạnh trái của Phân vùng Cột B tiếp theo và các Phân vùng Cột B có chiều rộng gần như nhau. Có vẻ như A có một số khác so với B. Các điều kiện cùng một chiều rộng cho phép A để giải thích B với phần in rời. 4. Cả hai cạnh của hai bộ Phân vùng Cột B rơi vào trong cùng một thành phần kết nối của A. Điều này có nghĩa rằng A đã sáp nhập hai cột của B. Lưu ý rằng hai cạnh của một trong các Phân vùng Cột B được phép rơi vào hai Phân vùng Cột A, miễn là chiều rộng không phải là chung. Điều này cho phép tiêu đề hợp nhất cột trong B được giải thích bằng A. Một danh sách các ứng cử viên cột được thực hiện từ bộ Phân vùng Cột trên trang, lệnh tốt nhất và với hai lần loại do A giải thích quy tắc B trên. Trong quá trình này, tất cả các Phân vùng Cột hình được bỏ qua. Sau khi tạo sự phù hợp ban đầu, thì phải được cải thiện bằng cách thêm các Phân vùng Cột mới và mở rộng các Phân vùng Cột hiện có, bằng cách sử dụng các cạnh của một Phân vùng Cột trong bộ Phân vùng Cột khác nhau trong khi mở rộng không gây chồng chéo của các Phân vùng Cột. Một quá trình lặp đi lặp lại sau đó các nhãn đoạn dài nhất liên tiếp (cho phép một vùng rất nhỏ thất bại) các tọa độ y trang được giải thích bởi một trong những phù hợp cột. Hình 7 cho thấy kết quả của quá trình này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  43. 43 Hình 34: làm sạch các tab-stop 4 – Tìm các khu vực Sau khi tìm thấy các cột, thì chữ được cho các Phân vùng Cột theo bao nhiêu cột mà các cột có. Các Phân vùng Cột trong một cột được in, phân vùng chạm vào nhiều hơn một cột, nhưng không mở đến các cạnh bên ngoài của cả hai bên được in rời và các phân vùng mà mở rộng hoàn toàn nhiều hơn một cột là tiêu đề. a.Tạo luồng in của các Phân vùng Cột Mỗi Phân vùng Cột chọn khung trên và dưới phù hợp nhất của nó, khung là Phân vùng Cột theo chiều dọc gần nhất mà chồng chéo theo chiều ngang. Vì mỗi Phân vùng Cột tự nó bảo đảm với khung lựa chọn của nó, mỗi Phân vùng Cột có thể không có hoặc nhiều khung trên và dưới bảo đảm. Kích thước của danh mục của các khung bảo đảm buộc phải trở thành không hay một cho mỗi khung trên và dưới, bằng cách sử dụng các quy tắc sau đây để: 1. Loại. Nếu có nhiều chữ, thì văn bản chỉ có thể ở lại với loại hình của nó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  44. 44 (chính xác) của riêng, trong khi đó hình có thể ở lại với bất kỳ loại hình nào khác. 2. Các phím tắt khung dịch chuyển bị phá vỡ. Nếu A có 2 khung B và C và cũng như B có C như là một khung trong cùng một hướng, thì hãy xóa C như là một khung của A, để lại một chuỗi ABC đã làm sạch. Ngoài ra, nếu A có một đối tác B và B có một khung A trong cùng một hướng, hãy phá vỡ quy trình. 3.Chỉ có văn bản. Nếu A vẫn còn 2 khung B, C thì đuổi theo khung B và C để xem cái có các chuỗi dài nhất. Hãy xóa từ A khung mà có chuỗi ngắn nhất và chuyển đổi các loại chuỗi ngắn nhất để in rời. 4. Chỉ có hình. Hãy chọn Phân vùng Cột khung CP với sự đè ngang lớn nhất . Hình 35: Typed partition chains Hình 35: Typed partition chains Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  45. 45 Tất cả các Phân vùng Cột có khung 0 hoặc 1. Mặc dù vậy, hãy theo (theo lại) quy tắc 1 ở trên. Việc thanh lọc tất cả các chuỗi văn bản thành một loại duy nhất và chia tách các chuỗi văn bản từ chuỗi hình. Chuỗi hình được tinh lọc bằng cách thiết lập tất cả các Phân vùng Cột trong một chuỗi đến loại chung nhất trong chuỗi. Hình 8 cho thấy các Phân vùng Cột chữ cuối nơi văn bản đổ vào là màu xanh, văn bản tiêu là màu lục lam, hình tiêu đề là màu đỏ tươi và hình in rời có màu cam. Các chuỗi của các Phân vùng Cột văn bản sau này được chia thành các nhóm khoảng cách dòng cố định, nó tạo các khối văn bản. Hiện tại, mỗi chuỗi các Phân vùng Cột đại diện cho một khu vực phù hợp, nhưng các khu vực đều phải có thứ tự. b. Đọc xác định thứ tự Nhớ rằng các phần hình ảnh và văn bản được phân loại theo một trong 3 khả năng: in liên tục, in rời và tiêu đề. Ngoài ra, trang được chia thành các đoạn bố trí cột phù hợp. Với thông tin này, thứ tự đọc hợp lý bỏ một vài quy định đơn giản sau: 1. Khối liên tục theo vị trí y trong giới hạn một cột. 2. In rời các khối theo theo vị trí của y trong một cột hình giữa các cột thực sự mà họ chạm vào. 3.Một tiêu đề mở nhiều cột và sau đó là bất kỳ mà trên nó trong các cột mở rộng hoặc giữa chúng. Bất cứ cái gì nằm trong các cột tương tự dưới đây tiêu đề này theo sau nó. 4. Thực hiện một sự thay đổi trong cách bố trí cột như là một tiêu đề. Bất cứ điều gì trong bất kỳ cột được thay đổi (hoặc giữa chúng) tới, trước khi bất cứ điều gì trong các cột mới. Cột không thay đổi không bị ảnh hưởng bởi một sự thay đổi nào đó trong cách bố trí cột. 5. Giữa tiêu đề, nội dung của các cột được sắp xếp từ trái sang phải. c.Tìm ranh giới đa giác cho từng vùng Để đơn giản việc thực hiện, các đa giác khu vực là isothetic: ví dụ, các cạnh xen kẽ giữa ngang và song song với dòng tab trung bình (khoảng dọc). Các cạnh đa giác được lựa chọn để giảm thiểu số lượng các đỉnh, trong khi đáp ứng những cản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  46. 46 trở mà tất cả các tạo dòng (CPs ) được chứa trong đa giác vùng của chúng và không có tạo dòng (CP) từ các phân vùng khác . Hình 36: Các khối cuối cùng C) Đánh giá thuật toán phân tích trang văn bản dựa trên Tab-Stop Tab-stop tạo ra sự lựa chọn thú vị và hữu ích để hình chữ nhật màu trắng cho việc tìm kiếm các cấu trúc cột của một trang. Kết hợp khái niệm cấu trúc cột từ trên xuống với các phương pháp phân loại từ dưới lên cho phép phân tích bố cục trang để dễ dàng xử lý bố trí phức tạp không phải hình chữ nhật của các trang tạp chí hiện đại mà không mất thị giác của "bức tranh lớn hơn" mà thường xảy ra khi sử dụng riêng các phương pháp từ dưới. Các thuật toán được mô tả không có định dạng hoặc phân tích bảng, nhưng các tab-stop làm cho tính năng đặc biệt hữu ích cho cả hai, vì vậy trong tương lai, việc phân tích bảng sẽ được thêm vào. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  47. 47 2.2. Lựa chọn giải pháp Các phương pháp phân tích Top-down, Bottom-up và Phương pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) đã được một số nghiên cứu trong nước phát triển, vì thế trong đề tài này sẽ dừng ở mức độ giới thiệu để so sánh. Từ phần II.1 dễ nhận thấy rằng thuật toán phân tích trang văn bản dựa trên Tab-Stop có nhiều ưu điểm vượt trội với các loại ảnh tài liệu có cấu trúc phức tạp. Đồng thời có thể làm việc với ảnh đa cấp xám, điều mà Top-down (TD) và Bottom-up (BU) không làm được. Vì thế trong phạm vi đề tài này sẽ tập trung nghiên cứu và triển khai phương pháp phân tích trang văn bản dựa trên Tab-stop với các mục tiêu sau: - Phân tích với ảnh đa cấp xám có cấu trúc phức tạp và nhiễu. - Phát triển tab-stop có hiệu quả cao với các loại trang tài liệu có cấu trúc phức tạp mà Top-down, Bottom-up và Phương pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) kém hiệu quả. - Đầu ra của hệ thống là khoanh vùng được vùng ảnh và vùng văn bản. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  48. 48 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  49. 49 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  50. 50 Hình 39: ảnh 003.FindTabBoxes: Các thành phần tab-stop ứng cử (candidate tab-stop CCs) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  51. 51 Ả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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  52. 52 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  53. 53 Hình 42: ảnh 020.MovePartitionsToGrid Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  54. 54 Hình 43: ảnh 024.InitialPartitions Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  55. 55 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  56. 56 Ả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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  57. 57 Hình 46: ảnh 038.RefinePartitionPartners Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  58. 58 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  59. 59 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  60. 60 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ả Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  61. 61 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  62. 62 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ế. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  63. 63 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  64. i 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  65. ii 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  66. iii 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  67. iv 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  68. v 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên