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

n bản tổng quát là : đối với form nhập dữ liệu, ta thực hiện phân vùng trên ảnh đã biết trước cấu trúc và ta chỉ cần tách ra các vùng đã được định nghĩa từ trước là sẽ được nhập dữ liệu để sau đó tiến hành nhận dạng trên các vùng này. Chính nhờ việc biết trước một số thông tin mà kết quả phân vùng chính xác hơn rất nhiều cũng như thời gian xử lý giảm đi đáng kể do ta chỉ cần tách ra một số vùng cần thiết. Hình 12: Form mẫu và các vùng nhập dữ liệu được định nghĩa Hình 13: Form sau khi được in ra, điền thông tin và scan vào máy tính Khi tách vùng trên ảnh scan, ta luôn phải đối chiếu với ảnh mẫu để xác định vị trí tương ứng của các vùng trên ảnh scan so với các vùng trên ảnh mẫu. Phân vùng ảnh dựa vào hệ tọa độ tuyệt đối Phân vùng ảnh theo hướng tiếp cận này, ta đặt một hệ trục tọa độ vào ảnh mẫu và tương ứng với nó là một hệ trục tọa độ trên ảnh scan. Sau khi khớp được hai hệ trục tọa độ này cũng như tìm được tỉ lệ chính xác giữa kích thước của hai ảnh, ta sẽ có tương ứng 1:1 giữa một điểm trên ảnh mẫu và một điểm trên ảnh scan. Eq 2: Tọa độ tương ứng giữa 1 điểm trên ảnh scan và 1 điểm trên ảnh gốc trong đó xi,yi là tọa độ của điểm i trong ảnh mẫu, x’i,y’i là tọa độ của điểm tương ứng với nó trong ảnh scan. Trên cơ sở sự tương ứng này, ta tách được được các vùng cần xử lý trên ảnh scan tương ứng với các vùng đã được xác định trước trên ảnh mẫu. Để khớp hai hệ trục tọa độ giữa hai ảnh, ta đưa vào ảnh mẫu một số đối tượng đặc biệt ( như một đường thẳng dày, khung bao quanh …). Khi nhận dạng được các đối tượng này trên ảnh scan, ta có thể khớp được hai hệ trục tọa độ. Dưới đây là hình vẽ minh họa ảnh gốc và ảnh scan, sau khi khớp hai hệ trục tọa độ ta tách được vùng cần nhận dạng. Hình 14: (a) Ảnh gốc; (b) Ảnh scan sau khi tiền xử lý Nhận xét : Ưu điểm : đơn giản, dễ hiểu, dễ cài đặt, tính toán đơn giản Nhược điểm : độ chính xác không cao nhất là trên những ảnh có kích thước lớn Phân vùng ảnh dựa vào hệ tọa độ tương đối Một hướng tiếp cận khác trong việc phân vùng ảnh trên form nhập dữ liệu là dựa trên hệ tọa độ tương đối. Trong phương pháp phân vùng dựa vào hệ tọa độ tuyệt đối, do sự biến dạng của ảnh trong quá trình scan cộng với sai số của quá trình tiền xử lý, vị trí tuyệt đối của các vùng sẽ bị thay đổi, đặc biệt là các vùng xa gốc tọa độ. Để giảm bớt sai số về vị trí, ta sẽ không sử dụng tọa độ tuyệt đối mà sử dụng vị trí tương đối giữa các đối tượng để phân vùng. Theo phương pháp này, Vị trí của vùng sẽ được tính thông qua các đối tượng đã đượ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ượ