Am image based, trainable symbol recognizer for hand-drawn sketches

Characteristics of recognizer

1. Template representation: Uses an image-based recognition system. Input symbols are described as down-sampled bitmap images which we call "templates".

Advantages: Pen stroke segmentation is eliminated.

Suita able for recognizing sketchy symbols

Symbols drawn with multiple strokes or varying orders so not pose difficulty.

2. Learning from a single example: Enables users users to create, extend and update their own library of symbols without the need for extensive training. Single prototype is enough for system to work.

Advantage: users can seamlessly train new symbols.

 remove or overwrite existing ones on the fly

existing symbols do not need to be retrained or adjusted upon the introduction of a new symbol

3. Multiple classifiers: Four classifiers were used in combination which outperforms the individual classifier

4. Achieving rotation invariance invariably: The system uses polar coordinate to determine best alignment angle for comparing. The rotations on screen coordinates become translation using polar coordinates.

5. Two step recognition: Polar coordinates eliminates a large number of unlikely matches. This is followed by a detailed evaluation of the reduced set of candidates in screen coordinates.

6. System Architecture:

Preprocessing: A template is formed of size 48 x 48 preserving the aspect ratio.

Template matching using multiple classifiers

1. Hausdorff distance:

H(A,B) = max(h(A,B), h(B,A)) where h(A,B) = max( min ||a-b||)) - directed hausdorff distance

Maximum of all the distances one can measure from each point in A to closest point in B.

2. Modified Hausdorff distance :

hmod(A,B) = i/N sum(min||a-b||)

N is number of points in A

3. Tanimoto coefficient:

T(A,B) = nab/(na+nb-nab)

where na is total number of black pixels in A

nb = total number of black pixels in B

nab= total number of overlapping black pixels

T(A,B) specifies the number of matching points in A and B, normalized by the union of the two point sets.

maximum similarity = 1

minimum similarity =0

Two pixels are overlapping if they are at a distance of 1/15th of image's diagonal length. For 48 x 48 it is 4.5 pixels.

4. Yule coefficient :

maximum value = 1, minimum value = -1.

Distance transform:

It is a morphological operation that converts a binary bitmap image into an image in which each pixel encodes its distance (we use the Euclidean distance) to the nearest black pixel in the same image. The resulting image is called a distance map. This is done during preprocessing.

Polar coordinates are used to rotate the sketch.

User Studies:

Two experiments: using 20 graphic symbols and digits

Limitation: Insensitive to translation, rotation and uniform scaling but sensitive to non-uniform scaling . Square and rectangle would be treated different. But not always advantageous. For example, a cantilever having different length will be classified as two distinct sketches though practically they are same in most cases.

 Quantization of input into template may wash out minute details