MARQS

-Brandon Paulson, Tracy Hammond

COMMENTS

1. Comment on Nabeel's blog

SUMMARY

In this paper the authors describe their goal as extending the traditional text-based search to include capabilities of sketch based search which can find documents from a single query search. In the system described, two classifiers have been combined to recognize sketches- (1)A single classifier (a classifier that learns and classifies from a single example to create a sketch system that is immediately usable after a single example; (2)A linear classifier that takes advantage of multiple examples as they become available from queries, creating a sketch that becomes more accurate with use. Both classifiers use the same feature set which is based on global features of the set. The system uses only four global features- (1)Bounding aspect Ratio, (2)Pixel density, (3)Average curvature, (4)Number of perceived corners. Features which would constrain how a user could draw a symbol were not used.
Next, the algorithm is described briefly. When we search a sketch for the first time, a simple classifier is run that calculates the values for features. These features are compared with the sketches in the database. Errors are computed as teh absolute difference between the corresponding features. Normalized errors are then summed up to give total error. Those with lowest errors are displayed in the search results. Once the system has used at least two examples, the linear classifier is used. In order to test the recognition algorithm, MARQS system was implemented. Testing consisted of 1350 different search queries (15 sketches, 9 queries each, 10 tests). The results obtained were very encouraging. 98% of the time the correct sketch was ranked among the top four.
Some shortcomings of the system are slowdown during query time, and reduction in accuracy over time with single classifier. Then some issues of overfitting might occur if the system is repeatedly trained with similar data. Some work may be done to counter this. Another area which could be explored is inputting several sketches at the same time, but that would need perceptual grouping of these strokes.

DISCUSSION

It is amazing that the algorithm works so accurately with just 4 features. The fact that we could draw the sketch in any orientation, of any size and it would still be recognized is something that makes it easy for the user. I think the whole trick was to choose the features carefully, which the authors accomplished successfully. One area were there could be a fault is the reporting of accuracies. In the tests, the classification could result into only 15 classes of sketches. Some combinatorial mathematics tells me that getting the required sketch among the top four retrieved can be achieved randomly with a probability of about 26.7%. So the 98 percent accuracy will have some component of this probability. If I were doing these experiments, I would test it with say 100 sketch classes... where the chances of random success are just 4%.