BIPARTITE WEIGHTED MATCHING FOR ONLINE HANDWRITTEN CHINESE CHARACTER-RECOGNITION

The matching of line segments between input and prototype characters c an be formulated as bipartite weighted matching problem. Under the ass umption that the distance of the two line segments and the unmatched p enalty of any line segment are given, the matching goal is to find a m atching such that the sum of the weights of matching edges and the pen alties of unmatched vertices is minimum. In this paper, the Hungarian method is applied to solve the matching problem by a reduction algorit hm. Moreover, a greedy algorithm based on the Hungarian method is prop osed by restricting the above matching which satisfies the constraints of geometric relation. For each iteration in the greedy algorithm, a matched pair is deleted if the relation of their neighbors does not ma tch and a new matching is then found by applying Hungarian method. Fin ally, we can find a stable matching that preserves the geometric relat ion. We have implemented this method to recognize on-line Chinese hand written characters permitting both stroke-order variation and stroke-n umber variation and a 91% recognition rate is attained.