Homework 3 - Recognition

Overview
For the third and final homework assignment, before we turn our attention to the project, we will look at building sketch recognition algorithms.  By now you have implemented feature extraction and corner-finding/segmentation methods.  We will build on this experience to perform recognition.

Instructions
Languages and Data
As in Homework 2, you are not required to use any specific language, but the data is only available via the Sketch Recognition Library Database (srlib_db), so you will at least need to make calls to the service and parse the JSON files.  If you have completed Homework 2 in any language, you will have code to handle these operations.

The data handlers for srlib_db are available in Javascript via srlib_js, which is included in a limited form in the Starter code available on the class drive under "Homework 3".  The documentation for srlib_js is also included in "srlib_jsdoc"; it is a JSDoc directory and should be downloaded and read through a web browser by opening the "index.html" inside "srlib_jsdoc".

The specification of SketchML::JSON, which is the format of all sketches on srlib_db, is also available in the homework's folder.  If you wish to use another language, that will be a useful reference, but any language that handles JSON-like objects natively will be easy to adapt.

Recognition

The goal of this assignment is that, given a set of processed strokes, you can group them into meaningful, recognized shapes.  Specifically, you should be able to recognize "arrow" and "truss" shapes from the substrokes.  You may use your pre-existing code for feature extraction and segmentation (from Homeworks 1 and 2, respectively) if you wish.  Alternatively, you may directly use the substrokes provided by the Mechanix data; for this assignment, only the shape data has been removed, while both shapes and substrokes were removed in the previous assignment.  As mentioned in the previous assignment, if you performed some additional effort in Homework 2 to identify nodes, that could be useful in your recognition of trusses in this assignment if you want to use your own segmenter.

You may implement any recognition method you like except template matching.  Such a method does not scale to trusses of any number of nodes, nor does it handle the many variations of drawing arrows very well.  It may be possible to perform fairly well in this specific domain on very specific examples with template matching, but it is heavily discouraged because of the lack of scalability.  We will be covering more recognition methods over the next two weeks in class, and you are encouraged to explore your own ideas for sketch recognition algorithms.  Any exploration and implementation you do during this assignment will likely benefit your final project.

As before, evaluation code and details will be shared soon.  Placeholder text has been added to the Starter code so that only the function will need to be added.  Your shapes will be evaluated against other types of shapes (e.g. triangles, letters, generic closed bodies, etc.), so be sure your algorithm is robust enough to detect true negatives.  That is, do not assume that you can label every shape as an arrow or a truss simply because there are so many in the Mechanix data; that will lead to many false positives on test data.

Starter Code

As with Homeworks 1 and 2, there is provided Starter code in the directory for Homework 3.  This file already handles loading data and converting it into the appropriate format.  It also visualizes the original sketch data, prefixed "old", and your sketch data, prefixed "new", according to either the substrokes or shapes.

When plotting substrokes, each substroke is assigned a random color to easily differentiate them on the canvas.  Substrokes are identical for "old" and "new" in the current version, as strokes were in the previous homework, although you may use your own segmenter if desired.  When plotting shapes, the entire shape is given the same random color.  The "old" sketches will have correctly segmented (by Mechanix) shapes, which will be the basis for comparison of your "new" sketch shapes.  The Starter code simply makes all substrokes part of one shape at the moment in order to demonstrate some useful functions of srlib_js.  Once finished, your "new" sketches should also feature multiple shapes for the different recognized objects.

Note that Mechanix sketches can be large and may get cut off by the canvas.

Obtaining Credit

Again, the goal of this assignment is that you write sketch recognition algorithms for arrows and trusses.  You will need to submit all of your source files to the grader.  Also, include a small report describing what algorithm you implemented, the intuition of how it works, and the most difficult problems you encountered.  If you run the metrics code, include those numbers as well.

Please ZIP all your files together into a single file submission titled "HW3_<last name>_<first initial>.zip".  Since the university may block ZIP files, it is recommended that you upload your file to Google Drive and share the link via email.

More details will follow regarding the evaluation metrics.  Remember to keep false positives and true negatives in mind so that your algorithm can perform well on general test data.

This homework may seem large, but given the previous experience and code you've developed from homeworks 1 and 2, it should be quite manageable.  You will have approximately two weeks to complete the assignment before we switch over to project-centered tasks for the final half of the class.

Due Date
Nov. 2, Wednesday @ Midnight (extended from Oct. 26)
25% deducted per day late