MARQS

Brandon Paulson and Tracy Hammond
Journal on Multimodal User Interfaces, October 2007

Summary
MARQS is a dual classifier sketch retrieval system that builds stronger associations with sketches the more it is used. Its principle domain for the paper was for finding personal photos and music albums.
The algorithm is broken down like so:
1- The major axis is calculated by finding the two farthest points away from one another and rotating the sketch to make that axis the horizontal axis
2- Determine the bounding box aspect ratio (width/height)
3- Determine Pixel Density (# of black pixels to # of pixels in bounding box)
4- Determine average curvature to be the values of all the points in all strokes divided by the total sketch length
5- Number of perceived corners via segmentation (refer to “Sketch based interfaces: early processing for sketch understanding by T.M. Sezgin et al.)
6- If only a single example exists then calculate the features and compare to the database examples
7- Calculate the normalized total error
8- Display sketches with lowest errors

This algorithm is able to return the correct sketch in the highest ranking 70% of the time, 87.6% top 2, 95.5% top 3 and 98% top 4 (initially only four returned).

Discussion
This is fascinating to me. The feature set doesn't seem to be that robust, but I guess the capture of curvature and density really return some powerful recognizers. I wonder if center of gravity and area could have as much power? It seemed to me that the pixel density is based on only black and white pictures--sketches. I wonder if the accuracy could be increased by allowing the user to color different lines of the sketch. It might be unreasonable to make the user remember what color they made what lines, but if the user kept it simple then it might not be that difficult.