Tài liệu Phương pháp phát hiện bảng trong tài liệu tổng hợp

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG ------------ ------------ Nguyễn Cảnh Ân PHƢƠNG PHÁP PHÁT HIỆN BẢNG TRONG TÀI LIỆU TỔNG HỢP LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN THÁI NGUYÊN- 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG ------------ ------------ Nguyễn Cảnh Ân PHƢƠNG PHÁP PHÁT HIỆN BẢNG TRONG TÀI LIỆU TỔNG HỢP Chuyên ngành : Mã số: Khoa học máy tính 60 48 01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS Ngô Quốc Tạo THÁI NGUYÊN- 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỤC LỤC DANH MỤC CÁC HÌNH VẼ.............................................................................. i LỜI CẢM ƠN .................................................................................................... iii MỞ ĐẦU .............................................................................................................. 1 CHƢƠNG 1: HỆ PHÂN TÍCH TRANG TÀI LIỆU ẢNH VÀ BÀI TOÁN PHÁT HIỆN BẢNG……………………………………………………………4 1.1. Giới thiệu chung hệ phân tích trang tài liệu và bài toán phát hiện bảng…...4 1.1.1. Quá trình thu nhận ảnh ............................................................................. 7 1.1.2. Các bước xử lý điểm ảnh ......................................................................... 8 1.1.2.1. Phương pháp nhị phân........................................................................ 8 1.1.2.2. Giảm nhiễu ....................................................................................... 10 1.1.2.3. Phân đoạn ......................................................................................... 11 1.1.2.4. Làm mảnh và xác định vùng ............................................................ 11 1.1.2.5. Mã hóa CC và véctơ hóa .................................................................. 13 1.1.3. Phân tích các đặc trưng của tài liệu ảnh ................................................. 14 1.1.4. Phân tích các đối tượng văn bản trong tài liệu ....................................... 15 1.1.4.1. Ước lượng độ nghiêng của văn bản ................................................. 15 1.1.4.2. Phân tích sơ đồ trình bày của trang tài liệu ...................................... 17 1.1.5. Nhận dạng ký tự quang học (OCR)........................................................ 19 1.1.5.1. Trích chọn đặc trưng ........................................................................ 21 1.1.5.2. Phân loại ........................................................................................... 22 1.1.5.3. Nhận dạng ký tự dựa trên ngữ cảnh ................................................. 25 1.2. Bài toán phát hiện bảng ................................................................................ 26 1.2.1. Mô tả bài toán ...................................................................................... 27 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.2.2. Một số hướng tiếp cận ......................................................................... 29 1.3. Kết luận chương ........................................................................................... 30 CHƢƠNG 2: PHÂN TÍCH BẢNG DỰA TRÊN T-RECS ......................... 32 2.1. Phương pháp phát hiện bảng trong tài liệu ảnh............................................ 32 2.2. Giới thiệu thuật toán T-Recs ........................................................................ 38 2.2.1. Các bước khởi tạo và phân đoạn của thuật toán ................................... 41 2.2.2. Trường hợp xác định sai cột của thuật toán .......................................... 43 2.2.3. Cải tiến một số bước của thuật toán ..................................................... 44 2.2.4. Những ưu điểm của thuật toán .............................................................. 48 2.2.5. Những mặt hạn chế của thuật toán khởi tạo .......................................... 49 2.3. Xử lý khối sau khi phân đoạn .................................................................... 51 2.3.1. Trộn các khối phân đoạn sai.................................................................. 51 2.3.2. Phân tách các cột bị trộn vào một khối ................................................. 52 2.3.3. Nhóm các từ bị phân tách ...................................................................... 55 2.4. Phân tích khối ............................................................................................... 56 2.5. Phát hiện cấu trúc các cột, hàng ................................................................... 57 2.6. Kết luận chương ........................................................................................... 58 CHƢƠNG 3: CHƢƠNG TRÌNH DEMO CỦA THUẬT TOÁN ................. 59 3.1. Giới thiệu chung ........................................................................................... 59 3.2. Mô tả chương trình ....................................................................................... 60 3.3. Một số kết quả thử nghiệm........................................................................... 61 KẾT LUẬN ........................................................................................................ 63 DANH MỤC CÁC TÀI LIỆU THAM KHẢO ............................................... 66 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ i DANH MỤC CÁC HÌNH VẼ Hình 1.1 Sơ đồ khối của việc xử lý tài liệu Hình 1.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 1.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 Hình 1.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…………………… Hình 1.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 (hướng 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) Hình 1.6 Văn bản bị nghiêng khi quét Hình 1.7 Biểu đồ Histogram của phép chiếu ngang và dọc của ảnh (a) và (b) Hình 1.8 Kết quả phân tích cấu trúc và chức năng các khối Hình 1.9 Để 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 dễ gây nhầm lẫn Hình 1.10 Các ký tự viết bằng tay sẽ rất dễ nhầm lẫn……………………….. Hình 1.11 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ự Hình 1.12 Các đặc trưng của ảnh ký tự được trích ra Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ii Hình 1.13 Một số nhầm lẫn giữa bảng và đối tượng khác Hình 1.14 Khái niệm các thành phần trong bảng Hình 2.1 Một số lỗi phổ biến của các thuật toán phát hiện cấu trúc bảng Hình 2.2 Thuật toán phát hiện bảng dựa Tab-stop Hình 2.3 Các từ láng giềng của từ “consist” theo chiều dọc Hình 2.4 Thuật toán phân đoạn khởi tạo đối với một đoạn văn bản Hình 2.5 Trường hợp thuật toán nhận dạng sai cột Hình 2.6 Trường hợp giữa các dòng của một cột trong bảng có ô trắng Hình 2.7 Mô tả kết quả thuật toán đã được điều chỉnh nhận dạng khối Hình 2.8 Kết quả nhận dạng các cột từ hình 2.5 Hình 2.9 Mô tả quá trình phân khối của văn bản trong các cột có khoảng cách rất hẹp Hình 2.10 Trường hợp một ô của bảng chiếm nhiều dòng dữ liệu Hình 2.11 Những mặt hạn chế của thuật toán Hình 2.12 Trộn hai khối bị phân tách Hình 2.13 (a):Tách các cột nhỏ trong cột lớn;(b):Trộn các khối nhỏ vào khối lớn Hình 2.14 Trộn các từ bị tách nhờ vào các đoạn thẳng canh lề Hình 2.15 (a) Phân tích khối loại 1 thành cấu trúc các ô của bảng ; (b) Ô khối loại 2 được phân tich nhờ vào ô khối loại 1 Hình 2.16 Tách các khối loại 2 thành các hàng trong bảng Hình 3.1 Giao diện chương trình thử nghiệm Hình 3.2 Kết quả nhận dạng khối của chương trình Hình 3.3 Trường hợp nhận dạng có môi trường bảng Hình 3.4 Nhận dạng ra các cột, các khối văn bản Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ iii LỜI CẢM ƠN Trong suốt thời gian 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 và công nghệ Việt Nam, luận văn của em đã được hoàn thành. Mặc dù bản thân đã 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 cũng còn nhiều hạn chế nên luận văn cũng không tránh khỏi những thiếu sót trong quá trình làm. Để hoàn thành xong 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 hướng dẫn em trong 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 Ban giám hiệu, phòng Đào tạo, các thầy cô giáo của trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên cùng các thầy cô giáo trong Viện Công nghệ Thông Tin – Viện Khoa học và Công nghệ Việt Nam đã quan tâm, tạo điều kiện thuận lợi, nhiệt tình giảng dạy và hướng dẫn em trong suốt hai năm học qua. Và cuối cùng tôi xin gửi lời cảm ơn đến gia đình, cơ quan và toàn thể học viên lớp K11I Ninh Bình đã quan tâm, động viên và giúp đỡ tôi trong suốt hai năm học vừa qua. Cuối cùng em rất mong nhận được sự chỉ dẫn, góp ý của các thầy cô giáo để luận văn của em được hoàn thiện hơn. Em xin trân trọng cảm ơn ! Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU Trong những năm gần đây, các thiết bị phần cứng máy tính phục vụ cho công việc lưu trữ và xử lý hình ảnh đã phát triển vượt bậc cả về dung lượng lẫn tốc độ xử lý. Đồng thời, giá cả của các thiết bị này cũng đã giảm đến mức con người trên toàn thế giới dễ dàng sở hữu những thiết bị liên quan đến việc phân tích và xử lý hình ảnh. học máy tính. Các loại tài liệu lưu trữ trên giấy và xử lý theo các cách thức cũ không theo kịp tốc độ phát triển của công nghệ. Những công việc ngày nay liên quan đến các loại tài liệu không chỉ là các tài liệu chữ chỉ để lưu trữ mà tài liệu bao gồm nhiều thành phần như các bảng biểu, ảnh…với 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. Lĩnh vực xử lý ảnh là một công việc có nhiều ứng dụng trong cuộc sống, theo đó, một số nước phát triển trên thế giới như Nhật Bản, Trung Quốc, Pháp, Mỹ, Canada đã không ngừng nghiên cứu phát triển công nghệ phần mềm liên quan đến ngành nhận dạng và xử lý hình ảnh để khai thác triệt để lợi thế của sức mạnh phần cứng hiện có. Cùng với sự phát triển công nghệ tri thức và nhận dạng trên thế giới, Việt Nam ta cũng đang từng bước đầu tư và phát triển ngành nhận dạng và xử lý ảnh. Điển hình là sự phát triển và ứng dụng mạnh mẽ của Viện Khoa học công nghệ Việt Nam – Viện Công nghệ Thông tin Việt Nam. Tại Viện Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2 đã có nhiều tác giả nghiên cứu và cải tiến một số thuật toán quan trọng liên quan đến việc nhận dạng và phân tách các đối tượng khác nhau trong ảnh tài liệu. Từ đó đưa ra được một số phần mềm ứng dụng thiết thực trong cuộc sống. Điển hình là sản phẩm phần mềm Hệ nhận dạng quang học OCR, hay hệ nhận dạng các chuỗi văn bản, bảng biểu VnDOCR. Nhiều thuật toán ra đời và từng bước phát triển đã phục vụ đắc lực cho việc đưa ra các ứng dụng khả thi vào cuộc sống cũng như góp phần xây dựng và bổ sung kho tri thức khoa học công nghệ của thế giới. Điển hình về thuật toán nhận dạng đối tượng trong ảnh tài liệu là 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) được đề xuất bởi tác giả Thomas G.Kieninger được đặt tên là T-Recs. Phát hiện bảng và ả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.. Một số yếu tố cấu thành nên bảng biểu (structure of table) đó là các ô (cells), các dòng (rows) và các cột (columns). Phát hiện bảng là bài toán phát hiện ra các cột, các dòng, các ô của bảng biểu. Việc phân tích cấu trúc của ảnh tài liệu có vai trò quan trọng rằng khi máy tính định hình được cấu trúc của ảnh thì sẽ giúp ích cho việc phục vụ mang tính chất đầu cuối cho những công đoạn xử lý khác, cũng như kết hợp xử lý tự động các dữ liệu thu thập được. Do đó, khi đã phát hiện được một đối tượng (văn bản hay hình ảnh) thì việc phát hiện luôn cả cấu trúc chứa đựng và liên quan với đối tượng đó là thật sự cần thiết. Một trong những cấu trúc quan trọng phổ biến thường được sử dụng mà trong luận văn quan tâm đề cập đến đó là việc phát hiện bảng biểu (detect table) trong ảnh tài liệu Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 Trong phạm vi một đề tài luận văn thạc sĩ với chủ đề “Phƣơng pháp phát hiện bảng trong tài liệu tổng hợp” tôi sẽ tìm hiểu một số phương pháp, kỹ thuật phát hiện bảng trong tài liệu tổng hợp, đưa ra giải pháp cải tiến thuật toán, hướng phát triển của thuật toán, xây dựng chương trình thử nghiệm. Bố cục của luận văn ngoài phần mở đầu và phần kết luận bao gồm 3 chương. 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... và giới thiệu bài toán phát hiện bảng Chương 2 đưa ra một thuật toán phát hiện 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) được đặt tên là T-Recs. Tuy nhiên để phát hiện đượ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 thuật toán phát hiện sai và đưa ra giải pháp nâng cao độ chính xác khi phát hiện. Cuối cùng chương 3 trình bày chương trình thử nghiệm: Nhận dạng bảng theo cấu trúc dùng để nhận dạng bảng trong trang tài liệu tổng hợp. 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. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 4 CHƢƠNG 1: HỆ PHÂN TÍCH TRANG TÀI LIỆU ẢNH VÀ BÀI TOÁN PHÁT HIỆN BẢNG 1.1. Giới thiệu chung một hệ phân tích trang tài liệu và bài toán phát hiện bảng Ảnh tài liệu sau khi được quét và lưu trữ trong 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. Một vấn đề đặt ra cho chúng ta là trích chọn ra các thông tin đặc trưng để máy tính có thể nhận biết được các dữ liệu này. Đây chính là nhiệm vụ của một hệ phân tích trang tài liệu. Đó chính là một tập hợp các thuật toán và các kỹ thuật để có thể phát hiện ra các đối tượng văn bản, đối tượng ảnh trong ảnh tài liệu và có khả năng trích chọn ra các thông tin người dùng mong muốn. Một trong những công nghệ được áp dụng để nhận dạng văn bản là công nghệ nhận dạng ký tự bằng quang học (Optical Character Recognition – OCR). Phần mềm này có khả năng nhận dạng ký tự trên nền định dạng ảnh tài liệu và chuyển sản phẩm nhận dạng sang kiểu tập tin văn bản có khả năng soạn thảo và tìm kiếm nội dung của tài liệu. Như vậy, mục đích của hệ phân tích tài liệu là phát hiện ra được các đối tượng khác nhau trong ảnh tài liệu như các đối tượng văn bản, hình ảnh… và đưa ra được các thông tin người dùng mong muốn để phục vụ cho các mục đích nghiên cứu, ứng dụng khác nhau. Và đặc biệt, trong phạm vi nghiên cứu của luận văn này đi sâu về việc phát hiện bảng (detect table) trong ảnh tài liệu. Trong các loại văn bản, tài liệu thì đối tượng bảng là thành phần quan trọng trong một trang tài liệu tổng hợp, do đó trước hết việc phân tích sơ đồ trình bày, Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 5 cấu trúc trang là rất cần thiết để phục vụ cho việc xác định đối tượng bảng biểu. Một trang tài liệu tổng hợp thông thường gồm có hai loại đối tượng chính là văn bản và hình ảnh, trên cơ sở các công nghệ nhận dạng hiện nay thì một hệ phân tích trang tài liệu sẽ thực hiện hai nhiệm vụ chính sau. Nhiệm vụ thứ nhất là xử lý các đối tượng văn bản như ký tự, chuỗi ký tự, các từ. Nhiệm vụ thứ hai là xử lý các đối tượng hình ảnh được tạo ra từ các hình vẽ, đường kẻ, biểu đồ, các lôgô công ty…Sau khi thực hiện thành công hai nhiệm vụ chính trên thì hệ phân tích trang tài liệu sẽ trích chọn ra các thông tin cần thiết đã phát hiện được và được lưu lại dưới dạng định dạng tài liệu khác như Word,Html… Ta có thể đưa ra sơ đồ khối liệt kê quá trình xử lý ảnh tài liệu như sau: 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 Phân tích sơ đồ trình bày Xác định độ nghiêng, dòng văn bản, các khối văn bản, đoạn văn bản Xử lý đối tượng ảnh Xử lý đường kẻ Đường thẳng, đường cong, góc Xử lý vùng và biểu tượng Vùng được tô Hình 1.1: Sơ đồ khối của việc xử lý tài liệu. Nguồn: Gorman(2009) Trên thực tế chúng ta thấy việc thiết kế và ứng dụng được một hệ phân tích tài liệu ảnh rất cần thiết, nó giúp chúng ta giải quyết nhiều vấn đề khi mà số lượng dữ liệu lớn. Chúng ta có thể xem một số ví dụ cụ thể dưới đây để thấy được sự cần thiết của việc phân tích trang tài liệu. Thứ nhất, thực tế khi ta làm Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 6 các công việc văn phòng thì hầu hết các tài liệu văn bản được tạo ra từ máy tính nhưng các máy tính có thể được cài đặt các phần mềm khác nhau, do đó có thể định dạng của chúng là không tương thích với nhau và kích thước cũng khác nhau. Khi đó sẽ cần có một hệ phân tích tài liệu ảnh có khả năng lựa chọn được một số thông tin cần thiết để có khả năng chuyển đổi giữa các định dạng trên máy tính khác nhau. Trường hợp thứ hai là tại các doanh nghiệp sản xuất lớn với hàng ngàn công nhân thì việc chấm công theo cách thông thường sẽ rất khó khăn. Tuy nhiên, việc này được khắc phục nhằm đem lại sự tiện lợi, chính xác và nhanh chóng bằng cách sử dụng máy chấm công bằng vân tay tích hợp công nghệ xử lý và so sánh dấu vân tay bảo đảm được công tác chấm công giờ làm không cần sự theo dõi trực tiếp của con người. Trong đó máy chấm công bằng vân tay ứng dụng hệ phân tích ảnh tài liệu. Ngày nay, Công nghệ OCR có khả năng nhận dạng văn bản chính xác đến hơn 90%, các tài liệu lưu trữ trong thư viện, các tài liệu kỹ thuật sẽ được chuyển đổi thành các tài liệu điện tử trên máy tính để thuận tiện hơn trong việc lưu trữ, chỉnh sửa, biên tập lại. Tuy nhiên tài liệu giấy cho đến nay vẫn được sử dụng rộng rãi vì phù hợp với mọi đối tượng, dễ thao tác, phổ biến vì tính trực quan. Do đó, vấn đề ở đây là chúng ta phải sử dụng công nghệ kết hợp các thuật toán để tích hợp các dữ liệu dưới dạng ảnh để đưa vào xử lý trong máy tính. Sau khi có dữ liệu, máy tính phải thực hiện các bước xử lý cơ bản như xử lý điểm ảnh, phân tích các thành phần đặc trưng để phát hiện đối tượng văn bản và đối tượng ảnh. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 7 Trang tài liệu Lấy dữ liệu 107 điểm ảnh 7500 hình bao ký tự, mỗi ký tự Xử lý điểm ảnh 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 Phân tích đặc trưng 7500x10 đặc trưng của ký tự Phân tích và nhận dạng đối tượng ảnh 1500x10 ký tự, 10 đoạn văn bản, 1 tiêu đề chính và 2 tiêu đề phụ Mô tả tài liệu 1000 vùng ảnh được tô với kích thước từ 20x20 đến 200x200 điểm ảnh 500x5 đặc trưng của đường thẳng và đường cong 10x5 đặc trưng vùng Phân tích và nhận dạng văn bản Hai sơ đồ và 1 ảnh lô gô của công ty,.v.v.. Hình 1.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. Nguồn: Gorman(2009) 1.1.1. Quá trình thu nhận ảnh Thông thường ảnh được thu thập bằng cách quét quang học thông qua máy quét hoặc bằng cách sao chép hình ảnh, những đoạn phim kỹ thuật số từ máy chụp hoặc máy quay phim rồi được lưu trữ vào máy tính dưới dạng một tập tin ảnh gồm có các yếu tố hình ảnh, hoặc điểm ảnh, đó là “nguyên liệu” đầu vào để phân tích ảnh tài liệu sau này. 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. Thí dụ, với một trang Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 8 ảnh tài liệu có kích thước 30x40 cm và có 140 điểm ảnh trong 1 centimet thì tạo được ảnh với 4200x5600 điểm ảnh. Do đó có thể thấy rằng một tài liệu ảnh chỉ bao gồ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.1.2. Các bƣớc xử lý điểm ảnh Sau khi đã thu thập được ảnh, người ta sẽ tiến hành quá trình xử lý điểm ảnh để làm cơ sở cho các quá trình phân tích và nhận dạng về sau. Cụ thể, thường thực hiện các công việc như chọn ngưỡng để chuyển ảnh đa cấp xám, ảnh màu về dạng ảnh nhị phân hay các thành phần trong ảnh tài liệu không cần quan tâm đến có thể được loại trừ bằng việc giảm nhiễu (noise reduction) và một số bước còn lại là phân đoạn, dò biên để xác định các vùng, các đặc trưng và đối tượng phù hợp. Sau khi đã thực hiện các công đoạn vừa rồi, thì người ta thường nén các dữ liệu bằng các phương pháp mã hóa chuỗi (chain coding) và biểu diễn ở dạng vectơ. 1.1.2.1. Phƣơng pháp nhị phân Đối với ảnh tài liệu dạng đa cấp xám có thông tin vốn là nhị phân như văn bản hoặc hình ảnh thì mục tiêu là phải chọn được một ngưỡng để tách thông tin nền và thông tin ảnh thành hai phần riêng biệt. Công việc này chính là để chọn được một ngưỡng thích hợp để tách thông tin ảnh tài liệu thành hai phần như vậy không phải là việc dễ dàng và sẽ càng khó khăn hơn đối với chúng ta khi gặp phải những thông tin ảnh mà độ tương phản giữa giá trị điểm ảnh nền và giá trị điểm ảnh văn bản là thấp. Khi đường nét của văn bản quá mỏng hoặc khi quét ảnh tài liệu không đủ cường độ sáng thích hợp thì cũng gây ra những khó khăn trong quá trình tìm ngưỡng. Vì vậy, người ta đã áp dụng nhiều phương pháp tách ngưỡng để khắc phục khó khăn trên. Trong đó phương pháp tách ngưỡng tự động thường được áp dụng. Cụ thể, giá trị ngưỡng α trong kỹ thuật Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 9 tách ngưỡng thường cho bởi người sử dụng. Kỹ thuật tìm, tách ngưỡng tự động nhằm tìm ra ngưỡng α một cách tự động dựa vào histogram theo nguyên lý trong vật lý là vật thể tách làm hai phần nếu tổng độ lệch trong từng phần là tối thiểu (Đỗ Năng Toàn-2008). Hình 1.3: Mô phỏng phương pháp nhị phân ảnh. (a): Biểu đồ Histogram của ảnh đa cấp xám ban đầu. (b): ngưỡng thấp. (c): ngưỡng phù hợp. (c): ngưỡng cao. Nguồn: Gorman (2009). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 10 1.1.2.2. Giảm nhiễu 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.. Các nhiễu làm giảm hoặc nhiều khi làm mất khả năng biểu lộ thông tin của đối tượng chính trong ảnh. Có nhiều loại nhiễu như nhiễu cộng, nhiễu nhân, nhiễu xung. Với mỗi loại nhiễu cần có các bộ lọc thích hợp. 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à lọc đồng hình. Sở dĩ như vậy vì 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 nào đó thông qua. Nhiễu có thể coi như sự đột biến của một điểm ảnh so với các điểm lân cận. 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. 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 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. 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 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 11 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.1.2.3. Phân đoạn Để phục vụ cho các bước xử lý ảnh tài liệu về sau, một trong những công đoạn khá quan trọng là phải tiến hành phân đoạn các đặc tính cơ bản có chứa trong hình ảnh thu nhận được. Cụ thể, việc phân đoạn được tiến hành với hai tiến trình chính. Thứ nhất là tách riêng biệt giữa các lớp của ảnh tài liệu, gồm lớp hình ảnh và lớp văn bản đối với trường hợp dữ liệu đầu vào có chứa cả hình ảnh và văn bản. Thứ hai là tiếp tục thực hiện các tiến trình phân tích trên các lớp vừa được tách ra. Với lớp hình ảnh thì phân định rõ các đối tượng hình vẽ, đường kẻ, biểu tượng cũng như các loại hình ảnh khác. Còn đối với lớp văn bản thì tiến hành xác định các ký tự, từ, đoạn văn, chia cột văn bản,…Một số hướng tiếp cận phương pháp phân khúc các đặc tính ảnh như dựa trên không gian đặc trưng, không gian ảnh hoặc là dựa trên mô hình vật lý. Tiếp đến là văn bản sẽ được tách thành các đoạn, các cột, các chuỗi, còn hình ảnh thì được tách thành các biểu tượng, đường kẻ và các đối tượng ảnh khác. Như vậy, tài liệu ảnh sau khi được thực hiện phân khúc sẽ quản lý được các đối tượng rất nhỏ như các phần cơ bản của ảnh. 1.1.2.4. Làm mảnh và xác định vùng Làm mảnh ảnh là một thao tác xử lý trong đó đối tượng ảnh được biểu diễn như những đường trục trung tâm hay còn gọi là lấy xương của đối tượng ảnh. Đây là kỹ thuật làm giảm bớt các điểm ảnh lân cận có cùng bản chất nhưng vẫn bảo đảm tính liên kết và liên thông của mỗi đối tượng ảnh. Xương được coi như là hình dạng cơ bản của một đối tượng, người ta có thể lấy lại được các thông tin về hình dạng nguyên bản của một đối tượng thông qua xương của nó. Việc tìm được xương của đối tượng ảnh sẽ giúp chúng ta giảm bớt tốn kém vì không cần thiết phải lưu trữ những thông tin không quan trọng trong quá trình Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 12 xử lý sau này, cũng như có thể đồng bộ hóa việc lưu trữ các đối tượng ảnh tương tự nhau ví dụ như những đoạn thẳng có thể vẽ với độ dày mỏng khác nhau nhưng khi lưu trữ và biểu diễn thì các đoạn này là giống nhau nhờ vào việc biểu diễn xương của chúng. Hình 1.4 biểu diễn ảnh nguyên bản bên trái và xương tương ứng của chúng phía bên phải. Đã có nhiều thuật toán được phát triển trong việc tìm xương nhằm từng bước khắc phục việc mất mát thông tin trong quá trình thực hiện. Người ta chia thành hai loại thuật toán tìm xương là tìm xương dựa trên làm mảnh (thinning) và tìm xương không dựa trên làm mảnh. Thuật toán làm mảnh là quá trình lặp duyệt và kiểm tra tất cả các điểm thuộc đối tượng. Trong mỗi lần lặp tất cả các điểm của đối tượng sẽ được kiểm tra: Nếu chúng thỏa mãn điều kiện xóa nào đó tuỳ thuộc vào mỗi thuật toán thì nó sẽ bị xóa đi. Quá trình được lặp lại cho đến khi không còn điểm biên nào được xóa. Đối tượng được bóc dần lớp biên cho đến khi nào bị thu mảnh lại chỉ còn các điểm biên. Người ta thường sử dụng thuật toán làm mảnh song song và thuật toán làm mảnh tuần tự. Nếu tìm xương không dựa trên làm mảnh thì để tách được xương của đối tượng, người ta sử dụng đường biên của đối tượng nhờ vào trục trung vị thông qua hai bước cơ bản: Bước thứ nhất là tính khoảng cách từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất và cần phải tính toán khoảng cách tới tất cả các điểm biên của ảnh. Bước thứ hai, khoảng cách ảnh đã được tính toán và các điểm ảnh có giá trị lớn nhất được xem là nằm trên xương của đối tượng (Đỗ Năng Toàn-2008). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 13 Hình 1.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. Nguồn: Gorman (2009). 1.1.2.5. Mã hóa CC và véctơ hóa Khi đã phát hiện được xương hoặc biên của đối tượng ảnh thì ta có thể biểu diễn ảnh theo một trong hai cách này. Nhưng đối tượng ảnh còn có thể được biểu diễn hiệu quả hơn bằng cách lưu trữ các điểm ảnh theo các giá trị ON và OFF, trong đó giá trị ON thể hiện giá trị của mỗi điểm ảnh và OFF biểu diễn giá trị điểm nền. Một trong những phương pháp lưu ảnh hiệu quả đó là lưu dưới dạng mã xích CC (Chain Code – Freeman 1974), trong đó các điểm có giá trị ON được biểu diễn thông qua tập các điểm láng giềng đi theo một hướng quy định. Thay vì phải lưu trữ vị trí của điểm ảnh có giá trị ON chúng ta sẽ lưu trữ hướng của các điểm láng giềng. Các điểm láng giềng của một điểm x là tất cả các điểm nằm liền kề với x thuộc ma trận 3 x 3 với điểm x là tâm. Có hai ưu điểm khi biểu Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/