Khóa luận Nghiên cứu về nhận dạng chữ in Tiếng Việt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Bùi Thế Hân NGHIÊN CỨU VỀ NHẬN DẠNG CHỮ IN TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Bùi Thế Hân NGHIÊN CỨU VỀ NHẬN DẠNG CHỮ IN TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Lê Anh Cường HÀ NỘI - 2009 Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân i Lời cảm ơn Lời đầu tiên em xin bày tỏ lòng biết ơn sâu sắc tới TS. Lê Anh Cường, người đã không chỉ hướng dẫn em tận tình trong suốt năm học và thời gian làm luận văn. Mà còn là người đã khơi dậy trong em lòng yêu nghề, yêu Công Nghệ Thông Tin. Đồng thời Thầy cũng là người giúp em nhìn thấy con đường đi của riêng mình. Một lần nữa xin được nói lời cảm ơn với Thầy. Em xin bày tỏ lòng biết ơn tới các thầy, cô giáo trong Khoa Công nghệ thông tin - Trường Đại học Công nghệ - ĐHQGHN. Các thầy cô đã dạy bảo, chỉ dẫn chúng em và luôn tạo điều kiện tốt nhất cho chúng em học tập trong suốt quá trình học đại học đặc biệt là trong thời gian làm khoá luận tốt nghiệp. Tôi xin cảm ơn các bạn sinh viên lớp K50CB trường Đại học Công nghệ và các bạn trong lớp KHMT, đã giúp đỡ tôi trong suốt quá trình học tập. Cuối cùng con xin gửi tới bố mẹ và toàn thể gia đình lòng biết ơn và tình cảm yêu thương. Hà Nội, ngày 22 tháng 5 năm 2009 Bùi Thế Hân Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân ii Tóm tắt Nhận dạng chữ in nói chung và nhận dạng chữ in tiếng Việt nói riêng đã và đang là những bài toán thu hút nhiều sự quan tâm và nghiên cứu. Bài toán nhận dạng chữ in tiếng Việt gồm ba công đoạn chủ yếu: Phân đoạn ảnh, nhận dạng kí tự và hậu xử lý. Trong luận văn này tôi tập trung chủ yếu vào giai đoạn Phân đoạn ảnh, nhằm đưa ra những cải tiến để đẩy nhanh tốc độ xử lý. Đồng thời chúng tôi cũng sử dụng môdul nhận dạng để xây dựng thành một hệ thống hoàn chỉnh. Với bài toán nhận dạng chữ tiếng Việt có sự khó khăn do hệ thống dấu tiếng Việt làm số kí tự cần nhận dạng tăng lên rất nhiều, đồng thời làm tăng khả năng giao nhau giữa các dòng, các ký tự. Để giải quyết vấn đề đó, trong khóa luận này chúng tôi sử dụng phương pháp tách dòng dựa vào khoảng trắng, thành phần liên thông. Trong phần thực nghiệm của luận văn, chúng tôi cũng thực nghiệm các văn bản với nhiều cỡ chữ và font chữ khác nhau. Kết quả của việc phân đoạn ảnh và nhận dạng là tương đối tốt, có thể chấp nhận được. Từ khóa: Xác định góc nghiêng văn bản, Tách dòng văn bản, Thành phần liên thông, Biểu đồ Histogram, Mạng Neural, Nhận dạng kí tự quang học, trích trọn đặc trưng. Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân iii MỤC LỤC Chương 1 Giới thiệu................................................ 1 1.1 Đặt vấn đề...............................................................................................................1 1.2 Nội dung nghiên cứu của khóa luận ..........................................................................3 1.3 Cấu trúc khóa luận....................................................................................................3 Chương 2 Cơ sở lý thuyết cho phân đoạn ảnh.... 5 2.1 Khái niệm ảnh số......................................................................................................5 2.2 Nhị phân hóa ............................................................................................................6 2.3 Biểu đồ sắc thái của hình ảnh (Histogram)................................................................8 2.4 Thành phần liên thông ..............................................................................................8 2.4.1 Khái niệm điểm lân cận .....................................................................................9 2.4.2 Thành phần liên thông: Liên thông bốn và liên thông tám..................................9 Chương 3 Phân đoạn ảnh cho nhận dạng văn bản .................................................................................. 11 3.1 Tiền xử lý ảnh ........................................................................................................11 3.1.1 Nhị phân hóa ...................................................................................................11 3.1.2 Lọc nhiễu ........................................................................................................11 3.1.3 Xoay lại ảnh ....................................................................................................12 3.2 Tách đoạn...............................................................................................................14 3.3 Tách dòng ..............................................................................................................14 3.3.1 Tách dòng dựa vào các đường kẻ ngang...........................................................14 3.3.2 Tách dòng dựa vào thành phần liên thông ........................................................15 3.3.3 Tách dòng dựa vào khoảng trắng giữa các dòng...............................................16 3.4 Tách từ ...................................................................................................................17 3.4 Tách ký tự ..............................................................................................................18 Chương 4 Trích chọn đặc trưng .......................... 20 4.1 Khái niệm cơ bản ...................................................................................................20 4.1.1 Đặc trưng ảnh – Image Features.......................................................................20 4.1.2 Trích chọn đặc trưng – Feature Extraction .......................................................20 4.2 Vai trò của trích chọn đặc trưng..............................................................................20 4.3 Một số phương pháp trích chọn đặc trưng...............................................................21 4.3.1 Phương pháp trích chọn đặc trưng GSC ...........................................................21 Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân iv 4.3.1 Trích chọn đặc trưng theo hướng hình học .......................................................22 4.3.2 Trích chọn đặc trưng theo cấu trúc...................................................................25 4.3.3 Trích chọn đặc trưng theo tính lồi lõm .............................................................27 Chương 5: Phân lớp và mô hình học máy.......... 30 5.1 Cấu trúc hoạt động của mạng neuron ....................................................................30 5.1.1 Cấu trúc và hoạt động của một neuron .............................................................30 5.1.2 Cấu trúc và hoạt động của mạng neuron...........................................................31 5.1.3 Hàm truyền......................................................................................................33 5.2 Quá trình huấn luyện mạng và các thuật toán học mạng..........................................34 5.2.1 Mạng neuron và bài toán phân loại mẫu ...........................................................34 5.2.2 Đặc trưng của mạng neuron .............................................................................34 5.2.3 Các phương pháp huấn luyện mạng .................................................................34 5.2.4 Mạng lan truyền ngược nhiều tầng (Back-propagation Neural Network).........35 5.3 Ứng dụng mô hình nhận dạng cho tiếng Việt ..........................................................38 5.3.1 Khó khăn và giải pháp đề xuất cho nhận dạng kí tự..........................................38 5.3.2 Phân nhóm kí tự ..............................................................................................40 Chương 6 Thực nghiệm ........................................ 42 6.1 Môi trường thực nghiệm.........................................................................................42 6.2 Thực nghiệm về phân đoạn ảnh ..............................................................................42 6.2.1 Tách dòng........................................................................................................42 6.2.3 Tách từ ............................................................................................................43 6.2.4 Tách ký tự .......................................................................................................43 6.2.5 Thực nghiệm nhận dạng...................................................................................44 Chương 7: Kết Luận .............................................. 45 Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân v Danh mục hình vẽ Hình 1.1 Sơ đồ hệ nhận dạng văn bản tiếng Việt. ..............................................................2 Hình 2.1 Ví dụ về quá trình lấy mẫu...................................................................................5 Hình 2.2: Ví dụ chuyển ảnh đa mức xám sang ảnh nhị phân. ..............................................6 Hình 2.3 ví dụ về chuyển ảnh nhị phân...............................................................................7 Hình 2.4 Minh họa biểu đồ Histogram ngang. ....................................................................8 Hình 2.5a: Ví dụ lân cận bốn..............................................................................................9 Hình 2.5b: Ví dụ lân cận tám..............................................................................................9 Hình 2.6: Hai ví dụ về thành phần liên thông 4-connected..................................................9 Hình 2.7: Hai ví dụ về thành phần liên thông 8.................................................................10 Hình 3.1 Ví dụ về nhiễu đốm ...........................................................................................11 Hình 3.2 Ảnh sau khi áp dụng lọc trung vị. ......................................................................12 Hình 3.3: Histogram của một văn bản không nghiêng. .....................................................13 Hình 3.4: Histogram của văn bản nghiêng. .......................................................................13 Hình 3.5 Ví dụ minh họa cắt đoạn ....................................................................................14 Hình 3.6: Các đường đặc trưng của một dòng văn bản......................................................15 Hình 3.7: Biểu đồ phân cách của ngưỡng. ........................................................................18 Hình 3.8: Các vị trí chính xác, vị trí cắt nhập nhằng. ........................................................19 Hình 5.1: Mố hình phi tuyến của một neuron ...................................................................31 Hình 5.3 Mạng neuron hai lớp..........................................................................................36 Hình 5-4 : Hình ảnh kí tự được chia làm 3 phần. ..............................................................40 Hinh 5-5:ảnh gốc .............................................................................................................40 Hình 5-6: Ảnh cắt ............................................................................................................41 Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân vi Hình 6.1: Minh họa tách dòng văn bản. ............................................................................42 Hình 6.2: Minh họa cắt từ. ...............................................................................................43 Nghiên cứu nhận dạng chữ in tiếng việt Bùi Thế Hân vii Danh mục bảng biểu Bảng 4.1 Các luật về đặc trưng theo cấu trúc của điểm ảnh .............................................25 Bảng 5-1. Một số hàm truyền ..........................................................................................33 Bản 6.1 Kết quả thực nghiệm tách từ................................................................................43 Bảng 6.2 Kết quả thực nghiệm tách từ..............................................................................43 Bảng 6.3 Kết quả thực nghiệm tách từ..............................................................................44 Chương I: Giới thiệu Bùi Thế Hân 1 Chương 1 Giới thiệu 1.1 Đặt vấn đề Nhận dạng kí tự quang học (OCR – Optical Character Recognition) là một bài toán chuyển các hình ảnh của chữ viết tay hoặc chữ đánh máy (thường được quét bằng máy scanner) thành các văn bản tài liệu. Do bài toán vẫn còn nhiều vấn đề chưa được giải quyết một cách triệt để, như vấn đề về tốc độ xử lý, độ chính xác của tách từ, hay độ chính xác của nhận dạng. Và vì vậy vẫn nhận được nhiều sự quan tâm nghiên cứu, đặc biệt cho tiếng Việt. Nhận dạng văn bản được áp dụng trong quá trình tự động hoá các công việc văn phòng như nhập liệu, lưu trữ văn bản, sách báo, phân loại thư tín, …, những công việc đòi hỏi nhiều thời gian của con người. Hiện nay cũng có rất nhiều bài báo đề cập đến bài toán nhận dạng kí tự quang học, nhằm cải tiến các phương pháp phân đoạn ảnh, nhận dạng. Song vẫn chưa giải quyết một cách triệt để những vấn đề khó khăn của bài toán thường gặp phải. Đặc biệt là đối với việc nhận dạng các kí tự tiếng Việt, gặp rất nhiều khó khăn, do tính riêng biệt của tiếng Việt: Số kí tự nhiều, các kí tự lại có dấu…Nên bài toán vẫn còn thu hút được sự quan tâm, nghiên cứu nhằm giải quyết những vấn đề khó khăn của bài toán một cách triệt để. Một số hệ nhận nhận dạng văn bản đã và đang được áp dụng rất nhiều vào ứng dụng như FineReader của hãng AABBYY, OmmiPage của hãng Scansoft được dùng để nhận dạng các văn bản tiếng Anh,… VNDOCR của Viện công nghệ thông tin cho các văn bản tiếng Việt. Bài toán nhận dạng văn bản được thực hiện qua ba giai đoạn chính: Phân đoạn ảnh, nhận dạng từ và hậu xử lý. Trong luận văn này chúng tôi đi sâu vào nghiên cứu cải tiến công đoạn phân đoạn ảnh. Bên cạnh đó kết hợp với mô đun nhận dạng [3] để xây dựng thành một hệ thống nhận dạng văn bản hoàn thiện. Bài toán mà chúng tôi đang nghiên cứu được thực hiện qua các giai đoạn như mô tả trong hình I.1.1. Chương I: Giới thiệu Bùi Thế Hân 2 Hình 1.1 Sơ đồ hệ nhận dạng văn bản tiếng Việt. Đầu vào của hệ thống nhận dạng của chúng ta là một hình ảnh scan từ một văn bản tiếng Việt. Đầu ra là một bản đã được nhận dạng, văn bản này có thể chỉnh sửa. Để xử lý được điều này hệ thống nhận dạng của chúng ta sẽ trải qua giai đoạn sau đây: 1. Phân đoạn ảnh: Giai đoạn này có nhiệm vụ loại bỏ nhiễu nhằm nâng cao chất lượng hình ảnh đầu vào. Sau đó thực hiện việc tách đoạn, tách dòng, tách từ, tách kí tự. 2. Bộ nhận dạng kí tự: Đầu vào của giai đoạn này là ảnh của một kí tự, đầu ra là kí tự nhận dạng được. Thông thường trong phần này sử dụng một thuật toán học máy hoặc một bộ đối sánh mẫu. 3. Bộ hậu xử lý: Tổng hợp các kí tự nhận dạng được và hiển thị lên cho người dùng. Đồng thời trong phần này có nhiều nghiên cứu và hệ thống đưa nhiệm vụ điều chỉnh nhận dạng sai dùng từ điển hoặc mô hình ngôn ngữ. Từ sơ đồ hình I.1.1 chúng ta cũng thấy rằng để xây dựng được hệ thống nhận dạng thì có hai công đoạn quan trọng nhất: Phân đoạn ảnh và Xây dựng bộ nhận Văn bản sau khi scan Bộ phân đoạn ảnh Văn bản được nhận dạng Bộ nhận dạng Bộ hậu xử lý Chương I: Giới thiệu Bùi Thế Hân 3 dạng kí tự. Trong luận văn này chúng tôi đi vào nghiên cứu và cải tiến các phương pháp nhằm nâng cao chất lượng của giai đoạn phân đoạn ảnh. Đồng thời chúng tôi cũng sử dụng lại các bộ nhận dạng kí tự có sẵn, để xây dựng lên một hệ thống nhận dạng văn bản hoàn chỉnh. 1.2 Nội dung nghiên cứu của khóa luận Bài toán thực hiện trong khóa luận này là bài toán nhận dạng chữ in tiếng Việt ứng dụng trong quá trình tự động hóa các công việc văn phòng. Bài toán này gồm 3 công đoạn chủ yếu. Nhưng trong khoá luận này tập trung chủ yếu vào việc nghiên cứu cải tiến ứng dụng phân đoạn ảnh vào nhận dạng văn bản tiếng Việt: giải pháp và các thực nghiệm. Đồng thời cũng nghiên cứu lý thuyết cơ bản về các hệ nhận dạng đã được xây dựng và phát triển. Để xây dựng được một hệ thống nhận dạng hoàn chỉnh chúng tôi đã thực hiện việc cài đặt các giải pháp đề xuất trong luận văn, kết hợp với các bộ nhận dạng kí tự có sẵn. Tách đoạn, tách dòng, tách từ và tách ký tự là bốn nội dung quan trọng của quá trình phân đoạn ảnh. Độ chính xác của mỗi giai đoạn có thể làm ảnh hưởng đến độ chính xác của giai đoạn khác, cũng như của toàn bộ hệ thống. Chúng tôi nghiên cứu đánh giá một số phương pháp được sử dụng để thực hiện các nội dung đó, và áp dụng nó vào bài toán nhận dạng văn bản chữ in tiếng Việt. Trong giai đoạn nhận dang kí tự, trong luận văn này chúng tôi đề xuất sử dụng mô hình mạng neuron cho việc nhận dạng. 1.3 Cấu trúc khóa luận Các phần còn lại của khóa luận có cấu trúc như sau: Chương 2 trình bày cơ sở lý thuyết của phân đoạn ảnh, bao gồm các khái niệm cơ bản, các kỹ thuật cơ bản được sử dụng trong phân đoạn ảnh. Chương 3 trình bày chi tiết về phân đoạn ảnh cho nhận dạng văn bản. Đồng thời chúng tôi đưa ra những giải pháp nhằm cải tiến chất lượng cũng như tốc độ của phân đoạn ảnh. bao gồm các thuật toán xác định góc nghiêng văn bản, các thuật toán tách đoạn,tách dòng, tách từ và tách ký tự. Chương I: Giới thiệu Bùi Thế Hân 4 Chương 4: Trình bày các phương pháp trích chọn đặc trưng cơ bản. Áp dụng các phương pháp trích chọn đặc trưng cho tiếng Việt. Chương 5: Trình các mô hình học máy và ứng dụng các mô này vào nhận dạng tiếng Việt Chương 6: trình bày về các kết quả thực nghiệm của quá trình thu thập cơ sở dữ liệu, trong quá trình phân đoạn ảnh và kết quả thực nghiệm của hệ thống nhận dạng sau khi đã ghép nối các thành phần lại với nhau. Chương 7: Kết luận Chương 2:Cơ sở lý thuyết cho phân đoạn ảnh Bùi Thế Hân 5 Chương 2 Cơ sở lý thuyết cho phân đoạn ảnh Đầu vào hệ thống nhận dạng là một ảnh bất kì, nhưng phân đoạn ảnh thì thực hiện hoàn toàn trên ảnh nhị phân. Đồng thời kết hợp với một số phương pháp để xử lý theo nhưng yêu cầu của công việc. 2.1 Khái niệm ảnh số Ảnh số được tạo nên từ hàng trăm ngàn cho đến hàng triệu ô vuông rất nhỏ- được coi là những thành tố của bức ảnh và thường được biết dưới tên gọi là pixels. Máy tính hay máy in sử dụng những ô vuông nhỏ này để hiển thị hay in ra bức ảnh. Để làm được điều đó máy tính hay máy in chia màn hình, trang giấy thành một mạng lưới chứa các ô vuông, sau đó sử dụng các giá trị chứa trong file ảnh để định ra mầu sắc, độ sáng tối của từng pixel trong mạng lưới đó - ảnh số được hình thành. Việc kiểm soát, định ra địa chỉ theo mạng lưới như trên được gọi là bit mapping và ảnh số còn được gọi là ảnh bit-maps. Hình 2.1 Ví dụ về quá trình lấy mẫu. Chương 2:Cơ sở lý thuyết cho phân đoạn ảnh Bùi Thế Hân 6 Một bức ảnh số a[m, n] gồm có m hàng và n cột, phần giao giữa một hàng và một cột được gọi là điểm ảnh (Pixel). Giá trị mỗi điểm ảnh được gán cho một số nguyên biểu diễn màu sắc tại điểm ảnh đó. 2.2 Nhị phân hóa Ảnh nhị phân là ảnh số mà trong đó giá trị mỗi điểm ảnh có thể nhận một trong hai giá trị 0 hoặc 1. Quá trình phân đoạn ảnh yêu cầu ảnh đầu vào phải là ảnh nhị phân, trong khi đó ảnh đầu vào của hệ thống là một ảnh đa mức xám, chính vì vậy mà cần phải thực chuyển ảnh đa mức xám sang ảnh nhị phân để thực hiên phân đoạn (hình II.2.2 ). Hình 2.2: Ví dụ chuyển ảnh đa mức xám sang ảnh nhị phân. Quá trình này được thực hiện nhờ vào hàm phân ngưỡng: Dest(x, y) = 1 if Source(x, y) >= T 0 if Source(x, y) < T Trong đó, Source(x,y) là giá trị điểm ảnh ở vị trí (x,y) của ảnh nguồn, Dest(x,y) là giá trị điểm ảnh tương ứng ở vị trí (x,y) của ảnh đích. T là giá trị ngưỡng. Tuy nhiên, giá trị cụ thể của ngưỡng lại phụ thuộc vào từng ảnh, vùng ảnh đầu vào đang xét, không thể lấy cố định. Ví dụ như trên hình II.2.3, thể hiện ảnh đã được nhị phân hóa với ngưỡng thấp, ngưỡng cao Chương 2:Cơ sở lý thuyết cho phân đoạn ảnh Bùi Thế Hân 7 Hình 2.3 ví dụ về chuyển ảnh nhị phân. Để xác định giá trị của ngưỡng hiện nay có rất nhiều phương pháp được sử dụng: 1. Chọn ngưỡng theo phân phối xác suất mức xám. 2. Chọn ngưỡn cố định. 3. Thuật toán Isodata (Iterative self-organizing data analysis technique) 4. Thuật toán Background-symmetry 5. Thuật toán Triangle (thuật toán tam giác) Tùy vào điều kiện và mục đích chúng ta có thể sử dụng một phương pháp xác định ngưỡng thích hợp. Vì mỗi phương pháp đều có những ưu điểm và nhược điểm riêng của mình. Trong luận văn này chúng tôi sử dụng phương pháp chọn ngưỡng theo phân phối mức xám. Phương pháp chọn ngưỡng theo phân phối mức xám: là thiết lập ngưỡng sao cho số lượng các điểm đen đạt một ngưỡng chấp nhận được. Ví dụ, chúng ta có thể biết rằng các kí tự chiếm 25% diện tích của một trang văn bản thông thường. Vì thế Chương 2:Cơ sở lý thuyết cho phân đoạn ảnh Bùi Thế Hân 8 chúng ta có thể thiết lập ngưỡng sao cho số lượng điểm đen còn lại chiếm ¼ trang văn bản. Phương pháp này có ưu điểm là tiết kiệm được tính toán, kết quả của phép chọn chấp nhận được trong bài toán nhận dạng của chúng ta. 2.3 Biểu đồ sắc thái của hình ảnh (Histogram) Histogram là một dạng biểu đồ với trục hoành là độ sáng và trục tung là số lượng điểm ảnh ở những độ sáng tương ứng. Hoặc nói dễ hiểu hơn Histogram là 1 biểu đồ trong đó cột đứng tượng trưng cho số điểm ảnh còn cột ngang tượng trưng cho dãy sắc độ chuyển từ đen (bên trái) sang trắng (bên phải). Chúng ta có thể nhìn vào Histogram để đánh giá về sắc thái và mức độ tương phản của một hình. Trong hầu hết các ứng dụng đồ hoạ chuyên nghiệp đều cung cấp cho ta công cụ này. Và trong phần review của các máy ảnh số sau này cũng thường có phần hiển thị histogram. Hiện nay có hai loại Histogram phổ biến là: Histogram theo chiều ngang và Histogram theo chieu doc. Hình 2.4 Minh họa biểu đồ Histogram ngang. 2.4 Thành phần liên thông Chương 2:Cơ sở lý thuyết cho phân đoạn ảnh Bùi Thế Hân 9 2.4.1 Khái niệm điểm lân cận Cho một điểm P với tọa độ (x, y), khi đó bốn điểm (x + 1, y); (x – 1, y), (x, y + 1), (x, y – 1) được gọi là lân cận bốn (hình 2.3a) của điểm P, và các điểm (x - 1, y - 1); (x – 1, y + 1); (x + 1, y - 1); (x + 1, y + 1)} Tám điểm đến được gọi là lân cận 8 (hình II.1.5b) của điểm P. Hình 2.5a: Ví dụ lân cận bốn Hình 2.5b: Ví dụ lân cận tám 2.4.2 Thành phần liên thông: Liên thông bốn và liên thông tám Hai điểm , được gọi là liên thông bốn với nhau nếu có một trong hai điều kiện:  là lận cận bốn với của (hoặc là lân cận bốn với  Tồn tại điểm mà là lân cận bốn của và là lân cận bốn của . Hình 2.6: Hai ví dụ về thành phần liên thông 4-connected. Chương 2:Cơ sở lý thuyết cho phân đoạn ảnh Bùi Thế Hân 10 Hai điểm , được gọi là liên thông tám với nhau nếu có một trong hai điều kiện:  là lận cận tám với của (hoặc là lân cận bốn với  Tồn tại điểm mà là lân cận tám của và là lân cận tám của . Hình 2.7: Hai ví dụ về thành phần liên thông 8 Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 11 Chương 3 Phân đoạn ảnh cho nhận dạng văn bản 3.1 Tiền xử lý ảnh Đầu vào của quá trình xử lý ảnh là các ảnh gốc ban đầu, thu được qua scanner. Do cách ảnh ban đầu thường có chất lượng thấp do ảnh hưởng của nhiễu, do bị nghiêng, có thể bị đứt nét nên để tăng chất lượng nhận dạng ta cần phải có một quá trình tiền xử lý ảnh để nâng cao chất lượng ảnh đầu vào trước khi đưa vào nhận dạng. 3.1.1 Nhị phân hóa Đầu vào ban đầu của hệ nhận dạng là một ảnh đa mức xám. Mà phân đoạn ảnh chúng ta xử lý trên ảnh nhị phân, chính vì vậy chúng ta phải thực hiện chuyển về ảnh nhị phân. Phương pháp mà chúng tôi sử dụng để chuyển sang ảnh nhị phân là xác định dựa vào ngưỡng. Ngưỡng được xác định dựa trên phân phối mức xám của ảnh đã được trình bày ở trên. 3.1.2 Lọc nhiễu Trong nhận dạng nói chung và trong nhận dạng chữ viết nói riêng, nhiễu thường gặp và có nhiều ảnh hưởng đến kết quả nhận dạng là nhiễu đốm và nhiễu vạch. Hiện nay, chất lượng máy quét rất tốt vì thế nhiễu vạch đã giảm nhiều, tuy nhiên nhiễu đốm thì vẫn thường thấy. Hình 3.1 Ví dụ về nhiễu đốm Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 12 Trong khóa luận này chúng tôi chỉ giới hạn ở việc xử lý các nhiễu đốm, việc loại bỏ các nhiễu đốm được thực hiện bằng cách áp dụng bộ lọc trung vị (median filter). Lọc trung vị: Cho I là ảnh, với mỗi điểm P trong ảnh ta lấy cửa sổ W(P), sau đó lấy trung vị và gán điểm P. Hình 3.2 Ảnh sau khi áp dụng lọc trung vị. 3.1.3 Xoay lại ảnh Ảnh đầu vào của chúng ta là ảnh scan lên rất dễ bị xoay. Chính vì vậy việc xoay lại ảnh hay khử độ nghiêng của ảnh là rất cần thiết, cho việc xử lý sau này. Công việc xoay văn bản gồm 2 giai đoạn chính là:  Xác định góc nghiêng.  Xoay lại ảnh theo góc nghiêng đã xác định. Hiện nay thì có ba phương pháp thường được xử dụng để xác định góc nghiêng của ảnh là: Sử dụng Histogram, phương pháp láng giềng gần nhất, phương pháp sử dụng biến đổi Hough. Phương pháp sử dụng biến đổi Hough rất hữu ích cho việc dò tìm đường thẳng trong trang văn bản vì thế rất thích hợp cho việc xác định góc nghiêng của trang văn bản gồm các thành phần là các dòng văn bản. Biến đổi Hough cần rất nhiều tính toán do phải thao tác trên từng điểm ảnh riêng lẻ. Mặc dùng hiện phương pháp này được rất nhiều người nghiên cứu và cải tiến. Tuy vậy tốc độ xử lý của phương pháp này là tương đối chậm, so với các phương pháp khác. Phương pháp láng giềng gần nhất: Phương pháp này được phát triển dựa trên nhận xét: trong một trang văn bản, khoảng cách giữa các kí tự trong một từ và giữa các kí tự của từ trên cùng một dòng là nhỏ hơn khoảng cách giữa hai dòng văn bản, vì thế đối với mỗi kí tự, láng giềng gần nhất của nó sẽ là các kí tự liền kề trên cùng một dòng văn bản. Phương pháp này có tốc độ nhanh hơn phương pháp biến đổi Hough tuy vậy thì nó vẫn châm hơn phương pháp sử dụng Histogram. Và một điểm khá quan trọng là nó khó có thể áp dụng cho tiếng Việt, vì: với những chữ có 3 Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 13 thành phần gồm thân, mũ và dấu hỏi. Khi đó, láng giềng gần nhất của mỗi phần sẽ là một trong hai thành phần còn lại chứ không phải là kí tự liền kề với nó Phương pháp sử dụng Histogram được phát triển dựa trên nhận xét: khi văn bản không bị nghiêng thì các điểm đen tập trung chủ yếu ở các đường thuộc dòng văn bản, các tại các đường không thuộc dòng văn bản, số điểm đen là rất ít. Trong khi đó đối với văn bản nghiêng thì số điểm đen lại được phân bố khá đồng đều ở cả các đường thuộc dòng văn bản, và các đường không thuộc dòng văn bản. Hình 3.3: Histogram của một văn bản không nghiêng. Hình 3.4: Histogram của văn bản nghiêng. Thuật toán xác định Histogram để xác định góc nghiêng: Mô tả thuật toán:  h là chiều cao của ảnh (tính theo điểm ảnh).  entireBlackPoints là số điểm đen tích lũy, sau khi duyệt hết toàn bộ bức ảnh.  avgPointLine là số điểm đen trung bình tại một đường nằm ngang của ảnh  lineBlackPoint là số điểm đen tích lũy của một dòng.  Delta là phương sai của điểm đen trên một đường nằm ngang với số điểm đen trung bình. Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 14 Ta thấy rằng góc lệch của văn bản thường chỉ nằm trong khoảng [-25, 25] độ. Chính vì vậy ta quay ảnh tại các góc trong khoảng [-25,25] với bước nhảy góc là stepAngle, và tính giá trị Delta tại mỗi lần quay, góc quay mà tại đó giá trị lớn nhất của theta, sẽ ứng với góc nghiêng của văn bản. 3.2 Tách đoạn Khi quan sát ảnh quét ta dễ nhận ra, mỗi văn bản sẽ được chia thành các đoạn khác nhau. Mỗi đoạn này có những đặc trưng khá tương đồng về cỡ chữ, font chữ. Chính sự tương đồng đó sẽ tạo điều kiện thuận lợi, giảm bớt sự phức tạp trong giai đoạn xử lý phía sau. Hình 3.5 Ví dụ minh họa cắt đoạn Để tách thành các đoạn (hay các vùng ảnh) chúng ta sử dụng 2 đặc trưng: Khoảng cách trắng giữa các đoạn sẽ lớn hơn khoảng trắng giữa các dòng, lùi đầu dòng của dòng kế tiếp. 3.3 Tách dòng 3.3.1 Tách dòng dựa vào các đường kẻ ngang Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 15 Ta nhận thấy, với mỗi dòng văn bản chúng ta có thể chia làm 3 vùng dựa vào bốn đường cơ bản là : Top_Line, Bottom_Line, X_Line, Base_Line. Hình 3.6: Các đường đặc trưng của một dòng văn bản. Bước 1:Ý tưởng chính của phương pháp này là dựa trên nhận xét các điểm đen tập trung chủ yếu trong khoảng đường Base_line và X_Line. Các đường này thì có số điểm đên lớn hơn số điểm đên trung bình chính vì vậy chúng ta có thể xác định được hai đường Base_Line và X_Line. Bước 2:Sau khi xác định được Base_Line và X_Line chúng ta tiến hành xác định miền liên thông. Bước 3:tiếp theo là ta duyệt tất cả các miền liên thông. Nếu miền liên thông nào có diện tích về dòng nào nhiều hơn, thì thuộc về dòng đó. Nhận xét: Tuy nhiên phương pháp này sẽ gây ra lỗi nếu có xuất hiện các dòng ngắn. Khi đó vì số ký tự trong dòng này quá ít, nên trong khoảng từ base-line đến x-line, số điểm đen trên mỗi đường vẫn nhỏ hơn giá trị trung bình. Có thể khắc phục lỗi này bằng cách gọi đệ qui với các vùng chứa các dòng ngắn. Phương pháp cũng sẽ gây lỗi nếu gặp dòng toàn chữ in hoa (không tồn tại 4 đường đặc trưng như trên), và khó áp dụng đối với văn bản tiếng việt vì tiếng việt có thêm các dấu nên nhiều trường hợp giá trị x-line tìm được lại chính là top line, kết quả sẽ không chính xác nữa. Sau khi xác định được x-line, base-line cũng khó phân tách các dòng, nếu chúng khá liền nhau (hoặc dính vào nhau). 3.3.2 Tách dòng dựa vào thành phần liên thông Ý tưởng của phương pháp này là tìm tất cả các thành phần liên thông trong ảnh và sắp xếp theo thứ tự tăng dần của tung độ của điểm trên nhất. Sau đó dựa vào sự tương quan giữa tung độ của điểm trên nhất, tung độ của điểm dưới nhất của mỗi thành phần liên thông để gộp các thành phần này vào một dòng văn bản. Nhận xét: Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 16 Ưu điểm của phương pháp này ta có thể tách được các dòng mà giữa chúng có phần giao với nhau (không dính) và đường cắt giữa 2 dòng sẽ được đi theo một đường cong, chứ không phải là một đường thẳng như những cách khác. Nhược điểm: Phương pháp này chạy tương đối chậm, do thời gian tính toán thành phần liên thông. Và phải duyệt lại thành phần liên thông nhiều lần. 3.3.3 Tách dòng dựa vào khoảng trắng giữa các dòng Trong đề tài này chúng tôi đề xuất một phương pháp tách dòng đó là tách dòng dựa vào khoảng trắng và kết hợp Histogram ngang. Ý tưởng của phương pháp này đó là dựa vào khoảng trắng giữa các dòng với nhau. Khoảng trắng giữa các dòng chính là nơi ta đặt nhát cát để tách các dòng với nhau. Phương pháp này có ưu điểm là tốc độ rất nhanh. Nhưng nhược điểm của phương pháp này là do sự xuất hiện của nhiễu. Nhiễu có thể làm mất khoảng trắng giữa các dòng, dẫn dến hiện tượng tách sai dòng (Một dòng thành hai hoặc ba dòng). Để giải quyết được nhược điểm của phương pháp này tôi đã kết hợp phương pháp này với Histogram ngang cho các trường hợp nghi ngờ tách hai dòng hay ba dòng. Histogram ngang dựa trên đặc điểm các điểm đen chỉ phân bố chủ yếu tại các đường thuộc các dòng, tại khoảng giữa các dòng thì rất ít. Ta tìm Histogram ngang của văn bản và xác định một ngưỡng threshold nào đó, đối với các đường mà trên đó số điểm đen < threshold thì sẽ được chọn làm phân cách giữa các dòng. Các bước thực hiện: Bước 1: Xác định khoảng trắng giữa các dòng và chọn làm vạch phân cách hay là vị trí cắt các dòng. Quá trình được lặp lại cho đến khi hoàn tất công việc tách dòng trong đoạn. Chiều cao của mỗi dòng phài > minHeightLine (tránh trường hợp tách các dấu thành một dòng) Bước 2: Xác định độ cao trung bình của các dòng trong một đoạn( avgHeightLine ). Thực nghiệm ta thấy ValueHistogram được tính: valueHistogram=avgHeightLine x 1,2 Bước 3: Kiểm tra độ cao của các dòng đã tách. Nếu dòng nào có độ cao > valueHistogram, thì thực hiện bước 4,5. Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 17 Bước 4: Tìm threshold bằng cách trung bình các điểm trong một dòng. Khi thực nghiệm tôi thấy rằng nếu giá trị threshold *=0,2->03. Thì độ chính xác là cao nhất. Bước5:Đối với các đường mà trên đó số điểm đen < threshold thì sẽ được chọn làm phân cách giữa các dòng. Nhận xét: Ưu điểm: Thời gian chạy của phương pháp là nhanh hơn so với 2 phương pháp trên. Độ chính xác của phương pháp qua thực nghiệm là chấp nhận được, khoảng 99 %. Nhược điểm: Phương pháp này không có khả năng tách các dòng mà giữa chúng có phần giao nhau (không dính nhau). Nhưng trên thực tế việc các dòng giao nhau rất ít xẩy ra ở các văn bản. 3.4 Tách từ Trong để tách từ trong dòng văn bản, chúng ta dựa trên nhận xét khoảng cách giữa các kí tự trong một từ, sẽ nhỏ hơn khoảng cách giữa các từ trong một dòng. Ở đây chúng ta sẽ sử dụng một giá trị làm ngưỡng, giá trị này có tác dụng tách khoảng trắng giữa các kí tự với khoảng trắng giữa các từ. Để đạt được độ chính xác cho quá trình tách từ, do các dòng, các từ trong cùng văn bản có thể có kích cỡ khác nhau. Chính vì vậy ta phải xác định ngưỡng đối với từng dòng riêng biệt. Nếu như vậy ta phải xác định lại ngưỡng nhiều lần, để giảm điều này như trên chúng tôi đã đưa thêm vào giai đoạn tách thành các vùng văn bản. Các vùng văn bản này có cỡ chữ thường là giống nhau. Nên ta có thể tính ngưỡng chung cho một vùng của văn bản. Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 18 Hình 3.7: Biểu đồ phân cách của ngưỡng. Thuật toán: Bước 1: Xác định tất cả các khoảng trống trong dòng văn bản. Bước 2: Sắp xếp theo thứ tự tăng dần kích thước khoảng trống, xác định ngưỡng của dòng. Bước 3: Ta lần lượt đi từ đầu đến cuối mảng các khoẩng trống, tại mỗi vị trí ta so sánh kích thước khoảng trống tai đó với kích trước trung bình các khoảng trống đã đi qua, nếu nó vượt quá một giá trị nào đó thì sẽ dừng và xác định là vị trí của nhát cắt. 3.4 Tách ký tự Thao tác được coi là phức tạp nhất của phân đoạn ảnh chính là giai đoạn tách kí tự. Do các kí tự thường bị dính vào nhau, làm cho các nhát cắt của chúng ta trở lên không chính xác. Ở đây chúng ta đưa ra hai khái niệm mới: Nhát cắt chính xác và nhát cắt nhập nhằng. Một nhát cắt được coi là chính xác nếu nhát cắt đó phân thành 2 kí tự. Một vị trí cắt được gọi là nhập nhằng nếu ta không thể chắc chắn đó là vị trí phân tách giữa hai kí tự (thực tế có thể là có). Trong ví dụ hình 3.11 ta có thể thấy có 4 nhát căt, thì 3 vị trí cắt đầu tiên là những chính xác phân tách giữa 2 ký tự tại mỗi vị trí đó. Chương 3: Phân đoạn ảnh cho nhận dạng văn bản Bùi Thế Hân 19 Hình 3.8: Các vị trí chính xác, vị trí cắt nhập nhằng. Trong khi đó nhát cắt 4 lại là một vị trí cắt nhập nhằng. Do chữ ‘ơ’ và chữ n dính vào nhau. Thuật toán tìm các vị trí cắt có thể được thực hiện trong 2 bước sau: Bước 1: Ta cắt từ thành một ký tự dựa vào khoảng trắng giữa các ký tự. Khoảng trắng được chọn làm vị trí đặt nhát cắt. Bước 2: Sau bước 1 thì các ký tự thu được (nằm giữa 2 vị trí cắt) có thể không thật sự là một ký tự (vì có thể 2 ký tự dính nhau). Do vậy đối với các ký tự thu được ta xét xem liệu nó có thể là hai từ dính lại với nhau hay không, nếu có thì sẽ thực sử dụng Histrogram theo chiều dọc với một ngưỡng threshold để xác định các vị trí cắt không chính xác. (Tại các đường dọc trong Histogram, nếu số điểm đen < threshold thì sẽ coi đó là một vị trí cắt). Để xác định xem liệu một ảnh ký tự thu được (nằm giữa hai vị trí cắt) có thể là do nhiều ký tự dính vào nhau hay không, chúng tôi đưa ra giải pháp đó là xác định thành phần liên thông lớn nhất trong ký tự này, nếu như nó có bề rộng > bề cao thì nó sẽ có khả năng là do 2 ký tự dính vào nhau. Tuy nhiên với cách này thì ký tự “m” có thể bị cắt làm đôi (vì bề rộng > bề cao) nhưng chúng ta chấp nhận điều đó. Và nó sẽ được xử lý ở trong bộ nhận dạng. Chương 4: Trích chọn đặc trưng Bùi Thế Hân 20 Chương 4 Trích chọn đặc trưng 4.1 Khái niệm cơ bản 4.1.1 Đặc trưng ảnh – Image Features Đặc trưng ảnh là tập hợp các thuộc tính, các đặc điểm nổi bật có trong một ảnh. Đặc trưng của ảnh chia làm hai loại: Đặc trưng mang tính tự nhiên và đặc trưng nhân tạo. Các đặc trưng mang tính tự nhiên: nghĩa là các đặc trưng mà con người có thể cảm nhận được một cách thông thường, qua các giác quan. Còn các đặc trưng nhân tạo theo nghĩa nó thường được tạo ra thông qua các thao tác trên ảnh. 4.1.2 Trích chọn đặc trưng – Feature Extraction Các đặc trưng chúng ta làm việc ở đây là các đặc trưng mang tính nhân tạo. Trích chọn đặc trưng là việc tìm và chọn ra các đặc trưng đặc thù của mỗi ảnh. Vector đặc trưng: Các đặc trưng được dùng để miêu tả ảnh sau quá trình trích chọn đặc trưng được gọi là vector đặc trưng của ảnh. Không gian đặc trưng: Tập hợp các khả năng có thể có của vector đặc trưng được gọi là không gian đặc trưng của ảnh. 4.2 Vai trò của trích chọn đặc trưng Trích chọn đặc trưng là bước cung cấp đầu vào trực tiếp cho hệ nhận dang. Đầu vào các chính xác thì nó giúp cho hệ nhận dạng của chúng ta làm việc chính Chương 4: Trích chọn đặc trưng Bùi Thế Hân 21 xác hơn. Như vậy ta có thể nói rằng vai trò của trích chọn đặc trưng là khá quan trọng, việc trich chọn đặc trưng phải đạt được một số yêu cầu sau đây: 1. Mục tiêu đầu tiên của trích chọn đặc trưng là chúng ta phải trích chọn được những đặc trưng tốt. Đến đây câu hỏi được đặt ra thế nào là đặc trưng tốt. “Đặc trưng tốt là những đặc trưng mà giá trị của các đặc trưng này là giống nhau với những đối tượng thuộc cùng một lớp và rất khác so đối với những đối tượng thuộc các lớp khác”. Ta thấy rằng trong một bức ảnh có rất nhiều đặc trưng, nhưng không phải là đặc trưng nào cũng là đặc trưng tốt. Nên chúng ta phải lựa chọn đặc trưng tốt mang nhiều thông tin hữu ích trong việc phân lớp. Chứ không phải chọn toàn bộ các đặc trưng như vậy sẽ làm mất thời gian, thậm chí còn ảnh hưởng đến bộ nhận dạng. 2. Trên thực tế, trong mỗi bức ảnh đầu vào thường chứa nhiễu. Nên khi trích chọn đặc trưng của ảnh chúng ta thường lấy đặc trưng của ảnh là những điểm biên. Vì các điểm biên là nơi tập trung các thông tin quan trọng nhất có trong ảnh. Như vậy yếu tố nhiễu đã được giảm bớt mặt khác các thông tin quan trọng có trong ảnh vẫn được bảo tồn. 3. Thực hiện trích chọn đặc trưng không nhất thiết phải thực hiện trên các ảnh nhị phân. Mà ta có thể thực hiện trên các ảnh đa mức xám, ta có thể trích chọn được nhiều thông tin hơn. 4.3 Một số phương pháp trích chọn đặc trưng Trong một ảnh có rất nhiều loại đặc trưng: đặc trưng về hướng, về cấu trúc và về tính lồi lõm. Vì vậy cũng có rất nhiều phương pháp trích chọn đặc trưng ảnh khác nhau như trích chọn đặc trưng theo hướng hình học, theo cấu trúc, theo tính lồi lõm,…. và một số phương pháp tổng hợp khác như GSC, Zernike moments, Karhunen Loeve Transformation, …..Tuy vậy luận văn này chúng tôi đã sử dụng mô đun nhận dạng có sẵn để kết nối thành hệ thống nhận dạng hoàn chỉnh, trong đó mô đun này sử dụng phương pháp GSC để trích chọn đặc trưng. Nên chúng tôi chỉ trình bày lý thuyết của phương pháp GSC. 4.3.1 Phương pháp trích chọn đặc trưng GSC Chương 4: Trích chọn đặc trưng Bùi Thế Hân 22 Phương pháp GSC được nêu ra bởi nhóm nghiên cứu của J.Favata, V.Govindaraju và S.N.Srihari ở trung tâm nghiên cứu về nhận dạng và phân tích ảnh của trường đại học tổng hợp New York, Hoa Kỳ. Phương pháp GSC là tổng hợp của 3 phương pháp trích chọn đặc trưng theo hướng, theo cấu trúc và theo tính lồi lõm. Do vậy, nó có khả năng thể hiện ảnh trên nhiều mức độ, từ mức độ thấp (theo hướng), tới mức độ cao (theo tính lồi lõm). Phương pháp này tỏ ra rất hiệu quả với loại bài toán nhận dạng khi số mẫu đầu vào là đa dạng do vậy rất phù hợp khi áp dụng vào bài toán nhận dạng chữ tiếng Việt. Dựa trên sự kết hợp giữa phương pháp trích chọn đặc trưng GSC và thuật toán nhận dạng là mạng Neural. Nhóm tác giả trên đã xây dựng thực tế hệ thống chuyên nhận dạng các địa chỉ thư ở bưu điện ở Mỹ và cho kết quả khá khả quan 97%. 4.3.1 Trích chọn đặc trưng theo hướng hình học Phương pháp trích chọn đặc trưng theo hướng hình học là phương pháp trích chọn ra các đặc trưng về hướng tại các điểm biên ảnh. Yếu tố cơ bản nhất của trích chọn đặc trưng theo hướng hình học là tìm tần suất xuất hiện theo hướng của điểm biên ảnh trong một vùng nhất định. Phương pháp trích chọn đặc trưng theo hướng sử dụng véc tơ Gradient để xác định hướng của các điểm ảnh. 4.3.1.1 Khái niệm công thức tính vector gradient Vector gradient: Gradient là một vector có các thành phần biểu thị tốc độ thay đổi giá trị điểm ảnh theo hai hướng x và y. Với ảnh có giá trị mức xám của các điểm ảnh được biểu diễn bởi hàm f(x,y) thì vector gradient tại điểm có tọa độ (x,y) được tính như trong công thức (1.3.1): f =       Gy Gx =                 y f x f (1.3.1) Biên độ của vector gradient tại điểm (x,y) được tính bởi công thức: r(x,y) = mag (f) = [ 22 yx GG  ] 1/2 (1.3.2) Chương 4: Trích chọn đặc trưng Bùi Thế Hân 23 Hướng của vector gradient tại điểm (x,y) được tính bởi công thức:  (x,y) = tan )(1 x y G G  (1.3.3) Khi tại vị trí (x,y) của ảnh là một điểm biên ảnh thì hướng của vector gradient tại điểm ảnh đó được coi là hướng của biên ảnh tại vị trí (x,y). 4.3.1.2 Các bước cơ bản của phương pháp trích chọn đặc theo hướng Bước 1: Tìm hình bao của ảnh đầu vào và bao ảnh bởi hình bao này. Tác dụng của việc bao ảnh là loại bỏ khoảng trắng xung quanh phần ảnh mang thông tin thực sự nhằm loại bỏ các thông tin không cần thiết, đồng thời giảm thời gian tính toán của chương trình. Hình 4.1 Ảnh ban đầu và ảnh sau khi được bao Bước 2: tính bản đồ Gradient về biên độ và hướng tại mỗi điểm ảnh theo toán tử Sobel. Cách tính bản đồ này như sau: Ảnh đầu vào được cho dưới dạng ma trận mức xám I(x,y) với kích thước D1*D2. Mặt nạ của toán tử Sobel theo tọa độ X (nằm ngang) và tọa độ Y (thẳng đứng) được biểu diễn bởi hai ma trận trong hình 2.2: Hình 4.2 Mặt nạ Sobel theo hai hướng X và Y Với điểm ảnh có toạ độ (i, j), ta quan tâm đến giá trị mức xám tại điểm ảnh này và 8 điểm lân cận nó, các giá trị này được cho bởi ma trận I. Chương 4: Trích chọn đặc trưng Bùi Thế Hân 24 Các vector thành phần SX và GY của vector gradient tại điểm ảnh có tọa độ (i, j) khi đó sẽ được tính dựa trên mặt nạ của toán tử Sobel theo hướng X và hướng Y như sau: GX(i, j) = I (i - 1, j + 1) + 2I (i, j + 1) + I (i + 1, J + 1) - - I (i - 1, j - 1) - 2I (i, j - 1) - I (i + 1, J - 1) (1.3.4) SY(i, j) = I (i - 1, j - 1) + 2I (i - 1, j) + I (i - 1, J + 1) - - I (i + 1, j - 1) - 2I (i + 1, j) - I (i + 1, J + 1) (1.3.5) Sau khi tính được GX, GY ta tính biên độ và hướng của vector gradient tại điểm ảnh này theo công thức: Biên độ: Gradient_Manitude r(i, j) = ),(),( 22 jiGjiG YX  (1.3.6) Hướng: Gradient_Direction  (i,j) = tan-1 ),( ),( jiS jiS X Y (1.3.7) Từ đó, ta xây dựng bản đồ biên độ và bản đồ hướng của ảnh tương ứng là tập hợp biên độ và hướng của vector gradient tại tất cả các điểm ảnh. Bước 3: Từ bản đồ biên độ, ta tìm các điểm biên của ảnh bằng cách chọn một ngưỡng θ, và xét r(i, j). Nếu r(i, j) > θ thì điểm ảnh tại (i, j) là điểm biên. Bước 4: Xác định các điểm biên và lượng tử hướng của chúng về 12 giá trị: 0….tương ứng với 360 độ. Bước 5: sau khi tính được bản đồ biên độ và bản đồ hướng của ảnh, chia ảnh thành 4*4 phần bằng nhau. Với mỗi phần ảnh k (k = 0…15) ta làm như sau: Dựa vào bản đồ biên độ và bản đồ hướng để tính tổng số điểm biên có giá trị hướng lần lượt là 0, …, 11. Giả sử thu được bộ 12 giá trị ai với i = 0…11 và ai là tổng số điểm biên có giá trị hướng bằng i. Với ngưỡng η được chọn trước (áp dụng cho tất cả các phần của ảnh) ta xác định lại giá trị ai như sau: nếu ai > η thì ai = 1; ngược lại ai = 0; Kết quả: phần ảnh k sẽ có 12 bit đặc trưng có giá trị 0 hoặc 1 (tương ứng với các giá trị ai) thể hiện các đặc trưng về hướng của các điểm biên trong phần ảnh này. Chương 4: Trích chọn đặc trưng Bùi Thế Hân 25 Như vậy, số đặc trưng theo hướng của toàn bộ ảnh sẽ là: 4*4*12 = 192 và được thể hiện dưới dạng bit nhị phân (0 hoặc 1). 4.3.2 Trích chọn đặc trưng theo cấu trúc Đặc trưng về cấu trúc thể hiện vùng ảnh đó có dạng một đường thẳng theo phương ngang, đứng, đường chéo đi lên hoặc đi xuống, hay là một góc nào đó. Sau đây là thuật toán trích chọn đặc trưng theo cấu trúc: INPUT :Ảnh đầu vào, Giá trị ngưỡng threshold OUTPUT : Vector đặc trưng của ảnh (192 bit) PROCESS : 1. Xác định hình bao ảnh 2. Tính bản đồ Gradient về biên độ và hướng tại mỗi điểm ảnh 3. Xác định các điểm biên và lượng tử hướng của chúng về 12 giá trị: 0…11 4. Chia ảnh làm 4*4 phần bằng nhau 5. Trong mỗi phần:  Tính 12 giá trị ai tương ứng là tổng số điểm biên thỏa mãn lần lượt 12 luật: luật 0…11.  Nếu ai > threshold thì ai = 1, ngược lại ai = 0 6. Xác định vector đặc trưng là tập hợp các giá trị ai (i = 0…11) trong tất cả các phần. Bảng 4.1 Các luật về đặc trưng theo cấu trúc của điểm ảnh Luật Kiểu của ảnh Điều kiện TM Luật Hình vẽ minh hoạ Chú giải Luật 1 Đường thẳng nằm ngang N0 (2,3,4) N4 (2,3,4) N0, X, N4 tạo thành đường nằm ngang Chương 4: Trích chọn đặc trưng Bùi Thế Hân 26 loại 1 Luật 2 Đường thẳng nằm ngang loại 2 N0 (8, 9, 10) N4 (8, 9, 10) N0, X, N4 tạo thành đường nằm ngang Luật 3 Đường thẳng đứng loại 1 N2 (5, 6, 7) N6 (5, 6, 7) N2, X, N6 tạo thành đường thẳng đứng Luật 4 Đường thẳng đứng loại 2 N2 (1, 0, 11) N6 (1, 0, 11) N2, X, N6 tạo thành đường thẳng đứng Luật 5 Đường chéo đi lên loại 1 N5 (4, 5, 6) N1 (4, 5, 6) N1, X, N5 tạo thành đường chéo đi lên Luật 6 Đường chéo đi lên loại 2 N5 (0, 11, 10) N1 (0, 11, 10) N1, X, N5 tạo thành đường chéo đi lên Chương 4: Trích chọn đặc trưng Bùi Thế Hân 27 Luật 7 Đường chéo đi xuống loại 1 N3 (3, 2, 1) N7 (3, 2, 1) N3, X, N7 tạo thành đường chéo đi xuống Luật 8 Đường chéo đi xuống loại 2 N3 (7, 8, 9) N7 (7, 8, 9) N3, X, N7 tạo thành đường chéo đi xuống Luật 9 Góc loại 1 N2 (5, 6, 7) N0 (8, 9, 10) N2, X, N0 tạo thành góc vuông loại 1 Luật 10 Góc loại 2 N6 (5, 6, 7) N0 (2, 3, 4) N0, X, N6 tạo thành góc vuông loại 2 Luật 11 Góc loại 3 N4 (8, 9, 10) N2 (1, 0, 11) N2, X, N4 tạo thành góc vuông loại 3 Luật 12 Góc loại 4 N4 (4, 3, 2) N6 (1, 0, 11) N6, X, N4 tạo thành góc vuông loại 4 Kết quả: mỗi phần ảnh sẽ được đặc trưng bởi 12 bit có giá trị 0 hoặc 1 thể hiện cấu trúc của phần ảnh này có bao nhiêu xu hướng là những đường thẳng hay góc được liệt kê trong bảng 2.1 Như vậy, sau khi thực hiện với 4*4 phần của ảnh đầu vào ta sẽ thu được 4*4*12 tức bằng 192 bit đặc trưng về cấu trúc cho toàn bộ ảnh. 4.3.3 Trích chọn đặc trưng theo tính lồi lõm Chương 4: Trích chọn đặc trưng Bùi Thế Hân 28 Đặc trưng theo tính lỗi lõm của ảnh là tìm ra những đặc trưng dựa trên nhiều điểm ảnh với mục tiêu tìm ra những vùng lồi lõm và những lỗ trống trong một bức ảnh đầu vào. Ảnh ban đầu được chia thành 4*4 phần bằng nhau, với ứng với mỗi phần ta sẽ tìm ra 8 đặc trưng đặc thù của nó. 8 đặc trưng này bao gồm: 1. Đặc trưng về mật độ điểm đen. 2. Đặc trưng thể hiện ảnh phần ảnh này là một nét lớn theo chiều thẳng đứng 3. Đặc trưng thể hiện ảnh phần ảnh này là một nét lớn theo chiều ngang 4. Năm đặc trưng thể hiện tính lồi lõm hay là lỗ trống có trong phần ảnh này. 4.3.3.1Tìm đặc trưng về mật độ điểm đen: Để tính đặc trưng này, trước hết ta tìm tổng số điểm đen có trong mỗi phần ảnh. So sánh tổng số điểm đen này với một ngưỡng θ được chọn trước : nếu lớn hơn thì đặc trưng này có giá trị bằng 1, ngược lại có giá trị bằng 0. 4.3.3.2 Đặc trưng thể hiện phần ảnh là nét lớn Để tìm đặc trưng thể hiện phần ảnh là nét lớn theo chiều ngang hay chiều thẳng đứng ta làm như sau:  Gọi C1 là chiều dài của đoạn thẳng dài nhất theo phương ngang chứa các điểm đen liên tục (toàn bộ các điểm trong đoạn thẳng đều là điểm đen).  R1 là chiều dài của đoạn thẳng dài nhất theo phương thẳng đứng chứa các điểm ảnh liên tục (toàn bộ các điểm trogn đoạn thẳng đều là điểm đen).  Nếu C1 < R1 * 0.75 thì vùng này là nét lớn theo chiều thẳng đứng. Từ đó, thiết lập đặc trưng về nét lớn theo chiều thẳng đứng bằng 1, và đặc trưng về nét lớn theo chiều ngang bằng 0. Chương 4: Trích chọn đặc trưng Bùi Thế Hân 29  Nếu C1 > R1 * 1.5 thì vùng này là nét lớn theo chiều ngang. Từ đó, thiết lập đặc trưng về nét lớn theo chiều thẳng đứng bằng 0, và đặc trưng về nét lớn theo chiều ngang bằng 1. 4.3.3.3 Tìm đặc trưng thể hiện tính lồi lõm hay lỗ trống của ảnh: Ta quy ước như sau: U là mặt lõm quay về phía trên, D là mặt lõm xuống phía dưới, L là mặt lõm sang bên trái, R là mặt lõm quay sang bên phải, H là lỗ trống. Ý tưởng để tìm ra các đặc trưng này như sau: Với mỗi điểm ảnh (ngoại trừ các điểm đen) trong vùng, vẽ 8 tia xuất phát từ điểm ảnh đó lần lượt hợp với trục hoành các góc 0o, 45o, 90o,…, 270o, 315o. Các tia này chỉ có thể tiếp xúc với điểm đen trong ảnh hoặc sẽ chạm vào mép ảnh. Tại điểm ảnh đó, lỗ trống được phát hiện nếu cả 8 tia đều chạm vào điểm đen nằm trong ảnh. Vùng lõm hướng xuống phía dưới (D) được phát hiện nếu các tia có hướng 0o, 45o, 90o, 135o, 180o chạm vào điểm đen nằm trong ảnh còn các tia có hướng 225o, 270o, 315o chạm vào mép của ảnh. Việc phát hiện ra các vùng lồi lõm khác được thực hiện tương tự. Về thực chất, việc các tia chạm vào điểm đen nằm trong ảnh hay chạm vào tương đương với việc tổng số các điểm đen nằm trên tia đó lớn hơn hoặc bằng 0. Do việc tính toán là đơn giản nên thuật toán tính tổng số các điểm đen nằm trên mỗi tia không được miêu tả chi tiết ở đây. Với mỗi 5 đặc trưng nêu trên (U, D, L, R, H), ta tính tổng số điểm ảnh thỏa mãn có các đặc trưng đó. Giả sử thu được 5 giá trị ai với i = 1…5 và ai là tổng số điểm ảnh thỏa mãn. Với ngưỡng θ được chọn trước (áp dụng cho tất cả các phần của ảnh) ta xác định lại giá trị ai như sau: nếu ai > θ thì ai = 1; ngược lại ai = 0. Như vậy, với phương pháp trích chọn đặc trưng ảnh theo tính lồi lõm, mỗi phần ảnh có 8 đặc trưng nên số đặc trưng của toàn bộ ảnh là 4*4*8 = 128. Chương 5: Phân lớp và mô hình học máy Bùi Thế Hân 30 Chương 5: Phân lớp và mô hình học máy Vấn đề quan trọng nhất của nhận dạng tiếng Việt: Với mỗi hình ảnh kí tự đưa vào mô hình nhận dạng của chúng ta phải trả lời được câu hỏi đây là kí tự gì. Hay nói cách khác hình ảnh kí tự này thuộc lớp nào? Để thực hiện được việc này chúng ta sử dụng véc tơ đặc trưng x = (x1, x2, …, xm) được lấy ra từ giai đoạn trích chọn đặc trưng, làm đầu vào cho mô hình nhận dạng. Có rất nhiều mô hình nhận dạng được dùng hiện nay như mạng neural, Mô hình học máy Entropy, Hidden Markov model (HMM) . Nhưng trong khuôn khổ của luận văn chúng tôi chỉ đi vào nghiên cứu và ứng dụng mô hình mạng neuron cho bài toán nhận dạng kí tự tiếng Việt của mình. 5.1 Cấu trúc hoạt động của mạng neuron 5.1.1 Cấu trúc và hoạt động của một neuron Một neuron nhân tạo là một đơn vị tính toán hay đơn vị xử lý thông tin cơ sở cho hoạt động của môt mạng neuron. Sơ đồ khối của hình 1.2 chỉ ra mô hình của một neuron nhân tạo. ở đây, chúng ta xác định ba thành phần cơ bản của một mô hình neuron: 1. Một tập hợp các synapse hay các kết nối, mà mỗi một trong chúng được đặc trưng bởi một trọng số của riêng nó. Tức là một tín hiệu xj tại đầu vào của synapse j nối với neuron k sẽ được nhân với trọng số synapse wkj. ở đó k là chỉ số của neuron tại đầu ra của synapse đang xét, còn j chỉ điểm đầu vào của synapse. Các trọng số synapse cuả một neuron nhân tạo có thể nhận cả các giá trị âm và các giá trị dương. Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 31 2. Một bộ cộng để tính tổng các tín hiệu đầu vào của neuron, đã được nhân với các trọng số synapse tương ứng; phép toán được mô tả ở đây tạo nên một bộ tổ hợp tuyến tính. 3. Một hàm kích hoạt (activation function) để giới hạn biên độ đầu ra của neuron. Hàm kích hoạt cũng được xem xét như là một hàm nén; nó nén (giới hạn) phạm vi biên độ cho phép của tín hiệu đầu ra trong một khoảng giá trị hữu hạn. Mô hình neuron trong hình 1.2 còn bao gồm một hệ số hiệu chỉnh tác động từ bên ngoài, bk. Hệ số hiệu chỉnh bk có tác dụng tăng lên hoặc giảm đi đầu vào thực của hàm kích hoạt, tuỳ theo nó dương hay âm. Hình 5.1: Mố hình phi tuyến của một neuron 5.1.2 Cấu trúc và hoạt động của mạng neuron Hình III.2.2 là một cấu trúc mạng neuron phổ biến. Mạng nơ ron này gồm 3 lớp, gọi là lớp vào, lớp khuất và lớp ra. Mỗi lớp gồm có một hay nhiều lớp, thể hiện trên biểu đồ bởi các vòng tròn nhỏ . Đường thẳng giữa các nút minh hoạ luồng thông tin từ nút này tới nút kế tiếp. Trong kiểu mạng neuron xác định này, luồng thông tin chỉ đi từ đầu vào tới đầu ra ( từ trái sang phải ). Các kiểu mạng neuron khác có nhiều kết nối phức tạp hơn , như các đường phản hồi. Các nốt của lớp vào là bị động , nghĩa là chúng không thay đổi dữ liệu. Chúng nhận các giá trị của dữ kiện vào và nhận giá trị với các bội số ra. Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 32 Hình 5-3 Cấu trúc chung của mạng neuron Các nút của lớp khuất và lớp ra là chủ động . Nghĩa là chúng có thể thay đổi dữ liệu như trên Hình III.2.1. Các biến : X11,X12…X115 giữ các giá trị để đánh giá. Lấy ví dụ, chúng có thể là các giá trị pixel từ ảnh, các mẫu từ tín hiêụ audio, giá thị trường chứng khoán .... Chúng có thể là cả các thuật toán khác giống như phân loại xác định ung thư, bán kính, độ sáng, góc cạnh... Mỗi giá trị của lớp vào được nhân đôi và được gửi cho tất cả các nút khuất. Nó được gọi là cấu trúc kết nối liền. Như hình III.2.1 giá trị đưa vào nút khuất được nhân với weight, số được định trước trong chương trình.Các giá trị vào qua weight sau đó được cộng vào để tạo ra các số đơn. Chúng được chỉ ra trên hình bởi biểu tượng ∑. Trước khi rời khỏi nút, số này được đi qua các hàm toán học phi tuyến sigmoid. Nó là đường cong hình chữ "s" giới hạn ngõ ra của nút. Đầu vào cho sigmoid là các giá trị giữa -∞ và +∞, khi các giá trị ra chỉ có thể giữa 0 và 1.Giá trị Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 33 ra từ lớp khuất được tái hiện trên biểu đồ luồng (III.2-1) bởi các biến :X21,X22,X23 và X24. Vừa như truớc đó, mỗi giá trị này được nhân đôi và đặt vào lớp kế tiếp. Các nút chủ động của lớp ra kết hợp và chỉnh sửa dữ liệu để tạo ra 2 giá trị ra trong mạng X31 và X32. Mạng neuron có thể có số lớp bất kỳ, và số nút bất kỳ trên mỗi lớp. Hầu hết ứng dụng sử dụng cấu trúc 3 lớp với tối đa vài trăm nút. Lớp khuất thường có cỡ khoảng 10% lớp vào. Trong ứng dụng xác định mục tiêu, lớp ra thường chỉ cần một nút. Ngõ ra của nút này thường có ngưỡng để đưa ra chỉ số dương hay âm chỉ sự có mặt hay vắng mặt của mục tiêu trong dữ liệu truyền vào 5.1.3 Hàm truyền Có rất nhiều hàm truyền có thể dùng trong các mạng neuron. Việc lựa chọn hàm truyền phù hợp với bài toán thường được tiến hành qua thực nghiệm. Trong bảng dưới đây, chúng ta dùng công thức y = f(x) để biểu diễn hàm truyền. Bảng 5-2. Một số hàm truyền Tên hàm truyền Đồ thị Miền giá trị Ứng dụng Symmetrical Hard limit (hardlim) y =    1 1 Sử dụng ở tầng ra của mạng neuron trong các bài toán phân loại hai lớp Linear (purelin) y = x Sử dụng trong mạng ADALINE Hàm Saturating Linear (satlin) y =      1 0 x với 0≤x≤1 Sử dụng trong mạng ADALINE với x<0 với x>1 với x<0 với x≥1 Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 34 Log-Sigmoid (sigmoid) y = ne1 1 Sử dụng trong mạng neuron nhiều tầng 5.2 Quá trình huấn luyện mạng và các thuật toán học mạng 5.2.1 Mạng neuron và bài toán phân loại mẫu Chún ta có thể nói nhiệm vụ của các hệ nhận dạng trong các bài toán nhận dạng chính là phân loại mẫu. Có nghĩa là từ một mẫu vào ban đầu, hệ nhận dạng cần chỉ ra nó thuộc về lớp phân loại nào. Bên cạnh bài toán nhận dạng chữ in tiếng Việt, nhiều bài toán nhận dạng khác cũng có thể coi là bài toán phân loại mẫu như nhận dạng dấu vân tay dùng làm mã khoá trong các hệ an ninh, nhận dạng khuôn mặt hay tiếng nói, … Câu hỏi đặt ra đối với chúng ta là sử dụng mô hình nào cho các hệ nhận dạng này để nó không chỉ phân loại được những mẫu đã học mà còn có thể tổng quát hoá để phân loại những mẫu chưa được học? 5.2.2 Đặc trưng của mạng neuron Mạng neuron có hai đặc trưng cơ bản: khả năng học hỏi và khái quát hóa. Khả năng học hỏi: là khả năng mà mạng neuron có thể phân loại chính xác những mẫu đã được huấn luyện (những mẫu trong tập training). Khái quát hóa: là khả năng mạng có thể nhận biết, phân loại được nhưng mẫu chưa được huấn luyện. Ví dụ như trong nhận dạng chữ in tiếng Việt: Khi ta đưa một mẫu chữ ‘a’, chữ này có nhiễu tức là chữ ‘a’ này chưa được huấn luyện. Mà mạng neuron vẫn có thể phân loại vào lớp chữ ‘a’. Các khả năng này có được là do việc hiệu chỉnh và cập nhật bộ tham số mạng trong suốt quá trình huấn luyện. 5.2.3 Các phương pháp huấn luyện mạng Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 35 Huấn luyện mạng: là quá trình đào tạo mạng sao cho khả năng học và tổng quát hoá mà nó đạt được là cao nhất. Bản chất của việc huấn luyện cho mạng là ta điều chỉnh các trọng số sao cho phù hợp để có được kết quả nhận dạng chính xác nhất. Trọng số này có thể điều chỉnh cập nhật trong suốt quá trình huấn luyện của mạng neuron. Học có giám sát: Trong học có giám sát ta được cho trước một tập ví dụ: gồm các cặp và mục tiêu là tìm một hàm f (trong lớp các hàm được phép) khới với các ví dụ. Nói cách khác, ta muốn tìm ánh xạ mà dữ liệu đầu vào đã hàm ý, với hàm chi phí đo độ không khớp giữa ánh xạ của ta và dữ liệu. Học không có giám sát: Trong học không có giám sát, ta được cho trước một số dữ liệu x, và hàm chi phí cần được cực tiểu hóa có thể là một hàm bất kỳ của dữ liệu x và đầu ra của mạng, f. Hàm chi phí được quyết định bởi phát biểu của bài toán. Học tăng cường: Trong học tăng cường, dữ liệu x thường không được cho trước mà được tạo ra trong quá trình một agent tương tác với môi trường. Tại mỗi thời điểm t, agent thực hiện hành động yt và môi trường tạo một quan sát xt và một chi phí tức thời ct, theo một quy trình động nào đó (thường là không được biết). Mục tiêu là tìm một sách lược lựa chọn hành động để cực tiểu hóa một chi phí dài hạn nào đó, nghĩa là chi phí tích lũy mong đợi. Quy trình động của môi trường và chi phí dài hạn cho mỗi sách lược thường không được biết, nhưng có thể ước lượng được. Mạng neuron nhân tạo thường được dùng trong học tăng cường như là một phần của thuật toán toàn cục. Các bài toán thường được giải quyết bằng học tăng cường là các bài toán điều khiển, trò chơi, và các nhiệm vụ quyết định tuần tự (sequential decision making) khác. 5.2.4 Mạng lan truyền ngược nhiều tầng (Back-propagation Neural Network) Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 36 5.2.4.1 Kiến trúc mạng Hình 5.3 Mạng neuron hai lớp Các nơ ron lớp thứ t được nối đầy đủ với các nơ ron lớp thứ t+1. Trong nhiều ứng dụng thực tế, để đơn giản, người ta thường sử dụng mạng có một lớp ẩn, số nơ ron trong lớp ẩn được xác định dựa trên kinh nghiệm, hoặc dựa trên các kỹ thuật tìm kiếm khác nhau 5.2.4.2 Huấn luyện mạng Quá trình huấn luyện mạng được trình bày ở đây là quá trình học có giám sát với tập mẫu {(Xs, Ys)}. Thủ tục học có thể tóm lược như sau: Mỗi khi đưa một mẫu Xs = (x1 , ..., xn) vào mạng, ta thực hiện các công việc sau: - Lan truyền mẫu Xs qua mạng để có outs = Tinh (Xs, NN) - Tính sai số Errs của mạng dựa trên sai lệch outs - Ys - Hiệu chỉnh các trọng số liên kết nơ ron dẫn tới lớp ra Wij từ nơ ron j tại lớp ẩn cuối cùng tới nơ ron i tại lớp ra: wij = wij +  . aj . i, (15) ở đây:  là hệ số học, aj là đầu ra của nơ ron j, i là sai số mà nơ ron i ở lớp ra phải chịu trách nhiệm, được xác định theo công thức: Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 37 i = erri g'(Neti) (16) với erri là sai số thành phần thứ i trong Errs , Neti là tổng thông tin vào có trong số của nơ ron thứ i (Neti=wij.aj) và g'(.) là đạo hàm của hàm kích hoạt g được dùng trong các nơ ron. - Hiệu chỉnh các trọng số liên kết nơ ron Wjk dẫn tới tất cả lớp ẩn từ nơ ron thứ k sang nơ ron j (các lớp ẩn được xét từ dưới lên) : Tính tổng sai số tại nơ ron j phải chịu trách nhiệm HiÖu chØnh träng sè wjk wjk = wjk + ak j (18) (trường hợp xét liên kết từ nơ ron vào thứ k sang nơ ron j trên lớp ẩn thứ nhất, ta có ak = Ik, chính là tín hiệu vào). Chú ý : a) Trường hợp xét hàm kích hoạt tại các nơ ron ta có hệ thức g'(x)=g(x)(1-g(x)). b) Từ các công thức (15), (18) ta có thể viết lại: wij = wij + wij , wjk = wjk + wjk , víi wij =  aj i vµ wjk =  ak j Trong các ứng dụng thực tế, người ta thường hiệu chỉnh wij theo nguyên tắc có chú ý đến thao tác trước đó. Do vậy: wij(mới) =  aj i + wij(cũ), ở đây  là hệ số quán tính. Quá trình huấn luyện mạng cần chú ý tới các yếu tố sau:  Các trọng số ban đầu wij được gán các giá trị ngẫu nhiên, nhỏ  Lựa chọn các hệ số học  và hệ số quán tính  sao cho  +  1, với  không lớn hơn  quá nhiều.  i iij w)j(Netg'j  (17) xe xg   1 1 )( Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 38  Các tín hiệu vào, ra nên được định cỡ chỉ nằm trong khoảng [0,1]. Các nghiên cứu thực nghiệm chỉ ra rằng nên ở trong khoảng [0.2,0.8]. 5.2.4.3 SỬ DỤNG MẠNG Giả sử đã huấn luyện mạng như trên hình 7.23 với tập mẫu {(Xs,Ys)} để được ma trận trọng số W. Quá trình lan truyền trong mạng một vectơ tín hiệu vào X=(x1,x2,x3) được cho bởi: out = g(w64 a4 + w 65 a5) = g(w 64 g(w 41 x1 + w 42 x2 + w 43 x3) + w 65 g(w 51 x1 + w 52 x2 + w 53 x3)) = F ( X , W) Kh¶ n¨ng tÝnh to¸n cña m¹ng nhiÒu líp Víi mét líp Èn, m¹ng cã thÓ tÝnh to¸n xÊp xØ mét hµm liªn tôc bÊt kú ®èi víi c¸c biÕn t­¬ng øng lµ c¸c tÝn hiÖu ®Çu vµo. Víi hai líp Èn, m¹ng cã thÓ tÝnh to¸n xÊp xØ mét hµm bÊt kú. Tuy vËy, sè n¬ ron trong c¸c líp Èn cã thÓ t¨ng theo hµm mò ®èi víi sè ®Çu vµo vµ cho ®Õn nay vÉn ch­a cã nh÷ng c¬ së lý luËn ®Çy ®ñ ®Ó kh¶o s¸t hä c¸c hµm cã thÓ xÊp xØ nhê c¸c m¹ng nhiÒu líp. 5.3 Ứng dụng mô hình nhận dạng cho tiếng Việt 5.3.1 Khó khăn và giải pháp đề xuất cho nhận dạng kí tự Như chúng ta đã biết, chữ tiếng Việt là sự kết hợp giữa chữ cái Latinh và hệ thống dấu (sắc, huyền, hỏi, ngã, nặng). Khi chúng ta cắt các từ tiếng Việt viết thường ra thành các kí tự (chữ cái kèm theo dấu), ta sẽ thu được những nhóm kí tự sau: 18 kí tự có dấu bắt nguồn từ các chữ cái a, ă, â đó là: a, à, á, ã, ạ, ả, â, ầ, ấ, ẫ, ậ, ẩ, ă, ằ, ắ, ặ, ẳ, ẵ. (1) 12 kí tự có dấu bắt nguồn từ các chữ cái e, ê đó là: e, è, é, ẹ, ẽ, ẻ, ê, ề, ế, ệ, ể, ễ (2). 6 kí tự có dấu bắt nguồn từ chữ cái i là: i, í, ì, ị, ĩ, ỉ. (3) Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 39 6 kí tự có dấu bắt nguồn từ chữ cái y đó là: y, ỳ, ý, ỵ, ỹ, ỷ. (4) 18 kí tự có dấu bắt nguồn từ các chữ cái o, ô, ơ đó là: o, ò, ó, õ, ọ, ỏ, ô, ồ, ố, ộ, ỗ, ổ, ơ, ờ, ớ, ợ, ỡ, ở. (5) 12 kí tự có dấu bắt nguồn từ chữ các chữ cái u và ư đó là: u, ù, ú, ụ, ũ, ủ, ư, ừ, ứ, ự, ữ, ử. (6) 17 kí tự không dấu còn lại: b, c, d, đ, g, h, k, l, m, n, p, q, r, s, t, v, x. (7) Từ đặc điểm trên của chữ tiếng Việt, bên cạnh những khó khăn chung của bài toán nhận dạng chữ viết tay đã trình bày trong phần Giới thiệu, bài toán nhận dạng chữ viết tay tiếng Việt còn gặp những khó khăn sau: Số các kí tự tiếng Việt là rất lớn: 89 kí tự viết thường và 89 kí tự viết hoa chưa kể đến các chữ số và dấu câu. Nếu chỉ sử dụng hệ nhận dạng đơn thuần là nhận dạng một cấp (nhận dạng một lần) thì số các kí tự cần phân biệt là rất lớn, do vậy xác suất nhận dạng sai cũng sẽ cao. Tập hợp các kí tiếng Việt có thể chia thành bảy nhóm như ở trên, trong đó các nhóm (1), (2), (3), (4), (5) và (6) gồm các kí tự rất giống nhau, chúng chỉ khác nhau về dấu nên rất khó phân biệt. Có thể nói, bên cạnh độ lớn về số lượng kí tự, các nhóm kí tự gần giống nhau này là thách thức lớn nhất đối với các hệ nhận dạng chữ viết tay tiếng Việt. Nhận biết được những khó khăn này, chúng tôi đề xuất giải pháp như sau: Dùng hệ nhận dạng nhiều cấp (trước hết phân tập hợp kí tự thành các nhóm, mỗi nhóm gồm các kí tự gần giống nhau, sau đó nhận dạng các kí tự trong mỗi nhóm) nhằm giải quyết khó khăn về độ lớn của số lượng kí tự. Đối với mỗi kí tự ở đây chúng tôi đề xuất phương pháp chia kí tự thành 3 phần: Phần trên của kí tự (các dấu ), phần thân kí tự, phần dưới kí tự (dấu chấm). Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 40 Hình 5-4 : Hình ảnh kí tự được chia làm 3 phần. ở đây chúng ta nhận dạng 3 phần riêng biệt, sau đó sẽ ghép lại với nhau. Kết quả của các phép nhận dạng sẽ được kí tự nhận dạng hoàn chỉnh. Ví dụ “â:a:ạ”  ậ 5.3.2 Phân nhóm kí tự Trong phần thân gồm 29 kí tự trong đó có một số trường hợp có cấu tạo khá giống nhau như: d và đ; u và ư ...Ngoài ra còn có các trường hợp cấu tạo giống nhau giữa các kí tự với số, biểu tượng như ‘o’ và ‘0’; ‘1’ và ‘l’;’/’ và ‘\’,’|’. Trong mỗi nhóm chúng ta có thể trích chọn đặc trưng theo cách riêng. Trong nhóm ’/’ và ‘\’,’|’ để phân biệt được các kí tự ta phải sử dụng đến góc nghiêng của các kí tư thì mới có thể nhận biết được. Trong nhóm kí tự tương tự nhau chúng ta sẽ cắt kí tự thành nhiều phần và ta sẽ tiến hành trích chọn đặc trưng của các phần có thông tin hữu ích. Ví dụ như ‘u’ và ‘ư’ chúng ta sẽ tiến hành cắt kí tự làm đôi. Chỉ trích chọn đặc trưng của nửa kí tự có thông tin hữu ích. Hinh 5-5:ảnh gốc Chương 5:Phân lớp và mô hình học máy Bùi Thế Hân 41 Hình 5-6: Ảnh cắt Chương 6:Thực nghiệm Bùi Thế Hân 42 Chương 6 Thực nghiệm 6.1 Môi trường thực nghiệm Các chương trình được cài đặt bằng ngôn ngữ C# trên môi trường phát triển Visual Studio 2005 và được thử nghiệm trên hệ điều hành Windows XP SP2. 6.2 Thực nghiệm về phân đoạn ảnh 6.2.1 Tách dòng Điều kiện thực hiện: trong cài đặt thực nghiệm, chúng tôi xác định tham số minHeightLine = 7. Chúng tôi thực nghiệm phân tách 5 văn bản gồm 200 dòng. Các dòng tách sai trong trường hợp:  Vị trí tách dòng không đúng với vị trí thực tế của dòng đó trong văn bản.  Các dòng bị gộp với nhau tạo thành một dòng (hình 4.5). Hình 6.1: Minh họa tách dòng văn bản. Kết quả thực hiện: Tách dòng kết quả thực nghiệm chính xác 99%. Chương 6:Thực nghiệm Bùi Thế Hân 43 Số văn bản Số dòng Số dòng tách Chính xác Tính % 5 200 199 99 Bản 6.1 Kết quả thực nghiệm tách từ 6.2.3 Tách từ Điều kiện thực nghiệm: trong quá trình thực nghiệm, chúng tôi thử với các giá trị khác nhau của tham số k, và với k = 2.75 thì có cho kết quả tốt nhất, tách chính xác gần như tòan bộ văn bản. Hình 6.2: Minh họa cắt từ. Kết quả: Chúng tôi tiến hành tách từ trong 5 văn bản gồm 2200 từ. Độ chính xác cắt từ là: 99.2%. Một ví dụ về tách từ được minh họa như trong hình 4.6. Số văn bản Số từ Số từ tách chính xác 5 2200 1189 Bảng 6.2 Kết quả thực nghiệm tách từ 6.2.4 Tách ký tự Chúng tôi thực nghiệm việc tách kí tự với đầu vào là các từ đã được tách ở giai đoạn trên. Thì kết quả đạt được như sau: Chương 6:Thực nghiệm Bùi Thế Hân 44 Với những từ trong đó các kí tự tách rời nhau, thì độ chính xác của phép tách là rất cao (99.8%). Nhưng với nhưng từ các kí tự dính nhau thì không chính xác, chính vì vậy chúng tôi đã đưa ra nhiều kết quả cho các nhát cắt. 6.2.5 Thực nghiệm nhận dạng Chúng tôi thực nghiệm việc nhận dạng với đầu vào là các văn bản. Thì kết quả đạt được như sau: Số văn bản Số từ Số từ tách chính xác 5 2200 1189 Bảng 6.3 Kết quả thực nghiệm tách từ Chương 7:Kết Luận Bùi Thế Hân 45 Chương 7: Kết Luận Trong khóa luận này chúng tôi đã trình bày những lý thuyết cơ bản về phân đoạn ảnh, nghiên cứu và so sánh một số kỹ thuật phổ biến sử dụng trong phân đoạn ảnh cho nhận dạng. Đồng thời tôi cũng trình bày một cách khái quát về các phương pháp trích chọn đặc trưng và các mô hình học máy được áp dụng trong luận văn. Từ đó áp dụng vào bài toán nhận dạng chữ in tiếng Việt. Để nâng cao chất lượng trong quá trình phân đoạn ảnh nhằm tăng chất lượng tổng thể của hệ thống nhận dạng, chúng tôi đã đề xuất phương pháp văn bản thành các vùng,tách dòng dựa vào các phương pháp trực quan như đã trình bày ở trên. Kết quả thực nghiệm trên các văn bản chữ in thu được là rất khả quan với độ chính xác tại giai đoạn tách dòng là 99,2%, tại giai đoạn tách từ là 99,4%. Thực nghiệm trên văn bản chữ viết tay bước đầu cũng đem lại kết quả khả quan. Chúng tôi tiến hành ghép nối các modun để tạo thành một hệ thống nhận dạng, quá trình thực nghiệm thu được độ chính xác của hệ thống là 90.3%. Chúng tôi cũng đã xây dựng một ứng dụng nhận dạng văn bản chữ in tiếng Việt. Kết quả thu được cho thây, ứng dụng là có ích, có thể nhận dạng được các văn bản chữ in tiếng Việt với độ chính xác khá cao. Tuy nhiên vẫn tồn tại một số hạn chế chưa giải quyết được, đó là chưa giải quyết được khi các dòng các từ bị dính vào nhau ... Trong tương lai chúng tôi sẽ tiếp tục nghiên cứu và phát triển để nâng cao chất lượng hệ thống cả về độ chính xác và tốc độ. Đối với khó khăn khi cắt ký tự làm ba phần sẽ giải quyết theo hướng xác định các vị trí cắt có thể và tiến hành giống với quá trình tách ký tự. Qua đó mở rộng nghiên cứu và thực nghiệm trên các văn bản chữ viết tay tiếng Việt. Tài liệu tham khảo Bùi Thế Hân 46 Tài liệu tham khảo [1] 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, 1999. [2] Ngô Quốc Đạt , Luận văn “Tích hợp mô hình cho nhận dạng tiếng Việt” khoa CNTT Trường đại học Công Nghệ đại học QGHN năm 2008. [3] Hoàng Kiếm, Nguyễn Hồng Sơn, Đào Minh Sơn, “Ứng dụng mạng Nơron nhân tạo trong hệ thống xử lý biểu mẫu tự động”, Kỷ yếu hội nghị kỷ niệm 25 năm thành lập Viện Công Nghệ Thông Tin, 2001. [4] [5] Lakhmi C. Jain (Editor), Beatrice Lazzerini (Editor) Detection technique for Binary Document Images based on Hough transform, International journal of information technology, Volume 3 number 3 2006, ISSN 1305-2403 Knowledge-based-intelligent-techniques-in-character-recognition [6] Pattern Recognition with Neural Networks in C++.chm. CRC Press [7] H. Bunke (Editor), P. S. P. Wang (Editor) Handbook of Character Recognition and Document Image Analysis [8] Bahram Javidi (Author) Image Recognition and Classification [9] Stephen V. Rice (Author), George Nagy (Author), Thomas A. Nartker (Author) Optical Character Recognition: An Illustrated Guide to the Frontier (The Springer International Series in Engineering and Computer Science) [10] Oliveira Luiz S., Robert Sabourin, Flavio Bortolozzi and Ching Y.Suen. Automatic Recognition of Handwritten Numerical Strings: A Recognition and Verfication Strategy. [11] Francis T. S. Yu (Editor), Suganda Jutamulia (Editor) In Stock Optical Pattern Recognition [12] ng118