Luận văn Tìm hiểu bài toán nhận dạng kí tự viết tay và phát triển ứng dụng

tập trung vào nghiên cứu các đối tượng mà có thể coi như tập hợp các đối tượng sơ cấp liên hệ với nhau bởi một số liên kết chuẩn. Gần đây, một số nhà toán học có cố gắng xây dựng cấu trúc đại số cho đối tượng và thuật toán nhận dạng, những công trình này cho thấy triển vọng của một lý thuyết đại số về nhận dạng đang hình thành ngày càng rõ nét . Do nhu cầu cấp bách phải giải quyết các vấn đề thực tiễn hoạt động sản xuất, nghiên cứu khoa học kỹ thuật hiện đại đặt ra, cùng với các kỹ thuật tin học mới phát triển (đặc biệt là máy tính điện tử ), nhiều chuyên gia thuộc các lĩnh vực hoạt động khác nhau cũng đã đề xuất và sử dụng các mô hình, thuật toán nhận dạng trên cơ sở thực nghiệm, theo cách tiếp cận heuristic. Song song với việc xây dựng cơ sở lý thuyết nhận dạng, các hoạt động nghiên cứu ứng dụng lý thuyết nhận dạng cũng tiến hành mạnh mẽ và rộng khắp trên nhiều lĩnh vực khác nhau ở nhiều nước trên thế giới. II. Một số khái niệm về nhận dạng: 1.Nhận dạng: Một biểu diễn là giá đỡ (cái mang) thông tin, thường biểu diễn dưới dạng sau: Mỗi xi biểu diễn kết quả của một phép đo. Tập hợp các biểu diễn xác định X được gọi là không gian biểu diễn. Ví dụ không gian vectơ. Giải thích một biểu diễn nghĩa là cho một kết quả chẳng hạn một cái tên. Giả sử: ta có tập hợp các tên là: Không gian giải thích là một tập thoả các luật, thao tác nào đấy. Một định danh là một ánh xạ của không gian biểu diễn vào không gian giải thích. Mục đích nhận dạng là thực hiện ánh xạ này và tìm thuật toán để thực hiện trên toàn X. Một thuật toán như vậy gọi là toán tử nhận dạng. 2. Tập mẫu nhận dạng: Dữ liệu cho bài toán nhận dạng thường được biểu diễn qua tập mẫu học T với T={(xq, w)} là tập các cặp (dữ liệu - tên). 3. Độ đồng dạng và dị dạng: Là hai chỉ số thường dùng để xây dựng trên quan hệ gần thứ tự trên các cặp đặc biệt khoảng cách giữa hai đối tượng là một chỉ số dị dạng thoả mãn 3 tiên đề: - r(x, y)³ 0 , r(x, x)=0 - r(x, y)= r(y, x) - r(x, z)£ r(x, y)+ r(y, z) 4. Khoảng cách đối tượng: Các hàm đặc trưng quan sát có thể dẫn đến một quan hệ gần thứ tự giữa 1 đối tượng X và các khái niệm Ai, nghĩa là với mọi i, j có thể thiết lập một quan hệ :  (X, Ai) £ (X, Aj) Quan hệ này thường được thiết lập nhờ một khoảng cách đối tượng, ký hiệu: D(X, A). Nếu muốn phân lớp hoặc định danh X có thể dùng thông tin này. Giả sử Ci là lớp phân hoạch tương ứng với khái niệm đại diện Ai ; X được gán vào Ci nếu D(X, Ai) là nhỏ nhất. III. Một số thuật toán phân lớp: Có nhiều giải pháp phân lớp, trong thời gian qua em đã tìm hiểu và thử nghiệm một số giải pháp sau: 1. Xếp lớp khoảng cách cực tiểu: Giả thiết là mỗi lớp mẫu được biểu diễn bằng một vectơ đơn (hoặc trung bình). Trong đó Nj là số vectơ mẫu từ lớp wj, M là số lớp cần phân biệt và tổng được xác định từ các vectơ này, cách xác định lớp của một vectơ mẫu x chưa biết là chỉ định nó cho lớp đơn điệu gần nhất. Dùng khoảng cách Euclid để xác định độ gần sẽ giảm được tính toán. Trong đó || a ||=(aTa )1/2 là dạng Euclid. Sau đó ta chỉ định x cho lớp wj nếu Dj(x) là khoảng cách ngắn nhất. Đó là khoảng cách ngắn nhất dùng trong biểu diễn. Ta dễ dàng nhìn thấy nó tương đương với việc đánh giá bằng hàm số Và chỉ định x cho lớp wj, nếu dj(x) cho giá trị số lớn nhất. 2. Thuật toán hàm thế: Phương pháp nhận dạng theo hàm thế được ứng dụng nhiều trong thực tiễn. Việc sử dụng hàm thế được được xuất phát từ nghĩa thế điện trong trường điện từ: Trong không gian có điện tích q tại A thì xung quanh nó có điện trường theo mọi phía. Tại điểm M của không gian ta có thế gây ra bởi q là: a : hằng số q: độ lớn điện tích q r: khoảng cách từ M tới q Các dạng hàm thế thường dùng trong thuật toán nhận dạng: Ở đây µ, C1, C2 là các hằng số cho trước. rµ(S, S’) là khoảng cách S và S’ (µ=0, 1, 2..) Cách tính thế đối với mỗi lớp: mj: số mẫu của Kj St: mẫu thuộc Kj Ta có luật quyết định: Chú ý : Việc tính thế đối với mỗi lớp, có thể bổ sung trọng số mẫu g(St) : Nhận xét: Nếu chọn r là hàm khoảng cách Euclid thì giải thuật hàm thế này gần giống với cách xếp lớp theo khoảng cách cực tiểu. 3. Phương pháp LDA (Linear Discriminant Analysis): Phương pháp LDA cho trường hợp phân biệt 2 lớp, LDA sẽ tìm một phương chiếu mà phân biệt tốt nhất các mẫu thuộc hai lớp khác nhau trong tập mẫu. Giả sử ta có một tập gồm n mẫu học X bao gồm các vectơ cột d chiều: Trong đó n1 mẫu thuộc về lớp C1 và nằm trong tập con X1, n2 mẫu thuộc về lớp C2 và nằm trong tập con X2. Giả sử ta có một vectơ d chiều w, tích vô hướng y=wTx biểu diễn hình chiếu của vectơ x lên phương w. Ta sẽ tìm một phương chiếu w nhằm tối ưu hoá độ phân biệt giữa các mẫu thuộc 2 lớp C1 và C2. Điều này tương đương với việc giảm số chiều của vectơ đặc trưng xuống còn 1 chiều. Ta gọi mi, i=1, 2 là trị trung bình của các mẫu tương ứng với 2 lớp C1 và C2. Và tương ứng là trung bình của các mẫu được chiếu lên phương w: Trong đó y là hình chiếu của x lên w. Yi là tập các hình chiếu của các x Ỵ Xi lên w. Ta có thể xem là một độ đo cho tính phân biệt giữa hai tập Y1 và Y2 . Tuy nhiên để có được sự phân biệt tốt giữa hai tập khi chiếu lên phương w, ta cần có độ sai khác giữa hai trị trung bình này khá lớn hơn so với độ lệch chuẩn nội tại của mỗi tập ( có thể xem như độ rộng của đám mây các mẫu). Thay vì sử dụng phương sai của mỗi tập ta sẽ sử dụng một độ đo khác, gọi là độ rải (scatter) cho các hình chiếu của các mẫu thuộc lớp Ci như sau: Phương pháp LDA sẽ tìm giá trị w để cực đại hoá hàm tiêu chuẩn sau đây: Để thấy J(w) là một hàm theo w ta định nghĩa các ma trận SB và Sw như sau: SW được gọi là ma trận rải nội lớp (within-class scatter matrix) SB được gọi là ma trận rải liên hợp (between-class scatter matrix) Ta có: = = = wTSWw Nên Tương tự ta cũng có: = wTSBw. Do đó: J(w) = . Để xác định w sao cho J(w) cực đại ta cho đạo hàm riêng J(w) theo w bằng 0 kết quả ta sẽ được: SB w = lSW w Với l là trị riêng, giải bài toán tìm trị riêng ta sẽ có: Đây là kết quả tìm được của phương pháp LDA đối với trường hợp chỉ có 2 lớp. Sau khi đã tìm được w, mỗi vectơ x cần nhận dạng sẽ được xử lý như sau: lấy x trừ đi trung bình của mẫu học rồi chiếu lên phương w ta được một giá trị vô hướng, tính khoảng cách từ giá trị vô hướng này trên của mỗi lớp này chia cho độ lệch chuẩn ta được một độ đo khoảng cách từ x đến các cụm ứng với mỗi lớp. i=1..2 x sẽ được gán vào lớp ứng với cụm gần nhất. Để phân biệt được n lớp ta xây dựng n bộ phân loại 2 lớp theo phương pháp nêu trên. Mỗi bộ phân loại sẽ phân biệt một lớp với n-1 lớp còn lại. Nếu một vectơ đầu vào được xếp vào cả hai lớp thì ta sẽ sử dụng khoảng cách di nêu trên để quyết định nó thuộc vào lớp nào. Nếu một vectơ không được xếp vào lớp nào thì coi như không nhận dạng được. Phần tiếp theo xin trình bày cách phân lớp dựa trên mô hình mạng nơron lan truyền ngược, em dành một chương riêng để giới thiệu về mô hình này. CHƯƠNG II PHÂN LỚP DỰA TRÊN MẠNG NƠRON LAN TRUYỀN NGƯỢC Sơ lược về mạng nơron MLP (Multi-Layer Perception ) với thuật toán lan truyền ngược: I. Giới thiệu: Xét về mặt cấu trúc, MLP có cấu trúc phân lớp. Các cung được nối từ một nút ở lớp này đến các nút ở lớp kế tiếp. Hai nút trong cùng một lớp thì không kết nối với nhau. Mỗi nút trong một lớp nhận giá trị từ các nút ở lớp liền trước, tổng hợp lại theo trọng số của cung kết nối và chuyển giá trị kết xuất của nó cho các nút ở lớp liền sau. Lớp đầu tiên nhận giá trị từ bên ngoài vào và được gọi là lớp nhập (input). Các nút trong lớp nhập được gọi là nút nhập. Lớp cuối cùng sẽ xuất ra kết quả của mạng và được gọi là lớp xuất (output). Các nút trong lớp xuất được gọi là nút xuất. Các lớp còn lại được gọi là lớp ẩn và các nút tương ứng được gọi là nút ẩn. Hình minh hoạ mô hình mạng nơron 4 lớp:1 lớp nhập, 2lớp ẩn và một lớp xuất . Quá trình nhận dạng là quá trình ánh xạ một mẫu x từ không gian các đặc trưng vào không gian các lớp. Cũng như vậy, MLP thực chất là một hàm ánh xạ một vectơ đầu vào x thành một vectơ đầu ra z. Hàm này có đặc tính sau: 1. Nó là hàm phi tuyến (nonlinear) . 2. Nó có tính ổn định (stable). Nghĩa là nếu một giá trị x0 được ánh xạ thành một giá trị z0 thì một giá trị x1 “gần” với x0 sẽ được ánh xạ thành một giá trị y1 gần với y0. Hay ta có thể nói, sai số nhỏ ánh xạ thành sai số nhỏ. Mạng nơron cũng có thể ánh xạ một giá trị x2 xa x0 thành một giá trị y2 gần với y0 (ánh xạ nhiều một). Thực tế mạng nơron là một bộ máy nội suy và ngoại suy phi tuyến. Một mạng chỉ với một lớp ẩn là đã có thể xấp xỉ bất cứ một hàm phi tuyến nào thông qua một số mẫu trong tập mẫu. Để đạt được điều này, ta cần luyện mạng bằng cách thay đổi các trọng số để ánh xạ từ các giá trị trong tập mẫu đến các giá trị đích mong muốn. Quá trình luyện mạng này cần có tập các vectơ mẫu đầu vào và đầu ra mong muốn tương ứng. Do đó, quá trình học này là quá trình học có giám sát. II. Hoạt động: Mạng nơron MLP chỉ có thể ở một trong hai trạng thái: trạng thái ánh xạ và trạng thái học. Ở trạng thái ánh xạ, thông tin sẽ được lan truyền tiến từ các nút nhập đến các nút xuất và một mẫu x sẽ được ánh xạ thành một kết quả z. Ở trạng thái học, các trọng số của kết nối sẽ được điều chỉnh theo một thuật toán học để mạng có thể xấp xỉ được một hàm mong muốn nào đó. Thuật toán lan truyền ngược là một thuật toán hiệu quả cho quá trình học của MLP. Tiếp theo đây em xin trình bày chi tiết hơn về hai trạng thái này của mạng. 1. Trạng thái ánh xạ: Như đã nói, ở trạng thái ánh xạ, mỗi vectơ đầu vào x sẽ được ánh xạ thành một vectơ kết quả z. Quá trình này được thực hiện như sau: Đầu tiên vectơ mẫu x sẽ được đưa vào lớp nhập. Mỗi nơron trong lớp nhập sẽ mang giá trị của một thành phần của x. Các nút nhập sẽ không tính toán gì cả mà gửi trực tiếp giá trị của nó đến các nơron ở lớp tiếp theo. Tại mỗi nơron của các lớp tiếp theo, một thao tác giống nhau sẽ được thực hiện. Đầu tiên nó sẽ tính tổng trọng hoá của tất cả các giá trị được gửi tới. Sau đó một hàm truyền sẽ được áp dụng trên tổng trọng hoá này để cho giá trị xuất của nút này. Hàm truyền có tác dụng nén giá trị của tổng trọng hoá vào một miền giới hạn nào đó. Giá trị này được truyền cho các nơron ở lớp kế tiếp. Cứ thế thông tin được lan truyền cho đến lớp xuất của mạng. Để đơn giản ta khảo sát mạng gồm 3 lớp: 1 lớp vào, 1 lớp ẩn và 1 lớp xuất. Thực tế cũng chỉ cần mạng 3 lớp là đủ để xấp xỉ các loại hàm. Đối với nút ẩn ta có: Tổng trọng gửi tới nút j là: Kết xuất của mạng có J nút ẩn là: Trong đó I là số nút nhập xi, aij là các trọng từ input i đến nút ẩn j và a0j là trọng ngưỡng của nút ẩn j, g(x) là hàm truyền. Đối với mạng K nút xuất ta có: Tổng trọng gửi tới nút xuất k là: Kết xuất của mạng: Trong đó J là số nút ẩn với các kết xuất yj, bjk là các trọng trên các cung liên kết từ nút ẩn j đến nút xuất thứ k, còn b0k là trọng ngưỡng của nút xuất thứ k, g(vk) là hàm truyền theo k. Ta có sơ đồ thể hiện các thao tác được thực hiện tại mỗi nơron. Một số hàm truyền thường được sử dụng là: Hàm sigmoid (hay hàm logistic) được xác định bởi: Hình vẽ đồ thị hàm logistic (a=1). Miền giá trị của hàm là(0, 1). - Hàm tanh (tan- hyperbol) Đồ thị hàm tanh. Miền giá trị của hàm là (-1, 1). Hàm này có miền giá trị tương ứng là (0, 1) và (-1, 1). Việc sử dụng hàm logistic (a=1) hay hàm tanh thực ra là tương đương với nhau vì chúng liên hệ tuyến tính với nhau. Việc sử dụng các hàm truyền khác nhau có liên hệ với các khoảng giá trị khác nhau của trọng số. (Thực tế cho thấy, hàm tanh thường cho tốc độ hội tụ nhanh hơn trong quá trình học ). Các hàm truyền có thể được áp dụng vào các nút xuất hoặc không tuỳ vào mục đích ánh xạ của mạng. Nếu ta cần có một số giới hạn nhất định đối với đầu ra, ta sẽ áp dụng một hàm truyền thích hợp cho các nút xuất. Khi mạng nơron được ứng dụng cho nhận dạng thì quá trình nhận dạng chính là quá trình ánh xạ của mạng nơron. 2. Trạng thái học: Xét mạng MLP có một lớp ẩn với thuật toán lan truyền ngược. Thuật toán lan truyền ngược là thuật toán hữu hiệu cho quá trình học của MLP. Thuật toán này sẽ cập nhật trọng số dựa trên một hàm lỗi E giữa kết xuất của mạng với giá trị đích. Mục đích của việc học có giám sát bằng MLP là cực tiểu hoá hàm lỗi này. Kỹ thuật cơ bản để cực tiểu hoá hàm lỗi là phương pháp giảm gradient. Mặc dù phương pháp này có thể dẫn đến một cực tiểu cục bộ, nhưng nó được áp dụng rộng rãi vì tính đơn giản của nó. Thực tế cũng cho thấy trong hầu hết trường hợp phương pháp giảm gradient đều cho kết quả chấp nhận được. Quá trình học của mạng MLP theo thuật toán lan truyền ngược sẽ lặp đi lặp lại các thao tác sau: Lan truyền tiến : tính kết xuất y của mạng với một mẫu x. Lan truyền ngược : tính sai số giữa kết xuất y và giá trị đích t và lan truyền ngược sai số này lại để cập nhật trọng số cho mạng. Quá trình học sẽ dừng khi mạng đã đạt được một độ lỗi nhỏ nhất định. Phương pháp giảm gradient: Phương pháp giảm gradient gồm các bước chính sau: Chọn ngẫu nhiên một điểm x0 trong không gian trọng số. Tính độ dốc của hàm lỗi tại x0. Di chuyển điểm x0 theo hướng dốc nhất của hàm lỗi. Quá trình tính độ dốc và di chuyển điểm x0 được lặp đi lặp lại cho đến khi x0 tiến đến giá trị làm cho hàm lỗi cực tiểu (có thể là hàm lỗi cực tiểu địa phương). Cập nhật trọng số theo phương pháp giảm gradient: Phương pháp cập nhật trong số theo hướng giảm gradient sẽ dựa trên đạo hàm riêng phần của hàm lỗi E đối với trọng số đang xét theo công thức sau: trong đó: t là chỉ số của lần cập nhật trọng số hiện tại. e được gọi là hệ số học (learning rate). w là một trọng số bất kì trong mạng: aij hoặc bij Công thức trên có thể diễn dịch như sau: cập nhật lại trọng số theo hướng ngược hướng của gradient với độ dài vectơ dịch chuyển phụ thuộc vào e và độ lớn của vectơ đạo hàm. Nếu trọng số được cập nhật theo hướng ngược với gradient một độ dịch chuyển vừa phải, thì giá trị của hàm lỗi sẽ giảm đi so với trước khi cập nhật. Giá trị của e có ảnh hưởng lớn đến tốc độ hội tụ của thuật toán. Nếu e lớn thì độ dịch chuyển lớn, kết xuất của mạng có thể dao động rất thất thường (vì có thể nhảy qua điểm cực tiểu) và thuật toán khó hội tụ. Nếu e nhỏ, ta phải cần rất nhiều bước lặp để đi đến được vị trí cực tiểu của hàm lỗi. c. Quy tắc tính đạo hàm lỗi: Sai số trung bình bình phương thường được sử dụng để đo lường sự trùng khớp giữa ánh xạ ( ký hiệu NN) cần xây dựng với hàm đích cho trước (qua tập mẫu). Cho tập mẫu: W={(Xk, Zk) =(xk1, …,xkM;zk1,…,zkN ); xki, zkj Ỵ R ; i= 1,…,M; j=1,…,N; k=1,…,K}, gọi Tk= NN(Xk)=(tk1,…,tkN) thì sai số trung bình bình phương sẽ là: Đạo hàm hàm lỗi có thể được tính dựa vào quy tắc chuỗi như sau: Ta xét từng trường hợp cụ thể: Trọng số nút xuất: Ta có chuỗi tính đạo hàm hàm lỗi theo trọng số giữa lớp ẩn và lớp xuất: Một nút xuất không ảnh hưởng gì đến sai số của các nút xuất khác trong lớp xuất. Để đơn giản trong công thức ta bỏ qua chỉ số của các nút xuất, nếu nút xuất đang xét có giá trị thực là z và giá trị đúng của nút đó là t, thì sai số bình phương là: Từ đó ta có: Mặt khác độ dốc hàm logistic được tính như sau: Tính số hạng thứ 3, ¶v/¶b trong công thức ¶E/¶b Ta có: Xét với b0 ta có: ¶v/¶b0 =1 Với trọng số bj, ta có: ¶v/¶bj =yj Đặt: Ta có: p=(z-t)z(1-z) Như vậy: Xét trọng số nút ẩn: Ta có đạo hàm của hàm lỗi đối với các trọng số của một nút ẩn: Các nút ẩn tự chúng không tạo lỗi nhưng chúng góp phần tác động vào lỗi của các nút xuất. Những tác động này cũng xác định theo luật chuỗi: (trong công thức này chỉ số j đã được bỏ đi vì chỉ có một nút ẩn tham gia) Công thức trên cho thấy ảnh hưởng của nút ẩn vào hàm E là một tổng theo tất cả các nút xuất (k=1…K) của tích ba số hạng. Hai số hạng đầu trong tích đó có ý nghĩa tương tự như phần trên. Ở trên ta đặt tích này là p. Lượng p này lan truyền ngược từ nút xuất đến nút ẩn. Nếu ta cho p một chỉ số cho biết nó thuộc về nút xuất nào, ta có thể viết phương trình trên lại như sau: Xét số hạng ¶vk/ ¶y ta có: Như vậy: Ta tiếp tục xét ¶y/¶u trong chuỗi tính ¶E/¶a Đặt : Ta có: Và cuối cùng ¶u/¶a, trong chuỗi tính ¶E/¶a chính là thay đổi của u đối với thay đổi của một trọng số. Nó phụ thuộc vào loại trọng số. Đối với trọng ngưỡng a0, ta có: Với các trọïng trên cung nối trực tiếp ai, i>0 ta có: Tóm lại: 3. Một vài kỹ thuật luyện mạng: a. Học theo lô: Như đã nói trong phần trước, trọng số của mạng được cập nhật khi tất cả các mẫu học đều đã được đưa vào mạng (học theo bước học). Đây là một kỹ thuật học theo lô. Trong cách học thông thường của thuật toán lan truyền ngược, mỗi khi ta đưa vào mạng một mẫu học đạo hàm hàm lỗi được tính và trọng số được cập nhật ngay, sau đó mẫu học tiếp theo được đưa vào mạng và quá trình trên được lặp lại cho từng mẫu học. Mỗi bước trong quá trình trên gọi là một bước lặp. Khi tất cả các mẫu trong tập học đã được đưa vào mạng, ta hoàn tất bước học. Cách cập nhật này có thể dẫn đến trường hợp ở một bước lặp p trọng số được cập nhật sao cho giảm E(p), nhưng ở một bước lặp q khác, trọng số lại được cập nhật sao cho tăng E(q). Kết quả là một bước học sẽ chứa đựng sự tự mâu thuẫn trong nó, cụ thể sẽ có một bước lặp làm ngược lại với những kết quả đã đạt được ở những bước trước một cách cục bộ tại một trọng số. Điều này làm cho quá trình học nhiễu loạn và kém hiệu quả. Cách học theo bước giúp ta tránh được hiện tượng này. Trong phương pháp này trọng số sẽ được cập nhật sau mỗi bước học. Nghĩa là tất cả các mẫu học sẽ được đưa vào mạng và các đạo hàm riêng phần ứng với mỗi trọng số và mỗi mẫu học sẽ được tính toán. Sau đó đạo hàm riêng phần ứng với mỗi trọng số sẽ được tính bằng tổng tất cả các đạo hàm riêng phần ứng với trọng số đó trên tất cả các mẫu học. Phương pháp học theo bước học đã được ứng dụng rộng rãi trong các hệ thống xử lý lớn nhờ khả năng áp dụng việc xử lý song song cho việc tính toán các đạo hàm riêng phần. b. Ngăn chặn quá khớp: Quá khớp: Là trường hợp mạng thuộc hết dữ liệu học ( kể cả nhiễu), lúc đó nó sẽ trả lời chính xác những gì nó được học còn những gì nó không được học thì không quan tâm. Nghĩa là mạng không có khả năng tổng quát hoá, mà tổng quát lại là điều ta cần khi sử dụng mạng. Cách khắc phục: Có nhiều cách khắc phục tình trạng này song cách đơn giản nhất là: Chia mẫu thành tập luyện và tập kiểm tra. Luyện mạng với tập mẫu luyện, nhưng định kỳ ngừng luyện để đánh giá sai số bằng tập mẫu kiểm tra. Mỗi lần ngừng lại để đánh giá sai số trên mẫu kiểm tra, cần lưu lại các trọng số. Khi sai số trên mẫu kiểm tra đi lên, thì quá khớp đã bắt đầu. Do vậy, ta ngừng luyện, trở về trọng sinh lỗi thấp nhất trên mẫu kiểm tra. PHẦN III KẾT QUẢ THỬ NGHIỆM CHƯƠNG I MINH HỌA ỨNG DỤNG GIẢI THUẬT TÁCH THÀNH PHẦN LIÊN THÔNG TRONG BÀI TOÁN NHẬN DẠNG ẢNH VĂN BẢN Trước khi xây dựng chương trình nhận dạng kí tự viết tay, em xin giới thiệu một ứng dụng có liên quan đến nhận dạng kí tự, đó là ứng dụng nhận dạng ảnh văn bản. Với cơ sở lí thuyết vừa nêu ta hoàn toàn có thể xây dựng được ứng dụng này. I. Nhận dạng một văn bản: Giả thiết coi đầu vào chỉ là một ảnh văn bản đơn giản: chỉ có một cột và gồm các kí tự ( tuy nhiên không nhất thiết chỉ chứa kí tự vì có thể hoàn toàn loại bỏ các liên thông là hình ảnh nếu căn cứ vào kích thước của chúng). Ta có sơ đồ nhận dạng như sau: Tách liên thông Khử liên thông đặc biệt Xác định hàng liên thông Sửa lỗi xác định hàng Tách liên thông dính Nhận dạng các liên thông Aûnh văn bản đơn Tập các liên thông ( còn liên thông đặc biệt & liên thông dính) Tập liên thông đã được xử lý Các liên thông đã được sắp xếp theo hàng Trật tự các liên thông trên hàng được xếp lại Vị trí các liên thông đã được xếp đúng Văn bản có thể hiệu chỉnh II. Minh hoạ chương trình: Chương trình sau đây minh hoạ cho nhận dạng văn bản chứa kí tự font Vni-Times, size 12.Việc nhận dạng từng kí tự được thực hiện như sau: Kí tự được chuẩn hoá vào lưới ô vuông kích thước 56x48 điểm ảnh. Cách xác định đặc trưng của font chữ in như sau: Chia khung kí tự thành nhiều ô vuông nhỏ kích thước 8x8. Trên mỗi ô vuông nhỏ ta xác định 4 đặc trưng gồm: Tổng số pixel có hướng 0 hoặc 4 Tổng số pixel có hướng 1 hoặc 5 Tổng số pixel có hướng 2 hoặc 6 Tổng số pixel có hướng 3 hoặc 7 Hướng của pixel được xác định so với pixel ở trung tâm của ô vuông kích thước 8x8. Như vậy với một ảnh kí tự ta sẽ có được 7x6x4=169 đặc trưng, X=(x1, x2, …xn) n=169. Giải thuật nhận dạng trong chương trình dựa trên ý tưởng: tìm một mẫu trong số các mẫu lưu trữ có đặc trưng gần giống nhất với mẫu nhận dạng. Hàm “gần giống” dựa vào hàm tính khoảng cách ơclit giữa hai vectơ. Chương trình minh hoạ cho nhận dạng văn bản tiếng Việt không chứa kí tự đặc biệt, kết quả cho thấy việc tách chữ và xác định hàng tương đối chính xác, độ chính xác nhận dạng khoảng 93-95%. Thực hiện như sau: Nạp ảnh văn bản cần nhận dạng vào, sau đó nhấn nút nhận dạng để xem kết quả. Ta có hình minh hoạ kết quả nhận dạng: CHƯƠNG II CHƯƠNG TRÌNH NHẬN DẠNG KÍ TỰ VIẾT TAY I. Giới thiệu chương trình: Chương trình nhận dạng các kí tự viết tay không trực tuyến, ảnh kí tự nhận dạng được thu nhận qua máy quét hoặc viết trực tiếp vào vùng nhận dạng. Aûnh có thể chứa nhiều kí tự, được viết trên nhiều hàng khác nhau. Tuỳ vào mục đích ứng dụng cần phát triển mà ta xây dựng tập mẫu cho mỗi ứng dụng. Bước đầu thử nghiệm em xây dựng bộ nhận dạng cho 2 lớp kí tự gồm: kí tự là chữ cái không có dấu và kí tự là chữ số. Lớp kí tự chữ cái: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, d, e, f, g, h, i, j, k, l, m, n, q, r, s, t, v, x, y. Lớp kí tự số : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Do một số