Ai-Jia Hsieh*, Kuo-Chin Fan, Tzu-I Fan and Chin-Wen Ho
Institute of Computer Science and Information Engineering
National Central University
Chungli, Taiwan 320, R.O.C.
* Computer & Communication Research Laboratories
Industrial Technology Research Institute
Hsinchu, Taiwan 310, R.O.C.
A greedy matching method for the recognition of stroke-based handwritten Chinese characters is proposed in this paper. First, a stroke extraction algorithm is employed by making use of a multi-stage strategy based on a feature point stroke extraction technique to merge the short line segments which are broken by crossing strokes or touching strokes. After thinning and stroke extraction, the pattern is represented by line segments of strokes, and then a greedy matching method based on bipartite weighted matching with penalty is applied. The greedy matching assumes that the matching cost and the unmatched penalty of each line segment are given as well as any matching pair in the matching which preserves the geometric relations. Our goal is to find a matching such that: (1) the sum of weights of matching edges and the penalties of unmatched vertices is a minimum, and (2) the matching preserves the geometric relations. 51 Chinese postal characters were selected as the prototype characters and the experiments were conducted on 2601 samples with each category having 51 variations. The recognition rate was 93.0%, which reveals the feasibility of the proposed method in recognizing handwritten Chinese postal characters.
Keywords: stroke extraction, greedy matching, bipartite weighted matching, combinatorial optimization
Received August 1, 1994; revised January 11, 1995.
Communicated by Jhing-Fa Wang.