Robust sketched symbol fragmentation using templates

ABSTRACT

Analysis of sketched digital ink is often aided by the division of stroke points into perceptually-salient fragments based on geometric features. Fragmentation has many applications in intelligent interfaces for digital ink capture and manipulation, as well as higher-level symbolic and structural analyses. It is our intuitive belief that the most robust fragmentations closely match a user's natural perception of the ink, thus leading to more effective recognition and useful user feedback. We present two optimal fragmentation algorithms that fragment common geometries into a basis set of line segments and elliptical arcs. The first algorithm uses an explicit template in which the order and types of bases are specified. The other only requires the number of fragments of each basis type. For the set of symbols under test, both algorithms achieved 100% fragmentation accuracy rate for symbols with line bases, ›99% accuracy for symbols with elliptical bases, and ›90% accuracy for symbols with mixed line and elliptical bases.

REFERENCES

• 1: Alvarado, C., Oltmans, M. and Davis, R., A Framework for Multi-domain Sketch Recognition. in 2002 AAAI Spring Symposium - Sketch Understanding, (Palo Alto CA, 2002), AAAI Press, 1--8.
• 2: Ajay Apte , Van Vo , Takayuki Dan Kimura, Recognizing multistroke geometric shapes: an experimental evaluation, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.121-128, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168654]
• 3: Richard Bellman, On the approximation of curves by line segments using dynamic programming, Communications of the ACM, v.4 n.6, p.284, June 1961 [doi>10.1145/366573.366611]
• 4: Calhoun, C., Stahovich, T.F., Kurtoglu, T. and Kara, L.B., Recognizing Multi-Stroke Symbols. in 2002 AAAI Spring Symposium - Sketch Understanding, (Palo Alto CA, 2002), AAAI Press, 15--23.
• 5: Chang, H. and Yan, H. Vectorization of Hand-drawn Image using Piecewise Cubic Bezier Curves Fitting. Pattern Recognition, 31 (11). 1747--1755.
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 7: M A Fischler , R C Bolles, Perceptual organization and curve partitioning, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.1, p.100-105, Jan. 1986 [doi>10.1109/TPAMI.1986.4767756]
• 8: Fonseca, M.J., Pimentel, C. and Jorge, J.A., CALI: An Online Scribble Recognizer for Calligraphic Interfaces. in 2002 AAAI Spring Symposium - Sketch Understanding, (Palo Alto CA, 2002), AAAI Press, 51--58.
• 9: Marti A. Hearst, Sketching Intelligent Systems, IEEE Intelligent Systems, v.13 n.3, p.10-19, May 1998 [doi>10.1109/5254.683174]
• 10: Jason I. Hong , James A. Landay, SATIN: a toolkit for informal ink-based applications, Proceedings of the 13th annual ACM symposium on User interface software and technology, p.63-72, November 06-08, 2000, San Diego, California, United States [doi>10.1145/354401.354412]
• 11: Takeo Igarashi , Satoshi Matsuoka , Sachiko Kawachiya , Hidehiko Tanaka, Interactive beautification: a technique for rapid geometric design, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.105-114, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263525]
• 12: James A. Landay , Brad A. Myers, Sketching Interfaces: Toward More Human Interface Design, Computer, v.34 n.3, p.56-64, March 2001
• 13: James Lin , Mark W. Newman , Jason I. Hong , James A. Landay, DENIM: finding a tighter fit between tools and practice for Web site design, Proceedings of the SIGCHI conference on Human factors in computing systems, p.510-517, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332486]
• 14: James S. Lipscomb, A trainable gesture recognizer, Pattern Recognition, v.24 n.9, p.895-907, 1991 [doi>10.1016/0031-3203(91)90009-T]
• 15: A. Chris Long, Jr. , James A. Landay , Lawrence A. Rowe , Joseph Michiels, Visual similarity of pen gestures, Proceedings of the SIGCHI conference on Human factors in computing systems, p.360-367, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332458]
• 16: Theodosios Pavlidis, Curve Fitting with Conic Splines, ACM Transactions on Graphics (TOG), v.2 n.1, p.1-31, Jan. 1983 [doi>10.1145/357314.357315]
• 17: Pavlidis, T. Structural Pattern Recognition. Springer-Verlag Press, Berlin, 1977.
• 18: Perez, J. and Vidal, E., An Algorithm for the Optimum Piecewise Linear Approximation of Digitized Curves. in 11th IAPR International Conference on Pattern Recognition, (1992), 167--170.
• 19: Andrew Fitzgibbon , Maurizio Pilu , Robert B. Fisher, Direct Least Square Fitting of Ellipses, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.476-480, May 1999 [doi>10.1109/34.765658]
• 20: Dean Rubine, Specifying gestures by example, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.329-337, July 1991
• 21: Eric Saund, Finding Perceptually Closed Paths in Sketches and Drawings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.475-491, April 2003 [doi>10.1109/TPAMI.2003.1190573]
• 22: Eric Saund , Thomas P. Moran, A perceptually-supported sketch editor, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.175-184, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192494]
• 23: Tevfik Metin Sezgin , Thomas Stahovich , Randall Davis, Sketch based interfaces: early processing for sketch understanding, Proceedings of the 2001 workshop on Perceptive user interfaces, November 15-16, 2001, Orlando, Florida [doi>10.1145/971478.971487]
• 24: Shilman, M., Pasula, H., Russell, S. and Newton, A.R., Statistical Visual Language Models for Ink Parsing. in 2002 AAAI Spring Symposium - Sketch Understanding, (Palo Alto CA, 2002), AAAI Press, 126--132.
• 25: Ulgen, F., Flavell, A. and Akamatsu, N., Recognition of On-Line Handdrawn Geometric Shapes by Fuzzy Filtering and Neural Network Classification. in HCI International '95, (Yokohama, Japan, 1995), 567--572.
• 26: G. A. W. West , P. L. Rosin, Techniques for segmenting image curves into meaningful descriptions, Pattern Recognition, v.24 n.7, p.643-652, 1991 [doi>10.1016/0031-3203(91)90031-Y]
• 27: Bo Yu, Recognition of freehand sketches using mean shift, Proceedings of the 8th international conference on Intelligent user interfaces, January 12-15, 2003, Miami, Florida, USA [doi>10.1145/604045.604077]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Edge and feature detection

General Terms:
Algorithms, Human Factors

Keywords:
HCI, curve segmentation, fitting, perceptual grouping, shape templates, sketch-based user interface