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

Nội dung text: 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

1. ĐẠ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
2. ĐẠ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
3. 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
4. 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
5. 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
6. 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 Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên Hình 2.3 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. Tài liệu ảnh trước và sau các bước tiền xử lý. Ảnh (a) gốc, ảnh (b) ảnh Hình 2.5 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
7. 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
8. 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
9. 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ủatà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ấutrú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ượnglớ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ựcnhư: 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ìmra 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
10. 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ọnra 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ánT-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
11. 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
12. 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 quamộ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étcá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ưutrữ trong máy tính. Ảnh tài liệu có nhiều loại: đen trắng, ảnh màu, ảnhđacấ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
13. 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]: Xử lý tài liệu Xử lý văn bản Xử lý đối tượng ảnh Nh ận dạng Phân tích Xử lý Xử lý vùng ký tự quang cấ u trú c đường và ký tự đặc học trang kẻ biêt Xác định độ nghiêng, Vă n bản Đường thẳng, Vùng được tô dòng văn bản, các khối đường cong, văn bản, các đoạn văn góc bản 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14. 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ữngvấn đề phổ biến. Vì vậy chúng cần phải được khôi phục và chỉnhsử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àiliệ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
15. 8 Trang tà i liệ u Thu nhậ n dữ liệ u Xử lý điể m ả nh Phân tí ch đặ c trưng Phân tích và nhận Phân tích và nhận dạng đối tượng văn dạng đối tượng ảnh bản Mô tà i liệ u 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16. 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à àml 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à 0hoặ 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 ảnhvà 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
17. 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
18. 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ểmlâ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
19. 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áctừ 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ảncủ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 tinthiế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
20. 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 đốitượ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 ảnhsẽ đượ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
21. 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ưucá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(ChainCode – 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ểmlá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
22. 15 (a) (b) (c) (d) 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ướcnhậ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ệcphâ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ậndạ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à Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23. 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ệnmộ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ụngnhậ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àiliệ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. Ướclượng độ nghiêng và phân tích sơ đồ trình bày của văn bản sẽ được mô tả ngắngọ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
24. 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) khiqué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épchiế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òngcóchứa ký tự, còn các vùng trũng biểu diễn cho khoảng khônggian 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 ảnhcó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25. 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íchbố 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ả saukhi 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ácgiả, 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 chocá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áchcá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ạnvă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
26. 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ặcdù các ký tự có thể viết theo nhiều cách nhưngchú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ántrê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ủaOCR. 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ể đạttớ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ễuv.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ộttừ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27. 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, hayhoàn toàn là các ký tự trong bảng chữ cái hoặc có thể trộn lẫngiữ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ộtlớ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ủaOCR. 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ảixâydự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
28. 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ừ khilắ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ự đitheo 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ủanhận dạng cũng đạt từ 89.34% tới 97.01%. Kết quả nhận dạng giảm điđốivớ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ácký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
29. 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ớivă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ũngcó 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ơnkhi 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ậnthấ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ácphiê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ữnghệ 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 địnhdạ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ạngchữ 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ựcnghiên cứu này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30. 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ảyra.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ảnvà đâ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 ảnhmàu với nhiều lớp của bản đồ, nhận dạng đối tượngảnhbachiề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 ảnhvà văn bả n. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31. 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ấyra được phần chứa đựng thông tin và phần chứa ảnh riêng rẽ và chính xác cầncó các kỹ thuật xử lý phức tạp. Các thuật toán tách vănbả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ảilà 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áckỹ 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ạiký tự Tiếng Anh, ký tự số, ký tự Trung Hoa đòi hỏi phải được nghiên cứudựa theo những cách thức khác nhau. Chính vì những lý do đó tách cácthành phần văn bản và ảnh từ những tệp tài liệu ảnhlà 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
32. 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ảnhcá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ạitrên các tài liệu ảnh chứa nhiều các đối tượng ảnh thì phương pháp khônghiệ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ựatrê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ậttoán. - Các chuỗi ký tự trong tài liệu ảnh phải không tiếpxú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 nganghay Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33. 26 chiều dọc. Trong trường hợp chuỗi ký tự có hướng khác việc nhận dạngsẽ khó hơn. - Văn bản phải không chứa các kiểu ký tự TrungHoa [16]. Tuy nhiên những điều ện,ki 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ộtsốứ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ộtsố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 rakhỏ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 đồ đơngiả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ứctạphơ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
34. 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ăngphâ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ôngtincủ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ượngvăn bản trước. Thuật toán này có khả năng phân tách đượccá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 đặcbiệ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ậttoá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 ảnhvà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 ảnhsẽ đượ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ứacácđối tượng ảnh. Các loại đối tượng này sẽ được nhận dạng sau đó bằng nhữnghệ 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ănbả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
35. 28 bởi vì cả hai đối tượng đều được biểu diễn bởi cáccon 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àysẽ 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ẳnghạ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
36. 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. a b c d 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ớicác đối tượng ảnh. Hình 3.3c là một đối tượng ảnh có LSD cao. Những ngoại lệ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37. 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 saicá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ínhcủa thuật toán được tóm tắt trong Hì nh 3.4 như sau: 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. Hình 3.4 Sơ đồ thuậ t toá n phân tá ch văn bả n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38. 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 đitheo 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
39. 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
40. 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ỏi kh 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ảnhchỉ 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
41. 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íchthướ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,ẳng ch 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 thamsố 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úngcù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 tasẽ 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ủabú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
42. 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ậndạ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ếpxú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ấyra 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
43. 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ữ ậtnh 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 đưavà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ỗiký 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
44. 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íacạ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ượngHav, đạ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ớnvào Hav khi mà giá trịav H 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ảinhư 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ănbả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 tincậ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ùnghình bao chữ nhật để trích ra các ký tự, vì vậytấ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
45. 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ộtvà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ố đốitượ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ệnsau 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ế đốivớ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âydự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
46. 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áctừ 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ộidung đó. 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ọitê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
47. 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ộtcá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ậndạ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ẽ đivà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ầncá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ìnhbao 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
48. 41 đề xuất và sau đó chỉ ra những trường hợp mà thuật toán phân đoạn doG. 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ồntạ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ềnkề 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ớitừ đó. 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
49. 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 àon đó. Đầu vào của thủ tục là hình bao chữ nhật của các từ, đầu ralà 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 xW 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
50. 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ốii B 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
51. 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ìmcá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ếpvà 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ánphâ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
52. 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áckhố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 8bước như sau: 1. Gán Xmin= -1 và Xmax = 0. 2. Tìm một từ bất kỳ nào đó xW 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 xW 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
53. 46 riêng rẽ thì với các bước đã cải tiến trên thuật toánsẽ 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ủaHì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ủadò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
54. 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
55. 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ảnghay 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ộtcộ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ựatừ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ợpnhậ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
56. 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òngtrong đ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ộnhai 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ộtkhố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àolàmmộ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ằmngoà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 đượckhoả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
57. 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 tasẽ quyết định liệu rằng hai khối có được trộn vào với nhau haykhông. Trong trường hợp hai khối được trộn lại là hai khối loại 1 do đó tasẽ 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
58. 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à có thể là độ t ương đồ ng củ a cá c từ trong cộ t v.v để đánh giá sự tồn tại của cột đó . Nế u cá c điề u kiệ n trên không thoả mãn theo một tiêu chuẩn nào đó thì khối con mới được tạo ra đó sẽ được trộ n ngượ c trở lạ i vớ i khố i cha nó (khi đó khố i con không thoả mã n tạ o thà nh mộ t cộ t). Cụ thể hoá quá trình nhận biết một khối con được tách riêng từmột khối cha có tạo thành một cột riêng rẽ trong bảng hay không ta sẽ đi so sánh các khối con được tách ra với nhau. Quá trình tách mộtkhối thành các khối con sẽ chia khối cha thành các khối con được đánh số từB1 đến nB . Do một Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59. 52 khối iB (1 ≤ i ≤ n) bao gồm các từ liên tục nằm cạnh nhau, mỗi khối Bi có những đặc trưng (XImin, YImin) và (XImax, YImax). Trong đó (XImin, YImin) là toạ độ góc trên cùng bên trái của khối và (XJmax, YJmax) là toạ độ góc dưới cùng bên phải của khối. Vì vậy ta sẽ tìm tất cả các khối từ 1 đến n, nếu tồn tạihai khối i và j thoả mãn điều kiện như sau: XJmin <= XImin < XImax <= XJmax YJmin<= YImin < YImax <= YJmax thì có nghĩa là khối i nằm trong khối j và ta sẽ thực hiện trộn hai khối ivàj vào làm một khối. Quá trình sẽ tiếp tục tìm hai khối bất kỳ đến khi không có hai khối nào thoả mãn điều kiện trên thì bước tìm kiếm sẽ dừng lại. Điều kiện trên sẽ đảm bảo các khối con được tách riêng ra sẽ tạo thành một cột trong bảng hay chúng sẽ được trộn với các khối khác để tạo thành một cột củabảng khi mà khối đó không thoả mãn điều kiện tạo thành một cột riêng rẽ củabảng. Một cách khác để nhận biết các khối con bị tách rakhông tạo thành các cột trong bảng đó là dựa vào so sánh khoảng cách giữa hai khối vớiđộ rộng trung bình của ký tự cách (khoảng cách trung bình giữa các từ trong một khối). Nhiều trường hợp do sự trùng lặp của ký tự cách mà một khối loạihai được chia thành các khối con loại một. Do đó các khối con này phải được trộn ngược lại tạo thành một khối duy nhất. Hình 4.12 chỉ ra một thí dụ một khối loại hai được phân tách thành ba khố i con và kế t quả sau khi phân tí ch ba khố i nà y lạ i đượ c trộ n vớ i khố i cha tạo thành một khối duy nhất . 4.3.3. Nhóm các từ bị phân tách Một số từ mà không có các từ làm láng giềng trên hay láng giềng dưới thì chúng có thể thuộc về một dòng phân tách (chẳng hạn dòng tiêu đềcủa bảng), những từ gắn vào phía cuối của một khối chưa được căn chỉnh hay Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên