Tài liệu Ứng dụng vài kỹ thuật xử lý ảnh trong phân tích chứng minh thư nhân dân

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ ĐỨC HIẾU ỨNG DỤNG MỘT SỐ KỸ THUẬT XỬ LÝ ẢNH TRONG PHÂN TÍCH CHỨNG MINH THƯ NHÂN DÂN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2012 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ ĐỨC HIẾU ỨNG DỤNG MỘT SỐ KỸ THUẬT XỬ LÝ ẢNH TRONG PHÂN TÍCH CHỨNG MINH THƯ NHÂN DÂN Ngành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 60 48 10 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 Hà Nội – 2012 -4- Mục lục Lời cam đoan ...................................................................................................................2 Lời cảm ơn .......................................................................................................................3 Mục lục ............................................................................................................................4 Danh mục hình vẽ ............................................................................................................6 Danh mục bảng biểu ........................................................................................................8 Danh mục thuật toán ........................................................................................................9 Mở đầu ...........................................................................................................................10 Chương 1: Tổng quan về phân tích ảnh tài liệu ............................................................12 1.1. Tổng quan về hệ thống nhận dạng ảnh tài liệu ...................................................12 1.2. Phân tích ảnh tài liệu ..........................................................................................13 1.2.1. Bố cục tự nhiên và cấu trúc lôgic ................................................................14 1.2.2. Phân loại ảnh tài liệu ...................................................................................15 1.3. Phân tích bố cục..................................................................................................16 1.3.1. Hướng tiếp cận trên-xuống ..........................................................................17 1.3.2. Hướng tiếp cận dưới-lên ..............................................................................18 1.4. Phân tích cấu trúc ...............................................................................................19 1.5. Kết luận chương .................................................................................................20 Chương 2: Một số thuật toán tiền xử lý ảnh ..................................................................21 2.1. Nhị phân ảnh .......................................................................................................21 2.1.1. Phân loại các phương pháp xác định ngưỡng T ..........................................23 2.1.2. Một số phương pháp xác định ngưỡng T ....................................................23 2.1.3. Nhận xét .......................................................................................................26 2.2. Hiệu chỉnh độ nghiêng của trang văn bản ..........................................................28 2.2.1. Phương pháp dựa trên biến đổi Hough ........................................................29 2.2.2. Phương pháp láng giềng gần nhất (nearest neighbours) .............................31 2.2.3. Phương pháp sử dụng chiếu nghiêng (project profile) ................................33 2.2.4. Nhận xét .......................................................................................................34 2.3. Các toán tử hình thái (Morphological operations) .............................................34 2.4. Kết luận chương .................................................................................................37 -5Chương 3: Phương pháp phân tích Giấy chứng minh nhân dân ...................................38 3.1. Giới thiệu bài toán ..............................................................................................38 3.2. Tách các trường thông tin ở mặt trước ...............................................................39 3.2.1. Tiền xử lý ảnh ..............................................................................................40 3.2.2. Tách trường Số CMND ...............................................................................43 3.2.3. Tách các trường thông tin còn lại ................................................................46 3.3. Tách các trường thông tin ở mặt sau ..................................................................51 3.3.1. Tiền xử lý ảnh ..............................................................................................51 3.3.2. Xác định cấu trúc bảng ................................................................................52 3.3.3. Tách trường thông tin ..................................................................................53 3.4. Kết luận chương .................................................................................................54 Chương 4: Cài đặt thử nghiệm và đánh giá ...................................................................55 4.1. Môi trường cài đặt ..............................................................................................55 4.2. Dữ liệu kiểm thử .................................................................................................55 4.3. Kết quả thực nghiệm...........................................................................................55 4.4. Đánh giá ..............................................................................................................56 Kết luận..........................................................................................................................58 Tài liệu tham khảo .........................................................................................................59 -6- Danh mục hình vẽ Hình 1. 1 Sơ đồ hệ thống nhận dạng .............................................................................12 Hình 1. 2 Ví dụ ảnh tài liệu có bố cục phức tạp ............................................................14 Hình 1. 3 Sơ đồ hệ thống phân tích bố cục và cấu trúc ảnh tài liệu ..............................15 Hình 1. 4 Các loại ảnh tài liệu .......................................................................................16 Hình 1. 5 Hình chiếu ngang và dọc của ảnh tài liệu ......................................................17 Hình 1. 6 Thuật toán whitespace ...................................................................................18 Hình 1. 7 Thuật toán Docstrum .....................................................................................19 Hình 1. 8 Thuật toán Voronoi........................................................................................20 Hình 2. 1 Nhị phân ảnh..................................................................................................22 Hình 2. 2 So sánh các phương pháp nhị phân ảnh đối với có độ sáng thay đổi ............27 Hình 2. 3 So sánh các phương pháp nhị phân ảnh đối với ảnh Chứng minh nhân dân 28 Hình 2. 4 Biến đổ Hough ...............................................................................................30 Hình 2. 5 Phương pháp láng giếng gần nhất .................................................................32 Hình 2. 6 Phương pháp chiếu nghiêng ..........................................................................33 Hình 2. 7 Phần tử cấu trúc 3x3 ......................................................................................34 Hình 2. 8 Phép giãn ảnh với phần tử cấu trúc 3x3 ........................................................35 Hình 2. 9 Phép co ảnh với phần tử cấu trúc 3x3 ...........................................................36 Hình 2. 10 Phép toán opening .......................................................................................36 Hình 2. 11 Phép toán closing .........................................................................................37 Hinh 3. 1 Mẫu “Giấy Chứng minh nhân dân” ...............................................................38 Hinh 3. 2 Vùng thông tin cần tách ở mặt trước CMND ................................................39 Hinh 3. 3 Tiền xử lý ảnh mặt trước CMND ..................................................................41 Hinh 3. 4 Xác định vùng Số CMND .............................................................................44 Hinh 3. 5 Phân đoạn vùng Số CMND ...........................................................................45 Hinh 3. 6 Mặt nạ dòng mặt trước ..................................................................................47 Hinh 3. 7 Xoá phần tiêu đề ............................................................................................49 Hinh 3. 8 Kết quả lấy lại các ký tự bị mất .....................................................................50 Hinh 3. 9 Các vùng thông tin cần tách ở mặt sau ..........................................................51 Hinh 3. 10 Tiền xử lý mặt sau CMND ..........................................................................52 -7Hinh 3. 11 Xác định cấu trúc bảng ................................................................................53 Hình 4. 1 So khớp khối đúng và khối tách được ...........................................................56 Hình 4. 2 Trường hợp tách bị lỗi ...................................................................................57 -8- Danh mục bảng biểu Bảng 2. 1 So sánh phương pháp Niblack và Otsu .........................................................28 Bảng 3. 1 Đặc trưng các trường thông tin ở mặt trước CMND ....................................40 Bảng 4. 1 Kết quả phân tích ảnh CMND.......................................................................56 -9- Danh mục thuật toán Thuật toán 2.1. Nhị phân ảnh ....................................................................................21 Thuật toán 2.2. Phương pháp phân ngưỡng Niblack.................................................23 Thuật toán 2.3. Phương pháp phân ngưỡng Otsu ......................................................25 Thuật toán 2.4. Hiệu chỉnh độ nghiêng của ảnh tài liệu ............................................29 Thuật toán 2.5. Xoay ảnh ..........................................................................................29 Thuật toán 2.6. Xác định góc nghiêng dựa vào biến đổi Hough ...............................30 Thuật toán 2.7. Phương pháp láng giềng gần nhất ....................................................31 Thuật toán 2.8. Sử dụng chiếu nghiêng để xác định góc nghiêng ............................33 Thuật toán 3.1. Xác định các vùng có thể là Trường Số CMND ..............................43 Thuật toán 3.2. Tìm và tách trường Số CMND.........................................................44 Thuật toán 3.3. Phân đoạn vùng Số CMND ..............................................................45 Thuật toán 3.4. Ước lượng bề dày đường lượn sóng ................................................46 Thuật toán 3.5. Tách các ký tự thuộc mỗi dòng ........................................................48 Thuật toán 3.6. Xoá phần tiêu đề ..............................................................................49 Thuật toán 3.7. Tìm các đường kẻ ngang trong ảnh..................................................52 -10- Mở đầu Nhận dạng mẫu là một ngành khoa học của học máy (hay trí tuệ nhân tạo) nhằm phân loại dữ liệu (các mẫu) vào một số lớp [4]. Mẫu có thể là bất kỳ thực thể nào cần được nhận ra, ví dụ: chữ in, chữ viết tay, vân tay, khuôn mặt, tiếng nói, hình dạng,… Cùng với sự phát triển của khoa học kỹ thuật, các ứng dụng của nhận dạng mẫu ngày càng được mở rộng, từ việc tự động hoá một số quy trình trong sản xuất công nghiệp cho đến dự báo thời tiết, dự báo cháy rừng hay là một phần quan trọng trong các hệ thống máy tính thông minh… Một trong những ứng dụng phổ biến của nhận dạng mẫu hiện nay là phân tích và nhận dạng ảnh tài liệu (có nguồn gốc từ hệ thống nhận dạng ký tự quang học), nhằm số hoá các trang tài liệu giấy như sách, báo, tạp chí,… Cho đến nay, bài toán phân tích và nhận dạng ảnh tài liệu đã được giải quyết gần như trọn vẹn và cũng đã có những sản phẩm thương mại, như VnDOCR của Viện công nghệ thông tin hay FineReader của hãng ABBYY,… Bên cạnh lớp bài toán phân tích và nhận dạng ảnh tài liệu một cách tổng quát ở trên còn có lớp bài toán riêng biệt cho từng ngành, từng lĩnh vực cụ thể, như: phân tích và nhận dạng bảng biểu, phiếu điều tra, mẫu điền thông tin, danh thiếp, hộ chiếu,… Đối với lớp bài toán này thì việc phân tích cấu trúc của ảnh tài liệu là đặc biệt quan trọng, bởi vì nó sẽ quyết định đến việc tách và nhận dạng chính xác các trường thông tin cần thiết cho từng ứng dụng cụ thể. Trên thế giới đã có nhiều sản phẩm phần mềm phân tích và nhận dạng ảnh thẻ chứa thông tin cá nhân (như hộ chiếu, danh thiếp,…) và được ứng dụng trong nhiều lĩnh vực, như: làm thủ tục hải quan, các giao dịch ở các cửa hàng, khách sạn,… Ở Việt Nam loại thẻ chứa thông tin các nhân được sử dụng nhiểu nhất là Giấy chứng minh nhân dân (CMND), nhưng hiện nay chưa có một giải pháp nào được đưa ra cho việc phân tích và nhận dạng CMND. Do đó, trong luận văn này, tôi xin đề xuất một phương pháp phân tích ảnh CMND dựa trên việc phân tích và nhận dạng biểu mẫu. Luận văn gồm bốn chương với các nội dung như sau: Chương 1: Tổng quan về phân tích ảnh tài liệu. Giới thiệu tổng quan về hệ thống nhận dạng ảnh tài liệu nói chung và hệ thống phân tích ảnh tài liệu nói riêng. Giới thiệu các hướng tiếp cận trong phân tích bố cục và cấu trúc của ảnh tài liệu. Chương 2: Một số thuật toán tiền xử lý ảnh. Giới thiệu một số thuật toán tiền xử lý ảnh thường được áp dụng trong các hệ thống phân tích và nhận dạng ảnh tài liệu, như: nhị phân ảnh, căn chỉnh độ nghiêng, các toán tử hình thái. -11Chương 3: Phương pháp phân tích Giấy chứng minh nhân dân. Giới thiệu bài toán và các vấn đề cần giải quyết, từ đó áp dụng các kỹ thuật xử lý ảnh và phân tích ảnh tài liệu ở trên để phân tích ảnh CMND. Chương 4: Cài đặt thử nghiệm và đánh giá. Đánh giá hiệu quả của giải pháp đưa ra trên tập ảnh CMND thu thập được. -12- Chương 1: Tổng quan về phân tích ảnh tài liệu 1.1. Tổng quan về hệ thống nhận dạng ảnh tài liệu Một hệ thống nhận dạng ảnh tài liệu gồm các bước sau (Hình 1. 1): Ảnh Thu nhận và lưu trữ ảnh Tiền xử lý ảnh Phân tích ảnh Nhận dạng Hậu xử lý Lưu văn bản Văn bản Hình 1. 1 Sơ đồ hệ thống nhận dạng  Thu nhận và lưu trữ ảnh: Các trang tài liệu được thu nhận thông qua các thiết bị ghi nhận hình ảnh (máy quét, máy ảnh kỹ thuật số,…) và được lưu trữ dưới dạng các file hình ảnh (*.bmp, *.jpg, *.tif,…). Tuỳ từng ứng dụng cụ thể mà chọn định dạng file và kiểu ảnh (ảnh mầu, ảnh đa cấp xám, ảnh đen/trắng,…) cho phù hợp. -13 Tiền xử lý ảnh: Do các tài liệu gốc thường có chất lượng khác nhau (có thể bị mờ, ố,…) hoặc quá trình thu nhận ảnh chịu ảnh hưởng của môi trường nên ảnh thu nhận được thường có chất lượng không đồng nhất. Để đảm bảo kết quả nhận dạng được chính xác cần áp dụng các kỹ thuật xử lý ảnh để nâng cao chất lượng của ảnh đầu vào. Các kỹ thuật thường được sử dụng là khử nền, xoá nhiễu, làm trơn ảnh, căn chỉnh độ nghiêng của trang tài liệu…  Phân tích ảnh: Là quá trình phân ly ảnh thành các vùng (văn bản, hình ảnh, bảng biểu,…) và hiểu vai trò chức năng của mỗi vùng cũng như mối quan hệ của nó với các vùng khác. Đây là một trong những công đoạn quan trọng nhất của một hệ thống nhận dạng vì nó ảnh hưởng rất lớn đến kết quả nhận dạng.  Nhận dạng: Đây là thao tác gán nhãn các đối tượng dựa trên các tri thức đã được học, hay nói cách khác là việc tìm một lớp mẫu phù hợp nhất với đối tượng đầu vào.  Hậu xử lý: Bao gồm các công việc như: ghép các ký tự đã được nhận dạng thành các từ, các câu, các đoạn nhằm khôi phục lại văn bản như ban đầu, đồng thời phát hiện các lỗi nhận dạng bằng việc kiểm tra chính tả dựa trên cấu trúc và ngữ nghĩa của câu, đoạn văn.  Lưu văn bản: Sau khi đã tái tạo được nguyên bản của tài liệu, cần lưu chúng ở các định dạng file được hệ thống hỗ trợ (như: *.doc, *.docx, *.rtf,…). 1.2. Phân tích ảnh tài liệu Một ảnh tài liệu bao gồm nhiều thành phần khác nhau như các khối văn bản, hình ảnh, bảng biểu, sơ đồ, công thức,… và chúng có thể được gán cho các nhãn lôgic hay chức năng khác nhau như nhan đề, tiêu đề, tên và địa chỉ tác giả,… Quá trình phân tích ảnh tài liệu là việc cố gắng phân ly tài liệu thành các vùng và hiểu vai trò chức năng cũng như mối quan hệ giữa các vùng [5]. Các ảnh tài liệu thường được tạo ra từ các tài liệu thực bởi quá trình số hoá sử dụng máy quét hoặc máy ảnh kỹ thuật số. Nhiều tài liệu như báo, tạp chí, quảng cáo có bố cục rất phức tạp do sự sắp đặt của hình ảnh, nhan đề và đầu đề, nền phức tạp, định dạng văn bản có tính nghệ thuật,… (Hình 1. 2) Một người đọc sử dụng một loạt các thông tin bổ xung như ngữ cảnh, quy ước và thông tin ngôn ngữ/kịch bản, cùng với quá trình lý luận phức tạp để giải mã nội dung của tài liệu. Tự động phân tích một tài liệu tuỳ ý với bố cục phức tạp là một nhiệm vụ vô cùng khó khăn và vượt ngoài khả năng của các hệ thống phân tích bố cục và cấu trúc tài liệu tiên tiến. Bởi vì các tài liệu này được thiết kế để hiệu quả và rõ ràng đối với sự phân tích của con người hơn các ảnh có trong tự nhiên. -14- Hình 1. 2 Ví dụ ảnh tài liệu có bố cục phức tạp Như vậy, chúng ta cần phân biệt giữa bố cục tự nhiên và cấu trúc lôgic của tài liệu, và cũng có thể chia quá trình phân tích ảnh tài liệu làm hai phần tương ứng. Hình 1. 3 mô tả các bước của một hệ thống phân tích ảnh tài liệu. 1.2.1. Bố cục tự nhiên và cấu trúc lôgic Bố cục tự nhiên của ảnh tài liệu là đề cập đến hình bao và vị trí tự nhiên của các vùng khác nhau trong ảnh tài liệu. Phân tích bố cục tự nhiên là quá trình phân ly ảnh tài liệu thành các dãy các vùng đồng nhất, như: hình ảnh, khối văn bản, dòng văn bản, từ, ký tự,… Có hai hướng tiếp cận chính để phân tích bố cục:  Hướng tiếp cận bottom-up (dưới-lên): bắt đầu từ các thành phần nhỏ nhất của tài liệu (như điểm ảnh, thành phần liên thông), lặp đi lặp lại quá trình gom nhóm chúng thành các khối đồng nhất lớn hơn.  Ngược lại, hướng tiếp cận top-down (trên-xuống) lại bắt đầu từ cả trang ảnh tài liệu, cố gắng chia nó thành các vùng nhỏ hơn. Mỗi cách tiếp cận đều có ưu/nhược điểm riêng và làm việc tốt trong những trường hợp nhất định, tuỳ thuộc vào từng bài toán cụ thể mà chọn phương pháp thích hợp. Ngoài ra một số tác giả còn đề xuất các hướng tiếp cận lai, sử dụng cả hai cách tiếp cận ở trên. Ngoài bố cục tự nhiên, các tài liệu còn chứa các thông tin bổ xung về nội dung của nó như: nhan đề, tiêu đề,… Mặt khác, mỗi tài liệu có các thứ tự đọc khác nhau (như: các ngôn ngữ Ả Rập đọc từ trái qua phải, tiếng Trung Quốc lại đọc từ trên xuống dưới,…), giúp cho việc hiểu tài liệu dễ dàng hơn. Một tập các thực thể lôgic hoặc chức năng trong tài liệu, với các quan hệ bên trong của nó được hiểu là cấu trúc lôgic của tài liệu. -15Phân tích cấu trúc lôgic là việc biểu diễn kết quả của phân tích cấu trúc bố cục. Tuy nhiên trong nhiều tài liệu phức tạp, phân tích bố cục cũng cần một số thông tin lôgic để việc phân đoạn được chính xác. Tiền xử lý ảnh Ảnh tài liệu Nhị phân ảnh Chỉnh độ nghiêng Xoá nhiễu Phân tích ảnh Đánh giá hiệu năng Tài liệu đã phân đoạn Phân tích cấu trúc Phân tích bố cục Tập mẫu Hình 1. 3 Sơ đồ hệ thống phân tích bố cục và cấu trúc ảnh tài liệu 1.2.2. Phân loại ảnh tài liệu Dựa trên mức độ phụ thuộc của tài liệu vào bố cục tự nhiên hay cấu trúc lôgic, người ta chia làm 4 loại ảnh tài liệu (Hình 1. 4) [6]: Loại 1: Quá phụ thuộc vào bố cục tự nhiên. Vị trí, độ dài của các trường dữ liệu là được ấn định trước. Ví dụ như các biễu mẫu ứng dụng, ngân phiếu, danh sách câu hỏi,… Loại 2: Phụ thuộc vào cấu trúc lôgic hơn là bố cục tự nhiên. Cụ thể, vị trí của mỗi trường có thể di chuyển lên/xuống hoặc sang trái/phải từ vị trí bình thường so với các trường có liên quan hoặc các trường trước đó. Ví dụ như thẻ danh mục, thư từ, danh thiếp. Loại 3: Phụ thuộc vào bố cục tự nhiên như loại 1, nhưng cấu trúc phức tạp hơn (các trường phân cấp hoặc lặp đi lặp lại) hoặc bố cục được hướng dẫn bởi các yếu tố khác (ví dụ như các đoạn thẳng, các vùng trống,…). Vị trí, độ dài mỗi trường là gần như cố định. Ví dụ như bảng biểu. Loại 4: Vị trí và độ dài của các trường phụ thuộc vào mối quan hệ của các trường. Nói chung, mặc dù cấu trúc chung của tài liệu là đã được định nghĩa trước bởi bố cục tự -16nhiên, nhưng cấu trúc thực tế lại phụ thuộc vào mối quan hệ giữa các trường. Cụ thể, loại này liên quan đến bố cục tự nhiên của toàn bộ tài liệu, cũng như cấu trúc lôgic về vị trí và hình dạng. Ví dụ như các trang báo, các bài báo. Bố cục tự nhiên biểu mẫu ứng dụng, ngân phiếu, danh sách câu hỏi,… [Loại 1] bảng biểu,… [Loại 3] thẻ danh mục, thư từ, danh thiếp,… [Loại 2] trang báo, bài báo, … [Loại 4] Cấu trúc lôgic Hình 1. 4 Các loại ảnh tài liệu 1.3. Phân tích bố cục Mục đích chính của phân tích bố cục tự nhiên của ảnh tài liệu (sau đây gọi tắt là phân tích bố cục) là xác định các vùng “tự nhiên” khác nhau trong tài liệu và các đặc trưng của nó. Sự phân chia các vùng này là được dựa trên tính đồng nhất của chúng, một vùng tối đa trong ảnh tài liệu là miền đồng nhất tối đa của ảnh tài liệu. Thuộc tính của tính đồng nhất được dùng để phân loại các vùng, chẳng hạn như: khối văn bản, hình ảnh, đồ họa, dòng văn bản, từ,… Các vùng này không loại trừ lẫn nhau và một vùng có thể chứa nhiều vùng không cùng loại bên trong nó. Các bước của phân tích bố cục bao gồm:  Phân đoạn vùng: Là việc chia một hình ảnh tài liệu thành các vùng thành phần, khi mà thuộc tính của tính đồng nhất không còn thoả mãn nữa. Tính đồng nhất thường được định nghĩa dựa trên một vectơ tham số, , có vai trò quan trọng trong sự thành công của thuật toán. Điều này cũng đúng cho phương pháp tiếp cận từ dưới lên, khi chúng ta cố gắng để nhóm các thành phần nhỏ hơn vào các vùng. Tính toán vectơ tham số, , hoạt động tốt cho tất cả các tài liệu thường là điều không thể. Các phương pháp hiện nay cố gắng điều chỉnh các thông số dựa trên thông tin phản hồi từ các bước xử lý phía sau như nhận dạng ký tự. -17 Phân loại vùng: Là việc quyết định xem các vùng đã phân đoạn được thuộc loại nào. Bài toán điển hình là phân loại các vùng vào khối văn bản hay hình ảnh và nhận ra đâu là các đối tượng đồ hoạ, đâu là các bảng biểu. Phân loại vùng là điều kiện kiên quyết để xử lý nhiều loại vùng, vì mỗi loại vùng thì có các đặc trưng khác nhau nên cần các thuật toán khác nhau để xử lý. Có rất nhiều thuật toán đã được đề xuất để thực hiện phân tích bố cục của ảnh tài liệu. Bây giờ chúng ta sẽ xem xét một số thuật toán phổ biến để minh họa cho các hướng tiếp cận ở trên. 1.3.1. Hướng tiếp cận trên-xuống Hình 1. 5 Hình chiếu ngang và dọc của ảnh tài liệu Một kỹ thuật cơ bản của hướng tiếp cận trên-xuống là sử dụng hình chiếu theo phương ngang và dọc để chia ảnh tài liệu đầu vào thành các vùng nhỏ hơn. Ví dụ điển hình của kỹ thuật này là thuật toán X-Y Cut [7], bắt đầu chia ảnh tài liệu thành các phần dựa vào các khe lõm của các hình chiếu (Hình 1. 5). Thuật toán lặp đi lặp lại với các phần của tài liệu bằng cách chiếu lần lượt các vùng của phân đoạn hiện thời lên các trục ngang và dọc. Quá trình phân tách dừng khi bề rộng của khe lõm nhỏ hơn một ngưỡng đã được xác định từ trước. Các kỹ thuật dựa trên hình chiếu là cực kỳ nhạy với độ nghiêng của ảnh. Chỉ cần ảnh bị nghiêng với một góc nhỏ là có thể thay đổi hoàn toàn bản chất của hình chiếu, kết quả là khe lõm không còn được rõ ràng nữa. Do đó phải đặc biệt chú ý đến khâu quét tài liệu hoặc sử dụng một thuật toán chỉnh nghiêng ảnh đáng tin cậy trước khi tiến hành phân đoạn. Một kỹ thuật khác của hướng tiếp cận này là dựa vào hình học để phân tích cấu trúc nền của ảnh tài liệu. Ý tưởng chính của kỹ thuật này là cố gắng tìm một tập hợp các -18hình chữ nhật lớn nhất có thể sao cho không chứa bất kỳ điểm ảnh nào của đối tượng (chỉ chứa nền). Các hình chữ nhật này chia ảnh tài liệu thành các vùng có chứa văn bản, hình ảnh hoặc đồ hoạ. Tiếp đó là sử dụng một thuật toán phân lớp để phân loại các vùng này trước khi chuyển sang bước tiếp theo. Phương pháp này hiệu quả và chính xác với các tài liệu có nền mầu trắng và các vùng được bố cục dưới dạng hình chữ nhật (manthatan). Ví dụ như thuật toán bao phủ hình dạng định hướng của Baird [8] và phân đoạn dựa trên dòng trắng của Pavlidis và Zhou [9]. Tuy nhiên các thuật toán này cài đặt rất phức tạp do phải miêu tả các kết quả trung gian và các trường hợp đặc biệt cần được xử lý. Thuật toán khoảng trắng bao phủ (whitespace) của Breuel [10] là một biến thể hiệu quả của ý tưởng tương tự sử dụng nguyên lý hình học, khi đã bỏ đi các trường hợp đặc biệt (Hình 1. 6). Hình 1. 6 Thuật toán whitespace 1.3.2. Hướng tiếp cận dưới-lên Hướng tiếp cận dưới-lên sử dụng các thành phần nguyên thuỷ để bắt đầu quá trình gom nhóm. Thuật toán Docstrum của O’Gorman [11], coi một tập hợp các thành phân liên thông trong ảnh tài liệu như là các thành phần nguyên thuỷ. Các nhiễu lớn hoặc các thành phần không phải là văn bản được loại bỏ khỏi tập này. K láng giềng gần nhất của mỗi thành phần được xác định và các dòng văn bản được tạo thành dựa trên một ngưỡng của góc giữa tâm các thành phần. Biểu đồ khoảng cách giữa các thành phần là được sử dụng để xác định khoảng cách giữa các ký tự trong từ và giữa các từ. Khoảng các giữa các thành phần liên thông trong dòng và giữa các dòng được tính toán để tạo thành các dòng và các khối văn bản. Thuật toán có một tập các tham số được thiết lập bởi các thí nghiệm trên một các tài liệu. Thuật toán thực hiện tốt với nhiều bố cục của -19các văn bản tiếng Anh. Hình 1. 7 cho chúng ta thấy thuật toán xử lý tốt các phông chữ với kích cỡ và kiểu khác nhau, và có bố cục tương đối phức tạp. Hình 1. 7 Thuật toán Docstrum Thuật toán dựa trên biển đồ Voronoi của Kise [12] là một phương pháp hiệu quả khác bằng cách gom nhóm các thành phân liên thông trong một trang. Bắt đầu với việc tính toán một lưới tổ ong Voronoi của ảnh tài liệu. Đồ thị láng giềng của các thành phần liên thông là được tính toán từ sơ đồ Voronoi. Sau đó, thuật toán sử dụng một ngưỡng dựa trên diện tích và khoảng cách giữa các thành phần liền kề trong biểu đồ Voronoi để quyết định đường bao của vùng. Dòng văn bản được xác định dựa trên một ngưỡng được tính toán từ khoảng các giữa các thành phần bên trong đồ thị láng giềng của nó. Các kết quả thu được có độ chính xác cao và rất đáng tin cậy trên các tài liệu có nền trắng, khi mà các thành phần liên thông được xác định một cách đáng tin cậy. Cũng giống như Docstrum, thuật toán dựa trên Voronoi có thể xử lý các bố cục phức tạp và thực hiện tốt trên hầu hết các văn bản bằng tiếng Anh (Hình 1. 8). 1.4. Phân tích cấu trúc Cấu trúc lôgic của ảnh tài liệu là một ánh xạ từ các vùng tự nhiên trong tài liệu đến các nhãn lôgic của chúng. Phân tích cấu trúc lôgic của ảnh tài liệu (sau đây gọi tách là phân tích cấu trúc) là quá trình gán các nhãn lôgic cho các vùng tự nhiên đã xác định ở bước phân tích bố cục. Các nhãn lôgic bao gồm tiêu đề, đoạn tóm tắt, tiêu đề con, đoạn văn, câu, từ, đầu trang, cuối trang, chú thích, số trang,… Một trong các hướng tiếp cận phổ biến để xác định cấu trúc lôgic của tài lại là coi tập các vùng trong tài liệu như là một chuỗi các ký hiệu. Một ngữ pháp định nghĩa thông qua các ký hiệu này để miêu tả cấu trúc lôgic của một tài liệu bất kỳ được xem xét. Sau đó, quá trình phân tích cấu trúc sẽ tìm một phân tích cú pháp có khả năng nhất (một tập các quy tắc ngữ pháp) được tạo ra từ chuỗi các ký hiệu được quan sát. Vấn đề phát sinh là khi có nhiều phân tích cú pháp tương ứng với một tài liệu xác định và chúng ta phải quyết định chọn phân tích cú pháp nào. Các quy tắc ngữ pháp được tăng -20cường thêm các thuộc tính của các vùng và các mối quan hệ của chúng để thích ứng với tình trạng này. Phân tích cú pháp có khả năng nhất có thể được định nghĩa bằng cách sử dụng một hàm chi phí được đưa vào các tính toán và các giá trị thuộc tính. Hoặc cũng có thể sử dụng một ngữ pháp sác xuất ngẫu nhiên, mà có thể cung cấp một giá trị có khả năng cho phân tích cú pháp, tuỳ thuộc vào các luật sử dụng và các thuộc tính cuối cùng. Các luật của ngữ pháp xác suất ngẫu nhiên cũng có thể chứa xác suất liên kết với nó, mà có thể được sử dụng để xác định phân tích cú pháp có khả năng nhất, cùng với các thuộc tính của vùng. Hình 1. 8 Thuật toán Voronoi Hướng tiếp cận thứ hai là áp dụng sự hiểu biết về cấu trúc và bố cục dựa trên kết quả nhận dạng ký tự quang học và nhận dạng các đối tượng đồ hoạ của tài liệu. Các tiếp cận này giả định rằng đã xác định chính xác bố cục của các vùng văn bản, và sau đó được nhận dạng bằng một thuật toán nhận dạng ký tự quang học. Các tiếp cận này là rất mạnh mẽ, vì nó sử dụng chính nội dung của văn bản để quyết định chức năng của nó, mà điều này không có trong phương pháp ở trên. Ví dụ, hướng tiếp cận dựa trên nhận dạng ký tự quang học có thể sử dụng các từ trong dòng văn bản gần với một hình ảnh để quyết định xem nó có phải là một chú thích hay không. 1.5. Kết luận chương Trong chương này, luận văn đã trình bầy một cách tổng quan về hệ thống phân tích và nhận dạng ảnh tài liệu, đặc biệt là bước phân tích ảnh tài liệu. Phân biệt sự khác nhau giữa bố cục tự nhiên và cấu trúc lôgic, giới thiệu các hướng tiếp cận và một số thuật toán trong phân tích bố cục và cấu trúc của ảnh tài liệu. Trong chương tiếp theo sẽ trình bầy một số thuật toán tiền xử lý ảnh thường được sử dụng trong phân tích ảnh tài liệu. -21- Chương 2: Một số thuật toán tiền xử lý ảnh Đầu vào của các hệ thống xử lý ảnh thường là các tệp ảnh được thu nhận từ các thiết bị như: máy quét, máy ảnh, thiết bị ghi hình hay các thiết bị thu nhận hình ảnh khác. Các ảnh này thường có chất lượng thấp (bị lẫn các nhiễu, mất các chi tiết của đối tượng, hay bị lệch so với ảnh gốc một góc bất kỳ,…). Nguyên nhân là do: thiết bị thu nhận không đảm bảo, điều kiện thu nhận không tốt (độ sáng thay đổi, thu nhận trong khi di chuyển,…) hay quá trình sao lưu bị mất mát thông tin. Để các bước xử lý tiếp theo thu được kết quả tốt cần phải có quá trình tiền xử lý để nâng cao chất lượng ảnh đầu vào. Quá trình này bao gồm các công đoạn khôi phục và tăng cường ảnh:  Khôi phục ảnh nhằm mục đích loại bỏ hay giảm thiểu các ảnh hưởng của môi trường tác động lên ảnh. Bao gồm các bước: lọc ảnh, khử nhiễu, xoay ảnh,… nhằm giảm bớt các biến dạng của ảnh và đưa ảnh về trạng thái gần như ban đầu.  Tăng cường ảnh không phải làm tăng lượng thông tin trong ảnh mà là làm nổi bật các đặc trưng của ảnh giúp cho công việc phía sau được hiệu quả hơn. Công đoạn này bao gồm các việc như: lọc độ tương phản, làm trơn ảnh, nhị phân ảnh,… Trong đó các thao tác nhị phân ảnh, căn chỉnh độ nghiêng và xóa nhiễu là các thao tác cơ bản nhất và thường được áp dụng. Trong các phần tiếp theo của chương này sẽ trình bầy một số thuật toán trong các thao tác đó. 2.1. Nhị phân ảnh Ảnh nhận được từ các thiết bị thu nhận hình ảnh như máy ảnh hay camera thường là ảnh mầu hay ảnh đa cấp xám, các thành phần trong ảnh là rất phức tạp (mầu sắc, kết cấu…). Do đó muốn làm nổi bật các đặc trưng trong ảnh thì phải chuyển về dạng ảnh nhị phân, ảnh chỉ có hai mầu (đen và trắng) – tương ứng với nền và tiền cảnh (đối tượng “quan tâm”). Nhị phân ảnh (hay còn gọi là phân ngưỡng) là thao tác chuyển từ ảnh đa cấp xám (hoặc ảnh mầu) về ảnh nhị phân (Thuật toán 2.1). Thuật toán 2.1. Nhị phân ảnh INPUT: Ảnh mầu hoặc ảnh đa cấp xám OUTPUT: Ảnh nhị phân 1. Xác định ngưỡng T 2. Chuyển ảnh về dạng nhị phân