CHƯƠNG 1 – ĐỀ XUẤT GIẢI PHÁP TIỀN XỬ LÝ ẢNH Sau khi nhận được ảnh từ máy quét, ảnh thu được có thể bị nghiêng do đặt lệch giấy trong quá trình quét hoặc có thể có nhiễu nền. Những nguyên nhân này làm cho các vùng nhập liệu trên ảnh bị thay đổi vị trí, biến dạng. Do đó tiền xử lý là một bước rất quan trọng, tạo tiền đề để có thể nhận dạng ảnh chính xác và hiệu quả. Các giải pháp được áp dụng trong hệ thống bao gồm : lọc nhiễu và nhị phân hóa [3], xác định góc nghiêng dựa trên phép chiếu [3] và xác định góc nghiêng dựa trên các block.1 Lọc nhiễu và nhị phân hoá.
Thông thường văn bản được quét và lưu trữ dưới dạng ảnh đa mức xám trong khi đó hầu hết các thuật toán về xử lý và phân tích văn bản đều dựa trên ảnh nhị phân. Việc sử dụng ảnh nhị phân chỉ với hai mức trắng và đen giảm bớt được khối lượng tính toán và đơn giản hoá các phương pháp phân tích so với ảnh xám( 256 mức). Do vậy việc tìm ra một thuật toán nhị phân hóa nhanh và hiệu quả là một điều rất cần thiết Nhiều phương pháp về nhị phân hóa ảnh đã được phát triển, trong số đó có những phương pháp đem lại kết quả rất tốt. Có thể kể đến như thuật toán dựa trên sự biến thiên về cường độ mức xám ở các vùng khác nhau của văn bản [24], thuật toán về tính ngưỡng nhị phân cục bộ [18] hay thuật toán dựa trên đa độ phân giải [17] … Tuy nhiên các phương pháp này thường áp dụng đối với những hình ảnh tổng quát và đòi hỏi tính toán phức tạp bởi vì đều phải tính đến cấu trúc của ảnh.
Trong bài toán này, chúng tôi chỉ xử lý trên các văn bản kiểu form nhập liệu, vốn dĩ là các ảnh đơn giản chỉ gồm hai mức đen (để thể hiện chữ) và trắng (nền của văn bản); văn bản cũng thường phân bố khá đồng đều. Chính vì vậy việc nhị phân hóa ảnh có thể được thực hiện chỉ dựa trên lược đồ xám của ảnh mà không phụ thuộc vào cấu trúc. Trên cơ sở này, chúng tôi đã kết hợp các kỹ thuật thực hiện nhiều lần tăng cường độ tương phản bằng cách điều chỉnh mức xám, phân ngưỡng tự động để nhị phân hoá ảnh. Mô tả thuật toán Ảnh của văn bản gốc vốn dĩ là ảnh nhị phân, tức là chỉ có hai ngưỡng đen, trắng cho chữ và nền.
Song sau khi in ra và quét lại vào máy tính, nó trở thành ảnh đa mức xám tức là có 256 ngưỡng khác nhau. Một số vùng nền có thể xám hơn, ngược lại một số đối tượng chữ, bảng và dòng kẻ có thể mờ đi. Nhiệm vụ của chúng ta ở đây là tách các đối tượng cần xử lý ra khỏi hình nền. Thuật toán được xây dựng dựa trên giả thiết tổng diện tích của hình( chữ và đối tượng trên form) so với diện tích ảnh là nhỏ ,và tuy có sự biến đổi về ngưỡng nhưng vẫn có sự khác biệt tương đối giữa ngưỡng của chữ và của nền.
Thông qua việc LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 tăng cường độ tương phản lặp lại nhiều lần, ta hi vọng rằng có thể khuyếch đại sự khác biệt này một cách đáng kể. Ảnh là một tập các điểm ảnh, được biểu diễn bởi công thức : I x, y n n [0,255] Công thức 1-1 Trong đó x,y là các trục tọa độ của ảnh và n có thể lấy bất kì giá trị nào trong khoảng [0, 255]. Khi n = 255 thì đó là điểm trắng, n = 0 thì đó là điểm đen. Khi đó giá trị trung bình của mức xám là: x W y H I ( x, y ) x 0 y 0 W : Width T W H H : Height Công thức 1-2 Hình 1-1: Lƣợc đồ mức xám của ảnh Với giả định rằng tổng số lượng điểm ảnh biểu diễn cho chữ và các đối tượng chứa thông tin là nhỏ so với kích cỡ của ảnh, và các điểm ảnh này cũng có mức xám nhỏ hơn so với các điểm ảnh nền, chúng tôi cho rằng giá trị trung bình của mức xám của ảnh được quyết định bới các điểm ảnh nền.
Dựa trên giả thiết này, để tăng độ tương phản của ảnh – tức là làm tăng độ nổi của các điểm ảnh chứa thông tin so với nền, chúng tôi coi như tất cả các điểm ảnh có mức xám lớn hơn giá trị của mức xám trung bình là các điểm ảnh nền và đặt lại mức xám của chúng là 255 (trắng). Sau bước biến đổi này ta thu được một ảnh mới: I ' ( x, y) n' (n' [0, T ] {255}) Công thức 1-3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Tiếp đó để tăng cường độ tương phản của ảnh sau khi chọn T là ngưỡng để tách nền, ta tăng cường độ tương phản của ảnh mới thông qua việc giãn khoảng của mức xám [2] của các điểm ảnh có mức xám nhỏ hơn mức xám trung bình từ [0,T] lên [0,255] n1 f ( n ') 255.n ' f ( n ') T Công thức 1-4 Cuối cùng ta thu được ảnh mới : I1 ( x, y) n1 (n1 [0,255]) Công thức 1-5 Hình 1-2: Đồ thị biến đổi mức xám LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Hình 1-3: Ảnh trƣớc (a) và sau biến đổi lần 1 (b) Công việc trên được thực hiện lặp đi lặp lại cho đến khi hình ảnh đạt được đến một độ sạch cần thiết. Điều kiện kết thúc là khi mức xám trung bình của ảnh trước và sau khi biến đổi không thay đổi. Ta có thể tóm tắt quy trình lọc nhiễu như sau : Bƣớc 1 : Tính giá trị trung bình T W H I ( x, y) x 0 y 0 k Tk W H Công thức 1-6 Bƣớc 2 : Loại nền cho ảnh dựa vào Tk I ( x, y ) I k ( x, y ) Tk I k' ( x, y ) k 255 I k ( x, y) Tk Công thức 1-7 Bƣớc 3 : Tăng độ tương phản cho ảnh mới LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 I k 1 f ( I k' ) Công thức 1-8 Bƣớc 4 : Lặp lại bước 1 cho tới khi giá trị T giữa 2 lần lọc liên tiếp nhau là gần như nhau Với cách lọc trực tiếp trên ảnh ở trên, thì tiếp chi phí tính toán cho phương pháp lọc này chủ yếu tập trung vào chi phí tính toán ở Tk và Ik+1.
Trong công thức tính Tk, giá trị của Tk chỉ phụ thuộc vào giá trị của Ik(x,y) chứ không phụ thuộc vào vị trí. Nếu ta lưu lại được giá trị này thì sẽ không cần đọc lại ảnh trong mỗi bước lặp. Để giảm chi phí tính toán cho phép lọc này chúng ta chỉ tính lược đồ histogram của ảnh, sau đó tất cả các tính toán đều thực hiện trên lược đồ histogram với 256 phần tử( so với 1241x1755 điểm ảnh của ảnh trang A4 scan với độ phân giải 150DPI). Phép lọc ảnh được thực hiện nhiều lần chỉ trên lược đồ mức xám và cuối cùng mới thực hiện phép biến đổi tăng độ tương phản( công thức 2-7) cho ảnh cuối Ifinal.
Ta có thể hình dung các bước thực trên lược đồ mức xám như sau: Bước 1 : Xác định lược đồ mức xám của ảnh Bước 2 : Tính giá trị trung bình Tk, dựa vào lược đồ mức xám Bước 3 : Biến đổi lược đồ mức xám dựa trên Tk Bước 4 : Lặp lại bước 2, cho tới khi Tk và Tk-1 gần như nhau. Bước 5 : Thực hiện điều chỉnh độ tương phản cho ảnh gốc cuối cùng dựa trên kết quả của lược đồ mức xám ở bước cuối. Sau cùng, khi ảnh đã được lọc nền và làm sạch, ta tiến hành nhị phân hóa ảnh. Ngưỡng nhị phân được chọn là: 3 Threshold T final 10 N 4 Công thức 1-9 Trong đó Tfinal là mức xám trung bình trong bước biến đổi cuối cùng, N là số bước thực hiện biến đổi.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Ta thu được ảnh đã lọc nhiễu và nhị phân hóa như trong hình vẽ Hình 1-4: (a) Ảnh scan; (b) Ảnh sau lần lọc thứ nhất; (c) Ảnh sau lần lọc cuối cùng; (d) Ảnh sau khi nhị phân hóa Dựa trên kết quả thực nghiệm sau khi áp dụng thuật toán đối với 60 form văn bản thuộc về 4 loại khác nhau, chúng tôi thấy rằng kết quả thu được hoàn toàn có thể so sánh với kết quả của các thuật toán khác. Thời gian để nhị phân hóa ảnh có độ phân giải là 300 DPI với 10 lần lặp chỉ là 66 ms. Điều này chứng minh rằng thuật toán có thể áp dụng rất hiệu quả khi ta cần xử lý văn bản với số lượng lớn.2 Xác định góc nghiêng của ảnh Văn bản bị nghiêng xảy ra trong quá trình copy hoặc khi quét vào máy tính, điều này ảnh hưởng đến toàn bộ các đối tượng có trong văn bản nhất là các vùng mà ta cần phải nhận dạng. Văn bản bị nghiêng là một điều không thể tránh khỏi, và trong nhiều trường hợp gây ảnh hưởng không tốt đến độ chính xác đối với kết quả phân vùng và nhận dạng ký tự.
Cũng có một số phương pháp về phân vùng ảnh không yêu cầu văn bản phải có góc nghiêng bằng không [5, 25]. Tuy nhiên các phương pháp này vẫn đòi hỏi góc nghiêng của văn bản nằm trong một khoảng giới hạn cho phép. Bên cạnh đó, đơn giản hóa vấn đề này sẽ dẫn tới phức tạp hóa cũng như tốn thời gian xử lý đối với các nhiệm vụ khác. Do đó chính xác lại góc nghiêng của ảnh là một việc làm tất yếu và phải được thực hiện trước khi tiến hành phân vùng và nhận dạng ảnh.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Hình 1-5: (a) ảnh sau khi khử nhiễu và tách nền; (b) ảnh sau khi khử nghiêng Các văn bản có rất nhiều đặc trưng khác nhau như đặc trưng về hướng, về cấu trúc phân bố các đối tượng. Từ đó cũng có một số phương pháp xác định góc nghiêng cho ảnh của văn bản tương ứng như các phương pháp dựa trên phép biến đổi Hough [9,19,14,29,34], hàng xóm gần nhất( Nearest Neighbour) [7,30,37], phép chiếu [6,8,22,36] , đối tượng liên kết [28,31], và một số phương pháp khác [10,15,32,38]. Mỗi phương pháp có một cách tiếp cận khác nhau cùng những ưu điểm và nhược điểm nhất định. Một số phương pháp có khả năng tìm góc nghiêng trong khoảng [-50,+50] cho đến [-450,+450].