Adapting Surface Sketch Recognition Techniques for Surfaceless Sketches

1 Introduction andMotivation

People frequently employ sketches on surfaces as a powerful medium to express ideas and concepts, and researchers have made significant strides in developing surface sketch recognition techniques for a wide range of domains. Not limited to surfaces, sketches can additionally extend beyond physical surface environments, with both realized and potential applications for surfaceless sketches that are performed in the air using wireless devices or from limb motions using motion-tracking sensors. Unlike for surface sketches though, recognition techniques for analogous surfaceless sketches are largely unexplored and also highly constrained for similar surfaceless gesture recognition techniques. Furthermore, developing robust recognition techniques for sketches in surfaceless environments are further complicated with challenging properties not inherent with sketches made in surface environments including less precise motion-tracking sensors, unclear states of when sketches begin and end (i.e., the Midas touch problem), physical fatigue in prolonged sketching (i.e., the gorilla arm problem), and so on. Yet in order to develop recognition techniques that perform robustly for surfaceless sketches, they must adequately address the additional challenges posed with the corresponding surfaceless environments.

Since surfaceless sketches share analogous core properties with surface sketches, developing recognition techniques for surfaceless sketches may strongly benefit from taking cues from corresponding surface sketch recognition techniques. In the initial stage of conventional surface sketch recognition, corner-finding recognizers process the raw strokes in the sketch and rely on features and heuristics to locate the corners within those strokes (e.g., ShortStraw [Wolin et al., 2008]). The subsequent stage involves low-level recognizers using information from these located corners to recognize primitive shapes (e.g., PaleoSketch [Paulson and Hammond, 2008]). In the final stage, high-level recognizers make use of the information of these primitive shapes to recognize the larger sketch (e.g., LADDER [Hammond and Davis, 2007]).

While research work for surfaceless sketch recognition techniques are largely lacking, there has been further research work done in different aspects of recognition techniques for related surfaceless gestures. Such research works included directly extending existing gesture recognition from surface environments into its surfaceless analog (e.g., Protractor3D [Kratz and Rohs, 2011]) or recognizing dynamic hand gestures expressed in the air (e.g., Bag-of-Gestures [Ponce et al., 2011]), but such recognition techniques are highly constrained to a limited number of gestures.

2 Accomplishments and Results

In researching the development of robust recognition techniques for surfaceless sketches, I was strongly motivated in exploring the limitations of na¨ıve implementations of existing surface sketch recognition techniques on surfaceless sketches [Taele and Hammond, 2012]. As a result, I utilized a Microsoft Kinect motion-tracking sensor to record surfaceless sketches performed with a user's dominant hand and interactive editing cues performed by the spatial location of the user's non-dominant hand.

Taking analogous cues from surface sketch recognition techniques, I first explored the performance of corner-finding approaches on raw sensor readings of those sketches with state-of-the-art na¨ıve surface sketch corner-finding algorithm ShortStraw and two prevalent na¨ıve corner-finding metrics curvature and speed [Wolin et al., 2008]. I additionally proposed two new corner-finding algorithms that were specifically designed for surfaceless sketches: the BestFit (BF) corner-finder, which is a simplified version of the Sezgin corner-finder [Wolin et al., 2008] that was tuned to noisier motion-tracking data, and the Extended BestFit (BF-E)

corner-finder that uses an ensemble approach of the BF and ShortStraw corner-finding algorithms.

I additionally explored the performance of surface-based primitive shape recognition approaches from the collected corner information of the raw surfaceless sketches, which rely on two key metrics used in state-of-the-art na¨ıve surfacebased primitive shape recognizer PaleoSketch [Paulson and Hammond, 2008]: normalized distance between direction extremes (NDDE) and direction change ratio (DCR), which are effective features in classifying curves (e.g., circles, arcs) and polylines on surface sketches, respectively.

In order to evaluate the performances of corner-finding and primitive shape recognition for surfaceless sketches, I conducted a preliminary study on four engineering graduate students with prior exposure to current-generation motiontracking sensors but no research background in using such sensors. Each user was tasked with naturally sketching ten iterations of seven basic geometric shapes in the air with their dominant hand: arc, circle, curve, ellipse, one-, two- , and three-stroke line. Prior to performing the study, users were given several minutes to familiarize themselves with the sketching and interaction cues. Corner-finding performance was evaluated with both the previously-described conventional and modified corner-finding approaches, while primitive shape extraction was evaluated from the previouslydescribed conventional surface-based metrics. Accuracies of the users' collected surfaceless sketch data were calculated with all-or-nothing recognition using leave-one-out crossvalidation (Figure 1).

3 Discussion and Future Directions

From the corner-finding evaluation, the na¨ıve surface sketch recognition techniques performed relatively much poorer to the initial surfaceless sketch recognition ones: the BF algorithm achieved the best performance with a wide margin over the other evaluated corner-finders for curved shapes (i.e., arc, circle, curve, ellipse), with misclassifications stemming from false positives where curved shapes were sometimes approximated as polylines; and the BF-E algorithm performed best for polyline shapes. For the evaluation of the primitive shape extraction, NDDE and DCR features performed with mixed results compared to very high accuracies for surface sketches [Paulson and Hammond, 2008]. While these preliminary findings strongly suggest that low-level surface sketch recognition techniques and features for surfaceless sketches perform poorly in corner-finding and with mixed results for primitive shape extraction, better accuracy results from the proposed basic surfaceless counterparts demonstrated strong potential in instead adapting surface sketch recognition techniques to surfaceless environments.

Motivated by these findings, one future research direction involves a more expansive collection of surfaceless sketch data. Data repositories currently exist for surface sketches, but is lacking for sketches made in surfaceless environments, so it would be greatly beneficial to create such a repository incorporating more diverse users performing surfaceless sketches in greater quantity, in wider variety, and with different input methods (e.g., with a wireless device, with motiontracked limbs). A related follow-up research direction involves developing more refined proposed surfaceless sketch recognition techniques that would be evaluated on this expanded data collection for corner-finding, primitive shape extraction, and compound shape recognition. One additional research direction would also involve addressing indirect sketch recognition issues in surfaceless environments such as the Midas Touch and gorilla arm problems.