Tài liệu Nghiên cứu giải pháp tách bảng - tách ảnh trong phân tích trang tài liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC CÔNG NGHỆ ------------***----------- Tô Văn Khánh Nghiên cứu giải pháp tách bảng-tách ảnh trong phân tích trang tài liệu LUẬN VĂN THẠC SĨ Hà nội – 2007 ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC CÔNG NGHỆ ------------***----------- Tô Văn Khánh Nghiên cứu giải pháp tách bảng-tách ảnh trong phân tích trang tài liệu LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TS. Ngô Quốc Tạo Hà nội – 2007 MỤC LỤC MỤC LỤC ......................................................................................................................1 DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT ............................................................3 DANH MỤC CÁC BẢNG BIỂU ..................................................................................4 DANH MỤC CÁC HÌNH VẼ .......................................................................................5 MỞ ĐẦU .........................................................................................................................7 CHƢƠNG 1 TỔNG QUAN HỆ PHÂN TÍCH TÀI LIỆU ẢNH .............................10 1.1. Giới thiệu chung một hệ phân tích trang tài liệu ...............................................10 1.2. Thu nhận ảnh (Data Capture) .............................................................................13 1.3. Bƣớc xử lý điểm ảnh (Pixel – level processing) ..................................................13 1.3.1. Phương pháp nhị phân (Binarization)......................................................................... 13 1.3.2. Giảm nhiễu (Noise reduction) ................................................................................... 14 1.3.3. Phân đoạn (Segmentation) .......................................................................................... 15 1.3.4. Làm mảnh và xác định vùng (Thinning and region detection)................................... 16 1.3.5. Mã hóa CC và véctơ hóa (Chain coding and vectorization) ....................................... 17 1.4. Bƣớc phân tích các đặc trƣng của tài liệu ảnh (Feature – level analysis) .......18 1.5. Phân tích các đối tƣợng văn bản trong tài liệu ..................................................18 1.5.1. Ước lượng độ nghiêng của văn bản ............................................................................ 19 1.5.2. Phân tích sơ đồ trình bày của trang tài liệu (Layout analysis).................................... 20 1.6. Nhận dạng ký tự quang học (OCR) ....................................................................22 1.6.1. Phương pháp ............................................................................................................... 24 1.6.1.1. Trích chọn đặc trưng............................................................................................ 24 1.6.1.2. Phân loại .............................................................................................................. 24 1.6.2. Nhận dạng ký tự dựa trên ngữ cảnh ............................................................................ 27 1.7. Phân tích các đối tƣợng ảnh trong tài liệu .........................................................28 1.8. Kết luận chƣơng....................................................................................................29 CHƢƠNG 2 THUẬT TOÁN TÁCH VĂN BẢN - ẢNH TỪ TRANG TÀI LIỆU ẢNH ..............................................................................................................................31 2.1. Giới thiệu ...............................................................................................................31 2.2. Những đặc trƣng chung của một tệp tài liệu ảnh ..............................................34 2.3. Thuật toán phân tách văn bản - ảnh ...................................................................37 2.3.1. Xoá bỏ các đối tượng tuyến tính (đường thẳng) ......................................................... 37 2.3.2. Phân tích các thành phần liên thông của nét bút......................................................... 39 2.3.3. Kết hợp các nét ký tự tạo thành các chuỗi văn bản .................................................... 41 2.3.4. Thực hiện các phép toán hình thái .............................................................................. 42 2.3.5. Phân tích các thành phần liên thông mới (NCCs) ...................................................... 42 2.3.6. Biểu diễn cấu trúc thông tin của các chuỗi văn bản ................................................... 42 1 2.3.7. Thiết lập các tham số .................................................................................................. 43 2.4. Kết luận chƣơng....................................................................................................44 CHƢƠNG 3 THUẬT TOÁN TÁCH BẢNG T-RECS .............................................46 3.1. Giới thiệu ...............................................................................................................46 3.2. Thuật toán phân đoạn khởi tạo ...........................................................................48 3.2.1. Trường hợp thuật toán nhận dạng sai cột ................................................................... 49 3.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++ ............................. 50 3.2.3. Những ưu điểm của thuật toán.................................................................................... 52 3.2.4. Những mặt hạn chế của thuật toán khởi tạo ............................................................... 53 3.3. Các bƣớc xử lý khối sau khi phân đoạn .............................................................54 3.3.1. Trộn các khối phân đoạn sai ....................................................................................... 54 3.3.2. Phân tách các cột bị trộn vào một khối ....................................................................... 55 3.3.3. Nhóm các từ bị phân tách ........................................................................................... 57 3.4. Phân tích khối .......................................................................................................58 3.4.1. Khối loại 2 nằm cùng với khối loại 1 ........................................................................ 59 3.5. Xác định cấu trúc các cột, hàng ..........................................................................59 3.6. Kết luận chƣơng....................................................................................................59 CHƢƠNG 4 THỰC NGHIỆM ...................................................................................61 4.1. Nhận dạng đối tƣợng ảnh ....................................................................................61 4.1.1. Giới thiệu .................................................................................................................... 61 4.1.2. Mô tả chương trình ..................................................................................................... 62 4.1.3. Một số kết quả thử nghiệm ......................................................................................... 62 4.2. T-Recs++ ................................................................................................................67 4.2.1. Giới thiệu .................................................................................................................... 67 4.2.2. Mô tả chương trình ..................................................................................................... 67 4.2.3. Một số kết quả thử nghiệm ......................................................................................... 69 KẾT LUẬN ..................................................................................................................72 TÀI LIỆU THAM KHẢO ...........................................................................................74 2 DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT 3–D CAD 3 Dimensions Computer Aided Design CAM CC CCs Computer Aided Manufacturing Chain Code Connected Components CPU Control Processing Unit DP Dynamic Programming HWRatio Height Width Ratio K – NNR K – Nearest Neighbour Rule LC LSD NCCs NNR OCR T-Recs Linear Component Local Stroke Density New Connected Components Nearest Neighbour Rule Optical Character Recognition Table Recognition System WBRatio WDG White Black Ratio White-space Density Graphs 3 DANH MỤC CÁC BẢNG BIỂU Bảng 1 Bảng 2 Bảng 3 Độ đậm của nét bút (LSD) của Hình 13. .................................................................. 35 Tổng kết một số kết quả thực nghiệm nhận dạng đối tượng ảnh.............................. 63 Tổng kết một số kết quả thực nghiệm nhận dạng bảng. ........................................... 70 4 DANH MỤC CÁC HÌNH VẼ Hình 1. Sơ đồ khối của việc xử lý tài liệu ............................................................................. 11 Hình 2. Các bước xử lý cho một hệ phân tích tài liệu, đi kèm sơ đồ là một thí dụ với các kết quả thu được từ từng bước. ....................................................................................... 12 Hình 3. Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên bản. Trục ngang biểu diễn các giá trị ngưỡng được chọn. Ảnh sau khi được nhị phân: (b) sử dụng ngưỡng thấp, (c) ngưỡng hợp lý, (d) ngưỡng quá cao. .................................... 14 Hình 4. Ảnh nguyên bản bên trái và ảnh sau khi làm mảnh bên phải. (a) Ký tự “m”. (b) Một sơ đồ. (c) Vân tay...................................................................................................... 17 Hình 5. Cửa sổ 3x3 điểm ảnh với điểm ảnh X nằm ở tâm. Các giá trị số biểu diễn cho hướng mà một điểm láng giềng của X thuộc: 0 (tây), 1(tây - bắc), 2(bắc), 3(đông - bắc), 4(đông), 5(đông – nam), 6(nam), 7(tây – nam). ....................................................... 18 Hình 6. Biểu đồ Histogram của phép chiếu ngang và dọc của ảnh (a) và (b). ...................... 20 Hình 7. Kết quả phân tích cấu trúc và chức năng các khối của một trang tài liệu. Phân tích cấu trúc sẽ cho kết quả là các khối riêng rẽ dựa trên khoảng trắng giữa các khối. Nhận dạng chức năng và gãn nhãn cho các khối dựa trên quy tắc sắp xếp thông tin của trang tài liệu. ...................................................................................................... 21 Hình 8. Các ký tự viết bằng tay sẽ rất dễ nhầm lẫn ............................................................... 23 Hình 9. Sẽ không dễ dàng gì để phân tách và nhận dạng hai số 4,2 có các nét nối liền nhau như trên ..................................................................................................................... 23 Hình 10. Các cấu trúc đặc trưng nét, tính lõm, lỗ hổng, các điểm cắt ngang và kết thúc có thể được sử dụng làm các chiều của không gian đặc trưng để phân loại ký tự. ............. 25 Hình 11. Các đặc trưng của ảnh ký tự được trích ra ................................................................ 26 Hình 12. Một số thí dụ nhầm lẫn giữa ký tự và ảnh ................................................................ 35 Hình 13. Thí dụ về văn bản và ảnh .......................................................................................... 35 Hình 14. Biểu diễn các điểm ảnh giao nhau ............................................................................ 36 Hình 15. Một số trường hợp ngoại lệ ...................................................................................... 36 Hình 16. Sơ đồ khối thực hiện của thuật toán phân tách văn bản - ảnh .................................. 38 Hình 17. Phép toán kéo giãn trong việc nhận dạng các đường kẻ nghiêng. (a) ảnh nguyên bản. (b) α = ±22.5. (c) α = ±45. (d) α = ±67.5 .......................................................... 38 Hình 18. 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). ...... 41 Hình 19. Các từ láng giềng của từ “consist” theo chiều dọc .................................................. 48 Hình 20. Thuật toán phân đoạn khởi tạo đối với một đoạn văn bản ....................................... 49 Hình 21. Trường hợp thuật toán nhận dạng sai cột ................................................................. 49 Hình 22. Trường hợp giữa các dòng của một cột trong bảng có ô trắng ................................. 50 Hình 23. Mô phỏng việc thực hiện các bước sau khi đã cải tiến thuật toán T-Recs++ ........... 52 Hình 24. Kết quả nhận dạng các cột từ Hình 22...................................................................... 52 Hình 25. Quá trình phân đoạn các cột của bảng ...................................................................... 52 Hình 26. Trường hợp một ô của bảng chiếm nhiều dòng ........................................................ 53 Hình 27. Những mặt hạn chế của thuật toán ........................................................................... 54 Hình 28. Trộn hai khối bị phân tách ........................................................................................ 55 Hình 29. Tách các cột bị trộn .................................................................................................. 56 Hình 30. Trộn lại các khối con bị tách .................................................................................... 56 Hình 31. Nhận biết các từ bị phân tách dựa vào các điểm phân lề.......................................... 58 Hình 32. Tách các khối loại 1 thành các ô của bảng ............................................................... 58 Hình 33. Tách các khối loại 2 thành các hàng trong bảng ...................................................... 59 Hình 34. Giao diện của chương trình nhận dạng đối tượng ảnh ............................................. 63 5 Hình 35. Hình 36. Hình 37. Hình 38. Hình 39. Hình 40. Hình 41. Hình 42. Hình 43. Hình 44. Hình 45. Kết quả nhận dạng một sơ đồ ................................................................................... 64 Một thí dụ về ký tự tiếp xúc với đối tượng ảnh ........................................................ 64 Một thí dụ cho kết quả nhận dạng khá chính xác ..................................................... 65 Thí dụ một hình vẽ máy cơ khí................................................................................. 65 Thí dụ về một bản thiết kế ........................................................................................ 66 Thí dụ về sơ đồ một bộ điều chỉnh điện áp và mạch điện ........................................ 66 Giao diện chương trình T-Recs++ ............................................................................ 68 Kết quả xây dựng khối của T-Recs++ ..................................................................... 69 Trường hợp nhận dạng có môi trường bảng ............................................................. 70 Trường hợp nhận dạng đối với một văn bản thông báo ........................................... 71 Thí dụ về nhận dạng bảng điểm ............................................................................... 71 6 MỞ ĐẦU Ngày này khi máy tính phát triển, cùng với tốc độ và không gian lưu trữ trong máy tính đã được nâng cấp lên rất nhiều. Việc lưu trữ số lượng khổng lồ tài liệu và xử lý những nhiệm vụ phức tạp trên máy tính ngày càng nhiều. Những công việc văn phòng hàng ngày đều liên quan đến tài liệu, một tài liệu không chỉ đơn giản được lưu trữ mà nó cần phải được xử lý để có khả năng thay đổi, soạn thảo, chỉnh sửa và trích chọn các thông tin quan trọng. Vì thế các hệ phân tích tài liệu ra đời, mục đích của chúng là giúp biểu diễn thông tin trong các tài liệu ảnh, tài liệu giấy được đưa vào từ máy quét dưới dạng có cấu trúc. Một 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. Rõ ràng rằng khi máy tính ra đời và phát triển đã giải quyết được nhiều vấn đề trong việc lưu trữ thông tin. Theo ước tính trên thế giới, chỉ có một số lượng nhỏ tài liệu từ những thư viện giấy khổng lồ được đưa lên mạng và vì vậy còn có một số lượng lớn những nguồn tri thức của nhân loại đang được lưu trữ theo cách thức cổ điển trong những thư viện mà việc bỏ ra chi phí duy trì (chủ yếu trả lương cho nhân viên) cho những nguồn tài liệu này là rất lớn. Thông tin bây giờ không nhất thiết phải lưu trữ bằng giấy, một cách lưu trữ không an toàn, không bền vững theo thời gian, thay vì đó nó được lưu trữ một cách ổn định và an toàn trong máy tính. Do đó bằng cách này hay cách khác tài liệu giấy được quét thành các tệp dữ liệu ảnh và được lưu trữ trong máy tính. Không chỉ đơn giản là vấn đề lưu trữ, các tài liệu từ giấy in được đưa vào máy tính còn cần được xử lý và trích chọn ra những thông tin quan trọng. Một tài liệu giấy in được đưa vào máy tính còn yêu cầu có khả năng soạn thảo, hiệu chỉnh và khôi phục lại. Một tệp dữ liệu ảnh cần phải chuyển được sang những định dạng khác để có khả năng soạn thảo, khi đó phải đảm bảo các thông tin được chuyển sang từ tệp dữ liệu ảnh phải không bị mất đi, không bị thiếu thông tin và cấu trúc vị trí của dữ liệu vẫn được giữ nguyên. Chẳng hạn vị trí các đoạn văn bản, tiêu đề, các bảng dữ liệu, các vùng ảnh, .v.v.. phải được 7 chuyển sang đúng theo cấu trúc thể hiện trên tệp dữ liệu ảnh. Vì thế ngành nhận dạng hay các hệ phân tích tài liệu ảnh ra đời và phát triển để giải quyết những vấn đề trên. 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ột vài sản phẩm thương mại đã có chẳng hạn như các hệ nhận dạng quang học OCR để nhận dạng các ký tự in, ký tự viết tay, các bảng biểu tuy nhiên vẫn cần nhiều nghiên cứu để cải thiện độ chính xác của các hệ thống này. Một số sản phẩm chẳng hạn như VnDOCR (của Việt Nam) cho phép nhận dạng các chuỗi văn bản, các bảng biểu hay Omnipage, Find Reader .v.v.. là những sản phẩm nhận dạng nổi tiếng. Bài toán nhận dạng bảng và các đối tượng ảnh trong tài liệu ảnh là những bài toán khó và phức tạp. Trước đây các hệ phân tích tài liệu ảnh chỉ tập trung vào nhận dạng các chuỗi ký tự, phân đoạn các khối văn bản. Ngày nay tài liệu không chỉ đơn thuần là văn bản mà nó còn bao gồm hỗn hợp những đối tượng các chuỗi ký tự, ảnh, các hình vẽ, sơ đồ, các bảng biểu .v.v.. 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.. Đã có rất nhiều phương pháp, thuật toán tách bảng, tách ảnh được công bố trước đây. Tuy nhiên những nghiên cứu trên những vấn đề đó đã và đang 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 chưa thực sự hoàn chỉnh và cần phải cải tiến chúng. 8 Luận văn bao gồm 5 phần chủ yếu tập trung vào trình bày những thuật toán nhận dạng bảng và trích ra những đối tượng ảnh trong trang tài liệu ảnh. Chương 1 trình bày ngắn gọn cấu trúc chung của một hệ phân tích tài liệu ảnh, bao gồm các thành phần chính như: lấy dữ liệu, xử lý điểm ả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 2 trình bày một bài toán điển hình trong nhận dạng đó là 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 3 đưa ra một thuật toán nhận dạng bảng theo phương pháp tiếp cận dưới – lên (bottom – up). Thuật toán được đề xuất bởi Thomas G .Kieninger (1998) [15] được đặt tên là T-Recs. Tuy nhiên để nhận dạng được chính xác các cấu trúc bảng thì thuật toán còn nhiều hạn chế. Luận văn sẽ chỉ ra trường hợp hạn chế của thuật toán và đề xuất thuật toán cải tiến T-Recs++. Cuối cùng chương 4 trình bày hai chương trình thử nghiệm: Nhận dạng đối tượng ảnh để tách các đối tượng ảnh ra khỏi trang tài liệu ảnh có lẫn văn bản và T-Recs++ dùng để nhận dạng bảng. Phần kết luận nêu tóm tắt lại các vấn đề được đưa ra trong luận văn và đưa ra những vấn đề còn tồn tại để nâng cao tính hiệu quả của những thuật toán. Các hướng giải quyết và nghiên cứu trong tương lai đối với những phương pháp này cũng sẽ được đưa ra. Thuật toán T-Recs++ trình bày trong chương 3 được công bố trong báo cáo [1]. Ngoài bốn chương chính và phần kết luận, luận văn còn có thêm các danh mục bao gồm: danh mục các từ viết tắt, danh mục bảng biểu, danh mục hình vẽ và tài liệu tham khảo để thuận tiện cho việc đọc và tìm hiểu nội dung của luận văn. 9 CHƢƠNG 1 TỔNG QUAN HỆ PHÂN TÍCH TÀI LIỆU ẢNH 1.1. Giới thiệu chung một hệ phân tích trang tài liệu Một hệ phân tích tài liệu ảnh nói đến một hệ thống bao gồm những thuật toán và các kỹ thuật mà 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 [3]. Một sản phẩm phân tích tài liệu ảnh mà nhiều người biết đến đó là phần mềm Nhận dạng ký tự quang học (OCR), phần mềm có khả năng nhận dạng các ký tự từ các loại tài liệu dưới dạng ảnh. 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. Chương này sẽ mô tả tóm tắt các 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 (Hình 1). 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à 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… Chúng ta có thể xem xét 3 ví dụ cụ thể được chỉ ra dưới đây để thấy được sự cần thiết của việc phân tích tài liệu: 1) Phần lớn các tài liệu văn bản trong văn phòng làm việc đều được tạo ra từ máy tính, và thậm chí chúng được tạo ra bởi các máy tính, phần mềm khác nhau, và do đó có thể định dạng của chúng là không tương thích với nhau. Chúng có thể bao gồm các định dạng văn bản, các bảng dữ liệu và cũng có 10 thể là các văn bản viết bằng tay. Chúng có kích thước khác nhau, có thể từ một tấm thẻ doanh nghiệp đến một ảnh vẽ kỹ thuật lớn. Một hệ phân tích tài liệu sẽ giúp nhận dạng các loại tài liệu, có khả năng trích chọn ra được các phần chức năng và có khả năng chuyển từ một định dạng máy tính này 2) sang một định dạng khác. Một thí dụ khác 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. 3) Hơn thế nữa trong những thư viện cổ điển trước đây (thư viện lưu trữ các loại sách báo dưới dạng giấy tờ, vẫn còn tồn tại 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 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. Những ví dụ 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. Xử lý tài liệu Xử lý văn bản Nhận dạng ký tự quang học - OCR Văn bản Xử lý đối tượng ảnh Phân tích cấu trúc trang Xử lý dòng 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 Xử lý vùng và biểu tượng Vùng được tô Hình 1. Sơ đồ khối của việc xử lý 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 11 đư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 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ý. Trang tài liệu Lấy dữ liệu 107 điểm ảnh Xử lý điểm ảnh 7500 hình bao ký tự, mỗi ký tự có kích thước 15x20 điểm ảnh 500 đường kẻ và đường cong với độ dài từ 20 đến 2000 điểm ảnh 1000 vùng ảnh được tô với kích thước từ 20x20 đến 200x200 điểm ảnh Phân tích đặc trưng 7500x10 đặc trưng của ký tự 10x5 đặc trưng vùng Phân tích và nhận dạng đối tượng ảnh Phân tích và nhận dạng văn bản 1500x10 ký tự, 10 đoạn văn bản, 1 tiêu đề chính và 2 tiêu đề phụ 500x5 đặc trưng của đường thẳng và đường cong Hai sơ đồ và 1 ảnh lô gô của công ty,.v.v.. Mô tả tài liệu Hình 2. Các bước xử lý cho một hệ phân tích tài liệu, đi kèm sơ đồ là một thí dụ với các kết quả thu được từ từng bước. Hình 2 minh hoạ cho các bước xử lý chung của một hệ phân tích tài liệu [3]. Sau khi dữ liệu được tạo ra, tài liệu ảnh phải trải qua các bước xử lý điểm ảnh và phân tích 12 đặc trưng và sau đó tách ra từng phần nhận dạng văn bản và ảnh riêng rẽ. Các phần sau sẽ mô tả ngắn gọn các bước xử lý trên. 1.2. Thu nhận ảnh (Data Capture) Dữ liệu trong các 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 các tệp dữ liệu ảnh, chúng bao gồm các điểm ảnh (pixels) và mô hình giống như lưới các điểm ảnh. Giá trị điểm ảnh có thể là 0 và 1 trong ảnh nhị phân, 0 đến 255 trong ảnh đa cấp xám và ảnh màu 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 trong 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. 1.3. Bƣớc xử lý điểm ảnh (Pixel – level processing) 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 sau này. Chẳng hạn như các thao tác: chọn ngưỡng để chuyển ảnh đa cấp xám hay ả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ơ. Bước xử lý điểm ảnh (người ta cũng có thể gọi là bước tiền xử lý (preprocessing) hay bước xử lý cấp thấp trong một số bài báo) sẽ là chủ đề của phần này [3]. 1.3.1. Phương pháp nhị phân (Binarization) Với những ảnh đa cấp xám với các thông tin mà vố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 (Hình 3). Điều 13 này sẽ đặc biệt khó 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), khi nét của văn bản là mỏng hoặc là khi dữ liệu không được chiếu sáng tốt khi thực hiện quét 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. Hình 3. Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên bản. Trục ngang biểu diễn các giá trị ngưỡng được chọn. Ảnh sau khi được nhị phân: (b) sử dụng ngưỡng thấp, (c) ngưỡng hợp lý, (d) ngưỡng quá cao. 1.3.2. Giảm nhiễu (Noise reduction) Xuất hiện các điểm 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, sự sao chép, quá trình quét tài liệu từ máy quét. Một số kỹ 14 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. Nhiễu muối và nhiễu hạt tiêu (Salt and Pepper noise) là những loại nhiễu phổ biến nhất có trong các tài liệu kém chất lượng. Chúng xuất hiện như những điểm ảnh khác biệt so với vùng xung quoanh, 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. Các phép toán hình thái thường được sử dụng để loại bỏ nhiễu. Hai phép toán hình thái cơ bản là giãn ảnh (Dilation) và co ảnh (Erosion). Co ảnh là phương pháp làm giảm kích cỡ của vùng ON. Giãn ảnh là phương pháp ngược lại với co ảnh, trong đó những điểm đơn ON thì tăng thêm. Các phép toán này thường được kết hợp với nhau nhiều lần và áp dụng tuần tự co ảnh và giãn ảnh nhiều lần. Một trong những phương pháp kết hợp đó được gọi là phép toán OPENING, sử dụng cùng một số lần co ảnh và giãn ảnh. Kết quả của phép toán OPENING là vùng biên của đối tượng nhẵn hơn, vùng eo nhỏ bị đứt và các vùng điểm nhiễu nhỏ được loại bỏ. Phép toán đối xứng của OPENING là CLOSING. Nó thực hiện giãn ảnh cùng một số lần với co ảnh. Kết quả thu được của phép toán CLOSING đó là vùng biên nhẵn hơn, loại bỏ các lỗ hổng (holes) nhỏ trong đối tượng và nối liền các kẽ hở ngắn giữa các đối tượng. 1.3.3. Phân đoạn (Segmentation) Quá trình phân đoạn được thực hiện làm hai phần. Phần thứ nhất, tách ra thành 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. Phầ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. 15 1.3.4. Làm mảnh và xác định vùng (Thinning and region detection) 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à khác nhau nhưng có thể biểu diễn chúng giống nhau. Trong Hình 4, một số ảnh được đưa ra trong đó nội dung của ảnh được phân tích bằng phương pháp làm mảnh và kết quả làm mảnh của ảnh cũng được đưa ra. Chú ý rằng một số cuốn sách hay bài báo cũng gọi làm mảnh ảnh bằng các thuật ngữ lấy xương ảnh hay lấy đường tâm của ảnh. Trong khuôn khổ của luận văn này chúng ta sẽ dùng thuật ngữ “làm mảnh” (thinning). Một thuật ngữ khác cũng liên quan đến thao tác làm mảnh ảnh đó là tìm “trục trung vị”. Trục trung vị bao gồm các điểm ảnh của một vùng mà mỗi điểm ảnh có khoảng cách bằng nhau tới hai điểm biên gần nó nhất. Tiêu chuẩn của trục trung vị chính là tư tưởng chính của phương pháp làm mảnh ảnh. Tuy nhiên khái niệm trục trung vị chỉ được xác định đối với những vùng ảnh liên tục, với trường hợp các mẫu ảnh không liên tục một số kỹ thuật làm mảnh ảnh khác được đưa ra. 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 16 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. Hình 4. Ảnh nguyên bản bên trái và ảnh sau khi làm mảnh bên phải. (a) Ký tự “m”. (b) Một sơ đồ. (c) Vân tay. 1.3.5. Mã hóa CC và véctơ hóa (Chain coding and vectorization) Khi một đối tượng đượ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 (Hình 5). 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 17 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. 3 2 1 4 X 0 5 6 7 Hình 5. Cửa sổ 3x3 điểm ảnh với điểm ảnh X nằm ở tâm. Các giá trị số biểu diễn cho hướng mà một điểm láng giềng của X thuộc: 0 (tây), 1(tây - bắc), 2(bắc), 3(đông - bắc), 4(đông), 5(đông – nam), 6(nam), 7(tây – nam). 1.4. Bƣớc phân tích các đặc trƣng của tài liệu ảnh (Feature – level analysis) Sau bước 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. 1.5. Phân tích các đố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 18