Ứng dụng mạng Noron nhân tạo SOM cho bài toán nhận dạng kí tự - Lê Anh Tú

Lê Anh Tú và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 55 - 60 55 ỨNG DỤNG MẠNG NORON NHÂN TẠO SOM CHO BÀI TOÁN NHẬN DẠNG KÍ TỰ Lê Anh Tú1*, Nguyễn Quang Hoan2, Lê Sơn Thái1 1Trường Đại học Công nghệ thông tin và truyền thông – ĐH Thái Nguyên 2Học viện Công nghệ Bưu chính Viễn thông TÓM TẮT Khi áp dụng mạng noron SOM cho bài toán nhận dạng nói chung và nhận dạng ký tự nói riêng, chúng tôi nhận thấy mạng noron SOM có nhiều triển vọng trong vấn đề này. Tuy nhiên, với mỗi dạng dữ liệu vào thì vector trọng số và hàm khoảng cách đánh giá độ phi tương tự của dữ liệu cần được thiết kế phù hợp để mạng hoạt động hiệu quả hơn. Trong bài báo này chúng tôi đề xuất một cấu trúc trọng số mới của mạng noron SOM để biểu diễn các đặc trưng hình dạng của đối tượng, đồng thời xây dựng một hàm khoảng cách để đo độ phi tương tự giữa các đặc trưng dữ liệu và áp dụng cho bài toán nhận dạng ký tự. Kết quả thử nghiệm chỉ ra rằng mạng noron SOM có khả năng nhận dạng tốt hơn khi áp dụng giải pháp cải tiến. Từ khóa: nhận dạng kí tự, mạng noron nhân tạo, mạng tự tổ chức, phân cụm dữ liệu, học cạnh tranh. GIỚI THIỆU* Trong những năm gần đây, lĩnh vực nhận dạng đối tượng sử dụng mạng noron nhân tạo là một hướng nghiên cứu được nhiều người quan tâm [1,2,4,5]. Tùy từng kiểu đối tượng cần nhận dạng và mô hình mạng noron được áp dụng mà có các giải pháp khác nhau đã được đưa ra. Trong phạm vi nghiên cứu của bài báo này, chúng tôi tập trung vào vấn đề nhận dạng đối tượng dựa trên các đặc trưng hình dạng sử dụng mạng noron nhân tạo SOM[7]. Với mỗi ảnh đối tượng huấn luyện đầu vào (ví dụ ảnh ký tự, chữ kí,..), trích ra các điểm đặc trưng mô tả đối tượng và sử dụng các thông tin này để huấn luyện mạng noron SOM. Giải pháp này có thể áp dụng cho các bài toán nhận dạng kí tự, chữ ký, biển số xe Hình 1 minh họa quy trình nhận dạng ký tự sử dụng mạng noron nhân tạo SOM. Trong cả hai giai đoạn của quy trình trên đều thực hiện tiền xử lý ảnh đầu vào để giảm nhiễu. Tuy nhiên, chỉ có giai đoạn 1 phải trích chọn đặc trưng của ký tự sau bước tiền xử lý. Còn giai đoạn 2, ảnh sau khi tiền xử lý sẽ được đưa trực tiếp vào mạng để đối sánh. Hiện tại có nhiều giải pháp trích chọn đặc trưng có thể áp dụng cho tập dữ liệu ký tự như[3]: phương pháp trọng số vùng (zoning), biểu đồ chiếu (projection histograms), trích chọn chu tuyến (contour profiles), wavelet * Tel: 0989 199088, Email: latu@ictu.edu.vn Haar[6] mỗi phương pháp đều có những ưu, nhược điểm riêng. Thực tế, khi áp dụng mạng noron SOM cho bài toán nhận dạng kí tự, chúng tôi thấy độ chính xác của kết quả nhận dạng phụ thuộc nhiều vào phương pháp trích chọn đặc trưng và hàm đánh giá độ phi tương tự của SOM (hàm khoảng cách). Hàm khoảng cách này cần được xây dựng phù hợp với từng dạng dữ liệu và đặc trưng cụ thể. Chúng tôi đã chia ảnh thành nhiều vùng tương tự phương pháp trọng số vùng (chia ảnh thành lưới kích thước m x n, mỗi ô lưới là một đầu vào của mạng với giá trị là số điểm đen trong ô lưới đó)[3] và xác định đặc trưng hình dạng của đối tượng dựa vào vị trí các điểm đen đặc trưng và vị trí các điểm trắng đặc trưng. Trong đó, điểm đen (đặc trưng điểm đen) mô tả đường nét của đối tượng, chỉ ra những vị trí bắt buộc phải có nét vẽ; ngược lại, điểm trắng (đặc trưng điểm trắng) mô tả các vị trí không có đường nét (không được phép có nét vẽ). Những đặc trưng này là cơ sở để chúng tôi thiết kế cấu trúc trọng số cho mạng noron SOM, từ đó xây dựng một hàm khoảng cách mới phù hợp với cách lựa chọn các đặc trưng này. Các phần tiếp theo của bài báo sẽ trình bày chi tiết hơn, trong đó: phần 2 trình bày giải thuật SOM, phần 3 mô tả cấu trúc trọng số mới sử dụng đặc trưng điểm đen và đặc trưng điểm trắng, phần 4 đưa ra công thức xác định độ phi tương tự giữa trọng số của noron và ảnh đầu vào, phần 5 trình bày kết quả thực nghiệm và cuối cùng là kết luận. Lê Anh Tú và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 55 - 60 56 MẠNG NORON NHÂN TẠO SOM Mạng noron SOM[7] gồm lớp tín hiệu vào và lớp ra Kohonen. Lớp Kohonen thường được tổ chức dưới dạng một ma trận 2 chiều các noron. Mỗi đơn vị i (noron) trong lớp Kohonen được gắn một vector trọng số wi= [wi1, wi2, ,win], với n là kích thước vector đầu vào (Hình 2); wij là trọng số của noron i ứng với đầu vào j). Quá trình huấn luyện mạng được lặp nhiều lần, tại lần lặp thứ t thực hiện 3 bước: Bước 1- tìm noron chiến thắng (BMU- Best Matching Unit): chọn ngẫu nhiên một đầu vào v từ tập dữ liệu, duyệt ma trận Kohonen tìm noron b có hàm khoảng cách dist nhỏ nhất (thường dùng hàm Euclidian, Manhattan hay Vector Dot Product). Noron b được gọi là BMU. { }is || w || min || ||b iid t v v m= − = − (1) Bước 2- xác định bán kính lân cận của BMU: ( ) 0 exp t tσ σ λ    = −    là hàm nội suy bán kính (giảm dần theo số lần lặp), với σ0 là bán kính khởi tạo; hằng số thời gian ( )0log K λ σ = , với K là tổng số lần lặp. Bước 3- cập nhật lại trọng số của các noron trong bán kính lân cận của BMU theo hướng gần hơn với vector đầu vào v: ( ) ( ) ( ) ( ) ( )w 1 w wi i bi it t t h t v tα  + = + −   (2) Trong đó: ( ) 0 exp t tα α λ    = −    là hàm nội suy tốc độ học, với α0 là giá trị khởi tạo của tốc độ học; hbi(t) là hàm nội suy theo thời gian học, thể hiện sự tác động của khoảng cách đối với quá trình học, được tính theo công thức ( ) ( ) 2 2 || || exp 2 b i bi r rh t tσ  − = −     trong đó rb và ri là vị trí của noron b và noron i trong ma trận Kohonen. CẤU TRÚC TRỌNG SỐ DỰA TRÊN ĐẶC TRƯNG ĐIỂM ĐEN VÀ ĐẶC TRƯNG ĐIỂM TRẮNG Ảnh ký tự gốc ban đầu được lọc xương, xén tỉa các mép thừa và biến đổi về dạng ảnh nhị phân có kích thước u x v pixels (điểm đen có giá trị 1, điểm trắng có giá trị 0), với u và v chia hết cho k (k là kích thước đơn vị của lưới lấy mẫu). Mỗi ô của lưới lấy mẫu có kích thước k x k. wi1 wi2 win noron i y x1 x2 xn Hình 2. Noron i trong lớp Kohonen Hình 1. Quy trình nhận dạng ký tự sử dụng mạng noron nhận tạo Huấn luyện mạng noron SOM Mạng noron SOM đã được huấn luyện Tập ảnh kí tự huấn luyện Tập ảnh kí tự cần nhận dạng Mạng noron SOM đã được huấn luyện Kết quả nhận dạng Tiền xử lý Giai đoạn 1 Giai đoạn 2 Trích chọn đặc trưng Tiền xử lý Hình 3. Minh họa chia lưới lấy mẫu trên ảnh ký tự nhị phân Lê Anh Tú và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 55 - 60 57 Ký tự ban đầu Ký tự mới sau khi xóa đi một vài nét của ký tự ban đầu Hình 4. Ví dụ một số ký tự có hình dạng bao nhau Hình 3 minh họa ảnh nhị phân kích thước 20x16 và kích thước đơn vị của lưới lấy mẫu k=4, tức là kích thước lưới lấy mẫu là 5x4 ô, mỗi ô có kích thước 4x4 pixels. Mỗi ô của lưới lấy mẫu được trích trọn đặc trưng theo hai bước. Bước 1, lấy đặc trưng điểm đen (mb, xb, yb), trong đó mb là số pixels có giá trị 1 (điểm màu đen) và xb, yb là tọa độ trung tâm của tất cả các điểm màu đen. Bước 2, lấy đặc trưng điểm trắng (mw, xw, yw), trong mw là số pixels có giá trị 0 và xw, yw là tọa độ trung tâm của tất cả các điểm màu trắng (trình tự các bước có thể thay đổi nhưng phải thống nhất trên tất cả các ô). Lý do chúng tôi sử dụng thêm đặc trưng điểm trắng là do các đặc trưng điểm đen không hoàn toàn phân biệt được các mẫu ký tự có hình dạng bao nhau (tập nét vẽ của ký tự này bao tập nét vẽ của ký tự khác). Tức là nếu xóa đi một vài nét của ký tự ban đầu thì ta sẽ có một ký tự mới (Hình 4). Mỗi ký tự sẽ trích chọn được s=(u/k)x(v/k) đặc trưng điểm đen và s đặc trưng điểm trắng. Ví dụ, ô lưới được đánh dấu trong Hình 3 có đặc trưng điểm đen là (4, 2.5, 7) và đặc trưng điểm trắng là (12, 2.5, 6.3). Mạng noron SOM được thiết kế gồm 2s đầu vào, s đầu vào đầu tiên tương ứng với các đặc trưng điểm đen, s đầu vào tiếp theo tương ứng với các đặc trưng điểm trắng. Hình 5 minh họa kiến trúc của một noron i. Như vậy, mỗi noron i trong lớp Kohonen được gắn một vector trọng số wi= [wi1, wi2, ,wis, wis+1, wis+2, , wi2s], trong đó cấu trúc của đầu vào xj và trọng số wij (với j=1..2) gồm 3 thành phần đặc trưng m, x và y. Như vậy trong quá trình tính toán của mạng SOM, công thức (2) sẽ được áp dụng để điều chỉnh cho cả 3 tham số này. HÀM ĐÁNH GIÁ ĐỘ PHI TƯƠNG TỰ GIỮA TRỌNG SỐ CỦA NORON VÀ ẢNH ĐẦU VÀO Để đánh giá độ khác biệt giữa vector trọng số của noron và vector dữ liệu vào, thuật toán SOM sử dụng công thức (1). Đây chỉ đơn giản là công thức xác định khoảng cách giữa hai vector. Như vậy, với cách thiết lập trọng số đã trình bày ở đoạn 3, chúng tôi đề xuất một hàm đánh giá mới đo độ phi tương tự giữa trọng số của mỗi noron và ảnh kí tự vào, với dist = min{dblack+dwhite}. Trong đó, dblack là hàm đánh giá sự khác biệt dựa trên đặc trưng điểm đen, dwhite là hàm đánh giá sự khác biệt dựa trên đặc trưng điểm trắng. Hàm dblack được tính dựa trên ý tưởng coi mỗi điểm đen đặc trưng như là các điểm khung của đối tượng. Do đó khi áp một đối tượng (ký tự) lên khung này để so sánh, thì mỗi điểm trên khung (điểm đen) sẽ cần một lực Hình 6. Minh họa lực kéo của các điểm khung với đối tượng wi2 wis noron i y x1 x2 xs wi 2s xs+1 xs+2 x2s wi1 wi s+1 wi s+2 Hình 5. Noron i với vector trọng số theo đặc trưng điểm đen và trắng Lê Anh Tú và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 55 - 60 58 kéo nhất định để giữ được đối tượng (Hình 6). Lực kéo tại một điểm trên khung tỉ lệ thuận với khoảng cách từ điểm đó tới điểm đen gần nhất trên đối tượng và số lượng pixels tại điểm khung đó. Tổng lực kéo này càng nhỏ thì độ tương tự giữa khung và đối tượng càng lớn (đối tượng giống với khung), ngược lại lực kéo lớn thì độ phi tương tự lớn (đối tượng không giống khung). Công thức dblack được xác định như sau: 1 * s black bi bi i d m r = =∑ , trong đó: mbi là số pixels có giá trị 1 tại điểm khung thứ i; rbi là khoảng cách từ điểm khung thứ i đến điểm đen gần nhất trên đối tượng. Hình 7. Minh họa lực đẩy của các điểm trắng đặc trưng Ngược với các điểm đen đặc trưng (được coi là các điểm kéo), các điểm trắng đặc trưng được coi là các điểm đẩy (Hình 7). Các điểm này sẽ góp phần đẩy hình dạng của đối tượng đến gần các điểm khung hơn. Như vậy, nếu cần càng nhiều lực đẩy thì độ phi tương tự càng lớn, ngược lại lực đẩy nhỏ thì độ tương tự cao. Điều này có nghĩa là nếu đối tượng có càng nhiều nét vẽ vi phạm các vị trí “cấm vẽ” thì độ phi tương tự càng tăng. Về nguyên tắc, lực đẩy sẽ tỉ lệ nghịch với khoảng cách từ điểm trắng đặc trưng tới điểm đen gần nhất trên đối tượng. Công thức dwhite được xác định như sau: w w 1 w s i hite i i md r= =∑ , trong đó: mwi là số pixels có giá trị 0 của đặc trưng điểm trắng thứ i; rwi là khoảng cách từ điểm trắng đặc trưng thứ i tới điểm đen gần nhất trên đối tượng. Như vậy, hàm đánh giá độ phi tương tự được viết lại như sau: w 1 1 w is min * s s i bi bi i i i md t m r r= =    = +      ∑ ∑ (3) KẾT QUẢ THỬ NGHIỆM Chúng tôi đã cài đặt thử nghiệm đồng thời cả hai giải pháp: giải pháp trọng số vùng (trích chọn đặc trưng theo phương pháp trọng số vùng, với hàm khoảng cách Euclidian) và giải pháp trích trọn cải tiến (đoạn 3) với hàm đánh giá độ phi tương tự theo công thức (3). Kết quả thử nghiệm trình bày trong Hình 8 được áp dụng đối với 26 mẫu kí tự quang in hoa và một số ký tự viết tay. Trong tất cả các trường hợp thử nghiệm, giải pháp cải tiến đều cho kết quả nhận dạng chính xác hơn, đặc biệt với các mẫu ký tự quang kết quả nhận dạng đều chính xác. Với các mẫu ký tự viết tay tuy không hoàn toàn chính xác, nhưng ít sai hơn so với giải pháp chuẩn. Ảnh mẫu đầu tiên, các mẫu kí tự quang in hoa tương đối mảnh (nét mảnh), cả hai giải pháp đều cho kết quả nhận dạng chính xác. Nhưng ở ảnh mẫu thứ hai và thứ ba các mẫu ký tự quang in hoa đậm hơn (nét dày hơn) thì giải pháp chuẩn có một số kí tự bị nhận dạng sai, trong khi giải pháp cải tiến vẫn có kết quả nhận dạng chính xác. Nguyên nhân là do ảnh đầu vào được lọc xương, nên khi các kí tự có nét càng dày thì xương của ký tự càng có xu thế bị biến dạng hơn. Điều này cho thấy giải pháp cải tiến đánh giá đặc trưng của ký tự chính xác hơn (ít nhạy hơn khi có các biến dạng). Tương tự với 3 ảnh mẫu cuối, ngoài mức độ dày, mảnh của kí tự thì đây là các mẫu kí tự viết tay nên có nhiều biến dạng so với kí tự gốc. Giải pháp cải tiến vẫn có kết quả nhận dạng khả thi hơn giải pháp chuẩn. KẾT LUẬN Tuy mạng noron SOM có nhiều triển vọng trong các bài toán phân cụm dữ liệu và nhận dạng, nhưng tính khả thi thực sự phụ thuộc rất nhiều vào đặc trưng của dữ liệu và hàm đánh giá độ phi tương tự của đặc trưng. Bài báo đã đề xuất một cấu trúc trọng số mới phù hợp với cách trích trọn đặc trưng của đối tượng và đưa ra một hàm đánh giá độ phi tương tự của các đặc trưng này, góp phần nâng cao khả năng nhận dạng của noron SOM. Giải pháp đề xuất có thể áp dụng cho các bài toán nhận dạng kí tự, chữ ký, biển số xe Lê Anh Tú và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 55 - 60 59 Ảnh đầu vào Giải pháp trọng số vùng, sử dụng hàm khoảng cách Euclidian Giải pháp cải tiến Kết quả Tỉ lệ đúng Kết quả Tỉ lệ đúng A B C D E F G H I J K L M N O F Q R S T U V K X Z W 100% A B C D E F G H I J K L M N O F Q R S T U V K X Z W 100% A B C D E F G H I J K L M N O F Q P S T U V Y X Z W 92.3% A B C D E F G H I J K L M N O P Q R S T U V Y X Z W 100% A B C O E F B H I J K L M N O P M R S T U V H X Z M 76.9% A B C D E F G H I J K L M N O F Q R S T U V Y X Z W 100% A B C O E P P K 50% A B C D E F G H 100% D C F K F D 33.3% B C F I P D 83.3% N H A N O A R P K C K U 50% N H A N D A N G K I T U 100% Hình 8. Kết quả thử nghiệm nhận dạng kí tự Mặc dù kết quả thử nghiệm của giải pháp đề xuất với một số mẫu ký tự đơn giản có khả quan, nhưng để đánh giá tính khả thi thực sự của giải pháp cần tiếp tục thử nghiệm với các bộ test lớn hơn (ví dụ như MNIST). Trên các bộ test lớn thời gian tính toán cũng là một vấn đề cần xem xét, do cách thức tổ chức trọng số và việc đối sánh trọng số của noron với ảnh đầu vào tương đối phức tạp. Về mặt chất lượng nhận dạng, thì giải pháp đã đề xuất có thể tiếp tục cải tiến. Chẳng hạn, ở giai đoạn tiền xử lý có thể tăng cường đặc trưng điểm giao của các nét trong mỗi kí tự. Tức là giá trị pixel tại các điểm giao giữa các nét không phải là 1, mà có thể là tổng của tất cả các pixels có giá trị 1 quanh nó. Việc tăng cường này có thể làm tăng độ chính xác của hàm đánh giá độ phi tương tự căn cứ vào đặc trưng điểm giao. TÀI LIỆU THAM KHẢO [1]. Dong Xiao Ni, (May 4th, 2007), “Application of Neural Networks to Character Recognition”, Proceedings of Students/Faculty Research Day, CSIS, Pace University. [2]. Prof. M.S.Kumbhar, Y.Y.Chandrachud, (9-2012), “Handwritten marathi character recognition using neural network”, International Journal of Emerging Technology and Advanced Engineering, Vol 2, Issue 9. [3]. Phạm Anh Phương, (2009), “Một số phương pháp trích chọn đặc trưng hiệu quả cho bài toán nhận dạng chữ viết tay rời rạc”, Tạp chí khoa học – Đại học Huế, số 53. [4]. C .M. Bishop, (1995), “Neural networks for pattern recognition”, Oxford University Press , USA. [5]. Jelmer de Vries, “Object Recognition: A Shape-Based Approach using Artificial Neural Networks”, University of Utrecht. [6]. Viola, P., Jones, M., (2001), “Rapid object detection using a boosted cascade of simple features”, Proc. Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), Vol 1, p511–518. [7]. Teuvo Kohonen, (2001), “Self-Organizing Maps”, Springer, 3rd Edition. Lê Anh Tú và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 55 - 60 60 SUMMARY APPLYING SOM ARTIFICIAL NEURAL NETWORK TO THE CHARACTER RECOGNITION PROBLEM Le Anh Tu1*, Nguyen Quang Hoan2, Le Son Thai1 1College of Information and Communication Technology - TNU 2Posts and Telecommunications Institute of Technology When applying the SOM neural network for the identification problem in general, and character recognition problem in particular, we found that SOM neural network offers prospects of this problem. However, for each type of input data, weight structure and function that assess the dissimilarity should be adapted to make the network operate more efficiently. In this paper, we propose a new weighting structure for SOM neural network to present the shape characteristics of the object. Then, we develop a new distance function that is used to assess the non-similarity of the characteristics and applications for character recognition problem. The experimental results show that our improved solution makes the SOM neural network capable of better character recognition. Keywords: character recognition, artificial neural network, self organizing map, data clustering, competitive learning. Ngày nhận bài: 15/9/2012, ngày phản biện:25/10/2012, ngày duyệt đăng:10/12/2012 * Tel: 0989 199088, Email: latu@ictu.edu.vn