"MARQS: Retrieving Sketches Using Domain- and Style-independent Features Learned From a Single Example Using a Dual-classifier"

by Brandon Paulson, Tracy Hammond

Comment
1. Andrew's blog

Summary

In this paper, the authors implemented a search-by-sketch system called MARQS. It 1) recognizes a wide range of shapes that are not necessarily geometric nor drawn in the same way each time, 2) recognize a query example from only one initial training example, and 3) learn from successful queries to improve accuracy over time. MARQS uses two classifiers: 1) Single Classifier: immediate used after a single example and 2) Linear Classifier: improve accuracy over time as more examples are available from queries.

Previous work in feature-based recognizers: Rubine, Long, etc (single stroke), HMM(Hidden Markov Model), however it's style-dependent. Kara & Stahovich, similar to this paper, uses combination of four different recognizers that recognize shapes after only a single example, however, unlike approaches used in this paper, it's not an interactive learning system, and does not learn from future sketches. There are other single-stroke recognizers that use geometric properties instead. Sezgin's system use the process of approximation -> beautification -> basic recognition. Kato's system: create black&white abstraction of full color image, divide into 8*8 blocks and determine local correlation between each block, which are then summed to global correlation to determine similarity.

Recognition algorithm in this paper uses a feature set based on global features of the sketch, allowing them to be drawn to any scale and orientation, in any order, and with multiple strokes. The first step of the algorithm is to find the major axis (line that connects 2 points in a sketch that are furthest apart), and rotate so that axis lies horizontally. Then it uses two classifiers to perform sketch searching. The first one is Single Classifer: errors between features of query and features of sketches in database are calculated, normalized and summed to total error, ranked in increasing order. And the second one is Linear Classifier: implemented in much the same way as that in Rubine's paper, this classifier is used when at least 2 examples for every album in the database. Here, 4 global features are chosen: 1) bounding box aspect ratio 2) pixel density 3) average curvature 4) number of perceived corners across all strokes of the sketch.

Experiment on MARQS: 1350 queries was performed, 27% used Single Classifier with average search rank of 1.7, and 73% used Linear Classifier with average search rank of 1.44. The overall search rank was 1.51. 70% ranked in top 1 and 98% ranked in top 4.

Then the downfalls (slowdown during query time and reduction in accuracy over time with the Single Classifier) are discussed and improvements (generalize feature values of a symbol across all examples of that symbol for comparison, add more features, etc.) are suggested.


Discussion

I think the highlight of the system is the use of two classifiers, which enables "cold startup". But since the Linear Classifier uses Rubine's approach, I wonder if there is such a number of query examples beyond which gives little improvement or even negative effect in accuracy (like in Rubin's work, the number was 15.)

Another thing is that I don't think "pixel density" is a good feature to choose, because for the same picture, larger scale renders smaller pixel density. Thus using this feature means constraint on scales of the sketches.