線上手寫中文辨認－動態規劃法和任務分配法則

Abstract

在手寫中文辨識系統中,連筆、筆順及辨識速度一直都是具有關鍵性的三 個問題,有待持續的研究，不斷的改進。本篇論文提出了三種對策,分別針 對這三個問題,做進一步的研究。以下逐條列出這三種方案,並作簡略說 明: 1.動態規劃法：藉著成本矩陣和插入、刪除、取代，這三種修改運算 ，可求出兩個字間的差異度。這個方法不受連筆限制，但有筆順的問題。 此外，為了使差異度能反應出手寫特性，在屬性字串中加入了需要屬性， 使重要的點得到較高成本，不重要的點得到較低成本。 2.任務分配法： 以線性規劃的方式解決派遣問題，加上插入、刪除及取代運算，在成本矩 陣上求出兩個中文字間的差異度。這個方法比較不受筆順的影響，即使筆 順不對，也能求出合理的差異度。 3.切割中文字:藉著下筆及提筆的資 訊,將輸入中文字和候選中文字切成數個小塊,再藉動態規劃法及任務分配 法,求出這兩種不同小塊間,相對應小塊的差異度。藉著這種方式,可以加 快辨識的速度,有效解決時間的問題。結合以上三種方案，可以在較短時 間內，不受筆順及連筆的限制而達到辨識的目的。 In the On-Line Chinese Recognition, stroke permutation、 stroke merge and speed are key issues. Three different techniques are proposed in this thesis to improve performance on these issues. 1.Dynamic Programming: By combining the insert、delete and replace operations,the distance between input and reference can be obtained. This technique is proposed to recognize Chinese characters written in a cursive way under the constraint of correct strokes orders. Because of the uncertainty of written style, we add a necessary attribute into the attribute string and get a more accurate edit cost than before. 2.Job Assignment: With the linear programming, we calculate the distance between two Chinese characters in a cost matrix. This technique has three edit operation: insert、delete and replace. Unlike the dynamic programming, this method is not sensitive to stroke permutation. 3. Chinese Character Division: First, we divide the input and reference into several blocks by pen down and pen up. Then we can obtain the sum of the distance by calculating the distance between those matching blocks of two characters. An advantage of using the division method is the saving of time. With the above three techniques, we can finish recognition and ignore the constraint of stroke permutation and stroke merge.