Luận văn Nhận dạng chữ viết và phân tích trang tài liệu

106 trang yendo 7110

Download

Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nhận dạng chữ viết và phân tích trang tài liệu", để 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:

luan_van_nhan_dang_chu_viet_va_phan_tich_trang_tai_lieu.pdf

Nội dung text: Luận văn Nhận dạng chữ viết và phân tích trang tài liệu

Luận văn Nhận dạng chữ viết và phân tích trang tài liệu
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Mục lục Mục lục i Danh mục các hình ảnh iv MỞ ĐẦU 1 I. Đặt vấn đề 1 II. Nội dung nghiên cứu 2 III. Bố cục của luận văn 4 Chƣơng I. TỔNG QUAN VỀ NHẬN DẠNG CHỮ VIẾT 5 VÀ PHÂN TÍCH TRANG TÀI LIỆU 5 I.1. Ảnh tài liệu và nhận dạng ảnh tài liệu 5 I.1.1. Tổng quan về ảnh tài liệu 5 I.1.2. Nhận dạng tài liệu và vai trò của phân tích ảnh tài liệu 6 I.2. Cấu trúc của ảnh tài liệu 7 I.2.1. Cấu trúc vật lý 8 I.2.2. Cấu trúc logic 10 I.3. Quá trình phân tích tài liệu 10 I.3.1. Tiền xử lý(preprocessing): 11 I.3.2. Phân tích cấu trúc vật lý 12 I.3.3. Phân tích cấu trúc logic 13 I.4. Một số hệ thống phân tích tài liệu hiện nay 14 I.4.1. VnDOCR 14 I.4.2. OminiPage 18 I.4.3. Finereader 20 I.5. Kết luận 22 Chƣơng II: CÁC PHƢƠNG PHÁP TIẾP CẬN 23 ĐỂ PHÂN TÍCH TRANG TÀI LIỆU 23 II.1. Các phƣơng pháp phân tích định dạng trang tài liệu 23 II.1.1. Top-down 23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên i GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy II.1.2. Bottom-up 30 II.1.3. Phƣơng pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) . 32 II.1.4. Fractal Signature (FS) 34 II.2. Lựa chọn giải pháp 38 II.3. Thiết kế hệ thống 39 II.3.1. Sơ đồ khối 39 II.3.2. Ảnh đầu vào 39 II.3.3. Module Tiền xử lý 40 II.3.4. Phân tích sử dụng giả pháp Fractal Signature 41 II.4. Kết luận 45 Chƣơng III: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM 46 III.1. Yêu cầu hệ thống 46 III.2. Thiết kế chƣơng trình 46 III.2.1. Cấu trúc dữ liệu 46 III.2.2. Module chuẩn hóa ảnh 48 III.2.3. Module giao diện chính 51 III.2.4. Module phân tích Top-down (TD) 52 III.2.5. Module phân tích Fractal Signature 55 III.2.6. Module lọc và làm trơn nhiễu 57 III.2.7. Module mô phỏng thuật toán FS 58 III.2.8. Các hàm chức năng chính của image processing tool trong matlab sử dụng trong chƣơng trình 60 III.3. Kết luận và đánh giá kết quả 62 Kết luận 83 TÀI LIỆU THAM KHẢO 84 Phục Lục 85 A. Mã nguồn đầy đủ của chƣơng trình 85 A.1. Danh mục các chƣơng trình con trong chƣơng trình 85 A.2. Sơ khối liên kết giữa các thủ tục trong chƣơng trình 86 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ii GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy A.3. Mã nguồn các module 86 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên iii GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 5 Hình 2: Ví dụ ảnh tài liệu 6 Hình 3: Sơ đồ OCR cơ bản 7 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] 9 Hình 5: Ví dụ loại tài liệu có bố cục phức tap 10 Hình 6: Sơ đồ nguyên lý hệ thống xử lý tài liệu[6] 11 Hình 7: a - Ảnh gốc b - Ảnh sau khi tách nền 12 Hình 8: Ví dụ một ảnh tài liệu bị nghiêng một góc 5 độ 13 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] 14 Hình 10: VnDOCR và một ví dụ nhận dạng 15 Hình 11: Ảnh mẫu có cấu trúc vật lý phức tạp 16 Hình 12: Kết quả ra hai vùng ảnh với ảnh mẫu 11 16 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 17 Hình 14: Kết quả phân tích với ảnh 13 18 Hình 15: Đầu ra phân vùng chỉ có 1 vùng văn bản 19 Hình 16: Đầu ra có vùng chứa cả ảnh và text 19 Hình 17: Với ảnh 13 đạt hiệu quả 90% 20 Hình 18 Với ảnh I-15 hiệu quả đạt 100% 21 Hình 19: Với mẫu phức tạp hơn Finereader cho kết quả 95% 22 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ệu 24 Hình 21: Phân tách cột dựa vào phép chiếu nghiêng theo phƣơng ngang 25 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 29 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 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên iv GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy (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. 31 Hình 27: Mô tả thuật toán Tách và Nối thích nghi 33 Hình 28: Mô tả thuật toán FS 35 Hình 29: Sơ đồ khối hệ thống phân tích tài liệu trong phạm vi đề tài 39 Hình 30: Ví dụ một bolck chuyển sang dạng bề mặt trong không gian 3D 41 Hình 31: Ví dụ chuyển ảnh chữ "c" sang dạng bề mặt trong không gian 3D 41 Hình 32: (a) Ảnh một tài liệu gốc, (b) kết quả sau khi áp dụng FS 44 Hình 33: Giao diện chính 51 Hình 34: Kết quả phân tích của top-down trên tài liệu có cấu trúc đơn giản 63 Hình 35: Kết quả phân tích của top-down trên tài liệu có cấu trúc bảng 65 Hình 36: : Kết quả phân tích của top-down trên tài liệu thuần văn bản 67 Hình 37: : Kết quả phân tích của top-down trên tài liệu có cấu trúc phức tạp (trang tạp trí) 69 Hình 38 : Kết quả phân tích của top-down trên một tờ quảng cáo 71 Hình 39: Kết quả phân tích của top-down trên tài liệu có cấu trúc phức tạp 73 Hình 40: Kết quả phân tích của top-down trên tài liệu bị nghiêng 75 Hình 41: Kết quả phân tích của FS trên tài liệu bị nghiêng 77 Hình 42: Kết quả phân tích của FS trên tài có cấu trúc phức tạp 79 Hình 43: Kết quả phân tích của FS trên một trang quảng cáo 81 Hình 44: Kết quả phân tích của FS trên tài liệu đơn giản 82 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên v GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy MỞ ĐẦU I. Đặt vấn đề Ngày nay việc sử dụng máy tính để lƣu trữ tài liệu không còn là vấn đề mới mẻ và cần phải chứng minh tính an toàn, thuận tiện của nó. Tuy nhiên việc sử dụng giấy để lƣu trữ tài liệu trong một số mục đích vẫn không thể thay thế đƣợc (nhƣ báo, sá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. Chúng ta mong muốn có thể điện tử hóa hàng tỉ trang tài liệu đó và cất chúng chỉ trong một ổ cứng kích thƣớc bằng một cuốn sách nhỏ, tìm kiếm thông tin mà chỉ cần tốn vài giây với một cái gõ phím Enter. Giải pháp là gì? Thông thƣờng ngƣời ta sẽ phải thuê ngƣời cùng với việc tốn hàng tháng, hàng năm mới có thể nhập vào máy tính đƣợc hết lƣợng tài liệu đó. Hiện nay chúng ta đã có các máy Scan với tốc độ cao, công nghệ xử lý của máy tính ngày càng siêu việt với tốc độ tính toán vƣợt cả tốc độ ánh sáng, vậy tại sao chúng ta không quét toàn bộ các trang tài liệu vào và chuyển chúng thành văn bản một cách tự động? Bằng cách đó tốc độ và tính chính xác sẽ tăng hàng trăm lần trong khi chi phí lại là cực tiểu. Vấn đề là khi quét vào máy tính chúng ta không thu đƣợc ngay các dòng văn bản từ các trang tài liệu kia, để có thể soạn thảo, sửa chữa và tìm kiếm nhƣ làm trên Office. Tất cả những gì thu đƣợc chỉ là các tấm ảnh của các trang văn bản, máy tính lại đối xử công bằng nhƣ nhau với mọi điểm ảnh, máy tính không có “mắt” nhƣ chúng ta để biết đâu là điểm ảnh của chữ, đâu là điểm ảnh của đối tƣợng đồ họa. Một giải pháp đƣợc nghĩ đến ngay đó là đó là xây dựng các hệ thống nhận dạng chữ, trong tấm ảnh chứa cả chữ và đối tƣợng đồ họa cần tách và chuyển thành dạng trang văn bản, từ đó có thể mở và 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 làm việc của một hệ thống nhận dạng chữ nhƣ sau[5]: 1. Chụp ảnh các trang tài liệu trên giấy và lƣu lại trong 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 1 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 2. Sử dụng một chƣơng trình xử lý ảnh để 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 đó. a. Bƣớc 1 là 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 chữ, đâ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. 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 (phi chữ). II. Nội dung nghiên cứu 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, ) Cài đặt thử nghiệm một giải pháp phân tích có hiệu quả cao so với các phƣơng pháp truyền thống nhƣ top-down hay bottom-up trên ảnh vào là ảnh đa cấp xám có cấu trúc phức tạp. 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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ƣ: Lƣu trữ thƣ viện, điện tử hóa văn phòng, nhận dạng và xử lý ảnh, 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. 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. 5. Phạm vi nghiên cứu Bài toán nhận dạng và xử lý ảnh 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 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à 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: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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. III. 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 các khái niệm và mô hình tổng quát của hệ thống nhận dạng chữ viết, cùng với một số phần mềm nhận dạng tiêu biểu hiện nay. 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 phƣơng pháp Fractal Signature cho chƣơng trình thử nghiệm. Trình bày về thiết kế cho chƣơng trình demo. Chƣơng 3: Trình bày chi tiết về việc cài đặt chƣơng trình cũng nhƣ các thủ tục sử dụng trong chƣơng trình với phƣơng pháp phân tích Fractal Signature và ảnh đầu vào là ảnh đa cấp xám 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 4 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Chƣơng I. TỔNG QUAN VỀ NHẬN DẠNG CHỮ VIẾT VÀ PHÂN TÍCH TRANG TÀI LIỆU 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. I.1. Ảnh tài liệu và nhận dạng ảnh tài liệu I.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, 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 màu, ả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. Ảnh số Tài liệu Thiết bị thu nhận ảnh Anh 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 5 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 2: Ví dụ ảnh tài liệu I.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ơ đồ một hệ thống OCR cơ bản ở Hình 3. Trong đó: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy - 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õ dà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 củ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 I.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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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ý (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. I.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. - Các thuật toán không theo thứ bậc: nhƣ Fractal Signature, Adaptive split- and-merge Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy I.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. I.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 10 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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] I.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), 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 màu 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 pixell 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, ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy - 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. I.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 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) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 độ I.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) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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] I.4. Một số hệ thống phân tích tài liệu hiện nay I.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 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: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy - 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ạng1 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ả phân tích với hiệu quả chƣa cao (Hinh 11, 12) Thí nghiệm 1: - Với ảnh đầu vào nhƣ sau: 1 Nguồn từ www.vndocr.com Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 16 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 Kết quả phân tích bởi VnDOCR bỏ sót một vùng văn bản và gồm nhầm 2 vùng ảnh vào vùng văn bản số 1 (Hình 14). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 14: Kết quả phân tích với ảnh 13 I.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ính2: - 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 - 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) 2 Nguồn từ nhà sảnh xuất Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 Vùng lỗi Hình 16: Đầu ra có vùng chứa cả ảnh và text Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy I.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 sau3: - 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. Hình 17: Với ảnh 13 đạt hiệu quả 90% 3 Nguồn từ nhà sản xuất Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 18 Với ảnh I-15 hiệu quả đạt 100% Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 so với VNDocr đối tƣợng của đề tài sẽ là ảnh đa cấp xám 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 22 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Chƣơng II: CÁC PHƢƠNG PHÁP TIẾP CẬN ĐỂ PHÂN TÍCH TRANG TÀI LIỆU 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. II.1. Các phƣơng pháp phân tích định dạng trang tài liệu II.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 màu đen (hoặc trắng) theo phƣơng vuông góc với x dọc theo trục x. 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 nguyên tắc này nếu áp dụng phe 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). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 4 (Anoop M. Namboodiri and Anil K. Jain) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 21: Phân tách cột dựa vào phép chiếu nghiêng theo phƣơng ngang5 5 Serban Iliescu. PATTERN RECOGNITION lecture. Concordia University, Montreal, Canada (p. 8) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 22: Phép chiếu nghiêng theo phƣơng ngang để phân đoạn ký tự hoặc từ 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 27 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 24: Lƣợc đồ chiếu đứng của trang tài liệu bị nghiêng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 25: 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 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy II.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. Esposito6 đã 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ƣ 6 Floriana Esposito, Dipartimento di Informatica, Università degli Studi di Bari, Italy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy nhóm các ký tự và các từ dọc theo hƣớng của trang. Các dòng văn 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 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 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. 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy - 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. II.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 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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 chia Tách vùng không thành 4 cùng nhỏ hơn) đồng nhất ở lớp 1 thành 4 vùng nhỏ hơn Lớp 2 Hình 27: 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: Trong đó: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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ó. II.1.4. Fractal Signature (FS) a) Tổng quan Ý tƣởng chính của thuật toán chia trang tài liệu A thành các vùng có kích thƣớc bằng nhau Bk (k=1, ,n) sao cho Bk Є A. Sau đó tính FS cho mỗi vùng này, theo lý thuyết FS thì nếu có 3 vùng B1(giả thiết là vùng nền), B2(giả thiết là vùng chữ), B3(giả thiết là vùng đồ họa) thì luôn có FS(B1)<FS(B2)<FS(B3). Quá trình thực hiện thuật toán có thể đƣợc mô tả nhƣ sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy B1 B2 B3 FS1 FS2 FS3 B4 B5 B6 FS4 FS5 FS6 B7 B8 B9 FS7 FS8 FS9 Bn FSn B1: Trang tài liệu đƣợc B2: Tính FS cho từng Block chia thành n block FS1 FS5 FS7 FS9 FSn FS8 FS3 Thuộc vùng Nền Thuộc vùng Text Thuộc vùng Graphic FSthấp FStrung bình FSCao B3: Phân đoạn dựa vào FS Hình 28: Mô tả thuật toán FS  Cơ sở toán học tính Fractal Signature[1] Cho F{Xi,j}, với i=0,1, ,K và j=0,1, ,L là một ảnh tài liệu đa cấp xám, trong đó Xi,j là giá trị cấp xám của điểm ảnh thứ (i,j). Trong một dải đo nào đấy thì bề mặt tạo bởi các độ xám của các điểm ảnh có thể xem nhƣ một phần tử hình học (Fractal). Vùng bề mặt này có thể đƣợc dùng để xác định gần đúng hƣớng hình học của nó (Fractal dimension). Cho một đơn vị đo , khi đó thể tích của một vùng A( ) có thể đƣợc tính xấp xỉ nhƣ sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy (1) trong đó là một hằng số, D là fractal dimension có thể tính đƣợc từ A( ). Để chính xác hơn ta logarithm hai vế của phƣơng trình (1) ta đƣợc: Để tính fractal dimension, chúng ta cần đo đƣợc vùng bề mặt mức xám, trong giải thuật này sử dụng đối tƣợng là một “lớp” (blanket) để tính. Ý tƣớng tƣởng của kỹ thuật sử dụng “blanket” dựa theo định nghĩa về -parallel body Fδ” nhƣ sau: Trong kỹ thuật “blanket” tất cả các điểm trong không gian 3 chiều trong phạm vi tính từ bề mặt mức xám đƣợc xét đến. Các điểm này tạo thành một “blanket” (lớp) bao bọc với độ dầy là của bề mặt đang xét. Một ảnh tài liệu đƣợc biểu thị qua một hàm mức xám g(i,j). Khối “Blanket” bao bọc đƣợc định nghĩa chính là lớp phía trên uδ(i,j) và lớp phía dƣới bδ(i,j) của g(i,j). Và thể tích Volδ của khối blanket đƣợc tính nhƣ sau: Định nghĩa: Thể tích Volδ của một Blanket tính đƣợc quá bán kính δ, tứ đó ta có thể tính đƣợc cho một vùng bề mặt hình học (area of a fractal surface) và chúng ta gọi nó là đặc trƣng hình học (FS – Fractal Signature): Theo công thức (1) ta có một vùng bề mặt hình học nhƣ sau: Theo đó hƣớng hình học D có thể đƣợc tính, để xác định hƣớng ta chỉ cần đến 2 điểm vì vậy ta sẽ phải dùng 2 giá trị δ để tính hƣớng hình học, khi đó ta cho δ = δ1 và δ2, sau đó tính: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Ta lấy biểu thức (5) chia cho biểu thức (6) đƣợc: Tiến hành logarithm hai vế ta đƣợc: Vậy D đã đƣợc tính:  Ứng dụng phân tích tài liệu dựa vào FS[1] FS đƣợc sử dụng để xác định cấu trúc hình học của một tài liệu. Một bề mặt thu đƣợc từ việc ánh xạ hàm mức xám của một ảnh tài liệu, do đó FS phản ánh các đặc tính chính cần một ảnh tài liệu. Xét một trang tài liệu F, giải thiết nó có một số vùng với các nội dung nhƣ văn bản (Texts), đò họa (Graphics) hay nền (Background). Trong đó: là tập các vùng văn bản là tập các vùng đồ họa tập các vùng nền Các vùng khác nhau sẽ có hàm giá trị mức xám khác nhau . Các hàm mức xám khác nhau sẽ dẫn đến các bề mặt khác nhau và tất nhiên các bề mặt khác nhau thì sẽ có các FS khác nhau (A A ). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Định lý: Cho là một khối văn bản của một tài liệu, và , nếu cả hai khối này có cùng một kích thƣớc hình học thì FS của vùng văn bản luôn lớn FS của vùng nền. Đây là đặc tính rất quan trọng của FS va nó có thể đƣợc dùng để định dạng các loại vùng khác nhau trong tài liệu. b) Ƣu điểm - Tốc độ thực hiện chỉ phụ thuộc vào kích thƣớc của ảnh mà không phụ thuộc vào cấu trúc của tài liệu - Hiệu quả cao với các loại tài liệu có cấu trúc phức tạp. - Hiệu quả cao với các loại tài liệu có nhiều kiểu font, hay font chữ nghiêng, chữ viết tay. - Làm việc tốt với cả ảnh đa cấp xám và ảnh nhị phân c) Nhƣợc điểm - Không có một quy chuẩn để chọn đƣợc kích thƣớc Block là tốt nhất (thƣờng dựa vào kinh nghiệm). - Với mỗi loại trang tài liệu thì ngƣỡng để phân tách miền giá trị FS cho mỗi vùng nền, văn bản và đồ họa là khác nhau. - Với các loại tài liệu có cấu trúc đơn giản hoặc biết trƣớc thì tốc độ thực hiện chậm hơn so với thuật toán Top-down và Bottom-up. II.2. Lựa chọn giải pháp Các phƣơng pháp phân tích Top-down và Bottom-up đã đƣợ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 Fractal signature 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 Fractal Signature (FS) với các mục tiêu sau: - Phân tích với ảnh đầu vào là đa cấp xám. - Phát triển FS 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à TD và BU 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. - Phát triển thuật toán Top-down để so sánh với FS. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy II.3. Thiết kế hệ thống II.3.1. Sơ đồ khối Ảnh tài liệu đa cấp xám Tiền xử lý Lọc và làm trơn nhiễu Phân tích Sử dụng Fractal signature Ảnh đã đƣợc khoanh vùng Văn bản và Đồ họa Hình 29: Sơ đồ khối hệ thống phân tích tài liệu trong phạm vi đề tài II.3.2. Ảnh đầu vào - Ảnh đầu vào đƣợc chọn là ảnh đa cấp xám với định dạng “*.JPG”. Do thời gian có hạn nên đề tài chỉ tập trung vào loại ảnh này, với anh màu cần phải chuyển sang đa cấp xám trƣớc khi qua phân tích. - Về kích thƣớc ảnh đầu vào về mặt thiết kế là không giới hạn. - Với ảnh nhị phân là trƣờng hợp đặc biệt của ảnh đa cấp xám thì đã đƣợc các đề tài trƣớc phân tích và trong thực tế thì thao tác với ảnh nhị phân đơn giản hơn so với ảnh đa cấp xam (vì không cần phân ngƣỡng) nên đề tài không cài đặt cho loại ảnh này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy - Về độ phức tạp của ảnh về mặt thiết kế là không giới hạn. II.3.3. Module Tiền xử lý Nhằm nâng cao hiệu quả cho quá trình phân tích, ảnh sẽ đƣợc qua khâu tiền xử lý trƣớc khi qua khâu phân tích. Trong phạm vi đề tài này khâu tiền xử lý chỉ dừng ở mức lọc và làm trơn nhiễu. Lý do là khâu phân tích sử dụng giải pháp FS không bị ảnh hƣởng bởi góc nghiêng của tài liệu, tham số duy nhất ảnh hƣởng đến giá trị của FS là nhiễu. Vì bản chất của FS là đi tính hiệu thể tích của hai lớp đƣợc tạo ra từ mỗi block ảnh chuyển sang không gian 3D và dịch theo phƣơng z một khoảng ±Δ. Có thể so sánh quá trình FS nhƣ đi tính thiết diện bề mặt của mỗi Block hay còn gọi là độ nhám từ đó đƣa ra các miền giá trị FS đặc trƣng cho mỗi vùng (Text, Graphic, ) (Hình-30). Từ đó dễ nhận ra rằng nếu tồn tại các nhiễu dạng muỗi thì có thể làm một vùng nền (độ nhám =0) trở thành một vùng bề mặt cực nhám dẫn đến FS của nó có thể trùng vào miền Text hoặc Graphic. Để khắc phục một giải pháp là khử và làm trơn nhiều nhằm làm giảm ảnh hƣởng của vùng nhiễu muỗi lên vùng nền và ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 30: Ví dụ một bolck chuyển sang dạng bề mặt trong không gian 3D Hình 31: Ví dụ chuyển ảnh chữ "c" sang dạng bề mặt trong không gian 3D II.3.4. Phân tích sử dụng giả pháp Fractal Signature Chi tiết thuật toán FS[1] Đầu vào: Ảnh đa cấp xám của một trang tài liệu F; Đầu ra: Anh đã khoanh vùng vùng văn bản và đồ họa; Thuật toán: Trƣớc tiên ta chia F thành n vùng không trùng nhau có kích thƣớc NxN gọi là Rk(x,y), trong đó k là vùng NxN thứ k của tài liệu và k=1,2, ,n Bƣớc 1: For x=1 to Xmax do For y=1 to Ymax do Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Tính hàm mức xám gk(x,y) cho F; Bƣớc 2: For x=1 to Xmax do For y=1 to Ymax do Bƣớc 2.1: Khởi tạo cho δ = 0 khi đó lớp trên và lớp dƣới của Blanket đƣợc chọn bằng với hàm mức xám gk(x,y) nhƣ sau: ; Bƣớc 2.2 Cho δ = δ1 a) đƣợc tính theo công thức sau: b) đƣợc tính theo công thức sau: c) Thể tích của Blanket đƣợc tính theo công thức sau: Bƣớc 2.3: Cho δ = δ2 a) đƣợc tính theo công thức sau: b) đƣợc tính theo công thức sau: c) Thể tích của Blanket đƣợc tính theo công thức sau: Bƣớc 3: Tính các FS cho mỗi Rk(x,y) là theo công thức sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Bƣớc 4: Tổ hợp các FS thành FS của tài liệu theo công thức sau:  Nhận xét: Dễ nhận thấy với một ảnh đầu vào có cùng kích thƣớc thì tốc độ thực hiện thuật toán là không đổi và chỉ phải duyệt qua mỗi điểm ảnh một lần duy nhất.  Ví dụ: Giả thiết ta có gk(x,y) là Cho δ = 1, ta có: Thu đƣợc kết quả là: Ta có: Thu đƣợc kết quả là: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Ví dụ về một kết quả áp dụng thuật toán này: Hình 32: (a) Ảnh một tài liệu gốc, (b) kết quả sau khi áp dụng FS Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy II.4. Kết luận Sau chƣơng 2 này, ta đã có đƣợc các module và công việc của mỗi module trong hệ thống demo phân tích trang tài liệu sẽ đƣợc cài đặt, từ những cơ sở phân tích ở trên sẽ làm cơ sở để triển khai cài đặt trên máy tính cho thuật toán Fractal Signature và các chức năng của chƣơng trình demo. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Chƣơng III: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM 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 tich đƣa ra cấu trúc vật lý của ảnh đầu vào là ảnh đa cấp xám có độ phức tạp cao sử dụng thuật toán Fractal Signature. Đồng thời triên khai cả thuật toán Top-down nhằm so sánh vơi thuật toán Fractal Signature III.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 phƣơng pháp phân tích Fractal Signature và để có thể so sánh hiệu quả của FS thì chƣơng trình thử nghiệm sẽ cài đặt thêm phƣơng pháp Top-down. 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 theo thuật toán FS hoặc Top-down - Cho phép tùy chọn ảnh đa cấp xám đầu vào dạng *.jpg - Ảnh kết quả đã khoanh vùng các vùng văn bản 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 - Chƣơng trình đƣợc cài đặt trên MatLab v7.0 Ảnh ra đã *.jpg Lọc và làm Phân tích cấu khoanh Gray Image trơn nhiễu trúc vật lý vùng vă bản và đồ họa Tùy chọn FS hoặc Top-down III.2. Thiết kế chƣơng trình III.2.1. Cấu trúc dữ liệu - Cấu trúc vùng nhớ lƣu ảnh: Ảnh đầu vào là ảnh đa cấp xám dạng *.jpg, sau khi đƣợc tải vào bộ nhớ sẽ đƣợc giải mã và chuyển sang dạng ma trận điểm ảnh (quá trình này đƣợc thực hiện tự động khi sử dụng hàm đọc ảnh trong matlab). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Nhƣ vậy về mặt logic thì cấu trúc vùng nhớ sử dụng để lƣu ảnh là một mảng hai chiều Im x n có kích thƣớc (m x n) phần tử. Image = { I[i,j], i = 1 m, j = 1 n} Trong đó I[i,j] là giá trị độ xám của điểm ảnh tƣơng ứng với tọa độ (i,j) trong ảnh 36 26 80 60 90 15 14 53 81 65 16 49 85 65 73 18 8 68 71 27 28 35 93 39 7 12 96 1 29 10 35 64 85 22 68 91 69 33 44 52 63 80 30 89 18 93 60 58 97 98 89 11 40 17 15 8 15 22 42 98 34 92 87 79 72 44 35 39 39 24 86 50 56 45 87 92 19 27 46 53 11 94 52 54 83 71 98 7 72 64 27 41 58 31 26 60 Ảnh 37 18 4 56 4 91 86 79 11 73 14 96 19 7 13 75 2 21 50 38 57 91 19 3 22 50 65 97 81 50 30 7 76 86 87 74 82 18 81 81 Ma60 trậ21n đi88ểm ả59nh 92 8 66 49 71 95 72 76 61 26 33 55 25 80 91 72 Thông thƣờng với ảnh đa cấp xám thì giá trị độ xám của mỗi điểm ảnh nằm trong khoảng [0 255], nhƣ vậy kích thƣớc tối thiểu cho mỗi I[i,j] là 1Byte. Chƣơng trình sẽ sử dụng mảng có thuộc tính nhƣ sau để lƣu trữ ảnh: - Mảng I hai chiều với I[i,j] kiểu Byte (Max(I[i,j])=255) - Kích thƣớc của mảng là m x n với m là chiều cao của ảnh, n chiều rộng của ảnh và m, n kiểu Double (max(m/n)=232) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy n (Double) m (Double) 1 Byte Ảnh I - Cấu trúc lƣu trữ lƣợc đồ xám (kết quả của các phép chiếu nghiêng). Phép chiếu nghiêng là đi tính tổng các điểm đen theo phƣơng vuông góc với hƣớng chiếu. Kết quả của phép chiếu sẽ đƣợc lƣu trữ vào một mảng một chiều H có kích thƣớc d phần tử. Trong dó H[i] (với i = [1 d]) là tổng số điểm đen của cột thứ i theo phƣơng chiếu. III.2.2. Module chuẩn hóa ảnh Thuật toán FS tính giá trị FS cho từng khối Block trong ảnh, vì thế cần phải chia ảnh thành các block có kích thƣớc bằng nhau trƣớc khi thực hiện thuật toán. Giả thiết kích thƣớc của mỗi Block là (k x q), để việc tính FS cho các block không gặp trƣờng hợp đặc biệt (Kích thƣớc ảnh không bằng nguyên lần của Block) ta sẽ nối thêm vào chiều ngang và dọc của ảnh vùng nền đủ để sao cho kích thƣớc ảnh mới bằng một số nguyên lần của Block. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Phần dƣ không đủ 1 block Block Ảnh gốc Phần nền bổ xung cho đủ 1 block  Giải thuật: Input: - Ảnh I có kích thƣớc m x n - Block có kích thƣớc k x q (k,q<m,n) Output: Ảnh I có kích thƣớc m’ x n’ sao cho m’ = i*k và n’ = j*q (với i,j € N) Thuật toán: B1: Tính m’ Nếu (m/k = nguyên (m/k)) thì m’=m; Trái lại m’ = nguyên (m/k))*k + k; B2: Tính n’ Nếu (n/q = nguyên (n/q)) thì n’=n; Trái lại n’ = nguyên (n/q))*q + q;  Mã nguồn (Mã nguồn cho module chuẩn hóa cài đặt trong Matlab) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy % chuan hoa kich thuoc anh the nguyen lan cua NxN %chuan chieu cao anh if (chieucao/N)>round(chieucao/N) chieucao=round(chieucao/N)*N+N; else chieucao=round(chieucao/N)*N; end %chuan chieu rong anh if (chieurong/N)>round(chieurong/N) chieurong=round(chieurong/N)*N+N; else chieurong=round(chieurong/N)*N; end %%%%%%%%%%%%%%%%%%%% Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy III.2.3. Module giao diện chính Giao diện chính đƣợc thiết kế đơn giản với một số chức năng chính nhƣ sau: Vùng hiển thị ảnh gốc Vùng hiển thị ảnh kết quả Chọn phân tích kiểu FS Chọn phân tích Mô phỏng FS Chọn ảnh mới kiểu Top-down Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 GVHD: PGS. TS. Ngô Quốc Tạo Hình 33: Giao diện chính
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy  Mã nguồn: Một số mã nguồn sự kiện cho các Button chính trên giao diện chính (cài dặt trong Matlab) - Button chọn ảnh: function pushbutton1_Callback(hObject, eventdata, handles) % Hop thoai chon uong dan? [fname,pname] = uigetfile('*.jpg','Hay chon mot anh da cap xam'); if fname~=0 % da chon 1 file set(handles.path,'String',[pname,fname]); % hien thi duong dan cua file anh axes(handles.anhgoc); imshow([pname,fname]); axes(handles.anhdich); end - Button Top-Down function pushbutton2_Callback(hObject, eventdata, handles) imshow('anhmau\running.jpg') pause(0.5) filename=get(handles.path,'string'); topdown % Gọi chương trình con TOPDOWN clear all - Button Fractal Signature function pushbutton3_Callback(hObject, eventdata, handles) imshow('anhmau\running.jpg') pause(0.5) filename=get(handles.path,'string'); Fsign % Gọi chương trình con Fractal signature clear all III.2.4. Module phân tích Top-down (TD) Thuật toán phân tích TD đƣợc thiết kế theo kiểu đệ quy, và cần tham số chiều cao của font chữ. Để tính chiều cao của font chữ có 2 giải pháp - Một là cho phép ngƣời sử dụng nhập vào. - Hai là tự động dò theo thuật toán sau: B1: Tính lƣợc đồ chiếu nghiên theo phƣớc thẳng đứng B2: Tìm độ rộng xuất hiện nhiều nhất của các “cột” trong lƣợc đồ chiếu nghiêng, đây xấp xỉ bằng chiều cao của font chữ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Ảnh vào Lƣợc đồ chiếu đứng Thuật toán phân tích TD ~k đƣợc thiết kế theo kiểu đệ quy, và cần tham số chièu ~k cao của font chữ. ~k ~y Thuật toán phân tích TD đƣợc thiết kế theo kiểu đệ Cột quy, và cần tham số chièu cao của font chữ. Thành phần độ rộng ≈k xuất hiện nhiều nhất => k là chiều cao của font chữ Trong đề tài này việc xác định chiều cao đƣợc dò tự động theo phƣơng pháp trên.  Giải thuật Top-Down Input: Ảnh đa cấp xám I kích thƣớc m x n, chiều cao font chữ k Output: Ảnh đã đƣợc phân đoạn văn bản và đồ họa. Thuật toán: Proceduce Topdown (I,x,y,m,n,k) // I là ảnh đầu vào, m và n là kích thƣớc vùng ảnh // k chiều cao font chữ // x,y là tọa độ hàng và cột // của điểm ảnh góc trái trên cùng Begin B1: Tính lƣợc đồ chiếu đứng cho ảnh I đƣợc kết quả là mảng A gồm m phần tử B2: Xác định các “cột” trên lƣợc đồ A For (mỗi cột(i) trong lƣợc đồ A) do IF độ rộng cột(i) ≈ k then Khoanh vùng trên ảnh tại vị trí của cột(i) chiều dài n là vùng văn bản; Else IF độ rộng côt(i) > k then Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy B2.1: Tính lƣợc đồ chiếu ngang cho vùng ảnh chứa cột(i) đƣợc kết quả là mảng B gồm n phần tử B2.2: Xác định các cột trên B IF nếu số cột của A = 1 và số cột của B = 1 then khoanh vùng là Ảnh; Else For mỗi Cột(j) trên B do TopDown(I, x(cột(i)), y(cột(j)), độ rộng(cột(i)), độ rộng(cột(j)), k); End for End if End if End if End for End  Mã nguồn: function ketqua=phantichtrong(start,limit,letrai,lephai,anh,nguongtach,chieu_cao_hang) y=anh; chieucao=limit; chieurong=lephai; %Phan nguong va tim hinh chieu doc % z=zeros(1,size(y,1));% z la hinh chieu doc z=zeros(1,limit-start+1);% z la hinh chieu doc for i=start:chieucao for j=letrai:chieurong if (y(i,j)>nguongtach) % vung nen else z(i-start+1)=z(i-start+1)+1; % tinh cho bieu do xam end end end % tach khoi bang cach vao tung khoi van ban ngang tim hinh chieu ngang i=start; start_t=i; limit_t=i; while (i (2*min(z))) %di het vung van ban de tinh chieu cao i=i+1; end limit_t=i-1; %limit-start la chieu cao vung van ban ngang % tinh luoc do xam cho moi vung ngang if (start_t start_t) if limit_t>chieucao limit_t=chieucao; % tranh vuot qua vung bien anh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy end y=phantich(start_t,limit_t,y,nguongtach,chieu_cao_hang,letrai,lephai); end while (i<=chieucao)&(z(i-start+1)<=(2*min(z))) i=i+1; end start_t=i; end %%%%%%%%%%%%%%%%%%% ketqua=y; III.2.5. Module phân tích Fractal Signature  Giải thuật Fractal Signature Input: Ảnh đa cấp xám I, kích thƣớc block m x n Output: Ảnh đã phân đoạn văn bản và đồ họa Thuật toán: B1: Chuẩn hóa kích thƣớc ảnh đƣợc I’ (trình bày ở phần IV.2.2) B2: Lọc và làm trơn nhiễu B3: Tách nền ra khỏi nội dung ảnh B4: Chia ảnh I’ thành q Block có kích thƣớc (m x n) For (mỗi Block(i) của I’) Do B4.1: Chọn ∂ = 1 . Tính giá trị lớp trên của block(i): . Tính giá trị lớp dƣới của block(i) . Tính thể tích của Blanket B4.2: Chọn ∂ = 2 . Tính giá trị lớp trên của block(i): Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy . Tính giá trị lớp dƣới của block(i) . Tính thể tích của Blanket (với x,y thuộc Block(i)) B4.3: Tính FS(Block(i)) = End for B5: Chọn ngƣỡng phân tách vùng nền, văn bản và đồ họa  Mã nguồn: for i=1:round(chieucao/N) for(j=1:round(chieurong/N)) %%%%%%%%%% thao tac voi block thu K u_layer1(:,:)=0; b_layer1(:,:)=0; u_layer2(:,:)=0; b_layer2(:,:)=0; vol1=0; vol2=0; block_k(2:N+1,2:N+1)=anh((i-1)*N+1:i*N,(j-1)*N+1:j*N); % tinh gia tri cho lop tren va duoi voi delta1 cho moi vung thu k for ki=2:N+1 for kj=2:N+1 g1_u=block_k(ki,kj)+1; g1_b=block_k(ki,kj)-1; g2=block_k(ki,kj+1); g3=block_k(ki,kj-1); g4=block_k(ki+1,kj); g5=block_k(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer1(ki,kj)=max(temp(1:5)); b_layer1(ki,kj)=min(temp(2:6)); vol1=vol1 + (u_layer1(ki,kj)-b_layer1(ki,kj)); % tinh xong lop tren va duoi voi delta1 % tinh gia tri cho lop tren va duoi voi delta2 g1_u=u_layer1(ki,kj)+1; g1_b=b_layer1(ki,kj)-1; g2=u_layer1(ki,kj+1); g3=u_layer1(ki,kj-1); g4=u_layer1(ki+1,kj); g5=u_layer1(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer2(ki,kj)=max(temp(1:5)); b_layer2(ki,kj)=min(temp(2:6)); vol2=vol2+(u_layer2(ki,kj)-b_layer2(ki,kj)); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy %%%%%%%%%%%%%%%% tinh xong gia tri cua lop tren duoi voi delta2 end end % tinh FS k=k+1; FS(k)=(vol2-vol1)/2; end end %%%%%%%%%%%%%%%% Tach anh va text k=0;; anh=cat(3,anh,anh,anh); nguong=min(FS)+50; for i=1:round(chieucao/N) for(j=1:round(chieurong/N)) k=k+1; if (FS(k) 4000) % text for ki=1:N for kj=1:N anh((i-1)*N+ki,(j-1)*N+kj,:)=255-anh((i-1)*N+ki,(j-1)*N+kj); end end else % vung anh for ki=1:N for kj=1:N anh((i-1)*N+ki,(j-1)*N+kj,1)=150; anh((i-1)*N+ki,(j-1)*N+kj,3)=150; end end end end end III.2.6. Module lọc và làm trơn nhiễu Có rất nhiều kỹ thuật lọc nhiễu, tuy nhiên nhƣ đã trình bày ở phần II.1.4 bản chất của FS có thể coi nhƣ đi xác định đặc trƣng độ nhám của các bề mặt thuộc vùng nền, văn bản hay đồ họa. Để nhiễu bớt ảnh hƣởng đến đặc trƣng này thì giải pháp làm trơn nhiễu là hiệu quả nhất nhằm làm cho các điểm ảnh gần nhau có đặc tính tƣơng tự nhau. Điều này sẽ làm cho độ nhám mà nhiễu gây ra là không đáng kể. Trong đề tài này sử dụng phƣơng pháp lọc thông thấp[2] với ma trận cuộn sau:  Mã nguồn: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy %%%%%%% mat na loc loc=[0 1 0;1 2 1;0 1 0]; loc=1/8*loc; %%%%%%% dung ham loc anh=conv2(anh,loc); III.2.7. Module mô phỏng thuật toán FS Module mô phỏng thuật toán FS chỉ mang tính nghiên cứu quá trình làm việc của Fractal Signature. Về mặt thuật toán giống nhƣ III.2.5 chỉ khác không cần tính thể tích của các Blanket đƣợc tạo ra mà tiến hành vẽ các blanket đó trong không gian 3D.  Giải thuật: Input: Ảnh đa cấp xám I, kích thƣớc block m x n Output: Demo Thuật toán: B1: Chuẩn hóa kích thƣớc ảnh đƣợc I’ (trình bày ở phần IV.2.2) B2: Lọc và làm trơn nhiễu B3: Tách nền ra khỏi nội dung ảnh B4: Chia ảnh I’ thành q Block có kích thƣớc (m x n) For (mỗi Block(i) của I’) Do B4.1: Chọn ∂ = 1 . Tính giá trị lớp trên của block(i): . Tính giá trị lớp dƣới của block(i) B4.2: Chọn ∂ = 2 . Tính giá trị lớp trên của block(i): . Tính giá trị lớp dƣới của block(i) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy (với x,y thuộc Block(i)) B4.3: Vẽ các Blanket trong không gian 3D End for  Mã nguồn: for i=1:round(chieucao/N) for(j=1:round(chieurong/N)) %%%%%%%%%% thao tac voi block thu K u_layer1(:,:)=0; b_layer1(:,:)=0; u_layer2(:,:)=0; b_layer2(:,:)=0; vol1=0; vol2=0; block_k(2:N+1,2:N+1)=anh((i-1)*N+1:i*N,(j-1)*N+1:j*N); % tinh gia tri cho lop tren va duoi voi delta1 cho moi vung thu k for ki=2:N+1 for kj=2:N+1 g1_u=block_k(ki,kj)+1; g1_b=block_k(ki,kj)-1; g2=block_k(ki,kj+1); g3=block_k(ki,kj-1); g4=block_k(ki+1,kj); g5=block_k(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer1(ki,kj)=max(temp(1:5)); b_layer1(ki,kj)=min(temp(2:6)); vol1=vol1 + (u_layer1(ki,kj)-b_layer1(ki,kj)); % tinh xong lop tren va duoi voi delta1 % tinh gia tri cho lop tren va duoi voi delta2 g1_u=u_layer1(ki,kj)+1; g1_b=b_layer1(ki,kj)-1; g2=u_layer1(ki,kj+1); g3=u_layer1(ki,kj-1); g4=u_layer1(ki+1,kj); g5=u_layer1(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer2(ki,kj)=max(temp(1:5)); b_layer2(ki,kj)=min(temp(2:6)); vol2=vol2+(u_layer2(ki,kj)-b_layer2(ki,kj)); %%%%%%%%%%%%%%%% tinh xong gia tri cua lop tren duoi voi delta2 end end % ve he truc toa do va anh 3D trucx=[1:N+2]; trucy=[1:N+2]; meshgrid(trucx,trucy); % axes(handles.anhgoc); subplot(2,2,1); anhtem=goc; anhtem((i-1)*N+1:(i-1)*N+N,(j-1)*N+1:(j-1)*N+N)=0; imshow(anhtem); subplot(2,2,2); %axes(handles.uper); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy surf(trucx,trucy,u_layer2) subplot(2,2,3); %axes(handles.block); imshow(255-anh((i-1)*N+1:(i-1)*N+N,(j-1)*N+1:(j-1)*N+N)); subplot(2,2,4); %axes(handles.surf); trucx=[1:N]; trucy=[1:N]; meshgrid(trucx,trucy); surf(trucx,trucy,double(anh((i-1)*N+1:(i-1)*N+N,(j-1)*N+1:(j-1)*N+N))); pause(0.3) end end III.2.8. Các hàm chức năng chính của image processing tool trong matlab sử dụng trong chƣơng trình Image Processing Toolbox là một thƣ viện các hàm chức năng về xử lý ảnh tƣơng thích trong môi trƣờng MatLab. Các hàm trong thƣ viên có thể phân loại theo chức năng nhƣ sau: - Các phép toán hình thái - Các phép toán trên các khối hay các vùng liên thông - Thiết kế và lọc tuyến tính - Chuyển đổi kiểu và không gian ảnh - Nâng cao chất lƣợng ảnh - Các phép toán trên ảnh nhị phân - Một số hàm chức năng sử dụng trong chƣơng trình[3] a) Hàm đọc và ghi ảnh  Hàm đọc: Đọc một ảnh với đƣờng dẫn chỉ ra, kết quả trả về là một ma trận điểm ảnh. Cú pháp: imread(filename,fmt); Trong dó: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Filename: là xâu chỉ ra đƣờng dẫn và tên file ảnh cần đọc Fmt: Định dạng của ảnh đƣợc đọc Các giá trị của “fmt” theo bảng sau:  Hàm ghi ảnh: Ghi ảnh ra một file Cú pháp: imwrite(A,filename,fmt) Ghi một ảnh trong biến mảng A với tên file là “filename” theo định dạng “fmt” Trong đó: - A: Vùng nhớ lƣu trữ ảnh - Filename: Tên file cần ghi - Fmt: Định dạng file ảnh đầu ra  Hàm hiển thị ảnh Cú pháp: imshow(I); %hiển thị ảnh I Trong đó: I: Vùng nhớ chứa ảnh cần hiển thị  Hàm nhân chập: (để thực hiện lọc thông thấp làm trơn nhiễu) Cú pháp: C = conv2(A,B) Nhân chập mặt nạ B với ma trận A kết quả là ma trận C Trong đó: A: Ma trận nguồn B: Mặt nạ chập C: Ma trận kết quả  Hàm chuyển ảnh từ RGB sang ảnh đa cấp xám Cú pháp: I = rgb2gray(RGB) Chuyển đổi ảnh “RGB” từ hệ mầu Red-Green-Blue sang ảnh đa cấp xám Trong đó: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy - RGB: là ảnh nguồn - I: ảnh kết quả  Hàm vẽ mặt trong không gian 3D Cú pháp: surf(X,Y,Z); %vẽ mặt một bề mặt trong không gian X,Y,Z Trong đó: - X: mảng một chiều chƣa các điểm của trục x - Y: mảng một chiều chứa các điểm của trục y - Z: mảng 2 chiều chƣa các giá trị của trục Z trong mặt phẳng XY. III.3. Kết luận và đánh giá kết quả - Chƣơng trình demo đã đƣợc xây dựng để làm việc với ảnh đa cấp xám - Thuật toán Top-Down đƣợc cài trong chƣơng trình làm việc rất hiệu quả với các loại tài liệu có cấu trúc đơn giản, tốc độ thực hiện ổn định (Hình 34, 35, 36). - Đúng nhƣ nhƣợc điểm của Top-down đã nói ở chƣơng 2, top-down kém hiệu quả với các loại tài liệu có cấu trúc phức tạp hay bị nghiêng (Hình 37, 38, 39, 40). - Thuật toán Fractal Signature đặc biệt hiệu quả với những tài liệu có cấu trúc phức tạp, không phân biệt hƣớng tài liệu, với các tài liệu bị nghiêng FS vẫn có thể khoanh vùng chính xác vùng Text và đồ họa (Hình 41, 42, 43, 44) - Nhƣợc điểm của FS trong chƣơng trình này chƣa giải quyết đƣợc là tốc độ làm việc chậm và thuật toán khoanh vùng làm việc hiệu quả chƣa cao. - Một số yếu tố ảnh hƣởng đến hiệu quả của FS đó là việc chọn kích thƣớc của Block, chọn Block phải hợp lý tốt nhất nhất là ba đủ 1 ký tự thì kết quả phân tích sẽ cao. Tuy nhiên với các loại trang có nhiều loại size chữ thì điều này là khó khả thi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 34: Kết quả phân tích của top-down trên tài liệu có cấu trúc đơn giản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 35: Kết quả phân tích của top-down trên tài liệu có cấu trúc bảng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 36: : Kết quả phân tích của top-down trên tài liệu thuần văn bản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 68 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 37: : Kết quả phân tích của top-down trên tài liệu có cấu trúc phức tạp (trang tạp trí) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 69 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 70 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 38 : Kết quả phân tích của top-down trên một tờ quảng cáo Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 71 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 72 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 39: Kết quả phân tích của top-down trên tài liệu có cấu trúc phức tạp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 73 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 74 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 40: Kết quả phân tích của top-down trên tài liệu bị nghiêng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 75 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 76 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 41: Kết quả phân tích của FS trên tài liệu bị nghiêng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 77 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 78 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 42: Kết quả phân tích của FS trên tài có cấu trúc phức tạp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 79 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 80 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 43: Kết quả phân tích của FS trên một trang quảng cáo Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 81 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Hình 44: Kết quả phân tích của FS trên tài liệu đơn giản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 82 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Kết luận Qua nhiều mẫu ảnh phân tích cho thấy thuật toán FS lầm việc rất hiệu quả về nhiệm vụ phát hiện vùng văn bản hay vùng đồ họa, tỉ lệ gần nhƣ tƣơng ứng với phần mềm ABBYY FineReader 9.0, và hơn hẳn OminiPage, VNDocr. Đặc biệt là chƣơng trình đã đƣợc cài đặt để làm việc thành công với ảnh đầu vào là ảnh đa cấp xám và có độ phức tạp cao. Thuật toán FS là một thuật toán hay vì không phụ thuộc vào font chữ, tuy nhiên trong giới hạn đề này chƣa trình bày và cài đặt hoàn thiện đƣợc. Chƣơng trình thử nghiệm phân tích định dạng của trang ảnh tài liệu 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 tài liệu. Chƣơng trình chỉ phân tích từng trang ảnh tài liệu và phải điều chỉnh bằng tay nhƣng kết quả thật khả quan. Để đƣa chƣơng trình áp dụng thực tế trên còn phải qua một đoạn đƣờng dài nữa, tuy nhiên với kết quả này của công đoạn đầu tiên trong quá trình “lưu trữ thông tin trên tài liệu giấy theo cách máy tính có thể hiểu và xử lý được” thì các công đoạn nhận dạng chữ sau này sẽ dễ dàng hơn rất nhiều. Hƣớng phát triển đề tài: - Cải tiến thuật toán FS chạy nhanh hơn. - Cài đặt FS trên ảnh mầu. - Phát triển tiếp module nhận dạng ký tự. - Tích hợp thành phần mềm hoàn chỉnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 83 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy 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]. PGS. TS. 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 84 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy Phục Lục A. Mã nguồn đầy đủ của chƣơng trình A.1. Danh mục các chƣơng trình con trong chƣơng trình TT Tên chƣơng trình Nhiệm vụ Tên file lƣu trữ Chƣơng trình chính chứa giao diện 1 main Main.m của chƣơng trình. Module chính của thuật toán top- 2 Topdown Topdown.m down. Module con đƣợc gọi từ module topdown, thực hiện phân chia trang 3 Phantich tài liệu thành các block theo lƣợc Phantich.m đồ xám chiếu nghiêng, và khoanh vùng tài liệu. Module con đƣợc gọi từ module phantich, nếu block chứa cảc đồ 4 Phantichtrong Phantichtrong.m họa và text thì sẽ đƣợc module này phần tích tiếp. Module chƣơng trình cho thuật toán 5 FSign Fractal thực hiện phát hiện text và FSign.m đồ họa (chƣa khoanh vùng). Module chƣơng trình cho thuật toán 6 FSignKV Fractal thực hiện phát hiện và FSignKV.m khoanh vùng text và đồ họa. Module tìm vùng liên thông để 7 Lienthong Lienthong.m khoanh vùng. Module khoanh vùng một vùng liên 8 Vebien Vebien.m thông. Module chay theo thuật toán 9 Demo Fractal có vẽ demo các block đƣợc demoFS.m tính FS. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 85 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy A.2. Sơ khối liên kết giữa các thủ tục trong chƣơng trình Main Phantich (chương trình chính) Topdown Phantichtrong FSign FSignKV DemoFS A.3. Mã nguồn các module 1) Main: y=imread(filename); anhgoc=y; %%%%%%%%%%%%% Cac bien phu trong chuong trinh % bien de tranh pha tich trung lap global letraicu; global lephaicu; global startcu; global limitcu; %%%%%%%%%%%%%%%%%%% % loc nhieu anh goc y=double(y)/255; % chuyen sang kieu double %%%%%%% mat na loc k=[0 1 0;1 2 1;0 1 0]; k=1/8*k; %%%%%%% dung ham loc y=conv2(y,k); y=uint8(round(y*255)); %%%%%%%%%%%%%%%% kich_thuoc_anh=size(y); chieucao=kich_thuoc_anh(1); chieurong=kich_thuoc_anh(2); %%%%%%%%%Phan nguong va tim hinh chieu doc gray_min=min(min(y)); gray_max=max(max(y)); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 86 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy nguongtach=round(((gray_min+gray_max)/2)); z=zeros(1,chieucao);% z la hinh chieu doc for i=1:chieucao for j=1:chieurong if (y(i,j)>nguongtach) % vung nen y(i,j)=255; % xoa trang vung nen else z(i)=z(i)+1; % tinh cho bieu do xam end end end %%%%%%%%%%%%%%% chieu_cao_hang=timhang(z); %%%%%%%%%%%%%%%%% tach khoi bang cach vao tung khoi van ban ngang tim hinh %%%%%%%%%%%%%%%%% chieu ngang i=1; start=i; limit=i; luocdo=zeros(1,chieurong); while (i (2*min(z))) %di het vung van ban de tinh chieu cao i=i+1; end limit=i-1; %limit-start la chieu cao vung van ban ngang luocdo=zeros(1,chieurong); % tinh luoc do xam cho moi vung ngang if (start start) if limit>chieucao limit=chieucao; % tranh vuot qua vung bien anh end if (limit-start)>=(0.5*chieu_cao_hang) y=phantich(start,limit,y,nguongtach,chieu_cao_hang,1,size(y,2)); end end while (i<=chieucao)&(z(i)<=(2*min(z))) i=i+1; end start=i; end imshow(y); 2) Topdown: y=imread(filename); anhgoc=y; %%%%%%%%%%%%% Cac bien phu trong chuong trinh % bien de tranh pha tich trung lap global letraicu; global lephaicu; global startcu; global limitcu; %%%%%%%%%%%%%%%%%%% % loc nhieu anh goc y=double(y)/255; % chuyen sang kieu double %%%%%%% mat na loc k=[0 1 0;1 2 1;0 1 0]; k=1/8*k; %%%%%%% dung ham loc y=conv2(y,k); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 87 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy y=uint8(round(y*255)); %%%%%%%%%%%%%%%% kich_thuoc_anh=size(y); chieucao=kich_thuoc_anh(1); chieurong=kich_thuoc_anh(2); %%%%%%%%%Phan nguong va tim hinh chieu doc gray_min=min(min(y)); gray_max=max(max(y)); nguongtach=round(((gray_min+gray_max)/2)); z=zeros(1,chieucao);% z la hinh chieu doc for i=1:chieucao for j=1:chieurong if (y(i,j)>nguongtach) % vung nen y(i,j)=255; % xoa trang vung nen else z(i)=z(i)+1; % tinh cho bieu do xam end end end %%%%%%%%%%%%%%% chieu_cao_hang=timhang(z); %%%%%%%%%%%%%%%%% tach khoi bang cach vao tung khoi van ban ngang tim hinh %%%%%%%%%%%%%%%%% chieu ngang i=1; start=i; limit=i; luocdo=zeros(1,chieurong); while (i (2*min(z))) %di het vung van ban de tinh chieu cao i=i+1; end limit=i-1; %limit-start la chieu cao vung van ban ngang luocdo=zeros(1,chieurong); % tinh luoc do xam cho moi vung ngang if (start start) if limit>chieucao limit=chieucao; % tranh vuot qua vung bien anh end if (limit-start)>=(0.5*chieu_cao_hang) y=phantich(start,limit,y,nguongtach,chieu_cao_hang,1,size(y,2)); end end while (i<=chieucao)&(z(i)<=(2*min(z))) i=i+1; end start=i; end % Lam noi vung van ban %%%%%%%%%%%%%%%%%%% %subplot(1,2,1); %title('ANH GOC'); %imshow(anhgoc,'InitialMagnification',100); %subplot(1,2,2); %title('KET QUA'); imshow(y); 3) Phantich: function ketqua=phantich(start,limit,anh,nguongtach,chieu_cao_hang,bientrai,bienphai) %%%%%%%%%%%%%%% Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 88 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy global letraicu; global lephaicu; global startcu; global limitcu; %%%%%%%%%%%%%%%% CDmang=bienphai-bientrai+1; luocdo=zeros(1,CDmang); for k=start:limit % tim hinh chieu ngang for q=bientrai:bienphai if (anh(k,q) =luocdo(dau))&(dau =luocdo(cuoi))&(cuoi>2) cuoi=cuoi-1; end %%%%%%%%%%%% if cuoi>dau cuctieu=round(min(luocdo(dau:cuoi))*1.2); else cuctieu=bienphai-bientrai; end %%%%%%%%%%%% if (cuctieu>0)&((limit-start)>= 2*chieu_cao_hang)% vung anh for hang_anh=start:limit for cot_anh=bientrai:bienphai anh(hang_anh,cot_anh)=255-anh(hang_anh,cot_anh); end end else dorong=0; truoc=luocdo(1); letrai=bientrai; lephai=bientrai; i=bientrai; dautien=0; while(i =(1.2*chieu_cao_hang))|((lephai>letrai)&(i>=bienphai)) % khoang canh cho phep if (lephai>letrai) % tien hanh ve vung van ban % dautien=0; if ((limit-start)< 2*chieu_cao_hang) % khung vung van ban Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 89 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy if lephai>bienphai lephai=bienphai; end for ve_bien_ngang=letrai:lephai anh(start,ve_bien_ngang)=0; anh(limit,ve_bien_ngang)=0; end for ve_bien_doc=start:limit anh(ve_bien_doc,letrai)=0; anh(ve_bien_doc,lephai)=0; end else if (letraicu==letrai) & (lephaicu==lephai)&(startcu==start)&(limitcu==limit) % tranh bi treo % trung khoi phan tich letraicu lephaicu startcu limitcu else letraicu=letrai; lephaicu=lephai; startcu=start; limitcu=limit; anh=phantichtrong(start,limit,letrai,lephai,anh,nguongtach,chieu_cao_hang); end end end letrai=i;% bat dau mot vung van ban dorong=0; else dorong=0; end while (i cuctieu) i=i+1; % di qua vung van ban lephai=i; end end end ketqua=anh; 4) Phantichtrong: function ketqua=phantichtrong(start,limit,letrai,lephai,anh,nguongtach,chieu_cao_hang) y=anh; chieucao=limit; chieurong=lephai; %%%%%%%%%Phan nguong va tim hinh chieu doc %z=zeros(1,size(y,1));% z la hinh chieu doc z=zeros(1,limit-start+1);% z la hinh chieu doc for i=start:chieucao for j=letrai:chieurong if (y(i,j)>nguongtach) % vung nen else z(i-start+1)=z(i-start+1)+1; % tinh cho bieu do xam end end end %%%%%%%%%%%%%%%%% tach khoi bang cach vao tung khoi van ban ngang tim hinh %%%%%%%%%%%%%%%%% chieu ngang Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 90 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy i=start; start_t=i; limit_t=i; while (i (2*min(z))) %di het vung van ban de tinh chieu cao i=i+1; end limit_t=i-1; %limit-start la chieu cao vung van ban ngang % tinh luoc do xam cho moi vung ngang if (start_t start_t) if limit_t>chieucao limit_t=chieucao; % tranh vuot qua vung bien anh end y=phantich(start_t,limit_t,y,nguongtach,chieu_cao_hang,letrai,lephai); end while (i round(chieucao/N) chieucao=round(chieucao/N)*N+N; else chieucao=round(chieucao/N)*N; end %chuan chieu rong anh if (chieurong/N)>round(chieurong/N) chieurong=round(chieurong/N)*N+N; else chieurong=round(chieurong/N)*N; end %anh=zeros(1:chieucao,1:chieurong); %%%%%%%%%%%%%%%%%%%% %loc nhieu anh goc %anh = filter2(fspecial('average',3),anh); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 91 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy anh=double(anh)/255; % chuyen sang kieu double %%%%%%% mat na loc loc=[0 1 0;1 2 1;0 1 0]; loc=1/8*loc; %%%%%%% dung ham loc anh=conv2(anh,loc); anh=uint8(round(anh*255)); %%%%%%%%%%%%%% for i=1:chieucao for j=1:chieurong if (i>chieucao_goc)|(j>chieurong_goc) % ngoai vung bien anh goc anh(i,j)=0; % dat la vung nen anh else % trong vung bien anh goc %anh(i,j)=255-anh(i,j); if (anh(i,j)>nguongtach) % vung nen %anh(i,j)=255; % xoa trang vung nen anh(i,j)=0; else %z(i)=z(i)+1; % tinh cho bieu do xam anh(i,j)=255-anh(i,j); end end end end %%%%%%%%%%%%%%% tinh FS cho moi block FS=[]; k=0; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% u_layer1=zeros(N+2);b_layer1=zeros(N+2);u_layer2=zeros(N+2);b_layer2=zeros(N+2);block_k=zeros(N +2); %%%%%%%%%%%%%%%%%%%%%% for i=2:round(chieucao/N) for(j=2:round(chieurong/N)) %%%%%%%%%% thao tac voi block thu K u_layer1(:,:)=0; b_layer1(:,:)=0; u_layer2(:,:)=0; b_layer2(:,:)=0; vol1=0; vol2=0; block_k(2:N+1,2:N+1)=anh((i-1)*N+1:i*N,(j-1)*N+1:j*N); % tinh gia tri cho lop tren va duoi voi delta1 cho moi vung thu k for ki=2:N+1 for kj=2:N+1 g1_u=block_k(ki,kj)+1; g1_b=block_k(ki,kj)-1; g2=block_k(ki,kj+1); g3=block_k(ki,kj-1); g4=block_k(ki+1,kj); g5=block_k(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer1(ki,kj)=max(temp(1:5)); b_layer1(ki,kj)=min(temp(2:6)); vol1=vol1 + (u_layer1(ki,kj)-b_layer1(ki,kj)); % tinh xong lop tren va duoi voi delta1 % tinh gia tri cho lop tren va duoi voi delta2 g1_u=u_layer1(ki,kj)+1; g1_b=b_layer1(ki,kj)-1; g2=u_layer1(ki,kj+1); g3=u_layer1(ki,kj-1); g4=u_layer1(ki+1,kj); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 92 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy g5=u_layer1(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer2(ki,kj)=max(temp(1:5)); b_layer2(ki,kj)=min(temp(2:6)); vol2=vol2+(u_layer2(ki,kj)-b_layer2(ki,kj)); %%%%%%%%%%%%%%%% tinh xong gia tri cua lop tren duoi voi delta2 end end % tinh FS k=k+1; FS(k)=(vol2-vol1)/2; end end %%%%%%%%%%%%%%%% Tach anh va text k=0; %nguong=((min(FS)+max(FS))/2); %nguong=3000; anh=255-anh; anh=cat(3,anh,anh,anh); nguong=min(FS)+50; for i=2:round(chieucao/N) for(j=2:round(chieurong/N)) k=k+1; if (FS(k)>4000) % anh anh((i-1)*N+1:i*N,(j-1)*N+1:j*N,2:3)=20; elseif (FS(k)>nguong) % text anh((i-1)*N+1:i*N,(j-1)*N+1:j*N,1)=150; anh((i-1)*N+1:i*N,(j-1)*N+1:j*N,3)=150; end end end imshow(anh) 6) FSignKV global anh anh=imread(filename); % doc anh tu mot file JPG N=15; % kich thuoc moi block k=1; % so block tren anh co kich thuoc NxN chieucao=size(anh,1); % chieu cao cuar anh vao chieucao_goc=chieucao; chieurong=size(anh,2); % chieu rong cua anh vao chieurong_goc=chieurong; %%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%% %%%%%%%%%Phan nguong va tim hinh chieu doc gray_min=min(min(anh)); gray_max=max(max(anh)); nguongtach=round(((gray_min+gray_max)/2)); % chuan hoa kich thuoc anh the nguyen lan cua NxN %chuan chieu cao anh if (chieucao/N)>round(chieucao/N) chieucao=round(chieucao/N)*N+N; else chieucao=round(chieucao/N)*N; end %chuan chieu rong anh if (chieurong/N)>round(chieurong/N) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 93 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy chieurong=round(chieurong/N)*N+N; else chieurong=round(chieurong/N)*N; end %%%%%%%%%%%%%%%%%%%% %loc nhieu anh goc %anh = filter2(fspecial('average',3),anh); anh=double(anh)/255; % chuyen sang kieu double %%%%%%% mat na loc loc=[0 1 0;1 2 1;0 1 0]; loc=1/8*loc; %%%%%%% dung ham loc anh=conv2(anh,loc); anh=uint8(round(anh*255)); %%%%%%%%%%%%%% for i=1:chieucao for j=1:chieurong if (i>chieucao_goc)|(j>chieurong_goc) % ngoai vung bien anh goc anh(i,j)=0; % dat la vung nen anh else % trong vung bien anh goc %anh(i,j)=255-anh(i,j); if (anh(i,j)>nguongtach) % vung nen %anh(i,j)=255; % xoa trang vung nen anh(i,j)=0; else %z(i)=z(i)+1; % tinh cho bieu do xam anh(i,j)=255-anh(i,j); end end end end %%%%%%%%%%%%%%% tinh FS cho moi block FS=[]; k=0; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% u_layer1=zeros(N+2);b_layer1=zeros(N+2);u_layer2=zeros(N+2);b_layer2=zeros(N+2);block_k=zeros(N +2); %%%%%%%%%%%%%%%%%%%%%% % mang chua FS global AFS AFS=zeros(round(chieucao/N)-1,round(chieurong/N)-1); %%%%%%%%%%%%%%%%%%%%%% for i=2:round(chieucao/N) for(j=2:round(chieurong/N)) %%%%%%%%%% thao tac voi block thu K u_layer1(:,:)=0; b_layer1(:,:)=0; u_layer2(:,:)=0; b_layer2(:,:)=0; vol1=0; vol2=0; block_k(2:N+1,2:N+1)=anh((i-1)*N+1:i*N,(j-1)*N+1:j*N); % tinh gia tri cho lop tren va duoi voi delta1 cho moi vung thu k for ki=2:N+1 for kj=2:N+1 g1_u=block_k(ki,kj)+1; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 94 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy g1_b=block_k(ki,kj)-1; g2=block_k(ki,kj+1); g3=block_k(ki,kj-1); g4=block_k(ki+1,kj); g5=block_k(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer1(ki,kj)=max(temp(1:5)); b_layer1(ki,kj)=min(temp(2:6)); vol1=vol1 + (u_layer1(ki,kj)-b_layer1(ki,kj)); % tinh xong lop tren va duoi voi delta1 % tinh gia tri cho lop tren va duoi voi delta2 g1_u=u_layer1(ki,kj)+1; g1_b=b_layer1(ki,kj)-1; g2=u_layer1(ki,kj+1); g3=u_layer1(ki,kj-1); g4=u_layer1(ki+1,kj); g5=u_layer1(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer2(ki,kj)=max(temp(1:5)); b_layer2(ki,kj)=min(temp(2:6)); vol2=vol2+(u_layer2(ki,kj)-b_layer2(ki,kj)); %%%%%%%%%%%%%%%% tinh xong gia tri cua lop tren duoi voi delta2 end end % tinh FS k=k+1; FS(k)=(vol2-vol1)/2; % AFS %AFS(i,j)=(vol2-vol1)/2; end end %%%%%%%%%%%%%%%% Tach anh va text k=0; anh=cat(3,anh,anh,anh); nguong=min(FS)+50; for i=1:round(chieucao/N-1) for(j=1:round(chieurong/N)-1) k=k+1; if ((FS(k)>nguong)&(FS(k) =4000) % vung anh AFS(i,j)=2; % danh dau vung anh end end end %%%%%%%%% khoanh vung global MLT MLT=AFS; MLT=0; % chua 1 khoi cac phan tu lien thong %%%%%%%%%%% set(0,'RecursionLimit',1000) %%%%%%%%%%%% anh=255-anh; for i=1:round(chieucao/N-1) for(j=1:round(chieurong/N)-1) if ((AFS(i,j)~=3)&(AFS(i,j)==1)); % phan tu la text chua xet trong anh MLT=0; lienthong(i,j,1); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 95 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy if(sum(sum(MLT))>20 ) % bo qua vung lien thong qua nho vebien(MLT,N,1); end elseif ((AFS(i,j)~=3)&(AFS(i,j)==2)); % phan tu la text chua xet trong anh MLT=0; lienthong(i,j,2); if(sum(sum(MLT))>20 ) % bo qua vung lien thong qua nho vebien(MLT,N,2); end end end end imshow(anh) 7) DemFS: anh=imread(filename); % doc anh tu mot file JPG goc=anh; N=15; % kich thuoc moi block k=1; % so block tren anh co kich thuoc NxN chieucao=size(anh,1); % chieu cao cuar anh vao chieucao_goc=chieucao; chieurong=size(anh,2); % chieu rong cua anh vao chieurong_goc=chieurong; %%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%% %%%%%%%%%Phan nguong va tim hinh chieu doc gray_min=min(min(anh)); gray_max=max(max(anh)); nguongtach=round(((gray_min+gray_max)/2)); % chuan hoa kich thuoc anh the nguyen lan cua NxN %chuan chieu cao anh if (chieucao/N)>round(chieucao/N) chieucao=round(chieucao/N)*N+N; else chieucao=round(chieucao/N)*N; end %chuan chieu rong anh if (chieurong/N)>round(chieurong/N) chieurong=round(chieurong/N)*N+N; else chieurong=round(chieurong/N)*N; end %%%%%%%%%%%%%%%%%%%% %loc nhieu anh goc anh=double(anh)/255; % chuyen sang kieu double %%%%%%% mat na loc loc=[0 1 0;1 2 1;0 1 0]; loc=1/8*loc; %%%%%%% dung ham loc anh=conv2(anh,loc); anh=uint8(round(anh*255)); %%%%%%%%%%%%%% for i=1:chieucao for j=1:chieurong if (i>chieucao_goc)|(j>chieurong_goc) % ngoai vung bien anh goc anh(i,j)=0; % dat la vung nen anh else % trong vung bien anh goc %anh(i,j)=255-anh(i,j); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 96 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy if (anh(i,j)>nguongtach) % vung nen %anh(i,j)=255; % xoa trang vung nen anh(i,j)=0; else %z(i)=z(i)+1; % tinh cho bieu do xam anh(i,j)=255-anh(i,j); end end end end %%%%%%%%%%%%%%% tinh FS cho moi block FS=[]; k=0; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% u_layer1=zeros(N+2);b_layer1=zeros(N+2);u_layer2=zeros(N+2);b_layer2=zeros(N+2);block_k=zeros(N +2); %%%%%%%%%%%%%%%%%%%%%% for i=1:round(chieucao/N) for(j=1:round(chieurong/N)) %%%%%%%%%% thao tac voi block thu K u_layer1(:,:)=0; b_layer1(:,:)=0; u_layer2(:,:)=0; b_layer2(:,:)=0; vol1=0; vol2=0; block_k(2:N+1,2:N+1)=anh((i-1)*N+1:i*N,(j-1)*N+1:j*N); % tinh gia tri cho lop tren va duoi voi delta1 cho moi vung thu k for ki=2:N+1 for kj=2:N+1 g1_u=block_k(ki,kj)+1; g1_b=block_k(ki,kj)-1; g2=block_k(ki,kj+1); g3=block_k(ki,kj-1); g4=block_k(ki+1,kj); g5=block_k(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer1(ki,kj)=max(temp(1:5)); b_layer1(ki,kj)=min(temp(2:6)); vol1=vol1 + (u_layer1(ki,kj)-b_layer1(ki,kj)); % tinh xong lop tren va duoi voi delta1 % tinh gia tri cho lop tren va duoi voi delta2 g1_u=u_layer1(ki,kj)+1; g1_b=b_layer1(ki,kj)-1; g2=u_layer1(ki,kj+1); g3=u_layer1(ki,kj-1); g4=u_layer1(ki+1,kj); g5=u_layer1(ki-1,kj); temp=[g1_u g2 g3 g4 g5 g1_b]; u_layer2(ki,kj)=max(temp(1:5)); b_layer2(ki,kj)=min(temp(2:6)); vol2=vol2+(u_layer2(ki,kj)-b_layer2(ki,kj)); %%%%%%%%%%%%%%%% tinh xong gia tri cua lop tren duoi voi delta2 end end % ve he truc toa do trucx=[1:N+2]; trucy=[1:N+2]; meshgrid(trucx,trucy); % axes(handles.anhgoc); subplot(2,2,1); anhtem=goc; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 97 GVHD: PGS. TS. Ngô Quốc Tạo
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy anhtem((i-1)*N+1:(i-1)*N+N,(j-1)*N+1:(j-1)*N+N)=0; imshow(anhtem); subplot(2,2,2); %axes(handles.uper); % surf(trucx,trucy,b_layer2) surf(trucx,trucy,u_layer2) subplot(2,2,3); %axes(handles.block); imshow(255-anh((i-1)*N+1:(i-1)*N+N,(j-1)*N+1:(j-1)*N+N)); subplot(2,2,4); %axes(handles.surf); trucx=[1:N]; trucy=[1:N]; meshgrid(trucx,trucy); surf(trucx,trucy,double(anh((i-1)*N+1:(i-1)*N+N,(j-1)*N+1:(j-1)*N+N))); pause(0.3) % tinh FS k=k+1; FS(k)=(vol2-vol1)/2; end end 8) Lienthong function lienthong(i,j,loai) % loai=1 la text, =2 la anh global AFS; global MLT; AFS(i,j)=3; % danh dau la da xet MLT(i,j)=1; % danh dau diem thuoc vung lien thong if (((i-1)>0)&((j-1)>0)& (AFS(i-1,j-1)~=3)&(AFS(i-1,j-1)==loai)) lienthong(i-1,j-1,loai);end if (((j-1)>0)& (AFS(i,j-1)~=3)&(AFS(i,j-1)==loai)) lienthong(i,j-1,loai);end if (((i+1) 0)&(AFS(i+1,j-1)~=3)&(AFS(i+1,j-1)==loai))lienthong(i+1,j-1,loai);end if (((i-1)>0)& (AFS(i-1,j)~=3)&(AFS(i-1,j)==loai)) lienthong(i-1,j,loai);end if (((i+1) 0)&((j+1)<size(AFS,2))& (AFS(i-1,j+1)~=3)&(AFS(i-1,j+1)==loai)) lienthong(i-1,j+1,loai);end if (((j+1)<size(AFS,2))& (AFS(i,j+1)~=3)&(AFS(i,j+1)==loai)) lienthong(i,j+1,loai);end if (((i+1)<size(AFS,1))&((j+1)<size(AFS,2))& (AFS(i+1,j+1)~=3)&(AFS(i+1,j+1)==loai)) lienthong(i+1,j+1,loai);end 9) Vebien function vebien(MLT,N,loai) global anh; m=size(MLT,1); % chieu cao n=size(MLT,2); % chieu rong MLTF=zeros(m+4,n+4); MLTF(3:m+2,3:n+2)=MLT; % de da bao kong bi vuot bien %MLTF for i=3:m+1 % tim diem den dau tien for j=3:n+1 if (MLTF(i,j)==1)break end end if (MLTF(i,j)==1)break end end %%%%%%%%%%%%%%% Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 98 GVHD: PGS. TS. Ngô Quốc Tạo