đặt vấn đề để giải quyết bài toán nhận dạng chữ tổng quát. Tuy vậy, cho đến nay còn nhiều vấn đề liên quan đến hệ nhận dạng cú pháp chƣa đƣợc giải quyết độc lập và chƣa xây dựng đƣợc các thuật toán phổ dụng. Hiện nay, nhận dạng theo cấu trúc phổ biến là trích trọn các đặc trƣng của mẫu học, phân hoạch bảng ký tự dựa trên các đặc trƣng này, sau đó ảnh cần nhận dạng sẽ đƣợc trích chọn đặc trƣng, sau đó so sánh trên bảng phân hoạch để tìm ra ký tự có các đặc trƣng phù hợp. Đối với nhận dạng chữ viết tay rời rạc dựa theo cấu trúc xƣơng và đƣờng biên, công việc này đòi hỏi phải xây dựng các đặc trƣng của chữ, đặc biệt là đặc trƣng về các điểm uốn, điểm gấp khúc và đặc trƣng của các nét.
Sau khi tiến hành công đoạn tiền xử lý, công việc tách các nét đƣợc tiến hành thông qua các điểm chạc. Sau đó trích chọn đặc trƣng cấu trúc xƣơng của chữ, mỗi nét đặc trƣng bởi cặp chỉ số đầu và cuối tƣơng ứng với thứ tự của điểm chạc đầu và điểm chạc cuối. Cuối cùng là xây dựng cây tìm kiếm, dựa vào đặc trƣng về cấu trúc xƣơng và cấu trúc biên để phân tập mẫu học thành các lớp. Quá trình tìm kiếm để phân lớp đƣợc tiến hành qua hai bƣớc: Xác định lớp tƣơng ứng với mẫu vào và tìm kiếm trong lớp đó mẫu nào gần giống với mẫu vào nhất.
Các phƣơng pháp cấu trúc áp dụng cho các bài toán nhận dạng chữ đƣợc phát triển theo hai hƣớng sau: 1. Phƣơng pháp ngữ pháp (Grammatical Methods) Giữa thập niên 1960, các nhà nghiên cứu bắt đầu xét các luật của ngôn ngữ học để phân tích tiếng nói và chữ viết. Sau đó, các luật đa dạng của chính tả, từ vựng và ngôn ngữ học đã đƣợc áp dụng cho các chiến lƣợc nhận dạng. Các phƣơng pháp ngữ pháp khởi tạo một số luật sinh để hình thành các ký tự từ một tập các công.
Nguyễn Sơn Hà - CT1301 16. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng thức ngữ pháp nguyên thủy. Các luật sinh này có thể kết nối bất kỳ kiểu đặc trƣng thống kê và đặc trƣng hình thái nào dƣới một số cú pháp hoặc các luật ngữ nghĩa. Giống nhƣ lý thuyết ngôn ngữ, các luật sinh cho phép mô tả các cấu trúc câu có thể chấp nhận đƣợc và trích chọn thông tin theo ngữ cảnh về chữ viết bằng cách sử dụng các kiểu ngữ pháp khác nhau.
Trong các phƣơng pháp này, việc huấn luyện đƣợc thực hiện bằng cách mô tả mỗi ký tự bằng một văn phạm Gi. Còn trong pha nhận dạng thì chuỗi, cây hoặc đồ thị của một đơn vị viết bất kỳ (ký tự, từ hoặc câu) đƣợc phân tích để quyết định văn phạm của mẫu đó thuộc lớp nào. Các phƣơng pháp ngữ pháp hầu hết đƣợc sử dụng trong giai đoạn hậu xử lý để sửa các lỗi mà khối nhận dạng đã thực hiện sai. Phƣơng pháp đồ thị (Graphical Methods) Các đơn vị chữ viết đƣợc mô tả bởi các cây hoặc các đồ thị.
Các dạng nguyên thủy của ký tự (các nét) đƣợc lựa chọn bởi một hƣớng tiếp cận cấu trúc. Đối với mỗi lớp, một đồ thị hoặc cây đƣợc thành lập trong giai đoạn huấn luyện để mô tả các nét, các ký tự hoặc các từ. Giai đoạn nhận dạng gán một đồ thị chƣa biết vào một trong các lớp bằng cách sử dụng một độ đo để so sánh các đặc điểm giống nhau giữa các đồ thị. Có rất nhiều hƣớng tiếp cận khác nhau sử dụng phƣơng pháp đồ thị, tiêu biểu là hƣớng tiếp cận đồ thị phân cấp đƣợc dùng trong việc nhận dạng chữ viết tay Trung Quốc và Hàn Quốc.
Mạng nơ ron Một mạng nơ ron đƣợc định nghĩa nhƣ một cấu trúc tính toán bao gồm nhiều bộ xử lý “nơ ron” đƣợc kết nối song song chằng chịt với nhau. Do bản chất song song của các nơ ron nên nó có thể thực hiện các tính toán với tốc độ cao hơn so với các kỹ thuật phân lớp khác. Một mạng nơ ron chứa nhiều nút, đầu ra của một nút đƣợc sử dụng cho một nút khác ở trong mạng và hàm quyết định cuối cùng phụ thuộc vào sự tƣơng tác phức tạp giữa các nút. Mặc dù nguyên lý khác nhau, nhƣng hầu hết các kiến trúc mạng nơ ron đều tƣơng đƣơng với các phƣơng pháp nhận dạng mẫu thống kê.
Các kiến trúc mạng nơ ron có thể đƣợc phân thành hai nhóm chính: mạng truyền thẳng và mạng lan truyền ngƣợc. Trong các hệ thống nhận dạng chữ, các mạng nơ ron sử dụng phổ biến nhất là mạng perceptron đa lớp thuộc nhóm mạng. Nguyễn Sơn Hà - CT1301 17. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng truyền thẳng và mạng SOM (Self Origanizing Map) của Kohonen thuộc nhóm mạng lan truyền ngƣợc.
Mạng perceptron đa lớp đƣợc đề xuất bởi Rosenblatt đƣợc nhiều tác giả sử dụng trong các hệ nhận dạng chữ viết tay. Hầu hết các nghiên cứu phát triển nhận dạng chữ viết tay hiện nay đều tập trung vào mạng SOM. SOM kết hợp trích chọn đặc trƣng và nhận dạng trên một tập lớn các ký tự huấn luyện. Mạng này chứng tỏ rằng nó tƣơng đƣơng với thuật toán phân cụm k-means.
Với thuật toán đơn giản nhƣng rất hiệu quả, cùng với thành công của mô hình này trong các ứng dụng thực tiễn, mạng nơ ron hiện đang là một trong các hƣớng nghiên cứu của lĩnh vực học máy. Mạng nơ ron tỏ ra phù hợp với các bài toán đối sánh, phân loại mẫu, xấp xỉ hàm, tối ƣu hoá, lƣợng tử hoá véc tơ và phân hoạch không gian dữ liệu, trong khi các phƣơng pháp truyền thống không đủ khả năng giải quyết các vấn đề nêu trên một cách hiệu quả. Đặc biệt trong các hệ thống nhận dạng sử dụng mạng nơ ron đã đạt đƣợc tỉ lệ nhận dạng khá chính xác, có thể so sánh với các phƣơng pháp nhận dạng cấu trúc, thống kê, … 1. Đặc trƣng của mạng nơron Tính phi tuyến Một nơron có thể tính toán một cách tuyến tính hay phi tuyến.
Một mạng nơron cấu thành bởi các nơron phi tuyến thì cũng sẽ có tính phi tuyến. Hơn nữa, điều đặc biệt là tính phi tuyến này đƣợc phân tán trên toàn mạng. Tính phi tuyến là một thuộc tính rất quan trọng, nhất là khi các cơ chế vật lý sinh ra các tín hiệu đầu vào (ví dụ tín hiệu tiếng nói) vốn là phi tuyến. Tính chất tƣơng ứng đầu vào, đầu ra Mặc dù khái niệm “học” (hay “huấn luyện”) chƣa đƣợc bàn đến nhƣng để hiểu đƣợc mối quan hệ đầu vào-đầu ra của mạng nơron, chúng ta sẽ đề cập sơ qua về khái niệm này.
Một mô hình học phổ biến đƣợc gọi là “học có thầy” (hay “học có giám sát”), liên quan đến việc thay đổi các trọng số liên kết của mạng nơron bằng việc áp dụng một tập hợp các mẫu tích luỹ. Mỗi một mẫu bao gồm một tín hiệu đầu vào và một đầu ra mong muốn tƣơng ứng. Các trọng số liên kết của mạng đƣợc biến đổi sao cho có thể cực tiểu hoá sự sai khác giữa đầu ra mong muốn và đầu ra thực sự của mạng theo một tiêu chuẩn thống kê thích hợp. Sự tích luỹ của mạng đƣợc lặp lại với nhiều ví dụ trong tập hợp cho tới khi mạng đạt tới một trạng thái ổn định mà ở đó không có một sự thay đổi đáng kể nào của các trọng số liên kết.
Các ví dụ tích luỹ đƣợc áp dụng trƣớc có thể đƣợc áp dụng lại trong thời gian. Nguyễn Sơn Hà - CT1301 18. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng của phiên tích luỹ nhƣng theo một thứ tự khác. Nhƣ vậy, mạng nơron học từ các ví dụ bằng cách xây dựng nên một tƣơng ứng đầu vào - đầu ra cho vấn đề cần giải quyết.
Tính chất thích nghi Các mạng nơron có một khả năng mặc định là có thể biến đổi các trọng số liên kết tuỳ theo sự thay đổi của môi trƣờng xung quanh. Đặc biệt, một mạng nơron đã đƣợc tích luỹ để hoạt động trong một môi trƣờng xác định có thể đƣợc tích luỹ lại một cách dễ dàng khi có những thay đổi nhỏ của các điều kiện môi trƣờng. Tính chất đƣa ra lời giải có bằng chứng Trong ngữ cảnh phân loại mẫu, một mạng nơron có thể đƣợc thiết kế để đƣa ra thông tin không chỉ về mẫu đƣợc phân loại, mà còn về sự tin cậy của quyết định đã đƣợc thực hiện. Thông tin này có thể đƣợc sử dụng để loại bỏ các mẫu mơ hồ hay nhập nhằng.
Tính chất chấp nhận sai sót Một mạng nơron, đƣợc cài đặt dƣới dạng phần cứng, vốn có khả năng chấp nhận lỗi, hay khả năng tính toán thô (chứ không nhạy cảm lỗi). Tức là, tính năng của mạng nơron chỉ thoái hoá (chứ không đổ vỡ) khi có những điều kiện hoạt động bất lợi. Ví dụ, nếu một nơron hay các liên kết kết nối của nó bị hỏng, việc nhận dạng lại một mẫu đƣợc lƣu trữ sẽ suy giảm về chất lƣợng. Tuy nhiên, do bản chất phân tán của thông tin lƣu trữ trong mạng nơron, sự hỏng hóc cũng đƣợc trải ra trên toàn mạng.
Nhƣ vậy, về cơ bản, trong trƣờng hợp này một mạng nơron sẽ thể hiện một sự thoái hoá về tính năng hơn là sự đổ vỡ trầm trọng. Khả năng cài đặt VLSI (Very-Large-Scale-Intergrated) Bản chất song song đồ sộ của một mạng nơron làm cho mạng nơron đó rất nhanh trong tính toán đối với một số công việc. Đặc tính này cũng làm cho một mạng nơron có khả năng phù hợp trong việc cài đặt sử dụng kỹ thuật Very -large- scale-intergrated (VLSI). Kỹ thuật này cho phép xây dựng những mạch cứng tính toán song song quy mô lớn.
Chính vì vậy, ƣu điểm nổi bật của VLSI là mang lại những phƣơng tiện hữu hiệu để có thể xử lý đƣợc những hành vi có độ phức tạp cao. Nguyễn Sơn Hà - CT1301 19. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phòng 1. Tính chất đồng dạng trong phân tích và thiết kế Về cơ bản, các mạng nơron có tính chất chung nhƣ là các bộ xử lý thông tin.
Điều này áp dụng cho tất cả các lĩnh vực có liên quan tới việc ứng dụng mạng nơron. Đặc tính này thể hiện ở một số điểm nhƣ sau: Các nơron, dƣới dạng này hoặc dạng khác, biểu diễn một thành phần chung cho tất cả các mạng nơron. Tính thống nhất này đem lại khả năng chia sẻ các lý thuyết và các thuật toán học trong nhiều ứng dụng khác nhau của mạng nơron.