Đồ án Tìm hiểu phương pháp phân form tài liệu

nh hoặc các tiêu chuẩn “thông minh” để đo chất lượng ảnh hoặc tính hiệu quả của các kỹ thuật xử lý. Việc xử lý ảnh số yêu cầu ảnh phải được mẫu hóa và lượng tử hóa. Thí dụ một ảnh ma trận 512 dòng gòm khoảng 512 x 512 pixel. Việc lượng tử hóa ảnh là chuyển đổi tín hiệu tương tự sang tín hiệu số (Analog Digital Convert) của một ảnh đã lấy mẫu sang một số hữu hạn các mức xám. 1.2.3 Tăng cường ảnh – khôi phục ảnh Tăng cường ảnh là bước quan trọng, tạo tiền đề cho xử lý ảnh. Nó gồm một loạt các kỹ thuật như: lọc độ tương phản, khử nhiễu, nổi màu, v.v 1.2.4 Nhận dạng ảnh Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tượng mà người ta muốn đặc tả nó. Quá trình nhận dạng thường đi sau quá trình trích chọn các đặc tính chủ yếu của đối tượng. Có hai kiểu một tả đối tượng: - Mô tả tham số (nhận dạng theo tham số). - Mô tả theo cấu trúc (nhận dạng theo cấu trúc). Trên thực tế, người ta đã áp dụng kỹ thuật nhận dạng khá thành công với nhiều đối tượng khác nhau như: nhận dạng ảnh vân tay, nhận dạng chữ (chữ cái, chữ số, chữ có dấu). Ngoài ra, hiện nay một kỹ thuật nhận dạng mới dựa vào kỹ thuật mạng nơron đang được áp dụng và cho kết quả khả quan. 1.3 Thu nhận ảnh 1.3.1 Thiết bị thu nhận ảnh Các thiết bị thu ảnh thông thường gồm máy quay (camera) cộng với bộ chuyển đổi tương tự số AD(Analog to Digital) hoặc máy quét (scanner) chuyên dụng. Thiết bị thu nhận ảnh có thể cho ảnh trắng đen B/W (Black & White) với mật độ từ 400 đến 1600 dpi (dot per inch) hoặc ảnh màu 600 dpi.Khi dùng scanner, một dòng photodiot sẽ quét ngang ảnh (quét theo hàng) và cho ảnh với độ phân giải ngang khá tốt. Đầu ra của scanner là ảnh ma trận số mà ta quen gọi là bản đồ ảnh (ảnh Bitmap), bộ số hóa (digitalizer) sẽ tạo ảnh vectơ có hướng. Trong xử lý ảnh bằng máy tính, ta không thể không nói đến thiết bị monitor (màn hình) để hiện ảnh. Monitor có nhiều loại khác nhau: CGA, EGA, VGA, SVGA. Với ảnh màu, có nhiều cách tổ hợp màu khác nhau. Theo lý thuyết màu do Thomas đưa ra từ năm 1802, mọi màu đều có thể tổ hợp từ 3 màu cơ bản: Red (đỏ), Green (lục) và Blue (lơ). Thiết bị ra ảnh có thể là máy đen trắng, máy in màu hay máy vẽ (ploter). Máy vẽ cũng có nhiều loại: loại dùng bút, loại phun mực. Nhìn chung, các hệ thống thu nhận ảnh thực hiện hai quá trình: Cảm biến: biến đổi năng lượng quang học (ánh sáng) thành năng lượng điện. Tổng hợp năng lượng điện thành ảnh. 1.3.2 Biểu diễn màu Ánh sáng màu là tổ hợp của ánh sáng đơn sắc. Mắt người chỉ có thể cảm nhận được vài chục màu, song lại có thể phân biệt được hàng ngàn màu. Có 3 thuộc tính chủ yếu trong cảm nhận màu: Brighness: sắc màu, còn gọi là độ chói. Hue: sắc lượng, còn gọi là sắc thái màu. Saturation: độ bão hòa. Với nguồn sáng đơn sắc, độ hue tương ứng với bước sóng l. Độ bão hòa thay đổi nhanh nếu ta thêm lượng ánh sáng trắng. Hình 1.3 mô tả mối liên quan giữa những các đại lượng trên và 3 màu chủ yếu R, G và B. Một màu bất kỳ sẽ là một điểm trên vòng tròn. Nếu White và Black là như nhau thì đường tròn là lớn nhất và R là điểm bão hòa. S thay đổi theo bán kính H thay đổi theo góc . W* là sắc màu. Hình 1.3. Hệ tọa độ màu RGB 1.3.3 Hệ tọa độ màu Tổ chức y tế về chuẩn hóa màu CIE (Commision Internationalé d’Eclairage) đưa ra một số các chuẩn để biểu diễn màu. Các hệ này có các chuẩn riêng. Ở đây chỉ đề cập đến chuẩn mầu CIE-RGB (hệ tọa độ dùng 3 màu cơ bản). Như đã nêu trên, một màu là tổ hợp của các màu cơ bản theo một tỉ lệ nào đấy. Người ta dùng hệ tọa độ ba màu R-G-B (tương ứng với hệ tọa độ x-y-z) để biểu diễn màu như sau: Hình 1.4. Hệ tọa độ 3 màu R-G-B Trong cách biểu diễn này ta có công thức: đỏ + lục + lơ = 1. Công thức này gọi là công thức Maxwell. Ta cũng có thể chuyển từ hệ tọa độ 3 màu về hệ tọa độ x-y-z. 1.4 Các kỹ thuật xử lý ảnh cơ bản Trên đây đã nói các khái niệm cơ bản trong xử lý ảnh, chúng ta sẽ tìm hiểu một số kỹ thuật xử lý ảnh sẽ được dùng trong nhận dạng phiếu điều tra. 1.4.1 Nhị phân hóa Nhị phân hóa là thực hiện phép biến đổi ảnh từ ảnh đa cấp xám về ảnh nhị phân (có 2 cấp xám).Phương pháp đơn giản là dùng một hàm cắt với giá trị ngưỡng q. Trong đó u là mức xám của một điểm ảnh. Ngưỡng q có thể được chọn trước hoặc thực hiện chọn tự động bằng cách tính toán các đại lượng thống kê trên lược đồ tần xuất histogram của ảnh, của vùng ảnh. 1.4.2 Khử nhiễu Khử nhiễu được tiến hành bằng cách sử dụng các bộ lọc tuyến tính (lọc trung bình) hoặc phi tuyến (lọc trung vị). Khử nhiễu bằng các bộ lọc tuyến tính phổ biến là các bộ lọc sau: Các bộ lọc trên được kết hợp với ảnh bằng phép nhân chập (phép cuộn) và cho ra ảnh kết quả có độ nhiễu nhỏ hơn ảnh ban đầu. 1.4.3 Làm trơn biên, lấp đầy chỗ trống Trên thực tế, sau khi khử nhiễu, đường biên chữ không được trơn tru như ban đầu mà hình thành các đường cong có răng cưa. Khi đó ta phải tiến hành lấp đầy chỗ trống, xóa đi các điểm giả trên biên chữ. Hai kỹ thuật hay được sử dụng là Unger và Dineen. Kỹ thuật Dineen dùng một mặt nạ n x n di chuyển trên tất cả các vị trí trong ảnh. Một ảnh mới được tạo ra trên đó mỗi phần tử tại tâm cửa sổ được tính lại theo các phần tử lân cận. Nếu tổng các phầntử trong cửa sổ lớn hơn một ngưỡng nào đó thì vị trí tương ứng trong ảnh mới sẽ là 1, ngược lại là 0. Kích thước cửa sổ thường chọn là 3 x 3 hoặc 4 x 4. Kỹ thuật Unger dùng một tập luật để lấp đầy chỗ trống. Giả sử P là điểm đang xét, ta có các điểm lân cận của P như sau: P3 P2 P9 P4 P P8 P5 P6 P7 Điểm P trên ảnh mới là đen khi và chỉ khi thỏa mãn 1 trong 2 điều kiện sau: 1. P là điểm đen 2. Có ít nhất 3 trong 4 láng giềng P2, P4, P6, P8 là đen Để loại bỏ các điểm cô lập sau khi lấp đầy chỗ trống, Unger lại dùng một tập luật khác: 1. Có ít nhất 1 trong 3 láng giềng P2, P3, P4 là đen 2. Có ít nhất 1 trong 3 láng giềng P6, P7, P8 là đen hay 1. Có ít nhất 1 trong 3 láng giềng P4, P5, P6 là đen 2. Có ít nhất 1 trong 3 láng giềng P2, P8, P9 là đen 1.4.4 Thuật toán xác định góc nghiêng và chỉnh độ nghiêng 1.4.4.1 Xác định góc nghiêng dựa vào biến đổi Hough Chúng ta sẽ dùng biến đổi Hough để tìm các đường thẳng trên ảnh. Kĩ thuật tìm đường thẳng theo biến đổi Hough sẽ được ứng dụng vào tìm góc nghiêng. Mỗi đường thẳng trong toạ độ cực được xác định bởi cặp (r, ) với r là khoảng cách từ gốc đến đường thẳng, là góc giữa véc tơ pháp tuyến của đường thẳng và trục Ox như hình vẽ. Giả sử (x,y) là một điểm thuộc đường thẳng thì ta tìm công thức ràng buộc giữa x, y, r và. Ta có: r = (m + y) . sin Mặt khác ta có: tgθ = x/m Û sin / cosθ = x/m Û m.sinθ = x.cosθ Do đó ta có mối liên hệ giữa ( x, y ) và (r, θ ) như sau : r = x.cosθ + y.sinθ Phương trình này được gọi là phương trình đường thẳng Hough. Tư tưởng của nhận dạng đường thẳng Hough là: với mỗi giá trị của các tham số r và , ta tính số tọa độ (x, y) thỏa mãn phương trình đường thẳng Hough và là điểm đen. Nếu số này lớn hơn một ngưỡng thì tập hợp các điểm đó có thể tạo nên một đường thẳng. x y m θ Hình 1.5. Đường thẳng Hough trên tọa độ cực Ưu điểm của thuật toán này là có thể tìm được các đường thẳng không liền nét (các điểm trên đường thẳng rời rạc nhau) với độ chính xác cao. Điều này phù hợp với thực tế rằng, một ảnh khi quét vào có thể bị nhiễu hoặc đứt nét. Với thuật toán này, ta cũng có thể tính ngay được góc nghiêng của đường thẳng. Từ đó dễ dàng chuyển sang bước chỉnh độ nghiêng. Dựa vào biến đổi Hough, hàng loạt các kỹ thuật xác định góc nghiêng được phát triển. Các kỹ thuật này dựa trên sự tìm kiếm những đặc tính khác biệt của văn bản như là hướng của các ký tự, các dòng văn bản thường song song với nhau. Từng điểm đen (x,y) của ảnh được ánh xạ vào trong không gian Hough (ρ, θ), sử dụng biến đổi ρ = x cos(θ) + y sin(θ). Các điểm ảnh thẳng hàng sẽ đem lại các đỉnh trong không gian Hough. Góc nghiêng của phương pháp này phụ thuộc vào góc nghiêng của trục. Độ phức tạp của thuật toán là tuyến tính đối với số lượng các điểm biến đổi và sự thay đổi góc quay. 1.4.4.2 Các thuật toán phát hiện góc nghiêng dựa vào biến đổi hough Hệ thống xử lý ảnh văn bản thường phải giải quyết bài toán phát hiện góc nghiêng như một bước đầu tiên và tất yếu. Dựa vào tính chất mỗi đối tượng ảnh có duy nhất một chu tuyến ngoài và quan niệm con người nhận ra độ nghiêng của văn bản dựa vào cỡ chữ chiếm chủ đạo trong văn bản [3 ]. Việc xác định góc nghiêng văn bản được xác định nhờ phép biến đổi Hough cho những điểm giữa đáy của hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh cho các đối tượng ảnh có kích thước chủ đạo. Để xây dựng được thuật toán xác định góc nghiêng văn bản, trước hết phải dùng kỹ thuật dò biên để xác định chu tuyến cho các đối tượng ảnh. Các hình chữ nhật chứa các đối tượng này được lưu lại cho các qúa trình xử lý tiếp theo. Dựa vào sơ đồ phân bố các kích thước của các đối tượng, xác định các ngưỡng kích thước để phân loại các đối tượng và lựa chọn một số đối tượng có kích thước chủ đạo trong ảnh rồi dùng biến đổi hough để áp dụng cho các điểm đại diện là điểm giữa đáy của hình chữ nhật ngoại tiếp các đối tượng này. Cuối cùng góc nghiêng văn bản sẽ được ước lượng từ mảng tích lũy trong quá trình áp dụng biến đổi hough. Phương pháp xác định góc nghiêng văn bản dựa vào thuật toán sử dụng đường thẳng dày lại mở ra một hướng tiếp cận mới [1 ]. ở phương pháp này chúng ta sẽ tạo ra một đường thẳng song song với mép trên của văn bản và có một độ dày nhất định để tránh đường thẳng bị mất nét. Chúng ta sẽ nhận dạng đường thẳng này và độ nghiêng của nó dựa trên thuật toán Hough. Chúng ta quan niệm đường thẳng dày là tập hợp các đường thẳng mảnh song song và kề cận nhau hợp thành. Thay vì nhận dạng đường thẳng dày, chúng ta sẽ nhận dạng tập hợp các đường thẳng đó. - Tìm tất cả các đường thẳng trên ảnh phiếu có ngưỡng lớn hơn hoặc bằng ngưỡng của đường thẳng dày. - Xác định tập hợp các đường thẳng song song (cùng nghiêng một góc giống nhau) và kề nhau trong các đường thẳng trên. - Trong các tập hợp trên, tìm tập hợp có số lượng đường thẳng là lớn nhất. Đó chính là tập hợp tạo nên đường thẳng dày. 1.4.4.3 Chỉnh độ nghiêng Sau khi tìm được góc nghiêng của văn bản, ta đến bước điều chỉnh lại ảnh. Để xoay ảnh một góc θ, ta dùng biến đổi tọa độ như sau: Trong đó (x’, y’) là tọa độ mới sau khi quay. Thuật toán quay ảnh đơn giản là chuyển một điểm ảnh (x,y) từ ảnh ban đầu thành điểm ảnh mới có toạ độ (x’, y’) x’ = x.cosθ + y.sinθ y’ = y.sinθ - x.cosθ CHƯƠNG 2 - Biểu mẫu động 2.1 Hệ thống xử lý biểu mẫu động 2.1.1 Giới thiệu về hệ thống xử lý biểu mẫu động Trong hầu hết các hệ thống xử lý biểu mẫu đang được sử dụng ngày nay, màu sắc được sử dụng trong các biểu mẫu, như là các dòng chữ in giới thiệu hoặc các khung điền thông tin, mục đích nhằm phân tách chúng đối với phần chữ viết tay. Do đó, các hệ thống này sẽ đòi hỏi máy in màu và máy quét ảnh màu hay đầu đọc màu. Các biểu mẫu và các bản copy đồng màu (đen trắng hay đa cấp xám) của chúng không thể sử dụng được trong trường hợp này. Vì thế chi phí cho các hệ thống này sẽ bị nâng lên cao. Đối ngược lại các biểu mẫu màu, thì các biểu mẫu đồng màu (đen trắng hoặc đa cấp xám) chi phí thấp và thuận lợi cho việc sử dụng, nhưng chúng lại có một số nhược điểm. Chúng ta sẽ gặp khó khăn trong việc phân tách chữ viết tay ra khỏi khung điền trong trường hợp chữ viết tay đè lên khung điền. Trong hầu hết các hệ thống nhận dạng biểu mẫu đang được sử dụng, các biểu mẫu đều phải được đăng ký trước để hệ thống hiểu được các khung điền ở đâu, cái gì được viết trong các khung, xử lý từng khung như thế nào Để giải quyết vấn đề này, chúng ta sử dụng “biểu mẫu động”. Biểu mẫu động là biểu mẫu có các khung điền được hình thành bởi các “cấu trúc chấm nhỏ”. Bằng cách thức này, chúng ta có thể dễ dàng phân tách chữ viết tay ra khỏi khung điền một cách nhanh chóng và dễ dàng bằng các thuật toán xử lý ảnh đơn giản. Chúng ta cũng có thể loại bỏ việc đăng ký biểu mẫu mà hệ thống của chúng ta vẫn biết được các thuộc tính của chữ viết tay, cách xử lý chúng như thế nào trong từng khung điền bởi vì chúng có thể mã hóa thông tin vào trong khung điền. Việc mã hóa này được thực hiện thông qua các cấu trúc điểm nhỏ cấu tạo nên khung điền. Chính vì những lý do này mà chúng tôi gọi hệ thống này là “biểu mẫu động”. 2.1.2 Ưu điểm so với các phương pháp truyền thống (1) Tách các phần tử gối chồng lên nhau. Các hệ thống xử lý biểu mẫu truyền thống sử dụng màu cho khung điền (thường là màu đỏ) để phân tách các khung và chữ viết, các hệ thống này yêu cầu được xử lý trong môi trường có các thiết bị đọc và in màu. Tuy nhiên phương pháp của chúng ta có thể tách các phần tử gối chồng trong môi trường đơn màu bằng một xử lý đơn giản. Chúng ta sẽ mô tả kỹ hơn trong phần tiếp theo. (2) Tính đảm bảo thông tin trong biểu mẫu. Hầu hết các hệ thống xử lý biểu mẫu truyền thống cần thiết phải đăng ký các chi tiết các đầu vào của khung trên biểu mẫu. Điều này giúp ích cho việc xử lý đúng đắn các thông tin trên biểu mẫu. Tuy nhiên trong phương pháp này tất cả các thông tin đều đã được nhúng vào trong các khung, vì thế việc đăng ký trên các biểu mẫu là không cần thiết. (3) Phương pháp nhúng thông tin. Một phương pháp thông dụng để nhúng thông tin là mã vạch, nó có thể in trên giấy hoặc các chất liệu khác. Tuy nhiên điều đó sẽ gặp nhiều bất tiện nếu sử dụng mã vạch để nhúng thông tin vào các biểu mẫu. Mã vạch sẽ phải đặt gần các khung hoặc kết nối vào chúng trước khi chúng ta viết thông tin vào biểu mẫu. Hơn nữa, việc đưa các thông tin mã vạch vào biểu mẫu tốn mất nhiều diện tích và hình dạng biểu mẫu trông không mỹ cảm. Trong khi đó, việc nhúng thông tin trong phương pháp mới thì thông tin được đưa trực tiếp vào các khung, các thông tin gắn liền với khung nên sẽ rất tiết kiệm không gian của biểu mẫu. (4) So sánh các phần mềm ứng dụng trong việc nhập dữ liệu. Ngày nay, thông thường việc đưa dữ liệu vào máy tính thực hiện được nhờ sự giúp đỡ của bàn phím và con chuột. Tuy nhiên, sẽ là một sự khó khăn cho những người không có kiến thức về việc sử dụng PC (personal computer). Phương pháp chúng ta đưa ra chỉ sử dụng các định dạng trên giấy và bút, phương pháp này không cần thêm máy tính hay một thiết bị điện tử nào để nhập thông tin vào. Hơn nữa, phương pháp này thường được sử dụng trong các văn bản quan trọng (như các hợp đồng, các ký kết thỏa thuận ) bao gồm cả chứ ký và các thông tin các nhân. Vì vậy, các tài liệu theo phương pháp này có thể được chứng nhận như một căn cứ pháp lý và một chứng chỉ khi cần thiết. 2.1.3 Thiết kế hệ thống 2.1.3.1 Kiến trúc hệ thống Kiến trúc của hệ thống được thể hiện như trong hình 2.1. Nó bao gồm: hệ thống chuẩn bị biểu mẫu tạo ra các biểu mẫu động; hệ thống xử lý biểu mẫu, nó có nhiệm vụ trích lọc chữ viết và các thông tin được nhúng trong biểu mẫu động; và ứng dụng phần mềm/phần cứng hoạt động theo thứ tự đưa thông tin vào biểu mẫu. Active Form System Form Preparation System Form Processing System Application Software/ Hardware Hình 2.1: Hệ thống xử lý biểu mẫu động 2.1.3.2 Hệ thống chuẩn bị biểu mẫu Hệ thống này bao gồm một PC với một trình soạn thảo biểu mẫu động (chuẩn bị cho biểu mẫu động) và một máy in. Trình soạn thảo biểu mẫu động Trình soạn thảo biểu mẫu động là một trình có khả năng sắp xếp các khung đầu vào cùng với tiêu đề của chúng và có khả năng đưa thông tin vào giống như các trình soạn thảo biểu mẫu thông thường. Các thông tin đưa vào có thể được chọn theo danh sách dựa trên menu. Nhúng thông tin Để nhúng thông tin chúng ta sử dụng các điểm có hình dạng đường tròn và các hình chữ nhật (giống như hình bao). Đường kính của điểm chấm tròn là 0.1mm và chiều dài đầy đủ của hình chữ nhật là 0.25mm và chúng đại diện cho các ký tự 0 và 1. Thông tin được nhúng vào trong khung bao gồm: Thuộc tính của mục sẽ điền vào. Kiểu ký tự sẽ được sử dụng trong các khung (ví dụ: bảng chữ cái tiếng Anh, con số, ký tự đặc biệt ..) Phương hướng, chỉ dẫn. Tiêu đề. Dữ liệu nhúng vào nằm ở phần trên của khung (hình 2.3). Attribute Character type Direction Title Terminal Hình 2.2: Data set Hình 2.3: Vùng mã hóa thông tin 2.1.3.3 Hệ thống xử lý biểu mẫu Hệ thống này bao gồm một máy quét và một máy tính với phần mềm xử lý biểu mẫu. Giao diện của ứng dụng và ảnh của biểu mẫu được thể hiện trong hình 2.4, và luồng xử lý được thể hiện như trong hình 2.5. Các thành phần của hệ thống được mô tả chi tiết như sau: Phần đọc biểu mẫu Biểu mẫu được đọc bằng một máy quét ảnh. Sau khi quét ảnh chúng ta thu được 1 ảnh bitmap. Phân tách các ảnh Chúng ta sẽ thu được ảnh của chữ viết tay bằng phương pháp gán nhãn để loại trừ các điểm chấm nhỏ. Mặc dù có rất nhiều phương pháp loại trừ các điểm chấm, song dựa trên tốc độ xử lý ảnh và hiệu quả, chúng ta chọn phương pháp gán nhãn cho tình huống này. Bằng cách thực hiện phép trừ ảnh, trừ ảnh ban đầu với ảnh chữ chúng ta sẽ thu được ảnh khung. Hình 2.4: Một minh họa về biểu mẫu động Phân đoạn các ký tự Ảnh chữ viết tay được phân đoạn theo vị trí của khung và những ký tự này được giới hạn trong một khung. Giải mã Giải mã được áp dụng trên khung điền thông tin. Tại đây, chúng ta phải chú ý đến tình huống gối chồng của chữ viết tay tên khung và có thể làm hư hại đến một vài vùng trong kết cấu điểm. Do đó, vùng dữ liệu nhúng vào được sao chép nhiều lần, sau đó chúng được chiết xuất và giải mã theo phương pháp bình chọn đa số. Điều khiển nhận dạng Chức năng này gửi thông tin từ (3) và (4) tới modul nhận dạng chữ viết tay (6) và cũng gửi kết quả nhận dạng tới giao diện hiệu chỉnh (7). (6) Máy nhận dạng ký tự Các mẫu ký tự viết tay sẽ được đưa vào để nhận dạng. Để tăng tốc độ nhận dạng, hệ thống sẽ sử dụng thông tin của kiểu ký tự và thuộc tính kèm theo. (7) Giao diện hiệu chỉnh Các ký tự nhận dạng sẽ được hiện thị lên trên chữ viết tay trong khung. (8) Tạo nhóm sheet Dữ liệu được tạo ra bởi tiến trình từ (1) tới (7) được gói lại trong tập tin định dạng CSV. Hình 2.5: Luồng xử lý 2.1.3.4 Ứng dụng Một ứng dụng đọc các sheet tạo bởi hệ thống xử lý biểu mẫu và họat động theo chúng. Như một ví dụ cụ thể cho ứng dụng, chúng ta tạo ra một khóa học đầu vào cho sinh viên tại trường đại học. 2.2 Các thuật toán xử lý ảnh áp dụng trong xử lý biểu mẫu động 2.2.1 Khái niệm biểu mẫu động. Biểu mẫu động là biểu mẫu mà các khung điền trong nó được tạo ra bởi cấu trúc các chấm nhỏ. Hình dạng của các chấm nhỏ như sau : Hình 2.6: Hình ảnh của chấm nhỏ Một cấu trúc có thể của khung điền thông tin như sau: Hình 2.7: Một cấu trúc của khung Chúng ta thấy rằng, với hai mẫu hình dạng khác nhau của chấm nhỏ là chấm tròn và chấm dẹt, chúng ta có thể có nhiều cách sắp xếp hai loại chấm này. Nếu chúng ta quan niệm rằng với mỗi cách sắp xếp sẽ tương ứng với một ý nghĩa cụ thể nào đó thì chúng ta có thể mã hoá một số thông tin vào trong các khung. Một số kiểu cấu trúc các điểm chấm nhỏ có thể như sau: Hay Hình 2.8: Một số cấu trúc chấm nhỏ Mỗi loại cấu trúc này sẽ tương ứng với một loại dữ liệu riêng. Trong quá trình nhận dạng, sau khi phân tích cấu trúc các điểm nhỏ cấu tạo khung, ta sẽ biết dữ liệu trong khung là loại dữ liệu nào (chữ, số...), cách xử lý chúng ra sao, và cách lưu trữ chúng ở đâu. Như vậy là thứ tự trước sau của các khung điền thông tin trong biểu mẫu bây giờ sẽ trở nên không còn quan trọng nữa. 2.2.2 Lược đồ xử lý biểu mẫu động. Hình 2.9: Một lược đồ xử lý biểu mẫu động Hình 2.4 là ví dụ về một mẫu biểu mẫu động được chúng tôi thí nghiệm. Các khung điền thông tin được cấu tạo bởi các cấu trúc điểm nhỏ khác nhau. Thông tin dùng để điều khiển quá trình nhận dạng như là các thuộc tính của chữ viết tay (ví dụ như tên, tuổi, địa chỉ) và các nhóm ký tự được sử dụng trong chúng (ví dụ như các chữ số, các chữ cái alphabet,, các ký tự đặc biệt) được mã hoá tại đỉnh của các khung điền theo các cấu trúc chấm nhỏ khác nhau. Cách thức mã hoá thông tin được sử dụng ở đây là hết sức đơn giản và chúng tôi chỉ sử dụng hai dạng chấm nhỏ để mã hoá thông tin theo mã nhị phân. Một hệ thống xử lý biểu mẫu động sẽ tách lọc các nội dung đầu vào, các thông tin đã được mã hoá từ biểu mẫu động và đầu ra sẽ là một văn bản theo yêu cầu. 2.2.3 Các phương pháp tách chữ viết tay ra khỏi khung điền 2.2.3.1 Tìm hiểu các thuật toán tách cơ bản 2.2.3.1.1 Phương pháp nhân dạng cơ bản Giả sử rằng các chữ được viết trên khung được tạo bằng kết cấu điểm như trong hình 2.10(a). Phương pháp Erosion (ăn mòn) được sử dụng và thu được kết quả trong hình 2.10(b). Nếu thấy cần thiết phương pháp này có thể lặp lại nhiều lần. Nếu như bề dày các điểm chấm nhỏ hơn bề dày của chữ viết tay, thì các điểm chấm sẽ biến mất trước khi chữ viết tay có thể biến mất. Phương pháp Dilation (giãn nở) được làm cùng số lần với phương pháp Erosion. Do đó các chữ viết tay được khôi phục thường có độ dày như độ dày ban đầu trước khi áp dụng phép Erosion. Có thể dùng nhiều phương pháp khác nhau để phân tách các vùng gối chồng. Một cách là dựa trên độ đo của vùng các điểm chấm và phần viết tay bằng cách gán nhãn và sử dụng sự không tương ứng giữa 2 vùng để phân tách các vùng gối chồng. Bằng cách kết hợp các phương pháp này và bộ nhận dạng chữ viết tay thì việc tạo ra một hệ thống xử lý biểu mẫu có khả năng phân tách các vùng gối chồng của chữ viết tay và các khung một cách hiệu quả thậm chí cả trong môi trường đơn sắc là hoàn toàn khả thi. Hình 2.10: Phân tách chữ viết tay và các khung. 2.2.3.1.2 Thuật toán gán nhãn ( Labeling) Đây là phương pháp tính số điểm đen trong một vùng liên thông của các điểm đen, sau đó các điểm ảnh trong cùng một vùng liên thông sẽ được gán một nhãn giống nhau, đó là tổng số điểm đen vừa tính được. Có nhiều phương pháp để thực hiện phương pháp gán nhãn này. Ở đây, chúng tôi lựa chọn thuật toán đệ quy để thực hiện phép gán nhãn. Thuật toán đệ quy giúp tăng tốc độ tính toán đối với các mẫu biểu mẫu động có nhiều khung điền. Trong thuật toán này, nếu mỗi điểm đen được tìm thấy, nó sẽ tính các điểm đen hàng xóm liên kết với nó. Giá trị trả lại của thuật toán đó là số lượng điểm đen của các vệt đen. 2.2.3.1.3 Thuật toán hình thái học (Morphology) Có hai thuật toán hình thái học để xử lý: phép co (contraction) và phép dãn (expansion) Có hai thuật toán contraction khác nhau: Nếu một pixel trắng được tìm thấy thì tất cả 8 hàng xóm hoặc 4 hàng xóm của nó cũng sẽ bị chuyển thành trắng. Nếu một điểm đen được tìm thấy, thì chúng ta sẽ kiểm tra 8 hàng xóm hoặc 4 hàng xóm của nó. Nếu có ít nhất một hàng xóm của nó là điểm trắng thì nó sẽ chuyển thành trắng. Có hai thuật toán expansion khác nhau: Nếu một điểm đen được tìm thấy, thì tất cả 8 hàng xóm hoặc 4 hàng xóm của nó cũng sẽ chuyển thành đen. Nếu một điểm trắng được tìm thấy, thì chúng ta sẽ kiểm tra 8 hàng xóm hoặc 4 hàng xóm của nó. Nếu có ít nhất một hàng xóm của nó là đen thì nó sẽ chuyển thành đen. 2.2.3.2 Tách chữ viết tay ra khỏi khung điền Theo các thuật toán cơ bản được trình bày ở phần trước, chúng ta có các phương pháp tách khác nhau: a) Phân tách bằng thuật toán gán nhãn: Một thuật toán đệ quy được sử dụng để tính các thành phần liên thông đen trong biểu mẫu. Từ đó số lượng điểm đen trong mỗi thành phần liên thông được xác định. Để thu được chữ viết tay mà không còn khung, ta xét các thành phần liên thông : Nếu số điểm đen trong thành phần liên thông bé hơn một ngưỡng cho trước thì toàn bộ thành phần liên thông sẽ bị xoá. Ta biết rằng số lượng điểm đen trong thành phần liên thông của các chấm nhỏ là nhỏ hơn rất nhiều so với số lượng các điểm đen trong thành phần liên thông của chữ viết tay. Do đó qua phép toán này, chúng ta sẽ thu được các chữ viết tay không còn khung điền. Ngược lại, để thu được khung điền thông tin mà đã loại bỏ được chữ viết tay, chúng ta cũng thực hiện tương tự, chỉ khác ở chỗ thành phần liên thông nào có số lượng điểm đen lớn hơn ngưỡng cho trước thì sẽ bị xoá hoàn toàn. b) Phân tách bằng các thuật toán hình thái học: Morphology được sử dụng ở đây gồm có phép co và phép dãn Phép co : Nếu một điểm đen được tìm thấy, chúng ta sẽ xem xét các 4-hàng xóm hoặc 8-hàng xóm của nó và nó sẽ bị biến đổi thành điểm trắng nếu có ít nhất một hàng xóm của nó là điểm trắng. Phép dãn : Nếu một điểm đen được tìm thấy thì các 4-hàng xóm hoặc 8-hàng xóm của nó sẽ được chuyển thành các điểm đen. Đầu tiên, trang biểu mẫu sẽ được thực hiện nhiều lần phép co cho đến khi các khung điền thông tin bị biến mất. Lúc này trên ảnh chỉ cón lại các chữ viết tay, chúng ta sẽ thực hiện phép dãn để phục hồi lại các chữ viết tay. Phép co thực hiện bao nhiêu lần thì phép dãn cũng sẽ được thực hiện bấy nhiêu lần.s Để thu được chữ viết tay thông qua các biến đổi này, thì độ dày của các chữ viết tay phải dày hơn độ dày của các chấm nhỏ. Bởi vì nếu không có điều kiện này thì chữ viết tay cũng sẽ bị biến mất cùng khung điền thông tin sau một số bước thực hiện phép co. Ngoài ra, sau khi thực hiện phép co, thì các chữ viết tay sẽ bị biến dạng bào mòn, đứt nét. Để khôi phục lại chúng, chúng ta sẽ sử dụng phép dãn. Tuy nhiên thường là các chữ viết tay thu được sau khi thực hiện phép dãn sẽ dày hơn kích thước thật của nó. c) Phân tách sử dụng kết hợp phép gán nhãn và hình thái học: Chúng ta có một n