Efficient search space exploration for sketch recognition
Tevfik Metin Sezgin, Randall Davis · 2004
Why: In online sketching, strokes are put on the sketching surface one at a time. We propose a sketch recognition strategy that takes this incremental nature of the sketching process into account. Current approaches to online sketch recognition apply object recognition methods developed for static images to sketches that are formed in a dynamic, incremental fashion. The incremental nature of sketching necessitates a strategy for assigning image features to model features 1 that keeps the number of ambiguous interpretations minimum, or alternatively, the branching factor of the corresponding interpretation tree low 2 . Otherwise, creating all plausible interpretations that can be generated at a given time may result in too many partial interpretations. How: The approach we take is to analyze object models and derive a recognition strategy specifying the actions to take under different drawing scenarios. The actions that a recognizer can take may include: Checking if certain constraints are satisfied between image features Creating a partial interpretation by assigning an image feature to a model feature Delaying the partial interpretation creation until more strokes are drawn by the user The kinds of analysis include inspection of object descriptions, as well as simulations with hand drawn instances of the object. We conducted a simulation with a hand drawn example to serve as a proof of concept experiment. Our goal was to check if there were ways of filling in image features that minimized the number of partial interpretations created by the time the object is completely drawn. The recognition strategy used in our experiment is a variant of the interpretation tree algorithm. After each stroke is drawn, for each type of object to be recognized: If there are no partial interpretations from the object class we are trying to recognize, and if the geometric primitive derived from the latest stroke fits into a model feature without violating any constraints, create a new partial interpretation with that primitive assigned to the model feature. If there are existing partial interpretations that can be extended with the latest primitive without violating any constraints, these interpretations are cloned and extended. We implemented a stick-figure recognizer using this strategy. We recorded raw strokes for a stick