Sketch Recognition Based on Manifold Learning

Heeyoul Choi, Tracy HammondAAAI 2008

Abstract

Traditional sketch recognition systems have long relied on hand-crafted geometric and temporal features. This paper presents a shift toward automated feature extraction using manifold learning, specifically Kernel Isomap. By treating pen strokes as points on a low-dimensional manifold, the proposed method discovers nonlinear structures that are more robust and less redundant than human-designed features. Experimental results demonstrate a substantial increase in recognition accuracy, particularly for complex mathematical symbols, where accuracy improved from approximately 60% to over 92%.

Introduction

For decades, the standard approach to sketch recognition involved "feature engineering." Researchers identified specific characteristics—such as the angle of a bounding box diagonal or total stroke distance—to describe gestures. However, this manual approach is labor-intensive, sensitive to drawing variations, and often produces highly redundant features. This paper explores whether manifold learning can allow computers to "discover" more efficient, uncorrelated features directly from raw data.

Methodology

The authors employ Kernel Isomap, a manifold learning technique that offers a "projection property," enabling the mapping of new test sketches into a pre-established feature space. The process involves:

  1. Preprocessing: Sketches are normalized to a uniform size and resampled to a fixed number of points ($S$).
  2. Multi-stroke Integration: To handle characters with pen lifts (e.g., '4' or '5'), the algorithm interpolates points to "connect" separate strokes into a continuous path.
  3. Dissimilarity Matrix: A matrix is constructed based on the weighted sum of squared Euclidean distances between corresponding points in sketch pairs. Weights are used to minimize the influence of interpolated "connection" points.
  4. Feature Extraction: Kernel Isomap processes this matrix to produce a compact set of 13 features.

Key Insights: Feature Redundancy

A critical advantage of the manifold learning approach is the reduction of feature redundancy. Traditional methods, like Rubine’s, often produce features that are highly correlated, meaning they provide overlapping information. In contrast, the features extracted via (W)K-Isomap are almost entirely uncorrelated.

Correlation matrices comparing Rubine's features (left) with Isomap features (right). Red indicates high correlation.

This independence ensures that each learned feature contributes unique information to the classifier, leading to a more efficient and powerful representation of the sketch.

Experimental Results

The researchers evaluated the method against the industry-standard Rubine features using a k-Nearest Neighbor (kNN) classifier across three datasets: Alphabets, Digits, and Math Symbols.

Recognition accuracy comparison across three datasets.

The results show consistent improvements across all categories. The most dramatic gain occurred in the Math Symbols dataset, where manifold learning outperformed the traditional method by over 32%. The Weighted K-Isomap (WK-Isomap) variant was particularly effective for digits, likely due to its superior handling of multi-stroke characters.

Conclusion

Manifold learning represents a significant step forward in sketch recognition by automating the discovery of robust, nonlinear features. While the current approach shows great promise, future work is needed to address sensitivities to stroke order and to scale the method for larger, more diverse multi-user datasets.

Summary updated

BibTeX
@inproceedings{choi2008sketch,
  author = {Heeyoul Choi and Tracy Hammond},
  title = {{Sketch Recognition Based on Manifold Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure