Khóa luận Nghiên cứu và xây dựng hệ thống nhập dữ liệu tự động bằng nhận dạng quang học

xác định lân cận nó. Vì khoảng cách giữa các đối tượng này nhỏ, nên độ chính xác sẽ được tăng lên rất nhiều. Do các vùng ta cần tách có thể nằm ở bất kì chỗ nào nên ta không thể thêm các đối tượng như đường thẳng dày hay khung vào khắp nơi trên ảnh. Thay vào đó ta phải sử dụng các đối tượng đã có sẵn trong form như text line, text block,… Và vì các đối tượng này luôn luôn sẵn có nên ta cũng không cần thêm vào ảnh bất cứ đối tượng nào để đánh dấu như phương pháp tọa độ tuyệt đối. Phương pháp này tỏ ra ưu việt hơn phương pháp tọa độ tuyệt đối rất nhiều, tuy nhiên về tư tưởng cũng như cách cài đặt của phương pháp này rất phức tạp. Cũng nảy sinh một số vấn đề như chọn đối tượng nào để làm mốc trong các đối tượng đã có trên form hay làm thế nào để nhận dạng ra các đối tượng đó. Hình 15: Xác định các block trên form để làm mốc xác định các vùng cần tách [10] Nhận xét : Ưu điểm : có độ chính xác cao. Nhược điểm : khó cài đặt, tính toán phức tạp Đề xuất giải pháp khử nghiêng và phân vùng ảnh Khử nghiêng Trong việc xử lý văn bản, trước tiên văn bản được quét vào máy tính. Sau đó, nó sẽ được lọc nhiễu và nhị phân hóa để tạo ra một hình ảnh chỉ có hai mức đen và trắng. Bước tiếp theo là chính xác lại góc nghiêng của ảnh.Thông thường các thuật toán nhận dạng chỉ có thể áp dụng đối với các ảnh có góc nghiêng nhỏ. Do đó việc tìm góc nghiêng là một công việc hết sức quan trọng và nó có ảnh hưởng rất lớn đối với việc nhận dạng chính xác văn bản. Hiện nay đã có rất nhiều phương pháp xác định góc nghiêng cho một tài liệu dạng ảnh thuộc nhiều kiểu khác nhau từ tổng quát đến cụ thể. 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. Các phương pháp xác định góc nghiêng dựa trên các đối tượng liên kết ( connected component) rất hiệu quả với những ảnh có nhiều kí tự, tuy nhiên lại khá nhạy cảm với nhiễu. Các phương pháp dựa trên phép biến đổi Hough mặc dù có thể áp dụng trên các văn bản tổng quát lại đòi hỏi khối lượng tính toán lớn cũng như phải biến đổi ảnh qua nhiều bước mới áp dụng được. Các phương pháp dựa trên phép chiếu hiệu quả với các ảnh phân bố đều và có hướng nhưng xử lý vẫn còn rất phức tạp. Qua việc nghiên cứu rất nhiều dạng Form văn bản khác nhau bao gồm cả văn bản tiếng việt và tiếng anh cùng với việc nghiên cứu nhiều thuật toán [8,9,11,14,15,18,14], chúng tôi thấy rằng phương pháp phép chiếu là một phương pháp thích hợp để xác định góc nghiêng của các form văn bản trong phạm vi của bài toán. Bởi vì : Phương pháp phép chiếu cho kết quả với độ chính cao trên các form văn bản thuộc pham vi của bài toán. Có thể thực hiện một số cải tiến để giảm bớt khối lượng tính toán. Dễ hiểu, dễ bảo trì. Phương pháp xác định góc nghiêng dựa trên phép chiếu. Tư tưởng cơ bản của phương pháp này dựa trên đặc trưng của văn bản đó là các dòng chữ hoặc các đối tượng khác như bảng hoặc các đoạn thẳng thường được đặt một cách có thứ tự. Các chữ thường được đặt theo từng dòng, giữa các dòng có khoảng cách; các bảng hoặc hình hộp cũng thường được đặt theo chiều ngang. Do đặc trưng này nên khi ta chiếu các điểm đen của một văn bản với góc nghiêng bằng không theo chiều ngang thì ta sẽ thu được một đồ thị rất sắc và có độ biến thiên lớn. Với các văn bản bị nghiêng, ta có thể thấy là phép chiếu sẽ tạo ra một đồ thị trơn và thấp hơn. Dựa trên việc đánh giá các đồ thị này ta sẽ tìm được góc nghiêng chính xác của ảnh. Hình 16: (a)ảnh với góc nghiêng bằng không; (b) đồ thị của phép chiếu ngang trên ảnh (a) Hình 17: (a) Ảnh với góc nghiêng 50; (b) Đồ thị của phép chiếu ngang trên ảnh (a) Mô tả phương pháp phép chiếu [11] : Các điểm đen trên hình ảnh sẽ được chiếu theo các đường thẳng song song vào một mảng tích lũy ( A). Mỗi phần tử của mảng tương ứng với một đường chiếu và giá trị của nó là số điểm đen nằm trên đường chiếu đó. Sử dụng phép chiếu đối với mỗi góc nghiêng giả định, ta thu được một tập các mảng tích lũy ( Aθ). Dựa vào hàm đánh giá F ( Aθ) với MINANGLE ≤ θ ≤ MAXANGLE, ta tìm được góc nghiêng chính xác θ của ảnh là góc làm cho giá trị của hàm đánh giá F ( Aθ) đạt cực đại. Dựa trên các đặc trưng của văn bản ta có hai hàm đánh giá : Công thức 2: Đánh giá độ biến thiên trên đồ thị của phép chiếu (Dựa trên đặc điểm : đồ thị phép chiếu của văn bản với góc nghiêng chính xác thường có độ biến thiên lớn) Công thức 3: Đánh giá các khoảng trống trên đồ thị của phép chiếu (Dựa trên đặc điểm : đồ thì phép chiếu của văn bản với góc nghiên chính xác thường có nhiều khoảng trống và có khoảng trống rộng hơn) Áp dụng phương pháp phép chiếu, ta thử với từng góc θ nằm trong khoảng ( MINANGLE, MAXANGLE). Góc θ tìm được là góc có hàm đánh giá tương ứng đạt giá trị cực đại. Tối ưu các tham số. Văn bản sau khi qua máy quét thường tạo ra một hình ảnh bị nghiêng với góc nghiêng nằm trong khoảng [-150, 150]. Ta sẽ tìm góc nghiêng của ảnh trong khoảng này ( MINANGLE = -15, MAXANGLE = 15). Đây là một khoảng xác định phù hợp, vì nếu khoảng tìm kiếm quá lớn sẽ làm tăng thời gian xử lý, ngược lại nếu khoảng quá nhỏ thì có nhiều khả năng góc nghiêng sẽ nằm ngoài khoảng. Trong trường hợp góc nghiêng của hình ảnh vượt quá khoảng tìm kiếm thì điều đó cũng sẽ được phát hiện trong bước xử lý tiếp theo ( phân vùng ảnh), khi đó ta sẽ thực hiện tìm kiếm lại góc nghiêng với một khoảng tìm kiếm rộng hơn. Độ chênh lệch trong việc chọn từng góc θ trong khoảng tìm kiếm cũng có ảnh hưởng quan trọng đối với hiệu năng và độ chính xác. Ví dụ như nếu mỗi góc θ cách nhau một khoảng 0.1 và khoảng tìm kiếm là ±150 thì cần xét với 300 trường hợp, độ chính xác của góc nghiêng thu được là ±0.10. Việc tính hàm ước lượng đối với tất cả các góc nghiêng có thể như vậy là không cần thiết, thay vào đó chúng tôi sử dụng khoảng cách 20 để ước lượng ở bước đầu tiên. Sau đó dựa vào kết quả thu được, chúng tôi thu hẹp khoảng tìm kiếm và khoảng cách giữa các góc cần ước lượng để đạt được độ chính xác cao hơn. Cụ thể là sau bước đầu tiên, ta đã ước lượng được góc nghiên của ảnh là β với độ chính xác ±2o, Bước tiếp theo sẽ tiếp tục tìm kiếm góc nghiêng trong khoảng (β - 2o, β + 2o) với khoảng cách giữa các góc cần ước lượng là 0.4o. Sau bước này ta lại có một ước lượng về góc nghiêng mới là β’ với độ chính xác là ±0.4o. Cứ tiếp tục như vậy cho đến khi ta đạt được độ chính xác cần thiết là ±0.1o . Thực nghiệm cho thấy trong bước đầu tiên, nếu lấy khoảng cách là 10 hoặc 20 không làm thay đổi độ chính xác của thuật toán. Để tăng cường hơn nữa hiệu quả tính toán, trong bước đầu tiên khi độ chính xác là nhỏ, do đó không cần phải sử dụng ảnh lớn và chi tiết. Chúng tôi sử dụng ảnh cỡ khoảng 50DPI ( thu nhỏ từ ảnh ban đầu) cho các bước ước lượng ban đầu, còn trong các bước tiếp theo thì sử dụng ảnh gốc để đảm bảo độ chính xác. Hình 18: (a) Ảnh scan. (b) Ảnh sau khi chính xác góc nghiêng Ưu điểm của phương pháp : Phương pháp phép chiếu để xác định góc nghiêng của ảnh cho kết quả rất chính xác đối với ảnh của form nhập dữ liệu do có nhiều đường thẳng Tư tưởng của phép chiếu trong sáng, dễ cài đặt Tuy phép chiếu đòi hỏi tính toán phức tạp nhưng ta có thể tăng tốc được bằng cách sử dụng đường thẳng theo phương pháp Bresenham và kỹ thuật sử dụng bảng lookup table Nhược điểm : Cho kết quả không chính xác lắm đối với các ảnh có kích thước nhỏ do ta sử dụng các đường chiếu là các đường thẳng trong hệ tọa độ nguyên nên các đường thẳng này chỉ là xấp xỉ, ảnh càng lớn thì các đường thẳng này càng chính xác => càng cho kết quả chính xác hơn. Các hàm ước lượng về biểu đồ của phép chiếu chưa thể hiện được hết bản chất của phép chiếu. Mỗi công thức chỉ mô tả được một khía cạch cụ thể. Xác định vùng nhận dạng dựa trên xác định các đường thẳng Sau các bước xử lý lọc nhiễu và xác định góc quay của ảnh, công việc tiếp theo cần tiến hành đó là xác định các vùng văn bản cần xử lý, đây cũng chính là đầu vào cho phần nhận dạng dữ liệu. Chú ý rằng văn bản chúng tôi xử lý ở đây là văn bản dạng form nhập dữ liệu dựa trên mẫu form đã có sẵn. Sau khi form được nhập dữ liệu và quét lại vào máy tính, dựa trên mẫu có sẵn và đối chiếu với ảnh scan, ta tìm các vùng trên ảnh scan được nhập dữ liệu và xử lý nhận dạng trên các vùng này. Dữ liệu sau khi nhận dạng sẽ được lưu lại tương ứng với các trường dữ liệu trong form mẫu. Khi xử lý văn bản, ta không cần nhận dạng toàn bộ văn bản mà chỉ giới hạn nhận dạng trên các vùng mà thông tin được nhập vào. Xác định các vùng cần nhận dạng luôn luôn là công việc quan trọng nhất trong nhận dạng form nhập dữ liệu. Một số phương pháp thường dùng hiện nay để xác định các vùng này đã được nêu ở phần tổng quan như : dùng hệ tọa độ tuyệt đối và hệ tọa độ tương đối để phân vùng. Trong phương pháp thứ nhất, do trong quá trình scan, ảnh có thể bị biến dạng làm cho vị trí các vùng thay đổi. Thêm vào đó, sai số trong việc xác định góc quay và độ dịch của ảnh cũng ảnh hưởng đến vị trí tuyệt đối của các vùng. Theo phương pháp này, các vùng càng xa gốc tọa độ thì sai số về vị trí càng lớn. Tuy nhiên phương pháp này đơn giản và dễ cài đặt. Phương pháp thứ hai là phương pháp sử dụng tọa độ tương đối, tiêu biểu là phương pháp xác định các block, sau đó dựa vào các block này để tính vị trí tương đối của các vùng cần tách [10]. Trong phương pháp này, các khối trong ảnh sẽ được đối chiếu với các khối trong form mẫu. Sau đó vùng nhập dữ liệu sẽ được xác định thông qua tọa độ cục bộ. Phương pháp này tỏ ra rất hiệu quả đối với sai số về vị trí do văn bản bị dịch hoặc bị nghiêng trong một giới hạn cho phép. Mặc dù vậy, việc xác định các block trong ảnh không phải là công việc đơn giản, hơn thế nữa việc đối chiếu một số lượng lớn block với form mẫu đòi hỏi các phép tính phức tạp. Các block mang thông tin chỉ chiếm một tỉ lệ nhỏ và việc đối chiếu đúng phần lớn các block không hề có ý nghĩa trong việc nhận dạng về sau, trong khi đó nếu đối chiếu sai các block chứa vùng nhập dữ liệu sẽ làm sai hoàn toàn kết quả nhận dạng. Dựa trên đặc điểm của kiểu form nhập dữ liệu là dữ liệu được nhập vào các ô trên form ( nghĩa là nằm trong giới hạn giữa các đường thẳng) Chúng tôi đưa ra thuật toán xác định vùng nhập dữ liệu thông qua việc xác định các đường thẳng. Trong phương pháp này, trước tiên chúng tôi nhận dạng tất cả các đường thẳng có trong ảnh. Sau đó các đường thẳng này sẽ được đối chiếu với các đường thẳng có trong form mẫu để xác định thứ tự chính xác và khử nhiễu. Cuối cùng sau khi nhận dạng được các đường thẳng, vùng nhập dữ liệu sẽ được tính thông qua tọa độ gián tiếp tới các đường thẳng đó. Và bởi vì các tọa độ gián tiếp này là các tọa độ địa phương nên độ chính xác trong việc xác định các vùng là rất cao. Mô tả thuật toán xác định đường thẳng: Trong ảnh của văn bản cần xử lý, các đường thẳng thường không phải là các đường thẳng lý tưởng mà chỉ là một tập hợp các điểm ảnh có thể xấp xỉ bởi một đường thẳng. Trong bài toán này, do việc tính toán vị trí các vùng nhận dạng sử dụng hệ tọa độ tương đối theo chiều thẳng đứng và theo chiều ngang nên trong việc xác định đường thẳng không cần xem xét đến các đường thẳng theo các hướng khác. Theo giả thiết ở trên chúng tôi đưa ra thuật toán xác định đường thẳng dựa vào số lượng các điểm ảnh đen kề nhau liên tiếp theo chiều thẳng đứng và theo chiều ngang ( còn gọi là các black run). Một đường thẳng bao gồm một tập các black run liền kề nhau. Ngưỡng nhận dạng cũng được áp dụng để loại bỏ các black run quá ngắn ( các black run thuộc về đường thẳng hay thuộc về chữ hoặc các đối tượng đồ họa khác). Sau khi duyệt toàn bộ ảnh để lọc ra các black run đủ dài, các black run này sẽ được nhóm lại để tạo thành các đường thẳng. Thuật toán xác định đường thẳng Thuật toán được thực hiện qua bốn bước Bước 1: Duyệt toàn bộ ảnh, loại bỏ các black run ngắn, chỉ giữ lại các black run đủ dài ( lớn hơn ngưỡng) Bước 2 : Hợp các black run gần nhau lại để tạo thành đường thẳng. Bước 3 : Sau khi hợp các black run lại thành đường thẳng, thực hiện lại bước lọc với ngưỡng nhận dạng lớn hơn để giữ lại các đường thẳng đủ dài. Bước 4 : Lọc các đường thẳng còn lại dựa theo tỉ lệ giữa độ rộng và độ cao của đường. Các đường thẳng đạt tiêu chẩn là các đường thẳng có tỉ lê : độ rộng/độ cao > 10 hoặc độ cao/độ rộng > 10 ( bởi vì các đường thẳng của ta có đặc điểm là dài và hẹp). Bước này sẽ lọc được chữ hoặc hình ảnh có kích cỡ lớn trong văn bản. Kết quả của việc lọc các đường thẳng : Hình 19: (a) Ảnh sau khi tiền xử lý; (b) Ảnh sau khi lọc các black run ngắn theo chiều ngang (c) Ảnh sau khi hợp cách black run dài theo chiều ngang; (d) Ảnh sau khi lọc các black run ngắn theo chiều thẳng đứng (e) Ảnh sau khi hợp các black run dài theo chiều thẳng đứng (f) Các đường thẳng xác định được trên ảnh Trong việc lọc các đường thẳng, nếu lấy ngưỡng nhận dạng quá lớn thì các đường thẳng thu được sẽ không đầy đủ, ngược lại nếu lấy ngưỡng quá nhỏ thì sẽ còn lại rất nhiều nhiễu do chữ và các đối tượng đồ họa. Khi xử lý với những ảnh chứa các đường thẳng có độ dày ≥ 2 pixel, ta có thể lấy ngưỡng tương đối lớn mà không làm mất thông tin trong việc nhận dạng đường. Tuy nhiên, bởi vì chúng ta phải xử lý với cả những ảnh scan có chất lượng kém nên cần tìm ra giải pháp để khắc phục việc mất thông tin. Biện pháp khắc phục việc xác định các đường thẳng mờ hoặc đứt đoạn Theo trên, ta đã coi đường thẳng như một tập các điểm đen kề nhau. Để giảm bớt việc mất thông tin trong những trường hợp đường thẳng bị đứt đoạn hoặc quá mờ, ta có thể xem xét lại đường thẳng như là một tập các điểm đen có thể rời rạc, tuy nhiên phải thỏa mãn điều kiện : mật độ điểm đen trên một đường phải lớn hơn một ngưỡng alpha xác định ( trong bài toán này chúng tôi lấy là 0.7). Kết quả của việc xác định đường thẳng có tính đến mật độ : Hình 20: (a) Đường thẳng mờ và bị đứt doạn (b) Đường thẳng xác định được khi tính đến mật độ Việc tính đến mật độ của đường thẳng có thể dẫn đến việc nhận dạng lầm một số dòng chữ đậm hoặc viết sát là đường thẳng. Do đó sau khi xác định các đường thẳng theo thuật toán ở trên (mục 3.2.1.1) với ngưỡng nhận dạng tương đối lớn để lọc hết các đối tượng chữ và đồ họa ta mới áp dụng biện pháp này trên các đường thẳng xác định được để giảm bớt mức độ mất mát thông tin. Một vấn đề nữa trong việc tính đến mật độ của đường thẳng đó là việc dồn cục không đồng đều về mật độ dẫn đến việc xác định nhầm độ dài đường thẳng. Như hình dưới, số đường thẳng cần xác định là hai đường mặc dù mật độ điểm giữa điểm đầu và điểm cuối của đường thẳng xác định được vẫn lớn hơn ngưỡng. Hình 21: Xác định nhầm đường thẳng do phân bố không đều trên đường Để giải quyết vấn đề này, ta chỉ xét mật độ trên các đoạn ngắn, sau đó ghép các đoạn ngắn đó lại với nhau để tạo thành đường. Như vậy, theo cách này thì: một đường được coi là đường thẳng nếu nó là tập hợp các điểm đen theo chiều thẳng đứng hay theo chiều ngang với một độ dài đủ lớn, các điểm đen này có thể không cần chạm nhau tuy nhiên phải đảm bảo mật độ của đường và của từng phần cục bộ trên đường lớn hơn một ngưỡng xác định. Hình 22: Chia đường thẳng thành các đoạn ngắn rồi tính mật độ trên các đoạn này Đối chiếu các đường thẳng xác định được với Form mẫu. Trong bước xác định đường thẳng, ta đã cố gắng để giảm sự mất thông tin ít nhất có thể được cũng như giảm tối đa nhiễu. Tuy nhiên không bỏ qua giả thiết có một số đường tương ứng với form mẫu mà ta không xác định được hoặc xác định thừa một số đường do ảnh hưởng của nhiễu. Nhiệm vụ của bước đối chiếu đường thẳng là tìm đúng vị trí và thứ tự của các đường xác định được tương ứng với các đường trong form mẫu, để trên cơ sở đó tính tọa độ tương đối. Phương pháp đối chiếu các đường thẳng Việc đối chiếu các đường thẳng được thực hiện độc lập theo chiều thẳng đứng và theo chiều ngang. Xét trường hợp đối chiếu các đường theo chiều ngang, giả sử trong form mẫu ta có N đường thẳng, ta tìm được N’ đường thẳng trong ảnh scan. Như vậy, ta cần xác định các cặp tương ứng nhiều nhất có thể được giữa N đường trong form mẫu và N’ đường trong ảnh scan. Ta cũng biết rằng tồn tại một tỉ lệ giữa form gốc và ảnh scan, các cặp đường thẳng tương ứng được xác định dựa trên tỉ lệ này. Do tỉ lệ giữa hai ảnh là không biết trước ( tỉ lệ của kích thước ảnh không phải là tỉ lệ chính xác và chỉ có thể sử dụng như một tham số để ước lượng), để xác định tỉ lệ này ta giả định một cặp đường thẳng trong form mẫu tương ứng với một cặp đường thẳng trên ảnh scan. Từ đây ta xác định được một tỉ lệ ước lượng, tỉ lệ này được đánh giá dựa trên số đường thẳng còn lại từ hai tập thỏa mãn tỉ lệ ước lượng này. Tỉ lệ nào cho số cặp thỏa mãn nhiều nhất là tỉ lệ giữa hai ảnh. Cách xác định tỉ lệ như trên dựa trên giả thiết là có ít nhiễu và không bị mất nhiều thông tin trên ảnh scan. Các nhiễu nếu có cũng phân bố một cách ngẫu nhiên và có kích thước nhỏ so với các đường thẳng xác định đúng. Để chính xác hóa hơn nữa trong việc ghép cặp các đường thẳng, chúng tôi đưa ra thêm một tham số ước lượng về khoảng cách và kích thước. Ước lượng về khoảng cách và kích thước : Khoảng cách và kích thước của một đường được ước lượng dựa trên tất cả các đường thẳng trong một tập. Bởi vì tồn tại một tỉ lệ giữa hai tập đường thẳng nên ta phải đưa ra một tham số ước lượng độc lập với tỉ lệ của hai tập để so sánh. a)Ước lượng về độ dài : Tổng độ dài của các đường trong tập mẫu là Ln, của các đường trong tập cần so sánh là Ln’. Khi đó ta có các công thức sau để ước lượng độ dài : Công thức 4: ước lượng độ dài tương đối của một đường trong tập mẫu Công thức 5: công thức ước lượng độ dài tương đối của một đường trong tập đích (li : là độ dài tuyệt đối của đường thứ i trong tập mẫu; l’j : là độ dài tuyệt đối của đường thứ j trong tập đích) Hai đường thẳng tương ứng nhau sẽ có tham số ước lượng về độ dài xấp xỉ nhau. b)Ước lượng về khoảng cách: Ta xác định tọa độ tâm của tập các đường thẳng mẫu và tập các đường thẳng đích theo chiều thẳng đứng : Công thức 6: tọa độ tâm của tập các đường trong tập mẫu Công thức 7: tọa độ tâm của tập các đường trong tập đích Công thức để ước lượng khoảng cách của một đường thẳng tới tâm : Công thức 8: khoảng cách tới tâm của đường thẳng i trong tập gốc Công thức 9: khoảng cách tới tâm của đường thẳng j trong tập đích (hi : là độ cao của đường thứ i trong tập mẫu; h’j : là độ cao của đường thứ j trong tập đích) Hai đường thẳng tương ứng nhau sẽ có tỉ lệ tham số ước lượng về khoảng cách tới tâm bằng với tỉ lệ giữa hai ảnh. KL : Với giả thiết việc xác định các đường thẳng có ít nhiễu, nhiễu có kích thước nhỏ và các đường thẳng không bị mất thông tin, dựa vào các tham số đánh giá về kích thước và khoảng cách, ta biết được việc ghép cặp các đường thẳng trên hai tập cho kết quả có chính xác hay không. Xác định ngưỡng để nhận dạng các đường thẳng Ngay cả trên form mẫu, mặc dù không có các nhiễu ngẫu nhiên xuất hiện do quá trình scan ảnh, thì vẫn còn tồn tại rất nhiều đối tượng nhỏ như chữ hay các biểu tượng dùng trong form…Các đỗi tượng này vẫn được coi là nhiễu khi xác định các đường thẳng. Ta cần phải chọn một ngưỡng thích hợp để có thể loại bỏ được hết các đối tượng này. Mặt khác, ta chỉ quan tâm đến các đường thẳng tương đối dài – tức là các đường thẳng mà ta có thể “tin cậy” được vì xác xuất mất các đường này là rất nhỏ. Do đó cũng cần chọn ngưỡng sao cho có thể loại được cả những đường thẳng quá ngắn. Chọn ngưỡng thích hợp có ý nghĩa rất quan trọng trong việc xác định đường thẳng. Nếu lấy ngưỡng quá ngắn thì sẽ có nhiều nhiễu, ngược lại nếu ngưỡng quá dài thì sẽ bị mất nhiều đường. Qua quá trình thực nghiệm, tôi đã xác định ngưỡng nhận dạng tốt nhất là ngưỡng có kích thước gấp ba lần kích thước của loại font chữ phổ biến nhất trong ảnh. Nếu form mẫu được tạo ra do trình editor của chính chương trình thì ta có thể xác định ngay được kích thước của các font chữ. Tuy nhiên để có thể sử dụng lại các form đã có từ trước, ta cũng cần phải xác định được kích thước của font chữ trên một “ảnh chuẩn” bất kì. Phương pháp xác định font chữ trung bình được thực hiện qua các bước như sau : Xác định kích thước của tất cả các đối tượng có trong ảnh. Loại bỏ tất cả các đối tượng có kích thước quá nhỏ ( nhỏ hơn 3 hoặc 4 pixel) Loại bỏ tất cả các đối tượng có sự chênh lệch quá lớn về kích thước giữa chiều rộng và chiều dài ( thông thường thì chênh lệch về kích giữa chiều rộng và chiều dài của chữ tối đa là bốn lần) Tính kích thước trung bình của các đối tượng còn lại Loại bỏ các đối tượng có kích thước quá lớn hay quá nhỏ so với kích thước trung bình. Tính lại kích thước trung bình một lần nữa. Đây chính là kích thước ta cần tìm Qua thực nghiệm cho thấy kích thước tìm được theo phương pháp trên chỉ chênh lệch so với kích thước của loại font chữ phổ biến nhất trong ảnh một vài pixel. Hình 23: Ảnh cần xác định kích thước font chữ trung bình Hình 24: Hình chữ nhật bao các đối tượng tìm được trên ảnh Hình 25: Hình chữ nhật bao quanh các đối tượng chữ tìm được trên ảnh Phương pháp xác định kích thước các đối tượng có trong ảnh Trước tiên ta quan niệm rằng : đối tượng là tập hợp các điểm đen kề nhau theo tám hướng mà không bị đứt đoạn, ta có thể hiểu một cách khái quát mỗi đối tượng là một miền liên thông trên ảnh. Trên cơ sở như vậy chúng ta có hai phương pháp xác định các đối tương : phương pháp gán nhãn phương pháp đệ quy mở rộng vùng liên thông Xác định kích thước các đối tượng bằng phương pháp gán nhãn. Ta có các chữ là tập hợp của các điểm đen biễu diễn như trên hình vẽ, ta định nghĩa black run là tập hợp các điểm đen liên tiếp kề nhau, một black runs cũng có thể chỉ gồm một điểm đen duy nhất. Tập hợp các black runs tạo nên đối tượng Hình 26: Đối tượng tạo bởi các black run Giải thuật xác định các đối tượng dựa trên việc gán nhãn [7] có thể được mô tả cụ thể như sau : (I) Đối với mỗi dòng của ảnh : (A) Xác định các black runs (B) Nếu đây là dòng đầu tiên hoặc dòng trước đó là một dòng trắng thì gán cho mỗi black run một nhãn mới. Nếu không thì thực hiện các bước sau đối với mỗi black run tìm được trên dòng hiện tại : (1) Nếu nó không chạm vào bất kì black run nào của dòng trước đó thì gán cho nó một nhãn mới. (2) Ngược lại, gán cho nó nhãn của black run mà nó gặp đầu tiên. (3) Ta tiến hành gán lại nhãn đối với các black runs mà nó gặp sau đó (sau khi nó đã được gán nhãn bởi black run mà nó gặp đầu tiên). Ta sử dụng nhãn của nó để gán cho những black run này và tất cả các black run gắn liền với các black run này. (II) Cuối cùng việc xác định các đối tượng trên ảnh dựa vào nhãn của các black runs. Các black runs có cùng nhãn thì cùng thuộc về một đối tượng. Giải thuật 31 Hình ảnh minh họa cho thuật toán : Hình 27: Gán nhãn các đối tượng trên ảnh nhị phân Xác định kích thước các đối tượng bằng phương pháp đệ quy mở rộng vùng liên thông Xuất phát từ định nghĩa : đối tượng là tập hợp các điểm đen kề nhau theo tám hướng mà không bị đứt đoạn. Để xác định được đối tượng, khi gặp một điểm đen đầu tiên ta sẽ lần đệ quy theo tám hướng xung quanh điểm đen này cho đến khi không thể tiếp tục được nữa. Do đối tượng là một miền liên thông nên xuất phát từ một điểm trên đối tượng, ta có thể tìm được tất cả các điểm đen còn lại [16]. Nảy sinh một vấn đề đó là tồn tại những đối tượng có quá nhiều điểm đen. Ví dụ như ta có một hình hộp đen có chiều rộng bằng chiều cao và bằng 100. khi đó số lượng điểm đen trên đối tượng là 100*100 = 10000. Nghĩa là khi xác định đối tượng ta có thể sẽ phải thực hiện đệ quy tới 10.000 lần ! Việc này chắc chắn sẽ dẫn đến treo chương trình. Do vậy ta cần có một quá trình tiền xử lý để giảm bớt số lượng điểm đen trước khi tìm kiếm đệ quy theo chiều sâu để xác định đối tượng. Việc tiền xử lý để giảm bớt số lượng điểm đen được tiến hành như sau: [Với mỗi điểm đen, kiểm tra tám hướng xung quanh nó, ta sẽ xóa điểm đen này nếu tất cả các điểm xung quanh nó cũng đều là điểm đen.] Kết quả của việc giảm bớt các điểm đen : Hình 28: Ảnh sau khi giảm bớt các điểm đen Do ta chỉ cần xác định kích thước của mỗi đối tượng nên việc giảm bớt các điểm đen trước khi tìm kiếm không ảnh hưởng đến kết quả đạt được. Sau khi loại bỏ bớt các điểm đen thì số lần phải tính đệ quy đã giảm đi nhiều lần. Ta tiến hành tính toán hình hộp bao quanh mỗi đối tượng ( hình hộp này được xác định dựa trên tọa độ của đỉnh trên bên trái Xmin, Ymin và đỉnh dưới bên phải Xmax, Ymax) kính thước của đối tượng cũng chính là kích thước của hình hộp bao quanh nó. Giải thuật xác định hình hộp bao quanh mỗi đối tượng được mô tả như sau: FOR i = 1 TO no_of_rows FOR j = 1 TO no_of_columns IF pxl[i,j] = 1 SET MAX_X = MIN_X = i SET MAX_Y = MIN_Y = j CALL PROC MCR (i,j) PROC MCR (cur_x, cur_y) FOR 8 ngbr_pxl OF pxl[cur_x, cur_y] IF ngbr_pxl = 1 IF ngbr_pxl_x > MAX_X SET MAX_X = ngbr_pxl_x IF ngbr_pxl_x < MIN_X SET MIN_X = ngbr_pxl_x IF ngbr_pxl_y > MAX_Y SET MAX_Y = ngbr_pxl_y IF ngbr_pxl_y < MIN_Y SET MIN_Y = ngbr_pxl_y SET ngbr_pxl = 0 CALL PROC MCR (ngbr_pxl_x, ngbr_pxl_y) Giải thuật 32 Theo giải thuật này, trước hết ta duyệt ảnh lần lượt từ trên xuống, mỗi khi gặp một điểm đen ( điểm đen này thuộc về một đối tượng nào đó và ta phải tìm được hình hộp bao quanh đối tượng này) ta thực hiện một thủ tục đệ quy MCR (cur_x, cur_y) ( với cur_x và cur_y là tọa độ của điểm hiện tại) để tìm tất cả các điểm đen xung quanh nó theo tám hướng. Nếu nó có điểm lân cận ngbr_pxl là điểm đen ta tiến hành cập nhập lại tọa độ của hình hộp bao quanh rồi lại gọi thủ tục MCR (ngbr_pxl_x, ngbr_pxl_y) để tìm tất cả các điểm đen lân cận với điểm này. Công việc tiếp tục cho đến khi không tìm thêm được điểm đen nào thuộc đối tượng hiện tại. Như vậy khi duyệt ảnh, khi gặp một điểm đen, bằng việc tìm kiếm đệ quy theo tám hướng ta có thể xác định được toàn bộ đối tượng mà điểm đen đó thuộc về. Kết quả xác định các hình hộp bao quanh mỗi đối tượng Hình 29: Kết quả xác định các đối tượng Hình 30: Hình chữ nhật bao quanh các đôi tượng tìm được Kết luận : thực nghiệm cho thấy việc xác định kích cỡ chữ trung bình cho kết quả rất chính xác, thời gian tính toán khoảng 0.5 giây đối với ảnh có độ phân giải 300DPI. Nếu ta chỉ tiến hành nhận dạng đối với một form thì đây là một khoảng thời gian hoàn toàn chấp nhận được. Tuy nhiên khi ta phải xử lý hàng nghìn form nhập liệu thì đây cũng là một khoảng thời gian đáng kể. Để rút ngắn thời gian này, ta chỉ cần tính kích thước chữ trung bình cho form mẫu. Đối với ảnh scan, kích thước chữ trung bình được tính bằng kích thước chữ trung bình trong form mẫu nhân với tỉ lệ kích thước giữa hai ảnh. Lưu các đặc trưng của form Như đã xác định bài toán ở trên, nhận dạng form nhập dự liệu thực chất là bài toán nhận dạng trên ảnh đã biết trước cấu trúc. Do đó ta cần lưu lại các đặc trưng của form mẫu trong file template để làm tham số cho việc nhận dạng sau này. Các đặc trưng của form mẫu lưu trong file template cần càng chi tiết càng tốt để thuận lợi cho việc nhận dạng các ảnh scan của nó. Các thông tin thường được lưu trong file template : thông tin chi tiết về các đối tượng trên từng dòng thông tin về vị trí của các cụm chữ có trong form ( header, text, ...) ; nội dung, kích cỡ, font chữ thông tin về các đối tượng form : check box, input... thông tin về bảng biểu nếu có. Thông tin về các đối tượng hình học : đường thẳng, hình hộp... Và cuối cùng quan trọng nhất là thông tin về những vùng sẽ được nhập dữ liệu trên form Ví dụ : file template Ncs-16504.rco sử dụng trong Remark Classic OMR 2.5 Demo của Principia Products [Form] Name=Ncs-16504.rco Version=2.0 FormType=1 Manufacturer=National Computer Systems Description= NumPages=2 NumFields=29 LithocodeItems=0 NumItems=209 SkunkMarkPresent=-1 SkunkMarkLocation=1 SkunkMarkEnd=47 SkunkMarkStart=1 SkunkMarkOrientation=0 LithocodePresent=0 LithocodeShowGrid=0 RDDName= [Page] Columns=48 TimingMarks=53 NumFields=19 LithocodeItems=0 NumItems=109 SkunkMarkValue=00000001000000000000000000000000000000000010100 ReadHeadMarkPresent=0 ReadHeadMarkLocation=1 ReadHeadMarkEnd=48 ReadHeadMarkStart=1 ReadHeadMarkOrientation=0 ReadHeadMarkValue=111111111111111111111111111111111111111111111111 BarcodePresent=0 [Field] Name=Last Name LithocodeField=0 NumItems=1 FieldType=1 DataType=0 RecogType=0 Orient=1 Read=1 Required=0 Choices=Z,Y,X,W,V,U,T,S,R,Q,P,O,N,M,L,K,J,I,H,G,F,E,D,C,B,A, StartCol=17 NumCols=27 ColGap=1 StartRow=3 NumRows=12 RowGap=1 Measurement= Mults=* MultsAllowed=0 SelectBest=0 RespondentID=0 SubjectiveField=0 Blanks= Tally=0 Grade=0 Correct=0 Incorrect=0 NoResponse=0 Pattern= ……. Nói chung người ta cố gắng lưu càng nhiều và càng chi tiết thông tin về form trong file template càng tốt. Cũng có thể nói file template chính là file lưu lại kết quả nhận dạng chi tiết của form mẫu. Như mô tả ở trên, hệ thống được xây dựng có module quản trị form. Module này cho phép người dùng có thể soạn thảo form ngay trong chương trình. Như vậy ta có thể dễ dang lưu các thông tin chi tiết về form vào file template. Thực tế là không cần phải tiến hành nhận dạng trên các form này. Tuy nhiên module quản trị form cũng cần có khả năng sử dụng lại các form đã có từ trước hoặc được tạo ra bởi các trình soạn thảo khác.Điều này tạo khả năng sử dụng linh hoạt hệ thống hơn đối với người sử dụng, và cũng theo đó không cần phải tạo ra trình soạn thảo form quá phức tạp. Chính vì vậy ta cần thiết kế module nhận dạng các cấu trúc đặc trưng trên các form này để đưa vào file template, phục vụ cho việc nhận dạng trên các bản scan của nó về sau. Để tránh phức tạp trong việc nhận dạng các thông tin chi tiết trên các form đã có sẵn. Ta sẽ chỉ đưa vào file template của các form này cấu trúc đặc trưng của form cần thiết cho việc nhận dạng các bản scan của nó. Còn đối với các vùng cần nhận dạng thì sẽ do người dùng tự định nghĩa. Các phần mềm như FormFiller, Remark Office OMR Template Editor, … cũng có chức năng tương tự : Hình 31: FormFiller của hãng ABBYY Hình 32: Remark Office OMR Template Editor của Princia Produtcs Theo phương pháp phân vùng đã đề xuất ở trên, với một form mẫu bất kì, chỉ cần lưu thông tin về các đường thẳng có trong form và các vùng sẽ được nhập thông tin là đủ để nhận dạng các ảnh scan của nó sau này. Việc xác định các đường thẳng trên form mẫu vẫn làm theo cách như đã trình bày trong mục 3.2.1.1 Và bởi vì các form mẫu là các form chuẩn, nghĩa là chúng không có nhiễu và nhất là không bị nghiêng, nên việc xác định đường thẳng sẽ cho kết quả rất chính xác Cuối cùng ta đưa ra cấu trúc của file template như sau : 2560, 3295 // ImageFormSize (Width,Height) 15, 21 // AvgFontSize (Width,Height) 16 // NumOfHorizontalLine 1165, 411, 1725, 414 // HorizontalLine (Xmin,Ymin,Xmax,Ymax) 680, 771, 1558, 774 680, 843, 1558, 846 995, 1491, 2286, 1494 995, 1563, 2286, 1566 995, 1635, 2286, 1638 755, 1707, 1502, 1710 755, 1779, 1502, 1782 995, 2019, 2286, 2022 …………… 110 // NumOfVerticalLine 680, 771, 683, 846 // VerticalLine (Xmin,Ymin,Xmax,Ymax) 755, 771, 758, 846 755, 1707, 758, 1782 755, 2163, 758, 2238 755, 2619, 758, 2694 811, 771, 814, 846 811, 1707, 814, 1782 811, 2163, 814, 2238 811, 2619, 814, 2694 ……………. 197 // NumOfInputField 684, 776, 70, 68 // InputField (Xmin,Ymin,Xmax,Ymax) 760, 776, 49, 66 816, 776, 49, 66 872, 776, 60, 68 937, 776, 59, 66 1000, 776, 49, 66 1055, 776, 49, 66 ……………. Tách vùng nhập dữ liệu trên ảnh scan Sau khi xác định các đường thẳng trên ảnh scan và đối chiếu các đường thẳng này với các đường thẳng trên form mẫu thông qua các thông tin được lưu trong file template, ta tiến hành tách các vùng cần nhận dạng dựa trên các đường thẳng được đối chiếu chính xác. Xét thông tin về một vùng cần nhận dạng trên form mẫu, vùng này là một vùng hình chữ nhật được xác định bởi đỉnh trên bên trái và đỉnh dưới bên phải với tọa độ tuyệt đối (Xmin,Ymin) , (Xmax,Ymax) . Mục đích của ta là tách ra vùng tương ứng với vùng này trên ảnh scan. Để đảm bảo cho chất lượng nhận dạng của module nhận dạng chữ viết, ảnh thường được scan với độ phân giải 150DPI đến 300DPI. Những ảnh này thường có kích thước lớn, do đó sai số về vị trí khi tách vùng trên ảnh scan tương ứng với vùng nhập liệu trên ảnh mẫu dựa vào tọa độ tuyệt đối cũng lớn. Mặt khác, với nhận xét từ trước là khoảng cách giữa các vùng nhập thông tin đến các đường thẳng là nhỏ, để giảm bớt sai số ta sẽ tách vùng dựa trên vị trí tương đối của các vùng nhập thông tin đối với các đường thẳng. Giả sử như khi nhận dạng các đường thẳng, một số đường thẳng bị mất do ảnh quá mờ, Khi đó vị trí của vùng nhập thông tin sẽ được xác định thông qua đường thẳng gần nó nhất mà ta xác định được. Các bước để thực hiện tách vùng : Tìm các đường thẳng gần vùng cần tách nhất theo bốn hướng : trên, dưới, trái, phải mà các đường này đã được đối chiếu và ta đã nhận dạng được đường thẳng tương ứng với nó trên ảnh scan Xác định vị trí tương đối của vùng đối với các đường thẳng này Dựa vào thông tin về vùng cần tách, vị trí tương đối của nó đối với các đường thẳng lân cận và hệ số thay đối kích thước giữa hai ảnh, ta tính ra được vùng cần tách trên ảnh scan. Hình 33: (a) Ảnh mẫu; (b) Định nghĩa các vùng nhập dữ liệu trên ảnh mẫu; (c) Ảnh scan sau khi tiền xử lý; (d) Kết quả tách vùng trên ảnh scan Từ hình vẽ trên ta thấy, do các vùng cần tách nằm sát các đường thẳng nên các vùng này được tách rất chính xác. Thực nghiệm Môi trường thực nghiệm Chương trình được cài đặt trên ngôn ngữ visual C++ 6, và được thử nghiệm trên Máy tính Pentium IV 1.8 GHz, bộ nhớ RAM 256 MB sử dụng hệ điều hành Windows 2000 Server và Windows XP SP1, Chuẩn bị cơ sở dữ liệu Với mục đích đánh giá độ chính xác và hiệu năng thực hiện của các phương pháp trên, chúng tôi đã tuyển tập rất nhiều các tài liệu dạng ảnh trên các kiểu form khác nhau như: phiếu đăng ký, phiếu điều tra, hóa đơn, phiếu thanh toán, bảng điểm….Các ảnh này được tìm thấy phần lớn là thông qua trang tìm kiếm Google.com để có thể đảm bảo được sự đa dạng về kiểu form, về chất lượng ảnh, về kích cỡ và ngôn ngữ. Bên cạnh đó chúng tôi cũng tự thiết kế một số mẫu form đồng thời tiến hành thu thập các mẫu form trên thực tế ( form tiếng việt). Trên các ảnh kiểu form nhập dữ liệu này bao gồm nhiều đối tượng khác nhau như textline, bảng, check box, picture. Tất cả các ảnh này đều có kích thước như khổ A4, và được scan với nhiều độ phân giải khác nhau, từ 100 đến 300 DPI ( tương ứng với kích thước 827x1170 đến 2481x3510 pixel cho mỗi một ảnh). Chúng tôi sử dụng 60 ảnh trong cơ sở dữ liệu ảnh để kiểm thử, các ảnh này được chia làm 4 loại được liệt kê trong bảng. Với mỗi một ảnh, chúng tôi thực hiện kiểm thử với 300 góc nghiêng khác nhau – mỗi góc nghiêng lệch nhau 0.1o, khoảng góc nghiêng lớn nhất mà chúng tôi thực hiện là ±15o, đây cũng là khoảng góc phù với các máy scan dạng nạp giấy tự động. Bảng 1: phân loại ảnh Loại ảnh Số lượng Cat 1 Tài liệu thông thường 5 Cat 2 Tài liệu có chứa ảnh 5 Cat 3 Tài liệu có chứa bảng 20 Cat 4 Tài liệu hỗn hợp 30 Do đặc điểm của văn bản dạng Form, các vùng cần nhận dạng phải nằm trong các khoảng đường thẳng nào đó, do vậy tập dữ liệu cần để kiểm thử cho module xác định các vùng cần nhận dạng chỉ gồm các ảnh loại 3 và 4. Thực nghiệm về xác định góc nghiêng của ảnh Thực nghiệm về xác định góc nghiêng của ảnh được cài đặt theo phương pháp phép chiếu trên 60 ảnh, với 300 góc nghiêng khác nhau cho mỗi một ảnh được nêu trong mục 4.2, tổng số ảnh thử nghiệm là 18000 ảnh. Bảng 2: Kết quả thực nghiệm xác định góc nghiêng với một số góc tiêu biểu Góc thực Kết quả trên ảnh 150 DPI (0) Kết quả trên ảnh 300 DPI (0) 5 5 5 5.1 5.1 5.1 5.2 5.2 5.2 5.3 5.2 5.3 5.4 5.4 5.4 5.5 5.5 5.5 5.6 5.6 5.6 5.7 5.7 5.7 5.8 5.8 5.8 5.9 5.9 5.9 6 6 6 Qua kết quả thực nghiệm trên ta thấy với những ảnh bé, góc nghiêng xác định được chỉ có thể đạt được độ chính xác là ±0.30 đến ±0.20, Với những ảnh lớn thì độ chính xác cao hơn rất nhiều. Điều này là do các điểm ảnh có tọa độ nguyên, khi ta sử dụng các đường chiếu theo phương pháp Bresenham thì các đường chiếu này không phải là các đường thẳng hoàn toàn. Ảnh càng lớn thì các đường này càng chuẩn hơn và càng cho kết quả chính xác hơn Kết quả chúng tôi thu được đối với độ lệch trung bình (0) so với góc thực tế trên tất cả các category: Bảng 3: Độ lệch trung bình so với góc thực tế Phương pháp phép chiếu (0) Cat 1 0.0383 Cat 2 0.0351 Cat 3 0.0177 Cat 4 0.0246 Total 0.0289 Kiểm thử hiệu năng với ảnh 100 DPI, 150 DPI, 200 DPI, 300 DPI, kết quả thu được trong bảng 4 Bảng 4: Kiểm thử hiệu năng DPI Phương pháp phép chiếu (ms) Phương pháp phép chiếu đã tối ưu các tham số (ms) 100 225.36 90.33 150 503.60 120.42 200 895.61 200.67 300 2003.2 350.73 Thực nghiệm về Phân vùng ảnh Việc phân vùng ảnh, được thực hiện sau khi chính xác hóa góc nghiêng của ảnh, chúng tôi đã thực hiện kiểm thử theo từng bước: Thực nghiệm 1: Xác định các đường thẳng Với tập ảnh thực nghiệm chúng tôi chia ra làm 2 loại : Loại 1 gồm các ảnh có tập các đường thẳng với độ dày là 1 pixel và Loại 2 gồm các ảnh có tập các đường thẳng với độ dày ≥ 2 pixel. Thực hiện kiểm thử về độ chính xác cho việc xác định đầy đủ các đường thẳng chính ở trên ảnh Scan so với ảnh mẫu. Bảng 5: Độ chính xác của phương pháp xác định đường thẳng DPI Độ chính xác – Loại 1 (%) Độ chính xác – Loại 2 (%) 100 73.35 96.14 150 87.61 98.85 200 91.53 99.15 300 94.11 99.46 Kết quả thực nghiệm thu được cho thấy, để đạt được độ chính xác cao chúng ta nên sử dụng các ảnh có độ dày các đường thẳng tối thiểu là 2 pixel. Khi kiểm thử với tập các đường 1 pixel, với các góc nghiêng lớn, thì sau khi xác định được góc nghiêng và xoay lại ảnh, các đường thẳng này có dạng răng cưa và bị đứt đoạn do đó chỉ có thể xác định được các đoạn thẳng rất ngắn, dễ bị khử đi, dẫn tới việc mất một số đường thẳng chính. Trong khi đó với tập các đường thẳng có độ dày là 2 pixel thì sau khi xoay lại, các đường thẳng ít bị đứt đoạn, khi đó sẽ tạo ra được các đoạn thẳng dài, và có thể nhận dạng khá đầy đủ các đường thẳng chính. Thực nghiệm 2: Tìm cặp các đường thẳng giữa ảnh scan với ảnh mẫu. Trong phần thực nghiệm này, trước tiên chúng tôi thực hiện kiểm thử với những ảnh được scan, sau đó với những ảnh scan đó chúng tôi kẻ thêm các đường nhiễu hoặc xóa bớt các đường thẳng ngang và dọc, nhưng vẫn đảm bảo trong ảnh đó có ít nhất 3 đường thẳng ngang và 3 đường thẳng dọc, và số đường thêm vào hoặc bớt đi phải không quá ¼ số đường có trong ảnh mẫu. Kết quả thực nghiệm cho trong bảng Bảng 6: Độ chính xác của phương pháp ghép cặp các đường thẳng trong tập mẫu và tập ảnh mới Độ chính xác (%) Ảnh sau khi scan 99.61 Ảnh scan và thêm các đường thẳng 98.57 Ảnh scan và xóa bớt các đường thẳng 99.19 Ảnh scan và được thêm, bớt các đường thẳng 97.33 Thực nghiệm 3 : tìm kích thước trung bình trên ảnh chuẩn Thực nghiệm này được thực hiện trên các ảnh chuẩn được tạo ra ngay trên máy tính. Trên ảnh sử dụng nhiều loại font chữ khác nhau, nhiều đối tượng khác nhau, bao gồm cả hình ảnh. Kết quả thu được như sau : Bảng 7: Kết quả xác định kích thước trung bình của các đối tượng Font chữ phổ biến nhất Kích thước font chữ Kích thước trung bình xác định được theo chiều thẳng đứng Kích thước trung bình xác định được theo chiều thẳng ngang Times New Roman 12 11 9 Hình 34 : (a) ảnh chuẩn; (b) Một phần của ảnh được phóng to Hiệu năng xử lý : Bảng 8: Thời gian xác định kích thước trung bình DPI Thời gian xử lý (ms) 150 230 200 320 300 670 Thông thường, ta chỉ phải xử lý “một lần” để xác định kích thước trung bình của các đối tượng trên ảnh chuẩn nên thời gian xử lý không phải là một vấn đề quan trọng cần tối ưu. Thực nghiệm 4: Xác định các vùng cần nhận dạng Chúng ta thực hiện việc phân vùng bằng cách xác định các vị trí cục bộ của vùng cần nhận dạng so với vị trí của đường thẳng gần nó nhất cả theo chiều dọc và theo chiều ngang. Với cách làm này chúng tôi đã thực hiện kiểm thử với các trường hợp sau: Trường hợp 1: Vùng cần xác định gần với các đường thẳng gần nó nhất, khi đó sai số về vị trí của vùng được tính toán thực tế là nhỏ, do vậy trong trường hợp này chúng tôi xác định chính xác các vùng. Trường hợp 2: Vùng cần nhận dạng nằm các xa các đường thẳng gần nó nhất, do vậy khi thực nghiệm chúng tôi thấy các vị trí các vùng thường bì dịch chuyển so với vị trí ban đầu, dẫn tới bị mất một ít thông tin – hình 35 Hình 35: Vùng cần xác định bị lệch so với vùng xác định thực tế Nguyên nhân của việc mất thông tin này là do giữa ảnh scan và ảnh mẫu có sai số về tỉ lệ kích thước ( hệ số scale). Để hạn chế việc mất thông tin, chúng ta cần thêm tham số về độ dịch chuyển. Tham số này phụ thuộc vào hệ số scale và khoảng cách giữa vùng cần xác định với đường thẳng gần nó nhât. Kết quả sau khi áp dụng tham số về độ dịch chuyển cho ở hình 36. Hình 36: (a) Ảnh mẫu, các hình chữ nhật màu đỏ biểu diễn các vùng cần được xác định. (b) Kết quả thu được sau khi phân vùng Thực nghiệm tích hợp các thành phần Hình 37: Giao diện chính của chương trình (1): Nhập ảnh đầu vào. (2): Lưu ảnh. (3): Chức năng lọc nhiễu: chức năng này cho phép chúng thực hiện lọc nhiễu, tách nền và nhị phân hóa với ảnh. (4): Chức năng chính xác góc nghiêng của ảnh: chức năng này cho phép chúng ta thực hiện xác định góc nghiêng và quay ảnh lại tương ứng với góc nghiêng đấy. (5): Chức năng phân vùng: chức năng này cho phép chúng ta có thể thực hiện xác định các vùng cần nhận dạng bằng cách kết hợp Template File với ảnh đầu vào để thu được các vùng cần nhận dạng. (6): Chức năng phóng to ảnh: chức năng này cho phép chúng ta có thể phóng to ảnh hiện tại. Mức phóng to lớn nhất là 16 lần so với kích thước thực của ảnh. (7): Chức năng thu nhỏ ảnh: chức năng này cho phép chúng ta có thể thu nhỏ ảnh hiện tại. Mức thu nhỏ tối thiểu là 0.25 lần so với kích thước thực của ảnh. (8): Chức năng hiển thị kích thước thực: chức năng này cho phép hiện thị ảnh dưới kích thước thực của nó. (9): Chức năng tạo Template File: Chức năng này cho phép chúng ta có thể tạo ra một số thông tin trong ảnh mẫu phục vụ cho chức năng phân vùng. Các thông tin có thể được tạo như: thông tin về các đường thẳng ngang, dọc; thông tin về kích thước ảnh; thông tin về ngưỡng của các đường thẳng ngang và dọc. (10): Tab: Cho phép chúng ta chuyển đổi giữa các ảnh một cách dễ dàng. Lần thực nghiệm này chúng tôi thực hiện xử lý tích hợp các phần như: Nạp ảnh, xử lý nhiễu, chính xác góc quay, xử lý phân vùng. Kết quả về hiệu năng được cho trong bảng. Bảng 9: Kết quả kiểm thử tích hợp DPI Nạp ảnh (ms) Lọc nhiễu (ms) Xác định góc xoay (ms) Xoay ảnh (ms) Xử lý phân vùng (ms) Tổng thời gian (ms) 200 232.19 36.81 101.69 116.29 92.13 579.11 300 396.77 95.21 118.93 282.44 101.35 994.70 Hình 38: Nhập Template File Hình 39: Lưu Template File Kết luận Qua quá trình nghiên cứu về nhập dữ liệu tự động bằng phương pháp quang học, chúng tôi đã tìm ra những giải pháp thích hợp đối với đặc điểm của văn bản dạng form nhập dự liệu để từ đó tiến hành cài đặt các module cần thiết cho quá trình tiền xử lý ảnh như: lọc nhiễu và tách nền; chính xác góc nghiêng của ảnh; xác định các vùng cần nhận dạng. Cùng với việc nhận dạng chữ viết tay tiếng việt đã được các tác giả Nguyễn Thị Minh Ánh, Lê Việt Cường, Trần Trí Hoài [1] và một số tác giả khác thực hiện tại bộ môn Công nghệ Phần mềm, chúng tôi hy vọng sẽ kết hợp 2 phần lại tạo thành một sản phẩm nhận dạng hoàn chỉnh cho hệ nhập dữ liệu tự động. Trong quá trình nghiên cứu rất nhiều dạng Form văn bản khác nhau, bao gồm cả các văn bản tiếng Việt và tiếng Anh và việc nghiên cứu nhiều thuật toán khác nhau, chúng tôi đã lựa chọn, cải tiến và đưa ra được một số các giải pháp riêng cũng như cài đặt thành công các thuật toán về lọc nhiễu, tách nền và xác định góc nghiêng của ảnh. Việc tách nhiễu tỏ ra rất hiệu quả cho những ảnh có mức xám của nền và các kí tự in cũng như chữ viết tay là gần như nhau. Với những ảnh được scan 200, 300 DPI việc xác định góc nghiêng với độ chính xác là +0.1, cho tỉ lệ chính xác lên tới 98.91%. và tôc độ xử lý cũng rất nhanh cỡ 0.07 – 0.15 (s). Việc xác định các vùng cũng cho kết quả rất khả quan. Trên những văn bản dạng Form với các đường thẳng có độ dày tối thiểu 2 pixel, khi phân vùng cho độ chính xác rất cao ≥ 99%, và thời gian thực thi cỡ 0.045 – 0.17 (s) tùy thuộc vào số đường thẳng được xác định trong ảnh scan và trong tập mẫu. Giải pháp của chúng tôi cho việc phân vùng dựa trên việc xác định các đường thẳng ngang và thẳng đứng trong ảnh scan tỏ ra hiệu quả ngay cả trong trường hợp có nhiễu và mất mát thông tin và đã góp phần đáng kể vào kết quả nhận dạng chung. Với độ chính xác cao của việc tiền xử lý ảnh chúng tôi hy vọng khi kết hợp với module nhận dạng chữ viết tay tiếng Việt sẽ đem lại nhiều hứa hẹn. Cùng với các kết quả đã đạt được, hệ thống vẫn còn rất nhiều hạn chế như module phân vùng hiện mới làm việc tốt với những đường thẳng có độ dày tối thiểu là 2 pixel, cũng như vẫn còn rất nhiều phần việc chưa được thực hiện để để có thể đưa ra được một sản phẩm hoàn chỉnh. Vì vậy, trong thời gian tới, chúng tôi dự định sẽ tiếp tục nghiên cứu, cải tiến và hoàn thiện hệ thống với mục địch cuối cùng tạo ra một sản phẩm hoàn thiện có thể áp dụng ngay được trong thực tế góp phần đáng kể vào xu hướng số hóa của nước ta hiện nay. Các công việc sẽ được nghiên cứu tiếp như: Tích hợp với module nhận dạng chữ viết tiếng việt. Xây module quản trị tài liệu dạng Form. Nâng cao hiệu năng và độ chính xác cho module tiền xử lý ảnh và phân vùng. Phụ lục A : Một số thuật ngữ Anh-Việt Thuật ngữ Giải nghĩa Black run Tập hợp các điểm đen liên tiếp kề nhau theo chiều thẳng đứng hoặc theo chiều ngang trên ảnh Block Một hoặc một cụm các đối tượng được coi là liền kề nhau Bounding Box Hình hộp bao quanh một đối tượng hay một khối các đối tượng Deskew Khử nghiêng DPI Dots per inch – Số lượng các điểm trên một inch Form Recognition Nhận dạng form Object Là một tập hợp các điểm đen liền kề nhau để tạo nên một đối tượng như chữ cái, đường thẳng, điểm, … Region Extraction Tách vùng Resolution Độ phân giải Skewed Image Ảnh bị nghiêng Tài liệu tham khảo Tài liệu tham khảo tiếng Việt N.T.M. Ánh, Đ.V. Cường, N.T. Hoài. Ứng dụng mạng Neural trong nhận dạng văn bản., Khoa Công Nghệ, ĐHQGHN. NCKH SV 2004 Lương Mạnh Bá, Nguyễn Thanh Thủy. Nhập môn xử lý ảnh số. Nhà xuất bản khoa học và kỹ thuật 5/1999, tr143-144 Phan Văn Thuận, Ứng dụng nhận dạng trong xử lý kết quả điều tra, Luận văn tốt nghiệp ngành công nghệ thông tin – Đại Học Quốc Gia Hà Nội, Khoa Công Nghệ, 2004, tr21-22 Tài liệu tham khảo tiếng Anh A. Antonacopoulos and R.T. Ritchings, Representation and Classification of Complex-shaped Printed Regions Using White Tiles, In: Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, Canada, 1995, tr.1132-1135. Bo Yuan, Leong Keong Kwoh, and Chew Lim Tan. Finding Best-Fit Bounding-Boxes. Center of Remote Imaging, Sensing and Processing National University of Singapore, Singapore 119260 ; Department of Computer Science, School of Computing National University of Singapore, Singapore 117543. 2001, tr2. Dipti Deodhare, NNR Ranga Suri, R.Amit. Preprocessing and Image Enhancement Algorithms for a Form-based Intelligent Character Recognition System. International Journal Of Computer Science & Application, Vol. II, No. II, pp. 131-144. 2005 tr131-135 D. X. Le, G. Thoma. Document Skew Angle Detection Algorithm. Proc. 1993 SPIE Symposium on Aerospace and Remote Sensing - Visual Information Processing II, Orlando, FL April 14-16, 1993, Vol. 1961, tr. 251-262 E.Kavallieratou, D.C.Balcan, M.F.Popa, N.Fakotakis IEEE member. Handwritten text localization in skewed documents. University of Bucharest 14, Academiei St., 79543 Bucharest, RomaniaWire Communications Laboratory University of Patras, 26500 Patras, Greece. Int. Conference on Document Analysis and Recognition, ICDAR'99. 1999, tr. 705 – 708 Fu Chang, Chien-Hsing Chou, and Shih-Yu Chu. A New Approach to Estimation of Document Skew Angles Based on Piecewise Linear Approximation of Line Objects. Institute of Information Science, Academia Sinica, Taipei, Taiwan, R.O.C. NSC93-2422-H-001-0004. CVGIP ( Graphical Models and Image Processing), 2004, tr1-3 Hanchuan Peng, Member, IEEE, Fuhui Long, and Zheru Chi, Member, IEEE. Document Image Recognition Based on Template Matching of Component Block Projections. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.25, NO.9, SEPTEMBER 2003. tr1188-1192 Junichi Kanai, Andrew D. Bagdanov. Projection profile based skew estimation algorithm for JBIG compressed images. IJDAR (1998), tr43-51 J. L. Chen and H. J. Lee. An efficient algorithm for form structure extraction using strip projection. Pattern Recognition, 31 (9): 1353–1368, May 1998. tr1353–1368 K. Etemad, D. Doermann, and R. Chellappa, Multiscale Segmentation of Unstructured Document Pages Using Soft Decision Integration, IEEE Trans. on Pattern Recognition and Machine Intelligence, Vol. 19, No. 1, 1997, tr. 92-96. Oleg Okun, Matti Pietik¨ainen and Jaakko Sauvola. Robust Skew Estimation on Low-Resolution Document Images. Machine Vision and Media Processing Group, Infotech Oulu and Dept. of EE, University of Oulu. Tr1-4 R. Cattoni, T. Coianiz, S. Messelodi, and C. M. Modena. Geometric layout analysis techniques for document image understanding: a review. Technical report, IRST, Trento, Italy, 1998. tr5 Shamik Sural, CMC Ltd. 28 Camac Street, Calcutta 700 016, India ; P.K.Das, Dept. of CSE. Jadavpur University, Calcutta 700 032, India. A Document Image Analysis System on Parallel Processors. tr2-3 Yue Lu, Chew Lim Tan. A nearest-neighbor chain based approach to skew estimation in document images. Pattern Recognition Letters 24 (2003)2315–2323, Department of Computer Science, School of Computing National University of Singapore, Kent Ridge, Singapore 117543, 2003, tr2315-2319 Z.Shi, V.Govindaraju, Skew Detection for Complex Document Images Using Fuzzy Run length, Proc. Of the Seventh Int. Conf. on Document Analysis and Recognition, ICDAR’03. tr1-4