Tài liệu Nghiên cứu và ứng dụng thuật toán phát hiện bảng trong ảnh tài liệu

  • Số trang: 65 |
  • Loại file: PDF |
  • Lượt xem: 60 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

4 CHƯƠNG 1 GIỚI THIỆU TỔNG QUÁT VỀ HỆ PHÂN TÍCH ẢNH TÀI LIỆU 1.1 Tổng quan về hệ phân tích ảnh tài liệu Ảnh tài liệu sau khi được quét và lưu trữ vào máy tính thì nó được cấu thành từ những điểm ảnh, nhiệm vụ của chúng ta là phải trích chọn được những thông tin đặc trưng từ nó sao cho máy tính có thể “đọc” và “hiểu” được các thành phần này. Để làm được điều này người ta phải áp dụng các thuật toán kết hợp cùng với những kỹ thuật cả về phần cứng và phần mềm máy tính, sự tích hợp này là yếu tố chính tạo thành một hệ phân tích ảnh tài liệu. Sau khi tạo được hệ phân tích ảnh, người ta tiến hành quá trình xử lý ảnh gồm việc thao tác lên ảnh đầu vào để cuối cùng cho ảnh đầu ra với kết quả đạt được những mục tiêu đã định trước đó. Cụ thể là kết quả của ảnh đầu ra có thể là một kết luận về sự nhận dạng hoặc là một ảnh đã được xử lý tốt hơn. Một trong những công nghệ khá phổ biến hiện nay đượ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). Cơ chế chủ yếu của nó là 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 được sang kiểu tập tin văn bản. Từ đó OCR có thể giúp chúng ta thao tác trên văn bản như tạo, sửa đổi, xóa bỏ, tìm kiếm, thay thế nội dung của tài liệu. Như vậy, mục tiêu của hệ phân tích ảnh tài liệu là phát hiện ra được các đối tượng khác nhau trong một ảnh tài liệu như chữ đánh máy, chữ viết bằng tay, hình ảnh, văn bản chia thành hàng, cột, v.v. Đồng thời hệ phân tích này còn phải trích xuất được những thành phần trong ảnh tài liệu mà chúng ta mong muốn để phục vụ cho những mục đích nghiên cứu và ứng dụng khác nhau. Và đặc biệt trong bài luận này là trọng tâm nhấn mạnh đến việc phát hiện được bảng biểu (detect table) trong ảnh tài liệu. Trên cơ sở đặc điểm chung của một ảnh tài liệu thường có chứa hai loại đối tượng chính là văn bản và hình ảnh cũng như đa số các công nghệ nhận dạng được áp dụng hiện nay, chúng ta có thể thấy rằng một hệ phân tích ảnh tài liệu thực hiện hai nhiệm vụ chính (xem hình 1.1). Nhiệm vụ thứ nhất là phải xử lý các đối tượng hình ảnh được cấu thành từ hình vẽ, đường kẻ, dấu vân tay, khuôn mặt, những nốt đen lớn, biểu đồ,…Và nhiệm vụ thứ hai là phải xử lý các đối tượng văn bản cấu thành từ chữ viết như ký tự, từ, chuỗi ký tự, chữ viết tay. Việc phát hiện độ nghiêng (tilt) của tài liệu (độ nghiêng của văn bản xuất hiện khi chúng ta quét ảnh 5 tài liệu từ máy quét đã đặt không chuẩn xác các vị trí của nó), phát hiện các phông chữ, độ lớn chữ, từ, cụm từ, dòng văn bản, đoạn văn bản và các cột văn bản là những công việc quan trọng và cần thiết để thực hiện việc phát hiện văn bản được ứng dụng công nghệ OCR như đã đề cập. Sau khi thực hiện thành công hai nhiệm vụ chính, hệ phân tích ảnh tài liệu sẽ trích chọn những thông tin cần thiết đã phát hiện được, đưa vào một tài liệu ở một định dạng khác như tập tin văn bản (word) hoặc ngôn ngữ hiển thị siêu văn bản (Hyper Text Markup Language-HTML). Việc đầu tư tài chính, công nghệ, con người cùng các yếu tố liên quan để thiết kế và ứng dụng hệ phân tích ảnh tài liệu là rất cần thiết và vô cùng quan trọng. Nó giúp chúng ta giải quyết rất nhiều vấn đề trong thực tế khi mà số lượng các dữ liệu lớn. Con người tiếp nhận và xử lý thông tin nhờ vào các giác quan, nhưng có thể nói trong đó có khoảng 80% là thu nhận bằng mắt. Một vài ví dụ điển hình có thể minh chứng rằng thực sự cần thiết để sở hữu một hệ thống phân tích ảnh tài liệu nào đó. Thứ nhất, ta là người phải nhập điểm số cho hàng trăm nghìn sinh viên trong một trường đại học được gửi về từ các giáo viên giảng dạy, theo cách làm truyền thống thì tại phòng xử lý điểm phải có ít nhất một người ngồi đọc điểm cùng với một người gõ vào máy tính. Việc này vừa tốn thời gian, tốn chi phí nhân công, ít khách quan lại dễ xảy ra sai sót do yếu tố con người. Thay vào đó, nhà trường có thể thiết kế phiếu điểm giao cho giảng viên trong đó đã có sẵn các giá trị từ 1 đến 10 cho mỗi sinh viên và chỉ việc chấm điểm theo cách tô đen vào vị trí điểm số mà sinh viên đạt được. Cuối cùng bảng điểm này được quét để máy tính phát hiện điểm số một cách tự động nhờ vào chấm đen mà giảng viên đã tô đậm thông qua một hệ nhận dạng ảnh tài liệu, theo đó sẽ khắc phục được những nhược điểm của cách làm truyền thống. Thứ hai là, tại một doanh nghiệp sản xuất kinh doanh với số nhân công hàng chục ngàn người làm việc trong ngày, trong các công đoạn chấm công có việc kiểm tra sự có mặt của nhân viên vào đầu giờ và cuối giờ làm. Với phương pháp truyền thống doanh nghiệp phải cử ra rất nhiều người để theo dõi các nhân viên còn lại việc vào và ra khỏi công ty phải đúng giờ. Việc này đã được khắc phục nhằm đem lại sự thuận lợi, chính xác và ít tốn kém bằng cách sử dụng một máy chấm công bằng vân tay, trong đó tích hợp công nghệ xử lý và so sánh dấu vân tay bảo đảm công tác thống kê số giờ làm mà không cần sự theo dõi trực tiếp của con 6 người. Trong đó, máy chấm công bằng dấu vân tay ứng dụng hệ phân tích ảnh tài liệu. Xử lý Ảnh tài liệu Xử lý Văn bản Nhận dạng ký tự Quang học Phân tích bố trí trang Xử lý đối tượng ảnh Xử lý đường kẻ Xử lý biểu tượng và vùng Phát hiện độ Đường thẳng, góc và Lấp đầy các nghiêng, các đường cong khu vực dòng, khối và đoạn văn bản Hình 1.1: Sơ đồ khối liệt kê nhiệm vụ xử lý ảnh tài liệu được phân chia theo cấp bậc trong mỗi vùng của ảnh. Nguồn: Gorman(2009), tác giả dịch thuật (7/2012). Văn bản Hệ phân tích ảnh tài liệu đã được sử dụng trong vài thập kỷ qua, đặc biệt là trong ngành kinh doanh ngân hàng, bưu điện, thư viện,…ứng dụng để máy tính đọc mã vạch hoặc lưu trữ tài liệu ở dạng điện tử, vào cuối những năm 1980 và 1990 thì đã phát triển nhanh chóng. Lý do chủ yếu của việc phát triển này là tốc độ ngày càng lớn và chi phí thấp hơn của phần cứng máy tính. Kể từ khi máy fax trở nên phổ biến, chi phí của máy quét quang học cho các tài liệu đầu vào giảm xuống đã giúp các doanh nghiệp nhỏ cũng như mỗi cá nhân có cơ hội được sử dụng những công nghệ này. Mặc dù ảnh tài liệu có chứa một lượng tương đối lớn dữ liệu, thì ngay cả máy tính cá nhân hiện nay cũng đã có tốc độ đủ để xử lý chúng. Bộ nhớ máy tính bây giờ không những đủ cho các hình ảnh tài liệu lớn, mà quan trọng hơn, bộ nhớ quang học bây giờ cũng đủ để lưu trữ khối lượng lớn dữ liệu. Điều này dẫn đến ngày càng phát triển công nghệ nhận dạng và xử lý ảnh tài liệu. Sự bổ sung cần thiết cho những cải tiến phần cứng là những tiến bộ đang được thực hiện trong việc phát triển các thuật toán và phần mềm phân tích ảnh tài liệu. Trong đó công nghệ OCR có khả năng nhận dạng văn bản với độ chính xác lên đến khoảng 90%, bên cạnh đó nhiều phương pháp nhận dạng ảnh tài liệu khác cũng được cải tiến gần như 7 tương tự. Theo đó, các tài liệu viết tay hoặc tài liệu đã được in ấn hay những hình ảnh có thể được chuyển thành tài liệu điện tử trên máy tính để thuận tiện trong việc lưu trữ, quản lý, chỉnh sửa và biên soạn lại. Tuy nhiên, tài liệu giấy cho đến nay vẫn đang phát huy vai trò truyền thống của nó do tính chất trực quang, dễ thao tác, phổ biến được rộng rãi đối với mọi đối tượng sử dụng. Vì vậy, chúng ta phải tìm cách giải quyết vấn đề là sử dụng công nghệ và các thuật toán để tích hợp dữ liệu dưới dạng ảnh tài liệu vào trong bộ nhớ phần cứng để xử lý bằng máy tính. Sau khi đã tạo ra 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ân tách từng thành phần phát hiện riêng biệt là phát hiện hình ảnh và phát hiện văn bản. Trang Tài liệu Thu thập dữ liệu 107 điểm ảnh Xử lý mức điểm ảnh 7.500 hình bao ký tự, mỗi hộp có kích thước 15x20 điểm ảnh 500 đường kẻ và các đường cong, độ dài từ 20 đến 2.000 điểm ảnh 10 khu vực khác nhau được tô, từ 20x20 đến 200x200 điểm ảnh Phân tích mức đặc trưng 500x5 đặc trưng đường thẳng và đường cong 10 x 5 đặc trưng vùng 7,500x10 đặc trưng ký tự Phân tích và nhận dạng văn bản 1.500 ký tự, 10 đoạn văn, một tiêu đề chính,… Phân tích và nhận dạng hình ảnh Hai sơ đồ, một biểu tượng công ty, các hình ảnh khác. Mô tả tài liệu Hình 1.2. Một trình tự để phân tích ảnh tài liệu, cùng với các ví dụ về các kết quả trung gian, kết quả cuối cùng và kích thước của dữ liệu. Nguồn: Gorman (2009), tác giả dịch thuật (7/2012). 8 Hình 1.2 mô phỏng một chuỗi các bước trong phân tích hình ảnh tài liệu phổ biến. Các phần tiếp theo sẽ trình bày vắn tắt một số bước cơ bản này. Sau khi thu thập dữ liệu, hình ảnh trải qua xử lý cấp độ điểm ảnh và phân tích tính năng, sau đó mỗi loại đối tượng văn bản và hình ảnh được phát hiện và xử lý riêng. Thu thập dữ liệu được thực hiện trên một tài liệu giấy thường bằng cách quét quang học. Các dữ liệu sau đó được lưu trữ trong một tập tin hình ảnh, gọi là điểm ảnh, được lấy mẫu trong một mô hình mạng lưới xuyên suốt ảnh tài liệu (Gorman – 2009). 1.2 Quá trình thu nhận ảnh tài liệu Ảnh tài liệu thường đượ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 và những đoạn phim kỹ thuật số từ máy chụp hoặc máy quay phim (camera) 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. Dữ liệu lúc này được tập hợp là các điểm ảnh (pixels) và được mô phỏng thành tập hợp của một lưới các điểm ảnh (a grid pattern) (Gorman - 2009). Các thiết bị thu nhận ảnh tài liệu có hai loại chính tương ứng với hai loại ảnh thông dụng Vector và Raster. Theo đó, quá trình thu nhận ảnh tài liệu thực hiện các công đoạn chính gồm việc biến đổi năng lượng quang học thành năng lượng điện gọi là cảm biến và tổng hợp năng lượng điện thành ảnh gọi là quá trình lượng tử hóa (Đỗ Năng Toàn-2008). Với ảnh nhị phân thì cường độ điểm ảnh có thể nhận một trong hai giá trị OFF (0) hoặc ON (1) (Hình 1.3). Đối với ảnh đa cấp xám thì cường độ điểm ảnh nhận giá trị từ 0 đến 255 và với ảnh màu thì giá trị điểm ảnh nhận 3 kênh là R, G, B từ 0 đến 255 giá trị màu sắc. Thí dụ, với một trang ả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. Từ đó cho thấy rằng một ảnh tài liệu thông thường là tập hợp của các giá trị điểm ảnh mà người ta đã dùng các bộ cảm biến hoặc máy quét để biến tín hiệu quang thành tín hiệu điện liên tục, rồi thì khắc phục hiện tượng chồng phổ, thực hiện lượng tử hóa cùng với các công đoạn kỹ thuật khác và cuối cùng sẽ trích chọn được các thông tin phù hợp. 9 Hình 1.3. Một hình ảnh nhị phân của chữ "e" được thực hiện lên ON và OFF các điểm ảnh, ON điểm ảnh được hiển thị ở đây là "X". Nguồn Gorman (2009). 1.3 Các bước xử lý điểm ảnh của ảnh tài liệu Một số bước quan trọng trong quá trình xử lý điểm ảnh của hệ phân tích ảnh tài liệu cần phải được thực hiện để làm cơ sở cho các quá trình phân tích và nhận dạng về sau. Cụ thể, người ta thường thực hiện các công việc gồm tăng giảm độ sáng bằng cách cộng thêm cho mỗi giá trị của điểm ảnh một giá trị nguyên c nào đó, nếu giá trị c lớn hơn 0 thì ảnh sáng lên, ngược lại nếu giá trị c nhỏ hơn 0 thì ảnh sẽ tối đi. Tiếp đến là việc chọn và tách ngưỡng để chuyển ảnh màu hoặc ảnh đa cấp xám về ả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.3.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. Vì vậy phương pháp nhị phân thường được ưu tiên thực hiện trước. Song việc 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 10 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 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). Cũng phải lưu ý trong quá trình tách ngưỡng khi chuyển ảnh màu thành ảnh đen trắng được ứng dụng khi quét và nhận dạng văn bản có thể xảy ra sai sót nền thành ảnh hoặc ảnh thành nền, dẫn đến ảnh bị đứt nét hoặc kết dính (Hình 1.4). Hình 1.4: 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). 11 1.3.2 Phương pháp khử nhiễu ảnh Trong quá trình thu nhận ảnh tài liệu, có hai loại nhiễu cơ bản là nhiễu hệ thống (nhiễu này có quy luật nên có thể khử bằng các phép biến đổi) và nhiễu ngẫu nhiên (những dạng vết bẩn không rõ nguyên nhân nên có thể khắc phục bằng các phép lọc). Nguyên nhân chủ yếu gây ra nhiễu là do quá trình sao chép ảnh (photocopy) hay quá trình quét ảnh hoặc chuyển qua máy Fax. Giảm nhiễu nhằm mục đích loại bỏ các tính năng không liên quan để tránh trường hợp gây ra lỗi trong các bước xử lý tiếp theo cũng như giảm dung lượng lưu trữ và giảm được thời gian xử lý. Ảnh nhị phân thường xuất hiện một số loại nhiễu kích thước nhỏ gọi là nhiễu xung, nhiễu đốm hay chỉ một loại bụi bẩn nào đó, thuật ngữ tiếng anh thường gọi là salt-and-pepper noise, tức là mô tả điểm nhiễu như hạt muối hoặc hạt tiêu. Để khử nhiễu, người ta thường sử dụng một số phương pháp như các phép toán hình thái học, trong đó nghiên cứu về cấu trúc hay hình học topo của đối tượng trong ảnh tài liệu. Phần lớn các phép toán của “Hình thái” được định nghĩa từ hai phép toán cơ bản là phép toán “giãn nở” (Dilation) và phép toán “co” (Erosion). Giả sử ta có đối tượng X và phần tử cấu trúc mẫu B trong không gian hai chiều, ký hiệu Bx là dịch chuyển của B tới vị trí x. Khi đó, phép “giãn nở” của X theo mẫu B là hợp của tất cả các Bx với x thuộc X. Và phép “co” của X theo B là tập hợp tất cả các điểm x sao cho Bx nằm trong X. Như vậy có thể thấy rằng phép “co” ảnh sẽ làm giảm kích thước của vùng mang thông tin ảnh trong vùng mang thông tin nền, và phép “giãn nở” ảnh thực hiện điều ngược lại và làm cho vùng mang thông tin ảnh trong vùng mang thông tin nền tăng lên. Người ta thực hiện tuần tự việc “co” và “giãn nở” ảnh nhiều lần bằng cách kết hợp các phép toán này. Một vài phương pháp kết hợp như vậy có tên là phép toán mở (OPEN) và phép toán đối xứng của nó là phép toán đóng (CLOSE). Phép toán mở của X theo cấu trúc B là tập hợp các điểm của ảnh X sau khi đã co và giãn nở liên tiếp theo B. Kết quả mà phép toán mở mang lại là làm nhẵn vùng biên của đối tượng, làm đứt vùng eo nhỏ và từ đó khử được những vùng điểm nhiễu nhỏ. Theo đó, kết quả của phép toán đóng là làm nhẵn vùng biên, các lỗ hổng nhỏ được loại trừ và các kẽ hở không đáng kể giữa các đối tượng được hàn gắn lại (Hình 1.5). 12 Hình 1.5: Mô phỏng sự kết hợp giữa các phép toán hình thái học ứng dụng vào việc khử một vài loại nhiễu cơ bản. Nguồn: Gorman (2009). 1.3.3 Phân khúc các đặc tính Để 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 khúc (còn được gọi là phân đoạnsegmentation) 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 khúc đượ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ý. Hiện nay một số phương pháp phân khúc thường được áp dụng như phương pháp phân khúc 13 yếu của B.G. Prasad hoặc phân khúc dựa trên ngưỡng cục bộ thích nghi. Giả sử ảnh đầu vào là một trang sách, trong đó có cả chữ viết được chia thành các đoạn và chia ra hai cột, đồng thời có cả hình ảnh minh họa, thì lúc này việc phân khúc ảnh sẽ thực hiện tách riêng hình ảnh và văn bản. 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.3.4 Tìm xương và phát hiện biên Tìm xương của ảnh là việc biểu diễn ảnh dưới dạng những đường trục trung tâm 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 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.6 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ác 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 đó 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 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. tính khoảng 14 các 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). Việc tìm xương là hữu hiệu đối với những đối tượng ảnh có độ mảnh dạng đường thẳng, nét viết, bản đồ, đường vân và các đối tượng có hình thù tương tự, nhưng đối với những đối tượng ảnh có kích thước lớn như những vùng được tô kín bằng màu đen hoặc những vết loan thì xương của chúng chỉ là một điểm ảnh nằm tại tâm của đối tượng. Lúc này, việc phát hiện biên của đối tượng sẽ tỏ ra hiệu quả hơn để định hình và biểu diễn đối tượng kiểu này. Biên là yếu tố quan trọng trong việc trích chọn đặc điểm nhằm tiến đến “hiểu” ảnh. Với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen có ít nhất một điểm trắng bên cạnh. Tập hợp các điểm biên tạo nên đường biên hay đường bao của đối tượng ảnh. Người ta thường sử dụng một số phương pháp phát hiện biên như: Phát hiện biên trực tiếp, phát hiện biên gián tiếp thông qua một số kỹ thuật phát hiện biên như kỹ thuật Gradient, kỹ thuật Prewitt, kỹ thuật Sobel, kỹ thuật la bàn, kỹ thuật Laplace, kỹ thuật Canny (Đỗ Năng Toàn-2008)…Còn đối với các đối tượng ảnh chiếm những vùng nhỏ như những ký tự riêng biệt hoặc những nét vẽ các đối tượng cực nhỏ trong sơ đồ bản mạch điện tử chẳng hạn thì cả việc tìm xương lẫn phát hiện biên đều không phát huy hiệu quả mà lúc này người ta sẽ dùng cách thức lưu trữ mảng (array) của những giá trị của điểm ảnh để biểu diễn những vùng ảnh nhỏ này. Hình 1.6: Mô tả hình ảnh nguyên bản và Xương tương ứng của nó. (a): chữ “m”; (b): sơ đồ bản mạch; (c): dấu vân tay. Nguồn Gorman (2009) 15 1.3.5 Lưu trữ dạng 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. Người ta thường dùng phương pháp lưu trữ dưới dạng mã mắc xích, theo đó, các điểm có giá trị ON được biểu diễn thông qua một tập các điểm láng giềng có thể đi theo hướng 4 láng giềng hoặc 8 láng giềng của nó. Phương pháp này sẽ lưu trữ hướng (vector) của các điểm láng giềng mà không cần lưu trữ vị trí của điểm ảnh có giá trị ON. Láng giềng của điểm X là tất cả các điểm nằm liền kề điểm X thuộc ma trận 3x3 với điểm X là tâm (Hình 1.7). Một số ưu điểm mà phương pháp này đem lại là việc lưu trữ sẽ hiệu quả hơn vì thông thường với ảnh có kích thước lớn hơn 256x256 thì tọa độ giá trị điểm ảnh ON thường được biểu diễn bởi 16 bit; trong khi đó cách lưu trữ dạng véctơ hóa một điểm láng giềng thuộc một trong tám hướng do vậy mỗi điểm ảnh ON chỉ cần biểu diễn bằng một byte, thậm chí chỉ cần 3 bit để lưu. Ngoài ra, phương pháp vector hóa lưu theo cấu trúc các điểm ảnh có liên quan với nhau do vậy tạo điều kiện thuận lợi để làm trơn các đường cong và có thể xấp xỉ cho các đường thẳng. 1.4 Các bước phân tích ảnh tài liệu Để phân tích sâu sắc và hiểu được bản chất của ảnh tài liệu, thì sau các bước tiền xử lý đã trình bày ở những phần trên, người ta tiếp tục tiến hành các công đoạn phân tích ảnh. Một số nhiệm vụ quan trọng ở bước phân tích này là phân tích 16 các đặc trưng của ảnh, phân tích các đối tượng văn bản, trong đó việc ước lượng độ nghiêng và phân tích sơ đồ trình bày trên trang tài liệu là được chú trọng hơn cả. 1.4.1 Phân tích các đặc trưng của ảnh tài liệu Đặc trưng của ảnh tài liệu gồm có đặc trưng cục bộ (local features) và đặc trưng toàn cục (global features). Với ảnh tài liệu chứa văn bản, đặc trưng toàn cục mô tả từng trang, độ nghiêng của trang khi quét vào từ máy quét, độ dài dòng, khoảng cách dòng, còn đặc trưng cục bộ thì mô tả về kích thước phông chữ, dấu chấm câu, v.v…Tương tự như thế, với ảnh tài liệu chứa hình ảnh, thì đặc trưng toàn cục cũng xét đến độ nghiêng của trang tài liệu, độ rộng dòng, phạm vi của độ cong đối với các đường cong, độ dài tối thiểu của dòng. Và đặc trưng cục bộ lại xét đến việc mô tả mỗi góc, mô tả đường cong và đường thẳng, định vị các hình chữ nhật, hình tròn và hình dạng của các loại hình học khác. Như vậy, để phục vụ cho các công đoạn xử lý ảnh tiếp theo, thì các hình ảnh sau khi đã xử lý điểm ảnh nó sẽ được lưu trữ ở dạng xương, dạng hình bao hoặc dạng véctơ hóa và tiếp tục được phân tích đặc trưng. Sau khi hoàn thành bước phân tích đặc trưng thì gần như tất cả các loại đối tượng được phát hiện đầy đủ hơn, như là phát hiện đường cong được xấp xỉ thành hình đa giác nào đó (polygonal approximation), định vị được các điểm quan trọng nằm trên đường thẳng và đường cong như các điểm góc và điểm chuẩn bị để uốn cong. Theo đó, các biểu tượng ảnh hoặc các ký tự riêng biệt có các vùng giới hạn tương ứng thì những đặc trưng điển hình như độ thắt chặt của hình bao, tỷ lệ hình ảnh, độ dày đặc của các điểm ON của ảnh, số đường viền cũng như tính chất trơn của nó,… tất cả chúng đều được ghi nhận và xử lý để làm cơ sở dữ liệu cho những thao tác xử lý nhận dạng về sau. 1.4.2 Phân tích các đối tượng văn bản trong ảnh tài liệu Để phân tích đối tượng văn bản trong ảnh tài liệu, người ta thường sử dụng một số phương pháp phân tích truyền thống. Thứ nhất là phương pháp phát hiện ký tự, phát hiện chuỗi ký tự bằng công nghệ nhận dạng ký tự quang học (OCR) đã có đề cập ở phần đầu của bài luận này. Thứ hai là người ta sử dụng phương pháp phân tích bố trí trang tài liệu để phát hiện được định dạng của văn bản bao gồm những yếu tố quan trọng như phát hiện khu vực ghi chú thích, khu vực phân biệt đoạn này 17 với đoạn khác, dấu hiệu cho thấy nơi trình bày tiêu đề phụ, tiêu đề chính. Chúng ta có thể áp dụng hai phương pháp phân tích này một cách tuần tự, riêng lẻ hoặc phối hợp chặt chẽ với nhau bằng việc kế thừa sản phẩm của phương pháp này để ứng dụng vào phương pháp kia. Từ đó phát hiện được văn bản là một bảng ghi chú, một tờ mục lục, một bảng liệt kê hay biểu mẫu được sử dụng trong ngân hàng hay là một dạng bì thư được sử dụng trong ngành viễn thông và bưu điện. v.v…tùy vào cách thức bố trí của các khối văn bản. Điểm mạnh của phương pháp OCR thường được ghi nhận và đánh giá cao trong việc phát hiện văn bản từ những ký tự được tạo ra từ máy in hoặc những chữ viết tay. Trong khi đó phương pháp phân tích bố trí trang tài liệu lại đi phân tích các sơ đồ trình bày nhằm phân tích các định dạng trang ảnh tài liệu để tiến đến phát hiện các cấu trúc của những bảng biểu và cả việc phát hiện những thông tin đang được chứa đựng trong các biểu mẫu đó. Và đôi khi chúng ta cũng phải chú trọng phát hiện độ nghiêng của ảnh tài liệu để có giải pháp khắc phục sự nghiêng khi quét ảnh đầu vào vì yếu tố nghiêng sẽ ảnh hưởng rất lớn đến việc nhận dạng các đối tượng về sau. 1.4.2.1 Xác định độ nghiêng của ảnh tài liệu Như đã có trình bày sơ lược ở những phần trên của bài luận này, nguyên nhân tạo ra độ nghiêng của ảnh tài liệu là do trong quá trình thu nhận ảnh đầu vào (quá trình quét ảnh hoặc sao chụp ảnh bằng tay đã đặt ảnh không chính xác tuyệt đối về vị trí thẳng góc, hoặc quá trình chụp ảnh không giữ được phương thẳng đứng của máy chụp,…). Ảnh tài liệu được cho là nghiêng khi phát hiện góc nghiêng khác 0. Một dòng văn bản được cấu thành từ một nhóm các ký tự, các từ tiếp giáp tương đối gần nhau, các biểu tượng,…được bố trí trên một đường thẳng theo hướng đứng hoặc nằm ngang. Những dòng văn bản này là căn cứ cơ bản để xác định góc độ nghiêng của trang ảnh tài liệu trên cơ sở so sánh tính chất song song của các dòng văn bản so với các cạnh của mép trang tài liệu. Tức nhiên là trang ảnh tài liệu ban đầu sẽ không nghiêng theo nghĩa là các dòng văn bản có độ song song tuyệt đối so với các cạnh theo chiều ngang và chiều dọc của một trang, và khi quét vào máy tính thì trang này cũng có thể bảo toàn nghiêng nghĩa là góc nghiêng bằng 0 nhưng điều này là không chắc chắn hoàn toàn. Vì vậy, cần phải định vị độ nghiêng và khắc phục nó trước khi thực hiện những bước tiếp theo bởi vì khi áp dụng công nghệ 18 OCR hoặc phân tích bố trí trang tài liệu yêu cầu điều kiện là góc nghiêng trang tài liệu phải bằng 0. Một số phương pháp định vị độ nghiêng đã được đề xuất như là chọn đường cơ sở phù hợp với phép biến đổi Hough (fitting baselines by the Hough transform), phương pháp phân nhóm láng giềng gần nhất (nearest-neighbor clustering) hay phương pháp chiếu nghiêng một bên (using the projection profile). Với phương pháp chiếu nghiêng một bên thì người ta tính số các điểm ảnh có giá trị 1 đối với ảnh nhị phân sau khi đã rà ảnh theo các cột hay các dòng rồi ghi nhận các giá trị này vào một cấu trúc nhớ theo kiểu mảng hoặc danh sách liên kết, trong đó mỗi dòng hay cột được rà sẽ tạo ra một chỉ số cho mảng hay cho danh sách liên kết. Do đó một biểu đồ tần suất sẽ được hình thành để biểu thị các điểm ảnh có giá trị 1 nói trên. Người ta tiến hành chiếu ảnh theo các góc có giá trị từ 0o đến 180o theo phép chiếu nghiêng một bên (Hình 1.8a và Hình 1.8b). Người ta dùng các khái niệm “vùng đỉnh” và “vùng lõm” để ứng dụng vào việc phát hiện nghiêng. Cụ thể, với ảnh tài liệu có góc nghiêng là 0 thì vùng đỉnh của phép chiếu nghiêng một bên thể hiện các dòng chứa các từ (word) và vùng lõm sẽ thể hiện khoảng trắng giữa các dòng đó. Để định vị được độ lớn góc nghiêng của ảnh tài liệu, thì ta đi tìm góc quay một bên mà tại đó biểu đồ tần suất thể hiện nhiều vùng lõm nhất và nhiều vùng đỉnh nhất. Giả sử rằng biểu đồ tần suất ghi nhận được 20 vùng đỉnh và 20 vùng lõm thì có thể biết rằng ảnh tài liệu hiện có 20 dòng văn bản. Theo đó, với từng phép chiếu nghiêng một bên người ta tính tổng số đo về độ cao của các vùng đỉnh và tổng số đo về độ cao của các vùng lõm tương ứng, góc chiếu nào có sự khác nhau giữa hai số đo này lớn nhất thì đó là góc nghiêng của ảnh tài liệu. 19 Nguồn: Gorman (2009) 1.4.2.2 Phân tích cấu trúc bố trí của trang ảnh tài liệu Nếu ảnh tài liệu thu nhận được đã phát hiện ra góc nghiêng khác 0, người ta tiến hành xoay ảnh một góc thích hợp để trả độ nghiêng ảnh về 0, rồi tiếp tục thực hiện quá trình phân tích cấu trúc bố trí của mỗi trang mà có khi còn được gọi là phân tích theo cấu trúc bố trí vật lý và hình học. Mục tiêu của quá trình này là phát hiện và trích chọn được cấu trúc của các phần văn bản (ở đây chủ yếu lấy được khối và đoạn văn bản) bằng cách tách biệt các từ, tách cấu trúc của các khối, các dòng v.v…tùy thuộc vào định dạng vật lý ban đầu của tài liệu. Ngoài ra việc xem xét để phân tích cấu trúc của trang bố trí theo chức năng (còn được gọi là phân tích theo sự bố cục loogic và cú pháp) cũng được thực hiện, trong đó có sử dụng những thông tin miền phụ thuộc bao gồm các quy tắc bố trí của từng loại cấu trúc trang cụ thể, để thực hiện gán nhãn cho các khối cấu trúc và đưa ra một số dấu hiệu nhận biết các khối này. Việc ghi nhãn cho các khối chức năng này cũng có thể dẫn đến việc sáp nhập hoặc chia tách các khối cấu trúc trong trang. Hình 1.9 mô tả một thí dụ về kết quả phân tích cấu trúc một trang ảnh tài liệu, trong đó nội dung và cách thức sắp xếp thông tin quy định trình bày cho trang 20 đầu tiên của một tài liệu kỹ thuật. Sau khi phân tích đã phân định được các khối chỉ định cho các thành phần chính, gồm: tên tài liệu, tiêu đề chính, tên tác giả, phần tóm tắt, các từ khóa, các đề mục, các khối cấu thành phần thân chính của văn bản, phần chú thích và phần ghi nhận về bản quyền của tác giả. Ảnh tài liệu nguyên bản ban đầu được quét vào máy tính Tên của tài liệu Tiêu đề Tên tác giả Từ khóa Giới thiệu Đề mục Khối 1 thể hiện Thân văn bản Chú thích Hình ảnh thể hiện cấu trúc Hình ảnh thể hiện chức năng của các khối Khối 2 thể hiện Thân văn bản Thông tin bản quyền tác giả Hình 1.9: Mô tả phân tích cấu trúc và phân tích theo chức năng các khối trong trang tài liệu. Nguồn: Xử lý của tác giả (7/2012) 21 Hai phương pháp phân tích theo hướng cấu trúc vật lý thường được sử dụng để tiến hành phân tích trang là tiếp cận từ trên xuống (top-down) hoặc tiếp cận từ dưới lên (bottom-up). Hai phương pháp này có tính đối ngẫu lẫn nhau. Nhưng người ta thường áp dụng phối hợp theo hướng kế thừa sản phẩm của nhau để cùng phân tích trang tài liệu. Thông thường phương pháp từ trên xuống sẽ đi phân tích những khối cấu trúc lớn đến những khối và thành phần cấu trúc hay đối tượng nhỏ hơn. Thí dụ một trang có thể được phân tích thành các khối phần trên, khối phần giữa và khối phần chân của trang, rồi thì các khối này lại được phân tích thành các đoạn văn bản và đối tượng ảnh, tiếp đến các đoạn này lại được tách thành các dòng, các cụm từ, các từ, các ký tự. Trong khi đó phương pháp tiếp cận dưới lên lại phân tích theo chiều hướng quy nạp ngược lại, cụ thể là nó đối ngẫu bằng cách xuất phát từ các khoảng trắng liên thuộc được giao kết với các ký tự để phát hiện các từ, tiếp đến các từ này lại được giao kết với nhau để nhận dạng được từng dòng, cứ tiếp tục như vậy để phát hiện được các thành phần lớn hơn của trang. 1.5 Tìm hiểu phương pháp phát hiện ký tự quang học Phát hiện ký tự quang học (OCR) là một công nghệ thuộc lĩnh vực nhận dạng, người ta ứng dụng công nghệ này nhằm nhận dạng các chuỗi ký tự trên cơ sở căn cứ ban đầu là những ký tự trong bảng chữ cái, khởi đầu là bảng chữ cái tiếng Anh. Nhưng cho dù là bảng chữ cái giới hạn nào thì cũng có rất nhiều kiểu viết khác nhau, có thể do sự đa dạng của các nét viết tay hoặc do kiểu phông chữ, kích thước chữ. Vì thế, để phát hiện được các chuỗi ký tự đa dạng như vậy người ta phải tìm cách tạo ra các quy tắc cũng như một số quy ước tổng thể làm căn cứ thì mới có thể giải quyết được bài toán nhận dạng phức tạp này. Theo đó, OCR luôn cố gắng tích hợp và phát triển cả công nghệ phần cứng lẫn những thuật toán và xây dựng hệ thống phần mềm để từng bước nhận dạng chữ viết với khả năng càng giống với con người càng tốt. Tuy nhiên, cũng như những công nghệ nhận dạng khác, vì phải làm việc với dữ liệu ảnh đầu vào cực kỳ phức tạp là chữ viết, nó được tạo ra một cách tự do đó là không có một quy tắc nhất định hay bất kỳ ràng buộc nào về độ lớn, đường nét, độ đậm nhạt, sự kết nét hay đứt nét…khi người ta viết chữ. Hay ngay cả khi đánh máy tính thì với mỗi loại văn bản cũng được quy định bởi những phông chữ, cỡ chữ và 22 cách trình này khác nhau. Điều này tạo nên khó khăn rất lớn cho OCR trong khi nhận dạng nếu gặp phải những ảnh tài liệu chữ viết hoặc văn bản có nhiều điểm nhiễu hay bị liền nét giữa các con chữ hay bị đứt nét trong một con chữ hoặc gặp phải chữ viết không được nắn nót. Một khi chữ viết tay không nắn nót hoặc máy tính áp dụng một số phông chữ không được chân phương, không thường dùng thì thí dụ chữ u rất giống với chữ v, số 6 giống với số 0 hoặc giống với số 4, số 3 giống với số 9 (Hình 1.10a). Và sẽ càng khó khăn hơn khi mà cấu trúc của những từ ngữ lại được xây dựng cả con số lẫn với chữ cái như số tài khoản sử dụng trong các ngân hàng do máy tính tạo ra, hay thói quen viết tay các ký tự dính nét nhau khi tạo thành một từ hoặc là những từ viết tắt chẳng hạn (Hình 1.10b). Hình 1.10a: Mô tả những nét chữ viết tay không nắn nót dẫn đến rất khó nhận dạng bằng công nghệ OCR. Nguồn: Dengel (2001). Nguồn: Dengel (2001) Hình 1.10b: Mô tả chữ viết tay với thói quen viết liền nét giữa số 4 và số 2 dẫn đến rất khó nhận dạng và tách biệt hai con số bằng công nghệ OCR 23 Công nghệ OCR là một hệ thống rất phức tạp của nhiều bước và nhiều công đoạn thực hiện khác nhau. Trong đó có một số bước thực hiện cơ bản gồm có phương pháp thực hiện và nhận dạng ký tự dựa trên ngữ cảnh như sau đây. 1.5.1 Phương pháp Việc trích chọn các tính năng và phân loại để chia không gian đa chiều thành các vùng tương ứng là những phần cốt lõi của công nghệ OCR trong đó có áp dụng một số thuật toán chuyên biệt. Theo đó, thuật toán phân loại dựa trên các tính năng của ảnh được trích chọn và những đặc điểm liên quan giữa các tính năng đó sẽ được áp dụng để phân lớp trước các loại ký tự và phân bổ một ký tự nhận dạng được vào trong một lớp tương ứng. Để phân bổ được một ký tự vào một lớp nào đó người ta sử dụng tính chất về độ đo tương thích và thực hiện quá trình xử lý từ ngữ dựa trên ngữ cảnh để hiệu chỉnh một số lỗi mà OCR chưa thể khắc phục được. 1.5.1.1 Trích chọn các tính năng Các tính năng của đối tượng được trích xuất và sắp xếp dưới dạng những độ đo. Song song với quá trình này, người ta xây dựng các lớp dữ liệu chứa các ký tự bằng cách tạo ra một mô hình chung nhất cho các lớp đó. Từ đó tiếp tục thực hiện quá trình chọn lựa tính năng đặc trưng bằng cách tìm kiếm và so sánh các thuộc tính của từ ngữ đang nhận dạng trên cơ sở các lớp đã được xây dựng trước đó. Cụ thể, các tính năng thường được đưa vào lớp để so sánh bao gồm các điểm bắt đầu, điểm kết thúc, các dấu hiệu nối như gạch nối giữa hai thành phần để tạo nên ký tự mà cả chữ A và chữ H đều có, các góc, các cạnh, các điểm uốn, điểm cắt, mặt lỗi lõm của các đường bao bên ngoài cũng như các đường nét đặc trưng cơ bản của ký tự và của từ. Cuối cùng các sản phẩm là những tính năng của các ký tự đã được trích chọn và phân bổ vào từng lớp thích hợp. Nhưng trong quá trình phân lớp thì OCR thường gặp phải những khó khăn khi phân định các lớp có những đặc trưng tương tự nhau, như những đặc trưng của chữ o và số 0, chữ l và số 1 hay ký tự này quay đầu thì trở thành ký tự khác như ký tự số 6 và số 9, chữ d và chữ p, v.v… 1.5.1.2 Phân loại Nhìn chung nếu chỉ áp dụng một tính năng duy nhất thì không thể nhận dạng được ký tự cũng như không thể tạo ra được các lớp đa dạng của những ký tự
- Xem thêm -