Automated freehand sketch segmentation using radial basis functions

Freehand sketching is widely regarded as an efficient and natural way for interaction between computers and humans. We present a robust computerized scheme to automatically segment freehand sketches into a series of components with specific geometric meaning regardless of whether these are generated online or offline. This task is a necessary first step toward sketch understanding. By exploiting the interpolation/extrapolation characteristic of radial basis functions (RBFs), a greedy algorithm consisting of forward and backward operations is proposed for finding the minimum set of segmentation points that can be used to reconstruct with high fitting accuracy freehand sketches in the form of implicit functions. To obtain segmentation points, a simple angle-based rule is used to remove "bridging" points that provide a smooth transition between consecutive sketch components. Feasibility of the proposed algorithm is demonstrated by a preliminary performance assessment study using ten computer generated drawings. These experiments show that in this dataset sensitivity of the segmentation was higher than 97.5% with a false positive (FP) rate of approximately 25%. The majority of false positive identifications are located on arc regions where a larger number of segmentation points are needed for reconstruction purposes. The primary contribution of this algorithm is that it transforms an ambiguous problem, namely, freehand sketch segmentation, into an implicit function fitting operation. Therefore, this proposed approach has several advantages, including independence of the actual sketching activity, and the ability for a satisfactory detection of the transition point between a line and an arc or between two arcs. (C) 2009 Elsevier Ltd. All rights reserved.