Blog cộng đồng về Công nghệ thông tin

Khái niệm

Nhận dạng chữ viết cũng như nhận dạng nói chung là dùng thuật toán để tìm ra các đặc điểm riêng của từng cá thể trong quần thể mà chúng ta phải nhận dạng. Với mỗi dữ liệu nhập vào ta sẽ phải xuất ra cá thể tương tự nhất!

Các phương pháp nhận dạng

Hiện nay có rất nhiều phương pháp nhận dạng và càng ngày sắc xuất thành công lại cao hơn. Dưới đây liệt kê vài phương pháp nhận dạng cơ bản:

• Dùng mạng nơ-ron (neural network): thiết kế và coding đơn giản, nhưng tính chậm và xác xuất không cao.
• Dùng HMM (Hiden Markov Model): xác xuất cao, coding đơn giản, không dùng nhiều bộ nhớ, nhưng rất khó phân lớp dữ liệu.
• Dùng qui hoạch động (dynamic programming): đơn giản, nhưng hiệu quả không cao.

Các bước cần thiết

Để bước vào thế giới của nhận dạng bạn phải hiểu rằng bất kỳ phương pháp nhận dạng nào cũng đều cần phải tạo một từ điển từ những dữ liệu của các cá thể ban đầu và phải qua các bước sau đây:

1. Xử lý dữ liệu ban đầu (preprocessing): dữ liệu nhập vào thường là "thô", không qua bước xử lý này thì hiệu quả thường không cao.
2. Phân tích dữ liệu để lấy ra các đặc điểm (features): tùy vào các loại dữ liệu mà các bạn có thể lấy đặc điểm bằng các phương pháp khác nhau.
3. Tạo từ điển-tập cho máy học (training): nếu bạn dùng HMM hay mạng nơ ron thì phải cho máy training, còn nếu dùng các phương pháp khác thì có thể chỉ cần tạo từ điển với tập dữ liệu tốt nhất.

Ví dụ: nhận dạng chữ viết tay online

Chữ viết tay online là gì

Nếu bạn có từ điển tiếng Nhật mà có thể nhập bằng cách viết chữ kanji vào hoặc là trong máy tính bạn có phần nhập chữ kanji bằng cách viết vào thì đó chính là chương trình nhận dạng chữ viết tay online. Trong nhận dạng chữ viết thì có những loại như sau:

• Online-Offline: Người ta phân chia như thế này là muốn nói đến nhận dạng chữ viết ngay lúc viết và nhận dạng chữ viết đã được viết ra hoặc in trên giấy.
• Printed-Handwriting: Chữ trên biển hiệu, trong bản giấy đánh máy thì gọi là printed (hay là gì nữa thì cũng không rõ), còn Handwriting là chữ viết tay.

Nhiều người nói rằng mức độ khó khăn của nhận dạng chữ viết online và offline là như nhau. Nhưng điều đó không hoàn toàn đúng, nhận dạng chữ viết online chúng ta có thể thu được nhiều thông tin hơn là nhận dạng chữ viết offline. Ví dụ một chữ viết mà nét sau đè lên nét trước thì nhận dạng chữ viết kiểu online hoàn toàn có lợi thế hơn. Song ngược lại, nhận dạng chữ viết offline có cái hay của nó là dù bạn viết nét nào trước nét nào sau thì kết quả ra là vẫn giống nhau, nhưng với nhận dạng chữ viết online thì có thể kết quả sẽ cho ra khác nhau. Với thói quen, và cách viết đúng thì nhận dạng chữ viết online vẫn có ưu điểm hơn.

Giới thiệu qua về chương trình

Chương trình này thường phải có 2 phần: tạo từ điển và chương trình nhận dạng.Nếu bạn gộp 2 chương trình vào làm 1 thì cũng được. Một chú ý nữa là khi capture chuột (lấy các điểm của nét vẽ) thì các bạn phải lấy các điểm đều nhau và càng được nhiều điểm thì càng tốt. Lần đầu tiên làm chương trình, do lấy các điểm không nhiều nên kết quả không cao, song khi phát hiện ra và lấy được nhiều điểm chương trình của tôi đã có những cải thiện rõ rệt.

Tách lọc thông tin của chữ viết

Nét vẽ (Stroke)

Nét vẽ được chia làm 2 loại: nét thật (real Stroke) và nét ảo (virtual stroke). Với dấu cộng này chúng ta có 3 nét, 2 nét theo đường màu đỏ được gọi là nét thật, còn nét theo đường màu xanh là nét ảo. Nét ảo tượng trưng cho việc bạn nhấc bút và đặt vào điểm mới, vì vậy một điều thú vị là nét ảo lúc nào cũng thẳng.

Hướng viết

Hướng viết tùy theo bạn chia, thường thì người ta chia làm 8 hướng với tiếng Nhật. Tiếng Việt thì nên chia nhiều hơn vì chữ tiếng Việt ít nét hơn chữ tiếng Nhật, do đó thông tin thường ít hơn, có nghĩa là khó phân biệt các chữ với nhau hơn. Số lượng chữ tiếng Nhật nhiều vì thế nếu chia nhiều thì từ điển sẽ to mà hiệu quả không tăng cao là mấy.

