Tài liệu Phát hiện cấu trúc bảng trong nhận dạng văn bản

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG ------------ BÙI THỊ THI PHÁT HIỆN CẤU TRÚC BẢNG TRONG NHẬN DẠNG VĂN BẢN Chuyên ngành : Khoa học máy tính Mã số : 60.48.01 Luận văn thạc sĩ khoa học máy tính Ngƣời hƣớng dẫn khoa học: TS. Nguyễn Đức Dũng Thái Nguyên, 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 http://www.lrc-tnu.edu.vn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 http://www.lrc-tnu.edu.vn LỜI CẢM ƠN ..................................................................................................6 DANH SÁCH CÁC HÌNH ẢNH.....................................................................7 MỞ ĐẦU ..........................................................................................................8 CHƢƠNG 1 ...................................................................................................10 TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH ....10 1.1. Tổng quan về xử lý ảnh .......................................................................10 1.1.1. Xử lý ảnh ......................................................................................10 1.1.2. Các bƣớc cơ bản trong xử lý ảnh ..................................................10 1.1.2.1. Thu nhận ảnh..........................................................................11 1.1.2.2. Tiền xử lý ...............................................................................11 1.1.2.3. Phân đoạn ảnh ........................................................................12 1.1.2.4. Biểu diễn và mô tả .................................................................13 1.1.2.5. Nhận dạng và nội suy ảnh ......................................................14 1.1.2.6. Cơ sở tri thức .........................................................................14 1.1.2.7. Trích chọn đặc điểm...............................................................15 1.2. Hệ phân tích tài liệu ảnh ......................................................................15 1.2.1. Tài liệu ảnh ...................................................................................15 1.2.2. Hệ phân tích trang tài liệu ảnh ......................................................16 1.2.3. Các bƣớc xử lý của một hệ phân tích tài liệu ảnh ........................17 1.2.3.1. Thu nhận dữ liệu ảnh .............................................................18 1.2.3.2. Tiền xử lý điểm ảnh ...............................................................18 1.2.3.2.1. Xử lý nhị phân ....................................................................18 1.2.3.2.2. Khử nhiễu ............................................................................19 1.2.3.3. Phân đoạn ảnh ........................................................................20 1.2.3.4. Làm mảnh và xác định vùng ..................................................20 1.2.3.5. Mã hóa Chain Code và vector hóa .........................................21 1.2.4. Phân tích đặc trƣng của tài liệu ảnh ..............................................22 1.2.5. Phân tích đối tƣợng văn bản trong tài liệu ảnh .............................23 1.2.5.1. Xác định góc nghiêng của văn bản ........................................23 1.2.5.2. Phân tích bố cục của trang tài liệu ảnh .................................25 CHƢƠNG 2 ...................................................................................................27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 http://www.lrc-tnu.edu.vn PHƢƠNG PHÁP PHÁT HIỆN BẢNG TESSERACT, PHÂN TÍCH BẢNG T-RECS TRONG TRANG ẢNH TÀI LIỆU .................................................27 2.1. Phƣơng pháp phát hiện bảng T-Recs trong trang ảnh tài liệu .............27 2.1.2. Phân tích cấu trúc văn bản thông qua phát hiện TAB-STOP ...........29 2.1.3. Phƣơng pháp phát hiện bảng Tesseract ............................................31 Thuật toán phát hiện bảng đƣợc xây dựng với hai thành phần của mô đun phân tích cấu trúc sau: ................................................................................31 2.1.3.1. Xác định các phần của bảng ......................................................32 2.1.3.2. Xác định các trang cột phân tách ...............................................34 2.1.3.3 Xác định các cột bảng .................................................................34 2.1.3.4. Đánh dấu các vùng bảng ............................................................34 2.1.3.5. Loại bỏ các lỗi ...........................................................................35 2.2. Phƣơng pháp phân tích bảng T-Recs ......................................................35 2.2.1. Giới thiệu ...........................................................................................35 2.2.2. Thuật toán phân đoạn khởi tạo .........................................................37 CHƢƠNG 3 ...................................................................................................39 CÀI ĐẶT THỬ NGHIỆM VÀ ĐÁNH GIÁ..................................................39 3.1. Môi trƣờng cài đặt và dữ liệu kiểm thử ...............................................39 3.2. Trình tự thực hiện của thuật toán ........................................................39 3.3. Kết quả thực nghiệm ...........................................................................39 3.4. Đánh giá ..............................................................................................45 KẾT LUẬN ....................................................................................................51 TÀI LIỆU THAM KHẢO..............................................................................52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Trƣớc hết em muốn đƣợc gửi lời cảm ơn đến các thầy, cô giáo ở Viện Công nghệ thông tin, trƣờng ĐH Công nghệ Thông tin và Truyền thông… đã quan tâm tổ chức chỉ đạo, quản lý lớp, trực tiếp giảng dạy khóa học của chúng em. Em xin đƣợc bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS. Nguyễn Đức Dũng – Viện Công nghệ Thông tin – Viện Khoa học Việt Nam, ngƣời thầy đã tận tình giúp đỡ, chỉ bảo em trong suốt quá trình tìm hiểu, viết đề cƣơng và phát triển luận văn. Em xin đƣợc cảm ơn thầy giáo Lê Đức Hiếu – Viện Công nghệ Thông tin – Viện Khoa học Việt Nam ngƣời thầy đã tận tình giúp đỡ, chỉ bảo em trong suốt quá trình phát triển phần cài đặt, thử nghiệm. Mặc dù đã có cố gắng song khả năng của bản thân em còn rất nhiều hạn chế nên luận văn không tránh khỏi những thiếu sót. Em rất mong chỉ bảo, góp ý của các thầy cô giáo và các bạn để luận văn của em đƣợ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 6 http://www.lrc-tnu.edu.vn DANH SÁCH CÁC HÌNH ẢNH Hình 1.1 Quá trình xử lý ảnh Hình 1.2 Các bước cơ bản trong quá trình xử lý ảnh Hình 1.3 Lân cận các điểm ảnh của tọa độ (x, y) Hình 1.4 Văn bản bị nghiêng sau khi được quét qua máy quét Hình 2.1 Kết quả đầu ra của các bước khác nhau của các mô-đun phân tích trí trong tài liệu ảnh Hình 2.2 Kết qủa của các bước khác nhau trong việc phân tích bố trí của c vùng bảng của Tesseract’s Hình 2.3 Kết quả của các bước khác nhau trong thuật toán phát hiện bảng Hình 2.4 Ví dụ minh họa tư tưởng của thuật toán khởi tạo Hình 2.5 Thuật toán khởi tạo đối với một đoạn văn bản Hình 3.1 Phát hiện một phần Hình 3.2 Chia nhỏ bảng Hình 3.3 Gộp bảng với vùng văn bản Hình 3.4 Phát hiện sai Hình 3.5 Kết quả thực nghiệm 1 Hình 3.6 Kết quả thực nghiệm 2 Hình 3.7 Kết quả thực nghiệm 3 Hình 3.8 Kết quả thực nghiệm 4 Hình 3.9 Kết quả thực nghiệm 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 http://www.lrc-tnu.edu.vn MỞ ĐẦU Xử lý ảnh là một trong những chuyên ngành quan trọng và lâu đời của Công nghệ thông tin. Xử lý ảnh đƣợc áp dụng trong nhiều lĩnh khác nhau nhƣ y học, vật lý, hoá học, tìm kiếm tội phạm, trong quân sự và trong một số lĩnh vực khác.... Phần lớn con ngƣời thu nhận thông tin bằng thị giác, cụ thể đó là các hình ảnh. Vì vậy xử lý ảnh là vấn đề không thể thiếu và hết sức quan trọng để thu đƣợc hình ảnh tốt hơn, đẹp hơn, nhằm đáp ứng yêu cầu thông tin khác nhau của ngƣời nhận. Một trong những lĩnh vực của xử lý ảnh đó là xử lý, nhận dạng thông tin chứa đựng trong các tài liệu ảnh, tài liệu ảnh đa dạng, phức tạp không đơn thuần là các ký tự văn bản, hình vẽ, hình ảnh, bảng biểu…Trong đó phát hiện các bảng trong các tài liệu hình ảnh là một khâu rất quan trọng vì không những chúng ta phải xác định các thông tin chứa trong các bảng mà hầu hết các phƣơng pháp hiện nay đều gặp khó khăn trong việc nhận diện các bảng. Các phƣơng pháp phát hiện các bảng hiện nay tập trung chủ yếu vào các bảng chỉ có một cột mà nó không làm việc tốt với các bảng có nhiều dạng khác nhau. Xuất phát từ thực tế đó, luận văn lựa chọn đề tài “Phát hiện cấu trúc bảng trong nhận dạng văn bản”. Mục đích chính của đề tài là tìm hiểu các phƣơng pháp phát hiện cấu trúc bảng, trình bày, cài đặt một thuật toán phát hiện các bảng với độ chính xác cao áp dụng cho các dạng tài liệu phức tạp nhƣ: các báo cáo của các công ty, các bài báo, các trang tạp chí,… Ngoài phần mở đầu, kết luận luận văn đƣợc chia làm 3 chƣơng cụ thể nhƣ sau: Chƣơng 1: Tổng quan về xử lý ảnh và hệ phân tích tài liệu ảnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 http://www.lrc-tnu.edu.vn Trong chƣơng này trình bày sơ lƣợc về xử lý ảnh, giới thiệu các bƣớc xử lý trong một hệ thống xử lý ảnh, 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 2: Phƣơng pháp phát hiện bảng Tesseract, phân tích bảng TRecs trong trang tài liệu ảnh Trình bày các phƣơng pháp phát hiện bảng, thuật toán phát hiện cấu trúc bảng. Minh họa phát hiện cấu trúc bảng trong trang ảnh tài liệu. Tìm hiểu về thuật toán T-Recs do Thomas G.Kieninger [7] đề xuất. Chƣơng 3: Cài đặt thử nghiệm và đánh giá Mô tả chi tiết quá trình cài đặt thử nghiệm thuật toán, cũng nhƣ đánh giá các kết quả đạt đƣợc trên bộ dữ liệu thu thập đƣợc. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 http://www.lrc-tnu.edu.vn CHƢƠNG 1 TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH 1.1. Tổng quan về xử lý ảnh 1.1.1. Xử lý ảnh Quá trình xử lý nhận dạng ảnh là một quá trình thao tác nhằm biến đổi một ảnh đầu vào để cho ra một kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh "tốt hơn" hoặc một kết luận[1]. Ảnh “Tốt hơn” Ảnh Xử lý ảnh Kết luận Hình 1.1: Quá trình xử lý ảnh Nhƣ vậy mục tiêu của xử lý ảnh có thể chia làm ba hƣớng nhƣ sau: - Xử lý ảnh ban đầu để cho ra một ảnh mới tốt hơn theo một mong muốn của ngƣời dùng (ví dụ: ảnh mờ cần xử lý để đƣợc rõ hơn). - Phân tích ảnh để thu đƣợc thông tin nào đó giúp cho việc phân loại và nhận biết ảnh (ví dụ: phân tích ảnh vân tay để trích chọn các đặc trƣng vân tay). - Từ ảnh đầu vào mà có những nhận xét, kết luận ở mức cao hơn, sâu hơn (ví dụ: ảnh một tai nạn giao thông phác họa hiện trƣờng tai nạn). 1.1.2. Các bƣớc cơ bản trong xử lý ảnh Quá trình xử lý một ảnh đầu vào nhằm thu đƣợc một ảnh đầu ra mong muốn thƣờng phải trải qua rất nhiều bƣớc khác nhau [2]. Các bƣớc cơ bản của một quá trình xử lý ảnh đƣợc thể hiện thông qua hình sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 http://www.lrc-tnu.edu.vn Biểu diễn và mô tả Phân đoạn ảnh Tiền xử lý ảnh CƠ SỞ TRI THỨC Nhận dạng và nội suy Thu nhận ảnh (Scanner, sensor, camera) Hình 1.2: Các bước cơ bản trong quá trình xử lý ảnh 1.1.2.1. Thu nhận ảnh Đây là bƣớc đầu tiên trong quá trình xử lý ảnh. Để thực hiện điều này, ta cần có bộ thu ảnh và khả năng số hoá những tín hiệu liên tục đƣợc sinh ra bởi bộ thu ảnh đó. Bộ thu ảnh ở đây có thể là máy chụp ảnh đơn sắc hay màu, máy quét ảnh, máy quay... Trong trƣờng hợp bộ thu ảnh cung cấp chƣa phải là dạng số hoá ta còn phải chuyển đổi hay số hoá ảnh. Quá trình chuyển đổi ADC (Analog to Digital Converter) để thu nhận dạng số hoá của ảnh. Mặc dù đây chỉ là công đoạn đầu tiên song kết quả của nó có ảnh hƣởng rất nhiều đến công đoạn kế tiếp. 1.1.2.2. Tiền xử lý Ở bƣớc này, ảnh sẽ đƣợc cải thiện về độ tƣơng phản, khử nhiễu, khôi phục ảnh, nắn chỉnh hỉnh học... Với mục đích làm cho chất lƣợng ảnh trở lên tốt hơn nữa, chuẩn bị cho các bƣớc xử lý phức tạp kế tiếp sau đó. * Khử nhiễu: Đặc trƣng của nhiễu hệ thống là tính tuần hoàn. Do vậy, có thể khử nhiễu này bằng việc sử dụng phép biến đổi Fourier và loại bỏ các đỉnh điểm. Đối với nhiễu ngẫu nhiên, trƣờng hợp đơn giản là các vết bẩn tƣơng ứng với các điểm sáng hay tối, có thể khử bằng phƣơng pháp nội suy, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 http://www.lrc-tnu.edu.vn lọc trung vị và trung bình. * Chỉnh mức xám: Đây là kỹ thuật nhằm chỉnh sửa tính không đồng đều của thiết bị thu nhận hoặc độ tƣơng phản giữa các vùng ảnh. * Chỉnh tán xạ: Ảnh thu nhận đƣợc từ các thiết bị quang học hay điện tử có thể bị mờ, nhoè. Phƣơng pháp biến đổi Fourier dựa trên tích chập của ảnh với hàm tán xạ cho phép giải quyết việc hiệu chỉnh này. * Nắn chỉnh hình học: Những biến dạng hình học thƣờng do các thiết bị điện tử và quang học gây ra. Do đó, phƣơng pháp hiệu chỉnh ảnh dựa trên mô hình đƣợc mô tả dƣới dạng phƣơng trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tƣởng f(x',y') nhƣ sau:  x'  hx ( x, y)   y'  h y x, y  Trong đó hx, hy là các phƣơng trình tuyến tính (biến dạng do phối cảnh) hay bậc hai (biến dạng do ống kính camera). 1.1.2.3. Phân đoạn ảnh Phân đoạn ảnh là một thao tác ở mức thấp trong toàn bộ quá trình xử lý ảnh. Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và đồng nhất với nhau hay nói cách khác là xác định các biên của các vùng ảnh đó. Các vùng ảnh đồng nhất này thông thƣờng sẽ tƣơng ứng với tòan bộ hay từng phần của các đối tƣợng thật sự bên trong ảnh. Vì thế, trong hầu hết các ứng dụng của lĩnh vực xử lý ảnh, thị giác máy tính, phân đoạn ảnh luôn đóng một vai trò cơ bản và thƣờng là bƣớc tiền xử lý đầu tiên trong toàn bộ quá trình trƣớc khi thực hiện các thao tác khác ở mức cao hơn nhƣ nhận dạng đối tƣợng, biểu diễn đối tƣợng, nén ảnh dựa trên đối tƣợng, hay truy vấn ảnh dựa vào nội dung. Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần khác nhau hay còn gọi là các đối tƣợng để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận dạng chữ (hoặc mã vạch) trên phong bì thƣ cho mục đích Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 http://www.lrc-tnu.edu.vn phân loại bƣu phẩm, cần chia các câu, chữ về địa chỉ hoặc tên ngƣời thành các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. Đây là phần phức tạp khó khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này. Kết quả của bƣớc phân đoạn ảnh thƣờng đƣợc cho dƣới dạng dữ liệu điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh hoặc tập hợp tất cả các điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trƣờng hợp, sự chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý trong máy tính là hết sức cần thiết, nghĩa là nên biểu diễn một vùng ảnh dƣới dạng biên hay dƣới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh thuộc về nó. - Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan tâm đến các đặc trƣng hình dạng bên ngoài của đối tƣợng, ví dụ nhƣ các góc cạnh và điểm uốn trên biên. - Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính chất bên trong của đối tƣợng. Ví dụ nhƣ vân ảnh hoặc cấu trúc xƣơng của nó. Và trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết. 1.1.2.4. Biểu diễn và mô tả a) Biểu diễn Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã phân đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trƣng gắn với việc tách các đặc tính của ảnh dƣới dạng các thông tin định lƣợng hoặc làm cơ sở để phân biệt lớp đối tƣợng này với đối tƣợng khác trong phạm vi ảnh nhận đƣợc. Ví dụ: trong nhận dạng ký tự trên phong bì thƣ, chúng ta miêu tả các đặc trƣng của từng ký tự giúp phân biệt ký tự này với ký tự khác. b) Mô tả Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 http://www.lrc-tnu.edu.vn Ảnh sau khi số hoá sẽ đƣợc lƣu vào bộ nhớ, hoặc chuyển sang các khâu tiếp theo để phân tích. Nếu lƣu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lƣợng bộ nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông thƣờng, các ảnh thô đó đƣợc đặc tả (biểu diễn) lại (hay đơn giản là mã hoá) theo các đặc điểm của ảnh đƣợc gọi là các đặc trƣng ảnh nhƣ: biên ảnh, vùng ảnh. 1.1.2.5. Nhận dạng và nội suy ảnh Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thƣờng thu đƣợc bằng cách so sánh với mẫu chuẩn đã đƣợc lọc (hoặc lƣu) từ trƣớc. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ số và nét gạch ngang trên phong bì thƣ có thể đƣợc nội suy thành mã điện thoại. Có nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình toán học về ảnh đƣợc phân theo hai loại nhận dạng ảnh cơ bản: - Nhận dạng theo tham số. - Nhận dạng theo cấu trúc. Một số đối tƣợng nhận dạng khá phổ biến hiện nay đang đƣợc áp dụng trong khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay, chữ ký điện tử), nhận dạng văn bản, nhận dạng vân tay, nhận dạng mã vạch, nhận dạng mặt ngƣời… 1.1.2.6. Cơ sở tri thức Ảnh là một đối tƣợng khá phức tạp về đƣờng nét, độ sáng tối, dung lƣợng điểm ảnh, môi trƣờng để thu ảnh phong phú kéo theo nhiễu. Trong nhiều khâu xử lý và phân tích ảnh ngoài việc đơn giản hóa 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ử lý ả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ệ con ngƣời. Vì Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 http://www.lrc-tnu.edu.vn vậy, ở đây các cơ sở tri thức đƣợc phát huy. 1.1.2.7. Trích chọn đặc điểm Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong cuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc điểm đặc trƣng cần thiết thƣờng là nhiều, không thể do chuyên gia đề xuất, mà phải đƣợc trích chọn dựa trên các thủ tục phân tích dữ liệu. Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tƣợng ảnh chính xác, với tốc độ tính toán cao và dung lƣợng nhớ lƣu trữ giảm xuống. Các đặc điểm của đối tƣợng đƣợc trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây: - Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm uốn v.v.. - Đặc điểm biến đổi: Các đặc điểm loại này đƣợc trích chọn bằng việc thực hiện lọc vùng. Các bộ vùng đƣợc gọi là “mặt nạ đặc điểm” thƣờng là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn ...) - Đặc điểm biên và đường biên: Đặc trƣng cho đƣờng biên của đối tƣợng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến đƣợc dùng khi nhận dạng đối tƣợng. Các đặc điểm này có thể đƣợc trích chọn nhờ toán tử Gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo không” ... 1.2. Hệ phân tích tài liệu ảnh 1.2.1. Tài liệu ảnh Tài liệu ảnh là các file ảnh đã đƣợc số hóa thu đƣợc bằng cách: quét các trang tài liệu, chụp ảnh, máy fax, hoặc từ vệ tinh, các file ảnh này đƣợc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 http://www.lrc-tnu.edu.vn lƣu trữ trong máy tính. Ảnh tài liệu có nhiều loại: đen trắng, ảnh màu, ảnh đa cấp xám,… 1.2.2. Hệ phân tích trang tài liệu ảnh - Hệ phân tích trang tài liệu ảnh: 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ụ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. - Một hệ phân tích tài liệu ảnh có thể chia làm 2 phần: xử lý văn bản và xử lý các đối tƣợng ảnh. * Xử lý văn bản: + Đối tƣợng văn bản: ký tự, chuỗi ký tự, các từ. + Các bƣớc xử lý văn bản: - Xác định độ nghiêng của tài liệu (Độ nghiêng hay độ xiên của tài liệu ảnh là do khi quét vào từ máy quét ngƣời dùng đặt lệch tài liệu). - Xác định các cột, các đoạn văn bản, các dòng văn bản, các từ. - Nhận dạng văn bản. * Xử lý các đối tƣợng ảnh: + Đối tƣợng ảnh: các hình vẽ, các đƣờng kẻ trong sơ đồ, các đƣờng kẻ phân tách giữa các đoạn văn bản. 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 tách ra và đƣợc biểu diễn dƣới dạng một tài liệu định dạng khác, ví dụ: 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 1.4 [5]: Xử lý tài liệu Xử lý văn bản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 Xử lý đối tƣợng http://www.lrc-tnu.edu.vn 1.2.3. Các bƣớc xử lý của một hệ phân tích tài liệu ảnh Để mô tả các bƣớc xử lý cho một hệ phân tích tài liệu ảnh ta có hình 1.5 [5]. 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, sau đó phần nhận dạng văn bản, ả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 17 http://www.lrc-tnu.edu.vn 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 dạng đối tƣợng văn bản Phân tích và nhận dạng đối tƣợng ảnh Mô tả tài liệu Hình 1.5 Sơ đồ quá trình phân tích trang tài liệu ảnh 1.2.3.1. Thu nhận dữ liệu ảnh 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, và đƣợc lƣu trữ. Ở độ phân giải thông thƣờng thì có 120 điểm ảnh trên 1centimet và với một trang có kích thƣớc 20×30cm thì tạo ra một ảnh với 2400×3600 đ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 thông tin cần thiết. 1.2.3.2. Tiền xử lý điểm ảnh 1.2.3.2.1. Xử lý nhị phân - Mục đích: tự động chọn một ngƣỡng cần thiết để tách ra làm 2 phần: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 http://www.lrc-tnu.edu.vn thông tin ảnh và thông tin nền. Quá trình xử lý nhị phân sẽ gặp khó khăn trong các trƣờng hợp khi độ tƣơng phản giữa các giá trị các điểm ảnh văn bản và nền là thấp (ví dụ 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. Nhiều phƣơng pháp đã đƣợc phát triển để khắc phục những hạn chế trên, ví dụ phƣơng pháp tách ngƣỡng tự động để tìm ra các giá trị  thích hợp để chia ảnh thành 2 phần. 1.2.3.2.2. Khử nhiễu - Nhiễu luôn là một vấn đề trong hầu hết các bài toán đọc hiểu tài liệu. Nguyên nhân sinh ra nhiễu do quá trình quét tài liệu, quá trình sao chép, sự thoái hóa của tài liệu theo thời gian. 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. Trong kỹ thuật lọc, ngƣời ta sử dụng một mặt nạ và di chuyển khắp ảnh gốc. Tuỳ theo cách tổ hợp điểm đang xét với các điểm lân cận mà ta có kỹ thuật lọc tuyến tính hay phi tuyến. Điểm ảnh chịu tác động của biến đổi là điểm ở tâm mặt nạ. Trong kỹ thuật lọc tuyến tính, ảnh thu đƣợc sẽ là tổng trọng số hay là trung bình trọng số các điểm lân cận với nhân cuộn hay mặt nạ. Khác với lọc tuyến tính, kỹ thuật lọc phi tuyến coi một điểm ảnh kết quả không phải là tổ hợp tuyến tính của các điểm lân cận. Bộ lọc phi tuyến thƣờng dùng là lọc trung vị mang tên Tuckey. Với bộ lọc trung vị các điểm ảnh sẽ đƣợc thay thế bởi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 http://www.lrc-tnu.edu.vn 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ị”. 1.2.3.3. Phân đoạn ảnh Quá trình phân đoạn ảnh đƣợc thực hiện làm hai giai đoạn. Giai đoạn thứ nhất, tách các lớp văn bản và ảnh riêng biệt nếu nhƣ trong tài liệu có chứa cả văn bản và ảnh. Giai đoạn thứ hai là thực hiện phân tách trên hai lớp đối tƣợng vừa tách ở trên, với văn bản xác định các cột, các đoạn văn bản, các từ và các kí tự; với lớp đối tƣợng ảnh thực hiện phân tách các biểu tƣợng, các hình vẽ, các đƣờng kẻ và các hình ảnh. Chẳng hạn nhƣ một tài liệu ảnh có chứa các đoạn văn bản và các hình minh họa giống nhƣ một trang tạp chí, đầu tiên văn bản và hình ả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ẽ đƣợc 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. 1.2.3.4. Làm mảnh và xác định vùng Thuật toán làm mảnh làm mảnh ảnh số nhị phân là một trong các thuật toán quan trọng trong xử lý ảnh và nhận dạng. 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 nhƣ chúng thỏa mãn điều kiện xóa nào đó tùy 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 điểm biên. 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. Xƣơng đƣợc coi nhƣ hình dạng cơ bản của một đối tƣợng, với số ít các điểm ảnh cơ bản. Ta có thể lấy đƣợc các thông tin về hình dạng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 http://www.lrc-tnu.edu.vn nguyên bản của một đối tƣợng thông qua xƣơng. Thuật ngữ “xƣơng” đƣợc sử dụng để chỉ kết qủa của việc làm mảnh ảnh mà không cần quan tâm đến hình dạng chuẩn của ảnh ban đầu hoặc các phƣơng thức sử dụng để làm mảnh. Xƣơng chứa những thông tin bất biến về cấu trúc của ảnh giúp cho quá trình nhận dạng và vector hóa sau này. 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 cần 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. Nói chung với các đối tƣợng có kích thƣớc lớn thì sử dụng phƣơng pháp dò biên là 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 nét kết nối dài thì sử dụng phƣơng pháp làm mảnh là 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 logo thì áp dụng phƣơng pháp dò biên là 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ì 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 chứ không áp dụng phƣơng pháp làm mảnh hay dò biên. 1.2.3.5. Mã hóa Chain Code và vector hóa Khi một đối tƣợng ảnh đƣợc biểu diễn dƣới dạng xƣơng của ảnh hay bằng đƣờng viền, chúng có thể biểu diễn một cách hiệu quả hơn là lƣu các điểm ảnh một cách đơn giản các giá trị ON và OFF. Một trong những phƣơng pháp lƣu ảnh hiệu quả đó là phƣơng pháp mã xích CC (Chain Code), 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ữ vị trí của điểm ảnh có giá trị ON chúng ta sẽ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 http://www.lrc-tnu.edu.vn