Reading 2 : Sketch Recognition Algorithms for Comparing Complex and Unpredictable Shapes

Citation:
Sketch recognition algorithms for comparing complex and unpredictable shapes

M Field, S Valentine, J Linsey, T Hammond

IJCAI, 2436-2

Summary:

This paper describes the methods by which unusually shaped bodies are identified and compared. The identification is basically done by constantly trying to combine strokes to form larger shapes. The rest of the paper goes briefly over truss recognition and comparision techniques that were discussed in the Reading 1. This support for unspecified type of diagrams makes the software very flexible and adapt to any new type of diagrams that an instructor may want to assign questions on.

Discussion:

One of the main ideas used in this paper, is that the computation is done online. This basically means that every time a new stroke is made, only combinations including the new stroke need to be analyzed, as combinations excluding it are assumed to have already been performed.

The main concepts discussed here are on identifying and comparing bodies of complex/undefined shapes:

1. Body Identification

This is done by checking for a closed shape first, whereby an arbitrary end point is selected and we traverse along closest end points, until we reach the last segments second point.  This point should be close to the point first selected. The notion of close enough is defined as 9% of the total path length of the strokes.

2. Body Comparision

This step uses a modified version of the template comparison algorithms by Kara and Stockwich(2005), but uses stroke points instead of rasterizing an image. The steps followed here are :

(i)Resample the shape to 64 evenly spaced points (to prevent effect of stroke speed)

(ii)The shapes are scaled uniform to bring them to common bounding box for comparison

(iiI) Now we calculate three parameters - Hausdroff Distance, Modified Hausdroff Distance, and Tanimoto Coefficient. (note that nab is different from nba)
(iv) We use a combination of the three metrics for comparison, and set 0.65 as an acceptance threshold to determine if students sketch matches that of instructor.