NHậN DạNG Ký Tự Số VIếT TAY BằNG GIảI THUậT MáY HọC

- NHẬN DẠNG KÝ TỰ SỐ VIẾT TAY BẰNG GIẢI THUẬT MÁY HỌC Đỗ Thanh Nghị 1 và Phạm Nguyên Khang 1.
- Nhận dạng ký tự viết tay, Đặc trưng GIST, Cây ngẫu nhiên xiên phân, Phân tích biệt lập tuyến tính.
- Trong bài viết này, chúng tôi trình bày giải thuật máy học rừng ngẫu nhiên xiên phân (rODT) cho nhận dạng ký tự số viết tay.
- Chúng tôi đề xuất sử dụng đặc trưng toàn cục (GIST) cho biểu diễn ảnh ký tự số trong không gian có số chiều lớn.
- Tiếp theo, chúng tôi đề xuất giải thuật học tự động rừng xiên phân ngẫu đa lớp, mỗi cây thành viên sử dụng siêu phẳng phân chia dữ liệu hiệu quả tại mỗi nút của cây dựa trên phân tích biệt lập tuyến tính (LDA).
- Việc xây dựng cây xiên phân ngẫu nhiên vì thế tạo cho giải thuật có khả năng làm việc tốt trên dữ liệu có số chiều lớn sinh ra từ bước tiền xử lý.
- Kết quả thử nghiệm trên tập dữ liệu thực MNIST cho thấy rằng giải thuật rODT do chúng tôi đề xuất nhận dạng rất chính xác khi so sánh với các phương pháp nhận dạng hiện nay..
- Nhận dạng chữ số viết tay là cần thiết và được ứng dụng rộng rãi trong nhiều lĩnh vực như nhận dạng các chữ số trên chi phiếu ngân hàng, mã số trên bì thư của dịch vụ bưu chính, hay các chữ số trên các biểu mẫu nói chung.
- Vấn đề nhận dạng chữ viết tay nói chung và nhận dạng chữ số viết tay nói riêng là một thách thức lớn đối với các nhà nghiên cứu.
- Bài toán lớn luôn đặt ra phía trước vì sự phức tạp của việc nhận dạng chữ viết phụ thuộc nhiều vào phong cách viết và cách thể hiện ngôn ngữ của người viết.
- Chúng ta không thể luôn luôn viết một ký tự chính xác theo cùng một cách..
- Do vậy, xây dựng hệ thống nhận dạng chữ viết có thể nhận dạng bất cứ ký tự nào một cách đáng.
- Hệ thống nhận dạng thường bao gồm hai bước:.
- rút trích đặc trưng từ ảnh và học tự động từ các đặc trưng để có thể nhận dạng ký tự.
- Hiệu quả của hệ thống nhận dạng phụ thuộc vào các phương pháp sử dụng ở hai giai đoạn trên..
- Busa- Fekete, 2009) đều sử dụng các đặc trưng cơ bản từ ảnh ký tự như đường biên, cạnh, độ dày, giá trị mức xám, haar-like, với các xử lý đặc thù như lấy mẫu, dao động các điểm ảnh, biến đổi ảnh, thêm dữ liệu ảo.
- Sau đó hệ thống nhận dạng huấn luyện.
- Hệ thống chúng tôi đề xuất trong bài viết thực hiện hai bước: sử dụng đặc trưng toàn cục (GIST) cho biểu diễn ảnh ký tự số trong không gian có số chiều lớn (960 đặc trưng, chiều cho mỗi ảnh), huấn luyện rừng xiên phân ngẫu đa lớp dựa trên phân tích biệt lập tuyến tính (LDA), nhận dạng hiệu quả các ký tự số.
- Kết quả thử nghiệm trên tập dữ liệu thực MNIST (LeCun &.
- Cortes, 1989) cho thấy phương pháp chúng tôi đề xuất, huấn luyện, nhận dạng nhanh và chính xác khi so sánh với các phương pháp hiện có..
- Phần tiếp theo của bài viết được trình bày như sau: phần 2 trình bày ngắn gọn về trích đặc trưng GIST từ ảnh, phần 3 trình bày giải thuật ODT của chúng tôi đề xuất.
- 2 RÚT TRÍCH ĐẶC TRƯNG.
- Trong hệ thống nhận dạng, bước rút trích đặc trưng là rất quan trọng, ảnh hưởng lớn đến hiệu quả của việc huấn luyện mô hình học tự động..
- Các đặc trưng rút trích từ ảnh phải đạt được mục đích quan trọng là dựa trên các đặc trưng đó mà giải thuật học có thể phân biệt tốt nhất một ký tự số này với một ký tự số khác..
- Các nghiên cứu tiên phong trong lĩnh vực nhận dạng (LeCun et al., 1998), (Simard et al., 2003), (Kégl &.
- Busa-Fekete, 2009) đều sử dụng các đặc trưng cơ bản từ mức thấp nhất là giá trị mức xám của từng điểm ảnh, đường biên, cạnh, độ dày, tổ chức đồ haar-like, đến các phương pháp xử lý đặc biệt khác như lấy mẫu, dao động các điểm ảnh, biến đổi ảnh..
- Trong mấy năm trở lại đây, cộng đồng nghiên cứu về thị giác máy tính và tìm kiếm ảnh đặc biệt quan tâm đến hai kiểu đặc trưng rất hiệu quả là đặc trưng cục bộ không đổi (SIFT) của (Lowe, 2004) và đặc trưng toàn cục GIST của (Oliva &.
- Tuy nhiên bất biến với phép quay của đặc trưng SIFT lại gây ra sự.
- bất lợi cho nhận dạng ký tự số (số 9 và 6 có thể như nhau).
- Hơn nữa, phương pháp SIFT cung cấp rất nghèo nàn về số lượng các đặc trưng từ ảnh ký tự số (ít hơn 10 đặc trưng).
- Trong khi đó sử dụng đặc trưng toàn cục GIST thì không gặp khó khăn như SIFT.
- Chính vì lý do đó, chúng tôi sử dụng đặc trưng toàn cục GIST để giải quyết vấn đề nhận dạng số viết tay.
- Phương pháp GIST rút trích từ ảnh tập hợp các đặc trưng quan trọng như tính tự nhiên, mở rộng, độ nhám, độ chắc chắn, cho phép trình bày cấu trúc không gian của một cảnh.
- Để tính toán đặc trưng mô tả GIST, ảnh đầu vào được đưa về dạng vuông, chia thành lưới 4 x 4, các tổ chức đồ theo hướng tương ứng được trích ra.
- Nguyên lý trích đặc trưng dựa vào phép biến đổi Gabor theo các hướng và tần số khác nhau.
- Mỗi ảnh ký tự số được rút trích các đặc trưng GIST (véc tơ có 960 chiều).
- Sau bước trích đặc trưng này, tập dữ liệu ảnh đưa về dạng bảng hay ma trận mà ở đó mỗi ảnh là một dòng có 960 cột (chiều), mỗi ký tự số được gán nhãn (lớp tương ứng là 0, 1.
- Bước tiền xử lý, rút trích đặc trưng ảnh ký tự số tạo ra tập dữ liệu có số chiều lớn.
- Giải thuật phân lớp được chọn tiếp theo sau phải có khả năng xử lý tốt dữ liệu có số chiều lớn.
- Một nghiên cứu trước đây trong (Do et al., 2009), chúng tôi đã đề nghị giải thuật rừng ngẫu nhiên xiên phân RF-ODT cho phân lớp hiệu quả dữ liệu có số chiều lớn.
- Hiệu quả của một giải thuật học như đã nghiên cứu của (Breiman dựa trên cơ sở của 2 thành phần lỗi là bias và variance mà ở đó, thành phần lỗi bias là lỗi của mô hình học so với Bayes và variance là lỗi do tính biến thiên của mô hình so với tính ngẫu nhiên của các mẫu dữ liệu..
- Giải thuật RF-CART của Breiman xây dựng một tập hợp các cây quyết định hiệu quả cao và đa dạng (có sự tương quan thấp giữa các cây thành viên).
- Để giữ tính tương quan giữa các cây ở mức thấp, RF-CART sử dụng việc lấy mẫu có hoàn lại (bootstrap) từ tập dữ liệu ban đầu để xây dựng cây.
- RF-CART cho độ chính xác cao so với các giải thuật phân lớp tốt nhất hiện nay bao gồm Boosting (Freund &.
- Tuy nhiên, việc xây dựng cây của RF-CART chỉ chọn một chiều để phân hoạch dữ liệu tại các nút như đề nghị trước đây (Breiman et al., 1984), (Quinlan, 1993).
- Do đó, độ chính xác của mô hình.
- cây bị giảm khi làm việc với các tập dữ liệu có số chiều lớn và phụ thuộc lẫn nhau.
- Vì thế, việc phân hoạch đơn thuộc tính được dùng để xây dựng cây thông thường thì không hiệu quả trong trường hợp này..
- thuật xây dựng cây quyết định sử dụng phân hoạch đa thuộc tính (xiên phân) tại các nút được đề nghị.
- (Murthy et al., 1993) đã đưa ra giải thuật OC1, một hệ thống dùng để xây dựng các cây quyết định xiên trong đó dùng thuật toán leo đồi để tìm một phân hoạch xiên tốt dưới dạng một siêu phẳng.
- RF-ODT của (Do et al., 2009) xây dựng các cây xiên phân ngẫu nhiên dựa trên siêu phẳng tối ưu (phân hoạch hiệu quả cao, khả năng chịu đựng nhiễu tốt) thu được từ huấn luyện SVM.
- Tuy nhiên, việc tìm siêu phẳng tối ưu của SVM mặc dù hiệu quả nhưng có độ phức tạp cao..
- Để giảm độ phức tạp của cài đặt, chúng tôi đề xuất thay thế SVM bởi phân tích biệt lập tuyến tính LDA, và mở rộng cho vấn đề phân lớp đa lớp (lớn hơn 2).
- Xét vấn đề phân lớp nhị phân (2 lớp), ý tưởng chính của LDA (Fisher, 1936) là tìm siêu phẳng sao cho khi chiếu dữ liệu lên đó thì độ biệt.
- lập giữa trung bình dữ liệu của 2 lớp là lớn nhất và độ chồng lấp giữa 2 lớp là nhỏ nhất..
- Hình 2: Minh hoạ véc tơ (w) dùng để chiếu dữ liệu 2 chiều.
- Tập dữ liệu phân làm 2 lớp R 1 (có N 1.
- Mật độ phân bố (scatter) của dữ liệu 2 lớp sau khi chiếu:.
- Chính vì lý do đó, khi độ biệt lập tuyến tính của dữ liệu không dựa vào hai trọng tâm m 1 và m 2 (trường hợp dữ liệu phi tuyến), cây xiên phân vẫn xử lý được tình huống này..
- Từ khi bắt đầu trình bày giải thuật đến giờ, chúng tôi chỉ tập trung vào vấn đề phân lớp nhị phân (2 lớp).
- Để mở rộng giải thuật cho vấn đề phân lớp đa lớp (có hơn 2 lớp).
- Để làm được điều này, chúng tôi đề xuất mô hình phân cấp.
- Chúng tôi đề xuất tạo ra 2 lớp (lớp dương và lớp âm), mà ở đó mỗi lớp có chứa dữ liệu từ các lớp khác.
- Tức là những dữ liệu của các lớp gần nhau được gom vào một trong 2 lớp dương, âm.
- Đến đây, dữ liệu tại một nút đã trở lại bài toán phân lớp nhị phân, chúng ta có thể áp dụng công thức LDA ở trên.
- Quá trình cứ thế tiếp tục đến khi phân hoạch hoàn toàn dữ liệu..
- Giải thuật rừng ngẫu nhiên xiên phân (rODT) của chúng tôi đề xuất cho một vấn đề phân lớp tập dữ liệu m điểm dữ liệu x i (i=1,m) trong không gian n chiều, được thực hiện như mô tả trong Hình 3.
- Một cây quyết định xiên (ký hiệu là ODT k ) trong rừng ngẫu nhiên gồm k cây được xây dựng như sau:.
- Tập dữ liệu học B k là m phần tử dữ liệu được lấy mẫu có hoàn lại từ tập dữ liệu ban đầu..
- Hình 3: Giải thuật rừng ngẫu nhiên xiên phân (rODT) 4 KẾT QUẢ THỰC NGHIỆM.
- Trong phần thực nghiệm, chúng tôi sử dụng tập dữ liệu MNIST (LeCun &.
- Cortes, 1989) cung cấp, thường dùng để đánh giá hiệu quả của giải thuật nhận dạng ký tự số viết tay.
- Tập dữ liệu MNIST có nguồn gốc từ tập NIST do tổ chức National Institute of Standards and Technology (NIST) cung cấp, sau đó được LeCun cập nhật và chia thành 2 tập riêng biệt.
- Tất cả các ảnh trong tập học đều được canh chỉnh và biến đổi thành dữ liệu dạng điểm gồm 60.000 phần tử (ký tự số) có 784 chiều là giá trị mức xám của các điểm, 10 lớp (từ 0 đến 9)..
- chỉnh thành dữ liệu điểm gồm 10000 phần tử trong 784 chiều, 10 lớp (từ 0 đến 9)..
- Để có thể đánh giá hiệu quả của phương pháp đề xuất (rODT, GIST), chúng tôi đã sử dụng chương trình của (Douze et al., 2009) để rút trích đặc trưng và đồng thời chúng tôi cũng cài đặt giải thuật rODT bằng ngôn ngữ lập trình C/C++..
- Chúng tôi thực hiện so sánh hiệu quả của (rODT và GIST) với các giải thuật hiện nay như giải thuật AdaBoost.M1 (Freund &.
- Kết quả thu được độ chính xác như trình bày trong Bảng 1.
- Các kết quả tham khảo từ các phương pháp của (LeCun et al., 1998), (Kégl &.
- Bảng 1: Kết quả nhận dạng tập ký tự viết tay MNIST.
- STT Phương pháp Độ chính xác.
- Hình 4: Mẫu ký tự số của MNIST.
- Kết quả thực nghiệm cho thấy rằng rODT sử dụng GIST cho kết quả nhận dạng chính xác đến 99.12%, là một trong ba phương pháp nhận dạng tốt nhất khi so sánh với tất cả các phương pháp khác..
- Đi vào chi tiết kết quả thu được của từng phương pháp, những phương pháp có đánh dấu.
- cho biết tác giả đã sử dụng các xử lý đặc thù để thu được kết quả nhận dạng tốt.
- Thường các xử lý này khá phức tạp như trích đặc trưng haar-like, làm biến dạng, thay đổi dữ liệu và cả cài đặt giải thuật rất phức tạp như mạng tích chập CNN, tích các boosting.
- CNN của (Simard et al., 2003), (O’Neill, 2006) và các giải thuật AdaBoost.M1 (Freund &.
- Frank, 2005), thời gian huấn luyện mạng gần 1 ngày để đạt được độ chính xác như trong bảng.
- Trong khi các giải thuật SVM không cần bất kỳ một xử lý đặc biệt nào, chỉ mất thời gian huấn luyện 30 phút (nhanh hơn 50 lần), cho độ chính xác gần tương đương (thấp hơn 0.5.
- Giải thuật rODT cần thời gian huấn luyện khoảng 15 phút (nhanh hơn 100 lần so với mạng tích chập) vẫn cho độ chính xác trong top 3.
- Hình 5: Chương trình nhận dạng ký tự số (rODT, GIST) 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.
- Chúng tôi vừa trình bày giải thuật máy học rừng ngẫu nhiên xiên phân (rODT) sử dụng các đặc trưng toàn cục (GIST), cho phép nhận dạng.
- chính xác ký tự số viết tay.
- Bước tiền xử lý trích đặc trưng toàn cục từ ảnh ký tự số cho ra bảng dữ liệu có số chiều lớn.
- Chúng tôi đề xuất giải thuật học tự động rừng xiên phân ngẫu đa lớp, mỗi cây thành viên sử dụng siêu phẳng phân chia dữ liệu.
- hiệu quả tại mỗi nút của cây dựa trên phân tích biệt lập tuyến tính (LDA).
- Kết quả thử nghiệm trên tập dữ liệu thực MNIST cho thấy rằng giải thuật rODT do chúng tôi đề xuất nhận dạng rất chính xác khi so sánh với các phương pháp nhận dạng hiện nay.
- Phương pháp đề xuất đạt hiệu quả nhận dạng chính xác cao nhưng không cần bất cứ xử lý đặc biệt nào.
- Các thử nghiệm cho nhận dạng ký tự viết tay gồm ký tự số và 26 ký tự alphabet cho thấy phương pháp của chúng tôi thật sự tốt..
- Trong tương lai gần, chúng tôi kết hợp hệ thống này với các phương pháp khác cho phép trích, đọc số xe.