Paper Info
Title
Bipartite weighted matching for on-line handwritten Chinese character recognition
Abstract
The matching of line segments between input and prototype characters can be formulated as bipartite weighted matching problem. Under the assumption that the distance of the two line segments and the unmatched penalty of any line segment are given, the matching goal is to find a matching such that the sum of the weights of matching edges and the penalties of unmatched vertices is minimum. In this paper, the Hungarian method is applied to solve the matching problem by a reduction algorithm. Moreover, a greedy algorithm based on the Hungarian method is proposed 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 match and a new matching is then found by applying Hungarian method. Finally, we can find a stable matching that preserves the geometric relation. We have implemented this method to recognize on-line Chinese handwritten characters permitting both stroke-order variation and stroke-number variation and a 91% recognition rate is attained.
Year
DOI
Venue
1995
10.1016/0031-3203(94)00090-9
Pattern Recognition
Keywords
Field
DocType
Bipartite weighted matching,On-line handwritten,Chinese character recognition,Hungarian method,Combinatorial optimization,Greedy algorithm
Matching pursuit,Line segment,Artificial intelligence,Hungarian algorithm,Optimal matching,Pattern recognition,Vertex (geometry),Bipartite graph,Algorithm,Greedy algorithm,3-dimensional matching,Machine learning,Mathematics
Journal
Volume
Issue
ISSN
28
2
0031-3203
Citations 
PageRank 
References 
15
1.13
7
Authors
3
Name
Order
Citations
PageRank
Ai-Jia Hsieh1232.92
Kuo-chin Fan21369117.82
Tzu-I Fan3397.32