Luận văn Tìm hiểu phương pháp phân tích bằng bên trong tài liệu ảnh

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ------------    ------------ Nguyễn Thị Hiếu TÌM HIỂU PHƢƠNG PHÁP PHÂN TÍCH BẰNG BÊN TRONG TÀI LIỆU ẢNH Luận văn Thạc sỹ Công nghệ thông tin Thái Nguyên, tháng 11 năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ------------    ------------ Nguyễn Thị Hiếu TÌM HIỂU PHƢƠNG PHÁP PHÂN TÍCH BẰNG BÊN TRONG TÀI LIỆU ẢNH Luận văn Thạc sỹ: Công nghệ thông tin Chuyên ngành: Khoa học máy tính Mã số: 604801 Ngƣời hƣớng dẫn Khoa học: PGS.TS Ngô Quốc Tạo Thái Nguyên, tháng 11 năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC Trang phụ bìa Lời cảm ơn MỤC LỤC ------------------------------------------------------------------------------- i THUẬT NGỮ TIẾNG ANH:--------------------------------------------------------- iii DANH MỤC CÁC HÌNH VẼ -------------------------------------------------------- iv CHƢƠNG I: MỞ ĐẦU ---------------------------------------------------------------- 1 1.1. Cơ sở nghiên cứu và mục đích của luận văn ---------------------------- 3 1.2. Tổ chức của luận văn: -------------------------------------------------------- 4 CHƢƠNG II: TỔNG QUAN VỀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH --------- 5 2.1. Tài liệu ảnh --------------------------------------------------------------------- 5 2.2. Hệ phân tích trang tài liệu -------------------------------------------------- 5 2.3. Thu thập dữ liệu ảnh --------------------------------------------------------- 6 2.4. Tiền xử lý điểm ảnh ----------------------------------------------------------- 9 2.4.1. Xử lý nhị phân ---------------------------------------------------------- 10 2.4.2. Giảm nhiễu--------------------------------------------------------------- 11 2.4.3. Phân đoạn ảnh ----------------------------------------------------------- 12 2.4.4. Làm mảnh và xác định vùng ----------------------------------------- 12 2.4.5. Mã hóa CC và véctơ hóa ---------------------------------------------- 13 2.5. Phân tích đặc trƣng của tài liệu ảnh ------------------------------------- 15 2.6. Phân tích đối tƣợng văn bản trong tài liệu ----------------------------- 15 2.6.1. Xác định góc nghiêng của văn bản ---------------------------------- 16 2.6.2. Phân tích bố cục của trang tà i liệu ảnh ------------------------------ 18 2.7. Nhận dạng ký tự quang học (OCR) --------------------------------------- 19 2.7.1. Thuật toán OCR ----------------------------------------------------- 20 2.7.1.1. Trích chọn đặc trƣng --------------------------------------- 20 2.7.1.2. Phân loại ------------------------------------------------------ 21 2.7.2. Nhận dạng ký tự dựa trên ngữ cảnh ------------------------------ 21 2.8. Phân tích các đối tƣợng ảnh trong tài liệu ------------------------------ 22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 3: THUẬT TOÁN TÁCH VĂN BẢN - ẢNH TỪ TRANG TÀI LIỆU ẢNH ------------------------------------------------------------------------------ 24 3.1. Tổng quan về phân tách văn bản – ảnh --------------------------------- 24 3.2. Những đặc trƣng chung của một tệp tài liệu ảnh --------------------- 27 3.3. Thuật toán phân tách văn bản - ảnh -------------------------------------- 30 3.3.1. Xoá bỏ các đối tƣợng tuyến tính --------------------------------- 31 3.3.2. Phân tích các thành phần liên thông của nét bút --------------- 32 3.3.3. Kết hợp các nét ký tự tạo thành các chuỗi văn bản ------------ 34 3.3.4. Thực hiện các phép toán hình thái ------------------------------- 35 3.3.5. Phân tích các thành phần liên thông mới ----------------------- 35 3.3.6. Biểu diễn cấu trúc thông tin của các chuỗi văn bản ----------- 36 CHƢƠNG IV: PHƢƠNG PHÁP PHÂN TÍCH BẢNG T-RECS TRONG TRANG TÀI LIỆU ẢNH ------------------------------------------------------------ 39 4.1. Giới thiệu -------------------------------------------------------------------- 39 4.2. Thuật toán phân đoạn khởi tạo ---------------------------------------- 41 4.2.1. Trƣờng hợp thuật toán nhận dạng sai cột ----------------------- 42 4.2.2. Cải tiến các bƣớc của thuật toán phân đoạn khởi tạo T - Recs++ 44 4.2.3. Những ƣu điểm của thuật toán ----------------------------------- 46 4.2.4. Những mặt hạn chế của thuật toán khởi tạo -------------------- 47 4.3. Các bƣớc xử lý khối sau khi phân đoạn ------------------------------ 48 4.3.1. Trộn các khối phân đoạn sai -------------------------------------- 48 4.3.2. Phân tách các cột bị trộn vào một khối -------------------------- 49 4.3.3. Nhóm các từ bị phân tách ----------------------------------------- 52 4.4. Phân tích khối -------------------------------------------------------------- 53 4.5. Xác định cấu trúc các cột, hàng ---------------------------------------- 54 CHƢƠNG 5 CHƢƠNG TRÌNH THƢ̉ NGHIỆM VÀ MINH HỌA THUẬT TOÁN T-RECS++ --------------------------------------------------------------------- 56 5.1. Mô tả chƣơng trình ------------------------------------------------------- 56 5.2. Một số kết quả ------------------------------------------------------------- 58 KẾT LUẬN VÀ ĐỀ XUẤT ---------------------------------------------------------- 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên THUẬT NGỮ TIẾNG ANH 3 – D 3 Dimensions CAD Computer Aided Design CAM Computer Aided Manufacturing CC Chain Code CCs Connected Components CPU Control Processing Unit DP Dynamic Programming HWRatio Heigh Width Ratio K – NNR K – Nearest Neighbor Rule LC Linear Component LSD Local Stroke Density NCCs New Connected Components NNR Nearest Neighbour Rule OCR Optical Character Recognition T-Recs Table Recognition System WBRatio White Black Ratio WDG White-space Density Graphs Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC HÌNH VẼ Hình 2.1 Sơ đồ quá trình xử lý tài liệu Hình 2.2 Sơ đồ quá trình phân tích trang tài liệu Hình 2.3 Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên bản, (b) chọn ngưỡng thấp, (c) chọn ngưỡng hợp lý, (d) chọn ngưỡng quá cao. Hình 2.4 Ảnh nguyên bản(Vân tay) bên trái và ảnh sau khi làm mảnh bên phải. Hình 2.5 Tài liệu ảnh trước và sau các bước tiền xử lý. Ảnh (a) gốc, ảnh (b) ảnh sau khi chuyển về ảnh nhị phân, ảnh (c) ảnh sau khi chỉnh nghiêng, ảnh (d) ảnh sau khi lọc nhiễu. Hình 2.6 văn bản bị nghiêng sau khi được quét qua máy quét. Hình 2.7 Ví dụ minh họa kết quả phân tích bố cục của trang tài liệu ảnh Hình 2.8 Chữ viết tay có thể gây nhầm lẫn Hình 3.1 Ví dụ về các đối tượng văn bản và đối tượng ảnh Hình 3.2 Biểu diễn các điểm ảnh giao nhau Hình 3.3 Một số trường hợp ngoại lệ Hình 3.4 Sơ đồ thuật toán phân tách văn bản Hình 3.5 Hình 3.5 Nhận dạng đường kẻ nghiêng với phép toán kéo dãn Hình 4.1 Ví dụ minh họa tư tưởng của thuật toán khởi tạo Hình 4.2 thuật khởi tạo đối với một đoạn văn bản Hình 4.3 Trường hợp thuật toán nhận dạng sai cột Hình 4.4 Trường hợp giữa các dòng của một cột trong bảng có ô trắng Hình 4.5 Mô phỏng việc thực hiện các bước đã cải tiến của thuật toán Hình 4.7 Quá trình phân đoạn các cột của bảng Hình 4.8 Trường hợp một ô của bảng chiếm nhiều dòng Hình 4.9 Những mặt hạn chế của thuật toán Hinh 4.10 Trộn hai khối bị phân tách Hình 4.11 Tách các cột bị trộn Hình 4.12 Trộn lại các khối con bị tách Hình 4.14 Tách các khối loại 1 thành các ô của bảng Hình 4.15 Tách các khối loại 2 thành các hàng trong bảng Hình 5.1 Giao diện chương trình T-Recs Hình 5.2 Nhận dạng khối văn bản với T-Recc++ Hình 5.3 Nhận dạng tài liệu ảnh là bảng quy chế với T-Recs++ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lêi c¶m ¬n Trong quá trình làm luận văn vừa qua , dưới sự giúp đỡ và chỉ bảo nhiệt tình của PGS . TS Ngô Quốc Tạo – Viện Công nghệ Thông tin – Viện khoa học Việt Nam , luận văn của tôi đã được hoàn thành . Mặc dù đã cố gắng không ngừng cùng với sự tận tâm của thầy hướng dẫn song do thời gian và khả năng vẫn còn nhiều hạn chế nên luận vă n khó tránh khỏi những thiếu sót trong quá trình làm luận văn . Để hoàn thành được luận văn này. Em xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS Ngô Quốc Tạo - người thầy đã tận tình giúp đỡ em trong suốt quá trình tìm hiểu , xây dựng và phát triển luận văn này . Em xin chân thành cảm ơn các thầy , cô giáo trong Viện Công nghệ Thông tin – Viện khoa học Việt N am đã giảng dạy và hướng dẫn em trong suốt 2 năm học qua. Em cũng xin cảm ơn ban lãnh đạo khoa và toàn thể thầy cô giáo trong khoa Công Nghệ thông tin – Đại Học Thái Nguyên đã tạo điều kiện tốt nhấ t giúp em học tập và hoàn thành luận văn này . Và cuối cùng tôi cũng xin cảm ơn gia đình , các bạn trong nhóm luận văn và toàn thể các học viên lớp Cao học K 6 đã động viên , quan tâm và giúp đỡ tôi trong thời gian qua. Cuối cùng tôi rất mong nhận được sự chỉ dẫn , góp ý của các thầy cô và các bạn để luận văn của tôi được hoàn thiện hơn . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 CHƢƠNG 1: MỞ ĐẦU Nhận dạng và xử lý ảnh là một lĩnh vực mang tính khoa học và công nghệ. Ở Việt Nam Nhận dạng và xử lý ảnh là một ngành khoa học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ phát triển của nó rất nhanh. Sự ra đời của nó đã tạo ra các kỹ thuật quan trọng ảnh hưởng trực tiếp đến các lĩnh vực như: Tivi, truyền thông, kỹ xảo đồ hoạ… Cùng với sự phát triển đó có những nhu cầu thực tế đặt ra thách thức các nhà khoa học máy tính càng nhiều . Những công việc , những bài toán được xử lý theo lối cổ truyền không theo kịp tốc độ phát triển của công nghệ ngày nay . Một trong những bài toán đó chính là các tài liệu được lưu trữ trên các chất liệu cổ truyền như giấy, gỗ, vải với khối lượng khổng lồ , chứa đựng rất nhiều tri thức của nhân loại nhưng lại không có độ bền vĩnh cửu , khó xử lý và lưu trữ . Một bài toán khác là ngày nay công việc văn phòng liên quan nhiều đến các tài liệu không đơn thuần là tài liệu chữ mà tài liệu có nhiều thành phần như bảng biểu , ảnh. Tất cả các tài liệu đó nếu tiếp tục lưu trữ theo phương pháp cổ truyền thì rất phức tạp và khó xử lý . Vậy làm thế nào để chuyển đổi những kho tàng tri thức trên vào máy tính để lưu trữ , xử lý dễ dàng, thuận tiên và nhanh gọn . Một lĩnh vực của khoa học nhân dạng là Phân tích tài liệu ảnh đã ra đời nhằm biểu diễn thông tin trong các tài liệu ảnh dưới dạng có cấu trúc . Hệ phân tích và nhận dạng tài liệu ảnh có mục đích là chuyển đổi tự động những thông tin lưu trữ trong tài liệu giấy thành biểu diễn dưới dạng những cấu trúc mà có thể truy xuất, thay đổi được bằng máy tính. Quy trình xử lý của một hệ phân tích tài liệu bắt đầu bằng việc lấy dữ liệu, các tài liệu từ giấy in sẽ được quét qua máy quét để lưu trữ trong máy tính dưới dạng các tệp dữ liệu ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 Một tài liệu ảnh là một cách biểu diễn trực quan của các trang tài liệu được in như một bài tạp chí, một lá thư, một trang báo, một mẩu thư hay một bản vẽ kỹ thuật, .v.v.. Một tài liệu ảnh có thể bao gồm các chuỗi ký tự, các hình vẽ, các bức ảnh, .v.v.. Bên cạnh việc chuyển toàn bộ nội dung của tài liệu sang tài liệu điện tử cũng cần phải bảo toàn cấu trúc và định dạng của tài liệu. Mục tiêu cơ bản của một hệ phân tích tài liệu ảnh hoàn chỉnh đó là chuyển một tài liệu lưu trữ bằng giấy sang dạng biểu diễn có thứ tự cấu trúc và nội dung của nó. Tài liệu được chuyển sang phải có khả năng thay đổi, soạn thảo và lưu trữ bởi vì nội dung của tài liệu có thể truy cập bởi cấu trúc của nó thay vì phải truy cập dưới dạng những mẫu ảnh. Có một số lượng lớn ứng dụng của hệ phân tích tài liệu ảnh được ứng dụng trong các lĩnh vực như: dịch vụ bưu chính, Chính phủ, chăm sóc y tế, thư viện, ...v.v. Mục đích của luận văn là nghiên cứu kỹ thuật nhận dạng bảng và trích chọn ra đối tượng của tài liệu ảnh. Kỹ thuật “Phân tích bảng – T-Recs” là nghiên cứu chính . Với tư tưởng chính của “Phương pháp phân tích bảng” đó là không xem xét đến bất cứ một loại đường phân cách nào để xác định cấu trúc bảng. Thay vào đó phương pháp sẽ tập trung vào việc nhận biết các từ trong cùng một khối logic (chẳng hạn các từ trong cùng một cột dữ liệu sẽ được cho vào trong cùng một khối). Phương pháp sẽ không đi tìm những đặc trưng để phân biệt hai vùng dữ liệu (hai cột) khác nhau mà tìm những đặc trưng để tìm ra các từ trong cùng một khối logic và từ đó xây dựng cấu trúc riêng theo phương pháp tiếp cận bottom - up. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 1.1. Cơ sở nghiên cứu và mục đích của luận văn Ảnh là một đối tượng khá phức tạp về đường nét, dung lượng điểm ảnh, độ sáng tối, môi trường để thu nhận ảnh phong phú kéo theo nhiễu. Trong nhiều khâu phân tích ảnh ngoài việc đơn giản hoá các phương pháp toán học đảm bảo tiện lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử ảnh theo cách của con người. Trong các bước xử lý đó nhiều khâu hiện nay đã xử lý theo các phương pháp trí tuệ của con người. Những hệ thống nhận dạng cấu trúc không chỉ đơn giản là chuyển một tài liệu in thành một tài liệu điện tử mà hơn thế nữa còn là xây dựng những quá trình xử lý kết hợp chẳng hạn như: tự động chép nội dụng, đánh chỉ mục và phân loại. Do đó việc quan trọng là kèm theo nội dung của tài liệu cũng phải trích chọn ra những cấu trúc đi kèm với từng nội dung đó. Nhận dạng bảng là bài toán nhận dạng ra cấu trúc bảng có trong trang tài liệu ảnh, bao gồm việc nhận dạng các cột, các dòng và các ô có chứa dữ liệu trong bảng. Nhận dạng đối tượng ảnh là bài toán nhằm phân tách các đối tượng ảnh trong những trang tài liệu ảnh có chứa hỗn hợp các đối tượng là chuỗi ký tự và các đối tượng ảnh như: các sơ đồ, hình vẽ, bức ảnh …v.v. Mặc dù đã có nhiều kỹ thuật trong hệ thống nhận dạng cấu trúc. Tuy nhiên những nghiên cứu trên những vấn đề đó vẫn còn tiếp tục phát triển bởi vì chất lượng, độ chính xác, tính hiệu quả của những phương pháp được công bố trước đây vẫn còn chưa hoàn chỉnh và cần phải cải tiến chúng. Luận văn này trình bày kỹ thuật nhận dạng cấu trúc bảng bên trong tài liệu ảnh T-Recs và đề xuất một số phương pháp khắc phục hạn chế thuật toán T-Recs để hoàn thiện hiện hơn phương pháp phân tích bảng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 1.2. Tổ chức của luận văn Luận văn được trình bày thành 5 chương và 1 phụ lục. Chương 1 Trình bày tóm tắt cơ sở nghiên cứu và mục đích cũng như cách tổ chức của luận văn. Chương 2 Tổng quan về hệ phân tích tài liệu ảnh và các thành phần chính trong hệ phân tích tài liệu ảnh : Lấy dữ liệu , xử lý ảnh , trích chọn đặc trưng, nhận dạng đối tượng ảnh và nhận dạng văn bản . Chương 3 trình bày bài toán phân tách văn bản và ảnh một cách riêng rẽ. Trong chương này một thuật toán phân tách văn bản và ảnh cũng sẽ được trình bày dựa vào việc phân tích các thành phần liên thông (CCs). Chương 4 trình bày phương pháp phân tích bảng ( T-Recs) dựa trên những hình chữ nhật bao quanh một từ và đầu ra là cấu trúc logic của khối văn bản, cụ thể với những bảng nhận dạng được sẽ là cấu trúc các cột và các ô của bảng dữ liệu. Phân tích những mặt hạn chế của thuật toán - trường hợp nhận dạng chưa chính xác các cột dữ liệu trong bảng luận văn đưa ra thuật toán khắc phục những mặt hạn chế đó. Chương 5 Chương trình thử nghiệm và minh họa phân tích bảng trong trang tài liệu ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 CHƢƠNG 2: TỔNG QUAN VỀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH 2.1. Tài liệu ảnh Hình ảnh của một đối tượng là sự sao chụp lại chính bản thân đối tượng đó. Ảnh được hình thành qua một hệ thống ảnh. Tài liệu ảnh là các file ảnh đã được số hóa thu được bằng cách: quét các trang tài liệu, chụp ảnh, máy fax, hoặc từ vệ tinh, các file ảnh này được lưu trữ trong máy tính. Ảnh tài liệu có nhiều loại: đen trắng, ảnh màu, ảnh đa cấp xám,…v.v. 2.2. Hệ phân tích trang tài liệu Hệ phân tích trang tài liệu : Là một hệ thống bao gồm những thuật toán và các k ỹ thuật có thể áp dụng cho các tài liệu ảnh để lấy ra được các thông tin mà máy tính có thể đọc được và hiểu được từ các điểm dữ liệu ảnh. Một lĩnh vực thu được nhiều thành công nhất trong phân tích tài liệu ảnh đó là Nhận dạng Ký tự Quang học (OCR), phần mềm có khả năng nhận, chuyển đổi các ký tự từ các loại tài liệu dưới dạng ảnh sang tài liệu dưới dạng text . OCR giúp người dùng có khả năng soạn thảo và tìm kiếm nội dung của tài liệu. Thành phần chính có trong một hệ phân tích tài liệu: Mục đích của một hệ phân tích tài liệu là có khả năng nhận dạng ra các đối tượng văn bản, đối tượng ảnh trong tài liệu ảnh và có khả năng trích chọn ra được các thông tin mà người dùng mong muốn. Chúng ta có thể chia một hệ phân tích tài liệu thành hai phần. Phần thứ nhất là xử lý văn bản, liên quan đến việc xử lý các đối tượng văn bản: ký tự, chuỗi ký tự, các từ. Xử lý văn bản bao gồm các công việc sau: xác định độ nghiêng của tài liệu (độ nghiêng hay độ xiên của tài liệu ảnh do tài liệu được đặt không đúng khi thực hiện quét vào từ máy quét), tìm các cột, các đoạn văn bản, các dòng văn bản, các từ và cuối cùng là Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 nhận dạng văn bản (có thể thêm các thuộc tính như loại phông chữ, kích thước của phông chữ) bởi phương pháp nhận dạng ký tự quang học (OCR). Phần thứ hai là xử lý các đối tượng ảnh là các đối tượng tạo ra từ các đường kẻ trong sơ đồ, các đường kẻ phân tách giữa các đoạn văn bản, các hình vẽ, các lôgô của công ty… Sau khi áp dụng các kỹ thuật phân tích ảnh và văn bản, các đối tượng cần nhận dạng trong tài liệu ảnh được trích ra và được biểu diễn dưới dạng một tài liệu định dạng khác, chẳng hạn như word, html… Ta có thể tóm tắt quá trình xử lý của hệ phân tích tài liệu theo sơ đồ Hình 2.1 [8]: Hình 2.1 Sơ đồ quá trình xử lý tài liệu Tại sao lại phải phân tích tài liệu ? Những bài toán trong phần giới thiệu đã đề cập , ta hãy xem xét kỹ hơn về bài toán điển hình để thấy được sự cần thiết của việc phân tích tài liệu . - Lượng tri thức vô giá của nhân loại với số lượng lớn được lưu trữ trong các thư viện cổ điển dưới các chất liệu như giấy , vải, gỗ vẫn còn tồn tại rất nhiều , việc các tài liệu bị mất các thông tin , thiếu thông tin, số lượng bản Xử lý tài liệu Xử lý văn bản Nhận dạng ký tự quang học Phân tích cấu trúc trang Xử lý đối tượng ảnh Xử lý đường kẻ Xử lý vùng và ký tự đặc biêt Văn bản Xác định độ nghiêng, dòng văn bản, các khối văn bản, các đoạn văn bản Đường thẳng, đường cong, góc Vùng được tô Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 sao hạn chế hay thậm chí các tài liệu bị thoái hoá theo thời gian là những vấn đề phổ biến. Vì vậy chúng cần phải được khôi phục và chỉnh sửa bằmg những kỹ thuật phân tích tài liệu. - Ngày nay các văn phòng hiện đại các công việc đều được giải quyết dựa vào máy tính . Các tài liệu văn bản với nhiều đối tượng (chữ, hình ảnh , các sơ đồ ) được tạo ra trên nhiều m áy tính khác nhau , phần mềm khác nhau do đó có thể là các định dạng của các tài liệu đó là không tương thích với nhau, kích thước cũng khác nhau . Như vậy cần một hệ phân tích tài liệu giúp nhận dạng các loại tài liệu, trích chọn ra được các phần chức năng và có thể chuyển từ một định dạng máy tính này sang một định dạng khác. - Một bài toán khác được đề cập là các máy phân loại thư tự động dùng để phân loại, sắp xếp thư và nhận dạng địa chỉ thư. Những máy này đã có từ những thập kỷ trước, nhưng ngày nay yêu cầu cao hơn đó là xử lý nhiều thư hơn, nhanh hơn và yêu cầu chính độ xác cao hơn. Những bài toán trên đã tạo ra thách thức và động lực cho sự phát triển những giải pháp trong tương lai của một hệ phân tích tài liệu. Hình 2.2 mô tả các bước xử lý cho một hệ phân tích tài liệu [8]. Sau khi dữ liệu (tài liệu ảnh ) được đưa vào , tài liệu ảnh trải qua các bước xử lý điểm ảnh và phân tích đặc trưng và sau đó phần nhận dạng văn bản và phần nhận dạng ảnh được tách ra hai chức năng riêng rẽ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 Hình 2.2 Sơ đồ quá trình phân tích trang tài liệu Các hệ phân tích tài liệu sẽ ngày càng phát triển và hiển nhiên là chúng sẽ có trong các hệ xử lý tài liệu. Chẳng hạn như, hệ thống OCR sẽ được sử dụng rộng rãi để lưu trữ, tìm kiếm và trích dẫn từ các tài liệu lưu trữ trên giấy. Các kỹ thuật phân tích cách bố trí trong một trang tài liệu giúp nhận dạng những biểu mẫu (form) riêng biệt, hay định dạng của một trang tài liệu và cho phép sao lưu tài liệu đó. Các sơ đồ có thể được đưa vào từ các bức ảnh hay vẽ bằng tay và có thể thay đổi, soạn thảo lại chúng. Sử dụng máy tính có thể chuyển các tài liệu viết bằng tay thành các tài liệu điện tử được lưu trữ trong máy tính. Các tài liệu được lưu trữ trong các thư viện, các tài liệu kỹ thuật trong các công ty sẽ được chuyển đổi sang thành tài liệu điện tử nhằm nâng cao hiệu quả, thuận tiện trong việc lưu trữ và dễ dàng mang đến cơ quan hay mang về nhà. Mặc dù tài liệu sẽ ngày càng được xử lý và lưu trữ nhiều trong máy tính nhưng trên thực tế có rất nhiều các hệ thống khác nhau mà tài Thu nhận dữ liệu Trang tài liệu Xử lý điểm ảnh Phân tích đặc trưng Phân tích và nhận dạng đối tượng văn bản Phân tích và nhận dạng đối tượng ảnh Mô tài liệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 liệu giấy là phương tiện làm việc hiệu quả và chắc chắn rằng tài liệu giấy vẫn sẽ là phương tiện làm việc với chúng ta trong một vài thập kỷ nữa. Vấn đề ở đây là làm sao chúng ta tích hợp những tài liệu giấy vào trong máy tính xử lý. Sau đây ta sẽ tìm hiểu ngắn gọn các bước xử lý của một hệ phân tích tài liệu ảnh . 2.3. Thu nhận dƣ̃ liệu ảnh Các dữ liệu trên các trang tài liệu giấy thường được quét qua máy quét và đưa vào máy tính dưới dạng file ảnh , chúng bao gồm các điểm ảnh (pixels) và được lưu trữ . Với ảnh nhị phân g iá trị điểm ảnh có thể là 0 hoặc 1 ,với ảnh đa cấp xám và ảnh màu giá trị điểm ảnh nằm trong khoảng 0 đến 255 với 3 giá trị R, G, B từ 0 đến 255. Ở độ phân giải thông thường thì có 120 điểm ảnh trên 1 centimet và với 1 trang có kích thước 20 x 30 cm thì tạo ra một ảnh với 2400 x 3600 điểm ảnh. Do đó có thể thấy rằng một tài liệu ảnh chỉ bao bồm các dữ liệu thô (giá trị các điểm ảnh) và chúng sẽ được sử dụng những kỹ thuật phân tích thích hợp để lấy ra được các thông tin cần thiết. 2.4. Tiền xử lý điểm ảnh Bước tiếp theo trong một hệ phân tích tài liệu là thực hiện một số thao tác xử lý trên tài liệu ảnh thu được để chuẩn bị cho những bước phân tích tiếp theo. Chẳng hạn như các thao tác: chọn ngưỡng để chuyển ảnh đa cấp xám, ảnh màu về dạng ảnh nhị phân, giảm nhiễu để loại bỏ những dữ liệu không liên quan, phân đoạn để phân tách các thành phần khác nhau trong ảnh và cuối cùng là làm mảnh hay dò biên để dễ dàng xác định các vùng, các đặc trưng thích hợp và các đối tượng cần quan tâm. Sau những bước xử lý ở trên, dữ liệu thường được biểu diễn dưới dạng nén lại như dùng mã hoá CC và biểu diễn dưới dạng véctơ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 2.4.1. Xƣ̉ lý nhị phân Với những ảnh đa cấp xám các thông tin đã sẵn ở dạng nhị phân chẳng hạn như các chuỗi văn bản hay các đối tượng ảnh, thì phương pháp nhị phân thông thường sẽ được thực hiện trước. Mục đích của phương pháp này là sẽ tự động chọn một ngưỡng cần thiết để tách ảnh ra làm hai phần: thông tin ảnh và thông tin nền. Việc lựa chọn một ngưỡng tốt (ngưỡng mà có thể phân tách ảnh thành hai phần: phần ảnh, phần nền một cách chính xác) luôn là một quá trình khó và dễ gây ra lỗi (0). Hình 2.3 Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên bản, (b) chọn ngưỡng thấp, (c) chọn ngưỡng hợp lý, (d) chọn ngưỡng quá cao. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 Quá trình xử lý này sẽ gặp khó khăn trong các trường hợp khi: độ tương phản giữa giá trị các điểm ảnh văn bản và nền là thấp (chẳng hạn như văn bản được soạn thảo trên một nền xám thuần nhất), nét của văn bản mỏng hoặc dữ liệu không được chiếu sáng tốt khi thực hiện quét tài liệu giấy. Rất nhiều phương pháp đã được phát triển để khắc phục những hạn chế trên, chẳng hạn như phương pháp tách ngưỡng tự động tìm ra giá trị θ thích hợp để chia ảnh thành hai phần. 2.4.2. Giảm nhiễu Nhiễu trong tài liệu ảnh là do nhiều nguyên nhân bao gồm: sự thoái hoá theo thời gian, quá trình sao ch ép, quá trình quét tài liệu. Một số kỹ thuật xử lý ảnh sẽ được áp dụng để loại bỏ nhiễu. Sau khi được nhị phân hoá, tài liệu ảnh sẽ được lọc để giảm nhiễu. Trên thực tế tồn tại nhiều loại nhiễu, tuy nhiên người ta thường xem xét 3 loại nhiễu chính: nhiễu cộng, nhiễu nhân và nhiễu xung. Chúng xuất hiện như những điểm ảnh khác biệt so với vùng xung quanh, chẳng hạn các điểm ảnh nhiễu ON (điểm mang thông tin ảnh) trong vùng nền OFF (điểm mang thông tin nền) hay ngược lại các điểm ảnh OFF trong vùng nền ON và các cạnh gồ ghề của ký tự hay các đối tượng ảnh. Bản chất của nhiễu là thường tương ứng với tần số cao và cơ sở lý thuyết của các bộ lọc là chỉ cho những tín hiệu có tần số nào đó thông qua, do đó để lọc nhiễu người ta thường sử dụng bộ lọc thông thấp hay lọc trung bình. Với nhiễu cộng và nhiễu nhân ta dùng các bộ lọc thông thấp, trung bình; với nhiễu xung ta dùng lọc trung vị, giả trung vị. Trong lọc trung bình, thường người ta ưu tiên cho các hướng để bảo vệ biên của ảnh khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng tùy theo các trường hợp khác nhau. Các bộ lọc trên là bộ lọc tuyến tính theo nghĩa là điểm ảnh ở tâm cửa số sẽ được thay bởi tổ hợp các điểm lân cận chập với mặt nạ. Lọc thông thấp thường được sử dụng để làm trơn nhiễu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 Các bộ lọc phi tuyến cũng được dùng trong kỹ thuật tăng cường ảnh. Trong kỹ thuật này người ta dùng bộ lọc trung vị, bộ lọc giả trung vị. Với bộ lọc trung vị các điểm ảnh sẽ được thay thế bởi trung vị các điểm ảnh, bộ lọc giả trung vị thì các điểm ảnh được thay thế bởi trung bình cộng của hai giá trị “trung vị”. 2.4.3. Phân đoạn ảnh Quá trình phân đoạn ảnh được thực hiện làm hai giai đoạn . Giai đoạn thứ nhất, tách các lớp văn bản và ảnh riêng biệt nếu như trong tài liệu có chứa cả văn bản và ảnh . Giai đoạn thứ hai là thực hiện phân tách trên hai lớp đối tượng vừa tách ở trên, với văn bản xác định các cột, các đoạn văn bản, các từ và các ký tự; với lớp đối tượng ảnh thực hiện phân tách các biểu tượng, các hình vẽ, các đường kẻ và các hình ảnh. Chẳng hạn như một tài liệu ảnh có chứa các đoạn văn bản và các hình minh hoạ giống như một trang tạp chí, đầu tiên văn bản và ảnh sẽ được tách riêng. Sau đó văn bản sẽ được tách ra thành các chuỗi ký tự. Ảnh thì được tách ra các thành phần như hình chữ nhật, hình tròn, các đường kẻ, biểu tượng .v.v.. Sau bước trên tài liệu ảnh sẽ phân tách ra thành những đối tượng nhỏ hơn như các ký tự và các thành phần cơ bản của ảnh. 2.4.4. Làm mảnh và xác định vùng Làm mảnh ảnh là một thao tác xử lý ảnh trong đó đối tượng ảnh được biểu diễn như là những đường trục được gọi là đường tâm hay còn gọi là lấy xương của ảnh. Một đối tượng ảnh khi đó chỉ được biểu diễn bởi đường xương của nó bằng việc giảm bớt số lượng điểm ảnh có giá trị ON của đối tượng và vẫn đảm bảo tính chất liên thông của đối tượng. Mục đích của việc làm mảnh ảnh là giảm bớt các thành phần mà chỉ lưu trữ các thông tin thiết yếu phục vụ cho việc phân tích và nhận dạng sau này thuận tiện hơn. Chẳng hạn như một đường kẻ thẳng có thể vẽ bằng tay với độ đậm của nét bút là Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 khác nhau nhưng có thể biểu diễn chúng giống nhau. Trong Hình 2.4 đưa ra ví dụ ảnh được phân tích bằng phương pháp làm mảnh. Hình 2.4 Ảnh nguyên bản(Vân tay) bên trái và ảnh sau khi làm mảnh bên phải. Lưu ý rằng nếu một hình tròn hay một hình vuông mà được tô kín bởi các điểm đen thì kết quả làm mảnh những đối tượng trên sẽ là một điểm ảnh nằm tại tâm của hình vẽ bất kể kích thước của đối tượng là như thế nào. Do đó có thể thấy rõ ràng rằng việc xác định được vùng biên của đối tượng là rất quan trọng. Nói chung với các đối tượng có kích thước lớn, dò biên là phương pháp lựa chọn thích hợp để biểu diễn đối tượng, còn đối với những đối tượng được tạo thành bởi những nét kết nối dài thì làm mảnh là phương pháp thích hợp hơn. Làm mảnh thường được sử dụng như là một quá trình tiền xử lý đối với những ứng dụng phân tích tài liệu như xử lý sơ đồ hay bản đồ. Với những đối tượng ảnh lớn mà vùng ảnh được tô đầy chẳng hạn như những lôgô thì phương pháp dò biên đối tượng thích hợp hơn. Nhưng với những vùng nhỏ, chẳng hạn từng ký tự riêng biệt thì cũng không phải phương pháp làm mảnh cùng không phải phương pháp dò biên được thực hiện mà khi đó vùng ảnh sẽ được biểu diễn dưới dạng mảng các giá trị của điểm ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 2.4.5. Mã hóa CC và véctơ hóa Khi một đối tượng ả nh được biểu diễn dưới dạng xương của ảnh hay bằng đường viền, chúng có thể biểu diễn một cách hiệu quả hơn là lưu các điểm ảnh một cách đơn giản các giá trị ON và OFF. Một trong những phương pháp lưu ảnh hiệu quả đó là lưu dưới dạng mã xích CC (Chain Code – Freeman 1974), trong đó các điểm có giá trị ON được biểu diễn thông qua tập các điểm láng giềng đi theo một hướng quy định. Thay vì phải lưu trữ vị trí của điểm ảnh có giá trị ON chúng ta sẽ lưu trữ hướng của các điểm láng giềng. Các điểm láng giềng của một điểm x là tất cả các điểm nằm liền kề với x thuộc ma trận 3 x 3 với điểm x là tâm. Có hai ưu điểm khi biểu diễn giá trị điểm ảnh theo hướng thay vì phải lưu vị trí của điểm ảnh. Thứ nhất đó là việc lưu trữ hiệu quả hơn. Thông thường với những ảnh có kích thước lớn hơn 256 x 256, toạ độ giá trị điểm ảnh ON thường được biểu diễn bởi 16 bít; trái lại với cách lưu trữ CC một điểm láng giềng thuộc 1 trong tám hướng, do đó mỗi một điểm ảnh ON chỉ cần biểu diễn bằng 1 byte hay thậm chí chỉ cần 3 bít để lưu. Một ưu điểm khác có thể thấy trong CC đó là vì CC lưu theo cấu trúc các điểm ảnh có liên quan với nhau và do đó dựa vào cách thức lưu trữ này có thể thực hiện các công việc xử lý như làm trơn các đường cong và tính xấp xỉ các đường thẳng trơn. Sau bước xử lý điểm ảnh, dữ liệu thô của ảnh đã được biểu diễn ở cấp độ trừu tượng cao hơn: đã khoanh được vùng bao của chuỗi ký tự, biểu diễn CC và véctơ của các đường cong và đường thẳng, hay đã xác định được vùng biên của các đối tượng. Tài liệu ảnh qua các quá trình tiền xử lý sẽ là tài liệu cơ sở cho quá trình phân tích cấu trúc của tài liệu đó . Hình 2.5 minh họa một tài liệu trước và sau khi thực hiện quá trình tiền xử lý. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 Hình 2.5 Tài liệu ảnh trước và sau các bước tiền xử lý. Ảnh (a) gốc, ảnh (b) ảnh sau khi chuyển về ảnh nhị phân, ảnh (c) ảnh sau khi chỉnh nghiêng, ảnh (d) ảnh sau khi lọc nhiễu. 2.5. Phân tích đặc trƣng của tài liệu ảnh Sau quá xử lý trên các điểm ảnh , các đặc trưng của các đối tượng trên tài liệu ảnh sẽ được trích chọn và phân tích để giúp ích cho những bước nhận dạng sau này. Tại bước phân tích đặc trưng ảnh, dữ liệu ảnh làm mảnh và biểu diễn dưới dạng CC sẽ được phân tích để xác định các đường thẳng, các đường cong và các điểm quan trọng nằm dọc trên đường cong. Các đường cong thường được tính xấp xỉ bởi hình đa giác. Các điểm quan trọng chẳng hạn các điểm góc và điểm bị uốn cong đều được xác định để giúp ích cho việc phân tích nhận dạng các hình vẽ. Đối với các vùng giới hạn tương ứng của từng ký tự riêng rẽ hay các biểu tượng ảnh, các đặc trưng nội tại như tỉ lệ hình dáng, độ chặt của hình bao (tỉ lệ giữa diện tích và chu vi), tính không đối xứng, độ đậm đặc của các điểm đen, tính trơn của đường viền, số lượng đường viền, số lượng các đường thẳng giao nhau và các đường đầu mút đều được tính toán để làm dữ liệu đầu vào phục vụ cho việc nhận dạng từng đối tượng. 2.6. Phân tích đối tƣợng văn bản trong tài liệu Có hai loại phân tích được áp dụng trong việc phân tích văn bản trong tài liệu ảnh. Loại thứ nhất là nhận dạng ký tự quang học (OCR) để nhận dạng từng ký tự, các chuỗi ký tự từ ảnh bitmap (bmp), loại thứ hai là phân tích sơ đồ trình bày của trang tài liệu nhằm nhận biết được định dạng của văn bản, và (a) (b) (c) (d) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 từ đó hiểu được cấu trúc, vị trí, chức năng của các khối văn bản (tiêu đề chính, tiêu đề phụ, đoạn văn bản, chú thích .v.v..). Phụ thuộc vào cách sắp xếp của các khối văn bản, một trang văn bản có thể là một trang tiêu đề, một bảng mục lục của tạp chí, một biểu mẫu kinh doanh, hay là một phong bì thư. Nhận dạng ký tự quang học và phân tích sơ đồ trình bày có thể được thực hiện một cách riêng rẽ, hay có thể lấy kết quả của phần này để sử dụng cho phần kia. Nhận dạng ký tự quang học thường được nhận biết như là ứng dụng nhận dạng ký tự viết tay hay các ký tự trong tài liệu in. Kỹ thuật phân tích sơ đồ trình bày được áp dụng để phân tích định dạng của trang, một loại ứng dụng phân tích sơ đồ trình báy đó là nhận dạng biểu mẫu, giúp phân tích và nhận dạng cấu trúc biểu mẫu và các văn bản có trong biểu mẫu. Trong một số trường hợp người ta cần phải xác định độ nghiêng của tài liệu bởi vì tài liệu được quét có thể bị nghiêng so với bề ngang của trang giấy trong trường hợp tài liệu đó không được đặt đúng khi quét vào từ máy quét. Ước lượng độ nghiêng và phân tích sơ đồ trình bày của văn bản sẽ được mô tả ngắn gọn trong phần dưới đây. Phương pháp nhận dạng ký tự quang học sẽ được đề cập đến ở phần sau. 2.6.1. Xác định góc nghiêng của văn bản Một dòng văn bản bao gồm một nhóm các ký tự, biểu tượng và các từ nằm liền kề nhau, khá gần nhau và đều nằm trên cùng một đường thẳng (có thể theo chiều thẳng đứng hay chiều dọc). Thông thường hướng của các dòng văn bản sẽ xác định độ nghiêng của tài liệu. Bình thường một trang tài liệu sẽ có độ nghiêng là 0 khi mà các dòng văn bản theo chiều ngang hay chiều dọc sẽ song song với các cạnh tương ứng của trang tài liệu, tuy nhiên trong một số trường hợp khi một trang tài liệu được quét hay sao chụp bằng tay, độ nghiêng của tài liệu khi đó sẽ khác 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 Hình 2.6 Văn bản bị nghiêng sau khi được quét qua máy quét. Hình 2.6 cho ví dụ về một văn bản nghiêng sau khi quét ảnh gốc qua một máy scan . Vì các bước phân tích như OCR hay phân tích sơ đồ trình bày phụ thuộc vào trang tài liệu đầu vào với độ nghiêng là 0 do đó xác định độ nghiêng và điều chỉnh độ nghiêng của tài liệu là một việc làm cần thiết trước khi thực hiện những bước trên. Một phương pháp xác định độ nghiêng của tài liệu phổ biến đó là phép chiếu nghiêng. Phép chiếu nghiêng là phương pháp tính số lượng điểm ảnh ON (điểm ảnh có giá trị 1 trong ảnh nhị phân) khi quét ảnh theo các dòng hay các cột và lưu giá trị này vào một mảng, trong đó chỉ số của mảng chính là dòng hay cột được quét. Do đó giá trị các điểm ảnh ON khi quét qua trang ảnh sẽ được biểu diễn bởi một đồ thị tần suất. Mỗi một lần thực hiện phép chiếu nghiêng ta sẽ chiếu ảnh theo các góc khác nhau (từ 0 đến 180 độ), tức là sẽ thực hiện quay ảnh một góc tương ứng. Phép chiếu nghiêng thường được thực hiện theo chiều ngang hoặc dọc và được gọi là các phép chiếu nghiêng theo chiều ngang, dọc tương ứng. Với một tài liệu ảnh mà góc nghiêng bằng 0 thì các đỉnh của phép chiếu biểu diễn các dòng có chứa ký tự, còn các vùng trũng biểu diễn cho khoảng không gian trắng giữa các dòng. Để tìm được góc nghiêng của văn bản thì sẽ tìm góc quay sao cho đồ thì tần suất có nhiều những đỉnh cao nhất và những vùng trũng nhất. Nếu đồ thị tần suất có 10 đỉnh và 10 vùng trũng thì có thể suy ra rằng tài liệu ảnh có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 10 dòng văn bản. Do đó với mỗi phép chiếu nghiêng ta sẽ tính số đo độ cao của các đỉnh và số đo độ cao các vùng trũng, góc chiếu nào mà có sự khác nhau giữa hai số đo này là lớn nhất thì chính là góc nghiêng của văn bản. 2.6.2. Phân tích bố cục của trang tà i liệu ảnh Sau khi xác định được góc nghiêng của trang tài liệu , ảnh sẽ được quay một góc để độ nghiêng của trang bằng 0, sau đó quá trình phân tích bố cục của trang tài liệu được thực hiện . Phân tích bố cục trang được thực hiện để lấy ra được cấu trúc các khối văn bản (các đoạn văn bản) trong tài liệu. Tuỳ thuộc vào định dạng của từng loại tài liệu, quá trình phân đoạn có thể thực hiện phân tách các từ, các dòng văn bản hay cấu trúc các khối (nhóm các dòng văn bản, chẳng hạn các đoạn văn bản hay các bảng danh mục). Thông thường người ta dựa vào quy tắc sắp xếp thông tin trong trang tài liệu để nhận dạng từng khối và gán nhãn cho chúng. Một thí dụ đưa ra kết quả sau khi phân tích trang đầu tiên của một tài liệu kỹ thuật bao gồm: tên tài liệu, tác giả, tóm tắt, từ khoá, các đoạn trong thân văn bản...v.v. Hình 2.7 đưa ra một thí dụ với kết quả sau khi đã thực hiện phân tích cấu trúc và gán nhãn cho các khối trên một trang tài liệu ảnh. Phân tích cấu trúc của trang có thể sử dụng phương pháp tiếp cận trên - xuống [11] hay tiếp cận dưới – lên[10]. Với phương pháp tiếp cận từ trên - xuống, một trang tài liệu được phân tách từ các thành phần lớn xuống các thành phần nhỏ hơn, chẳng hạn trang tài liệu có thể phân tách thành các cột, sau đó các cột được phân tách thành các đoạn văn bản, từ các đoạn văn bản lại tách ra thành các dòng văn bản, sau đó tách các từ .v.v.. Với phương pháp tiếp cận từ dưới – lên, các thành phần liên thông được trộn với các ký tự để nhận dạng từ, các từ lại được trộn với nhau để tạo thành các dòng văn bản, từ các dòng văn bản xây dựng thành các đoạn văn bản.v.v... Một cách lần lượt, hai phương pháp trên có thể kết hợp cùng nhau để phân tích cấu trúc của tài liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 Hình 2.7 Ví dụ minh họa kết quả phân tích bố cục của trang tài liệu ảnh 2.7. Nhận dạng ký tự quang học (OCR) Như chúng ta đã biết trên thế giới có nhiều kiểu chữ khác nhau , mặt khác c ác ký tự trong một bảng chữ cái thường có rất nhiều kiểu viết khác nhau. Trên thực tế các ký tự thường được viết bằng nhiều kiểu khác nhau tuỳ thuộc vào kích cỡ, loại phông chữ và nét bút viết tay của từng người. Mặc dù các ký tự có thể viết theo nhiều cách nhưng chúng vẫn có những quy tắc xác định để nhận biết từng ký tự. Phát triển những thuật toán trên máy tính để nhận biết các ký tự trong bảng chữ cái là một nhiệm vụ trọng tâm của OCR. Nhưng thách thức đối với vấn đề này đó là – trong khi con người có thể nhận dạng gần như chính xác 100% các ký tự viết tay thì OCR vẫn chưa thể đạt tới được điều này. Khó khăn đối với OCR thể hiện qua một số đặc điểm. Sự gia tăng số lượng và kích cỡ của phông chữ trong bảng chữ cái, không ràng buộc các kiểu chữ viết tay, các ký tự nối liền nhau, các nét bị đứt, các điểm nhiễu v.v... Tất cả chúng làm cho quá trình nhận dạng gặp khó khăn. Hình 2.8 chỉ ra một thí dụ giữa số „0‟ và số „6‟ rất dễ nhầm lẫn khi chúng được viết bằng tay. Một từ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 cũng có thể hoàn toàn là các con số, chẳng hạn các số điện thoại, hay hoàn toàn là các ký tự trong bảng chữ cái hoặc có thể trộn lẫn giữa chữ cái và số. Hình 2.8 Chữ viết tay có thể gây nhầm lẫn 2.7.1. Thuật toán OCR Thuật toán OCR thường có hai phần chính: trích chọn đặc trưng và phân loại. Một cách cơ bản, quá trình OCR gán một ảnh ký tự vào một lớp bằng cách sử dụng thuật toán phân loại dựa trên những đặc trưng được trích chọn và mối liên hệ giữa các đặc trưng đó. Độ đo tương tự là cơ sở để xác định một đối tượng có thuộc một lớp ký tự hay không. Thông thường sẽ có một thành phần thứ ba đó là quá trình xử lý dựa trên ngữ cảnh để sửa lại những lỗi của OCR. Dưới đây sẽ trình bày ngắn gọn ba thành phần của OCR. 2.7.1.1. Trích chọn đặc trƣng Trích chọn đặc trưng liên quan đến việc trích ra những thuộc tính của đối tượng dưới dạng các độ đo. Để biểu diễn một lớp ký tự phải xây dựng một mô hình nguyên mẫu chung cho các lớp ký tự. Và do đó quá trình trích chọn đặc trưng sẽ cố gắng tìm ra các thuộc tính dựa trên nguyên mẫu đã xây dựng cho các lớp. Các đặc trưng chung như, số lượng các lỗ hổng trong ký tự, mặt lõm của đường viền bên ngoài, sự nhô ra của điểm cao nhất và các đặc trưng nội tại, các điểm cắt ngang, các điểm kết thúc, các góc .v.v... sẽ được sử dụng. Mỗi ảnh ký tự sẽ trích ra các đặc trưng trên và phân loại chúng vào lớp tương ứng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 2.7.1.2. Phân loại Trong phương pháp phân loại dựa trên thống kê, những mẫu ảnh ký tự được biểu diễn bằng các điểm trong không gian đặc trưng đa chiều. Mỗi một thành phần trong không gian đa chiều biểu diễn cho một độ đo đặc trưng. Quá trình phân loại sẽ chia không gian đa chiều thành các vùng tương ứng với các lớp ký tự và chúng được gán nhãn tương ứng. 2.7.2. Nhận dạng ký tự dựa trên ngữ cảnh Nhận dạng ký tự dựa trên ngữ cảnh sử dụng thông tin từ các ký tự khác nhau được nhận dạng trong một từ và dựa vào ý nghĩa của từ khi lắp ghép ký tự vào từ. Thông thường một từ có nghĩa hay không sẽ dựa vào từ điển hay từ vựng của ngôn ngữ đó. Giả sử giữa hai từ u và v rất khó phân biệt khi nhận dạng, chẳng hạn một trong hai từ này xuất hiện tại vị trí thứ hai (tính từ trái sang phải) của từ qXeen. Kỹ thuật xử lý dựa trên ngữ cảnh sẽ xác định ký tự u là thích hợp trong trường hợp này vì trong từ điển từ qveen không có trong từ điển Tiếng Anh. Chúng ta cũng có thể áp dụng quy tắc ký tự đi theo sau ký tự q chỉ có u. Đã có những nghiên cứu một cách hệ thống kết quả nhận dạng thu được từ OCR trên Tiếng Anh. Một báo cáo đầy đủ kết quả từ những sản phẩm OCR trên tài liệu được in bằng máy được công bố bởi trường đại học Nevada [9]. Với những tài liệu đạt tiêu chuẩn, kết quả nhận dạng chính xác từ 99.13% tới 99.77%. Với những tài liệu có chất lượng kém, độ chính xác của nhận dạng cũng đạt từ 89.34% tới 97.01%. Kết quả nhận dạng giảm đi đối với những tài liệu chất lượng kém chủ yếu là do các nét ký tự bị đứt và các ký tự liền kề nối liền nét. Đã có rất nhiều tài liệu nghiên cứu mô tả phương pháp nhận dạng OCR. OCR được coi là nghiên cứu quan trọng nhất trong lĩnh vực nhận dạng. Trong khi các nghiên cứu phương pháp OCR trên ký tự La mã đã giảm dần Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 thì nghiên cứu OCR trên các loại ký tự không phải La mã tiếp tục là vấn đề được quan tâm nhiều đến. 2.8. Phân tích các đối tƣợng ảnh trong tài liệu Trong phân tích trang tài liệu ảnh thì n hận dạng đối tượng ảnh là một trong hai chủ đề quan vì các thành phần của ảnh luôn đi kèm với văn bản, các sơ đồ biểu diễn, lôgô của công ty xuất hiện trong đầu thư, và các đường kẻ phân cách các ô trong bảng. Các đối tượng ảnh được nhận dạng là các ảnh xuất hiện dọc theo các đoạn văn bản và ảnh trong tài liệu. Chúng ta cũng có thể xây dựng những miền ứng dụng riêng biệt để nhận dạng từng loại đối tượng ảnh trong tài liệu; chúng có thể bao gồm các biểu tượng trong sơ đồ kỹ thuật, biểu đồ nghiệp vụ, bản đồ, vân tay .v.v… Mục đích của việc nhận dạng ảnh là lấy ra được các thông tin mang ý nghĩa xuất hiện bên trong nội dung của ảnh. Phân tích tài liệu ảnh càng trở nên quan trọng hơn khi mà tài liệu hầu như được tạo ra và xử lý bằng máy tính thì việc Những người làm việc trên máy tính liên quan đến việc truyền tải và chuyển đổi tệp dữ liệu nhận thấy một điều rằng các tệp dữ liệu thường ít khi tương thích với nhau. Bởi vì có sự khác nhau về ngôn ngữ, đặc điểm của hệ thống, và sự thay đổi của các phiên bản CAD và các gói định dạng văn bản, do đó các tệp dữ liệu của những hệ thống khác nhau thường không tương thích với nhau. Một hệ thống xử lý tài liệu có thể chuyển đổi một định dạng tài liệu ảnh kỹ thuật này sang định dạng khác, nhưng mục đích của hệ thống cũng phải có khả năng chuyển đổi được những tài liệu ảnh vẽ bằng tay. Điều này cũng giống như việc nhận dạng chữ viết tay và văn bản trong OCR. Khi máy tính có khả năng phân tích được những hình vẽ tay phức tạp một cách nhanh chóng và chính xác thì vấn đề nhận dạng ảnh sẽ được giải quyết, tuy nhiên để đến khi đạt được điều đó thì vẫn còn nhiều cơ hội và thách thức đối với lĩnh vực nghiên cứu này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Trong các bước xử lý đối tượng ảnh có những bước xứ lý chung cũng giống như đối với nhận dạng văn bản. Các phương pháp tiền xử lý, phân đoạn, và trích chọn đặc trưng được mô tả trước đây sẽ được thực hiện trước tiên. Thuật toán phân đoạn khởi tạo thường để áp dụng cho tài liệu có lẫn đối tượng văn bản và ảnh nhằm tách riêng thành hai phần văn bản và ảnh. Hầu hết các hệ thống OCR thương mại có khả năng nhận dạng các đường biên dài và đường kẻ trong bảng khác so với cách nhận dạng ký tự, do đó việc cố gắng nhận dạng các đối tượng đó như là ký tự không xảy ra. Hệ phân tích ảnh cho các bản vẽ kỹ thuật phải phân biệt được đâu là văn bản và đâu là ảnh. Thông thường các hệ thống đều có khả năng nhận dạng tốt các đối tượng ảnh ngoại trừ một số trường hợp đặc biệt chẳng hạn khi ký tự nối liền với các hình vẽ gây ra nhầm lẫn đây là một đối tượng ảnh; hay có những biểu tượng qua nhỏ và được coi như là một ký tự. Tách đoạn và phân tích ảnh màu với nhiều lớp của bản đồ, nhận dạng đối tượng ảnh ba chiều trong ảnh kỹ thuật, và những bản vẽ kiến trúc 3 – D là những thí dụ cho thấy còn nhiều thách thức đối với những người làm nghiên cứu trong lĩnh vực nhận dạng. Rõ ràng rằng rất nhiều miền ứng dụng phụ thuộc tri thức cũng được áp dụng vào trong tất cả những hệ thống nhận dạng, phân tích ảnh. Hệ phân tích tài liệu ảnh và các thành phần chung đã được mô tả tổng quan trong chương này . Trong đó đã trình bày các bước chính trong quá trình xử lý ảnh từ khi thu nhận ảnh đến khi trích ra được nhữn g thông tin người dùng mong muốn . Trong chương 3 sẽ mô tả chi tiết những thuật toán nhận dạng đối tượng ảnh dựa vào thành phần liên thông trong tài liệu có lẫn ảnh và văn bản. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 CHƢƠNG 3 THUẬT TOÁN TÁCH VĂN BẢN - ẢNH TỪ TRANG TÀI LIỆU ẢNH 3.1. Tổng quan về phân tách văn bản – ảnh Như chúng ta đã biết một trang tài liệu ảnh thường chứa đựng các thông tin hỗn hợp như các đoạn văn bản và ảnh, chẳng hạn như các trang báo được quét, bản đồ hay các tài liệu được quét từ máy quét. Do đó để lấy ra được phần chứa đựng thông tin và phần chứa ảnh riêng rẽ và chính xác cần có các kỹ thuật xử lý phức tạp. Các thuật toán tách văn bản - ảnh giúp chúng ta lấy ra được các thông tin như vậy. Một thuật toán tách văn bản - ảnh sẽ phân tách tài liệu thành hai lớp: lớp chứa văn bản và lớp chứa các đối tượng ảnh. Chương này sẽ trình khái quát về các phương pháp tách văn bản - ảnh và trình bày một thuật toán phân tách văn bản - ảnh hiệu quả. Tư tưởng cơ bản của thuật toán là trước tiên đi xác định các vùng không phải là văn bản và lưu giữ thông tin của vùng này vào lớp các đối tượng ảnh. Các vùng còn lại sẽ thuộc lớp văn bản. Cách làm như vậy sẽ hiệu quả hơn là trước tiên đi xác định trực tiếp các vùng văn bản. Trong một hệ thống nhận dạng tài liệu, một tài liệu thường chứa nhiều loại biểu tượng (các kiểu ký tự, ảnh) thông tin khác nhau. Chính vì có sự khác nhau lớn giữa các đặc trưng của từng loại biểu tượng mà chúng sẽ được xử lý theo từng kỹ thuật khác nhau. Hơn thế nữa, những yêu cầu cao đối với các kỹ thuật xử lý ảnh như các phép véc tơ hóa đối tượng ảnh, nhận dạng các loại ký tự Tiếng Anh, ký tự số, ký tự Trung Hoa đòi hỏi phải được nghiên cứu dựa theo những cách thức khác nhau. Chính vì những lý do đó tách các thành phần văn bản và ảnh từ những tệp tài liệu ảnh là một yêu cầu cần thiết đối với máy tính. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Có rất nhiều phương pháp tách văn bản và ảnh từ trang tài liệu ảnh được công bố trước đây. Phương pháp được đưa ra trong tài liệu [3] dựa trên khái niệm, đối tượng văn bản bao giờ cũng có kích thước nhỏ hơn đối tượng ảnh, quá trình tách văn bản và ảnh được thực hiện sau khi đã làm mảnh các đối tượng. Phương pháp trên khá đơn giản nhưng nó sẽ không hiệu quả khi một ký tự tiếp xúc với một ký tự khác hay một đối tượng ảnh khác. Yamada [6] giới thiệu một phương pháp tách các đối tượng từ bản đồ địa hình, trong đó phương pháp có thể tách ra các đối tượng là đường đi và các toà nhà, phần còn lại của bản đồ là các đối tượng văn bản. Một trong những phương pháp được biết đến nhiều nhất là của Wong, Casey và Wahl [7], được điều chỉnh và cải tiến trong [2] Tuy nhiên, một số chứng minh cho thấy phương pháp trên chỉ hoạt động hiệu quả trên các tệp tài liệu chứa nhiều văn bản, ngược lại trên các tài liệu ảnh chứa nhiều các đối tượng ảnh thì phương pháp không hiệu quả. Một vài phương pháp dựa trên các khoảng trắng [15]. Phương pháp được biết đến là hoạt động hiệu quả nhất trong kỹ thuật tách văn bản - ảnh được đưa ra trong [4]. Phương pháp này dựa trên việc phân tích các thành phần liên thông và dựa vào phép biến đổi Hough để nhóm các thành phần trong cùng một chuỗi ký tự và tách chúng ra khỏi các đối tượng ảnh. Phương pháp hoạt động hiệu quả trên cả những thay đổi kiểu phông chữ, kích cỡ phông chữ và hướng văn bản. Tất cả các phương pháp được giới thiệu ở trên hoạt động dựa trên các trang tài liệu ảnh thỏa mãn các yêu cầu sau: - Tài liệu ảnh phải không có các thành phần nhiễu và chúng phải được xử lý để chuẩn hoá một số điều kiện trước khi thực hiện thuật toán. - Các chuỗi ký tự trong tài liệu ảnh phải không tiếp xúc với đối tượng ảnh. Hướng của các chuỗi ký tự thường được nhận dạng theo chiều ngang hay Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 chiều dọc. Trong trường hợp chuỗi ký tự có hướng khác việc nhận dạng sẽ khó hơn. - Văn bản phải không chứa các kiểu ký tự Trung Hoa [16]. Tuy nhiên những điều kiện, yêu cầu đối với tài liệu được nhận dạng ở trên đã làm hạn chế việc nhận dạng một số lượng lớn tài liệu của một số ứng dụng. Chẳng hạn trong ứng dụng CAD/CAM, nó sẽ chuyển một số lượng lớn tài liệu ảnh trên giấy sang định dạng của CAD/CAM. Tuy nhiên những loại tài liệu ảnh vẽ này lại có một số lượng lớn thành phần nhiễu, có các ký tự tiếp xúc với ký tự và ký tự tiếp xúc với các đối tượng ảnh. Mặc dù có một số thao tác xử lý những vấn đề này nhưng chúng vẫn gặp phải một số hạn chế đó là vấn đề thời gian. Trong các phương pháp phân tách văn bản và ảnh trong tài liệu ảnh, có thể chia thành ba loại phương pháp cơ bản sau: 1. Sử dụng các phép biến đổi hình thái để lọc ra các đối tượng tuyến tính, chẳng hạn các hình vẽ và sau đó tách những đối tượng này ra khỏi tài liệu, những thành phần còn lại sẽ được coi là văn bản. Phương pháp này đặc biệt có hiệu quả đối với các tài liệu là các bản đồ đơn giản [5][14], tuy nhiên nó sẽ gặp phải khó khăn khi mà trong tài liệu có các hình vẽ phức tạp hơn. 2. Tương tự như vậy, một số khác lại đi tìm các đường kẻ để phân loại các đối tượng, dựa vào phép biến đổi véc tơ hoá [12] của tài liệu ảnh. 3. Phương pháp thứ 3 được sử dụng nhiều nhất, dựa trên việc phân tích các thành phần liên thông, và các thành phần liên thông này sẽ được lọc ra xem chúng thuộc lớp đối tượng nào (văn bản hay ảnh) dựa vào một số quy tắc xác định. Một trong những thuật toán nổi tiếng nhất dựa trên phương pháp này được đưa ra bởi Fletcher và Kasturi [4]. Thuật toán này đã chứng minh rằng nó có khả năng phân tách tốt hai lớp đối tượng, ngay cả khi tài liệu chứa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 các đối tượng phức tạp. Tuy nhiên thuật toán này vẫn chưa có khả năng phân loại trực tiếp đối tượng văn bản tiếp xúc với đối tượng ảnh. Một thuật toán phân tách văn bản - ảnh trên những tài liệu ảnh vẽ kỹ thuật dựa trên quy tắc sẽ được trình bày trong chương này. Thuật toán phân tách này dựa trên tư tưởng phương pháp phân tách thứ 3, tức là đi phân tích các thành phần liên thông và dựa vào phân tích các đặc trưng khác nhau của các đối tượng văn bản và ảnh. Chiến lược của thuật toán này đó là cố gắng đi tìm càng nhiều càng tốt các vùng đối tượng ảnh và lưu trữ thông tin của chúng, cách làm này hiệu quả hơn là đi tìm trực tiếp các vùng đối tượng văn bản trước. Thuật toán này có khả năng phân tách được các đối tượng văn bản bao gồm các ký tự Trung Hoa, ký tự Phương Tây, ký hiệu đặc biệt từ loại tài liệu ảnh có chứa hỗn hợp văn bản và ảnh một cách khá hiệu quả. Thuật toán cũng có một số hạn chế trong việc nhận dạng một số loại tài liệu ảnh và một số mức độ nhiễu và tuy nhiên nó có khả năng phân tách đối tượng văn bản tiếp xúc với đối tượng ảnh và không phụ thuộc vào kích cỡ kiểu ký tự. Hướng của chuỗi ký tự cũng sẽ được đánh giá. Quá trình làm mảnh ảnh có thể dẫn đến mất thông tin, thuật toán sẽ xử lý ở mức điểm ảnh trước khi quá trình làm mảnh và véc tơ hoá được thực hiện, chính vì vậy mà hai lớp đối tượng ảnh sẽ được lưu lại: một lớp chứa các đối tượng văn bản và lớp kia chứa các đối tượng ảnh. Các loại đối tượng này sẽ được nhận dạng sau đó bằng những hệ thống nhận dạng thích hợp. Tiếp theo luận văn sẽ trìn h bày chi tiết các bước thực hiện của thuật toán: Những đặc trưng chung của một tài liệu ảnh, mô tả các bước để xác định các đối tượng ảnh và tách chúng ra khỏi đối tượng văn bản. 3.2. Những đặc trƣng chung của một tệp tài liệu ảnh Đối tượng chủ yếu của tài liệu ảnh là văn bản và ảnh nhưng làm để phân biệt được hai đối tượng trên máy tính đặc biệt là đối với ảnh nhị phân Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 bởi vì cả hai đối tượng đều được biểu diễn bởi các con số 0 và 1 trong ảnh nhị phân. Do đó việc phân biệt được sự khác nhau giữa hai loại đối tượng này sẽ dựa vào phán đoán chủ quan và thống kê. Mặc dù máy tính sẽ rất khó để phân biệt sự khác nhau giống, nhưng chúng ta sẽ dễ dàng phân biệt chúng nếu dựa vào những điều kiện sau: - Văn bản – các biểu tượng hay chuỗi ký tự bao gồm các ký tự, các từ, ký tự số, ký tự Trung Hoa (hoặc ngôn ngữ khác) hoặc các ký tự đặc biệt. - Ảnh – các thành phần không chứa các ký tự, bao gồm tất cả các loại đường thẳng, đường cong, hay các bức ảnh, sơ đồ, .v.v.. Dựa trên những định nghĩa cơ bản của hai loại đối tượng văn bản và ảnh ở trên, chúng ta có thể nhận biết được những đặc trưng khác nhau giữa hình bao của vùng văn bản và ảnh được liệt kê dưới đây: - Kích cỡ của ký tự văn bản bao giờ cũng nhỏ hơn nhiều kích cỡ của các đối tượng ảnh. Tỉ lệ kích cỡ hình bao của văn bản thường nhỏ. Chẳng hạn với kiểu chữ Tahoma – 20 có tỉ lệ trung bình của chiều rộng/chiều cao là vào khoảng 2:3. - Các ký tự văn bản thường nằm trong một chuỗi ký tự. Khoảng cách giữa các ký tự trong một từ hay khoảng cách giữa các từ thường là nhỏ và thường theo những quy tắc nhất định. Hướng của chuỗi ký tự thường là theo chiều ngang, chiều dọc hoặc là nghiêng một góc 45 độ. - Độ đậm của nét chữ trong vùng chuỗi văn bản bao giờ cũng lớn hơn so với độ đậm của vùng ảnh. - Độ dài của các thành phần tuyến tính trong nét bút của chuỗi ký tự thường ngắn hơn so với các đối tượng ảnh, chẳng hạn như một đường kẻ dài hiếm khi xuất hiện trong nét bút của chuỗi ký tự. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Trên thực tế mỗi đặc trưng được đưa ra ở trên cũng có một số ngoại lệ xảy ra. Tuy nhiên ở trên là bốn đặc trưng chung nhất của các đối tượng văn bản và ảnh. Hình 3.1 Ví dụ về các đối tượng văn bản và đối tượng ảnh Hình 3.1 bao gồm hai loại kiểu ký tự: ký tự Trung Hoa và ký tự Tiếng Anh và hình ảnh là một phần của bảng vẽ kỹ thuật . Hình 3.2 biểu diễn tần số xuất hiện của các điểm ảnh giao nhau màu đen và màu trắng khi đường thẳng cắt ngang qua các đối tượng. Nhìn trên Hình 3.2 sự thay đổi tần số của các nét bút trong văn bản thường cao hơn so với đối tượng ảnh. Hình 3.2 Biểu diễn các điểm ảnh giao nhau Hình 3.3 chỉ ra một số trường hợp ngoại lệ. Hình 3.3a đưa ra một bức ảnh nhỏ và nhìn giống như một ký tự. Hình 3.3b là một ký tự Trung Hoa rất khó phân biệt so với các đối tượng ảnh, đặc biệt khi ký tự này tiếp xúc với các đối tượng ảnh. Hình 3.3c là một đối tượng ảnh có LSD cao. Những ngoại lệ a b c d Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 trên là những nguyên nhân chính dẫn đến sự nhận dạng và phân tách sai các đối tượng trong các kết quả thí nghiệm được đưa ra dưới đây. Hình 3.3 Một số trường hợp ngoại lệ 3.3. Thuật toán phân tách văn bản - ảnh Phần này sẽ trình bày thuật toán phân tách văn bản - ảnh dựa trên một số quy tắc để xác định các đối tượng ảnh [16], lưu giữ thông tin của chúng và từ đó xác định được các đối tượng văn bản. Các bước thực hiện chính của thuật toán được tóm tắt trong Hình 3.4 như sau: Hình 3.4 Sơ đồ thuật toán phân tách văn bản Xác định các thành phần tuyến tính, lƣu giữ thông tin của chúng, bao gồm các đƣờng thẳng dài hay các đƣờng thẳng ngắn Xác định các nét bút không phải là văn bản, lƣu giữ thông tin các đối tƣợng này, dựa vào việc phân tích nét bút của các thành phần liên thông Kết hợp các nét bút trong một chuỗi, xác định các đối tƣợng không phải là văn bản dựa vào thành phần liên thông mới sau khi đã thực hiện một số phép toán hình thái. Trích ra thông tin từ các vùng bao chuỗi văn bản dựa vào hình chữ nhật giới hạn của các chuỗi trong ảnh ban đầu. Lấy ra các đối tƣợng ảnh từ lớp đối tƣợng ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 3.3.1. Xoá bỏ các đối tƣợng tuyến tính Theo như đặc trưng 4 trong phần 3.2 các thành phần tuyến tính của ảnh thường được xác định trước. Khái niệm thành phần tuyến tính (LC) để ám chỉ đến các đối tượng có nét bút là các điểm ảnh đen nằm liên tiếp khi đi theo một hướng nhất định. Trong phần này, thuật toán sẽ duyệt từ trên xuống dưới quét theo từng hàng để tìm các thành phần LC, một LC sẽ được xác định là một đối tượng ảnh khi mà độ dài của nó lớn hơn một tham số T1 được đặt trước. Cũng làm tương tự như vậy nhưng sẽ quét theo chiều thẳng đứng từ trái sang phải để tìm những thành phần LC. Các thành phần LC có góc nghiêng là ±22.5, ±45, ±67.5 cũng sẽ được xác định. Tất cả các đối tượng LC được xác định không phải là văn bản sẽ được đưa vào lớp các đối tượng ảnh. Trường hợp hình chữ nhật bao của đối tượng văn bản có chiều rộng hẹp xấp xỉ một điểm ảnh thì đối tượng đó được cho là một đường kẻ thẳng đứng hay ngang có độ rộng là 1 điểm ảnh và chúng được coi như là một đối tượng ảnh. Do đó phần lớn các điểm nhiễu (dấu chấm câu) hay các LC ngắn (dấu gạch ngang, gạch nối) sẽ bị coi là những đối tượng ảnh. Nếu các đối tượng đường thẳng không phải là các đường kẻ ngang hoặc đường kẻ dọc sẽ được minh họa trong Hình 3.5 dưới đây thì m ột phép toán kéo giãn đơn giản (tương đương với phép quay một góc α) sẽ được thực hiện trên các đối tượng đường thẳng này. Hình 3.5 Nhận dạng đường kẻ nghiêng với phép toán kéo dãn Với một điểm ảnh có toạ độ (i, j) ta tính giá trị B = (tgα*j) trong đó α là góc nghiêng của đường thẳng so với mặt phẳng ngang. Khi đó điểm ảnh có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 toạ độ (i, j) sẽ được di chuyển tới toạ độ (i+B, j). Hình 3.5 b là kết quả của phép kéo giãn Hình 3.5 a khi góc α = 22.5 độ.Hình 3.5c với góc α = 45 độ. Hình 3.5d với góc α = 67.5 độ. Rõ ràng rằng đường kẻ có góc nghiêng 22.5 trên Hình 3.5a sẽ chuyển thành đường kẻ ngang trên Hình 3.5 b. Sau khi thực hiện phép kéo giãn ta có thể thực hiện quét từng dòng để xác định các đường kẻ ngang. Tham số để xác định xem đường thẳng có là một đối tượng ảnh hay không khi đó sẽ là T1*cosα, bởi vì sau khi thực hiện phép kéo giãn độ dài của đường thẳng sẽ thay đổi. Cuối cùng là thực hiện phép kéo giãn ngược lại để khởi tạo lại ảnh ban đầu với góc nghiêng là góc đối của phép kéo giãn vừa thực hiện. Hai phép biến đổi trên không làm mất thông tin của ảnh mà chỉ tìm được những đường thẳng thích hợp để xác định chúng là các đối tượng ảnh. Nếu như một bức ảnh được số hoá chính xác thì phần lớn đường kẻ nằm ngang hoặc nằm thẳng đứng với góc nghiêng là 0 hay 90 độ, hay nghiêng một góc 45 độ. Do đó phần lớn các đường kẻ sẽ được xác định một cách đơn giản chứ không cần phải thực hiện phép biến đổi như ở trên, điều đó sẽ giúp nâng cao tốc độ xử lý của hệ nhận dạng. 3.3.2. Phân tích các thành phần liên thông của nét bút Khi đã xác định được các thành phần tuyến tính là các đối tượng ảnh ở bước trên thì tài liệu vẫn còn các đối tượng ảnh, là những đối tượng có kích thước khác biệt. Chúng ta sẽ xem xét từng thành phần liên thông bắt gặp khi quét toàn bộ ảnh theo từng dòng. “Thành phần liên thông” (CCs) [4] nghĩa là các điểm ảnh màu đen thuộc về một vùng giới hạn liên thông tám, trong đó mỗi điểm ảnh đen sẽ liên thông tám với một điểm ảnh đen khác trong vùng giới hạn. Trong CCs các điểm ảnh liên thông tám có thể thuộc về đối tượng văn bản hay đối tượng ảnh và nằm trong vùng giới hạn hình chữ nhật. Mỗi một hình bao chữ nhật sẽ là một thành phần CCs. Một thành phần CCs sẽ nắm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 giữ các thông tin sau: toạ độ nhỏ nhất và lớn nhất của hình chữ nhật, số lượng điểm ảnh màu đen. Phương pháp phân tích CCs như sau 1. Thành phần CCs được tạo ra sau khi đã xác định được các thành phần LC và xoá chúng khỏi tài liệu. 2. Thứ hai là chúng ta sẽ sử dụng thông tin độ đậm đặc của CCs để xác định các đối tượng ảnh. Ngay khi CCs được xác định là một đối tượng ảnh, chúng sẽ được đưa vào lớp đối tượng ảnh và xoá chúng khỏi tài liệu ảnh, khi đó tài liệu ảnh chỉ bao gồm các đối tượng văn bản. Các thành phần liên thông – CCs được tạo ra nhờ sử dụng phương pháp tách cạnh, toạ độ các điểm ảnh của vùng bao giới hạn của một CCs được ký hiệu là (Xi, Yi), i = 1, 2, 3, .., n, trong đó n là tổng số điểm ảnh bao vùng giới hạn. Các thông số quan trọng sau sẽ được tính toán: 1) MaxBox, biểu diễn toạ độ lớn nhất và nhỏ nhất hình bao chữ nhật của CCs 2) WBRatio, biểu diễn độ đậm đặc của các điểm ảnh đen trong vùng giới hạn của MaxBox. 3) HWRatio biểu diễn tỉ lệ giữa hai chiều của vùng giới hạn MaxBox. Nếu HWRatio < 1 thì đặt HWRatio = 1 / HWRatio. Khi đó CCs sẽ được coi là một đối tượng ảnh nếu các thông số trên thoả mãn 1 trong các điều kiện sau: A) WBRatio ≤ T2, B) HWRatio ≥ T3, hoặc C) Độ dài của cạnh dài hơn của MaxBox ≤ T4. Trong đó T2, T3 và T4 là các tham số được thiết lập trước giống như T1. Điều kiện A để xác định các đường kẻ mà có góc nghiêng không nằm trong các trường hợp 0, ±22.5, ±45, ±67.5 hay ±90, bởi vì số lượng các điểm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 ảnh trắng trong MaxBox của các đường kẻ nghiêng sẽ nhiều hơn so với CCs của văn bản. Hơn thế nữa điều kiện A còn để xác định các hình có kích thước lớn và có WBRatio nhỏ. Sử dụng điều kiện B để xác định các hình dài nhưng có bề rộng nhỏ. Sử dụng điều kiện C để xác định các đối tượng ảnh mà nhỏ hơn cả ký tự văn bản, chẳng hạn các điểm nhiễu. Sau bước này, một số lượng lớn các đối tượng ảnh sẽ được xác định. Tuy nhiên có một số thành phần của văn bản cũng bị xoá đi vì được xác định là đối tượng ảnh, chẳng hạn như dấu chấm câu (.), nét bút của một số ký tự Trung Hoa, dấu chấm trên chữ cái i hay một số dấu trong kiểu chữ Tiếng Việt. Tuy nhiên dấu chấm rất giống như một điểm nhiễu, có thể khôi phục đối tượng này ở những bước xử lý sau nếu như nó nằm trong môi trường văn bản. Việc mất một số nét của ký tự Trung Hoa cũng sẽ được giải quyết ở một số bước sau. Để không làm mất dấu của ký tự Tiếng Việt cần điều chỉnh tham số T4 thích hợp để không loại bỏ dấu của Tiếng Việt. 3.3.3. Kết hợp các nét ký tự tạo thành các chuỗi văn bản Trong đặc trưng thứ 2 của phần 3.2 độ dài của khoảng trắng giữa các ký tự hay giữa các từ thường là nhỏ, do đó chúng ta có thể nhóm chúng cùng với nhau. Nếu như khoảng cách giữa hai điểm ảnh màu đen là nhỏ, chẳng hạn như số lượng điểm ảnh trắng giữa chúng nhỏ hơn một tham số T5, chúng ta sẽ thay thế các điểm ảnh màu trắng giữa chúng là màu đen. Điều này giống như chúng ta dùng bút tô màu đen để tô lên các điểm ảnh trắng. Hướng của bút lông này là theo chiều ngang hoặc chiều dọc. Hình 3.6 chỉ ra một thí dụ về việc dùng bút để tô các điểm ảnh. Mục đích bước này là xây dụng các thành phần liên thông mới (NCCs) bằng việc kết hợp nét bút của các ký tự, NCCs được xây dựng dựa vào đặc trưng 2 của phần 3.2. Có thể tóm tắt lại mục đích của bước này như sau đây: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 1. Những dấu chấm (.), ký hiệu “-“, và một số nét bút bị xoá đi ở bước trước có thể khôi phục lại được. 2. Việc kết hợp các nét bút và các ký tự sẽ giúp dễ dạng nhận dạng vùng văn bản, bởi vì một chuỗi văn bản được kết hợp tạo thành NCCs sẽ thể hiện tính đặc trưng của văn bản rõ rảng hơn. 3. Thao tác dùng bút lông để tô những điểm ảnh thích hợp sẽ giúp phân tách các đối tượng ảnh một cách rõ ràng hơn và giúp các bước xử lý sau này dễ dàng phân tách hai đối tượng văn bản và ảnh. Hình 3.6 Dùng bút để tô các điểm ảnh thoả mãn (T5 = 12 với kích thước cỡ chữ là 20). 3.3.4. Thực hiện các phép toán hình thái Thực hiện các phép toán hình thái nhằm mục đích loại bỏ khả năng có thể xảy ra khi ký tự tiếp xúc với đối tượng ảnh hay các chuỗi ký tự tiếp xúc với nhau và sau đó xây dựng lại thành phần NCCs mới để cuối cùng phân tách chuỗi văn bản và ảnh. Quá trình này gồm hai thao tác : một thao tác co ảnh và một thao tác giãn ảnh. 3.3.5. Phân tích các thành phần liên thông mới Bước này thực hiện giống như bước 3.3.2 tuy nhiên nó sẽ làm việc với NCCs thay vì CCs như trong 3.3.2. Một cách tương tự, chúng ta sẽ duyệt qua tất cả các điểm biên của NCCs bằng cách quét ảnh theo từng dòng và lấy ra toạ độ của tất cả các điểm biên. Ba thông số quan trọng, MaxBox2, WBRatio2, HWRatio2 sẽ được tính. Thành phần NCCs sẽ được coi như là một đối tượng ảnh khi các thông số trên thoả mãn 1 trong những điều kiện sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36  WBRatio2 ≤ T6,  Độ dài của cạnh dài hơn trong MaxBox2 ≤ T7,  Độ dài của cạnh nhỏ hơn trong MaxBox2 ≤ T8, hay  Độ dài của cạnh nhỏ hơn trong MaxBox2 ≤ T7 và HWRatio2 ≥ T9 Trong đó T6, T7, T8 và T9 là các các tham số ngưỡng cho trước . Trong bước này hướng của chuỗi văn bản cũng sẽ được đánh giá. Trường hợp WBRatio2 không đủ cao, chúng ta sẽ tìm cách thu nhỏ lại hình chữ nhật bao của NCCs. Chính vì lý do đó, các điểm biên trong ảnh của NCCs sẽ được quay để tìm hình bao chữ nhật nhỏ nhất. Trong thuật toán này mỗi lần sẽ được quay 10 độ, vì vậy cần có 8 lần quay cho mỗi NCCs. Sau đó hình bao chữ nhật nhỏ nhất sẽ được quay ngược lại ngần ấy độ, kết quả là hình chữ nhật nghiêng sẽ là hình bao nhỏ nhất của NCCs và khi đó góc của hình chữ nhật nghiêng sẽ là hướng của chuỗi ký tự. Sau bước này, toàn bộ các đối tượng ảnh được nhận dạng sẽ được đưa vào lớp đối tượng ảnh. 3.3.6. Biểu diễn cấu trúc thông tin của các chuỗi văn bản Trong 3.3.5, khi một đối tượng NCCs được coi là một chuỗi ký tự, hình bao MaxBox2 sẽ được biểu diễn dưới cấu trúc sau: Char_Box { double Angle; int Coe;}, Trong đó Angle biểu diễn hướng của chuỗi ký tự. Khi Angle = 0, hình bao là hình chữ nhật và Coe biểu diễn toạ độ góc trên bên trái và góc dưới bên phải của hình bao. Khi Angle > 0, hình bao sẽ là một hình chữ nhật nghiêng và Coe biểu diễn toạ độ góc trên bên trái và góc dưới bên phải. Kết quả của bước này là trích ra được các thông tin từ vùng giới hạn chuỗi ký tự, cũng chính là ghi lại thông tin các vùng bao hình chữ nhật từ tài liệu ảnh ban đầu. Nếu dựa vào các thông tin này chúng ta lấy ra các vùng giới hạn của chuỗi ký tự từ ảnh baban đầu, phần còn lại của ảnh khi đó sẽ là các đối tượng ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Chương này đã trình bày một thuật toán phân tách văn bản và ảnh một cách hiệu quả. Thuật toán sẽ hoạt động tốt và hiệu quả ở một số khía cạnh sau: - Nó có thể phân tách ảnh và văn bản trong trường hợp 2 đối tượng này tiếp xúc với nhau, điều này dường như có thể rất khó với các thuật toán khác, chẳng hạn như [3]. - Có thể nhận dạng khá tốt các ký tự của Trung Hoa. - Việc xác định hướng của văn bản là rất dễ dàng. - Phần lớn các tham số đều được tính qua đại lượng Hav, đại lượng này cho phép có thể thay đổi được. Điều này giúp cho thuật toán khá là thuận tiện. Kết quả ảnh thu được của thuật toán cũng sẽ không bị ảnh hưởng lớn vào Hav khi mà giá trị Hav nằm trong một khoảng giá trị là độ cao trung bình của một ký tự. - Thuật toán cũng sẽ không bị ảnh hưởng khi ảnh có nhiều điểm nhiễu. Mặt khác cũng sẽ dễ dàng nhận thấy thuật toán cũng còn một số điểm hạn chế. Chúng ta có thể tóm tắt lại các loại lỗi mà thuật toán gặp phải như sau: - Khi mà độ đậm đặc của đối tượng ảnh quá cao hay độ đậm đặc của vùng văn bản thấp sẽ dẫn đến nhận dạng nhầm đối tượng ảnh là văn bản. - Một số ký hiệu văn bản đặc biệt như “.”, “1”, “l” hoặc “I” hay các đường kẻ gạch ngang thường cho kết quả không tin cậy. - Đối với sơ đồ có các hình mũi tên, thông thường thuật toán sẽ không chuyển được các hình mũi tên theo chiều ngang và chiều dọc. - Nếu hai chuỗi ký tự được đặt song song và đặt quá gần nhau, chúng có thể được nhóm lại như là một chuỗi ký tự. Bởi vì thuật toán sẽ sự dùng hình bao chữ nhật để trích ra các ký tự, vì vậy tất cả các thành phần nằm trong hình Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 bao sẽ được hiểu là một thành phần văn bản. Lỗi sẽ xảy ra khi có một vài thành phần của đối tượng ảnh nằm trong hình bao đó. Dù vẫn còn một số hạn chế trong việc nhận dạng một số đối tượng nhưng có thể khắc phục được vấn đề này dựa vào việc điều chỉnh tham số. Hơn thế nữa trong một số tình huống việc thực hiện chuyển tất cả các thành phần tuyến tính thoả mãn điều kiện sang thành đối tượng ảnh có thể để lại những điểm ảnh rời rạc thuộc đối tượng ảnh mà các bước thực hiện sau này không có khả năng nhận dạng chúng là đối tượng ảnh. Dựa trên sự phân tích những đặc trưng khác nhau của các đối tượng ảnh và văn bản, thuật toán sẽ điều chỉnh với những sự thay đổi về kiểu ký tự, kích thước ký tự, loại ảnh và hướng của chuỗi ký tự trong văn bản. Thuật toán có khả năng nhận dạng các ký tự Trung Hoa, ký tự Phương Tây, ký tự Tiếng Việt và một số ký hiệu đặc biệt khá thành công. Nó có một số hạn chế đối với ảnh có các cấp độ nhiễu khác nhau và có khả năng phân tách với trường hợp văn bản và ảnh tiếp xúc nhau. Nếu được cải tiến ở tốc độ xử lý và xây dựng cách tính tham số hợp lý thì thuật toán sẽ thích hợp trong việc sử dụng để viết những ứng dụng nhận dạng trong văn phòng như OCR, CAD/CAM. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 CHƢƠNG 4 PHƢƠNG PHÁP PHÂN TÍCH BẢNG T-RECS TRONG TRANG TÀI LIỆU ẢNH 4.1. Giới thiệu Hệ thống nhận dạng quang học (OCR) trước đây chỉ là những phép chuyển đổi đơn giản một tài liệu ảnh sang một tài liệu văn bản bao gồm các từ nhưng ngày nay hệ thống OCR đã tiến xa hơn trước , ngoài việc chuyển tài liệu ảnh sang tài liệu văn bản nó còn tập trung vào việc xác định đúng những cấu trúc đặc trưng trong tài liệu. Mục đích của những hệ thống nhận dạng cấu trúc không chỉ đơn giản là chuyển một tài liệu in thành một tài liệu điện tử mà hơn thế nữa còn là xây dựng những quá trình xử lý kết hợp chẳng hạn như: tự động chép nội dụng, đánh chỉ mục và phân loại [13]. Do đó việc quan trọng là kèm theo nội dung của tài liệu cũng phải trích chọn ra những cấu trúc đi kèm với từng nội dung đó. Khi đề cập đến vấn đề nhận dạng cấu trúc trong các tài liệu có chứa dữ liệu bảng biểu sẽ có hai hướng tiếp cận khác nhau: cách tiếp cận thứ nhất đó là xác định chính xác cấu trúc của bảng, bao gồm các ô trong bảng, cách này thường được gọi là phân đoạn hay nhận dạng cấu trúc. Cách thứ hai là dựa vào hình dạng bất kỳ của các khối đã được sắp xếp và đưa tập các đối tượng trong các khối về một cấu trúc bậc cao hơn. Quá trình này được gọi tên là gán nhãn lôgíc, phân tích cấu trúc hay phân tích bố cục trình bày trang.. Tìm hiểu những phương pháp nhận dạng cấu trúc bảng đã có trước đây đều cho thấy một điểm giống nhau, đó là các phương pháp này đều nhận dạng ra cấu trúc bảng bằng xác định ra các dấu hiệu phân cách, có thể là các khoảng trắng, các đường kẻ. Chẳng hạn như Rus và Summers [1] mô tả một Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 hệ nhận dạng cấu trúc bảng có khả năng xác định được bảng mà các cột cách nhau một khoảng hẹp sử dụng WDG. Trong khi đó một số phương pháp khác lại dựa vào độ rộng thích hợp của khoảng trắng giữa hai cột để nhận dạng [17]. Một số phương pháp khác xác định cấu trúc của bảng bằng quy tắc các đường kẻ. Một trong số đó là mô tả của Green và Krishnamoorthy [18], các ông đã áp dụng phân tích vị trí của các đường kẻ để đưa ra cấu trúc của bảng. Trong phương pháp sẽ trình bày dưới đây với tư tưởng là không xem xét đến bất cứ một loại đường phân cách nào để xác định bảng mà sẽ đi vào nhận biết các từ trong cùng một khối logic (chẳng hạn các từ trong cùng một cột dữ liệu sẽ được cho vào trong cùng một khối). Chúng ta sẽ không đi tìm những đặc trưng để phân biệt hai vùng dữ liệu (hai cột) khác nhau mà tìm những đặc trưng để tìm ra các từ trong cùng một khối logic và từ đó xây dựng cấu trúc riêng theo phương pháp tiếp cận dưới lên (bottom - up). Một điều dễ nhận thấy ngay từ phương pháp này đó là chúng ta sẽ không phụ thuộc vào kiểu của đường thẳng được vẽ trong bảng nếu có hay là các khoảng trắng đủ rộng giữa các khối để nhận dạng cấu trúc của bảng. Đầu vào (input) của thuật toán là tập hợp các hình bao chữ nhật của các từ trong một đoạn văn bản. Đầu ra (output) là các cột, các dòng, các ô của bảng nếu tồn tại môi trường bảng trong đoạn văn bản. Thuật toán sẽ cần các bước tiền xử lý như nhận dạng các dòng văn bản của trang tài liệu, hình bao chữ nhật các từ trên từng dòng văn bản và nhận dạng các đoạn văn bản khác nhau. Từ đó có nhận dạng môi trường bảng trên từng đoạn văn bản của trang tài liệu. Toàn bộ chức năng của thuật toán T-Recs mà phần cốt yếu là thuật toán phân đoạn khởi tạo sẽ được trình bày trong chương nà y. Đầu tiên luận văn sẽ trình bày thuật toán phân đoạn khởi tạo do Thomas G. Kieninger [19] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 đề xuất và sau đó chỉ ra những trường hợp mà thuật toán phân đoạn do G. Kieninger sẽ nhận dạng sai. Tiếp theo luận văn sẽ trình bày thuật toán phân đoạn cải tiến (T-Recs++) để có thể nhận dạng chính xác các cột dữ liệu tồn tại trong một bảng. Những ưu điểm và hạn chế của thuật toán cũng được chỉ ra trong phần đầu của chương. Phần tiếp theo trong chương này luận văn sẽ chỉ ra một số bược xử lý sau khi phân đoạn (postprocessing) để khắc phục những hạn chế của thuật toán phân đoạn khởi tạo. Phần cuối của chương luận văn mô tả việc phân tích các cột được nhận dạng thành các dòng và các ô trong bảng để đưa ra được cấu trúc chính xác của bảng. 4.2. Thuật toán phân đoạn khởi tạo Phân đoạn khởi tạo ta có thể hiểu như là quá trình phân cụm các từ. Trong khi các phương pháp tiếp cận dưới-lên khác thường xác định các đường kẻ từ các từ liền kề theo chiều ngang và các khối từ các đường liền kề theo chiều dọc, hệ thống sẽ trực tiếp đánh giá các cấu trúc khối văn bản từ việc phân đoạn các từ. Tư tưởng của thuật toán : lấy một từ bất kỳ làm nhân để xây dựng một khối mới. Nhìn trên Hình 4.1 (ở giữa), ta vẽ một vùng mờ ảo bao quanh hình chữ nhật bao của từ (consist). Vùng mờ ảo này có độ rộng bằng với độ rộng của hình bao của từ và chiều dọc mở rộng đến các dòng liền kề với từ đó. Tất cả các từ mà có hình bao gối lên vùng mờ ảo của từ làm nhân sẽ nằm trong cùng một khối với từ đó. Do đó một khối bao gồm tất cả các từ được liên kết với nhau (hình bên phải của Hình 4.1). Hình 4.1 Ví dụ minh họa tư tưởng của thuật toán khởi tạo Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 Thủ tục trên sẽ được mở rộng bằng cách thực hiện đệ quy cho tất cả các từ cho đến khi không tìm thấy có từ nào mới mà không nằm trong một khối nào đó. Đầu vào của thủ tục là hình bao chữ nhật của các từ, đầu ra là các khối lôgíc và các từ thuộc từng khối lôgíc. Thủ tục xây dựng thuật toán khởi tạo: 1) Tìm một từ bất kỳ nào đó Wx mà chưa được đánh dấu là mở rộng (expanded). 2) Tạo một khối mới Bi 3) Đánh dấu Wx là đã mở rộng và thêm Wx vào Bi 4) Tìm tất cả các từ Wj theo chiều ngang ở dòng trước và dòng kế tiếp, sao cho Wj nằm chồng lên Wx (có nghĩa là Wj gối lên vùng mờ ảo của Wx). 5) Thực hiện đệ quy các bước 3, 4, và 5 cho các từ Wj vừa tìm được. 6) Nếu không tìm được từ nào mà chưa đánh dấu và không nằm chồng lên nhau (theo ý nghĩa của bước 4) thì tăng i lên một và quay trở lại bước 1. 7) Dừng thủ tục lại nếu không tìm thấy từ nào chưa được đánh dấu trong tài liệu. Hình 4.2 mô tả kết quả của thuật toán sau khi mở rộng tất cả các từ trong khối Hình 4.2 thuật khởi tạo đối với một đoạn văn bản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 4.2.1. Trƣờng hợp thuật toán nhận dạng sai cột 7 bước trong thuật toán phân đoạn khối phía trên về cơ bản nhận dạng được các khối riêng rẽ nhưng cũng chưa đủ tốt để nhận dạng được tất cả các loại khối phân tách. Hình 4.2 mô phỏng một thí dụ về trường hợp thuật toán phân tách thành hai khối khác nhau nhưng về logíc hai khối trên thực chất là một khối. Hình 4.3 Trường hợp thuật toán nhận dạng sai cột Khi phân tích các bước của thuật toán trên ta thấy có một hạn chế, đó là khi một từ Wj mới được xem xét có thêm vào khối đang duyệt Bi hay không thì thuật toán chỉ quan tâm xem Wj có nằm chồng lên từ Wx (là từ ở dòng trước hay dòng sau của Wj) mà không xem xét Wj có nằm chồng lên bất kỳ từ nào thuộc khối Bi hay không. Nhìn trên Hình 4.3, nếu thực hiện lần lượt các bước từ 1 đến 7 thì ta thấy các từ trên được chia thành hai khối riêng rẽ, nhưng ta thấy hai từ Thành và vọng tuy nằm chồng lên nhau nhưng lại thuộc hai khối khác nhau bởi vì khi thuật toán đi đến từ là nó sẽ xem xét hai từ là kỳ và vọng trong đó chỉ có mỗi từ kỳ là nằm chồng lên nó còn từ vọng không nằm chồng lên từ là Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 Hình 4.4 Trường hợp giữa các dòng của một cột trong bảng có ô trắng Hình 4.4 chỉ ra một thí dụ mà thuật toán do G. Kieninger có thể nhận dạng được các cột trong bảng. Trong 7 bước mà G. Kieninger đề xuất, khi thực hiện xuất phát từ một hình bao chữ nhật của một từ thuật toán chỉ tìm các từ có nằm chồng lên nó trong dòng trước và dòng kế tiếp. Vì vậy trong trường hợp một cột trong bảng mà có nhiều dòng để trống (chẳng hạn khi một ô của bảng kéo dài trên nhiều dòng) thì khi thực hiện tìm các từ ở dòng kế tiếp và dòng trước sẽ không tìm được từ nào thuộc cột đó. Do đó để tìm được chính xác các từ thuộc một cột của bảng thì xuất phát từ một từ phải tìm trên tất cả các dòng của đoạn văn bản. Dưới đây sẽ trình bày những cải tiến các bước của thuật toán phân đoạn trên. 4.2.2. Cải tiến các bƣớc của thuật toán phân đoạn khởi tạo - T-Recs++ Do các cột của một bảng đều nằm ở các vị trí là những khoảng khác nhau theo chiều ngang, vì vậy để cải tiến thuật toán ta sẽ đi xác định toạ độ nhỏ nhất - Xmin và lớn nhất - Xmax theo chiều ngang của một khối. Khi duyệt qua các từ cần thêm vào khối nếu như toạ độ nhỏ nhất và lớn nhất theo chiều ngang của khối có giao với khoảng (Xmin, Xmax) thì ta sẽ thêm từ đó vào khối và cập nhật lại toạ độ Xmin, Xmax của khối đó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 Đầu vào của thủ tục là hình bao chữ nhật của các từ, đầu ra là các khối lôgíc và các từ thuộc từng khối lôgic. Các bước cải tiến của thuật toán phân đoạn khởi tạo sẽ gồm 8 bước như sau: 1. Gán Xmin= -1 và Xmax = 0. 2. Tìm một từ bất kỳ nào đó Wx mà chưa được đánh dấu là mở rộng (expanded). Tính các toạ độ XXmin, XXmax lần lượt là 2 toạ độ nhỏ nhất và lớn nhất theo chiều ngang của hình bao của từ Wx. 3. Tạo một khối mới Bi 4. Đánh dấu Wx là đã mở rộng và thêm Wx vào Bi. Xét:  Nếu Xmin = -1 thì gán Xmin= XXmin.  Nếu Xmin > XXmin thì gán Xmin= XXmin.  Nếu Xmax < XXmax thì gán Xmax = XXmax. 5. Tìm tất cả các từ Wj nằm theo chiều ngang ở các dòng trước và những dòng kế tiếp (thuộc đoạn văn bản), sao cho: (Xmin , Xmax) ∩ (XJmin , XJmax) ≠ Φ Trong đó các toạ độ XJmin, XJmax lần lượt là 2 toạ độ nhỏ nhất và lớn nhất theo chiều ngang của hình bao của từ Wj. 6. Thực hiện đệ quy các bước 4, 5, và 6 cho các từ Wj vừa tìm được. 7. Nếu không tìm được từ nào mà chưa đánh dấu và không thoả mãn điều kiện 5 thì tăng i lên một và quay trở lại bước 1. 8. Dừng thuật toán lại nếu không tìm thấy từ nào mà chưa được đánh dấu là mở rộng trong tài liệu. Hình 4.5 dưới đây mô tả các bước thuật toán phân đoạn đã cải tiến. Nếu như trên Hình 4.3, thuật toán trước có thể phân tách các từ vào hai khối Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 riêng rẽ thì với các bước đã cải tiến trên thuật toán sẽ nhóm các từ trong Hình 4.3 vào thành một khối duy nhất (hình cuối bên phải của Hình 4.5). Hình 4.5 Mô phỏng việc thực hiện các bước đã cải tiến của thuật toán Trong bước thứ 5 của thuật toán, khi thực hiện tìm những từ thoả mãn để đưa vào một khối, thuật toán sẽ tìm tất cả các từ ở các dòng trước và các dòng kế tiếp chứ không phải chỉ tìm ở dòng trước và dòng kế tiếp của dòng đang xét. Do đó việc nhận dạng đúng các cột của bảng từ Hình 4.4 được minh hoạ trên Hình 4.6. Hình 4.6 Kết quả nhận dạng các cột từ Hình 4.4 4.2.3. Những ƣu điểm của thuật toán Trong thí dụ đưa ra ở trên, điểm nổi bật của thuật toán vẫn chưa thể hiện rõ ràng vì sự phân đoạn của những khối văn bản dường như cũng giống những phương pháp có trước đây. Hình 4.7 minh hoạ điểm nổi bật của thuật toán khi nhận dạng cấu trúc của bảng: ở đây ta thấy mỗi khối trong hình cách nhau một khoảng cách hẹp. Do không có một từ nào nằm giữa các cột vì vậy mà các cột được phân biệt với nhau một cách rõ ràng. (Để quan sát dễ dàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 hơn, mỗi cột đều được bôi một màu khác nhau để nổi bật). Ngoài những điểm mạnh đề cập trên, thuật toán còn có những đặc điểm sau: Hình 4.7 Quá trình phân đoạn các cột của bảng  Không quan tâm đến nội dung văn bản. Do đó nó có thể áp dụng cho một tài liệu kém chất lượng để thực hiện phân đoạn.  Cho phép nhận dạng ra các cột trong bảng trong trường hợp khoảng cách giữa các cột hẹp.  Nhận dạng cấu trúc của bảng mà không cần thông tin về tiêu đề của bảng.  Nhận dạng cấu trúc bảng với các ô có nhiều hơn một dòng dữ liệu (Hình 4.8)  Thuật toán áp dụng với các loại tài liệu phổ biến (không hạn chế một số loại bảng nào đó; không quy định luật cụ thể, không cần phải có giai đoạn học nhận dạng). Hình 4.8 Trường hợp một ô của bảng chiếm nhiều dòng 4.2.4. Những mặt hạn chế của thuật toán khởi tạo Thuật toán phân đoạn khởi tạo cũng tồn tài một số mặt hạn chế vốn có. Chẳng hạn như thuật toán sẽ coi một dòng đơn là bảng bởi vì dòng này không có những dòng là láng giềng của nó theo chiều dọc. Do đó nó sẽ coi đó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 là một bảng chỉ có một dòng dữ liệu trong đó mỗi một từ coi như là một cột trong bảng. Do đó khi nhận dạng một đoạn văn bản có tạo thành bảng hay không cần xem số dòng của đoạn văn bản là bao nhiêu. Hạn chế thứ hai thường xảy ra đối với một đoạn văn bản thông thường mà đều có ký tự cách (space) tại cùng một vị trí của tất cả các dòng trong đoạn văn bản đó. Do đó đoạn văn bản đó cũng không được nhận biết đó là một khối thống nhất. Một hạn chế khác đó là một số cột trong bảng có chung một tiêu đề. Trong trường hợp này tiêu đề chung của bảng sẽ được cho vào một khối với các cột có tiêu đề chung và thuật toán nhận biết đó chỉ là một cột. Hình 4.9 mô tả toàn bộ các mặt hạn chế trên. Hình 4.9 Những mặt hạn chế của thuật toán 4.3. Các bƣớc xử lý khối sau khi phân đoạn Một số bước xử lý được đưa ra để để khắc phục những hạn chế đề cập ở trên khi nhận dạng. Trong phần này sẽ đề cập đến hai loại khối khác nhau: khối loại một là khối chỉ bao gồm một từ trên một dòng (Hình 4.7), khối loại hai là tất cả các trường hợp còn lại (Hình 4.8). Dễ nhận thấy rằng khối loại một là một bảng đơn giản. Phân biệt hai loại khối này sẽ giúp chúng ta dễ dàng chọn lựa từng phương pháp, kỹ thuật để phân tích từng loại khối. Phần dưới đây sẽ trình bày những phương pháp xử lý để khắc phục những trường hợp nhận dạng sai từ Hình 4.9. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 4.3.1. Trộn các khối phân đoạn sai Hình 4.9 ở trên chỉ ra một thí dụ với một đoạn văn bản thông thường mà đều có ký tự cách (space) tại cùng một vị trí của tất cả các dòng trong đoạn văn bản đó. Trong trường hợp này phương pháp phân đoạn trên đoạn văn bản đó không nhận biết đó là một khối thống nhất mà sẽ hiểu rằng đó là hai khối tách biệt nhau. Do đó ta cần có bước xử lý để nhận biết và trộn hai khối tách biệt này làm một khối thống nhất. Trong phương pháp này chúng ta sẽ sử dụng những khối sau khi phân đoạn ở trên. Có thể thấy rõ ràng rằng các khối mà có thể trộn thành một khối chung thường nằm bên trái hoặc bên phải của nhau. Giả sử ta đã xác định được 2 khối có thể trộn với nhau, từ một khối trước tiên chúng ta sẽ đánh giá khoảng cách trung bình giữa các từ của hai khối để tìm độ rộng trung bình của ký tự cách trong đoạn văn bản. Nếu khoảng cách giữa hai khối xấp xỉ bằng độ rộng trung bình của ký tự cách thì có thể trộn hai khối đó vào làm một. Hinh 4.10 Trộn hai khối bị phân tách Một lưu ý rằng khi ta xét hai khối có khả năng được trộn với nhau thì các khối đó phải thoả mãn là tất cả các dòng của khối đều có các từ nằm ngoài cùng bên trái hay bên phải có vùng bao của từ phải thẳng hàng theo chiều dọc. Tức là khi khối có một từ ở một dòng nào đó nằm thụt vào so với mép lề trái hay mép lề phải của khối (Hình 4.10) thì ta coi hai khối đó không có khả năng trộn với nhau. Đối với khối loại hai chúng ta chúng ta dễ dàng tính được khoảng cách trung bình giữa các từ trên cùng một dòng, sau đó ta lấy khoảng cách đó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 so sánh với khoảng cách giữa hai khối. Dựa trên một số sai số đưa ra ta sẽ quyết định liệu rằng hai khối có được trộn vào với nhau hay không. Trong trường hợp hai khối được trộn lại là hai khối loại 1 do đó ta sẽ không tính được độ rộng trung bình của các từ trong khối liền kề. Vì vậy trong trường hợp này ta sẽ tính độ rộng trung bình giữa các từ dựa vào một khối loại hai khác. Hình 4.10 chỉ ra hai khối được xử lý bởi kỹ thuật trên và kết quả tương ứng của nó. 4.3.2. Phân tách các cột bị trộn vào một khối Một vấn đề khác gặp phải đó là các cột riêng biệt được trộn với nhau, chẳng hạn các cột có chung tiêu đề thường bị trộn thành một cột ở bước phân đoạn khởi tạo. Trong khi tìm ra dấu hiệu đơn giản để nhận biết các cột được tách ra ta nhận thấy rằng mối quan hệ một – một giữa các từ trong cột là tiêu chuẩn để đánh giá các cột được tách ra . Mối quan hệ đó phải đảm bảo là , nếu một từ Wa có chính xác một từ W b là láng giềng dưới và W b cũng chỉ có duy nhất Wa là láng giềng trên . Bước tiếp theo hoàn toàn dễ hiểu : chúng ta sẽ đi phân tách tất cả các từ có quan hệ một – một vào thành một khối , gọi là khối con của khối đó . Do đó chúng ta không cần phải quan tâm đến khía cạnh nội dung v à độ cao của khối để phân tách . Mối quan hệ một - một ở trên chỉ giúp chúng ta tách được các khối con loại một (trên mỗi dòng chỉ có duy nhất một từ) do đó để tách các khối con loại hai ta phải sử dụng kỹ thuật khác. Kết quả của quá trình phân tách sẽ được mô tả trên Hình 4.11 nhưng quá trình phân tách đến bước này vẫn chưa kết thúc vì cần phải xử lý một số bước nữa để tránh phân tách sai. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 Hình 4.11 Tách các cột bị trộn Do kỹ thuật trên áp dụng cho tất cả các khối loại ha i, nhưng có một số trường hợp ta thấy rõ ràng rằng có một số lượng lớn các từ có quan hệ một – một nhưng chúng lại không tạo thành cột trong bảng . Tuy nhiên , trong bước xử lý ở trên chúng ta chưa áp dụng một số điều kiệ n ràng buộc nào để loại trừ những trường hợp đó . Hình 4.12 Trộn lại các khối con bị tách Một quy tắc đơn giản để nhận biết một cột đó là cột đó luôn đi cùng với những cột khác . Xuất phát từ các khối đã được tách ra làm khối con , chúng ta tìm đến các khối láng giềng của khối con mới được phân tách . Tìm số lượng các khối loại một bao quanh nó , độ cao của chúng , độ rộng các khoảng trắng cách ly bên trái bên phải và