Envisioning Sketch Recognition: A Local Feature Based Approach to Recognizing Informal Sketches

Author: Michael Oltmans(thesis)

Comments:
1.Andrew's Blog

Summary:
This is a thesis work on freehand shape recognition. In this thesis, the author has discussed a method to recognize shapes based on the recognition results of the parts constituting the shapes.
Bulls-eye features are used in this method. This is calculated using a circle around interest point and cut into wedges. A vector containing the points which fall in particular wedges is taken as the feature. The circles around the interest point are separated equally in log space.The radius of the circles are chosen in such a way that it covers most of the shape. The inner bins capture more data while the outer bins capture coarse data.
The trajectory of the stroke is used to achieve rotational invariance. Shapes that drawn in the reverse order cannot be recognized. To solve this, bullseye feature for original and the reverse order of the shape is found. There may be errors in finding the bullseye histogram when the strokes are on the boundary. Some points may fall on either side of the boundary. To solve this, the bullseye axis oriented with interest point and rotating extra half a bin turn.
Direction at a point is found by tangent to window of 19 points. The preprocessing steps include resampling stroke for constant spatial frequency(> 1pixel). The author proposes way to calculate distance between the bullseye bins. The bins are also normalized based on the size of the bin. Outer bins hold lesser weights than inner bins. Finally, the result is normalized to 1 to remove the avoid the effect of the differences in total number of points in a region.
This algorithm first performs a clustering based on the bullseye for the training data. Then cluster centers added to a codebook. A match vector is then formed from the codebook which would contain data just enough for classifying shapes.
The algorithm uses support vector machines to differentiate the classes. One Vs One strategy is used to combine binary classfiers. So for n shapes n*(n-1)/2 binary classifiers are used.
For finding shapes in a complete sketch, the isolated shape recognition is run over candidate region. This assigns class labels to the candidate region. Isolated shape reconizers are trained for Wire recognition and also for variation in shapes in the form of change in alignment, inteference from the wire region,... . To give out a final set of predictions, the algorithm needs to first list the set of initial candidates and split the cluster of candidates if they are large.
Results show a 92.3% accuracy in recognizing circuit shapes and 94% recognition on HHreco dataset. The algorithm fails in recognizing symbols that are similar ( capacitor, battery, ground), (Bjt, diode), ... .

Discussion:
I have read 2 completely different approaches in sketch recognition today. One is the constellation method and the other is the bullseye window proposed by this author. These approaches are very different from the traditional approaches.
The results are quite good. The algorithm fails quite rarely in classifying similar shapes. It had worked well in classifying bjt and jfet. I am interested to know if this algorithm could differentiate resistor(zigzag line) and inductor(helix).
I think this algorithm will be very slow, given the number of steps in each section of the algorithm.