Mechanix : Sketch Recognition Algorithms for Comparing Complex and Unpredictable Shapes

In this paper, Field et al. discuss their software platform called, "Mechanix" which is designed to help teachers publish and grade course material that students submit to online in the form of sketches.

The main subject domain that their recognition system is used for is in the recognition of free body diagrams, primarily trusses, for engineering courses at Texas A&M (whoop!).

Their recognizer uses a single example provided by a professor, teacher, or TA as the training data that the student's input data (truss drawings) are compared to for grading. Rather than give a confidence or break down the results, the recognizer simply returns a correct or not correct response.

Body Identification
The free body input is also checked to see if the bodies are indeed closed shapes. This is done by traversing the stroke segments' endpoints and finding the closest endpoints to check if those endpoints are within 9% of the total path length to each other. After all end points are checked, the start and end point are checked to see if they are close enough. If all conditions pass, then the shape is closed shape

Body Comparison - Tanimoto + Hausdorff
Field et al.'s algorithm works by preprocessing the stroke for temporal invariance, rotational invariance, scale invariance, and position invariance similar to the preprocessing in $1.

Then, the Tanimoto coefficient, Hausdorff, and Modified Hausdorff distances are computed and combined to give a "matching" or "not matching" response if the confidence is greater than the acceptance threshold of 65%.

Hausdorff Distance:

• Haudorff Distance(A, B) = max(max(Da),max(Db))
• where Da = min (distance from a to b)
•            Db = min (distance form b to a )
• where a and b are points in point vectors Pa and Pb from the input (A) and training (B) points, respectively
• Modified Hausdorff(A,B) = Va + Vb / 2
• where Va = avg(Da)
•           Vb = avg(Db)

Tanimoto Coefficient:

• Normally: T(A,B) = numPts ( A & B ) /  numPts(A) + numPts(B) - numPts(A & B)
• Mechanix: T(A,B) = numPts(A & B) + numPts( B & A) / numPts(A) + numPts(B).

Truss Identification
Trusses are identified by finding intersection that share edges with 3 three distinct paths connecting them.

Field et al. achieved recall rates of 0.991 and a precision of 0.691.
While the precision seems low, but the high recall rates is what is really important since the recognizer needs to be able to verify correctness of the sketches and recognize correct trusses as such.

The high recognition rates for general symbols with Tanimoto and Hausdorff is impressive and its great to see a strong practical application of sketch recognition towards education. Knowing what's important for the domain was a strong point of the paper.

Martin Field, Stephanie Valentine, Julie Linsey, and Tracy Hammond. 2011. Sketch recognition algorithms for comparing complex and unpredictable shapes. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume Three(IJCAI'11), Toby Walsh (Ed.), Vol. Volume Three. AAAI Press 2436-2441. DOI=10.5591/978-1-57735-516-8/IJCAI11-406 http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-406