"Prototype Pruning by Feature Extraction for Handwritten Mathematical Symbol Recognition"

by Stephen M. Watt, Xiaofang Xie

Summary

Mathematical handwriting differs from other forms of handwriting: the set of possible input symbols is very extensive, (2) the spatial relation among symbols can use complex context-sensitive two dimensional rules, (3) can involve large operators such as matrix brackets, fraction bars or square roots. This paper presents approaches to recognize a large set of mathematical symbols.

Pruning prototypes is an intuitive way to break a large vocabulary into several smaller groups. For an unknown symbol, find the small group to which it belongs, then try to match the symbol in the group. During prototype pruning, the mathematical symbols are grouped according to some features. Then comparison during recognition is performed on groups instead of the whole set of symbols.

Data is gathered by using questionnaire, and about 50 people's handwritten is put into the database. Several pre-processing operations were performed, including selectively chopping the head and the tail of strokes, re-sampling, smoothing and size normalization.

Then some features are introduced:

Geometric Features:
(1) Number of Loops: by finding number of minimum distance pairs - sweep a line parallel to the line between "begin" and "end" (a pair of points within a certain distance threshold on a stroke) in the direction that shortens distanse between the two neighboring intersections with the stroke to find either to be locally connected or a minimus distance pair.
(2) Number of Intersections: using modified sweepline algorithm - on finding an intersection, delete the two line segments associated with the intersection, and insert two line segments that begin from intersection and end with their old ending points.
(3) Number of Cusps: cusp is formed by a series of five points p0, p1, p2, p3 and p4, such that angle between p0p1 and p1p2 > 170 degree, angle between p2p3 and p3p4 also > 170 degree, but angle between p1p2 and p2p3 is small.

Ink Related Features
(1) Number of Strokes
(2) Point Density: determine density similar to "o", "b" or "p".

Directional Features
(1) Initial, End and Initial-End Directions: discretize all directions to the nearest of N, NE, E, SE, S, SW, W, NW.

Global Features
(1) Initial and End Position: NE, NW, SE, SW of the bounding box.
(2) Width to Height Ratio: 0 for a slim symbol, 1 for a wide symbol, and 2 for a normal symbol.

Of them, the number of strokes (exact match), the (discretized) width to height ratio (exact match), the initial position (could differ by one), initial to end direction (could differ by one), and end direction (could differ by two) was used to prune models. (Models' feature values are pre-computed and stored.)

After pruning, elastic matching was used for recognition step, achieved by calculating the minimum distance between the unknown symbol and a set of models.

Experiments results show that although using feature to pre-classify lowers accuracy a little bit - while still quite high - the comparison is reduced to a large extent (approximately 89%), thus recognition speed is greatly promoted. And the authors suggest to introcude context and HMM recognizer to reduce ambiguity.


Discussion

I think the really important part in this paper is the introduction of features. Although only several was used, the authors discussed a lot. The geometric features seems to be quite useful if they are used in feature-based recognition. For other features, discrete values are used ignore small errors. This fuzzy logic actually improves recognition accuracy. The suggestion about using context is a good idea in mathemetical handwriting recognition and maybe some other fields.