Số hóa chữ viết

Đến bây giờ bạn đã có đầy đủ thông tin của một chữ viết: số nét (số nét ảo, số nét thật), hướng các nét. Chúng ta sẽ mã hóa (encoding) cho chữ viết của mình. Mỗi nét (cả nét thật và nét ảo) chúng ta tạm thời chia làm 4 cho dễ hiểu. Cụ thể chữ T:

Như vậy với chữ T thì ta có 3 nét, trong đó 2 nét thật và một nét ảo. Tưởng tượng bạn đặt bút, viết từ trái qua phải(nét 1, nét thật) nhấc bút, đặt vào giữa nét đầu (đang viết nét ảo), kéo xuông dưới (bạn đang vẽ nét thật cuối cùng). Khi chia mỗi nét làm 4 thì bạn có kết quả sau:

S1: 0 0 0 0
S2: 4 4 4 4
S3: 6 6 6 6

S là viết tắt cho stroke. Có nghĩa là bây giờ với chữ T, bạn đã cho vào từ điển của mình một đoạn thông tin như sau:

Tên chữ: T
Số nét: 3
Cụ thể:
Nét 1 (thật): 0 0 0 0
Nét 2 (ảo) :4 4 4 4
Nét 3 (thật): 6 6 6 6

Cứ tiếp tục làm như vậy cho đến khi bạn hoàn thành số lượng từ muốn nhận dạng, tất nhiên hãy lập trình để cho máy nó tính, chứ cứ ngồi mà tính từng chữ một thì rất lâu.

Nhận dạng

Có thể dùng phương pháp nhận dạng RDS và LSDS. RDS hơi phức tạp, dưới đây là trình bày về LSDS.

Khi đã tạo được mẫu từ điển như trên rồi, có rất nhiều chữ và kí hiệu cùng số nét, và thứ tự các nét ảo, nét thật giống nhau, ví dụ dấu "+" và chữ "T" là một ví dụ điển hình: chúng đều có 3 nét: 1 nét thật ,tiếp theo là 1 nét ảo và cuối cùng là 1 nét thật. Chúng ta sẽ liệt kê thông tin của dấu "+" và chữ "T" trong từ điển mà chúng ta đã làm:

<font class="content">

Bây giờ chúng ta thử viết một chữ như sau để lấy ví dụ cho nhận dạng (chữ viết là màu đen, màu xanh dùng để xác định các hướng).

Với các nét nằm giữa những hướng ta đã xác định thì cho nó vào với hướng gần nhất, cụ thể nét 1 so với hướng 0 là không thay đổi mấy, vì thế nó sẽ được cho bởi số: 0 0 0 0 (chú ý trong thực tế nó có thể là 0 1 0 0, hay nhiều số phức tạp hơn). Nét thứ 2 so với hướng 4 không thay đổi là mấy vì thế sẽ được cho bởi: 4 4 4 4 (nét xanh nhỏ song song với nét 2, để nhìn cho dễ). Nét thứ 3 thì quá rõ rồi nó sẽ được cho bởi: 6 6 6 6.

Vậy với chữ này bạn sẽ được 3 nét: 1 thật, rồi đến 1 ảo, rồi lại 1 thật.Tìm trong từ điển có những chữ nào 3 nét, và có thứ tự giống như trên. So sánh bằng phương pháp LSDS như sau:

<font class="content"> Độ chênh lệch so với chữ "T" = {(0-0)² + (0-0)² + (0-0)² + (0-0)² +  (4-4)² + (4-4)² + (4-4)² + (4-4)² + (6-6)² + (6-6)² + (6-6)² + (6-6)²}/(2*4*3) = 0</font>

<font class="content">Độ chênh lệch so với dấu "+" = {(0-0)² + (0-0)² + (0-0)² + (0-0)² +  (4-3)² + (4-3)² + (4-3)² + (4-3)² + (6-6)² + (6-6)² + (6-6)² + (6-6)²}/(2*4*3) = 1/6</font>

Đánh giá: Từ đây bạn thấy rằng độ chênh lệch so với chữ "T" là khác 0 trong khi độ chênh lệch so với dấu "+" là 1/6 = 16%, như vậy kết quả nhận dạng sẽ là chữ "T". Tất nhiên trong thực tế ít khi có kết quả "đẹp" đến mức độ như vậy, ngoài ra bạn phải còn phân biệt với toàn bộ những chữ có 3 nét nữa. Tóm lại, theo phương pháp này thì ta có công thức tổng quát như sau:

Trong đó, dij là hướng của phần j của nét i, Dij là hướng tương ứng của một chữ (hoặc ký hiệu) trong từ điển. Có n nét, và mỗi nét được chia làm N phần.

Có rất nhiều công thức ứng với thuật toán LSDS, trên đây là một trong những công thức được áp dụng thực tế trong chương trình nhận dạng của tử điển.

Gốc: VCSJ