In this paper, a greedy matching algorithm with geometric constraint for solving the polygonal arcs matching (boundary line segments matching) is proposed. Assume the matched cost and the unmatched penalty of each line segment are given, as well as any two matched pairs in the matching which preserves the geometric relation. Our goal is to find a matching such that (1) the sum of costs of matched line segments and the penalties of unmatched line segments is minimum, and (2) the matching preserves the geometric relation. The proposed greedy matching algorithm consists of two main modules. The first is an optimal matching module, which utilizes the optimization matching method to find an optimal matching without the geometric constraint. The second module is an evaluation and update module, which deletes the matched pair with a geometric relation having the maximum inconsistency after each matched pair has been evaluated, and a new matching is found again. The algorithm continues until a stable matching is found. To verify the validity of the proposed algorithm, we implement it to recognize handwritten Chinese postal characters. We selected 51 Chinese postal characters as the prototype characters, and the experiments are conducted on 2550 samples, with each category containing 50 variations. The recognition rate is 91.8%. Experimental results reveal the feasibility of our proposed method in recognizing handwritten Chinese postal characters.
- Bipartite weighted matching
- Combinatorial optimization
- Contour tracing
- Greedy matching algorithm
- Handwritten Chinese character recognition